Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 70
Текст из файла (страница 70)
334 длины й занимает во времени ровно й тактов; его. буквы можно считать функциями от времени: а(1) — буква, появившаяся на входе в момент 1, Автоматные функции 6 и Х реализуются с задержкой. Время задержки функции 6 равно единице: 6(д(1), а(1)) =д(1+1); состояние п(0) определено заранее. Время задержки функции Х обычно считается равным нулю: Х(д(1), а(1)) =п(1), но иногда равным единице; Х(д(1), а(1)) =с(1+1); во втором случае должно быть определено п(0). Таким образом, под действием последовательности входных сигналов одинаковой длины каждый из автоматов порождает последовательность промежуточных или внутренних сигналов (реализующих состояния) и последовательность выходных сигналов, причем длины тактов этих последовательностей совпадают с длиной входного такта.
Каким образом на практике достигается такая всеобщая синхронизация — за счет внешних синхронизирующих часов либо за счет идеальных временных характеристик автоматов и среды, в которой они функционируют, — на данном уровне рассмотрения несущественно (но, разумеется, становится существенным при физической реализации таких сетей). Прежде чем говорить о сетях из автоматов общего вида, рассмотрим некоторые основные виды соединения автоматовв.
!, Параллельное соединение (рис. ВАО): а — с разделительными входами и алфавитами А, и Аз, б — с общим входом и алфавитом А. ! ( а) ~- — .( Ь Рис. 8.10 Могут сказать, что соединение а — зто вообще ие сое- динение; тем не менее пару автоматов 5~=(Аь Яь Уь 6„ )ч); ог= (Аэ Ям Уь бм Хз) можно рассматривать как один автомат Я=(А, Я, У, 6, Л), который определяется так: Выход Чо Чо Чо 00 01 10 11 00 00 01 01 1О 1О 1! 11 лице предполагается, что Х не имеет задержки: ) (а(1), а(1)) =с(1) =д(1). Таким образом, автомат с одним состоянием и единичной задержкой на выходе оказывается эквивалентным автомату с двумя состояниями без задержки на выходе. Но тогда сеть на рис. 8.11 оказывается автоматом с четырьмя состояниями; ее таблица переходов строится из табл, 8.!1 по формуле (8,!2) и приведена в табл.
8.12, где пары (о)ь о7;) обозначены 11, а значение выхода совпадает с состоянием второго элемента задержки. Кажется парадоксальным, что цепь из двух элементов задержки удается описать автоматом, в котором функция Х не имеет задержки. Это происходит потому, что задержки «загоняются» в состояния. Аналогично можно описать цепь из любого числа элементов задержки. 3. Обратная связь (рис. 8.12): это соединение заключа- 22 — 750 а пока рассмотрим очень простой пример. Пусть автоматы 5, и Яо имеют по одному состоянию, двоичные вход и выход, а на выходе переписывают то, что подано на вход, но с задержкой на такт: 7.(а(1), а(1)) =а(1+1). В этом случае 5~ и Зо на рис. 8.11 — это просто устройства задержки на такт или, как говорят, элементы задержки.
Для этих элементов необходимо определить начальное значение выхода, положив его равным нулю. Казалось бы, такая сеть тривиальна и по свойствам прямого произведения Я=(!Хааа должна иметь одно состояние. Однако она осуществляет (при введенной ранее синхронной интерпретации тактов) отображение 5(а) =ООа х (а, обозначает слово а, у которого отброшены две последние буквы), которое нельзя реализовать автоматом с одним состояннем. Выход заключается в том, чтобы интерпретировать элемент задержки с двоичным входом и выходом как автомат с двумя состояниями, значения которых совпадают со значениями входа.
Его таблица переходов приведена в табл, 8.11. В этой табТаблица 8.11 Таблица В.12 ется в том, что выход автомата 8~ присоединяется к одному из его входов. Рассмотрим случай, когда 5~ — комбинационный авто. мат без задержки, и предположим, что 5~ реализует логическую функцию х~хр, вход х, оставлен внешним, на вход хз подана замкнутая обратная связь. Пусть в момент 1 и =О; тогда хз(1) О и о(1) =х~(1)хз(1) =1, т.е.
равен и нулю, и единице в один и тот же момент. Если же о(11= 1, то хз(1) =1 и при х,(1) 1 г(1) =х~(1)хз(1) =О, т.е. опять Рис. 8.12 получаем противоречие. Предоставляем читателю убедиться, что введение в обратную связь задержки устраняет противоречия. Этот пример показывает, что сеть из автоматов, содержащая контур обратной связи без задержек, может не иметь конкретной автоматной интерпретации, Правда, это бывает не всегда, но тем не менее сети с контурами обратной связи без задержек в теории автоматов, как правило, исключаются из рассмотрения. С другой стороны, обратная связь с задержкой оказывается мощным средством построения автоматов. Всякий автомат прн синхронной интерпретации может быть реализован как сеть, состоящая нз комбинационных автоматов и элементов задержки. Действительно, такая сеть для ав- томата с функциями 11(1+1) =б(Ч(1), а(1)), п(1) =2~(Ч(1) а(1)) приведена на рис.
8.13. На этом рисунке блок Х— комбинационный автомат с входным алфавитом А ХЯ и выходным алфавитом 11, блок б — комбинационный автомат с тем же входным алфавитом и выходным алфавитом 9. Блок 0 — это блок, задерживающий поступающие в него сигналы на один такт (блок задержки). Он представля. 338 ет собой автомат Мура, входной и выходной алфавиты которого совпадают и равны Я=(дь ...,д„), алфавит состояний Я=(гь...,г„) имеет ту же мощность, что и Я, Ха(г;) = =д„ба(гь д~) =Р для всех 1, 1=1, ...,и.
Частный случай Р— двоичный элемент задержки. Сигнал д'(1) на выходе блока б — это вычисленное значение б(д(1), а(1)), которое, будучи задержано блоком Р на такт, появится в момент 1+1 на входах блоков б и Х, т.е. д'(1) =б(д(1), а(г)) = = Ч(1+1) В важном частном случае, когда алфавиты А, У, Я состоят из двоичных наборов, блоки Х и б — это логические комбинационные автоматы, двоичные выходы которых в момент 1 являются логическнмн функциями от двоичных переменных, образующих наборы а(г) и д(1); блок Р— это параллельное соединение двоичных элементов задержки. Число этих элементов равно и — длине вектора Я, а число состояний блока Р, как и в общем случае, равно мощности его входного алфавита, т.
е. ~ Я ~ =2". Поскольку любые конечные алфавиты А, Я, У можно закодировать двоичными кодами подходящей длины (т.е. установить взаимно однозначное соответствие между элементами любого из этих алфавитов и двоичными наборами), получаем один из первых и фундаментальных результатов теории автоматов. Теорема 8.11. Любой конечный автомат при любом двоичном кодировании его алфавитов А, Я, У может быть реализован синхронной сетью нз логических комбинационных автоматов и двоичных задержек, причем число задержек не может быть меньше 1ойз~ Я ~, П В дальнейшем логические комбинационные автоматы для краткости будем называть логическими блоками (их входы и выходы двоичные), а блок задержки на один такт с одним двоичным входом и выходом — элементом задержки.
Вход элемента задержни будем обозначать У, а выход — у. Сеть из логических блоков и элементов задержки (и те к другие будем называть блоками) называется правильно построенной логической сетью (ППЛС), если: 1) к каждому входу блока сети присоединен не более чем один выход блока сети (однако допускается присоединение выхода более чем к одному входу, т. е. разветвленне выходов); 2) в каждом контуре обратной связи, т.е. в каждом цикле, образованном блоками и соединениями между ними, имеется по крайней мере один элемент задержки. Входами 339 такой сети называются те входы блоков, к которым не присоединены никакие выходы; выходами сети называются те выходы блоков, которые не присоединены ни к каким входам.
Сеть на рис. 8.13 превращается в ППЛС, если алфавиты А, С, У закодировать двоичными наборами число входов и выходов блоков б, Х, О согласовать с длинами соответствующих наборов, а блок .0 реализовать, как указано ранее, параллельным соединением двоичных задержек. Поэтому в формулировке теоремы 8.11 фактически подразумевается представление автомата синхронной ППЛС (СЛС) и следующую теорему можно считать обратной теоремой 8.11.
Теорема 8.12. Всякая СЛС со входами хо...,х, выходами гь...,з и Ф элементами задержки является конечным автоматом, входной алфавит которого состоит из 2~ двоичных наборов длины пз, выходной алфавит — из 2" наборов длины п, множество состояний — из 2Я наборов длины й. Начнем с рассмотрения СЛС без задержек. Такая сеть по определению не может иметь циклов. Рассмотрим любой ее выход г. Блок, которому он принадлежит, реализует на этом выходе логическую функцию г=)'(р',,..., р',), где р',,...,р, '— входы блока.
Каждый из них либо является входом сети, т. е. переменной х, либо присоединен к выходу другого бло- 2 2 2 ! 3 з ка: Р;=); (Рп, ..., Р~,) и, следовательно, а=1 ф (Р», -,рм,),-.,1.(р.~,...,р~„,)), где вместо некоторых ~~~ возможно, стоят переменные х. Еще одно повторение этой процедуры даст суперпозицию глубины три с функциями (з и переменными рз и т.д., причем верхний индекс переменной р, 'равен числу блоков между узлом р,'. и выходом г. Поскольку сеть ациклическая, этот процесс закончится и все переменные р', будут заменены переменными х. Отсюда (с учетом отсутствия задержек в сети) видно, что г(1) является логической функцией от некоторых из х, (г), ...
...,х (1) и, следовательно, ППЛС без задержек всегда является логическим комбинационным автоматом. Пусть теперь дана произвольная СЛС б. Если из нее удалить элементы задержки, то получим ациклическую сеть 60 без задержек, которая, как только что было показано, является логическим комбинационным автоматом. Входа- ми бс служат, во-первых, входы 6, а во;вторых, выходы уь ...,у„элементов задержки б; выходы бс — это выходы б и входы Уь ..., Уи элементов задержки 6 (рис. 8.14). Поэтому входной набор бс имеет вид (хь ..., х„„уь ..., уи), выходной набор — (гь ..., г„уь ..., Уи). Если теперь набор (х,(1),...,х (1)) считать входным сигналом а(1) сети 6, набор (г,(1),...,г (1)) — выходным сигналом п(1) сети 6, а набор (у1(1), ...,уи(1)) — состоянием д(1) сети 6 и учесть, что ( У, (1), ..., Уи (1) ) = (у, (1+ 1), ..., уи (1+1) ) = д (1+1), то получим, что сеть бс вычисляет две системы логических Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
