Главная  Кибернетика 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [ 75 ] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

6.7] ВРЕМЕННАЯ ХАРАКТЕРИСТИКА АВТОМАТА 233

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

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

р<2-1. (6.56)

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

= f>oX ® 6ia: i © ... ® 6n"Xv-n" ©

©ei2v-i©e22v-2© • • • ®4Zv-w- (6.57) где коэффициенты 6 и равны О или 1. Положим, что наблюдение свободной выходной последовательности начинается в момент ti , где р, = тах(р., р,"). Тогда для всех v> 1

= ei-l©e2v-2© ••• ©V-H" ()

Тогда не более чем через р. символов каждый выходной символ будет однозначно определяться предшествующими \i выходными символами. Следовательно, выходная последовательность становится периодической с периодом р, если для любого v>-l упорядоченные наборы значений р, переменных • . •. 0 и (2, 1р. Z 2, . . .,

совпадают. Так как существует всего 2* наборов значений р. переменных, последний отрезок длиной р, в выходной последовательности Z Z ...2м , а именно, z 2 и - ... 2 „ -

1 2 2* +(! 2* +1 2* +2 2* +ц

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



Бесконечная часть выходной последовательности, проявляющая периодические свойства, называется периодической частью выходной последовательности; ограниченная часть, которая предшествует периодической части, называется переходной частью выходной последовательности. Если наблюдение за свободной выходной последовательностью начинается в момент ty и если автомат имеет память [о,, то как периодическая, так и переходная части выходной последовательности зависят от значений л; 1, Ху 2, и 2 2, ...

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

символов, содержащаяся в периодической части выходной последовательности. Тогда из доказательства теоремы 6.3 следует, что р подпоследовательностей длины [х (где р. - z-память), начинающихся с символов Cj. Сг- •••> tip Должны

быть различными. Если р имеет максимальное значение 2" - 1, то эти последовательности содержат все ti-разрядные двоичные числа, за исключением г-paзpяднoгo числа 00 ... 0.

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

2 = д: 5®г 1®г з. (6.59)

Запись (6.60) показывает свободную выходную последовательность этого автомата, начиная с момента t, когда начальные условия Ху = Ху = Ху з= Ху = Zy l = 1 и Ху 2 =

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

: 11101 00 0000000 0000000...

001 01 1110100 1110100... (6.60)

Начальные Переход- Период 1 Период 2 условия ная часть



6.7] ВРЕМЕННАЯ ХАРАКТЕРИСТИКА АВТОМАТА 233

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

100 0000000 0000000 ... «й*: ООО 0011101 0011101 ...

(6.61)

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

Входную последовательность, которая является О во все моменты времени, за исключением момента обозначим через 55. Выходную реакцию автомата на будем обозначать М„ является импульсной характеристикой автомата, если импульс приложен в момент/. Будем говорить, что последовательность является суммой последовательностей gl, 2> •••• г записываемой как glQgj© ••• ©г- если символ последовательности в момент равен сумме по модулю 2 символов последовательностей j. • • • в тот же самый момент Таким образом, если есть О во все моменты времени, за исключением ....

то выражение может быть записано так:

=з1®а>1® ... ®а>1. (6.62)

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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [ 75 ] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

0.0011