учебное пособие - Конечные автоматы - Силин В.Б., Мельников Б.С., страница 9
Описание файла
PDF-файл из архива "учебное пособие - Конечные автоматы - Силин В.Б., Мельников Б.С.", который расположен в категории "". Всё это находится в предмете "вычислительные сети и системы" из 7 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "вычислительные системы и микропроцессоры" в общих файлах.
Просмотр PDF-файла онлайн
Текст 9 страницы из PDF
Описание 8 -триггера приведено на рис. 23. Поскольку ГОСТ не предусматривает специального обозначения дпя триг- геренов- 'Ю-и Е - типа, мы будем попьзоваться графичесхам изображением Ю-у -трютера с соответствующей буквой над ним. Из табпицы переходов поцучаем Щлч) = ФЛ) 0 (л) Ю(л) =[ЯЯ)+Й/ЛЯВ(Л) + Й(Л)1 . (4.6) В отначке от предыдущего снучая дкзъюнктивнаа и конь юиктивная формы Й ( П, + 1) эквивалентны, поскопьку онн 43 Рис. 24. Матркпы переходов л-я о'— триггеров Матрицы переходов Й - л Е -триггеров приведены на рис.
24, звачеция леспредвлевлых коэффициентов определены из вырвжввия [4.7). 44 отображают функцию пврвхода поллостью олрвделвллогв элвмвктарлого автомата Для лостроввия матрицы пврехода опрэделим злачвлкя вспомогательной фуиилии: переход Е) да Х =И» ш оа тт 0 »Йо ~ 5 ° откуда 6=»б; И= 0 Ео =6» первход 0- 1; Хб ю ~Ю+ 06 6, ОтКуда~э11 а=. 1„; »»»ю первход 1 1~ Х =М» 6 е Ьо,, 0».У ~,.0.,6,. Я8.Д5 о о о е 0 О Е, 0 Полученное выражелив о Е о-е 6, » для Х» говорит о том, чтв Е Е-0 Е 0 К Еа к У могут быть выра- О д д 6, д; жалы иволрвдэлвллымк~ ко обязательно завислмымк бЕ б друг от друга коэффициен- тами.
Так, скгвал л может Я- рк р: а- условное обозлачвлие; — та прилимвть 'лрокзвольвов зма лида переходов1 в-граф первхо- ченив при Я-О, а сигкал дав; г-матрица переходов ,ц к Поскольку ла переходе 1- 1 значение Х должно оставаться равным едиикпв, имввм л х =Й.г= 6 ° ~"=-~. (4.7) а 3 ю В И -т игге е сигнал У подавляет сигнал л» .поэтому комбивапяя 1, Я 1 переводкт триггвр в нулевое состояние. Анализ этого типа триггера во млогом напоминает аиа- ЛИЗ 0 -тркгГВРа, поэтомУ мы его опускаем и приводим функцию первхода сразу в ее аналитической форме: Я~л е)=~ХМ~Йл) е)(л)' . (4.8) В Е -т иггв е (от английского еуид — равный) комбинации Ю 1, Ы -1 сохраняет предыдушее состояние триггера, сигналы Еб и 0 эквивалент ны по силе друг другу л их действие компвпсирувтся. Функция перехода Е-триггера принимает вид Щл е)=Го(еб)8(л)+Ел(л)К(п) »1(л)6»л)- (4.9) вб-к ~ж»в в~~ О-1, К-1 состояние ла првтмлопвкожввв.
Своз иазваикв триггер 7-Е(-типа получил от имэпи изобретателя счетного триггвра Зоетбал (1919 г.) (лепишлв замвткть, что идея построения трштера ва год равьшв была проди(ижвив М.А. Беня-Бруевичем). Триггер 7-К вЂ” типа м~Фывают ешв в сальвым т щтвййм, поскольку ом совмвщавт в себе свойства Я-У-к 7 -триггеров. Учитывая особов пэложвиив 7- К -триггера среди другмх триггеров, примято вго»Е вход обозиачать буквой К, а $'- буллой 7 .
Соответстввиво изменяется маркировка входных сигналов. 7-К - триггер обладает замвчатвльвым свойством: все квопредвлвииые коэффициенты его матрицы переходов квзависммы. Это, ках правило, обвспвчивает доцолялтвльвыв резервы мивкмизацил фувклкй возбуждввия и приводит к лаилроствйшмм схемкым реализациям. 666»6 6 с тт а) Рис. 28. 7-л три1тер: а-условное обозиачвние; б-табиица переходов; в-граф переходов; г- матрица пере- ходов ' Графическое изображение триггера к его задание првдставлело ла рис. 28, Пс таблице первходов получавм й(п»)=КЬ).К(л) Й(л)ЭЮ.
(4.10) В творик .автоматов часто рассматривают трвхвходовый триггер л. - о - Т-типа. Однако в связи с разработкой и виедрввивм.7-К -триггеров примвквикв Я-и 7 -трлггвра в рввльвых схемах практически сввдеио к кулю. 48 4.2.2. Обобщенная логическая схема энвмэпта ного автомата. Все рассмотрэнныв вамп тркггерные схемы могут как выполняться в виде эдапых интегральных ехвм, тах к сэбнраться кз набора логических эпэмвнтвв. В качестве пркмэра па рнс.
28 кзображвна збобшэнная пвгкчвская схема трнггера на элементах И-ИЛИ НЕ. Ивдавкдуапьныв свойства триггера задаются комбинаппэнпэй скамей формкровання аагнкпов возбужденна левого пзтевпнальноге Ю -Ю - траггэра. 4 2,в. Комбкнапконные схемы автомата. Комбннэлаовные схемы автомата ( и У ) могут быгь выполнены на любом фупклаэнаньво, ' полном наборе вогпчэсккх эпвмэнтов.
Эпвмвжры двюквы обладать достаточным быстродэйствкем с твм, чтобы пврвкздныв процессы в схемах гаралткрованно за.канчпвапксь х пркхвду спедуюшвге скнхрзннзпрующвго импульса. 4А. Кв ванна та нац пе входов с Рис. 2б. Обобшеннаа схема траггвра йпя опредэлвннн структуры погпческой комбинапнонной схемы достаточно работу каждого нз триггеров выразкть в терминах функционирования ~~-~-триггэра п представать и Я как функции 3, Т, Й, 5 Д К, р(.: 3 - трпггэр р Т - трпггэр ррах 7 й) ~р='Гй. Ю-я - трпггер ~р=й; др= ~ 8 - триггер Яр= 8; йр=ЯБ Я - триггер Я,=32; йр- 2 трнггэр р = 5Я Кр= 22 З-К- триггер Я =,7Й; кр — дй, Работа триггера скнхронпзнрувтся двумя поспедоватэпьностнмп импульсов С и С, обэспвчнвающнмн двухтактность его работы; установка триггера в исходное состояние осуществляется сигналами Ю (уст, 'О ) и Мр~ (уст, 1 ).
46 Ках ужв было схазако, кэдпрованпэ внутренних состояний автомата (к, следовательно, вго таблицы перехода) заключа-ется в уставовпвпкп соотввтствкя между состояниями автомата п дввпчнымк хздамн состояний элементарных автоматов. Выбзр того апп нного варканта кодирования нэ пзменнет закова вавшнзгз фунхлповнрованпя автомата, цо зпачптвпьно апкавт на споаоюсть функцпй возбужденна эго элементарных автэматев.
Првдлопагают, что дпя всвх типов триггеров простата пх фуакппй возбуждения определяется простотой функдпй ваэшаих пэрвхздовр поэтому задачу оптпмапьнзго Саставме меевтзуавт— аьоююй хздарованкк эпредепают как заторн е задачу мпннмпзаппп сксте- ы гона гк мы иегкчэскпх фунхцкй внэш- ~й йр а. ках пврэхрцпмь В пзстоящвв арама за- а, бр, А двчк оптпмапьного хздкрова- ар ра рвг апя в общем виде эще нв рвшвва. В [4) яркводятся алгоритмы кодкрвванпа, обвспвчавающпв попучвнпэ функ- а ппй паравда, бпкзккх х ми- Рис. 27. Табпкпа коднроварктмы настопьхо сложны, что ' ' ння нв укладываютса в объвме предпагавмогв пособия. Рассмотрвм прквмы, позволяющие в некотором отношевпп олткмазаровать кодпрованке табпкц перэходов.
1. Кодирование осущэствпавтся посредством теблнп кодкрованпк, обшпй впд которых представлен на ркс. 27. Звэченке й. можно выбирать равным либо О, лабо 1, по так, чтобы ру двокчныв коды состоапнй автомата были различимы. Япя синхрокпых автоматов количество элементарных автоматов М эпрвдвпяэтся выраженпвм (4.2). Еспн чпспо внутренних со- 47 стояний равно цепей степени числа 2, то прк кодировании будут использованы все И -разрядные двоичные ходы, в противном случае — тоньке часть из нкх.
2. Дпя минимизации функций перехода можно рекомеядо» вать такой способ кодированки, при котором пареходы энемеитарных автоматов из одного состояния в другое зависепн бы от минимапьного чкспа других элементарных автоматов. Отсюда соседние по переходу состояния цепесообразне кодировать минимально отличающимися друг от друга кодами, например соседними значениями циклического хода. 3. Степень оптимальности кодирования оценивается пе конфигурапнн диаграмм Карно, описывающих функцик внешних переходов.
Диаграммы можно 'подправить путем перекодировки состояний, что приведет к перемещению нулей и единиц в диаграмме к появлению возможности объединения их в бень« шие группы, Следует помнить, что не всякаи переходировка миииыквирует логические функции; преобразованкя, сводящиеся к замене переменных их отрицаниями н циклической перестановке переменных, яе упрощают исходную погическую функцию, количество и характер членов в МКНФ и МДНФ остается прзж икм. 4. Если при кодировании задача минимизации не ставится, то процедуру кодирования пепесообразно организовать таким образом, чтобы максимально упростить дальнейшую работу по определению функций возбуждения.
Дця этого стецбцы таблицы переходов кодируются по законам кодироваикя диаграмм Карно, когда первый столбец, кодируется нуцевым кодом, а каждый поспедующий - возрастающим ва единицу значением И -разрядного пикнического кода. 4.4. Оп едепение акций внешних п входов Пепесообразно функции внешних переходов опредепять в минимальных нормальных формах записи погических выражений. Это осуществляется в три этапа: 1.
Расположение стоцбцов таблицы переходов (есин это еше не быцо сделано иа этапе кодирования) и эе строк изменяется перестановкой таким образом, чтобы входные переменные и состояния элементарных автоматов кодировали таблицу переходов, как это принято при построении диаграммы Карно. 2. Таблица перехода 'расспаивается на И диаграмм Карно функций внешних переходов. Прк этом есин код состояния 48 автомата записывается в порндке возрастания номера эпементарного автомата а, Р, ..., Ю,„, то все левые двоичные цифры внутренних клеток табдицы переходов формируют диаграмму Карно фунгдки внешних переходов элементарного автомата Я~, спадующие двоичные цифры — элементарного автомата И и, наконеп, правые цифры - эпементарного автомата Я, 3.
По дизъюнктивным и коиъювктивным диаграммам Карно определяют МДНФ и МКНФ функций внешних переходов всех элементарных авто)затеи: /> гя'"г ~ ~ 4т ~гт' '~ ~и)з 1 (4.11) Й~(п+~) =/'(ш,,д; ..., х 0 1~ . () ) 4.6. Оп еделения нкпий возб денни элемента ных автоматов Функции возбуждения элементарных автоматов (тряггеров) описывают значения входных сигнапов д,7, Я, ~~,„7, г( как функции входных сигналов синтезируемого автомата л'., а',..., Х~ и выходных сигнацов элементарных автоматов (тряггеров) а„ц„..., 1(,.
При заданном значении функции внешних переходов сложвость логических выражений дпя фуикпий возбуждения зависит от типа пркмениемого в схеме триггера. Поэтому при оптимизации структуры автомата целесообразно определить функция возбуждении дпя всех типов т игге в, после чего испольэовать тот из них, функции возбуждения которого требуют минимальных затрат дпи своей реапизапии.
Мы рассмотрим трк метода определения функций возбуждения — табпичный, аналитический и метод сравнения. 4.6.1. Табпнчный метод оп еделения нкпий возб ждення. Табпичный метод обеспечивает кратчайший переход от диаграммы Карно функции внешних переходов триггера к диаграммам Карно его функций возбуждения и может быть рекомендован при "ручном проектировании автоматов. Пусть определяются функции возбуждения ц -го элементарного автомата. Представим его функцию внешних перехо— дов дизъюнктивной диаграммой Карно, как это сдепанс на рис. 28. Разобъем диаграмму на две части, одна из которых закодирована нулевым значением Яй( П ), другая - единичным значением ~й(П ) (на диаграмме Цй (П) н 2~(П )).
Нули 40 ЛИТЕРАТУРА 4~ 1п <'7=(а, г Й~ а + й4 а ) (4.16) 3. Производится минимизация полученного выражения. Есля в функцию возбуждения входит неопределенные коэффициенты, то минимизация не полностью определенных выражений осуществляется по известным правилам> но обязательно с учетом допустимых значений неопределенных коэффициентов, связанных соотношением (4.7). Описанная процедура дает следующее выражение дпя функций возбуждения всех изученных нами триггеров: З - триггер Юй — — 4,(, Т - триггер Тй = Ц ~~) 4~уГ Ю-Я- триггер ~рй — — ( Д~(у ~ Д~(7 4 = Ь~б ~г ~()4 5 ' К вЂ” тРиггеР )7 - Р'"'(( г),,У г ~ф = 6 (7~ ~г, 4 у' + ( 4~ ~' е~, ~ ~' ) 5 — триггер )р~= 6~ Ю~ (7, ~2 0~ у '~74Д 494Д> —, (4,14) ~~= 4Ь ° 4"',б К,' Š— триггер К~ ~ Д~ ~г ~- Ц~ ~г, ~ ф4 р' ~,~ = Йк й ' ~~ К ' ~ ~)~ К; 7-К- триггер 7 4.б7 2 4Юг 4 ад 7(=9=Фа, р 4~г ° 4' Йб з 4УВ 4 4~2 В простейшем случае значения всех неопределенных коэффициентов можно принять равными нулю, однако дпя произ— вольной формы функции внешних переходов это не гарантирует получения минимальных форм функций возбуждения.