6.6. Линейные двоичные автоматы

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

где

Основное состояние линейного двоичного автомата определяется как состояние автомата, в котором

Будем говорить, что автомат находится в покое, если он находится в основном состоянии.

Теорема 6.2. Пусть М есть линейный двоичный автомат, находящийся в покое в момент времени и пусть в момент к автомату М прикладывается входная последовательность Тогда реакция

М в момент определяется выражением

где коэффициенты равны либо 0, либо 1.

Доказательство. Пусть автомат М имеет память . Тогда М может быть охарактеризован уравнением

где коэффициенты принимают значения 0 или 1. Если М находится в состоянии покоя в момент , то

Следовательно,

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

Так как по (6.33) все переменные с отрицательными индексами равны 0, то (6.35) можно записать в виде

где коэффициенты принимают значения либо 0, либо 1.

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

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

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

Аналогично пусть — входная последовательность, приложенная к автомату М, находящемуся в состоянии покоя, и пусть — реакция автомата М на Тогда

Теперь рассмотрим входную последовательность полученную сложением по модулю 2 соответствующих символов предыдущих двух последовательностей. Пусть обозначает реакцию автомата М на Тогда имеем:

Поэтому линейный двоичный автомат, выведенный из покоя, подчиняется принципу суперпозиции: выходная реакция на сумму (по модулю 2) входных воздействий равна сумме (по модулю 2) выходных реакций на отдельные входные воздействия.

Теперь введем оператор задержки D, определяемый так:

где у может обозначать как так и z. Вместо будем писать В терминах операторов задержки выражение (6.30) может быть записано так:

Прибавляя (по модулю 2) к обеим частям равенства (6.41), получим:

или

Характеристики вход - выход линейного двоичного автомата М могут быть выражены передаточным отношением, обозначаемым через Т (М):

Если задано передаточное отношение автомата, то функция в том виде, как она представлена равенством (6.30), всегда может быть определена выполнением в обратном порядке операций, описываемых уравнениями (6.41) — (6.44).

Из определения D и равенства (6.41) следует, что

Из (6.45) и свойства суперпозиции следует, что если автомат, характеризуемый равенством (6.41), находится в состоянии покоя, то обе части (6.41) могут быть умножены без нарушения равенства на произвольный полином от D:

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

Для примера рассмотрим линейный двоичный автомат определенный равенством

или

Поэтому передаточное отношение для имеет вид

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

Последний делитель (показанный стрелкой) является общим наибольшим делителем. Для того чтобы понизить передаточное отношение, разделим его числитель и знаменатель на этот делитель:

Из (6.51) и (6.52) получаем:

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

или

Например, если находится в начальный момент времени в состоянии покоя, то его выходная реакция на входную последовательность 100111001010 по равенству (6.55) будет 011011010001. Можно легко проверить, что эта выходная реакция совпадает с реакцией, которая получается при первоначальном (более длинном) соотношении (6.47).

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