Единичное кодирование
Для кодирования используется граф автомата.
Алгоритм метода:
1.Каждому состоянию автомата ставится в соответствие целое число Nm, которое равно количеству дуг на графе, входящих в данное состояние am.
2.Числа Nm, упорядочиваются по убыванию.
3.Состояние с наибольшим Nm кодируется комбинацией М нулей: 00...00, где М - число состояний автомата (М =|log2M|).
1.Все остальные состояния в соответствии с значением Nm кодируются путем прибавления одной единицы в кодовую комбинацию из нулей.
2.Если не хватает одной единицы, то добавляется вторая и т.д. до тех пор, пока не будут закодированы все состояния.
Таким образом, при данном способе кодирования наиболее связанные состояния кодируются минимальным числом единиц.
Соседнее кодирование
Каждой паре состояний автомата ставится в соответствии вес перехода: P(i,j)=q(i,j)+q(j,i), где q (i,j) - число дуг, идущих от i -гo состояния к j -му на графе состояний автомата; q(j,i) - число дуг, идущих от j -ro к i -му состоянию на графе состояний. Критерием сложности синтезированной комбинационной схемы автомата является величина
W=åP(i,j)*d(i,j), где d(i,j) - кодовое расстояние во Хеммингу, т.е. количество символов, которыми отличаются коды состояний i и j. Чем меньше W, тем проще схема. Алгоритм метода:
1. По графу или таблице переходов автомата составляется матрица Т, строки которой образуют пары состояний, между которыми возможен переход. Каждой паре состояний ставится в соответствие вес перехода P.
2. Матрица Т упорядочивается по убыванию веса перехода. В случае одинакового веса для упорядочивания используется суммарный вес перехода, определяемый как общее число дуг, связанных с обоими состояниями. Упорядоченная матрица обозначается М.
3. Состояния первой строки матрицы М кодируются начальными кодовыми комбинациями, то есть содержащими минимальное количество единиц, после чего эта строка вычеркивается. Так как матрица М упорядочена, одно из состояний второй строки уже получило свой код.
4. Для незакодированного состояния aj второй строки составляется дополнительная матрица Вj, в которую заносятся все пары состояний, содержащие aj.
5. Составляется множество кодовых комбинаций D для состояния aj c учетом условий соседнего кодирования. Для подбора кодов можно использовать карту Карно. 6. Для каждой кодовой комбинации из D вычисляется W.
7. В качестве кода для aj принимается комбинация с минимальным W.
Строки закодированных состояний в матрице М вычеркиваются.
П.п. 3-8 выполняются до тех пор, пока все состояния не будут закодированы.
12.
Основные этапы канонического метода: 1. Переход на структурный уровень, т.е. кодирование входных, выходных сигналов и состояний автомата. При этом каждая буква алфавитов A,Z,w,u кодируется двоичными векторами (наборами), длина которых равна числу физически реализованных входных и выходных каналов (для z,w,u) и числу элементов памяти. При этом две различные буквы одного и того же алфавита должны кодироваться различными двоичными векторами.
2. Выбор элементов памяти автомата. Для правильной работы схемы нельзя допустить, чтобы сигналы на входах элементов памяти участвовали в формировании сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. В связи с этим элементами памяти должны быть не автоматы Мили, а автоматы Мура, имеющие полную систему переходов и полную систему выходов.
3. Выбор функционально полной системы логических элементов. Система логических элементов должна быть функционально полной.
4. Построение булевых ф-ций возбуждения памяти и ф-ции выхода (СКУ и СВФ). Получение булевых ф-ций выходов не зависит от типа используемых элементов памяти и может быть сделано непосредственно по структурной таблице выходов автомата. Для построения ф-ций возбуждения памяти, в начале строится таблица ф-ции возбуждения памяти по которой записываются канонические уравнения ф-ции возбуждения. Для построения этой таблицы используется структурная таблица переходов автомата и ф-ция входов, используемого триггера.
5. Построение функциональной схемы автомата. Полученная на этапе 4 СКУ и СВФ, преобразуется для рациональной реализации в выбранном базисе и строится функциональная схема структурного автомата.Исходными данными для начала работы данного метода являются абстрактный цифровой автомат с памятью, заданный таблицей переходов и выходов.
Теоретическим обоснованием канонического метода структурного синтеза является о структурной полноте.
Теорема: Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов и полной системой выходов, и какую -либо функционально полную систему логических элементов, является структурно полной.
Схема: совмещенная модель автомата (С- автомат
Рис. 1-14. Абстрактный автомат.
Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов 1 и 2, каждая из которых характерна для этих моделей в отдельности. С-автомат можно описать следующими уравнениями:
a(t+1)=(a(t), z(t)); w(t)= 1(a(t), z(t)); u(t)= 2(a(t)), t=0,1,2,
13.
RS-триггер асинхронный
| S | R | Q(t) | Q(t) | Q(t+1) | Q(t+1) |
| не определено | не определено | ||||
| не определено | не определено |
RS-триггер[10][11], или SR-триггер — триггер, который сохраняет своё предыдущее состояние при нулевых входах и меняет своё выходное состояние при подаче на один из его входов единицы.
При подаче единицы на вход S (от англ. Set — установить) выходное состояние становится равным логической единице. А при подаче единицы на вход R (от англ. Reset — сбросить) выходное состояние становится равным логическому нулю. Состояние, при котором на оба входа R и S одновременно поданы логические единицы, в простейших реализациях является запрещённым.
RS-триггер синхронный
| C | S | R | Q(t) | Q(t+1) |
| x | x | |||
| не определено | ||||
| не определено |
D-триггеры также называют триггерами задержки(от англ. Delay).
D-триггер синхронный
Пример условного графического обозначения (УГО) D-триггера с динамическим синхронным входом С и с дополнительными асинхронными инверсными входами S и R
| D | Q(t) | Q(t+1) |
D-триггер (D от англ. delay — задержкалибо от data- данные) — запоминает состояние входа и выдаёт его на выход. D-триггеры имеют, как минимум, два входа: информационный D и синхронизации С. После прихода активного фронта импульса синхронизации на вход С D-триггер открывается. Сохранение информации в D-триггерах происходит после спада импульса синхронизации С. Так как информация на выходе остаётся неизменной до прихода очередного импульса синхронизации, D-триггер называют также триггером с запоминанием информации или триггером-защёлкой.
14.
Т-триггер (от англ. Toggle - переключатель) часто называют счётным триггером, так как он является простейшим счётчиком до 2.
Т-триггер асинхронный
Асинхронный Т-триггер не имеет входа разрешения счёта - Т и переключается по каждому тактовому импульсу на входе С.
Работа схемы асинхронного двухступенчатого T-триггера с парафазным входом на двух парафазных D-триггерах на восьми логических вентилях 2И-НЕ. Слева — входы, справа — выходы. Синий цвет соответствует 0, красный — 1
| T | Q(t) | Q(t+1) |
Синхронный Т-триггер[17], при единице на входе Т, по каждому такту на входе С изменяет своё логическое состояние на противоположное, и не изменяет выходное состояние при нуле на входе T. Т-триггер можно построить на JK-триггере, на двухступенчатом (Master-Slave, MS) D-триггере и на двух одноступенчатых D-триггерах и инверторе.
JK-триггер
| J | K | Q(t) | Q(t+1) |
работает так же как RS-триггер, с одним лишь исключением: при подаче логической единицы на оба входа J и K состояние выхода триггера изменяется на противоположное. Вход J (от англ. Jump — прыжок) аналогичен входу S у RS-триггера. Вход K (от англ. Kill — убить) аналогичен входу R у RS-триггера. При подаче единицы на вход J и нуля на вход K выходное состояние триггера становится равным логической единице. А при подаче единицы на вход K и нуля на вход J выходное состояние триггера становится равным логическому нулю. JK-триггер в отличие от RS-триггера не имеет запрещённых состояний на основных входах, однако это никак не помогает при нарушении правил разработки логических схем. На практике применяются только синхронные JK-триггеры, то есть состояния основных входов J и K учитываются только в момент тактирования, например по положительному фронту импульса на входе синхронизации.
На базе JK-триггера возможно построить D-триггер или Т-триггер. Как можно видеть в таблице истинности JK-триггера, он переходит в инверсное состояние каждый раз при одновременной подаче на входы J и K логической 1. Это свойство позволяет создать на базе JK-триггера Т-триггер, объединив входы J и К[20].
Алгоритм функционирования JK-триггера можно представить формулой 
15.