Главная > Логические методы анализа и синтеза схем
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

ВВЕДЕНИЕ

Введем основные понятия, на которых будет базироваться дальнейшее изложение.

Рассмотрим некоторое устройство (рис. В-1 ,а) - с входами и выходами, на каждый вход которого может быть подан произвольный символ из конечного алфавита

называемого входным алфавитом.

Совокупность символов, поданных на вход устройства, образует входное слово над алфавитом X нашего устройства. Один из символов алфавита X (например, ) соответствует пустому символу. Если на некоторый вход устройства подается символ то физически это означает отсутствие какого-либо возбуждения устройства по данному входу.

На выходе устройства появляются выходные слова, составленные из символов выходного алфавита:

В силу конечности алфавитов X и Y и входных и выходных слов (длина входного слова всегда равна , а выходного — ) общее число различных входных и выходных слов конечно.

Элементарный такт работы устройства состоит в том, что при появлении на входе устройства входного слова устройство выдает на выходах комбинацию выходных символов, образующих выходное слово

Рис. В-1.

Пусть работа устройства полностью определяется лишь входным словом. Тогда работа такого устройства будет определена, если мы зададим следующую таблицу соответствия для всех входных слов

В таблице имеется строк по числу различных входных слов длины над алфавитом X, состоящим из различных символов.

Определение Устройство, условия работы которого описываются при помощи соответствия называется конечным автоматом без памяти, или комбинационной схемой.

Автомат такого типа может рассматриваться как устройство, производящее кодирование слов над алфавитом X словами над алфавитом Очевидно, что декодирование при этом не всегда возможно.

Конечные автоматы без памяти являются наиболее простыми логическими устройствами дискретного типа. Рассмотрению методов анализа и синтеза подобных автоматов посвящена первая часть настоящей книги.

Рассмотрим автомаш более сложной природы. Зададимся конечным алфавитом

который назовем алфавитом внутренних состояний. Символы будем называть в нутре а ними состояниями (состояниями).

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

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

определена, если заданы две таблицы А и В следующего вида:

Первая таблица определяет выходное слово, соответствующее паре а вторая — определяет внутреннее состояние устройства в следующий такт.

Определение Устройство, работа которого определяется таблицами А и В, называется конечным автоматом с глубиной памяти

Такой автомат изображен на рис.

Конечные автоматы без памяти и с памятью являются устройствами детерминированного типа. Описание их работы в виде соответствия (рис. или таблиц А и В есть задание жесткого алгоритма их работы.

Естественным обобщением таких детерминированных автоматов являются автоматы стохастического типа. В таких автоматах вместо однозначного соответствия

задается лишь вероятность замены на или на

Эта вероятность для случая автомата без памяти задается с помощью стохастической матрицы

Элемент в этой матрице определяет вероятность появления слова на выходе автомата, если на его вход подано слово При этом

В случае автомата с памятью такие матрицы задаются для каждого столбца таблицы А и каждого столбца таблицы В.

Стохастические автоматы в настоящее время изучаются весьма интенсивно; теория таких автоматов находится в состоянии становления. Рассмотрение методов анализа и синтеза стохастических автоматов требует особого аппарата и выходит за рамки настоящей работы.

Мы пока не накладывали никаких ограничений на природу символов, образующих алфавиты и Теперь потребуем, чтобы эти символы были бы закодированы в числовой форме.

Для большего удобства рассуждений и возможностей логического анализа и синтеза схем автоматов мы чаще всего будем предполагать, что символы алфавитов X, Y и закодированы двоичным кодом. Это означает, что каждый символ алфавита состояний входного и выходного алфавитов соответствует некоторому слову из алфавита:

Рассмотрим пример такого кодирования. Пусть алфавит состоит из трех символов, представляющих собой цвета: желтый, синий и красный, и пусть алфавит состоит из шести символов, также представляющих собой цвета: желтый, синий, красный, зеленый, оранжевый и фиолетовый.

Устройство, перерабатывающее цвета, является конечным автоматом без памяти, с двумя входами и одним выходом. Это устройство отображает всевозможные слова длиной в два символа над алфавитом X в слова длиной в один символ над алфавитом У. Зададим теперь

Таблицу соответствия в следующей форме:

Устройство, работающее в соответствии с этой таблицей, является автоматом для оптического сложения двух цветов.

Для нумерации символов алфавитов X и сопоставим каждому из цветов десятичное число от 0 до Тогда таблица соответствия примет следующий вид:

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

Двоично-кодированная таблица соответствия имеет вид:

Видно, что двоичное кодирование алфавитов X и сводится к увеличению длины слов, поступающих на вход автомата и выдаваемых на его выходе.

Минимальное число двоичных разрядов, которое необходимо затратить при двоичном кодировании символов из алфавитов X и определяется из следующего соотношения:

где — число символов в алфавите (т. е. общее число различных символов алфавитов X и означает целую часть

Таким образом, путем соответствующего кодирования автомат с произвольным входным и выходным алфавитом может быть приведен к автомату с двоичным входом и выходом. Однако этот новый автомат должен оперировать со словами входного и выходного алфавита, длина которых больше длин соответствующих слов исходного автомата. Если для автомата с алфавитом X, состоящим из символов, и алфавитом У, состоящим из I символов, длина слов на входе и выходе равна соответственно и то для эквивалентного ему двоичного автомата допустимая длина слов на входе и на выходе равна соответственно где величина определяется на основании соотношения (В-2).

В первой и во второй частях настоящей работы рассматриваются методы анализа и синтеза двоичных автоматов. В третьей части рассматриваются аналогичные проблемы для автоматов, у которых произведено лишь цифровое, но не обязательно двоичное кодирование алфавитов X и

1
Оглавление
email@scask.ru