Кодирование внутренних состояний конечных автоматов.

Как отмечалось выше, минимальное число элементарных автоматов, которое требуется для проектирования схемы заданного конечного автомата с n состояниями, определяется как К= log2n . При этом каждому внутреннему состоянию конечного автомата ставится в соответствие к-разрядное двоичное число. Поэтому количество различных вариантов кодирования равно числу сочетаний из 2к элементов по n, т.е. С2kn.

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

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

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

Из определения конечного автомата известно, что внутреннее состояние автомата S(t+1) в момент времени (t+1) зависит от внутреннего состояния S(t) и входного слова X(t) в момент времени t. S(t+1)=FS[S(t),X(t)]

Если известно кодирование внутренних состояний автомата а12,…,аe, у которого подмножество переменных а12,…,ap (1≤p≤l) может быть определено независимо от (l-p) оставшихся двоичных переменных, то как правило, получают более простую схемную реализацию заданного автомата.

Поскольку кодирование внутренних состояний является задачей, относящейся к внутренней части автомата, то таблицу выходов рассматривать не будем.

Пример. Рассмотрим автомат, заданный таблицей переходов (табл 3.28)

Табл. 3.28

X S
S1 S2 S3 S4 S5 S6
S3 S3 S2 S5 S6 S5
S6 S4 S5 S2 S3 S1

Заданный автомат имеет шесть состояний. Для каждого двоичного кодирования шести состояний потребуется log26 =3 двоичных переменных а123, а число избыточных двоичных наборов равно двум.

Рассмотрим первый вариант кодирования А:

S1 → 000; S2 → 010; S3 → 100; S4 → 001; S5 → 111; S6 → 110;

Кодированная таблица переходов заданного автомата приведена в табл. 3.29

Табл.3.29

x(t) S1(t) S2(t) S3(t) S1(t+1) S2(t+1) S3(t+1)

Запишем функции возбуждения:

S1(t+1)=x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t);

S2(t+1)= x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t);

S3(t+1)= x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t);

Избыточные комбинации: x(t)S1(t)S2(t)S3(t); x(t)S1(t)S2(t)S3(t); x(t)S1(t)S2(t)S3(t); x(t)S1(t)S2(t)S3(t);

Минимизируем полученные функции (рис. 3.9)

    x(t)        
S1(t)          
  b b   S3(t)
      b b  
           
      S2(t)      
    x(t)        
S1(t)        
  b   b   S3(t)
    b b  
             
      S2(t)      
    x(t)        
S1(t)          
  b     b   S3(t)
      b b  
             
      S2(t)      

Рис. 3.9. Карты Вейча для минимизации функций S1(t+1), S2(t+1), S3(t+1).

Полученные в результате минимизации функции относительно сложны:

S1(t+1)=x(t)S2(t)S3(t)+x(t)S1(t) + x(t)S2(t) +S1(t)S2(t);

S2(t+1)= x(t)S2(t)+x(t)S1(t)+S1(t)S3(t);

S3(t+1)= x(t)S1(t)S2(t)+x(t)S1(t)S2(t)+x(t)S2(t)S3(t)+x(t)S1(t)S3(t);

Рассмотрим второй вариант кодирования Б внутренних состояний заданного автомата:

S1→111; S2→110; S3→100; S4→011; S5→000; S6→010.

Кодировочная таблица переходов для варианта кодирования Б приведена в табл.3.30.

x(t) S1(t) S2(t) S3(t) S1(t+1) S2(t+1) S3(t+1)

Функции возбуждения входов запишутся в этом случае в следующем виде:

S1(t+1)=x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t);

S2(t+1)= x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t)+ x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t);

S3(t+1)= x(t)S1(t)S2(t)S3(t)+x(t)S1(t)S2(t)S3(t);

Избыточные комбинации при таком кодировании: x(t)S1(t)S2(t)S3(t); x(t)S1(t)S2(t)S3(t); x(t)S1(t)S2(t)S3(t); x(t)S1(t)S2(t)S3(t);

Карты Вейча для минимизации полученных функций возбуждения приведены на рисунке 3.10

    x(t)        
S1(t)          
  b   b   S3(t)
    b   b  
           
      S2(t)      
    x(t)        
S1(t)          
  b   b   S3(t)
    b   b  
           
      S2(t)      
    x(t)        
S1(t)            
  b     b   S3(t)
    b     b  
             
      S2(t)      

Минимальные формы функций возбуждения

S1(t+1)=x(t)S1(t) + x(t)S1(t);

S2(t+1)= x(t)S2(t)+x(t)S2(t);

S3(t+1)= x(t)S2(t)S3(t);

Из полученных выраженийц для реализации заданного автомата видно, что кодирование внутренних состояний по варианту Б гораздо эффективнее, чем кодирование по варианту А. Оно является кодированием с минимальной зависимостью. В данном примере S, не зависит от S2 и S3, а S2 не зависит от S1 и S3.

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

Мы рассмотрели один из возможных подходов к кодированию внутренних состояний конечного автомата.

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

Различные подходы к кодированию внутренних состояний конечных автоматов рассмотрены в работах |11,12,13|.

3.3. Контрольные задания.

1. Синтезировать конечный автомат на Т триггерах и элементах И-НЕ, который при подаче на его вход сигнала х=0, меняет свое состояние в последовательности 0, 2,1,3,0,3…, а при подаче х=1 меняет свое состояние в последовательности 0,3,1,2,0,3…

2. Синтезировать конечный автомат на D триггерах и элементах И-НЕ, который при подаче на его вход сигнала х=0, меняет свое состояние в последовательности 0,1,2,4,7,3,5,6,0,1…, а при подаче сигнала х=1, меняет свое состояние в последовательности 0,2,3,4,1,6,5,7,0,2…

3. Синтезировать конечный автомат на R-S триггерах и элементах ИЛИ-НЕ, который при подаче на вход сигнала х=0, меняет свое состояние в последовательности 0,3,2,1,0,3…, а при подаче на вход сигнала х=1, меняет свое состояние в последовательности 0,1,2,3,0,1…

4. Синтезировать конечный автомат на j-k триггерах и элементах И-НЕ, который при подаче на его вход сигнала х=0, меняет свое состояние в последовательности 0,3,5,1,2,4,7,6,0,3…, а при подаче на его вход сигнала х=1, его состояние меняется в последовательности 0,5,4,1,2,6,3,7,0,5…

5. Выполнить структурный синтез счетчика с переменным модулем счета, который при х=0 выполняется с модулем К=10, а при х=1 с модулем счета К=12.

6. Синтезировать конечный автомат, который при подаче сигнала х=0 своего состояния не меняет, а при х=1 меняет свое состояние в последовательности 0,2,4,7,1,6,5,3,0,2…

7. Спроектировать автомат, выдающий результат от деления пятиразрядного двоичного числа на двоичное число 112 (310). На выходе автомата формировать только частное, которое получаетсяв результате целочисленного деления. Автомат реализовать на триггерах типа D.

8. Спроектировать автомат, выдающий результат от деления пятиразрядного двоичного числа на двоичное число 1012 (510). На выходе автомата формировать только частное, которое получается в результате целочисленного деления. Автомат реализовать на триггерах типа j-k.

Наши рекомендации