Математичекие основы теории систем анализ сигнального графа и синтез комбинационных схем (стр. 6 из 9)
Элементарный такт работы устройства состоит в том, что при появлении на входе слова Рi устройство выдает на выходах комбинацию символов yi, образующих слово Qj. Если слово Qj определяется только входным словом на данном такте, то устройство называется конечным автоматом без памяти, или комбинационной схемой.
Алгоритм функционирования комбинационного устройства будет определен, если задать таблицу соответствия {Pi}->{Qj} для всех слов Pi. Если входной алфавит X состоит из K различных символов, в таблице соответствия будет Km строк. Так как символы входного и выходного алфавитов принимают только два значения (в данном случае «1» или «0»), то при синтезе и анализе логического устройства применяется булева алгебра.
Произвольные входной и выходной алфавиты могут быть приведены к автомату с двойным входом и выходом путем соответствующего кодирования. Однако этот автомат должен оперировать со словами входного и выходного алфавитов, длина которых больше длин соответствующих слов исходного алфавита.
Под синтезом комбинационной схемы подразумевается построение логической схемы проектируемого устройства в заданном базисе логических элементов. Исходным материалом к синтезу является словесное описание работы устройства.
Согласно заданию на курсовое проектирование было предложено закодировать исходный алфавит кодом Грея и использовать для синтеза конечного автомата базис {и, не}.
Код Грея является циклическим кодом, получается из двоично-десятичного кода по следующим правилам:
1. пусть gn…..g1g0 – кодовый набор в коде Грея с (n+1) разрядами.
2. bn…b1b0 – соответствующее двоичное число.
3. тогда разряд g0 получается из следующего выражения:
gi=biÅbi+1; 0£i£n-1; gn=bn; где Å - символ операции сложения по модулю 2 (0+0=0, 0+1=1, 1+0=1, 1+1=0).
Закодируем входной алфавит в соответствии с этими правилами и с учетом значений yi составим таблицу истинности (см. таблицу 2.1.1).
Таблица 2.1.1
| Выходной символ | Сигнал (код) | y1 | y2 | y3 | y4 | y5 | y6 | y7 | ||||
| x4 | x3 | x2 | x1 | |||||||||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 2 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 3 |
| 3 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 2 |
| 4 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 6 |
| 5 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 7 |
| 6 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 5 |
| 7 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 4 |
| 8 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 12 |
| 9 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 13 |
| 10 | 1 | 0 | 1 | 0 | * | * | * | * | * | * | * | 8 |
| 11 | 1 | 0 | 1 | 1 | * | * | * | * | * | * | * | 9 |
| 12 | 1 | 1 | 1 | 0 | * | * | * | * | * | * | * | 10 |
| 13 | 1 | 1 | 1 | 1 | * | * | * | * | * | * | * | 11 |
| 14 | 1 | 0 | 0 | 0 | * | * | * | * | * | * | * | 14 |
| 15 | 1 | 0 | 0 | 1 | * | * | * | * | * | * | * | 12 |
Если не удается заполнить все строки этой таблицы, то функция называется не полностью определенной, а наборы на которых она не определена, носят название запрещенных. В этом случае схема называется неполной. Доопределение функции производится произвольно.
2.2 Составление логических функций
Существует два способа записи логической функции по таблице истинности: запись дизъюнктивной совершенной нормальной формы (ДСНФ) и запись конъюнктивной совершенной нормальной формы (КСНФ). В первом случае образуют дизъюнкции, соответствующие входным наборам, на которых функция принимает значение «1», их объединяют знаками конъюнкции. Во втором случае организуют конъюнкции, соответствующие входным словам, на которых функция принимает значение «0», эти конъюнкции объединяют знаками дизъюнкции. Рассмотрим на примере функции у3.
2.2.1 Дизъюнктивная совершенная нормальная форма
Введем понятие логической степени, которою будем обозначать
. Тогда, логическая степень будет определяться по формуле (2.1) 
(2.1)Любую функцию от n переменных можно представить в виде (см.(2.2))
(2.2)
означает, что коллективные члены формируются только для таких наборов (α1, α2,…, αn) для которых функция принимает единичное значение.Форма (2.2) определяет алгоритм перехода от таблицы истинности к аналитическому ее виду. Для такого перехода используется следующий алгоритм:
а) Выбрать в таблице истинности все наборы, в которых функция обращается в единицу.
б) Выписать конъюнкции, соответствующие этим наборам аргументов. При этом если аргумент хi входит в данный набор как «1», то он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если же входит в данный набор как «0», то в соответствующую конъюнкцию вписывается его отрицание.
в) Все полученные конъюнкции объединяют знаком дизъюнкции.
Для функции у3 СДНФ будет иметь вид:
2.2.2 Конъюнктивная совершенная нормальная форма
Любую функцию от n переменных можно представить в виду:
f=
означает, что коллективные члены формируются только для таких наборов, (α1, α2, …, αn) для которых функция принимает нулевое значение.Следующий алгоритм позволяет перейти от табличной записи функции к СКНФ:
а) Выбрать в таблице истинности все наборы, в которых функция обращается в «0».
б) Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом если аргумент хi входит в данный набор как «0», то он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же входит в данный набор как «1», то в соответствующую дизъюнкцию вписывается его отрицание.
в) Все полученные дизъюнкции объединяют знаком конъюнкции
Функция У3 в виде СКНФ будет иметь вид:
2.3 Минимизация булевых функций
Минимизация сводится к поиску минимальных форм (ДНФ и КНФ). Минимальной форме соответствует самая простая логическая схема, реализующая данную функцию и требующая минимальных аппаратных затрат.
В ходе курсового проектирования была выполнена минимизация полученных булевых функций следующими методами:
1. метод неопределенных коэффициентов
2. метод Квайна-Мак-Класки
3. карты Карно
Для примера в курсовом проекте рассмотрена минимизация этими способами для функции y3.
2.3.1 Пример минимизации методом неопределенных коэффициентов
Данный метод является по своим идеям наиболее простым. Для функции записываются все возможные конъюнктивные члены, которые могут входить в дизъюнктивную форму представления функции. Коэффициенты К с различными индексами являются неопределенными и подбираются так, чтобы получающаяся после этого дизъюнктивная форма была минимальной.
Если теперь задавать всевозможные наборы значений аргументов и приравнивать полученное после этого выражение значению функции на выбранных наборах, то получим систему 24 уравнений для определения коэффициентов К:
Находим выражения, имеющие в правой части ноль. Исходя из определения дизъюнкции вычеркиваются все элементы в этих уравнениях и эти же элементы находящиеся в других уравнениях. В итоге получим уравнения: