Проектирование цифрового комбинационного устройства - кодопреобразователя, реализующего шифр простой замены, с элементами функционального контроля

Изм.

Лист

№ Документа



Подпись

Дата



Лист

3









КубГТУ 100303.17.ПЗ









Разработал

Соколов П.А.

Проверил

Тельнов Г.В.









Утвердил











Цифровое

устройство

Литер

Листов

62













гр. 14-К-АС1













1КГТУ07-К

ИБ1











ЛИСТ

9









КубГТУ 100303.17.ПЗ

Изм.

№ документа

Лист

Подпись

Дата





















	Реферат

	

	Курсовой проект содержит: 62 с., 15 рис., 13 табл., 7 источников, 10 приложений, иллюстративная часть – 10 листов формата А4.

	

	ЦИФРОВОЕ  КОМБИНАЦИОННОЕ  УСТРОЙСТВО,  ЛОГИЧЕСКИЙ СИНТЕЗ,  КАРТА  КАРНО,  МИНИМИЗАЦИЯ  БУЛЕВЫХ  ФУНКЦИЙ,  МИНИМИЗАЦИЯ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ, ФУНКЦИОНАЛЬНЫЙ БАЗИС  ЦИФРОВОЙ  СХЕМОТЕХНИКИ,  ВЫБОР  И  ОБОСНОВАНИЕ ПРИМЕНЯЕМОЙ  СЕРИИ  МИКРОСХЕМ,  СТРУКТУРНАЯ, ФУНКЦИОНАЛЬНАЯ  И  ПРИНЦИПИАЛЬНЫЕ  СХЕМЫ,  РАСЧЕТ ЭНЕРГОПОТРЕБЛЕНИЯ  И  БЫСТРОДЕЙСТВИЯ,  РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ.

	

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




Содержание



	Нормативные ссылки	6

	Термины и определения	7

	Сокращения	8

	Введение	9

	1  Общая характеристика шифров замены	10

		2  Обоснование метода повышения достоверности	12

	3  Формализация исходных данных. Составление таблицы входов и выходов	13

	4  Выбор структуры и алгоритма функционирования кодопреобразователя	17

		4.1 Структурная схема кодопреобразователя	17

	4.2 Статическое описание структуры и назначения составных узлов кодопреобразователя	18

	4.3 Динамическое описание кодопреобразователя, блок схема алгоритма функционирования кодопреобразователя	19

	5  Минимизация системы булевых функций	21

	5.1 Методы минимизации булевых функций, выбор и обоснование метода минимизации	21

	5.2 Минимизации каждой булевой функции-выходов кодопреобразователя...	22

	5.3 Минимизация системы булевых функций-выходов кодопреобразователя.	26

	6  Выбор и обоснование применяемого логического базиса. Преобразование бу-                         левых функций к выбранному логическому базису	30

	6.1 Понятие функционально-полного логического базиса, вид функционально-полных логических базисов	30

	6.2 Методы преобразования булевых функций к заданному логическому бази-           су. Выбор метода преобразования	32

	6.3 Преобразование булевых функций к выбранному логическому базису	34

	7  Обоснование выбора серии ИМС	36

	7.1 Методика выбора серии ИМС	36

	7.2 Характеристика выбранной серии ИМС, условное графическое 
обозначение элементов выбранной серии и их основные параметры.	39

	8  Разработка функциональной схемы кодопреобразователя.	43

	8.1 Функциональная схема комбинационного устройства	43

	8.2 Функциональная схема входного и выходного регистров	43

	8.3 Функциональные схемы узлов проверки на четность и формирование контрольного бита четности	43

	8.4 Функциональная схема цифрового устройства - кодопреобразователя	43

	9  Компьютерное моделирование спроектированного комбинационного 
устройства.	44

	9.1 Разработка и описание функциональной модели комбинационного 
устройства в среде компьютерного моделирования ElectronicsWorkbench	44

	9.2 Результаты моделирования и их анализ.	45

	10  Принципиальная схема комбинационного цифрового устройства..	46

	11  Расчет технических характеристик спроектированного цифрового 
устройства.	47

		11.1 Расчет, объема аппаратурных затрат.	47

		11.2 Расчет энергопотребления.	47

		11.3 Расчет быстродействия	47

	Заключение	50

	Список использованных источников	51

	Приложения	52



	




Нормативные ссылки



        Курсовой проект основан на следующих стандартах, регламентирующих оформление текстовых документов: 

ГОСТ 2.702-2011 ЕСКД. Правила выполнения электрических схем; 

ГОСТ 2.1004-88 ЕСКД. Общие требования к выполнению конструкторских технологических документов на печатающих и графических устройствах вывода ЭВМ; 

ГОСТ 2.104-2006 ЕСКД. Основные надписи; 

ГОСТ 2.721-74 ЕСКД. Обозначения условные графические в схемах. Обозначения общего применения; 

ГОСТ 2.755-87 ЕСКД. Обозначения условные графические в электрических схемах. Устройства коммутационные и контактные соединения; 

	ГОСТ 2.301-68 ЕСКД Форматы. 	



	








Термины и определения



       В курсовом проекте применены следующие термины с соответствующими определениями: 

       1. Булева функция: Функция, аргументы и значение которой принадлежит множеству {0, 1}. 

       2. Дизъюнктор: Цифровое логическое устройство, реализующее функцию дизъюнкции 

       3. Задержка распространения сигнала: Время прохождения сигнала от передатчика до приемника. 

       4. Инвертор: Цифровое логическое устройство, реализующее функцию инверсии. 

       5. Контрольный бит: Разновидность контрольной суммы, добавляется обычно в конец номеров с целью первичной проверки их правильности. 

       6. Конъюнктор, схема совпадения: Цифровое логическое устройство, реализующее функцию конъюнкции. 

       7. Минтерм: Булева функция, принимающая истинное значение лишь при одной-единственной комбинации своих аргументов. 

       8. Регистр: Последовательное или параллельное логическое устройство, используемое для хранения n-разрядных двоичных чисел и выполнения преобразований над ними. 

        9. Синхровход: Вход регистра, отвечающий за синхронизацию. 

       10. Триггер: Устройство, обладающее способностью длительно находиться в одном из двух устойчивых состояний и чередовать их под воздействием внешних сигналов. 

       11. Энергопотребление: Количество энергоресурсов необходимое и достаточное для обеспечения технологического процесса при заданных параметрах производства и окружающей среды. 



Сокращения



В курсовом проекте приняты следующие сокращения: 

ДНФ – нормальная дизъюнктивная форма;

СДНФ – совершенная нормальная дизъюнктивная форма; 

ЛЭ – логический элемент;

ФАЛ – функция алгебры логики;

БФ – булева функция;

ИМС – интегральная микросхема; 

ЛС – логическая схема; 

ЛЭ – логический элемент; 

ЭиС – электроника и схемотехника; 

ТТЛШ – транзисторно-транзисторная логика с применением диодов Шоттки; 

ТТЛ - транзисторно-транзисторная логика;

ЭСЛ – эмиттерно-связная логика;

КМОП - комплементарный металлооксидный полупроводник;

ЕСКД - Единая система конструкторской документации;

EWB – Electronics Workbench




Введение



     Необходимость в преобразовании по произвольному правилу m-разрядных чисел одной двоичной системы в m-разрядные числа другой системы существовала ещё до появления средств вычислительной техники и решение данной задачи затрачивало большое количество времени. В современных условиях эта задача решается с помощью устройств, называемых кодопреобразователями, которые в свою очередь состоят из логических элементов. Логические элементы образуют универсальную среду, обеспечивающую арифметическую и логическую обработку входной двоичной информации, что позволяет применять их для решения любых логических задач. 

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

     Объектом исследования является дискретный автомат - кодопреобразователь. Сущность кодопреобразования заключается в том, что каждой комбинации одного кода ставится во взаимно однозначное соответствие определённая комбинация другого кода. 

      Предметом исследования является проектирование цифрового комбинационного устройства - кодопреобразователя, реализующего шифр простой замены, с элементами функционального контроля. 

      Цель разработки курсового проекта – закрепить знания, полученные в ходе изучения курса «Электроника и схемотехника» и привить навыки выполнения курсовых работ, проведения научных исследований и моделирования цифровых устройств. 



1 ОБЩАЯ ХАРАКТЕРИСТИКА ШИФРОВ ЗАМЕНЫ

Наиболее известными и часто используемыми шифрами являются шифры замены. Они характеризуются тем, что отдельные части сообщения (буквы, слова) заменяются на какие-либо другие буквы, числа, символы и т.д. При этом замена осуществляется так, чтобы потом по шифрованному сообщению можно было однозначно восстановить передаваемое сообщение. 

Пусть, например, зашифровывается сообщение на русском языке и при этом замене подлежит каждая буква сообщения. Формально в этом случае шифр замены можно описать следующим образом. Для каждой буквы «а» исходного алфавита строится некоторое множество символов  так, что множества  и  попарно не пересекаются при «а» не равном «б», то есть любые два различные множества не содержат одинаковых элементов. Множество  называется множеством шифр обозначений для буквы «а» [1].

Ключ шифра замены представлен в таблице 1.1. Зная эту таблицу, можно осуществить как шифрование, так и расшифровывание.



    Таблица 1.1 Ключ шифра замены 



  а

  б

  в

.…

  я







….





При шифровании каждая буква «а» открытого сообщения, начиная с первой, заменяется любым символом из множества . Если в сообщении содержится несколько букв «а», то каждая из них заменяется на любой символ из . За счет этого с помощью одного ключа (таблица 1.1) можно получить различные варианты зашифрованного сообщения для одного и того же открытого сообщения. 

Рассмотрим пример. Ключ шифра замены рассматриваемого примера представлен в таблице 1.2.



   Таблица 1.2 Ключ шифра замены рассматриваемого примера

а

б

в

г

д

е

ж

з

и

к

л

м

н

о

п

33

14

77

45

65

22

86

35

64

87

13

75

30

80

11

р

с

т

у

ф

х

ц

ч

ш

щ

ы

ь

э

ю

я

55

76

90

41

89

52

85

27

22

66

19

67

37

54

99











Таблица 1.3 Зашифрованная запись сообщения «я сдам электротехнику на отлично»          Зашифрованная запись сообщения «я сдам электротехнику на отлично» представлена в таблице 1.3



я

с

д

а

м

э

л

е

к

т

р

о

т

е

х

99

76

65

33

75

37

13

22

87

90

55

80

90

22

52

н

и

к

у

н

а

о

т

л

и

ч

н

о

30

64

87

41

30

33

80

90

13

64

27

30

80























	      2 ОБОСНОВАНИЕ МЕТОДА ПОВЫШЕНИЯ ДОСТОВЕРНОСТИ



При передаче дискретных сообщений всегда возникают ошибки, обусловленные несовершенством систем передачи дискретной информации (ПДИ), систем коммутации (мультиплексирования), каналов связи и др. Причины их могут быть самые различные, но результат оказывается один - появляющиеся ошибки снижают верность принятых сообщений. В то же время высокая верность передачи – основное требование к системам ПДИ, и ее снижение недопустимо. 

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

Очень часто верность передачи оказывается ниже требуемой. Поэтому необходимо принять меры по повышению верности. Один из методов повышения верности принимаемых сообщений основан на улучшении качественных показателей каналов, что достигается обычно либо устранением самих причин появления ошибок, либо включением в канал некоторых дополнительных устройств, уменьшающих влияние помех. Следует заметить, что улучшение качественных характеристик каналов с целью повышения «верности» приема всегда связано с определенными материальными затратами, которые в ряде случаев могут оказаться весьма высокими. 

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

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

1.  Кодовая комбинация – набор из символов принятого алфавита.

2. Код – совокупность кодовых комбинаций, используемых для отображения информации.

3.  Кодовое расстояние между двумя кодовыми комбинациями – число разрядов, в которых эти комбинации отличаются друг от друга.

4.  Минимальное кодовое расстояние – минимальное кодовое расстояние для любой пары комбинаций, входящий в данный код.

5.   Кратностью ошибки называют число ошибок в данном слове (число неверных разрядов).

Чтобы получить возможность обнаруживать хотя бы ошибки единичной кратности, необходимо увеличить минимальное кодовое расстояние на 1. Это и составляет сущность и основную идею для кода с контролем по модулю 2 (контроль «четности/нечетности»). 

При этом способе контроля каждое слово дополняется контрольным разрядом, значение которого подбирается так, чтобы сделать четным (нечетным) вес каждой кодовой комбинации. 

При одиночной ошибке в кодовой комбинации четность (нечетность) ее веса меняется, а такая комбинация не принадлежит к данному коду, что и обнаруживается схемами контроля. 

При двойной ошибке четность (нечетность) комбинации не нарушается - такая ошибка не обнаруживается. Легко можно заметить, что у кода с контрольным разрядом минимальное кодовое расстояние равно двум. 

В простейшем случае телеграфный пятиразрядный код преобразуется в избыточный, если к первичной комбинации прибавить еще один разряд, но так, чтобы число единиц в кодовой комбинации стало четным. Например, буквам А, Б и В телеграфного кода будут соответствовать кодовые комбинации 110000, 100111, 110011, в которых шестой разряд является проверочным. Таким образом, в кодовых комбинациях часть разрядов используется в качестве информационных, а часть (в данном случае шестой разряд) — в качестве проверочных. Если при передаче в линии произошла одиночная ошибка, например в комбинации буквы Б во втором разряде (110111), то специальное устройство в приемнике обнаружит эту ошибку, поскольку число единиц стало нечетным. Отсюда следует, что избыточные коды всегда содержат избыточную информацию (разряды), которая и позволяет обнаружить ошибку. Количество избыточной информации в кодовой комбинации равно числу дополнительных разрядов. Остальную информацию, в отличие от избыточной, называют полезной информацией. Устройства, которые предназначены для повышения, верности с помощью избыточных кодов, называются устройствами защиты от ошибок.  



























ФОРМАЛИЗАЦИЯ ИСХОДНЫХ ДАННЫХ. СОСТАВЛЕНИ

ТАБЛИЦЫ ВХОДОВ И ВЫХОДОВ



На основе полученного индивидуального задания составим таблицу входов и выходов цифрового устройства - преобразователя, которая отражает логику ее функционирования, используя при этом десятичную и шестнадцатеричную системы счисления. 

Исходные данные индивидуального задания представлены в таблице 3.1.

Таблица 3.1 – Исходные данные индивидуального задания

Входной алфавит (входной код)

24

7

0

30

11

21

25

10

2

3

6

4

5

27

16

14

Выходной алфавит (выходной код)

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F



	Исходя из исходных данных, заметим различие входного и выходного алфавитов.

	Далее составим подробную таблицу функционирования проектируемого устройства – таблицу входов и выходов кодопреобразователя с учетом двоичного представления символов входного и выходного алфавитов и наличия контроля четности входного и выходного бита контроля четности входной и выходной кодовой комбинации. 

	Сформируем контрольный бит следующим образом:

	Пусть на вход устройства подано пять информационных бит: , , , , . Тогда контрольный бит формируется при выполнении операции "Исключающее - ИЛИ" (сумма по модулю 2, операция XOR) поразрядно. В данном случае контрольный бит будет равен: . Аналогично контрольный бит формируется на выходе устройства, применением операции "Исключающее - ИЛИ" к разрядам выходного кода.

	Формализованное представление входных и выходных исходных данных проектируемого устройства приведено в таблице 3.2. 

	

	Таблица 3.2 – Формализованное представление входных и выходных исходных данных проектируемого устройства

	№

	п/п

	Входная информация

	Выходная информация

	

Входной

символ

Разряды

входного кода

Контроль-

ный бит

Выходной

символ

Разряды

выходного кода

Контроль-

ный бит

	



























	0

	0

	0

	0

	0

	0

	0

	0

	2

	0

	0

	1

	0

	1

	1

	

	0

	0

	0

	0

	1

	1

	

	Ф

	Ф

	Ф

	Ф

	Ф

	2

	2

	0

	0

	0

	1

	0

	1

	8

	1

	0

	0

	0

	1

	3

	3

	0

	0

	0

	1

	1

	0

	9

	1

	0

	0

	1

	0

	4

	4

	0

	0

	1

	0

	0

	1

	B

	1

	0

	1

	1

	1

	5

	5

	0

	0

	1

	0

	1

	0

	C

	1

	1

	0

	0

	0

	6

	6

	0

	0

	1

	1

	0

	0

	A

	1

	0

	1

	0

	0

	7

	7

	0

	0

	1

	1

	1

	1

	1

	0

	0

	0

	1

	1

	8

	

	0

	1

	0

	0

	0

	1

	

	Ф

	Ф

	Ф

	Ф

	Ф

	9

	

	0

	1

	0

	0

	1

	0

	

	Ф

	Ф

	Ф

	Ф

	Ф

	10

	10

	0

	1

	0

	1

	0

	0

	7

	0

	1

	1

	1

	1

	11

	11

	0

	1

	0

	1

	1

	1

	4

	0

	1

	0

	0

	1

	12

	

	0

	1

	1

	0

	0

	0

	

	Ф

	Ф

	Ф

	Ф

	Ф

	13

	

	0

	1

	1

	0

	1

	1

	

	Ф

	Ф

	Ф

	Ф

	Ф

	14

	14

	0

	1

	1

	1

	0

	1

	F

	1

	1

	1

	1

	0

	15

	

	0

	1

	1

	1

	1

	0

	

	Ф

	Ф

	Ф

	Ф

	Ф

	16

	16

	1

	0

	0

	0

	0

	1

	E

	1

	1

	1

	0

	1

	17

	

	1

	0

	0

	0

	1

	0

	

	Ф

	Ф

	Ф

	Ф

	Ф

	18

	

	1

	0

	0

	1

	0

	0

	

	Ф

	Ф

	Ф

	Ф

	Ф

	19

	

	1

	0

	0

	1

	1

	1

	

	Ф

	Ф

	Ф

	Ф

	Ф

	20

	

	1

	0

	1

	0

	0

	0

	

	Ф

	Ф

	Ф

	Ф

	Ф

	21

	21

	1

	0

	1

	0

	1

	1

	5

	0

	1

	0

	1

	0

	22

	

	1

	0

	1

	1

	0

	1

	

	Ф

	Ф

	Ф

	Ф

	Ф

	23

	

	1

	0

	1

	1

	1

	0

	

	Ф

	Ф

	Ф

	Ф

	Ф

	24

	24

	1

	1

	0

	0

	0

	0

	0

	0

	0

	0

	0

	0

	25

	25

	1

	1

	0

	0

	1

	1

	6

	0

	1

	1

	0

	0

	26

	

	1

	1

	0

	1

	0

	1

	

	Ф

	Ф

	Ф

	Ф

	Ф

	27

	27

	1

	1

	0

	1

	1

	0

	D

	1

	1

	0

	1

	0

	28

	

	1

	1

	1

	0

	0

	1

	

	Ф

	Ф

	Ф

	Ф

	Ф

	29

	

	1

	1

	1

	0

	1

	0

	

	Ф

	Ф

	Ф

	Ф

	Ф

	30

	30

	1

	1

	1

	1

	0

	0

	3

	0

	0

	1

	1

	0

	31

	

	1

	1

	1

	1

	1

	1

	

	Ф

	Ф

	Ф

	Ф

	Ф







ВЫБОР СТРУКТУРЫ И АЛГОРИТМА ФУНКЦИОНИРОВАНИЯ КОДОПРЕОБРАЗОВАТЕЛЯ



4.1  Структурная схема кодопреобразователя



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

	 Структурная схема кодопреобразователя представлена на рисунке 4.1

	

	Рис. 4.1 – Структурная схема кодопреобразователя







4.2  Статическое описание структуры и назначения составных узла

кодопреобразователя



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

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

Выходная шина содержит 4 информационных входа, один вход контрольного бита (контроль по четности), и один выход сигнала управления «ошибка, контроль записи».

       Входной регистр RG1 предназначен для записи и хранения 5 информационных бит, одного бита контроля по четности, и состоит из 6 элементов памяти (триггеров).

Выходной регистр RG2 предназначен для записи и хранения 4-х информационных бит, одного бита контроля по четности, и состоит из 5 элементов памяти (триггеров).

Входной и выходной узлы контроля по четности представляют собой соответственно 6-входовой и 4-входовый сумматоры по модулю 2, и предназначены для контроля достоверности входных информационных сигналов и формирования контрольного бита выходных информационных сигналов.

Комбинационное цифровое устройство представляет собой цифровой автомат без памяти и предназначено для преобразования входных данных представленных с помощью алфавита зашифрованного текста символами, взятыми из множества {0, …, 31} мощности 16, в выходные данные  (открытый текст), алфавит которого представлен символами множества {0, …, 15} мощности 16.

4.3 Динамическое описание кодопреобразователя, блок схема алгоритма функционирования кодопреобразователя

        Кодопреобразователь работает следующим образом.

        Начало функционирования спроектированного устройства совпадает с поступлением на соответствующий управляющий вход сигнала «сброс», который устанавливает регистры RG1 и RG2 в исходное состояние (нулевое при использовании прямой логики и единичное при использовании инверсной логики).

С поступлением первого синхроимпульса (по спаду или фронту) входное кодовое слово (6 бит) записывается во входной регистр RG1, с выхода которого сигнал поступает на входы входного узла контроля по четности и входы комбинационного цифрового устройства.

Если во входном кодовом слове ошибка не обнаружена, то через интервал времени, необходимый для формирования устойчивого сигнала – результата преобразования на выходе комбинационного цифрового устройства, на управляющий вход устройства «запись выходного сигнала» поступит второй синхроимпульс по спаду или фронту которого, результат преобразования кодового слова в комбинационном цифровом устройстве запишется в выходной регистр RG2.

С выхода регистра RG2 сигналы поступают в выходную шину данных устройства и на входы выходного узла контроля по четности, с выхода которого, бит контроля по четности поступает в выходную шину данных.

Если во входном кодовом слове была обнаружена ошибка, то нулевой сигнал с инверсного выхода входного узла контроля поступит на второй вход логического элемента И (конъюнктора – схема совпадения), который запретит прохождение второго синхроимпульса на синхровход регистра RG2, и тем самым не допустит записи искаженных данных.

Блок-схема алгоритма функционирования кодопреобразователя представлена на рисунке 4.2.



НЕТ

ДА

	Рис. 4.2 – Блок-схема алгоритма функционирования кодопреобразователя

	

	

	

	

МИНИМИЗАЦИЯ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ









5.1  Методы минимизации булевых функций, выбор и обоснование метода оптимизации

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

Минимизация может быть выполнена двумя методами: непосредственными и формальными. Непосредственный метод основан на применении законов алгебры логики к заданной булевой функции. Причем функция может быть задана в произвольной форме. 

Следовательно, минимальная форма получена в результате применения операции склеивания к конъюнктивным термам, которые отличаются друг от друга в одном разряде. 

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

Если требуется получить карту Карно для какой – либо функции, сначала надо записать эту функцию в совершенной дизъюнктивно нормальной форме (СДНФ) или в виде таблицы истинности. Каждое слагаемое булева выражения в СДНФ, или каждая единица в столбце функции таблицы истинности, задается на карте Карно единицей в соответствующей клетке. Координаты этой клетки содержат те же входные переменные и их инверсии, что и данное слагаемое СДНФ булева выражения (или данная строка таблицы истинности).



5.2 Минимизации каждой булевой функции – выходов кодопреобразователя (4 карты Карно)

По полученным выходным данным кодопреобразователя в разделе 3 настоящего курсового проекта для удобства последующей минимизации составим СДНФ каждой функции выхода , , , . Далее по полученным СДНФ каждой функции составим карты Карно и с их помощью получим 4 ДНФ функций выхода.

СДНФ функции выхода  имеет следующий вид:

	

	

	

	По полученной СДНФ составим карту Карно для функции выхода . Информационная структура карты Карно с пятью переменными и вариант группировки единиц с целью получения минимизированной булевой функции выхода  в формате дизъюнктивной нормальной формы приведена на рисунке 5.1.

	



	







	

		                                              		

	Ф

	

	Ф

	Ф

	

	1

	1

	1

	

	Ф

	Ф

	Ф

	

	Ф

	

	1

	

	Ф

	

	Ф

	Ф

	Ф

	1

	Ф

	1

	Ф

	Ф

	1

	Ф

	Ф

	1

	

	










	

	

	Рис. 5.1 – Карта Карно для функции выхода 

	Минимизированная таким образом булева функция для выхода  в дизъюнктивной нормальной форме имеет вид:

	

	

	СДНФ функции выхода  имеет следующий вид:

	

	

	

	По полученной СДНФ составим карту Карно для функции выхода . Информационная структура карты Карно с пятью переменными и вариант группировки единиц с целью получения минимизированной булевой функции выхода  в формате дизъюнктивной нормальной формы приведена на рисунке 5.2.

	



	







	

		                                              		

	Ф

	

	Ф

	Ф

	1

	1

	

	

	

	Ф

	Ф

	Ф

	1

	Ф

	

	

	1

	Ф

	1

	Ф

	Ф

	Ф

	1

	Ф

	1

	Ф

	Ф

	1

	Ф

	Ф

	

	

	










	

	

	Рис. 5.2 – Карта Карно для функции выхода 

	Минимизированная таким образом булева функция для выхода  в дизъюнктивной нормальной форме имеет вид:

	

	СДНФ функции выхода  имеет следующий вид:

	

	

	

	

	По полученной СДНФ составим карту Карно для функции выхода     Информационная структура карты Карно с пятью переменными и вариант группировки единиц с целью получения минимизированной булевой функции выхода  в формате дизъюнктивной нормальной формы приведена на рисунке 5.3.

	

	

	



	





	



		                                              		

	Ф

	1

	Ф

	Ф

	

	1

	1

	

	

	Ф

	Ф

	Ф

	1

	Ф

	

	

	1

	Ф

	

	Ф

	Ф

	Ф

	

	Ф

	

	Ф

	Ф

	1

	Ф

	Ф

	1

	1

	










	

	

	Рис. 5.3 – Карта Карно для функции выхода 

	Минимизированная таким образом булева функция для выхода  в дизъюнктивной нормальной форме имеет вид:

	

	

	     СДНФ функции выхода имеет следующий вид:

	

	

	

	

	По полученной СДНФ составим карту Карно для функции выхода     Информационная структура карты Карно с пятью переменными и вариант группировки единиц с целью получения минимизированной булевой функции выхода  в формате дизъюнктивной нормальной формы приведена на рисунке 5.4.

	

	 

	







	



		                                              		

	Ф

	1

	Ф

	Ф

	

	1

	

	

	

	Ф

	Ф

	Ф

	1

	Ф

	1

	1

	

	Ф

	1

	Ф

	Ф

	Ф

	

	Ф

	1

	Ф

	Ф

	

	Ф

	Ф

	1

	

	










	

	

	Рис. 5.4 – Карта Карно для функции выхода 

	             Минимизированная таким образом булева функция для выхода  в дизъюнктивной нормальной форме имеет вид:

	

	

	Таким образом, для схемотехнической реализации:

функции  потребуется 5 логических элементов, имеющих суммарное количество входов - 13;

функции  потребуется 4 логических элементов, имеющих суммарное количество входов - 10;

функции  потребуется 6 логических элементов, имеющих суммарное количество входов - 20;

функции  потребуется 6 логических элементов, имеющих суммарное количество входов - 19;

Всего для схемотехнической реализации рассматриваемого цифрового устройства потребуется  21 логический элемент с 62 входами.





5.3 Минимизации системы булевых функций – выходов кодопреобразователя (4 карты Карно)



	Выполним совместную минимизацию булевых функций с пятью аргументами  для четырех  выходов КЦУ в несколько ином виде, чем было рассмотрено ранее в пункте 5.2.

Информационная структура карты Карно с пятью переменными и вариант группировки единиц с целью получения минимизированной булевой функции для выхода  в форме нормальной дизъюнктивной формы приведена на рисунке 5.5.









	

	



	







	

	

		                                              		

	Ф

	

	Ф

	Ф

	

	1

	1

	1

	1

	Ф

	Ф

	Ф

	

	Ф

	

	1

	

	Ф

	

	Ф

	Ф

	Ф

	1

	Ф

	

	Ф

	Ф

	1

	Ф

	Ф

	1

	

	

















	

		


		

			

	

	Рис. 5.5 – Вариант карты Карно для функции выхода 

	

Информационная структура карты Карно с пятью переменными и вариант группировки единиц с целью получения минимизированной булевой функции для выхода  в форме нормальной дизъюнктивной формы приведена на рисунке 5.6.

	

	







	



		                                              		

	Ф

	

	Ф

	Ф

	1

	1

	

	

	1

	Ф

	Ф

	Ф

	1

	Ф

	

	

	1

	Ф

	1

	Ф

	Ф

	Ф

	1

	Ф

	

	Ф

	Ф

	1

	Ф

	Ф

	

	

	










		



		

	

	Рис. 5.6 – Вариант карты Карно для функции выхода 

	

Информационная структура карты Карно с пятью переменными и вариант группировки единиц с целью получения минимизированной булевой функции для выхода  в форме нормальной дизъюнктивной формы приведена на рисунке 5.7.

		

	







	

	

			                                              			

	Ф

	1

	Ф

	Ф

	1

	1

	1

	

	

	Ф

	Ф

	Ф

	

	Ф

	

	

	1

	Ф

	

	Ф

	Ф

	Ф

	

	Ф

	

	Ф

	Ф

	1

	Ф

	Ф

	1

	1

	










 

	

	Рис. 5.7 – Вариант карты Карно для функции выхода 

	

Информационная структура карты Карно с пятью переменными и вариант группировки единиц с целью получения минимизированной булевой функции для выхода  в форме нормальной дизъюнктивной формы приведена на рисунке 5.8.



















		





	

	



		                                              		

	Ф

	1

	Ф

	Ф

	1

	1

	

	

	1

	Ф

	Ф

	Ф

	

	Ф

	1

	1

	

	Ф

	1

	Ф

	Ф

	Ф

	

	Ф

	

	Ф

	Ф

	

	Ф

	Ф

	1

	

	

















	

		


	

	

	Рис. 5.8 – Вариант карты Карно для функции выхода 



Одинаковые функции всех 4 карт Карно заменим на:











	Данные булевы функции для выходов ,,, соответственно в дизъюнктивной нормальной форме будут иметь вид:









Таким образом, для схемотехнической реализации:

функции  потребуется  логических элемента, имеющих суммарное количество входов -;

функции  потребуется  логических элемента, имеющих суммарное количество входов -;

функции  потребуется  логических элементов, имеющих суммарное количество входов -;

функции  потребуется  логических элемента, имеющих суммарное количество входов -;

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




ВЫБОР И ОБОСНОВАНИЕ ПРИМЕНЯЕМОГО ЛОГИЧЕСКОГО БАЗИСА. ПРЕОБРАЗОВАНИЕ БУЛЕВЫХ ФУНКЦИЙ К ВЫБРАННОМУ ЛОГИЧЕСКОМУ БАЗИСУ



6.1  Понятие функционально-полного логического базиса, вид функционально-полных логических базисов

Логические функции могут быть реализованы простейшими логическими элементами. Совокупность логических элементов И, ИЛИ, НЕ, с помощью которых можно воспроизвести и реализовать любую ФАЛ, будем называть полным логическим базисом. 

Базис И, ИЛИ, НЕ обладает избыточностью и не является минимальным. Из этой совокупности ЛЭ можно исключить логический элемент И (либо ЛЭ ИЛИ), тогда наборы И, НЕ и ИЛИ, НЕ также будут обладать свойс.......................