Понятие о гонках. Противогоночное кодирование

При функционировании автомата могут появиться так называемые состязания (гонки). Явление состязаний возникает вследствие того, что элементы памяти имеют различные, хотя и достаточно близкие, времена срабатывания. Кроме того, различны задержки сигналов возбуждения, поступающих на входные каналы элементов памяти по логическим цепям неодинаковой длины. Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько триггеров, то между ними начинаются состязания. Тот элемент, который выиграет эти состязания, т. е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых триггеров до того, как другие участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное его графом. Поэтому в процессе перехода из состояния а_m в состояние а_S  под действием входного сигнала z_f автомат может оказаться в некотором промежуточном состоянии а_k или а_l, в зависимости от того, какой элемент памяти выиграет состязания.

Если затем при том же входном сигнале автомат из а_k и а_l перейдет в состояние а_{S ,} то такие состязания являются допустимыми, или некритическими. Если же в этом автомате есть переход, например, из а_k в а_j ≠ a_S, под действием того же сигнала Z, то автомат может перейти в а_j, а не в а_S, и правильность его работы тем самым будет нарушена. Такие состязания называются критическими состязаниями или гонками. При кодировании состояний гонки должны быть устранены. Кодирование с устранением гонок называется противогоночным.

Один из способов ликвидации гонок состоит в тактировании входных сигналов автомата импульсами определенной длительности. Предполагается, что кроме входных полюсов x₁,…,x_l имеется еще один полюс р от генератора синхроимпульсов (ГСИ), по которому поступает сигнал
р = 1 в момент прихода импульса и р = 0 при его отсутствии. В связи с этим на переходе (а_m, а_S) входным сигналом будет не z, а рz. Тогда, если длительность импульса меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационной схеме, то к моменту перехода в промежуточное состояние а_k сигнал р равен нулю и, следовательно, рz = 0, что и исключает гонки.

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

Таким образом, состязания могут возникнуть только между нижними триггерами, сигналы обратной связи не смогут измениться до тех пор, пока р не станет равным нулю. Но тогда входной сигнал рz_f также равен нулю, а потому гонок быть не может.

Наряду с аппаратурными способами для устранения гонок могут использоваться специальные методы кодирования, которым посвящено большое число работ. Например, предлагается метод противогоночного кодирования, основная идея которого сводится к следующему: пусть (a,b) и (c,d) - две пары двоичных кодов длиной m. Пары (a,b) и (c,d) называются развязанными, если при некотором 1 ≤ r ≤ m r-й разряд кода принимает одно значение на паре (a,b) и противоположное на паре (c,d). В противном случае пары двоичных кодов (a,b) и (c,d) называются связанными.

Доказана следующая теорема.

В автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют, если для любых двух переходов (аm,…,а s ) и (аk,…,al), а s ≠ аl, происходящих под действием одного и того же входного сигнала, соответствующие пары кодов состояний развязаны.

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

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

Таким образом, имеются 4 способа устранения гонок:

· двойная память;

· рациональный выбор длительности синхроимпульса;

· развязывание пар переходов;

· соседнее кодирование.

Проектирование автомата

Проектирование автомата заключается в определении функций {y_i,v_j | i=1,…,m, j=1,…,k} и синтезе в заданном базисе схемы, реализующей эти функции.

Выходные функции определяются по матрице выходов автомата: после кодировки входов, выходов и состояний автомата матрица выходов представляет таблицу, описывающую m булевых выходных функций.

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

 Для счётного триггера эти функции получаются как результат операции сложения по модулю два кодов текущего и следующего
состояний.

Пример. Пусть автомат описывается матрицами переходов и выходов (табл.2.3 и 2.4).

Таблица 2.3					Таблица 2.4
	a1	a2	a3	a4				a1	a2	a3	a4
z1	a2	a2	a3	a3			z1	w1	w2	w2	w1
z2	a4	a2	a1	a4			z2	w2	w2	w2	w1
z3	a4	a3	a2	a1			z3	w1	w1	w1	w2

 

 

Таблица 2.5
	00	01	11	10
00	0	1	1	0
01	1	1	1	0
11	0	0	0	1

Введём следующие кодировки для состояний, входов и выходов автомата (через переменные ai, Zj и wr): a1=00, a2=01, a3=11, a4=10,

Z1=00, Z2=01, Z3=11, w1=0,w2=1.

Перепишем в этой кодировке матрицу выходов, получим описание выходных
(в данном примере всего одной) функций (табл.2.5).

Таблица 2.6
	00	01	11	10
00	01	01	11	11
01	10	01	00	10
11	10	11	01	00

Если обозначить кодирующие переменные входа как x1 и x2, состояний как t1 и t2, выхода как y, то функция выхода будет иметь вид:

y=`t1•x2Ú`t1•t2•`x1 Út1•x1•`x2.

Если в качестве элемента памяти задан триггер типа линии задержки, то, заменив в табл.2.2 состояния на их коды, получим описание пары функций v1 и v2 (первый и второй столбец в
табл. 2.6).

По этой таблице

 v1=`t1•`t2•x2Ú`t1•x1Út1•`x2Ú`t2•`x1•x2.

v2=`x1•`x2Ú`t1•t2•x2Út2•x1•x2.

Если задан счётный триггер, то функции будут иметь вид, показанный в табл.2.7.

В этом случае функции имеют вид:

Таблица  2.7
	00	01	11	10
00	01	00	00	01
01	10	00	11	00
11	10	10	10	10

v1=`t1•`t2x•2Úx1•x2Út1•t2•x2,

v2=`t2•`x1•`x2Út1•xt•`x1•x2.

 

Рассмотрим ещё один пример.

Построим автомат-счётчик чисел от 0 до 9 с выходом на семисегментный индикатор. Индикатор имеет вид, как на рис.2.3. Числам сопоставляются выделенные сегменты индикатора в соответствии с
табл. 2.8.

На рис. 2.4 в качестве примера показана индикация цифры 5.

Таблица 2.8
число сегмент	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	0	0	1	1	1
2	1	1	0	1	1	1	1	1	1	1
3	1	0	1	1	0	1	1	0	1	1
4	1	0	1	0	0	0	1	0	1	0
5	1	0	0	0	1	1	1	0	1	1
6	1	0	1	1	0	1	1	1	1	1
7	0	0	1	1	1	1	1	0	1	1

Автомат Мура имеет 10 состояний от 0 до 9, 7 выходов, которые выделяют сегменты в соответствии с табл. 2.8 (1 означает, что сегмент виден, 0 – не виден). На единственный вход автомата поступает двоичный сигнал 0 или 1, 0 оставляет автомат (а значит, и число на индикаторе) в прежнем виде, 1 переводит автомат в следующее состояние и на индикаторе высвечивается следующее число. Значит, таблица переходов имеет вид как в табл. 2.9.

Таблица 2.9
Z\a	0	1	2	3	4	5	6	7	8	9
0	0	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9	0

Для кодировки необходимо взять 4 элемента памяти. Закодируем состояния автомата последовательно кодами

0	1	2	3	4	5	6	7	8	9
0000	0001	0010	0011	0100	0101	0110	0111	1000	1001

 

Тогда таблица переходов запишется, как в табл.2.10.

 

Таблица 2.10
t1,t2,t3,t4 x	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001
0	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001
1	0001	0010	0011	0100	0101	0110	0111	1000	1001	0000

 

Если в качестве триггера выбрана задержка, то данная таблица описывает 4 функции возбуждения элементов памяти v1-v4 от переменных t1-t4 и х. Переменная х кодирует z: z1=0, z2=1. Первая функция v1 имеет вид как табл.2.11. Здесь для удобства выход четвёртого триггера вынесен в имя строки.

Таблица 2.11
t1,t2,t3 t4,x	000	001	010	011	100	101	110	111
0 0	0	0	0	0	1	-	-	-
0 1	0	0	0	0	1	-	-	-
1 0	0	0	0	0	1	-	-	-
1 1	0	0	0	1	0	-	-	-

 

 

Отсюда v1=t1×`t4 v t1×`x v t2×t3×t4×x.

 

Таблица 2.12
t1,t2,t3 t4,x	000	001	010	011	100	101	110	111
0 0	0	0	1	1	0	-	-	-
0 1	0	0	1	1	0	-	-	-
1 0	0	0	1	1	0	-	-	-
1 1	0	1	1	0	0	-	-	-

 

 

` v2= t2×`t4 v×t2×`x v t2×`t3 v `t2×t3×t4×x

 

 

Таблица 2.13
t1,t2,t3 t4,x	000	001	010	011	100	101	110	111
0 0	0	1	0	1	0	-	-	-
0 1	0	1	0	1	0	-	-	-
1 0	0	1	0	1	0	-	-	-
1 1	1	0	1	0	0	-	-	-

 

 v3= t3×`t4 v ×t3×`x v `t1×`t3×t4×x

 

Таблица 2.14
t1,t2,t3 t4,x	000	001	010	011	100	101	110	111
0 0	0	0	0	0	0	-	-	-
0 1	1	1	1	1	1	-	-	-
1 0	1	1	1	1	1	-	-	-
1 1	0	0	0	0	0	-	-	-

 

 

v4=`t4× x v t4×`x

Проектируемый автомат является автоматом Мура. Записав соответствие между состояниями и выходами, получим формулы для выходных функций.

Задание. Выпишите функции для каждого сегмента индикатора.

 

Упражнение

 

Кодирование

 

Для заданного автомата построить кодирование состояний, свободное от гонок методом развязывания пар состояний.

 

 

Вариант 1

 

	1	2	3	4	5	6	7	8
z1	8	2	4	4	7	2	7	8
z2	1	3	3	6	1	6	1	3
z3	1	5	6	4	5	6	4	1

 

Вариант 2

 

	1	2	3	4	5	6	7	8
z1	1	4	6	4	1	6	8	8
z2	1	2	3	2	5	1	5	3
z3	5	7	3	2	5	3	7	2

 

Вариант 3

 

	1	2	3	4	5	6	7	8
z1	4	7	3	4	5	3	7	5
z2	1	2	6	8	1	6	2	8
z3	3	6	3	5	5	6	7	7

 

 

Вариант 4

 

	1	2	3	4	5	6	7	8
z1	3	5	3	4	5	4	7	7
z2	1	4	1	4	5	6	5	6
z3	8	2	6	7	2	6	7	8

Вариант 5

 

	1	2	3	4	5	6	7	8
z1	3	5	3	8	5	7	7	8
z2	1	2	3	4	4	2	1	3
z3	4	6	5	4	5	6	8	8

 

Вариант 6

 

	1	2	3	4	5	6	7	8
z1	7	2	3	3	2	6	7	6
z2	1	2	1	4	5	2	4	7
z3	4	7	3	4	8	3	7	8

 

Вариант 7

 

	1	2	3	4	5	6	7	8
z1	4	7	5	4	5	8	7	8
z2	1	3	3	5	5	1	8	8
z3	2	2	6	7	6	6	7	2

 

Вариант 8

 

	1	2	3	4	5	6	7	8
z1	2	2	4	4	6	6	8	8
z2	1	1	3	3	5	5	7	7
z3	3	4	3	4	5	6	5	6

 

Вариант 9

 

	1	2	3	4	5	6	7	8
z1	5	6	7	8	5	6	7	8
z2	1	2	3	4	1	2	3	4
z3	4	5	3	4	5	7	7	3

 

Вариант 10

 

	1	2	3	4	5	6	7	8
z1	2	2	4	4	4	6	7	2
z2	7	2	3	5	5	3	7	2
z3	4	8	6	4	5	6	5	8

 

 

Синтез автомата

 

Для заданного автомата определить функции возбуждения элементов памяти

 

Вариант 1

 

	1	2	3	4	5	6	7	8
z1	3	4	2	5	7	2	3	1
z2	1	3	1	6	1	5	1	3
z3	6	5	6	4	2	3	4	2

 

Вариант 2

 

	1	2	3	4	5	6	7	8
z1	5	8	1	2	4	3	3	7
z2	1	2	3	2	7	1	5	3
z3	5	7	4	2	5	3	1	2

 

Вариант 3

 

	1	2	3	4	5	6	7	8
z1	4	6	2	3	4	2	7	5
z2	1	2	6	1	1	6	2	8
z3	2	6	3	4	5	3	6	7

 

 

Вариант 4

 

	1	2	3	4	5	6	7	8
z1	3	5	2	6	5	4	7	7
z2	2	4	1	4	7	6	5	6
z3	8	2	6	7	2	1	3	5

 

 

Вариант 5

 

	1	2	3	4	5	6	7	8
z1	3	5	4	7	5	4	7	2
z2	1	2	3	7	4	2	1	3
z3	7	6	5	3	6	6	8	1

 

 

Вариант 6

 

	1	2	3	4	5	6	7	8
z1	8	2	3	5	2	8	7	6
z2	1	2	1	4	5	2	4	7
z3	4	7	2	4	8	3	5	8

 

Вариант 7

 

	1	2	3	4	5	6	7	8
z1	4	7	5	4	2	3	7	5
z2	1	3	3	5	5	1	8	1
z3	2	2	6	7	6	6	7	2

 

Вариант 8

 

	1	2	3	4	5	6	7	8
z1	2	3	4	1	6	7	8	2
z2	4	1	3	2	2	5	1	7
z3	3	4	5	2	2	7	5	6

 

 

Вариант 9

 

	1	2	3	4	5	6	7	8
z1	5	6	7	8	1	6	3	2
z2	1	5	2	3	1	2	8	4
z3	4	5	3	4	5	7	6	3

 

 

Вариант 10

 

	1	2	3	4	5	6	7	8
z1	1	2	4	3	4	6	1	2
z2	7	2	3	5	5	3	7	2
z3	4	8	6	4	7	2	5	8

 

 

Синтез схем

Определения

Пусть задано множество Y элементов, каждый из которых имеет единственный выходной полюс и характеризуется числом входных полюсов и реализуемой этим элементом функцией от значений на входных полюсах. Значения переменных на входных и выходных полюсах элементов принимаются из множества {0,1}. Будем считать, что каждый элемент из Y определяет тип элемента и что в наличии есть неограниченное множество элементов данного типа.

Схемой назовём композицию элементов из Y, полученную отожде-ствлением (связыванием) выходов некоторых элементов с входами других элементов, при которой выполняются следующие свойства:

1. С каждым входом связано не более одного выхода.

2. В схеме не образуются контуры.

3. С каждым выходом может быть связано более одного входа.

Назовём эти свойства свойством корректности связей схемы.

Все несвязанные входы элементов схемы назовём её входами, несвязанные выходы элементов и некоторые выделенные связанные выходы элементов схемы назовём выходами схемы.

Пример схемы приведён на рис. 3.1.

Здесь x, y и z – входы схемы, g и f – её выходы, элементы 1 и 2 реализуют функцию конъюнкции, элемент 3 – функцию инверсии.

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

 Для схемы 1: f=(x×y)×Z, g=x×y .

Множество Y назовём базисом схемы.

Задачей синтеза схем назовём задачу построения в заданном базисе Y для заданных функций F ={ f 1, f 2,…, fm } схемы, реализующей эти функции.

Будем оценивать решение числом элементов в схеме.

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

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: