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

Задача, упомянутая в названии этого параграфа, уже рассматривалась в гл. V, где она была частично решена. Здесь мы дадим другой метод решения, пригодный для машин любого типа.

Пусть задана произвольная П-машина G, тактность которой определяется моментами, когда изменяются состояния на ее входе. Формой задания машины G пусть будет матрица соединений либо диаграмма состояний. Множество допустимых входных последовательностей машины G содержит все возможные последовательности, кроме тех, в которых имеются повторяющиеся подряд символы.

Требуется построить быструю П-машину S, которая бы воспроизводила относительно заданную машину G при следующем законе преобразования тактности: моментами . наступления медленных тактов являются моменты прихода машины в состояния равновесия после любого изменения входа (т. е. в состояния, которые в быстрых тактах переходят в себя при неизменном входе).

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

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

Множество последовательностей вида (10.6) при условии будем обозначать символом . Множества удовлетворяют соотношению

причем .

Итак, за множество для машины можно взять любое множество при условии .

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

Построение машины выполним путем преобразования диаграммы состояний заданной машины .

Рассмотрим кружок диаграммы состояний машины G. Пусть, например, этот кружок вместе с подходящими к нему и отходящими от него стрелками имеет вид рис. . Заменим кружок m несколькими кружками, число которых будет равно числу подходящих к кружку стрелок с различными надписями (кольцевая стрелка считается как подходящей, так и отходящей).

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

В нашем случае (рис. 10.6) кружок следует заменить четырьмя кружками (они обведены пунктиром на рис. 10.7).

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

В нашем примере от кружка следует отвести стрелки к кружкам от кружка — стрелку к кружку и стрелку к кружку , от кружков — стрелки к кружку и стрелки с надписью к кружку , охваченному петлей .

Осуществим описанную перестройку для всех кружков диаграммы состояний машины G. В результате будет получена диаграмма состояний машины S, которая воспроизводит относительно заданную машину соответствие состояний машины G и S будет таково (рис. 10.6 и 10.7): состоянию машины G при входе соответствует состояние машины S, равновесное при этом это же состояние соответствует и состоянию машины G при состоянию при входе соответствует состояние машины S, равновесное при состоянию при соответствует , равновесное при , и т. д. Аналогично устанавливается соответствие и в общем случае.

Рис. 10.6.

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

Это означает, что для построенной машины введенное выше число . Кроме того, непосредственно по диаграмме видно, что машина S не имеет неустойчивых ни при каком входе состояний; каждое состояние при каком-либо определенном входном воздействии является равновесным (все кружки охвачены петлями).

Быстрая входная последовательность, которая при воспроизведении соответствует входной последовательности медленной машины имеет вид (10.6), причем все 1. Принимая в этих соотношениях знак равенства, находим, что одна из соответствующих входных последовательностей машины S имеет вид раораграг , т. е. совпадает со входной последовательностью машины .

Рис. 10.7.

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

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

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

Пусть задана матрица соединений машины G. Рассмотрим строку и столбец этой матрицы. Пусть в соответствии с примером рис. строка и столбец имеют вид

Заменим строку и столбец матрицы столькими строками и столбцами, каково число различных пар, содержащихся в столбце матрицы . В нашем примере различных пар в столбце четыре: это пары . Следовательно, строку и столбец заменяем, четырьмя строками и столбцами: :

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

Далее: в строке столбца матрицы содержалась пара впишем ее в ту же строку -матрицы С в тот из столбцов, в котором пара уже содержится. В нашем примере это — столбец . Аналогично поступаем с остальными парами, содержащимися в столбце матрицы . После этого столбцы матрицы С будут заполнены. В каждом из этих столбцов будут содержаться только одинаковые пары.

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

Пару напишем во всех четырех строках в том столбце, в котором она уже имеется.

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

Отметим свойство матрицы : в любом из столбцов этой матрицы могут содержаться лишь одинаковые пары.

Нетрудно видеть, что процесс перестройки матрицы соединений совпадает с описанным выше процессом перестройки диаграммы состояний.

Сделаем в заключение два замечания.

Замечание первое. В § 10.3, так же как и в § 10.2, построение машины S выполнено столь «удачно», что имеет место не только воспроизведение, но и изображение. В качестве множества допустимых входных последовательностей при изображении можно взять любое множество, в том числе и множество Е, так как входные воздействия машины 5 могут меняться даже с частотой быстрых тактов, ибо для машины 5 число m равно 1. Соответствие состояний при изображении будет тем же, что и при воспроизведении.

Замечание второе. Описанный прием дает один из способов построения быстрой П-машины , воспроизводящей относительно заданную П-машину G. Возможны и иные способы решения этой задачи, так как П-машина , воспроизводящая относительно машину G, не единственна.

Поэтому, естественно, возникает задача минимизации машины S, т. е. построение такой -машины S, воспроизводящей относительно заданную машину G, которая имеет наименьшее число состояний.