ОСНОВЫ ПРОЕКТИРОВАНИЯ ЦИФРОВЫХ УСТРОЙСТВ С ПАМЯТЬЮ

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

На абстрактном этапе под автоматом подразумевается цифровое устройст- во, задаваемое тремя непустыми множествами X ={xl, х2,... , хп}, Y ={yl, y2,... , ут}, Z = {zl, z2, … , zl},а также двумя функциями:функцией переходов ифункцией выходов . Мно­жества X, Y иZ называются соответственно алфавитами входных сигналов, выходных сигналов исостояний. Функция переходов определяет состо-яние автомата z(s+1) в зависимости от состояния z(s) и значения входной буквы x(s),т. е.

где s=0, 1, 2, ... – дискретное время; z(s)и х(s) – значения букв соответствующих алфавитов в s-e моменты дискретного времени,афункциявыхода определяет зна-чение выходной буквыy(s)взависимостиотсостоянияавтоматаz(s)и входнойбуквых(s):

(20)

Абстрактный автомат реализует отображение множества слов входного ал-фавита во множество слов выходного алфавита и имеет только один входной и один выходной каналы, являясь, таким обра­зом, лишь математической моделью реальных устройств. При по­строении таких моделей реальный автомат с g входами и h выхода­ми, имеющий k1 букв во входном алфавите и k2букв в выходном ал­фа- вите, заменяется автоматом с одним входом и выходом, входной алфавит которого состоит из букв, а выходной из букв.

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

Функция выходов абстрактного автомата может быть задана двумя спосо- бами. Если выходной сигнал автомата определяется выражением (20), т. е. зависит как от состояния автомата, так и от входного сигнала, то автомат называется авто- матом Мили. Если же выходной сигнал автомата не зависит от входного, а одно- значно определяется состоянием автомата

то такой автомат называют автоматом Мура.

Функции и , описывающие работу автомата Мили, задаются таблицами переходов и выходов. Столб­цы таких таблиц обозначаются символами из множества Z, а строки – символами из множества X. В клетку таб- лицы переходов, находя­щуюся на пересечении столбца zi и строки xj, записывает- ся состоя­ние автомата в которое он переходит из состояния под воздействием сигнала .В таких же клетках таблицы выхо­дов записывается сиг- нал Таблицы переходов и выхо­дов автомата Мили могут быть пред-ставлены совмещенной табли­цей, вклетках которой указаны как значения функ- ции ,так и значения функции .

Более наглядным является задание автоматов Мили с помощью графов. Граф автомата состоит из узлов (вершин), соединенных ветвями (ребрами). Узлы графа отождествляются с состояниями ав­томата, а ветви отмечаются входными сигнала- ми х, вызывающими переход автомата из состояния zi в состояние zj и выходны- ми сиг­налами

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

Иногда для задания автоматов используются так называемые квад­ратные автоматные матрицы (таблицы), строки и столбцы которых отмечены состояниями автомата. В клетку такой матрицы, находя­щуюся на пересечении i-й строки и j-го столбца, вписываются все входные сигналы, вызывающие переход автомата из сос-тояния zi в состояние zj. Для автоматов Мили каждый входной сигнал до­полни- тельно отмечается соответствующим выходным сигналом. Для автоматов Мура вы-ходными сигналами отмечаются строки квадратной автоматной матрицы.

Два автомата, у которых совпадают как входные, так и выход­ные алфави- ты, называются эквивалентными, если для любого вход­ного слова выходное слово одного автомата совпадает с выходным словом другого автомата при условии, что оба автомата находи­лись в одном и том же начальном состоянии. Для любого ав- томата Мили можно построить эквивалентный автомат Мура и наоборот. Рассмот- рим алгоритмы таких переходов на примере автомата Мили, заданного табл. 9 и 10. Поставим в соответствие каждой паре (zi, zj) автомата Мили состояние zij авто-

 

Таблица 9 Таблица 10

  z0 z1 z2 z3
x1 y3 y2 y1 y1
x2 y2 y1 y3 y3
x3 y1 y2 y2 y3
  z0 z1 z2 z3
x1 z1 z2 z0 z2
x2 z3 z0 z0 z0
x3 z2 z3 z2 z3

 

мата Мура. Кроме того, во множество состояний автомата Мура включим началь- ное состояние z0автомата Мили. Для рассматриваемого случая такое соответствие представлено табл. 11. Если автомат Мили имеет l состояний и k входных сигна-

 

Таблица 11

  z0 z00 z1 z2 z3
x1 z1 z01 z2 z11 z0 z21 z2 z31
x2 z3 z02 z0 z12 z0 z22 z0 z32
x3 z2 z03 z3 z13 z2 z23 z3 z33

 

лов, то эквивалентный автомат Мура будет иметь kl + 1 состояний. Из табл. 11видно, что состояние z0 автомата Мили совпадает с состояниями z32, z00, z21, z12, z22 автомата Мура, т. е.

и далее

Поэтому переход автомата Миля из состояния z0 в состояние z1 должен соответствовать всем переходам автомата Мура из состояний z00, z12, z21, z22,, z32 в состояние z01, переход из z1в z3 должен соответ­ствовать всем переходам автома- таМураиз z01вz02, z13, z33 и т. д. Отсюда следует, что если состояние zij входит во множество состоя­ний, совпадающих с состоянием zr, тостолбец таблицы пере- ходов для состояния zij будет совпадать со столбцом таблицы переходов для со- стояния zr. Значения функции выходов для эквивалентно­го автомата Мура опреде-ляются соотношением при zij z00.

Для начального состояния z00 значение выходного сигнала выби­рается про-извольно. Таким образом, переходы и выходные сигналы эквивалентного автомата Мура определяются табл. 12.

Таблица 12

 
x1 z01 z11 z31 z21 z21 z01 z31 z01 z01 z21 z21 z01 z31
x2 z02 z12 z32 z22 z22 z02 z32 z02 z02 z22 z22 z02 z32
x3 z03 z13 z33 z23 z23 z03 z33 z03 z03 z23 z23 z03 z33

 

Задача перехода от автомата Мура к эквивалентному автомату Мили реша- ется очень просто. Если 1 и 1– функции переходов и выходов автомата Мура, то функции переходов 2(z, x)и выходов 2(z, x)эквивалентного автомата Мили определяются следующими соотношениями:

2(z, x) = 1(z, x), 2(z, x) = 1(1(z, x)) .

 

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

Число состояний автомата существенно влияет на егосложность. Поэтому важное значение имеет определение абстрактного автомата с наименьшим возмож- ным числом состояний, реализующего за­данное отображение слов входного алфа- вита в слова выходного ал­фавита. Рассмотрим алгоритм минимизации числа состо- яний авто­мата. Будем называть k-эквивалентными два состояния автомата Мили (k = 1, 2, ... , ), если автомат, находясь в любом из них, при подаче входного слова из k букв выдает одинаковые выходные сигналы. Если состояние zi k-эквивалентно состоянию zt,a zt k-эквивалентно состоянию zj,то и zi k-эквивалент- но zj. Объединение всех k-эквивалентных состояний автомата образует класс k-экви-валентных состояний. Например, для автомата, заданного табл. 13 и 14, классы 1-эквивалентных состояний, определяемые одинако­выми столбцами таблицы выхо-

 

Таблица 13 Таблица 14

  z0 z1 z2 z3 z4 z5 z6
x1 y1 y2 y2 y1 y1 y2 y2
x2 y1 y2 y2 y1 y1 y2 y2
x3 y2 y3 y3 y2 y2 y3 y3
  z0 z1 z2 z3 z4 z5 z6
x1 z0 z3 z3 z6 z0 z3 z4
x2 z1 z2 z2 z5 z1 z2 z0
x3 z3 z1 z1 z4 z3 z1 z6

 

дов, будут следующие:

B11 = {z0, z3, z4} , B12 = {z1, z2, z5, z6 } (21)

(первый индекс при В является степенью эквивалентности k, а вто­рой – порядковым номером класса для данного k).

Для того чтобы из классов k-эквивалентных состояний сформи­ровать клас- сы k + 1-эквивалентных состояний, необходимо найти классы 1-эквивалентных сос-тояний внутри каждого класса k-эквивалентных состояний. Признаком разбиения множества состоя­ний автомата на классы -эквивалентности является совпадение разбиения на классы k-эквивалентных состояний с разбиением на классы к + 1-эквивалентных состояний. Таким образом, разбие­ние на классы -эквивалентных состояний может быть достигнуто за конечное число шагов. Если теперь из каж- дого класса -экви­валентных состояний выбрать по одному состоянию, то полу- чим автомат, имеющий минимальное число состояний, равное числу классов -эквивалентности, и формирующий при подаче любого входного слова те же вы- ходные сигналы, что и исходный автомат. Определим классы -эквивалентных состоя­ний для автомата, заданного табл. 13 и 14. На основе табл. 13 и выраже- ний (21) построим таблицу разбиения на классы 1-экви­валентности (табл. 15), за- меняя при этом состояния zi соответствующими классами эквивалентности. По табл. 15 получаем разбиение на классы 2-эквивалентности:

B21 = {z0, z4}, B22 = {z3}, B23 = {z1, z2, z5}, B24 = {z6}. (22)

Аналогично на основе табл. 13 и выражений (22) строим таб­лицу разбие- ния на классы 2-эквивалентных состояний (табл. 16), из которой получаем раз-

 

Таблица 15 Таблица 16

  B21 B22 B23 B24
z0 z4 z3 z1 z2 z5 z6
x1 B21 B21 B24 B22 B22 B22 B21
x2 B23 B23 B23 B23 B23 B23 B21
x3 B22 B22 B21 B23 B23 B23 B24
  B11 B12
z0 z3 z4 z1 z2 z5 z6
x1 B11 B12 B11 B11 B11 B11 B11
x2 B12 B12 B12 B12 B12 B12 B11
x3 B11 B11 B11 B12 B12 B12 B12

 

биение на классы 3-эквивалентности:

 

B31 = B21 = {z0, z4}, B32 = B22 = {z3}, B33 = B23 = {z1, z2, z5}, B34 = B24 = {z6}.

 

Таким образом, разбиение множества состояний автомата на классы -эк-вивалентности совпадает с разбиением его на классы 2-эквивалентных состояний. Выберем теперь из каждого класса 2-эквивалентности произвольно по одному сос-тоянию, например z0, z3, z1, z6. Заменяя в табл. 13 состояние z4 -эквивалентным ему состоянием z0, состояния z2 и z5 – состоянием z1и вычеркивая лиш­ние столб- цы в табл. 14, получаем автомат с минимальным числом состояний (табл. 17 и 18).

 

Таблица 17 Таблица 18

  z0 z1 z3 z6
x1 y1 y2 y1 y2
x2 y1 y2 y1 y2
x3 y2 y3 y2 y3
  z0 z1 z3 z6
x1 z0 z3 z6 z0
x2 z1 z1 z1 z0
x3 z3 z1 z0 z6

 

 

Для минимизации числа состояний автоматов Мура необходимо дополни-тельно рассматривать классы 0-эквивалентных состояний. При этом 0-зквивалент- ными называются любые одинаково отмечен­ные состояния автомата Мура. Все дальнейшие классы k-эквивалентности в данном случае определяются так же, как и для автома­та Мили.

В схемах ВТ часто встречаются автоматы, на входы которых некоторые последовательности сигналов никогда не подаются. Такие последовательности на-зываются запрещенными входными словами. Прн наличии запрещенных входных слов функции переходов и выходов будут определены не для всех пар значений z и х. Такие автоматы называются частичными автоматами. Графы частичных ав­томатовимеют узлы,у которых количество выходящих ветвей меньше числабукв входного алфавита.При синтезе частичного ав­томата производят доопределение функций переходов ивыходов стем, чтобы максимально упростить его реализа-цию.

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

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

Если для каждой пары zi и zj состояний автомата найдется хотя бы один входной сигнал, переводящий его из состояния zi в состоя­ние zj при i j и i = j, то такой автомат называется автоматом с пол­ной системой переходов.

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

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

Канонический метод структурного синтеза ав­томатов состоит в сведении задачи синтеза произвольных авто­матов к задаче синтеза комбинационных схем. Этот метод ориентиро­ван на использование структурно полного набора триггеров и ло­гических элементов и на обобщенное представление структурной схе­мы автомата в виде, показанном на рис. 5, а.

Обобщенная схема автомата состоит из триггеров Q1, Q2, ... ,Qm и ком-бинационной схемы F, связанных между собой так, чтобы вы­полнялись заданные условияработы автомата. Каждоесостояниеzi синтезируемогоавтомата кодирует- ся набором состояний триггеров.

Структурный синтез сводится к построению такой схемы автома­та, которая функционирует в соответствии с заданными таблицами переходов и выходов автомата. Для такого построения необходимо:

1. Поставить в соответствие каждой из букв хi и yi входного и выходного ал-фавитов абстрактного автомата совокупности букв структурного алфавита, т.е. вы-полнить кодирование входных и вы­ходных сигналов.

2. Определить количество и выбрать типы триггеров.

3. Поставить в соответствие каждому состоянию zi абстрактного автомата со-вокупность состояний Q1, Q2, … , Qm триггеров (выпол­нить кодирование состояний автомата).

4. Найти переключательные функции q1, q2, … , qm и у1, у2,... , ут. Эти функ- ции определяют структуру комбинационной схе­мы F.

 

Рис. 5

Число r и р входов и выходов структурных автоматов, а также число т триггеров при использовании двузначного структурного алфавита определяются из условий

где п и k – соответственно число букв во входном и выходном алфа­витах абст- рактного автомата, l – число состояний автомата.

Функция (i = 1, 2, ... , т)называется функцией возбуждения триггера Qi и определяет значение входного сигнала триггера в за­висимости от состояний триггеров и значений сиг­налов на входах автома- та, т. е.

 

Значения аргументов и функции в этом выражении определены для одного и того же момента дискретного времени, поэтому qi является переключательной функцией. Для триггера, имеющего не­сколько входов, на этапе структурного син- теза следует получить функцию возбуждения каждого его входа. Определение значений функций возбуждения i-гo триггера может быть произведено путем под-становки в его функцию переходов значений и ,взя тых из кодирован- ной таблицыпереходов заданного автомата,и последующегорешения полученно- го уравнения относительно значений . Так какчисло различных уравнений та- кого типа равно всего 4 (для наборов 00, 01, 10, 11 состояний и ,то на практике частопользуются готовыми таблицами решения такихуравнений, назы-ваемых таблицами возбуждения триггеров. Значение может иногда оказаться неопределенным, т. е. может быть равным как 1, так и 0. В таких случаях значе- ние можно выбирать произволь­но так, чтобы выполнялись условия появления допустимых комби­наций входных сигналов триггеров.

Функция (j = 1, 2 , ... , р)называется функцией выходов и определяет значение сигнала на j-м выходе автомата в зависимости от состояний триггеров и входных сигналов.

При структурном синтезе автоматов может возникнуть ситуация, когда ав-томат из состояния zi входным сигналом хr переводится в состояние zj,а из zj тем же входным сигналом хr – в состояние zi. Если длительность входного сигнала хr превышает время перехода автомата из одного состояния в другое, то, если не приняты спе­циальные меры, автомат проскочит состояние zj,которое является неустойчивым. Следовательно, для обеспечения устойчивости состоя­ний автомата длительность входного сигнала должна быть меньше, чем сумма времени прохож-дения сигнала по самому короткому пути в комбинационной схеме F и времени переключения триггера.

Наиболее распространенным способом обеспечения устойчивости состояний автомата является введение двойной памяти, т. е. дубли­рование каждого элемен- тарного автомата Qi элементарным автома­том (рис. 5, б). Передача информа- ции из ряда триггеров Qi в ряд происходит по сигналу Т, подаваемому во время отсутствия входных сигналов. Для формирования функций возбуждения и функций выходов автомата используются выходы . Автомат из состояния zi пе-рейдет в состояние zj лишь после передачи информа­ции из ряда Qi вряд . По- этому во время действия входных сигна­лов автомат не может пропустить состоя-ние zj.

Устойчивость состояний автомата можно также обеспечить, ис­пользуя две непересекающиеся во времени последовательности синх­ронизирующих сигналов – Т1 и Т2. Если синхронизировать пере­ход автомата из zi в zj сигналом Т1, а пере- ход из zj в zi сигналом Т2, то эти переходы будут вызываться различными вход- ными сигналами хr Т1 и хr Т2. Однако этот способ применим лишь в том случае, когда все переходы в состояние zj могут быть синхронизированы сигналом Т1, а все переходы из zj – сигналом Т2. При этом для любого узла графа автомата все входящие ветви должны быть отме­чены одним из символов Т1, Т2, а все выхо- дящие ветви – другим. В свою очередь, такую разметку графа можно всегда вы- полнить, если все замкнутые последовательности его ветвей содержат четное их число. Для графа, имеющего хотя бы одну нечетную замкну­тую последователь- ность ветвей, указанную разметку осуществитьнельзя. В некоторых случаях замк-нутую нечетную последовательность ветвей можно преобразовать вчетную путем разрыва однойветви последовательности и включения в разрыв дополнительного состояния автомата ,соответствующего нулевому выходному сиг­налу.

При работе автомата могут возникнуть так называемые гонки (состязания). Причиной гонок является то, что триггеры имеют раз­личные времена переключе- ния и различна также задержка сигна­лов, поступающих на входы триггеров по раз-личным цепям схемы F. При переходе автомата из одного состояния в другое, сопровождаю­щемся переключением нескольких триггеров, тот из них, который из-менит свое состояние раньше других, через схему F может изме­нить сигналы на входах триггеров до того,, как они переключаются. Поэтому в процессе перехода из состояния zi в состояние zj под действием входного сигнала хr автомат может ока- заться в некотором состоянии z,переход в которое не указан в таблице перехо- дов или на графе. Пусть, например, сигналом хr автомат, содержащий триг­геры Q1, Q2и Q3, переводится из состояния 011 в состояние 100. Предположим далее, что триггеры Q2 и Q3уже переключались, a Q1остается в исходном состоянии. Тогда автомат окажется в состоянии 000. Если к тому же в автомате имеется пе- реход из 000, например в 010 под действием того же сигнала хr,то автомат в ре-зультате мо­жет оказаться в состоянии 010, а не в 100.

Исключить гонки можно путем введения двойной памяти. В этом случае изменение состояний автомата происходит во время отсутст­вия входных сигналов. Кроме того, избежать гонок можно и с по­мощью соответствующего кодирования состояний автомата. Способы кодирования состояний автомата, исключающие гон- ки, называются противогоночными. Предположим, что состояния автомата закоди­рованы и состоянию zi соответствует код Ki .Обозначим через {Ki - j}множество кодов (наборов) состояний элементарных автоматов, ко­торые могут возникнуть при переходе из zi в zj за счет неодновремен­ного переключения последних. Например, если Ki = 0011 и Kj = 0100, то {Ki - j}={0011, 0000, 0001, 0010, 0101, 0110, 0111, 0100}. Если для любых пар переходов автомата из zi в zj и из zs в zp,вызываемых одним и тем же входным сигналом, во множествах {Ki - j}и {Ks -p}отсутствуют одина- ковые коды, то гонки в таком ав­томате отсутствуют. Если же имеется хотя бы одно состояние, код которого входит как в {Ki - j},так и в {Ks - p},то гонки могут воз-ни­кать.

Пары кодов Ki, Kj и Ks, Kp называются развязанными, если хотя бы один разряд кода принимает одно значение в паре Ki, Kj и про­тивоположное в паре Ks, Kp. В противном случае пары кодов назы­ваются связанными. Например, пары кодов 0100, 0101 и 0000, 0001 развязаны, так как третий разряд в первой паре противо-положен третьему разряду во второй паре. Связанными являются пары кодов 0100, 0101 и 0111, 0101. Для исключения гонок в автомате необхо­димо и достаточно закодировать его состояния так, чтобы для любых пар переходов из zi в zj и из zs в zp,вызываемых одним и тем же входным сигналом, соответствующие пары ко- дов Ki, Kj и Ks, Kp были развязаны.

Эффективным способом противогоночного кодирования является соседнее кодирование. По этому способу любые два состояния ав­томата, соединенные ветвью на графе, кодируются набором двоич­ных цифр, отличающихся лишь в одном раз- ряде. Таким образом, при любом переходе автомата из одного состояния в другое изме­няется состояние лишь одного триггера, и условие отсутствия гонок всегда бу- дет выполнено,