Определение поставленной задачи

Устройство, работа которого может быть представлена на языке алгебры высказываний, принято называть логическим. Пусть такое устройство имеет n выходов и m входов. На каждый вход может быть подан произвольный символ конечного множества Х, называемого входным алфавитом. Совокупность входных символов, поданных на входы устройства, образует входное слово Р _i в алфавите Х. На выходе устройства появляются выходные слова Q_j, составленные из символов выходного алфавита Y. В силу конечности алфавитов X, Y и слов P _i, Q _j (длина слова всегда равна m, а выходного слова - h) общее количество различных входных и выходных слов также конечно.

Элементарный такт работы устройства состоит в том, что при появлении на входе слова Р _i устройство выдает на выходах комбинацию символов y _i, образующих слово Q _j. Если слово Q _j определяется только входным словом на данном такте, то устройство называется конечным автоматом без памяти, или комбинационной схемой.

Алгоритм функционирования комбинационного устройства будет определен, если задать таблицу соответствия {P _i }->{Q _j } для всех слов P _i. Если входной алфавит X состоит из K различных символов, в таблице соответствия будет K ^m строк. Так как символы входного и выходного алфавитов принимают только два значения (в данном случае «1» или «0»), то при синтезе и анализе логического устройства применяется булева алгебра.

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

Под синтезом комбинационной схемы подразумевается построение логической схемы проектируемого устройства в заданном базисе логических элементов. Исходным материалом к синтезу является словесное описание работы устройства.

Согласно заданию на курсовое проектирование было предложено закодировать исходный алфавит кодом Грея и использовать для синтеза конечного автомата базис {и, не}.

Код Грея является циклическим кодом, получается из двоично-десятичного кода по следующим правилам:

1. пусть g_n…..g₁g₀ – кодовый набор в коде Грея с (n+1) разрядами.

2. b_n…b₁b₀ – соответствующее двоичное число.

3. тогда разряд g₀ получается из следующего выражения:

g_i=b_iÅb_i+1; 0£i£n-1; g_n=b_n; где Å - символ операции сложения по модулю 2 (0+0=0, 0+1=1, 1+0=1, 1+1=0).

Закодируем входной алфавит в соответствии с этими правилами и с учетом значений y_i составим таблицу истинности (см. таблицу 2.1.1).

Таблица 2.1.1

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

Составление логических функций

Существует два способа записи логической функции по таблице истинности: запись дизъюнктивной совершенной нормальной формы (ДСНФ) и запись конъюнктивной совершенной нормальной формы (КСНФ). В первом случае образуют дизъюнкции, соответствующие входным наборам, на которых функция принимает значение «1», их объединяют знаками конъюнкции. Во втором случае организуют конъюнкции, соответствующие входным словам, на которых функция принимает значение «0», эти конъюнкции объединяют знаками дизъюнкции. Рассмотрим на примере функции у₃.