Основы проектирования цифровых устройств с памятью

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

На абстрактном этапе под автоматом подразумевается цифровое устройст- во, задаваемое тремя непустыми множествами X ={x_l, х₂,... , х_п}, Y ={y_l, y₂,... , у_т}, Z = {z_l, z₂, … , z_l},а также двумя функциями:функцией переходов δ ифункцией выходов λ. Мно­жества 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 выхода­ми, имеющий k₁ букв во входном алфавите и k₂букв в выходном ал­фа- вите, заменяется автоматом с одним входом и выходом, входной алфавит которого состоит из букв, а выходной из букв.

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

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

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

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

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

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

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

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

Таблица 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

мата Мура. Кроме того, во множество состояний автомата Мура включим началь- ное состояние z₀автомата Мили. Для рассматриваемого случая такое соответствие представлено табл. 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видно, что состояние z₀ автомата Мили совпадает с состояниями z₃₂, z₀₀, z₂₁, z₁₂, z₂₂ автомата Мура, т. е.

и далее

Поэтому переход автомата Миля из состояния z₀ в состояние z₁ должен соответствовать всем переходам автомата Мура из состояний z₀₀, z₁₂, z₂₁, z_22,, z₃₂ в состояние z₀₁, переход из z₁в z₃ должен соответ­ствовать всем переходам автома- таМураиз z₀₁вz₀₂, z₁₃, z₃₃ и т. д. Отсюда следует, что если состояние z_ij входит во множество состоя­ний, совпадающих с состоянием z_r, тостолбец таблицы пере- ходов для состояния z_ij будет совпадать со столбцом таблицы переходов для со- стояния z_r. Значения функции выходов для эквивалентно­го автомата Мура опреде-ляются соотношением при z_ij ≠ z₀₀.

Для начального состояния z₀₀ значение выходного сигнала выби­рается про-извольно. Таким образом, переходы и выходные сигналы эквивалентного автомата Мура определяются табл. 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

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

δ₂(z, x) = δ₁(z, x), λ₂(z, x) = λ₁(δ₁(z, x)) .

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

Число состояний автомата существенно влияет на егосложность. Поэтому важное значение имеет определение абстрактного автомата с наименьшим возмож- ным числом состояний, реализующего за­данное отображение слов входного алфа- вита в слова выходного ал­фавита. Рассмотрим алгоритм минимизации числа состо- яний авто­мата. Будем называть k-эквивалентными два состояния автомата Мили (k = 1, 2, ... , ∞), если автомат, находясь в любом из них, при подаче входного слова из k букв выдает одинаковые выходные сигналы. Если состояние z_i k-эквивалентно состоянию z_t,a z_t k-эквивалентно состоянию z_j,то и z_i k-эквивалент- но z_j. Объединение всех 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

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

B₁₁ = {z₀, z₃, z₄} , B₁₂ = {z_1, z₂, z₅, z₆ } (21)

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

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

B₂₁ = {z₀, z₄}, B₂₂ = {z₃}, B₂₃ = {z₁, z₂, z₅}, B₂₄ = {z₆}. (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-эквивалентности:

B₃₁ = B₂₁ = {z₀, z₄}, B₃₂ = B₂₂ = {z₃}, B₃₃ = B₂₃ = {z₁, z₂, z₅}, B₃₄ = B₂₄ = {z₆}.

Таким образом, разбиение множества состояний автомата на классы ∞-эк-вивалентности совпадает с разбиением его на классы 2-эквивалентных состояний. Выберем теперь из каждого класса 2-эквивалентности произвольно по одному сос-тоянию, например z₀, z₃, z₁, z₆. Заменяя в табл. 13 состояние z₄ ∞-эквивалентным ему состоянием z₀, состояния z₂ и z₅ – состоянием z₁и вычеркивая лиш­ние столб- цы в табл. 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 и х. Такие автоматы называются частичными автоматами. Графы частичных ав­томатовимеют узлы,у которых количество выходящих ветвей меньше числабукв входного алфавита.При синтезе частичного ав­томата производят доопределение функций переходов ивыходов стем, чтобы максимально упростить его реализа-цию.

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

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

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

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

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

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

Обобщенная схема автомата состоит из триггеров Q₁, Q₂, ... ,Q_m и ком-бинационной схемы F, связанных между собой так, чтобы вы­полнялись заданные условияработы автомата. Каждоесостояниеz_i синтезируемогоавтомата кодирует- ся набором состояний триггеров.

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

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

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

3. Поставить в соответствие каждому состоянию z_i абстрактного автомата со-вокупность состояний Q₁, Q₂, … , Q_m триггеров (выпол­нить кодирование состояний автомата).

4. Найти переключательные функции q₁, q₂, … , q_m и у₁, у₂,... , у_т. Эти функ- ции определяют структуру комбинационной схе­мы F.

Рис. 5

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

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

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

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

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

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

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

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

При работе автомата могут возникнуть так называемые гонки (состязания). Причиной гонок является то, что триггеры имеют раз­личные времена переключе- ния и различна также задержка сигна­лов, поступающих на входы триггеров по раз-личным цепям схемы F. При переходе автомата из одного состояния в другое, сопровождаю­щемся переключением нескольких триггеров, тот из них, который из-менит свое состояние раньше других, через схему F может изме­нить сигналы на входах триггеров до того,, как они переключаются. Поэтому в процессе перехода из состояния z_i в состояние z_j под действием входного сигнала х_r автомат может ока- заться в некотором состоянии z_ω,переход в которое не указан в таблице перехо- дов или на графе. Пусть, например, сигналом х_r автомат, содержащий триг­геры Q₁, Q₂и Q₃, переводится из состояния 011 в состояние 100. Предположим далее, что триггеры Q₂ и Q₃уже переключались, a Q₁остается в исходном состоянии. Тогда автомат окажется в состоянии 000. Если к тому же в автомате имеется пе- реход из 000, например в 010 под действием того же сигнала х_r,то автомат в ре-зультате мо­жет оказаться в состоянии 010, а не в 100.

Исключить гонки можно путем введения двойной памяти. В этом случае изменение состояний автомата происходит во время отсутст­вия входных сигналов. Кроме того, избежать гонок можно и с по­мощью соответствующего кодирования состояний автомата. Способы кодирования состояний автомата, исключающие гон- ки, называются противогоночными. Предположим, что состояния автомата закоди­рованы и состоянию z_i соответствует код K_i .Обозначим через {K_{i - j}}множество кодов (наборов) состояний элементарных автоматов, ко­торые могут возникнуть при переходе из z_i в z_j за счет неодновремен­ного переключения последних. Например, если K_i = 0011 и K_j = 0100, то {K_{i - j}}={0011, 0000, 0001, 0010, 0101, 0110, 0111, 0100}. Если для любых пар переходов автомата из z_i в z_j и из z_s в z_p,вызываемых одним и тем же входным сигналом, во множествах {K_{i - j}}и {K_{s -p}}отсутствуют одина- ковые коды, то гонки в таком ав­томате отсутствуют. Если же имеется хотя бы одно состояние, код которого входит как в {K_{i - j}},так и в {K_{s - p}},то гонки могут воз-ни­кать.

Пары кодов K_i, K_j и K_s, K_p называются развязанными, если хотя бы один разряд кода принимает одно значение в паре K_i, K_j и про­тивоположное в паре K_s, K_p. В противном случае пары кодов назы­ваются связанными. Например, пары кодов 0100, 0101 и 0000, 0001 развязаны, так как третий разряд в первой паре противо-положен третьему разряду во второй паре. Связанными являются пары кодов 0100, 0101 и 0111, 0101. Для исключения гонок в автомате необхо­димо и достаточно закодировать его состояния так, чтобы для любых пар переходов из z_i в z_j и из z_s в z_p,вызываемых одним и тем же входным сигналом, соответствующие пары ко- дов K_i, K_j и K_s, K_p были развязаны.

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