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

[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.63)

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

Г: 101100 <i: 000001 <з: 000000 Mi- 000000 Ж: 000001

0000000 1101001 0111010 0011101 1001110

0000000 1101001 0111010 0011101 1001110

(6.64)

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

Период 1

Период 2

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

M = MT®Stp, (6.65)

где Stj - бесконечная последовательность, которая становится ООО ... не позднее чем через т символов; <йр - бесконечная периодическая последовательность с периодом р и без переходной части. Stf и (йр называются соответственно переходной составляющей и периодической составляющей М. Мр образуется следующим образом. Если т = 11 + /гр, где OTip, и & - неотрицательное целое число, то вычеркнем переходную часть и первые р - г\ символов из периодической части М. Полученная в результате бесконечная последовательность есть St р. Stj тогда определяется равенством:

MT = M®Stp.

(6.66)



6.8) РАСПОЗНАВАНИЕ ЛИНЕЙНОГО ДВОИЧНОГО АВТОМАТА 237

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

<„: 0011101 0011101 ...

Период 1 Период 2 ,„

001111 00000000...

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

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

6.8. Распознавание линейного двоичного автомата

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

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

7(M) = /Tii©DTi2®D4© ... ®D-\ (6.68)

где коэффициенты т]; равны либо О, либо 1. Тогда для автомата М, находящегося в начальный момент времени в состоянии покоя,

•2v = ni.>v©Vv-i©n3.v-2© ••• ©ПЛ-г+1- (6-69)

Предположим теперь, что бесконечная входная последовательность 1000... (т. е. импульс) прикладывается к М в момент При этом мы получим Xi=l, а х, = 0 для всех кф 1. Из (6.69) тогда имеем: Zi = r\i, 2 = Пг, .... •2j = % и = О для всех /г > Поэтому импульсная характеристика автомата, характеризуемого равенством (6.68), определяющим 7 (Ж), имее.т вид • • • П;000 ... Наоборот,



если автомат имеет импульсную характеристику tIj ... ... 11,000 ..., то он может быть охарактеризован передаточным отношением Т{М), которое задано выражением (6.68).

Полученный результат дает возможность найти передаточное отношение автомата, заданного произвольной импульсной характеристикой. Как было установлено в § 6.7, импульсная характеристика М линейного двоичного автомата может быть выражена как сумма переходной и периодической составляющих Slj- и Sip соответственно.

Пусть -

Str = \b2 ... б.(000 .... (6.70)

<P = eie2 ... ££162 ... Ер ... (6.71)

Автомат, который реализует Slj-, имеет передаточное отношение

7г = /61 ® D62 © ... © D-\. (6.72)

Автомат, который реализует Sip, имеет передаточное отношение:

7p = /ei©De2© ... @D>-\@

@D%@Df"-\@ ... ©DP-ep©

© D\ © DP+e2 © • • • © *"ep © © ...

= (/ei©De2© ... ©DP-ep)(/©DP©DP© .. .)= = (/ei©Z)e2© ...

Принимая BO внимание свойство суперпозиции, автомат М, который реализует импульсную характеристику SI = Stj<®Stp, имеет передаточное отношение

Т{M) = Tj®Tp = l\®D\® ... ®D-\®

/в.еРвзе... ерр-Ч

DP ф /

Выражение Т(Ж) может быть записано как отношение двух полиномов от D, у которых может быть сокращен общий делитель, как было объяснено в § 6.6. Таким образом, по импульсной характеристике автомата Ж всегда может быть определено его передаточное отношение. Построение



[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.0009