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

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

Г(Л1)=;--7 (6.44)

(О»© ... ©DsQdA ©/)z = (d«© ...©D2©di)a:.

(6.43)

Характеристики вход-выход линейного двоичного автомата М могут быть выражены передаточным отношением, обозначаемым через Г (Ж):

D ® ... ® Рф Р . Р- ф ... ф Р- ф Р-

Если задано передаточное отношение автомата, то функция / в том виде, как она представлена равенством (6.30), всегда может быть определена выполнением в обратном порядке операций, описываемых уравнениями (6.41) - (6.44). Из определения D и равенства (6.41) следует, что

Dz = D{Dx@Dx® ... ®Dx@Dz@

@dz® ...®Dvz). (6.45)

Из (6.45) и свойства суперпозиции следует, что если автомат, характеризуемый равенством (6.41), находится в состоянии покоя, то обе части (6.41) могут быть умножены без нарушения равенства на произвольный полином от D:

(D*©D*-»© ...©/).2 = (D*©D*-i© ...©/)

{dx®dx@ ... ®dx®dz®dz®... ®dvz).

(6.46)

Следовательно, если заданный линейный двоичный автомат М находится в начальный момент времени: в состоянии покоя, то числитель и знаменатель его передаточного отношения могут быть умножены на произвольный полином от D. Кроме того, если М находится в начальный момент времени в состоянии покоя и полиномы числителя и знаменателя его передаточного отношения содержат общий множитель, то этот общий множитель может быть без ущерба сокращен. Сокращение общего множителя, которое может быть выполнено с помощью алгоритма Евклида, понижает порядок полиномов числителя и знаменателя в передаточном отношении, тем самым упрощая как анализ, так и синтез рассматриваемого автомата.



D®I

D* ® ® D ® I

\D ® D<® Dq

@ DU

D*®D®DQ

D*® D®D(i

(6.52)

Для примера рассмотрим линейный двоичный автомат А29, определенный равенством

= ЛГ 1 © ЛГ з © ЛГ 5 © ЛГ в © ©

©V-8©2v-l©2v-6©2v-7 (6-47)

2-7 ©2-6 ©2-1 ©2 =

= © © v-6 © © © (6-48)

Поэтому передаточное отношение для Л29 имеет вид

/ (Лгщ - D@D@D®I • -

Для того чтобы определить общий наибольший делитель полиномов числителя и знаменателя, применим алгоритм Евклида, заменив вычитание по модулю 2 сложением (и заметив, что

D©D = 0): .

D»®Di®D®D D (6.50)

0«фО»фО!фО» 10фО«фОф/

О ф О" ф 0« ф О Ф О

общий наибольший делитель -> D« ф £> ф D ф / ОфОфОфО

ОфОфОфО 0.

Последний делитель (показанный стрелкой) является общим наибольшим делителем. Для того чтобы понизить передаточное отношение, разделим его числитель и знаменатель на этот делитель:

D*® Р® D

D* ® ® D ® l\ ® ® ® ® ® D (6.51) ® D @ ® D* D® D*® ® D D° ® ® ® D D®D*@D@D D® D*@ D® D



Из (6.51) и (6.52) получаем:

фз © /) (D © D © D © /) D © /

(6.53)

Поэтому работа автомата Л29, находящегося в начальный момент времени в состоянии покоя, может быть охарактеризована выражениями

•2v-3©2v = -v-4©-v-2©-v-l. (6-54)

Zy = Xy @Xy 2@Xy @Zy . (6.55)

Например, если Л29 находится в .начальный момент времени в состоянии покоя, то его выходная реакция на входную последовательность 100111001010 по равенству (6.55) будет 011011010001. Можно легко проверить, что эта выходная реакция совпадает с реакцией, которая получается при первоначальном (более длинном) соотношении (6.47).

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

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

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



[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