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

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

>) Несущественная переменная является такой переменной, которая оставляет без изменения значение функции независимо от значения, принимаемого этой переменной.

быть записано в форме

Zv - g(Xv-i, Xv-i....."-и v-y,. v-/2.....v-/J.

(6.1)

где принято, что О < 1 < 2 < • • • < <u и 1 < yl < Уг < •.. ... < Д. Если добавить ряд несущественных переменных i) и принять /„ = 1 и Уг, = М2 ™ урзвнение (6.1) можно записать в виде

Zv = /(Arv. Av-l.....-"fv-H,. Z-h Z„-2.....v J. (6.2)

Для того чтобы преобразовать приведенное характеристическое уравнение в характеристические стандартные функции Д и Д конечного автомата, переменную s определим так, чтобы Sy являлась упорядоченным набором значений

(lii + M2) переменных (aTv-i. Arv-2. -v-n,. Tv-i. Zv 2. ••• Zv-hj). Равенство (6.2) тогда примет вид

-2v = /z(v. *v)- (6-3)

Из определения s следует, что s+j определяется так:

(aTv. -fv-b •••• -"V-Hi+b v, v-l.....v-Hj+i) =

= (ATv. ATv-1.....-"v-Hi+b f {Xy, ATv-li АГу-ц,>

Zv-I, Zv 2. Tv-Hj), v 1.....Zv Hj+i). (6.4)

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

*v+l = (Arv> .....-"v-n,. .....V-Hj) (6.5)

5v+l = A(v. *v)- (6-6)

Уравнения (6.3) и (6.6) могут рассматриваться как характеристические функции конечного автомата. Следовательно, множество упорядоченных наборов значений (мх + Мг) переменных (aTv-i, лгу 2.....-"v-n,. Zv-i. Zv-2.....Zv-ii) адекватно множеству состояний системы, представленной урав-



6.2] ПРЕДСТАВЛЕНИЕ СИСТЕМ С КОНЕЧНОЙ ПАМЯТЬЮ 213

нением (6.2). Если число символов входного и выходного алфавитов для системы соответственно равно р и , то мощность множества состояний будет

n = pV-qV-K (6.7)

В качестве примера рассмотрим устройство Л27. На устройство периодически поступают цифры О и 1, выход его в момент равен сумме по модулю 2 выхода в момент и входа в момент t 2. Обозначая сложение по модулю 2 знаком © 1), Л27 может быть охарактеризовано равенством

Z = X2®-1 = (6.8)

Добавляя несущественные переменные и аг 1, вместо (6.8) получим:

z = f(x, x i, х 2. z i). (6.9)

Входной алфавит в этом случае

. = {0. 1}.

а выходной алфавит

Z={0. 1}.

Множество состояний является множеством всех упорядоченных наборов значений трех переменных (лг 1, аг 2. z i):

5= {(0. 0. 0), (О, О, 1). (О, 1, 0). (О, 1, 1), (1, О, 0), (1. О, 1).

(1. 1. 0). (1. 1. 1)}.

Зависимость между х, s, s и может быть представлена в табличной форме, как показано в таблице 6.1. Столбцы таблицы под представляют все упорядоченные наборы значений трех переменных; каждый набор записан дважды (по одному разу для каждого значения х). Столбцы, озаглавленные «54 1», могут быть заполнены путем воспроизведения ранее заполненных столбцов (таких как х и х {) и

) Сложение по модулю 2 определяется следующим образом: 0®0 = 0, 0®1 = 1, 1®0=1, 1®1=0. Если у прини.мает значение О или 1, то у ® у = 0.



Таблица 6.1 Соотношения между х, s, Sv+i и 2v для Л27

путем использования соотношения (6.8) (для столбца z). Показанную таблицу удобно использовать для определения характеристических функций Д и Д автомата Л27. Например,

Таблица 6.2

Автомат Л27

%+1

(0, 0, 0)

(0, 0. 0)

(1. 0, 0)

(0, 0, 1)

(0, 0, 1)

(1. 0, 1)

(0, 1, 0)

(0, 0. 1)

(1, 0, 1)

(0. 1. 1)

(0, 0, 0)

(1. 0. 0)

(1, 0, 0)

(0, 1. 0)

(1, 1, 0)

(1, 0, 1)

(0, 1. 1)

(1, 1. 1)

(1. 1. 0)

(0, 1. 1)

(1. 1. 1)

(1. 1- 1)

( 1. 0)

(1. 1. 0)



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