-v,.v.

I - .1

Рис. 4.16. Таблица переходов, которая может быть модифицирована для реализации с двумя переменными состояний.

цы, поскольку переход 4-у1 может быть заменен на 4->-->-3->-1, как указывалось выше. Из рассмотрения столбца 00 можно заключить, что пары (1, 3) и (1, 4) или (1, 3) и (3, 4) или (1, 4) и (3, 4) должны быть смежными парами взамен только одной смежной пары (1, 3) и (1, 4).

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

Вначале мы будем рассматривать класс универсальных кодирований, который требует (2So-1) переменных состояния для таблицы с п состояниями [11], где Sq= riog2nl. Универсальное

qi->qh-->-<7m- С другой стороны, можно положить N{q, 1}) = = qi, оставляя N{qi, Ij) = qm. Эта модификация противоположна нормализации, которая рассматривалась в разд. 4.1, и может привести к кодированию состояний с меньшим числом переменных.

Пример 4.7. В таблице переходов, представленной на рис. 4.16, а, столбец 00 содержит переходы 4->-1 и 3->-1. Кодирование состояний с двумя переменными, показанное на карте Карнау на рис. 4.16,6, является справедливым для этой табли-

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

ний, является межконтурным. Это легко проверяется с помощью рис. 4.17, так как два кода каж-. дого состояния отличаются только на одну переменную, а для любой пары состояний i, j имеется код для состояния i, который отличается от кода состояния / значением только одной переменной.

Упомянутое выше универсальное кодирование может быть обобщено с тем, чтобы получить кодирование для большего количества состояний. Рассмотрим карту Карнау, представленную на рис. 4.18. Переменные уи у^ и yz разделяют карту на восьмерки (октанты), как показано на

>5

Рис. 4.17. Универсальное кодирование четырех состояний с помощью множества связанных строк.

Рис. 4.18. Универсальное кодирование восьми состояний с помощью множества связанных строк.

рисунке. Карта конструируется таким образом, что переменные с нечетными номерами индексов уи уз, уь определяют столбцы, а переменные с четными номерами индексов у2, yi определяют строки. Коды, присваиваемые любому состоянию, состоят из столбца в одном октанте и строки в смежном октанте (определяемой изменением значения у2 для половины состояний и значений Ун для другой половины). Следовательно, коды каждого

СОСТОЯНИЯ образуют связанное множество. Кроме того, для каждой пары состояний qi и q существуют коды двух состояний в смежных октантах, а так как строки в октанте являются связанными со всеми столбцами в каждом смежном октанте (и наоборот), существуют коды для состояний qi и q, которые отличаются точно на одну переменную. Следовательно, присваивание кодов, показанное на рис. 4.18, является универсальным кодированием с помощью множества связанных строк для восьми состояний.

, Vl

1 I I--1

г

Рис. 4.19. Универсальное кодирование 16 состояний.

Представленный на рис. 4.18 образец может быть использован для генерирования универсальных кодирований любого количества состояний, равного целой степени 2. Переменные уи У2 и Уз определяют октанты на карте Карнау. Множество строк, присваиваемых любому состоянию, будет соответствовать строкам в одном октанте и столбцам в смежном октанте. Допустим, используются строки в октантах, соответствующие четному количеству единиц в переменных уи г/г, Уз, и столбцы в октантах, соответствующие нечетному количеству единиц в тех же самых переменных. Заметим, что строка получается присвоением фиксированных значений множеству переменных у, индексы которых являются четными, и присвоением всех возможных комбинаций значений переменным с нечетными индексами при уг и у2 при неизменном уз- Аналогичным образом могут быть получены столбцы, если оставлять неизменными переменные с нечетными индексами и варьировать переменными с четными индексами. Универсальное кодирование 16 состояний показано на рис. 4.19.

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

количество состояний, необходимо удвоить количество строк и столбцов. Это может быть выполнено добавлением двух переменных. Следовательно, число переменных, необходимых для универсального кодирования п состояний, использующих эту конструкцию, равняется 2So- I.

Если некритические состязания являются допустимыми, то требуется самое большее 4 интервала времени перехода для выполнения перехода к любому состоянию, когда универсальное кодирование для {2So- 1) переменных используется для любой таблицы с п состояниями независимо от величины п. В наихудшем случае эти переходы включают: 1) переход в пределах любого столбца (строки) в октанте (возможно, с некритическим состязанием); 2) изменение переменной октанта {уи у2 или ys) для достижения смежного октанта; 3) переход в пределах строки (столбца) в новом октанте (возможно, вновь с некритическим состязанием); 4) переход к коду незначительного состояния посредством изменения переменной октанта.

Пример перехода между точками а и е, требующий четыре шага, показан на рис. 4.19. Переход от а к b и от с к d происходит с некритическими состязаниями. Другие два перехода требуют изменений только одной переменной. Иное универсальное кодирование состояний, имеющее 2So переменных состояний, но требующее только двух времен переходов, можно получить из работы Хаффмана [11] (см. задачу 4.16).

4.4.2. КОДИРОВАНИЕ С ПОМОЩЬЮ РАЗДЕЛЯЕМЫХ СТРОК

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

Связанная траектория между двумя точками а и b представляет собой такую упорядоченную последовательность точек, начинающихся в G и заканчивающихся в Ь, что все последовательные пары точек являются смежными. Корректное кодирование состояний с помощью разделяемых строк для таблицы переходов нормального режима должно удовлетворять следующим двум условиям: 1) точка (или точки), представляющая каждое состояние, должна отличаться от точек, представляющих все

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

Пример 4.8. На рис. 4.20 показано кодирование с помощью разделяемых строк для таблицы переходов, представленной на рис. 4.13. Переходы для столбцов (00, 01, И) в таблице переходов показаны в виде линий, соединяющих смежные точки. Точ-

00 01 и

00 01 11 10

00 01 11 10

Рис. 4.20. Переходы в каждом столбце для таблицы переходов, показанной

на рис. 4.13.

ка 111 является общей при переходах 5->-6 в столбце 00, 4->-5 в столбце 01 и переходе 6-+4 в столбце 11.

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

Пример 4.9. На рис. 4.21 показана таблица переходов с семью состояниями и с ограничениями смежности. Мы начинаем с 5о = riog2 7l = 3, т. е. с трех переменных состояний. Так как состояние 1 имеет наибольшее количество ограничивающих условий смежности, то ему первому присваивается код (ООО). Наличие этих четырех смежностей приводит к необходимости присвоить точку перехода (разделяемую строку), смежную с этим кодом, как показано на рис. 4.21, е. По той же причине состояние 2 должно быть смежным с разделяемой строкой. Другие три точки, смежные с 1 и разделяемой строкой, должны быть заполнены требуемыми для этого состояния смежностями (3, 4 и 6). Поскольку 3 и 4 должны быть смежными как с 1, так и с 2, в то время как 6 должна быть смежной только с 1, они располагаются так, как это показано на рисунке. Смежности, требуемые для состояний 7 и 5, определяют показанные здесь присваиваемые коды. Переходами, при которых используется разделяемая строка, являются 4 -> 1 в столбце 00, 1 -> 2 в

Рис. 4.21. Получение кодирования состояний с помощью множества разделяемых строк (пример 4.9).

столбце 01 и 2->4 в столбце 10. Поскольку все переходы, которые используют разделяемую строку, располагаются в разных столбцах, проведенное присваивание кодов является правильным кодированием с помощью разделяемых строк. Легко показать, что кодирование с помощью множества связанных строк для этой таблицы переходов требует четыре переменных состояния.

Хотя для таблиц произвольного размера не известно универсальное кодирование с помощью разделяемых строк, Сау-сер [19] получил такие присваивания кодов при условии одного кода на состояние для таблиц перехода нормального режима

Уз>4 00 01 11

Рис. 4.22. Универсальное кодирование с помощью множества разделяемых

о) кодирование 8 состояний; б) коди рование 12 состояний.

С 8 И 12 состояниями. Такие присваивания кодов, требующие четыре и пять переменных соответственно, показаны на рис. 4.22. Получение обоих присваиваний кодов и доказательство минимальности при алгоритме поиска было проведено с использованием ЭВМ.

Кашер и Мак-Ги [12] определили класс кодов, называемый кодами с дополнительной проверкой на четность. Такие коды, которые являются обобщениями кодирования, предложенного Саусером, требуют примерно 5о + riog2 5о1 переменных состояния для п состояний, где So = riog2nl. При этом предполагалось, что они должны давать универсальное кодирование состояний, но это положение не было доказано.

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

Один из методов, позволяющих добиться одновременного завершения всех переходов, состоит в присваивании кодов смежных точек состояниям, между которыми совершаются переходы. Как указывалось ранее, такой метод вообще неприменим при использовании однозначного кодирования (хотя и может оказаться возможным для некоторых специальных таблиц перехода). Однако можно присвоить множество кодов каждому состоянию любой таблицы переходов таким образом, чтобы для любых двух состояний (?i и qj каждый код, присвоенный q, являлся смежным с некоторым кодом, присвоенным qj. В отличие от рассмотренного ранее кодирования с помощью множества строк точки, присваиваемые любому состоянию, не обязательно образуют связанное множество, поскольку переходы не совершаются в одном и том же множестве строк.

Присваивание кода Хэмминга является универсальным ОВП-кодированием с указанными выше свойствами. Проведем рассмотрение для кода Хэмминга, корректирующего одиночные ошибки [9]. Если значение п, представляющее собой количество состояний в таблице переходов, равняется 2, то присваивание кода Хэмминга с п состояниями имеет т = 2 - 1 переменных. Поскольку должны быть разрешены переходы между всеми парами состояний и в течение одного перехода допускается изменение только одной переменной, то такое присваивание кодов будет требовать по меньшей мере п - 1 переменных.

Таким образом, если п - 2, то присваивание кода Хэмминга является примером универсального присваивания с минимальным числом переменных, в котором все переходы совершаются с единственным изменением переменных.

Обозначим п состояний таблицы переходов целыми числами О, 1, ..., п - 1. Каждое целое /, О / п - 1, можно представить в виде -разрядного двоичного числа 6(/)(/), ... ..., bi{I), называемого двоичным представлением I. Например,

если = 3, то О / 7, а если двоичное представление 6 равно ПО, то Ьз{6)= 1, Ь2{6)= 1 й Ь,(6) = 0.

Будем присваивать каждому состоянию /, 0-1 -1, множество (п - 1) разрядных векторов (т. е. множество кодов п-1 переменных). Каждый из 2 - векторов будет присваиваться определенному единственному состоянию. Присваивание будем выполнять следующим образом. Допустим, что Pj, j k, является множеством целых чисел / п- 1, которые являются двоичными представлениями, имеющими 1 в позиции /, и где в самой правой старшей позиции находится 1. Для k = 3 Р^ - = {1, 3, 5, 7}, Рг = [2, 3, 6, 7} и Рз = {4, 5, 6, 7}. Для каждого вектора у определим k параметров

С/(у)= 1 Vi,

где Е является суммой по модулю 2, а / - целое число, / k. Таким образом, если = 3,

С, (у) = г/1 © г/3 Ф г/5 е г/7,

СЛу) = У4®Уь®Уъ®У7-

Эти k параметров всегда принимают значение О или 1 и воспринимаются как группа С^, С^-и ..., Сь определяющая двоичное представление целого 1, О / п- 1. Если параметры Cj (у), I j определяют двоичное представление I, то вектор у присваивается состоянию /. Для каждого состояния / множество векторов, присваиваемых /, записывается как Rj и обозначается в виде

/ = {у I С'и (у) Cft-i (у) ... С] (у) является двоичным представлением 7}

Пример 4.10. Для присваивания четырем состояниям кода Хэмминга имеем k = 2. Число переменных, требуемых для кодирования состояний, будет равно 4-1=3. Множеством векторов, присваиваемых состоянию О, является 7?о = = {у C2(y)Ci(y) =00}. Эти векторы в 7?о должны удовлетворять следующим условиям:

Ci(y)=i/i©i/2 = 0, С2(у) = г/2Фг/з = 0.

Таким образом, 7?о = {ООО, 111}. Аналогичным образом, 7?i = = {Oil, 100}, удовлетворяя условиям

С,(у) = у,е^з = 1;

С2(У) = 2Фг/з = 0;

Рассмотренный выше метод может быть использован для кодирования любой таблицы с п

Рис. 4.23. Универсальное кодиро- СОСТОЯНИЯМИ, где п = 2 . Дока-вание четырех состояний (при- жем теперь, ЧТО ЭТО кодирование сваивание кода Хэмминга). является универсальным ОБП-

кодированием.

Теорема 4.1. Присваивание кодов Хэмминга является универсальным ОВП-кодированием, если п = 2 .

Доказательство. Из определения Rj следует, что каждый вектор у содержится только в одном Ri. Так как имеются п таких множеств, присваивание кодов различных состояний отличается друг от друга.

Для того чтобы показать, что имеет место универсальное ОВП-кодирование, покажем, что для каждого вектора у е i?/ и любого / существует такое yei?j, что у и у' различаются точно в одном разряде. (Таким образом, переход от у к некоторому вектору, присваиваемому любому другому состоянию, может быть сделан посредством изменения одной переменной состояния.) Для любых двух целых / и /, двоичными представлениями которых являются bft (/) (/) . . . &i(/) и 6fe(/)6ft i(/) ...

... 6i(/) соответственно, мы определяем

/ф/=Е (ь.)(/)еь.(/))-2-.

Иначе говоря, / ф / представляет собой значение, получаемое преобразованием суммы по модулю 2 чисел / и /, представленной как двоичное число. Например, 9 ф 5 = 1001 ф 0101 = = 1100=12.

Положим yRi и С = /ф/. Допустим, что у' представляет собой вектор, полученный при изменении Q-разряда в у, считая справа. Тогда теорема может быть доказана, если показать, что у' е Rj. (Выполните в качестве упражнения.)

/?2 = 010, 101}, удовлетворяя условиям у^Уз - О, у2 Ф Уз= 1; Rs- 001, ПО}, удовлетворяя условиям у1®Уз= 1. У2®Уз= 1-Эти четыре множества показаны на карте Карнау на рис. 4.23, из которой становится очевидным, что, если каждому состоянию любой таблицы переходов с четырьмя состояниями присваиваются два члена из множества Ri, то все переходы могут быть сделаны заменой только одной переменной. Таким образом, это

кодирование представляет собой универсальное ОВП-кодирование для любой таблицы с четырьмя состояниями.