Курсовая работа: Логическое проектирование и минимизация

В настоящее время всё большее количество студентов получает доступ к персональным компьютерам. Возрастает количество компьютеров на кафедрах и в лабораториях институтов, растёт и число студентов, имеющих компьютеры дома.

Следовательно российские учебные заведения уже заинтересованы в появлении компьютерного лабораторного практикума. Таким образом объективные экономические причины для разработки компьютерного моделирования лабораторных работ уже есть.

В этой связи имеет смысл начать разработку моделирования лабораторных работ средствами вычислительной техники, тем более что программы появляющиеся на российском рынке программного обеспечения позволяют сделать это моделирование не менее наглядным чем работа на реальных стендах.

1. Обзор методов логического проектирования и минимизации

Термин “логическое проектирование” охватывает целый комплекс проблем, возникающих на одной из ранних стадий создания цифрового автомата. Одним из этапов логического проектирования является синтез его так называемых комбинационных устройств, который заключается в определении таких способов соединения некоторых простейших схем, называемых логическими элементами, при которых построенное устройство реализует поставленную задачу по преобразованию входной двоичной информации. В частности логическими элементами являются инвертор, конъюнктор и дизъюнктор. Поскольку эти элементы образуют функционально полный набор, то с их помощью можно построить комбинационное устройство (то есть устройство не обладающее памятью, в котором выходной сигнал в любой момент времени определяется только комбинацией входных сигналов), реализующее любой наперёд заданный закон преобразования двоичной информации .

Обычно логическое проектирование выполняется в следующей последовательности:

1) составление таблицы истинности синтезируемого узла согласно его определению, назначению и (словесному) описанию принципа работы ;

2) составление математической формулы для логической функции, описывающей работу синтезирующего узла, согласно имеющейся таблице истинности ;

3) анализ полученной функции с целью построения различных вариантов её математического выражения (на основании законов булевой алгебры) и нахождения наилучшего из них в соответствии с тем или иным критерием ;

4) составление функциональной (логической) схемы узла из заранее заданного набора логических элементов .

1.1 Нормальные формы логических функций

Синтез комбинационных устройств обычно начинается с табулирования значений истинности всех входных и выходных величин. Табличное задание закона функционирования некоторого устройства является наиболее наглядным и универсальным средством описания его работы. Результатом рассматриваемого этапа является таблица истинности, связывающая все возможные комбинации значений аргументов и функций. Пусть, например, требуется синтезировать цифровое устройство, реализующее сложение двух двоичных цифр (полусумматор) .

1-й этап синтеза - даётся словесное описание полусумматора и принципа его работы. Он должен анализировать все комбинации входных сигналов (т. е. двоичных цифр 00, 01, 10, 11) и в соответствии с ними формировать на выходе двухразрядные суммы. В первом разряде результата формируется цифра переноса, а во втором - цифра многоразрядной суммы. Следовательно, синтезируемый полусумматор должен иметь два входа (n=2) и два выхода. Далее от нестрогого словесного описания переходим к строгому формальному описанию работы полусумматора на табличном языке. Таблица истинности (см. табл. 1.1) в общем случае при n входах имеет 2 в степени n комбинаций значений аргументов .

Таблица 1.1

Таблица истинности полусумматора.

1-я цифра слагаемое Х1	0	0	1	1
2-я цифра слагаемое Х2	0	1	0	1
Цифра переноса р	0	0	0	1
Цифра суммы s	0	1	1	0

2-й этап синтеза - для того чтобы показать методику перехода от таблицы истинности к аналитическому выражению, рассмотрим некоторую обобщённую таблицу истинности двух аргументов f(X1,X2) (см. табл. 1.2). Ограничение на число аргументов не является в данном случае существенным, но значительно упрощает все рассуждения .

Таблица 1.2

Обобщённая таблица истинности функции двух аргументов.

1-й логический аргумент Х1	0	0	1	1
2-й логический аргумент Х2	0	1	0	1
Логическая функция f(X1,X2)	f0	f1	f2	f3

Здесь f0=f(0,0) ; f1=(0,1) ; f2=(1,0) ; f3=(1,1) - конкретные реализации функции f(X1,X2) при определённых частных значениях аргументов X1 и X2 . Они также являются двоичными переменными. Десятичные индексы при их символах числено равны тем двоичным числам, которые образуются соответствующими частными значениями аргументов. Кроме того, каждый десятичный индекс можно трактовать как номер некоторого столбца в Таблице 1.2, изменяющийся в пределах от 0 до 2ⁿ -1, так как обычно значения аргументов в таблице записываются таким образом, чтобы получающееся из них по вертикали двоичное число было равно номеру столбца. Исходя из вышеизложенного, уже можно перейти от табличной записи логической функции f(X1,X2) к аналитической :

f(X1,X2) = f₀ при, х₁ =0, х₂ =0 ;

f₁ при, х₁ =0, х₂ =1 ; (1.1)

f₂ при, х₁ =1, х₂ =0 ;

f₃ при, х₁ =1, х₂ =1 ;

Такая запись несколько удобнее и компактнее таблицы, однако она всё-таки громоздка и плохо обозрима (особенно в случае большого числа аргументов). Но от неё можно перейти к записи другого вида, более удобной и компактной :

f(x₁ ,x₂ ) = x₁ x₂ f₀ + x₁ x₂ f₁ + x₁ x₂ f₂ + x₁ x₂ f₃ (1.2)

Правило построения каждого члена в этом предложении несложно; производится логическое умножение элементов каждого столбца табл.1.2, причём вместо 1 берётся символ соответствующего аргумента, а вместо 0 - его отрицание. Равносильность соотношений (1.1) и (1.2) простой подстановкой в выражение (1.2) всех возможных комбинаций значений аргумента x_i .

Обобщив вышеизложенное можно сформулировать правило получения аналитической записи логической функции для некоторого комбинационного узла :

- для того чтобы получить аналитическое выражение функции, заданной таблично, нужно составить сумму конституент(см. ниже) единицы для тех наборов значений входных двоичных переменных, для которых реализации функции f_i равны 1, причём символ любой переменной в некоторой конституенте берётся со знаком отрицания, если конкретное значение переменной x_i в рассматриваемом наборе имеет значение 0 .

Поскольку логическая сумма всех элементарных произведений наивысшего ранга n обязательно равна 1, какой бы набор значений входных переменных ни рассматривался, то эти произведения вполне логично называть конституентами (составляющими) единицы . Аналогично объясняется и название конституенты (составляющей) нуля, так как известно, что логическое произведение всех элементарных сумм наивысшего ранга тождественно равно нулю .