Канонический метод синтеза

Синтез цифровых устройств выполняется в два этапа:

§ этап абстрактного синтеза;

§ этап структурного синтеза.

Для перехода от абстрактного автомата к его структурной схеме требуется:

1) поставить каждой букве входного алфавита Z=[z₁,…,z_k} совокупность двоичных сигналов из множества X={x₁,x₂,…,x_L}, то есть закодировать входные символы абстрактного автомата. Значение L вычисляется следующим образом L=intlog₂|X| = [log₂|X|], где |X| - мощность множества Х (число различных элементов множества Х);

2) поставить в соответствие каждому выходному символу из W={w₁,…,w_l} совокупность двоичных выходных сигналов из множества Y={y₁,y₂,…,y_N}, то есть закодировать выходные символы абстрактного автомата. Значение N вычисляется следующим образом N=intlog₂|Y| = [log₂|Y|];

3) поставить в соответствие каждому состоянию абстрактного автомата А={a_a,…,a_m} совокупность состояний элементов памяти T={t₁,t₂,…,t_r}, то есть закодировать состояния абстрактного автомата. Количество элементов памяти выбирается из условия r=intlog₂|А| = [log₂|А|];

4) составить систему уравнений для функций y₁,y₂,…,y_N,d₁,d₂,…,d_r предназначенной для построения логической схемы комбинационной части структурной схемы.

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

Рассмотрим пример структурного синтеза автомата Мили блок памяти которого построен на Т-триггерах. Исходные данные для выполнения синтеза структурной схемы заданы таблично (таблицы 32 и 33). Таблица истинности работы Т-триггера приведена в таблице 29.

Определяем вначале общее количество входов, выходов и элементов памяти автомата.

L=intlog₂|X| = [log₂|X|]= [log₂4]=2;

N=intlog₂|Y| = [log₂|Y|]= [log₂4]=2;

r=intlog₂|А| = [log₂|А|]= [log₂6]=3;

Структурная схема автомата изображена на рисунке (см. рис.42).

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

На основании кодирования строим таблицы переходов и выходов структурного автомата (таблицы 35 и 36). Они получаются путем занесения соответствующих значений из таблицы 34 в исходные таблицы 32 и 33.

Используя таблицу переходов Т-триггера (табл. 29) построим таблицу 37 - функций возбуждения элементов памяти по таблице 35.

Если r-й триггер на некотором переходе переключается из состояния 0 в состояние 1, или наоборот, то u_i=1, в противном случае (то есть если r-й триггер не переключается) u_i=0. Например, рассмотрим переход из состояния 10 в состояние 11 (3-й столбец 3-я строка). Первый триггер (установленный в 1) не меняет своего значения, поэтому функция возбуждения элемента памяти для него u₁=0. Второй триггер изменяет свое значение с 0 на 1, следовательно u₂=1.Остальные клетки таблицы 37 заполняются аналогично. На основании таблиц 36 и 37 запишем систему логических функций для построения комбинационной схемы автомата.

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

По результатам минимизации запишем систему минимальных функций.

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