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

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

 

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

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

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

где коэффициенты δ; и ε_i равны 0 или 1. Положим, что наблюдение свободной выходной последовательности начинается в момент t_1-µ, где µ = mах(µ´,µ´´). Тогда для всех v ≥ 1

Тогда не более чем через µ символов каждый выходной символ будет однозначно определяться предшествующими µ' выходными символами. Следовательно, выходная последовательность становится периодической с периодом р, если для любого v≥l упорядоченные наборы значений µ' переменных

совпадают. Так как существует всего 2^µ наборов значений µ' переменных, последний отрезок длиной µ' в выходной последовательности z₁ z₂ ... z₂^µ´_+µ´, а именно, z₂^µ´₊₁ z₂^µ´₊₂ ... z₂^µ´_+µ´ должен быть таким же, как некоторый предшествующий отрезок длиной µ'. Следовательно, период не может превышать 2^µ´. Теперь положим, что период точно равен 2µ´. Тогда последовательность должна содержать отрезок, который состоит из µ' нулей. Однако из (6.58) можно заключить, что за таким отрезком должна следовать бесконечная последовательность из нулей, период которой равен 1, а не 2^µ´. Так как это противоречит предположению, то период не может превышать 2^µ´ — 1. Периодичность начинается в некоторый момент t_v, где 1 ≤ v ≤ 2µ´, и, следовательно, не более чем через µ + 2^µ´ —1 символов.

 

Бесконечная часть выходной последовательности, проявляющая периодические свойства, называется периодической частью выходной последовательности; ограниченная часть, которая предшествует периодической части, называется переходной частью выходной последовательности. Если наблюдение за свободной выходной последовательностью начинается в момент t_v и если автомат имеет память µ, то как периодическая, так и переходная части выходной последовательности зависят от значений x_v-1, x_v-2, .... x_v-µ и z_v-1, z_v-2, ..., z_{v_µ}, которые составляют начальные условия автомата. Пусть р — период свободной выходной последовательности и пусть ζ_i1 ζ_i2... ζ_ip; — произвольная последовательность из р символов, содержащаяся в периодической части выходной последовательности. Тогда из доказательства теоремы 6.3 следует, что р подпоследовательностей длины µ' (где µ' — z-память), начинающихся с символов ζ_i1, ζ_i2,..., ζ_ip, должны быть различными. Если р имеет максимальное значение 2^µ´ — 1, то эти последовательности содержат все µ'-разрядные двоичные числа, за исключением µ'-разрядного числа 00 ... 0.

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

Запись F(6.0) показывает свободную выходную последовательность этого автомата, начиная с момента t_v, когда начальные условия x_v-5 = x_v-4 = x_v-3 = x_v-1 = z_v-1 = 1 и x_v-2 = z_v-3= z_v-2 = 0. ε и Ȓ обозначают соответственно входную и выходную последовательности. Как,видно, длина переходной части в этом случае равна 2. Период равен 7, т. е. максимальному значению для заданной z-памяти (2³ — 1 = 7). Начиная с третьего выходного символа, имеется семь подпоследовательностей длины 3: 111, 11О, 101, 010, 100, 001, 011, составляющих все трехразрядные двоичные числа за исключением 000.

 

Поведение линейного двоичного автомата, начинающего работать из своего основного состояния, удобно характеризовать посредством его импульсной характеристики. Импульсная характеристика автомата М определяется как выходная реакция автомата М, находящегося в состоянии покоя, на бесконечную входную последовательность 1000 ... Такая последовательность называяется импульсом. Ясно, что импульсная характеристика автомата, начиная с момента t_v, является такой же, как и его свободная выходная характеристика, начиная с момента t_v+1 и при начальных условиях x_v= 1, z_v = 0 или 1 и при всех предшествующих входных или выходных символах, равных 0. Тогда, по теореме 6.3, следует, что импульсная характеристика станет периодической не более чем через 2^µ´ + µ символов, где µ есть память, а µ' — z-память автомата М. Период импульсной характеристики не может превышать 2^µ´ — 1. Так, например, импульсная характеристика автомата A30 заданного равенством (6.59), показана в (6.61).

Входную последовательность, которая является 0 во все моменты времени, за исключением момента t_v, обозначим через Ɖ_v. Выходную реакцию автомата на Ɖ_v будем обозначать Ȓv. Ȓv является импульсной характеристикой автомата, если импульс приложен в момент t_v. Будем говорить, что последовательность ε является суммой последовательностей ε₁,ε₂,..., ε_r записываемой как если символ последовательности ε в момент t_v равен сумме по модулю 2 символов последовательностей ε₁,ε₂,..., ε_r в тот же самый момент t_v. Таким образом, если ε есть 0 во все моменты времени, за исключением ti1, ti2 , .... t_il., то выражение ε может быть записано так:

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

 

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

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

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

где Ȓ_T — бесконечная последовательность, которая становится 000 ... не позднее чем через τ символов; Ȓ_P — бесконечная периодическая последовательность с периодом р и без переходной части. Ȓ_T и Ȓ_P называются соответственно переходной составляющей и периодической составляющей Ȓ. Ȓ_P образуется следующим образом. Если τ = η + kp, где 0≤η≤p, и k — неотрицательное целое число, то вычеркнем переходную часть и первые р — η символов из периодической части Ȓ. Полученная в результате бесконечная последовательность есть Ȓ_P Ȓ_T тогда определяется равенством:

 

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

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