Рис. 3.59. К упражнению 3.2.

Рис. 3.61. К упражнению 3.4.

3.5. Используя процедуру 3.3, найдите диагностическую последовательность минимальной длины (если она существует) для нижеследующих таблиц.

Рис. 3.62. К упражнению 3.5.

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

3.7. Используя процедуру 3.4, найдите наводящую последовательность минимальной длины для следующих таблиц.

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

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

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

3.9. Данная ниже выходная последовательность формируется автоматом с тремя состояниями. Постройте для этого автомата таблицу состояний.

t 1 2 3 4 5 6 7 8 9 10 11 12 x OlOlolOllOOl z 0011101100 11

3.10. Приведенная ниже выходная последовательность принята автоматом М с тремя состояниями через канал с помехами, так что символы Оь Яг, Й4

О

Рис, 3 63. К упражнению 3.6,

О в

Рис. 3.64. К упражнению 3.7.

Рис. 3.65. К упражнению 3.8.

не могут быть декодированы правильно. Найдите, если это возможно, символы Сь 2, Яз. 4 и постройте таблицу состояний.

- t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

X 00000010010 0 010 г О О 1 О а, 1 О 1 аг О 1 I 1

Рис. 3,66. К упражнению 3.11.

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

Рис. 3.67. К упражнению 3.12. 3.13. Для передаточной функции

- D + P+l

найдите

а) соответствующую цепь,

б) импульсную реакцию,

в) выходную последовательность, возбуждаемую входной последовательностью 101101,

г) нулевую последовательность для исходного состояния Р'х = Р'г == I для всех и

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

Последовательностные цепи 189 3.14. Найдите передаточную функцию цепи на рис 3JB8.

Рис. 3.68. К упражнению 3.14.

3.15. Найдите линейную цепь со следующей импульсной реакцией: 10 110 110 110 1 10... .

3.16. Постройте таблицу состояний для следующих регулярных выражений:

а) (001 iu0 1 iu1 1)(0u1 1)*.

б) [1 1u1ua][0 1u0 1 1]*[0иЯ],

в) (00)* 1 (1 1)* [00(00)* 1 (1 1)*]*(00)*.

3.17. Для каждой из представленных таблиц состояний определите регулярное выражение. Исходное состояние примите равным I.

Рис. 3.69. К упражнению 3.17

3.18. Для автомата М, показанного на рис. 3.70 элементы следующих состояний А и В неизвестны, но 01 - диагностическая последовательность, а

Рис. 3.70 К упражнению 3.18

1001 - синхронизирующая последовательность. Найти возможные значения А я В.

Рис. 3.71. К упражнению 3.20.

3.21. Для таблицы на рис. 3.72 найдите все возможные значения А и В, прн которых таблица неупрощаема.

Рис. 3.72. К упражнению 3.21.

3.22. Докажите (или дайте противоположный пример) каждое из следующих утверждений:

а) Все линейные последовательностные автоматы (ЛПА) имеют диагностические последовательности.

б) Нн один ЛПА не имеет диагностической последовательности.

в) Все ЛПА имеют синхронизирующие последовательности.

г) Нн одни ЛПА не имеет синхронизирующей последовательности.

д) Все ЛПА относятся к автоматам без потерь информации типа III.

е) Все ЛПА относятся к автоматам без потерь информации типа IV.

ж) Все ЛПА относятся к автоматам без потерь информации типа П.

3.19. а) Докажите, что если автомат М, имеющий п состояний, является конечным автоматом без потерь информации степени к, го k 1п(п+ 1)/2] + + 1.

б) Найдите, если возможно, автомат с тремя состояниями, который являлся бы конечным автоматом без потерь информации степени 4. Если невозможно, объясните почему.

в) Найдите, если возможно, канонический автомат с п состояниями, который являлся бы конечным автоматом без потерь информации степени k для k = [n{n+l)/2]+L

3.20. Для цепи, показанной на рис. 3.71, докажите (или дайте противоположный пример) каждое из следующих утверждений:

а) Автомат без потерь информации М относится к типу III, если автоматы Ml и Mz относятся к типу III.

б) Автомат без потерь информации М относится к типу III, если автомат Ml относится к типу III, а автомат Мг не относится.

в) Автомат без потерь информации М относится к типу III, если Мг относится к типу III, а Ml не относится.

г) Автомат без потерь информации М относится к типу III только в том случае, если и М; и Мг относятся к типу III.

3.23. Докажите (или дайте противоположный пример) каждое из следующих утверждений.

а) Если полностью определенная таблица состояний М представляет автомат без потерь информации типа II, то М неупрощаема.

б) Если полностью определенная таблица состояний М представляет автомат без потерь информации типа III, то М неупрощаема.

в) Если полностью определенная таблица состояний М представляет автомат без потерь информации типа II, то М имеет синхронизирующую последовательность и/или диагностическую последовательность.

3.24. (а) Инверсия последовательностного автомата М определяется как последовательностный автомат М~\ вход которого есть выход z автомата М, а выход есть вход автомата М, возможно с запаздыванием. Докажите, что последовательностный автомат М имеет инверсию тогда и только тогда, когда М представляет собой автомат без потерь информации типа IV.

(б) Найдите инверсный автомат для автомата Мб, показанного на рис. 3.35.

(в) Все ли инверсные автоматы являются автоматами без потерь информации типа IV?

(г) Найдите, если возможно, автомат М, для которого М- = М.

-Часть il

ВРЕМЕННЫЕ СООТНОШЕНИЯ И СТРУКТУРЫ

Глава 4 АСИНХРОННЫЕ

ПОСЛЕДОВАТЕЛЬНОСТНЫЕ ЦЕПИ

4.1. ВВЕДЕНИЕ

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

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

Цепи, которые проектируются для работы без синхронизирующих тактовых импульсов, называются асинхронными цепями. Такие цепи используются в тех случаях, когда входные сигналы приходят в случайные моменты времени. Они исполь-

х,х2 01 11

(3)/. 3,1

©,0

Т),о

Рис. 4.1. Асинхронная таблица переходов.

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

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

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

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

Обозначим следующее состояние и выход полного состояния {с]й Ij) через {ди Ij) и Z {д^, Ij) соответственно. Считается, что если N{gi, Ij) = gi, то gi является устойчивым состоянием при входе Ij и обозначается в виде круга в таблице переходов, как показано на рис. 4.1. Все другие состояния являются неустойчивыми.

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

7 Зг.к. т

последовательностных цепях обычно предполагается работа с входными сигналами определенного уровня (хотя это допущение не является необходимым). Поскольку тактовые импульсы отсутствуют, переходы из состояния в состояние вызываются изменениями на входе цепи. Если переход от устойчивой конфигурации {qi, Im), вызываемой изменением / к /. , приводит к состоянию qj и конфигурации {qj. In), которая оказывается неустойчивой, то состояние вновь изменяется к N{qj,In) и продолжается изменение в пределах столбца In до тех пор, пока не будет достигнута устойчивая конфигурация.

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

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

В автомате, функционирование которого описывается таблицей переходов, приведенной на рис. 4.1, допускаемыми переходами являются перехо,пы между столбцами на одну входную переменную при условии изменения только одной входной переменной. Если цепь первоначально находилась в устойчивом состоянии 1 при входных сигналах 00, то изменение входных сигналов на 01 будет вызывать переход к состоянию 3, как показано сплошными линиями в таблице переходов. Если за этим входом будет следовать вход И, то автомат перейдет в устойчивое состояние 1, как показано пунктирными линиями. Следующее состояние и выход не указываются для полного состояния (2, 11), потому что они не могут быть получены из какого-либо другого состояния при ограничении на изменение только одной входной переменной. Автомат будет устойчивым в состоянии 2 только в том случае, если состоянием на входе является комбинация 00 и если следующими входными состояниями могут быть только 01 и 10. Кроме того, столбец 11 таблицы переходов не содержит состояния 2 в качестве следующего входного состояния.

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