Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Теория дискретных устройств - файл Лекция9.doc


Лекции - Теория дискретных устройств
скачать (1179.2 kb.)

Доступные файлы (11):

Лекция10.doc522kb.17.11.2010 17:46скачать
Лекция11.doc1221kb.17.11.2010 17:49скачать
Лекция1.doc211kb.07.12.2010 15:54скачать
Лекция2.doc98kb.06.12.2010 21:27скачать
лекция3.doc120kb.06.12.2010 22:25скачать
лекция4.doc173kb.09.03.2011 17:18скачать
Лекция5.docx176kb.10.03.2011 16:09скачать
лекция6.doc82kb.07.12.2010 01:39скачать
Лекция7.doc81kb.18.11.2010 15:16скачать
Лекция8.doc133kb.18.11.2010 19:07скачать
Лекция9.doc141kb.01.12.2010 18:09скачать

Лекция9.doc

Лекция №9

Структурный синтез автоматов
Если проанализировать структурную схему рис. 58 и результаты абстракт­ного синтеза автоматов на основании ГСА, то становится ясно, что СА – это одна или две независимые комбинационные схемы F1 в момент t и F2 по­сле сигнала τ, т.е. в момент t + 1.

Память автомата нужна для того, чтобы разнести во времени сигналы Zi(t), соответствующие состоянию автомата ai(t) в момент t, и те же сигналы по обратной связи Zi(t + 1), т.к. сигналы Zi являются входными для схемы СА в момент t, и по сигналу τ формируются выходные значения Zi, которые снова нужно подать на вход СА по обратной связи для определения кода Z нового состояния a(t + 1). Без наличия памяти в обратной связи автомат не будет устой­чиво работать, т.к. для одних и тех же значений сигналов {α} за время сигнала синхронизации τ, при достаточном быстродействии схемы СА может произойти многократная смена состояний, а необходима только одна.

^ Разнесение во времени сигналов Z(t) и Z(t + 1) возможно осуществить двумя способами:

  • включением в обратную связь элементов задержки (временная реализация функции памяти);

  • включением в обратную связь регистров памяти с записью по сигналу t и считыванием по сигналу (t + 1).

В интегральной схемотехнике первый способ практически не применяется.

^
Организация памяти автоматов


а) При малом числе состояний автомата (N < 12) для каждого состояния a(t) предусмотрим независимый триггер Z(t). Тогда переход из одного состояния в другое приведет к тому, что триггер Z, установленный в состояние 1 в момент t, в момент (t + 1) будет приведен в состояние «0», а в момент (t + 1) будет приведен в состояние «1».

Т.е. для представления памяти автомата потребуется столько триггеров, сколько состояний в автомате (для данного примера i = ), и переменные Z будут совпадать со значениями состояний ai (i = ).

Однако по­скольку необходимо разносить во времени Z(t) и Z(t + 1), то для реализации па­мяти автомата потребуется 2N триггеров, ведь не исключена ситуация перехода ai(t)→ai(t + 1), когда автомат снова должен вернуться в тоже состояние (например из2го снова во второе) при некоторых условиях.

Такой способ кодирования номеров состояний автомата называется унитарным (Unitт.к. каждому десятичному номеру состояния соответствует независимый эле­мент памяти (код с одной «1»).

б) Двоичное кодирование номеров состояний в памяти автомата.

^ При числе состояний N > 12 число триггеров, равное 2N, становится большим. Затраты элементов памяти и логических схем «И» для передачи кодов Z1, Z2, …, Zp(t) становятся неприемлемыми для экономичной реализации. В этом случае номера состояний автомата представляются двоичными кодами в виде ДПК или ДКГ. Тогда число триггеров P при N состояниях a(t) определится из соотно­шения:

2P ≥ N, т.е. p = Int(log2N), где Int обозначает целую часть числа. Для приведен­ного примера N = 10, следовательно, p = 4, и память автомата есть два четырехраз­рядных регистра с парафазной связью между ними.

Т.е. вместо Z1, Z2, …, Z9 в случае унитарного кодирования для ДПК (и для ДКГ) потребуется всего 4 пере­менных Z0, Z1, Z2, Z3 рис. 59. Следовательно, число триггеров с 18 снизится до 8.

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

^ Память автомата с оптимальным кодированием состояний. Во многих известных способах организации памяти не рассматрива­лись другие способы кодирования, кроме ДПК, ДКГ или унитарного кода. Кодирование внутренних состояний можно осуществлять, исходя из требо­ваний уменьшения аппаратурных затрат или увеличения надеж­ности функциони­рования автомата*.

^ Память быстродействующих автоматов. При организации памяти на двух последовательно соединенных регистрах а(t) и a(t+1) автомат работает по двухтактной схеме (τ и ). Но ведь полезной функ­цией автомата являются не его внутренние переходы из состояния в состоя­ние, а генерация выходных сигналов с1, с2, ..., сk (или Аl, A2, ..., Ak) в определенной логической взаимосвязи и временной последовательности.
О.Ф. Лобов и Н.А. Гасников [23] предложили параллельную организацию (рис. 60) памяти, позволяющую генерировать выходные микроопе­рации как по сигналу τ, так и по , сохраняя при этом временную после­довательность перехо­дов a(t) и a(t + 1). Для этого используются два параллельно работающих регистра, выходы которых объединены схемами «ИЛИ», т.е. по входам комбинационных схем работа производится как бы от единого регистра памяти. Синхронизация в параллельных блоках перекрестная: считывание кода происходит по синхроимпульсу τ с первого регистра памяти, а со второго – по сигналу . Пусть в Pг1 код a(t) через сборку схем «ИЛИ» пере­дан на комбинационные блоки в этот же временной промежуток (τ). Найден­ное значение a(t + 1) запишется в Рг2, а по сигналу Pг1 и Рг2 изменяют свою функ­цию на противоположную, т.е. в Pг1 окажется a(t + 1), а счи­тывание a(t) произой­дет с Рг2. Такая организация памяти позволяет по­высить быстродействие МПА в два раза на той же элементной базе.

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

На рис. 60 буквами F1 и F2 обозначены комбинационные схемы для реализа­ции соответствующих систем булевых функций, т.е. комплекс F1F2 и есть та схема СА, которая представлена на рисунке.



Рис. 60

Блок с буквой Ш представляет собой шифратор для того случая, когда F2 реализует функции формирования унитарных кодов f0, f1, …, f9, а в Pг1 и Pг2 про­изводится запись Z0, Z1, Z2, Z3 в ДПК.

^ Память автомата на счетчике. В большинстве случаев в графе переходов автомата можно выделить замкну­тый контур с последовательным чередованием номеров состояний. Для примера на рис. 59 такой контур образуется последовательностью вершин графа с номе­рами 0, 1, …, 8. Номер следующего состояния определяется из выражения а(t + 1) = а(t) + 1 или а(t + 1) = а(t) + 1. Символ «~» над α показывает, что может быть записано значение как α, так и . Вне этого контура лежат переходы

.

Следовательно, если в качестве одного из регистров памяти автомата взять счетчик, то всегда, когда функция R = f0 + f1 + f2 + f5 равна 1, необходимо использовать счетчик как регистр памяти состояния а(t) с переносом кода из регистра a(t + 1) по сигналу . Но если функция R = 0, то эта «связь» должна быть прервана, т.к. доста­точно прибавить 1 к счетчику для изменения (увеличения) номера его состоя­ния. Может также использоваться универсальный счетчик, работающий как на сложение, так и на вычитание. Очевидно, что этот более сложный случай должен быть рассмотрен отдельно и подробно.

В этом случае реализация функций при наличии счетчика вместо регистра может быть «экономически» более оправданной по сравнению с вариантом реали­зации функций F2 без счетчика.


* В.А. Горбатов предлагает алгоритм оптимального кодирования, основанный на частотно-матричном методе и построении значения производной для каждой пары состояний [7]. Для минимизации аппаратурных затрат по графу переходов получают кодирующее дерево, из которого следуют коды состояний. Однако алго­ритм В.А. Горбатова обеспечивает снижение затрат на реализацию комбинацион­ных схем F1 и F2 всего лишь на 5–10% при их реализации на логике средней инте­грации. Для современной техники БИС и СБИС он не дает преимуществ.

В работе [13] предлагается другой подход к «оптимальному» кодированию номеров состояний, основанный на последовательной и параллельной декомпозиции графа переходов автомата. Ю.Г. Карпов говорит о том, что предлагаемая теория отличается «внутренней красотой и может иметь важные применения». Однако нахождение специального кода, приводящего к минимизации системы булевых функций, автор демонстрирует на очень упрощенном примере автомата с одним логическим условием и числом состояний ≤8. Со ссылками на иностранные источники говорится о том, что при увеличении числа логических условий сложность задачи возрастает экспоненциально. Для инженерной практики, когда число состояний ≥32, а число логических условий ~ 10–12, эти методы требуют дополнительной доработки и оценки границ их применимости.




Скачать файл (1179.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации