Структурный синтез цифрового автомата по графу

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

Если автомат имеет М состояний, то для двоичного структурного алфавита количество триггеров в блоке памяти этого автомата

n=]log₂M[,

где ]...[ - ближайшее большее целое число.

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

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

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

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

Рассмотрим пример синтеза цифрового автомата Мили S₁₈, заданного таблицей 39 переходов и таблицей 40 выходов. Структурный алфавит для выходных сигналов и состояний - двоичный. Для кодирования трёх входных и трёх выходных сигналов двоичными кодами достаточно двухразрядного кода, а три состояния можно реализовать двумя триггерами. Таким образом, структурный автомат будет иметь две входных и две выходных линии, а память его будет состоять из двух триггеров.

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

Второй принцип кодирования соответствует противоположному подходу и ориентирован на возможность получения значительных упрощений ФАЛ в результате минимизации. Для кодирования выходных сигналов с максимальным количеством ссылок в таблице выходов используется код с максимальным количеством единиц, а для кодирования следующих по количеству ссылок в таблице выходных сигналов использовать коды с уменьшающимся количеством единиц в кодовых комбинациях. Этот принцип также без оговорок применим для кодирования состояний блока памяти на D триггерах для случая применения элементной базы, требующей минимизации для своей реализации. Минимальный по материальным затратам вариант кодирования выбирается из конечных результатов при использовании всевозможных вариантов кодирования.

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

Рис.48 Таблицы кодирования входных сигналов, выходных сигналов

и состояний (по второму варианту)

В таблице выходов выходной сигнал w₁ встречается 4 раза, выходной сигнал w₃ - 3 раза, выходной сигнал w₂ - 2 раза. В таблице переходов состояние a₁ встречается 6 раз, состояние a₃ - 2 раза, состояние a₂ - 1 раз. В соответствии с количеством этих ссылок заполнены таблицы кодирования на рис.48.

Запрещённые наборы переменных x₁x₀Q₁Q₀

1100; 1101; 1110; 1111; 0000; 0100; 1000.

Где 11§§ - запрещённый код входных сигналов,

§§00 - запрещённый код состояний.

Рис.49 Кодированные таблицы переходов, выходов и возбуждений блока памяти на JK триггерах

Выполним конкатенацию кодов входных сигналов и кодов состояний по порядку следования переменных x₁x₀ Q₁Q₀ и заполним таблицу истинности для функций выхода и возбуждений. В таблице на запрещённых наборах входных сигналов и состояний значения функций не определены и обозначены символом красного цвета §^к.

Рис.50 Таблица истинности булевых функций входной и выходной схем цифрового автомата Мили S₁₈

Рис.51 Минимизация функций выходов

Рис.52 Минимизация функций возбуждения

Минимизированные функции выходов в ДНФ:

Минимизированные функции возбуждений в ДНФ:

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

Запрещённые коды x₁x₀Q₁Q₀

1100; 1101; 1110; 1111; 0011; 0111; 1011.

Где 11§§ - запрещённый код входных сигналов,

§§11 - запрещённый код состояний

Рис.53 Таблицы кодирования входных сигналов, выходных сигналов

и состояний (по первому варианту)

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

Рис.54 Кодированные таблицы переходов, выходов и возбуждений

Рис. 55 Минимизация функций выхода

Рис.56 Минимизаций функций возбуждения JK триггеров блока памяти

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

Минимизированные функции выходов в ДНФ:

Минимизированные функции возбуждений в ДНФ:

На рис.57 приведена принципиальная схема цифрового автомата S₁₈ с использованием кодирования по первому варианту, который имеет явные преимущества при использовании элементной базы, не требующей минимизации булевых функций выходов и возбуждений.

В формулах А и Б функции возбуждения JK триггеров блока памяти не содержат дизъюнкций, а количество переменных в конъюнкции не больше трёх. Для блока памяти следует использовать JK триггеры с встроенной логикой (трёхвходовые конъюнкторы в триггерах типа 155ТВ1). Такие схемы дают большую экономию и повышенную надёжность. Функция К₀ «константа 1» задаётся подключением соответствующего входа через резистор сопротивлением 1 кОм к источнику питания схемы (для ТТЛ схем это напряжение равно +5В). Для соединения элементов схемы между собой использован «жгут». Соединены между собой проводники, имеющие одинаковую нумерацию входов в «жгут» и выходов из «жгута».

Рис.57 Принципиальная схема автомата Мили S₁₈

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

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

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

В обоих случаях усложняется принципиальная схема цифрового автомата. Иногда проектировщики ограничиваются упрощенной схемой начального сброса цифрового автомата при включении питающего напряжения. Для надёжной работы цифрового автомата такой схемы недостаточно.

Табличный и графический способы задания автоматов эквивалентны, поэтому граф автомата содержит всю необходимую информацию о функциях выходов и функциях переходов. На граф кодированного цифрового автомата следует нанести все необходимые данные по функциям возбуждения триггеров заданного типа. Однако дальнейшее использование информации, заданной в виде разметки графа цифрового автомата, выполняется с использованием табличного или аналитического представления ФАЛ. Таким образом, синтез цифрового автомата только по графу обычно не делается и этот метод синтеза цифрового автомата является гораздо менее распространённым, чем синтез цифрового автомата с использованием таблиц. На рис.58 представлен пример различных видов разметки графа цифрового автомата Мили S₁₈.

Рис.58 Различные виды разметки графа автомата Мили S₁₈

Функцию выходов по графу рис.58в) получим следующим образом:

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

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

Триггеры типа RS. Пример разметки дуг фрагмента графа автомата приведён на рис.59.

При разметке переходы триггера интерпретируются как переходы 0®0, 0®1, 1®0, 1®1 соответственно. Если на каком-то из переходов функция возбуждения имеет единичное значение, то дуга графа помечается символом этой функции с соответствующим индексом. Если же на каком-то из переходов функция возбуждения не определена, то дуга помечается символом функции возбуждения заключённым в скобки и имеющим соответствующий индекс.

Триггеры типа T. На рис.60 приведён пример разметки дуг фрагмента графа цифрового автомата для Т триггеров в блоке памяти.

Триггеры типа D. На рис.61 приведён пример разметки дуг фрагмента графа цифрового автомата для D триггеров в блоке памяти.

Триггеры типа JK. На рис.62 приведён пример разметки дуг фрагмента графа цифрового автомата для JK триггеров в блоке памяти.

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

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

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

Глава 3

Дата добавления: 2014-01-07