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

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

На абстрактном этапе под автоматом подразумевается цифровое устройст- во, задаваемое тремя непустыми множествами 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

	z 0	z 1	z 2	z 3
x 1	y 3	y 2	y 1	y 1
x 2	y 2	y 1	y 3	y 3
x 3	y 1	y 2	y 2	y 3

	z 0	z 1	z 2	z 3
x 1	z 1	z 2	z 0	z 2
x 2	z 3	z 0	z 0	z 0
x 3	z 2	z 3	z 2	z 3

 

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

 

Таблица 11

	z 0 z 00	z 1	z 2	z 3
x 1	z 1 z 01	z 2 z 11	z 0 z 21	z 2 z 31
x 2	z 3 z 02	z 0 z 12	z 0 z 22	z 0 z 32
x 3	z 2 z 03	z 3 z 13	z 2 z 23	z 3 z 33

 

лов, то эквивалентный автомат Мура будет иметь 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

x 1

z 01

z 11

z 31

z 21

z 21

z 01

z 31

z 01

z 01

z 21

z 21

z 01

z 31

x 2

z 02

z 12

z 32

z 22

z 22

z 02

z 32

z 02

z 02

z 22

z 22

z 02

z 32

x 3

z 03

z 13

z 33

z 23

z 23

z 03

z 33

z 03

z 03

z 23

z 23

z 03

z 33

 

Задача перехода от автомата Мура к эквивалентному автомату Мили реша- ется очень просто. Если δ₁ и λ₁– функции переходов и выходов автомата Мура, то функции переходов δ₂(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

	z 0	z 1	z 2	z 3	z 4	z 5	z 6
x 1	y 1	y 2	y 2	y 1	y 1	y 2	y 2
x 2	y 1	y 2	y 2	y 1	y 1	y 2	y 2
x 3	y 2	y 3	y 3	y 2	y 2	y 3	y 3

	z 0	z 1	z 2	z 3	z 4	z 5	z 6
x 1	z 0	z 3	z 3	z 6	z 0	z 3	z 4
x 2	z 1	z 2	z 2	z 5	z 1	z 2	z 0
x 3	z 3	z 1	z 1	z 4	z 3	z 1	z 6

 

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

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

	B 21	B 22	B 23	B 24
z 0	z 4	z 3	z 1	z 2	z 5	z 6
x 1	B 21	B 21	B 24	B 22	B 22	B 22	B 21
x 2	B 23	B 23	B 23	B 23	B 23	B 23	B 21
x 3	B 22	B 22	B 21	B 23	B 23	B 23	B 24

	B 11	B 12
z 0	z 3	z 4	z 1	z 2	z 5	z 6
x 1	B 11	B 12	B 11	B 11	B 11	B 11	B 11
x 2	B 12	B 12	B 12	B 12	B 12	B 12	B 11
x 3	B 11	B 11	B 11	B 12	B 12	B 12	B 12

 

биение на классы 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

	z 0	z 1	z 3	z 6
x 1	y 1	y 2	y 1	y 2
x 2	y 1	y 2	y 1	y 2
x 3	y 2	y 3	y 2	y 3

	z 0	z 1	z 3	z 6
x 1	z 0	z 3	z 6	z 0
x 2	z 1	z 1	z 1	z 0
x 3	z 3	z 1	z 0	z 6

 

 

Для минимизации числа состояний автоматов Мура необходимо дополни-тельно рассматривать классы 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 были развязаны.

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