Кибернетика. Строительная отрасль

Навигация

Меню

Электро Эволюция Электросистема Полупроводники Магистрали Интегралсхемы Электрика Хозяйство Компьютер Телефон Аппаратура Резистор

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

[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]

) Материал о линейном двоичном автомате базируется частично на работах Хаффмена (D. А. Huffman, The synthesis of Linear Sequential Coding Networks, «Information Theory*, pp. 77 - 95, Academic Press, Inc. Neu York, 1956. Русский перевод: Д. A. X a ф ф м e н. Синтез линейных многотактных кодирующих схем. В сборнике переводов «Теория передачи сообщений», ИЛ, М., 1957; D. А. Huffman, An Algebra for Periodically Timeva-rying Linear Binary Sequence Tranducers, Annals of the Computation Laboratory, vol. 29, pp. 189 - 203, Harvard University Press, Cambridge Mass., 1959).

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

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

Zv = f{Xv-li X„-i, X„.i, Z„-j, Z„.j, Z„-j =

=Xy,-i © ATv-j© •. • © Jfv-;„© 2v-;, © Zy,-j© ... © z-],

(6.30)

где 0</i</2< ... </„ и 1<У1<У2< ... <У„.

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

= zj=... =z-j = 0.

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

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

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

Zk = CkoXo®CklXi@---@CkkX„, (6.31)

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

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

©fiiv-i ©e22v-2© • • • © ev-j;. (6.32)

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

лг 1 = лг 2.= . . . =X = Z i = Z 2= • • . =2. = 0.(6.33)

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

2о = Мо- (6-34)

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

г 1+1 = ©11 © • • • © V-u+i®ii®41-1 © • • • •. • © V-u+i = "o+i©Mz© • • • ®\Xi i@

(6.35)

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

1+1 = Оо-о© «1-1 © • • • © aiXi® ai+iXi+i. (6.36)

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

Следовательно, если теорема справедлива для k=0, 1.....I,

то она должна быть справедливой для k = l-{-].. По индукции, теорема справедлива для всех kO.

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

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

k = <kolio®c,iln®...®c,,i:,. (6.37)

Аналогично пусть Ijgjj .. • Ijj - входная последовательность, приложенная к автомату М, находящемуся в состоянии покоя, и пусть Суй - реакция автомата М на Тогда

Теперь рассмотрим входную последовательность (;о©1/о) © 1"п) • • (l/ft © l/ft). полученную сложением по модулю 2 соответствующих символов предыдущих двух последовательностей. Пусть Cyft обозначает реакцию автомата М на {lik®l"ik)- Тогда имеем:

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

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

так:

Dy = yy-r- г = 0. 1. 2..... (6.40)

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

(6.41)

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

(6.42)

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