6.7. Временная характеристика линейного двоичного автомата

Свободную выходную последовательность линейного двоичного автомата М определим как выходную реакцию М на бесконечную входную последовательность 000... Назовем выходную последовательность автомата периодической, если выходной символ в момент времени является таким же, как и в момент для всех v; p — положительное конечное целое число — называется периодом свободной выходной

последовательности. Если выходная реакция постоянна, то ее период равен 1.

Теорема 6.3. Пусть М — линейный двоичный автомат с памятью - памятью Тогда свободная выходная последовательность станет периодической не более чем через символов и ее период

Доказательство. М может быть охарактеризован равенством

где коэффициенты равны 0 или 1. Положим, что наблюдение свободной выходной последовательности начинается в момент где Тогда для всех

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

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

Для примера рассмотрим линейный двоичный автомат АЗО с памятью 5 и с Z - памятью 3, определяемый равенством

Запись (6.60) показывает свободную выходную последовательность этого автомата, начиная с момента когда начальные условия обозначают соответственно входную и выходную последовательности. Как, видно, длина переходной части в этом случае равна 2. Период равен 7, т. е. максимальному значению для заданной -памяти Начиная с третьего выходного символа, имеется семь подпоследовательностей длины 3: 111, 110, 101, 010, 100, 001, 011, составляющих все трехразрядные двоичные числа за исключением 000.

Поведение линейного двоичного автомата, начинающего работать из своего основного состояния, удобно характеризовать посредством его импульсной характеристики. Импульсная характеристика автомата М определяется как выходная реакция автомата М, находящегося в состоянии покоя, на бесконечную входную последовательность 1000... Такая последовательность называяется импульсом. Ясно, что импульсная характеристика автомата, начиная с момента является такой же, как и его свободная выходная характеристика, начиная с момента и при начальных условиях или 1 и при всех предшествующих входных или выходных символах, равных 0. Тогда, по теореме 6.3, следует, что импульсная характеристика станет периодической не более чем через символов, где есть память, -память автомата М. Период импульсной характеристики не может превышать Так, например, импульсная характеристика автомата , заданного равенством (6.59), показана в (6.61).

Переходная Период 1 Период 2 часть

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

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

момент времени в состоянии покоя, то выходная реакция М, обозначаемая через равна:

Поэтому выходная реакция может быть получена сложением по модулю 2 импульсных характеристик автомата М, начинающихся с моментов . Ясно, что если входное возбуждение становится периодическим после ограниченного числа символов, то такой же становится выходная реакция. Например, (6.64) показывает реакцию автомата ЛЗО на последовательность, которая становится периодической (с периодом 1) после четырех символов:

Каждая последовательность из единиц и нулей, которая становится периодической с периодом после символов, может быть записана в форме

где — бесконечная последовательность, которая становится не позднее чем через символов; — бесконечная периодическая последовательность с периодом и без переходной части. называются соответственно переходной составляющей и периодической составляющей М. образуется следующим образом. Если где — неотрицательное целое число, то вычеркнем переходную часть и первые символов из периодической части . Полученная в результате бесконечная последовательность есть тогда определяется равенством:

Например, для М из (6.64) получаем:

Легко можно проверить, что последовательность (6.67) удовлетворяет равенству (6.65).