§ 6.2. Синтез двоичной структуры автономной последовательностной машины

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

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

Задача синтеза автономной П-машины, сформулированная выше, может быть подразделена на четыре задачи:

1. Определение минимального числа .

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

3. Синтез логической абстрактной структуры, которая замещает построенный конечный автомат.

4. Синтез выходного логического преобразователя.

Рассмотрим сначала случай, когда задана только одна последовательность, состоящая из 0 и 1 длины q, и требуется из любого начального состояния периодически генерировать ее (с точностью до циклической перестановки символов), начиная со второго такта работы П-машины.

Выберем наименьшее число , удовлетворяющее неравенству

Рассмотрим автомат, имеющий состояний.

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

Пусть этот автомат имеет граф, у которого первые q кружков объединены в цикл; если , то остальные кружки соединены стрелкой непосредственно с каким-либо кружком на цикле. Условимся, например, соединять эти «лишние» кружки графа с кружком, отмеченным символом 0 (пример для приведен на рис. 6.9).

Рис. 6.9.

По построенному графу сразу восстанавливается основная таблица автономного автомата. Так, для графа, показанного на рис. 6.9, основная таблица имеет вид табл. 6.2.

Построим теперь логическую абстрактную структуру такого автомата. Для этого (см. § 4.2) выберем логических координат (каждая из них может принимать лишь значения из алфавита ) и заполним табл. 6.3.

Таблица имеет строк и разделена двумя вертикальными столбцами, которые соответствуют , на левую и правую части.

В столбец вписываются подряд сверху вниз цифры , т. е. индексы из левого столбца основной таблицы построенного автомата, а в столбец — соответствующие индексы при и в правом столбце этой основной таблицы. В табл. 6.3 в качестве примера первые 8 строк столбцов заполнены в соответствии с табл. 6.2.

Таблица 6.2

В левую часть таблицы (столбцы ) вписываются в двоичной системе счислений числа, содержащиеся в столбце . Для этого удобно воспользоваться правилом, описанным в гл. I: последний столбец (для ) заполняется попеременно 0 и 1, второй столбец справа — парами 0 и 1, третий справа — четверками 0 и 1, пятый — восьмерками 0 и 1, так что в каждом следующем столбце количество 0 или 1 в чередующихся группах удваивается.

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

В качестве примера в табл. 6.4 показано заполнение табл. 6.3, выполненное для автомата, имеющего граф, показанный на рис. 6.9, и основную таблицу, представленную табл. 6.2.

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

Таблица 6.3

Таблица 6.4

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

Теперь рассматриваем второй столбец правой части таблицы (для ) и аналогично отроим правую часть второго соотношения. В случае табл. 6.4 оно имеет вид

Для следующего столбца (для ) аналогично получаем

и т. д., пока не будут рассмотрены все строк и таким образом восстановлены все соотношений искомой двоичной (логической) абстрактной структуры.

Построим теперь выходной логический преобразователь

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

Так, например, если задана последовательность длины 5 вида 10010, то составляются соответствия

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

Выделим те номера кружков, которым соответствует в заданной последовательности символ 1. В нашем примере это кружки 0 и 3. Им соответствуют состояния .

Составим конъюнкцию, характеризующую значения всех координат в каком-либо из этих выделенных состояний, например . С этой целью составляем коньюнкцию из всех и ставим знак отрицания над теми из них, для которых в строке левой части табл. 6.3 вписаны нули. Поступая так со всеми выделенными состояниями, соединим получающиеся конъюнкции знаками дизюнкции.

Так в рассмотренном выше примере были выделены два состояния: . Рассмотрим первое из них — состояние . В строке для табл. 6.4 вписаны только 0. Поэтому знак отрицания ставится над всеми тремя координатами Получаем конъюнкцию

Для второго выделенного состояния в соответствии с четвертой строкой табл. 6.4 имеем конъюнкцию

В результате получаем логическую функцию

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

Полученные дизъюнктивные формы, описывающие работу автомата и преобразователя, могут быть упрощены методами исчисления высказываний, исходя из любого критерия оптимальности.

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

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

Выберем наименьшее , удовлетворяющее неравенству

Если

то граф автомата может иметь как раз циклов, каждый длиной ). Если же

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

Теперь рассмотрим случай, когда последовательностная машина зависит от параметра , который можно менять, т. е. двоичная структура

содержит s двоичных параметров, допускающих выборов.

Пусть задано последовательностей.

Рис. 6.10.

Требуется построить двоичную абстрактную структуру П-машины по обычной схеме (рис. 6.10), т. е. двоичную структуру автомата А (6.9) и преобразователя

так, чтобы машина генерировала заданные m последовательностей. При этом числа и s должны быть наименьшими. Выбор генерируемых последовательностей производится за счет выбора параметров .

Выделим среди заданных последовательностей самую длинную. Пусть она имеет длину , т. е. содержит символов. Найдем наименьшие значения и s, удовлетворяющие неравенствам

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

Методом, описанным выше, построим для каждого из графов таблицу типа табл. 6.3, т. е. определим правые части в соотношениях

соответствующих каждому графу двоичной абстрактной структуры.

Пусть для графа эти соотношения имеют вид

и, таким образом, определено соотношений.

Введем в рассмотрение двоичных переменных и построим таблицу всех возможных сочетаний символов . Эта таблица (табл. 6.5) строится по типу левой части табл. 6.3. Табл. 6.5 имеет строк. В правом столбце перенумерованы первые m строк. Это, возможно, так как в силу (6.2) число строк не менее чем .

Таблица 6.5

Возвращаясь к соотношению (6.14), которое относится к графу, усложним его добавлением в правые части всех соотношений конъюнкций из тех символов , для которых в строке табл. 6.5 вписана 1 (а не 0). Вместо (6.14) получаем соотношение вида

Может быть выписано систем соотношений типа (6.15), если последовательно принимать .

Теперь объединим дизъюнкцией правые части всех первых соотношений из этих систем. Так же поступим с правыми частями всех вторых соотношений этих систем и т. д. В результате получаем одну систему соотношений вида

где через обозначены конъюнкции всех элементов , для которых в строке табл. 6.5 стоит 1.

Рассмотрим теперь все как параметры и выберем их, например, в соответствии с третьей строкой табл. 6.5. Тогда , а все остальные U равны нулю и в каждом из соотношений (6.16) останется лишь третий конъюнктивный член. Система (6.16) совпадает тогда с системой (6.14) при . Граф этой системы состоит из цикла, включающего столько кружков, сколько символов (т. е. 0 и 1) в третьей из заданных последовательностей.

Соотношения (6.16) являются, таким образом, абстрактной структурой, замещающей конечный автомат, в котором за счет выбора вектора U в соответствии с первыми строками табл. 6.5 можно получить построенных выше графов. Это обеспечивает генерирование последовательностей заданных длин.

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

Пусть эти выходные преобразователи будут

Тогда искомый преобразователь, который надо добавить к (6.16), описывается соотношением

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

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