Минимизация числа переключений элементов памяти.

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

Алгоритм кодирования:

1) Определяем множество пар состояний, между которыми существует переход M.

2) Выбирается любая пара состояний, между которыми есть переход, один из них кодируется всеми нулями, а другой нулями и одной единицей.(00…01)

3) Из множества M удаляются пары состояний, которые уже закодированы M\(S_i S_j), если станет равным 0, то процесс завершается.

4) Берем любую пару в которой одно состояние уже закодировано, а другое нет (*, S_q) S_q  - незакодированное состояние, * - состояние закодировано. Далее кодируем это состояние.

5) Выбираем множество пар из M куда входит S_q (M_q)

6) Из M_q  выбираем все закодированные состояния (B_q)

7) Строим множество кодов, имеющих расстояние d, с каждым кодом из состояния B_q

8) Для каждого кода из всех множеств C^d_q определяется сумма расстояний по Хеммингу с каждым кодом из B_q Выбирается код, имеющий минимальную сумму и этот код приписывается C_q Деле возврат к пункту 3.

 

Пример:

 

1) Пары состояний M = {(1,2),(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)}

2) {1,2} => S₁ = 000 S₂ = 001         

 

3) M = {(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)}

4) {2,4}

    q=4

5) M_q = {(2,4),(3,4),(4,5)}

6) B_q = {2}

7) C¹₄ = {101,011}

8) 101 + 001 = 100 d =1

011 + 001 = 010 d =1

S₄ = 101

3) M = {(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)}

4) {2,5} q=5

5) M_q = {(2,5),(1,5),(4,5)}

6) B_q = {2,4,1}

7) C¹₅ = {011}

C¹₅ = {(111),(100)}

C¹₅ = {(100),(010)}

8) 011 + 001 = 010

011 + 101 = 110

011 + 000 = 110

111 + 001 = 110

111 + 101 = 010

111 + 000 = 111

100 + 001 = 101

100 + 101 = 001

100 + 000 = 100

010 + 001 = 011

010 + 101 = 111

010 + 000 = 010

S₅ = 100

3) M = {(2,3,(3,4) }

4) {2,3} q=3

5) M_q = {(2,3),(3,4)}

6) B_q = {2,4}

7) C¹₅ = {011}

C¹₅ = {(111)}

C¹₅ = {(100),(010)}

8) 011 + 001 = 010

    011 + 101 = 110

    111 + 001 = 110

    111 + 101 = 010

    S₃ = 011

3) M = {0 } – конец цикла.

 

 

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

 

Универсальный способ кодирования (для синхронного автомата).

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

Для D триггера:

D₂ = q₁⌐q₂q₃⌐x₁ – любой код

D₂ = q₁⌐x₁  - унитарный код

Для унитарного кода опущены ⌐q₂⌐q₃, так как если q₁ = 1, то это однозначно подразумевает q₂ = q₃ = 0. Более того q₁ = 1 невозможно ни для одного из оставшихся состояний автомата.

 

 

Пример:

 

     0à1 0à1

D₁ =   q₅x v q₃x

     5à1 3à1

 

     0à1 

D₂ =   q₁⌐x 

     1à2

 

     0à1 0à1 0à1

D₃ =   q₁x v q₂x v q₄x

     1à3 2à3 4à3

 

     0à1 1à1

D₄ =   q₂⌐x v q₄⌐x

     2à4 2à4

 

     0à1 

D₅ =   q₃⌐x 

     3à5

 

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

R = 1, когда 1à0 обязательно

R = 1, когда 0à0 можно

S = 1, когда 0à1 обязательно

S = 1, когда 1à1 возможно

Для RS триггера сначала записываются функции обязательные, а там где возможно чтобы функция была равна 1 дописывают лишь в случае упрощения.

 

RS         

*0

0 à 0

01

0 à 1

10

1 à 0

0*

1 à 1

    1à0   1à0

R₁ = q₁⌐X v q₁X = q₁

    1à2   1à3

    0à1   0à1

S₁ = q₅X v q₃X = X(q₁ v q₃)

    5à1   3à1

В функции R_1, S₁ входит обязательная конъюнкция, обеспечивающая переход 1à0 для R₁  и 0à1 для S₁. В R₁ можно добавить конъюнкции переходов из 0à0, т.к. при этом R=*  и может быть доопределено до 1. Упростить R=q - можно добавить только ⌐q₁, однако при унитарном кодировании инверсное значение ⌐q не используется, а следовательно переходы 0à0 добавленные в R₁ только усложнят функцию.

Аналогично для S₁ можно добавить конъюнкции соответствующие переходу 1à1, такой переход возможен, только если присутствует петля вокруг S₁, в примере ее нет, значит получим окончательное значение R₁ S_1.

    1à0   1à0

R₂ = q₂⌐X v q₂X = q₂

    2à4   2à3

 

    0à1 

S₂ = q₁⌐X

    1à2

 

    1à0 

R₃ = q₃

    3à1

    3à5

 

    0à1   0à1    0à1

S₃ = q₁X v q₂X v q₄X = X(q_{1 v} q₂ v q₄)

    1à3   2à3  4à3

 

    1à0 

R₄ = q₄X

    4à3

 

    0à1   1à1

S₄ = q₂⌐X v q_4⌐X = q₂

    2à4   4à4

 

R₅ = q₅X

 

S₅ = q3⌐X

 

Автомат с дешифратором.

 

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

Каждому состоянию соответствует два кода с минимальным и максимальным числом разрядов, недостаток схемы – дополнительные затраты виде дешифратора.

Два кода, предписанных одному состоянию, связаны между собой функцией дешифратора.

 

 

При кодировании состояний предполагаем наличие дешифратора.

В данном случае 2à4 (2 входа, 4 выхода)

Каждому состоянию соответствует два входа.

При записи функции возбуждения в данном случае аргументами являются Y_i и X_i, а переходы триггера 0à0; 0à1; 1à0; 1à1 рассматриваются относительно q_i/

Рассмотрим D и RS триггера:

В качестве элемента памяти используется 2 D триггера.

На D подаем 1 при переходе 0à1; 1à1

 

     0à1     0à1    1à1        0à1      1à1

D₁ = Y0⌐X v Y₀X   v Y₁⌐X v Y₂⌐X     v Y₃⌐X = Y₀ v ⌐X (Y_{1 v} Y₂ v Y₃)

     1à2     1à4    2à4        3à2      4à4

 

     0à1     0à1     1à1        1à1

D₂ = Y₁X v Y₁⌐X v Y₃X v Y₃⌐X = Y₁ v Y₃

     2à3     2à4     4à3        4à4

 

Далее RS триггер (R₁ – сброс 1 разряда)

 

     1à0     1à0    0à0

R₁ =  Y₁X     v Y₃X v  Y₂X

     2à3     4à3    3à1

 

 

      0à1      0à1       1à1         1à1         0à1

S₁ = Y0⌐X v Y₂⌐X v Y1⌐X v Y₃⌐X v Y₀X = ⌐X (Y₀ v Y₂) v Y₀X

      1à2      3à2       2à4         4à4         1à4

 

     1à0        1à0       0à0

R₂ =  Y₂X     v   Y₂⌐X v  Y0⌐X = Y₂

     3à1        3à2       1à2

 

      0à1      0à1       0à1         1à1          1à1

S₂ =  Y0X v  Y₁⌐X v   Y1X v  Y₃X v  Y3⌐X = Y₀X  v Y₁

      1à4      2à4       2à3         4à3          4à4

 

 

Асинхронные автоматы.

 

Ранее рассматривались:

 

 

т.е.раньше неявно присутствовал синхроимпульс.

Наличие синхроимпульса позволяло осуществлять переход, при отсутствии его автомат остается в текущем состоянии.

По существу синхроимпульс является дополнительным входным сигналом. Входные сигналы можно разделить в зависимости от наличия синхроимпульса:

1. Синхронизируемое

С – синхроимпульс

Пример:

 

             Разновидностью данного сигнала является импульсный сигнал

1. Потенциальный сигнал

 

 

          Новое входное значение появляется после изменений предыдущего значения, т.е. длительности 0 и 1 могут быть разными.

 

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

Тип автомата определяется типом входного сигнала.

Если входной сигнал потенциален, то автомат асинхронный, в противном случае – синхронный. При асинхронной реализации автомата для обеспечения устойчивой его работы все его состояния должны быть устойчивыми (аналогично петли СИ в синхронном автомате).

Состояние S_i называется устойчивым, если при переходе в это состояние под воздействием входного сигнала P_k автомат остается в этом состоянии до тех пор, пока входной сигнал не станет отличаться от P_k.

 

Автомат будет асинхронным, если уже на абстрактном уровне все его состояния - устойчивы.

Пример асинхронного автомата:

 Составим таблицу переходов:

 

W	S/X1X2	00	01	10	11
0	S1	S1	S1	S3	S2
0	S2	S1	S2	S2	S2
1	S3	S1	S2	S3	S2

 

0 – устойчивое состояние (петля)

Проверка устойчивости:

S₁ à S₃ (двигаемся по строке, а потом по столбцу)

Для проверки является ли автомат асинхронным (по таблице переходов) вначале выделяем переходы соответствующие петлям вокруг состояний.

В каждой строке с номером I обводим состояние S_i, затем проверяется устойчивость переходов из каждого состояния.

Например переход S₁ à S₃ проверяется следующим образом:

1) Смотрится в строке с текущем состоянием под воздействием входного сигнала в какое состояние он должен перейти (горизонтальное движение стрелки)

2) Затем в столбце соответствующим данному сигналу ищется состояние, в которое переходит автомат, но отмеченное кружком (движение вертикальное).

3) Если все переходы попадают в отмеченное состояние, то все состояния устойчивы и автомат может быть асинхронным.