Исключение состязаний элементов памяти в синхронном автомате

Явление состязания элементов памяти рассматривалось в работе асинхронного автомата. Устранение данного явления в синхронном автомате можно сделать следующими двумя способами:

1. за счет выбора минимально необходимой длительности сигнала синхронизации;

2. использованием структуры автомата с двойной памятью.

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

Обычно используется структура автомата с двойной памятью. Структурная схема такого автомата представлена на рис. 6.54. Блок памяти состоит из двух ступеней памяти, каждая из которых тактируется своим сигналом синхронизации: первая (входная) – сигналом C₁, вторая (выходная) - сигналом C_2.

Входная ступень блока памяти служит для запоминания нового состояния автомата, в то время, когда выходная ступень; определяющая состояние автомата, сохраняет код старого состояния.

КС

x1

yk

y1

С

С

T21

T2k

С

С

T11

T1k

xn

z1

zm

С2

С1

y’D1 1

y’Dk

D

D

С

D

D

Рис. 6.54

На рис. 6.55 приведена временная диаграмма работы автомата с двойной памятью:

x

C1

C2

y’D

t1

t2

t5

t3

t4

t0

Рис. 6.55

К начальному моменту времени t₀ обе ступени блока памяти должны быть установлены в начальное состояние и на входы автомата поданы нужное значения входных сигналов x_i.

В интервале времени t₀ – t₁ в комбинационной схеме автомата происходит формирование значений функций возбуждения и выхода автомата.

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

К моменту t₃ состязание элементов памяти первой ступени должны быть закончены и на входах второй ступени блока памяти должны быть установлены значения кода нового состояния. По фронту сигнала синхронизации С₂ = 1 в течение интервала t₃ – t₄ происходит перезапись значения кода нового состояния из первой (входной) ступени во вторую (выходную) ступень блока памяти. При этом могут возникнуть состязание элементов памяти второй ступени, но это состязание не будет влиять на работу автомата, так как запись возникших неправильных значений функций возбуждения в первую (входную) ступень запрещена, потому что C₁ = 0. Таким образом, состязание элементов памяти второй ступени блока памяти, также будет не критическим. Длительность сигнала С₂ должна быть достаточна для записи кода нового состояния во все триггеры второй ступени блока памяти.

В интервале t₃ – t_4, при С₂ = 1 меняется значения на выходах элементов блока памяти y_j, которые поступают на входы комбинационной схемы и следовательно, целесообразно в это же время менять и входные сигналы x_i.

В интервал t₄ – t₅ в комбинационной схеме автомата формируются функции выхода и функции возбуждения. Длительность этого интервала выбирается минимально необходимой для формирования функции возбуждения и функции выхода и определяется глубиной комбинационной схемы.

К моменту времени t₅ при С₁ = 1 значения на выходах комбинационной схемы уже стабильны, и при С₁ = 1 можно считывать значения функций выхода z_j.

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

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

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

Пример реализации синхронного автомата структурой с двойной памятью и одной серией сигнала синхронизации:

Пусть задан граф автомата Мили рассмотренный ранее в каноническом методе синтеза и реализованный ранее структурой с одной ступенью памяти (рис. 6.56).

s0

0 / 0

s1

1 / 0

s2

1 / 0

0 / 1

0 / 0

1 / 0

Рис. 6.56

Таблица 6.19

x y1y2
0 1	11 /0	11 /0
1 1	10 /0	10 /0
1 0	01 /1	01 /0

После произвольного кодирования трех состояний автомата следующим образом: s₀ = 01, s₁ = 11, s₂ = 10, была получена кодированная таблица переходов и выходов (табл. 6.19) и по этой таблице была построена следующая система булевых функций возбуждения элементов памяти и выхода автомата:

z = ₂;

y’_S1 = ₁, y’_R1 = ₂;

y^’_S2 = ₂, y^’_R2 = y₁ y₂.

Структурная схема синтезируемого автомата с двойной памятью представлена на рис. 6.54, только в качестве элемента памяти используется RS-триггер. Комбинационная схема реализует систему следующих пяти булевых функций: z – функция выхода, y’_S1, y’_R1 - функции возбуждения триггера первой ступени T₁₁, y’_S2, y’_R2 - функции возбуждения триггера первой ступени T₁₂, зависящих от трех переменных: х, у₁, у₂.

R0

R

S

S0

T21

R0

R

S

S0

T22

R0

R

S

S0

T11

R0

R

S

S0

T12

&

&

x

C

y1

y2

x 0

1 q1

2

y1

y2

z

1

y2

&

&

&

&

&

&

&

&

2

2

C

P

P

1

2

y1

2

z

y’S1

y’R1

y’S1

y’R2

y’S2

Рис. 6.57

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

В результате получается следующая функциональная схема автомата с двойной памятью (рис. 6.57). Для проверки правильности ее построения необходимо протестировать его работу на конкретном входном слове. На рис. 6.58 представлена временная диаграмма работа автомата по переработке входного слова 1 0. Это слово перерабатывается в выходное слово 0 0 1.

По сигналу P = 1 к моменту времени t₀ обе ступени блока памяти должны быть установлены в начальное состояние s₀ = 01 и на входы автомата поданы нужное значения входного сигнала x.

В интервале времени t₀ – t₁ в комбинационной схеме автомата происходит формирование значений функций возбуждения и выхода автомата.

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

К моменту t₂ состязание элементов памяти первой ступени должны быть закончены и на входах второй ступени блока памяти должны быть установлены значения кода нового состояния. По спаду сигнала синхронизации С = 1 в течение интервала t₂ – t₃ происходит перезапись значения кода нового состояния из первой (входной) ступени во вторую (выходную) ступень блока памяти. При этом могут возникнуть состязание элементов памяти второй ступени, но это состязание не будет влиять на работу автомата, так как запись возникших неправильных значений функций возбуждения в первую (входную) ступень запрещена, потому что C = 0. Таким образом, состязание элементов памяти второй ступени блока памяти, также будет не критическим. Длительность сигнала С должна быть достаточна для записи кода нового состояния во все триггеры второй ступени блока памяти.

В интервале t₂ – t_3, при С = 0 меняется значения на выходах элементов блока памяти y_{1 и} y₂, которые поступают на входы комбинационной схемы и следовательно, целесообразно в это же время менять и входной сигнал x. Далее в этом же интервале t₂ – t₃ в комбинационной схеме автомата формируются значения функции выхода и функции возбуждения. Длительность этого интервала выбирается минимально необходимой для формирования функции возбуждения и функции выхода, после изменения значений входных сигналов, и определяется глубиной комбинационной схемы.

К моменту времени t₃ при С = 1 значения на выходах комбинационной схемы уже стабильны, и по фронту С = 1 можно считывать значения функции выхода z и значения функции возбуждения элементов памяти. Далее этот процесс повторяется до переработки всего входного слова и возврата автомата в начальное состояние.

Расчет параметров сигнала синхронизации

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

Тогда t₁ - длительность сигнала синхронизации С = 1 определяется временем срабатывания триггеров первой ступени t₁ = ∆τ + 2 ∆τ = 3 ∆τ, где 2 ∆τ время срабатывания базового RS-триггера. Длительность t₀ - сигнала синхронизации С = 0 определяется суммой времён срабатывания триггеров второй ступени: 2 ∆τ + 2 ∆τ = 4 ∆τ и времени формирования в комбинационной схеме значений функций - ∆τ, так как длина цепочки в комбинационной схеме равна единице, итого: t₀ = 4 ∆τ + ∆τ = 5 ∆τ.

T = t₁ + t₀ = 3 ∆τ +5 ∆τ = 8 ∆τ

P

x

C

y’S1

y’R2

y’S2

T11

y1=T21

y2=T22

z

y’R1

T12

t3

t0

t1

t2

t4

t5

t6

Рис. 6.58

6.6. Построение комбинационной схемы асинхронного автомата

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

Для анализа этого явления используется следующая модель реального логического элемента, которая состоит из идеального логического элемента (ИЛЭ) и элемента задержки ∆τ (рис.6.59). Задержкой обладают также линии связи, но эти задержки относят к задержкам логических элементов.

ИЛЭ

∆τ

Рис.6.59

Величина задержки ∆τ зависит от температуры, от расположения в схеме, нагрузки, влажности и других факторов. Величина задержки по техническому паспорту может меняться в следующих пределах:

∆τ _min < ∆τ < ∆τ _max

Из-за разброса значений ∆τ разных логических элементов в схеме из этих элементов возникает так называемое явление риска (далее просто риск). Риск возникают при смене одного набора значений входных переменных на другой набор значений и проявляется в появлении на выходе схемы кратковременного неправильного значения реализуемой функции.

На рис. 6.60 приведена логическая схема, реализующая функцию трех переменных: f (x₁x₂x₃) = ₁ x₃ V x_{2 3} :

f

&

1

x3

&

x2

3

1 1

0 1

1 1

1 0

0 1

1 0

1 1

Рис. 6.60

Пусть существует два набора значений входных переменных x₁x₂x₃: σ₁ = 010 и σ₂ = 011, таких что f (σ₁ ) = f (σ₂ ) =1. Пусть задержка первого элемента ∆₁ больше задержки второго элемента ∆₂ т.е. ∆₁ > ∆₂ и пусть для простоты ∆₃ = 0.

Временная диаграмма работы схемы при смене набора σ₁ на набор σ₂ приведена на рис. 6.61.

x3

∆1

∆2

Рис. 6.61

На рис. 6.61 видно, что на выходе схемы ненадолго появляется 0 - это называется явлением риска.

Статический риск.

Определение: пусть существует функция f( ) и существуют два набора значений входных переменных σ₁ и σ₂, таких что f (σ₁ ) = f (σ₂ ), тогда если при смене набора σ ₁ на σ ₂ на выходе схемы появляется значение, отличное от f (δ₁ ) , то говорят что в схеме имеет место статический риск.

Статические риски бывают:

a) статический риск в «1» (рис. 6.62).

t

Рис. 6.62

b) статический риск в «0» (рис. 6.63).

t

Рис. 6.63

Следует отметить, что если ∆₁ < ∆₂, то статический риск в «1» в схеме (рис. 6.61) отсутствует.

Динамический риск.

Определение: пусть существует функция f( ) и существуют два набора значений входных переменных σ₁ и σ_2, таких что f (σ₁ ) ≠ f (σ₂ ), тогда если при смене набора σ ₁ на σ ₂ на выходе схемы появляется следующая последовательность значений: f (σ₁ ) →f (σ₂ ) →f (σ₁ ) →f (σ₂ ) , то говорят, что в схеме имеет место динамический риск.

На рис. 6.64 приведена логическая схема, реализующая функцию пяти переменных: f ( ) = ( ₁x₂ v x₁x₃ ) ( ₁x₄ v x₅ ):

&

1

x2

&

x1

x3

1 0

1 1

0 1

1 1

1 0

0 1

&

1

x4

1 0

1 1

1 0

x5

0 0

1 1

1 0

&

1 0

f

Рис. 6.64

Пусть существует два набора значений переменных x₁x₂x₃x₄x₅:
σ₁ = 01110 и σ₂ = 11110, таких что f (σ₁ ) = 1, f (σ₂ ) =0. Пусть между задержками первых трех элементов существует следующие соотношения: ∆₁ < ∆₂ < ∆₃ и пусть для простоты ∆₄ = ∆₅ = ∆₆ = 0.

Временная диаграмма работы схемы при смене набора σ₁ на набор σ₂ приведена на рис. 6.65.

x3

∆2

∆1

∆3

Рис. 6.65

Из временной диаграммы видно, что при таком соотношении между задержками логических элементов, в схеме имеет место динамический риск.

Существует динамический риск при переключении 0 → 1 и динамический риск 1 → 0 (рис. 6.66).

t

t

0 → 1

1 → 0

Рис. 6.66

Наличие риска в комбинационной схеме автомата приводит к его неправильной работе.

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

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

Построение схем без риска.

В рассматриваемом способе исключения явления риска на комбинационные схемы накладывают следующие ограничения:

1. при смене набора значений входных переменных не может одновременно меняться значение более чем одной переменной;

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

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

В двухъярусной схеме возможно два варианта схем:

1. cхема построенная по дизъюнктивной нормальной форме (ДНФ).
f _ДНФ = k₁ ˅ k₂ ˅ … ˅ k_m, где: k_i – конъюнкция (рис. 6.67);

2. схема построенная по конъюнктивной нормальной форме (КНФ).
f _KНФ = d₁ ˄ d₂ ˄ … ˄ d_n, где: d_i – дизъюнкция (рис. 6.68).

&

&

&

0 0

0 0

0 0

0 0

Рис. 6.67

&

1 1

1 1

1 1

1 1

Рис. 6.68

Из анализа этих схем можно сделать следующие утверждения:

1. в двухъярусной схеме, построенной по ДНФ, статический риск в «0» отсутствует.

2. в двухъярусной схеме, построенной по КНФ статический риск в «1» отсутствует.

3. пусть есть схема, построенная по ДНФ и пусть переменная x_i входит в эту ДНФ только в прямом или только инверсном виде, тогда при изменении значения этой переменной статический риск в схеме отсутствует.

4. если есть схема, построенная по КНФ и если переменная x_i входит в эту КНФ только в прямом или только инверсном виде, тогда при изменении значения этой переменной статический риск в схеме отсутствует.

5. если есть схема, построенная по ДНФ, и если переменная x_i входит в эту ДНФ, как в прямом, так и в инверсном виде, тогда в схеме может возникнуть статический риск в «1» при изменении значения этой переменной.

Для доказательства исходная ДНФ представляется в виде:
f_ДНФ = A ˅ B(x_i) ˅ C( _i), где: A – группа конъюнкций не содержащих x_i; B(x_i) - группа конъюнкций содержащих x_i в прямом виде; C( _i) - группа конъюнкций содержащих x_i в инверсном виде (рис. 6.69).

A

B

C

xi

i

Рис. 6.69

Пусть σ₁ и σ₂ два набора значений переменных отличающихся значением только по переменной x_i, причем f(σ₁) = f(σ₂) = 1.

Возможны различные ситуации:

I. Если A(σ₁) = A(σ₂) = 1, то в этом случае риска нет, так как единица на выходе группы A обеспечит значение единица на выходе всей схемы;

II. A(σ₁) = A(σ₂) = 0, то в этом случае значение единица на выходе всей схемы обеспечивается конъюнкциями группы B или конъюнкциями группы C, т.е. возможны два варианта:

1. B(σ₁) = 1 C(σ₁) = 0;

B(σ₂) = 0, C(σ₂) = 1.

При этом возможны следующие три ситуации:

a. ∆_B = ∆_C - риска нет, но это нереальная ситуация;

b. ∆_B < ∆_C – риск есть (рис. 6.70);

∆B

статический риск в «1»

∆C

B

C

f

xi

Рис. 6.70

c. ∆_B > ∆_C - риска нет (рис. 6.71)

∆B

риска нет

∆C

B

C

f

xi

Рис. 6.71

2. B(σ₁) = 0 C(σ₁) = 1;

B(σ₂) = 1, C(σ₂) = 0.

При этом возможны следующие три ситуации:

a. ∆_B = ∆_C - риска нет, но это нереальная ситуация;

b. ∆_B < ∆_C – риска нет (рис. 6.72);

∆B

риска нет

∆C

B

C

f

xi

Рис. 6.72

c. ∆_B > ∆_C - риск есть (рис. 6.73).

∆B

статический риск в «1»

∆C

B

C

f

xi

Рис. 6.73

6. если есть схема, построенная по КНФ, и если переменная x_i входит в эту КНФ, как в прямом, так и в инверсном виде, тогда в схеме может возникнуть статический риск в «0» при изменении значения этой переменной.

Для доказательства исходная КНФ представляется в виде:
f _КНФ = A ˄ B(x_i) ˄ C( _i), где: A – группа дизъюнкций не содержащих x_i; B(x_i) - группа дизъюнкций содержащих x_i в прямом виде; C( _i) - группа дизъюнкций содержащих x_i в инверсном виде (рис. 6.74).

A

B

C

&

xi

i

Рис. 6.74

Пусть σ₁ и σ₂ два набора значений переменных отличающихся значением только по переменной x_i, причем f(σ₁) = f(σ₂) = 0.

Возможны различные ситуации:

I. A(σ₁) = A(σ₂) = 0 – то в этом случае риска нет, так как ноль на выходе группы A обеспечит значение ноль на выходе всей схемы;

II. A(σ₁) = A(σ₂) = 1 – то в этом случае значение ноль на выходе всей схемы обеспечивается дизъюнкциями группы B или дизъюнкциями группы C, т.е. возможны два варианта:

1. B(σ_i) = 0 C(σ_i) = 1;

B(σ_i) = 1 C(σ_i) = 0.

При этом возможны следующие три ситуации:

a. ∆_B = ∆_C - риска нет, но это нереальная ситуация;

b. ∆_B < ∆_C – риск есть (рис. 6.75);

∆B

статический риск в «0»

∆C

B

C

f

xi

Рис. 6.75

c. ∆_B > ∆_C - риска нет (рис. 6.76).

∆B

риска нет

∆C

B

C

f

xi

Рис. 6.76

2. B(σ_i) = 1 C(σ_i) = 0;

B(σ_i) = 0 C(σ_i) = 1.

a. ∆_B = ∆_C - риска нет, но это нереальная ситуация;

b. ∆_B < ∆_C – риска нет (рис. 6.77);

∆B

∆C

B

C

f

xi

риска нет

Рис. 6.77

c. ∆_B > ∆_C - риск есть (рис. 6.78).

∆B

∆C

B

C

f

xi

статический риск в «0»

Рис. 6.78

Из рассмотрения приведенных утверждений видно, что в некоторых случаях риск, который может возникнуть из за наличия разных значений на выходах элементов группы B и C, “шунтируется” наличием нужного значения на выходах элементов группы A. Поэтому идея построения схемы без риска заключается в выявлении наборов значений переменных σ₁ и σ₂, при смене которых может возникнуть риск, и добавлении к схеме элемента группы A, который обеспечит отсутствие риска в схеме для этой конкретной пары наборов σ₁ и σ₂.

Алгоритм построения схемы без риска по ДНФ.

Пусть задана в ДНФ функция f(x₁x₂…x_n) от n переменных.

1. задается i := 1 - индекс переменной x_i;

2. относительно текущей переменной x_i исходная ДНФ представляется в виде: f_ДНФ = A v B (x_i) v C _i) ;

3. для x_i определяются пары наборов σ₁ и σ₂, соседних по переменной x_i и для которых f(σ₁) = f(σ₂) = 1;

4. для каждой такой пары σ₁ и σ₂ определяются значения конъюнкций группы A;

Если A(σ₁) = A(σ₂) = 0, то риск возможен, и для выявленной пары σ₁ и σ₂ образуется конъюнкция, которая сохраняет значение 1 на обоих наборах σ₁ и σ₂ и не содержит x_i. Полученная конъюнкция добавляется к ДНФ, а в схему включается конъюнктор реализующий эту конъюнкцию;

5. индекс переменной увеличивается i:= i + 1 и, если i ≤ n, то переход к п.2, иначе конец работы алгоритма.

Пример построения схемы без риска по ДНФ:

Пусть f_ДНФ(x₁x₂x₃) = _{1 3} v x₂x₃.

Риск возможен по переменной x₃, так как только она входит в ДНФ как в прямом, так и в