Синтез и отладка алгоритмов функционирования цифровых устройств управления - 32 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

32
не будет содержать операционный автомат, т. к. не осуществляется преоб-
разование входной информации, а осуществляется только её анализ. Такое
устройство относится к классу "автомат-распознаватель". Во втором приме-
ре проектируемое цифровое устройство реализует параллельный алгоритм
вычисления арифметического выражения. В этом случае цифровое устрой-
ство будет содержать как управляющий автомат, так
и операционный авто-
мат.
3.1 Автомат-распознаватель
Рассмотрим решение задачи, в которой требуется за один просмотр
входной последовательности символов, заканчивающейся специальным
символом "bottom", идентифицировать наличие в ней хотя бы одной из трёх
искомых цепочек-образов. Входной алфавит Z=(z
1
, ... ,z
9
). Искомые цепоч-
ки-образы: z
1
z
2
z
2
... z
2
z
1
; z
3
z
2
z
1
; z
3
z
2
z
3
... z
2
z
3
z
1
(многоточие означает появле-
ние символа, стоящего слева и справа от него, любое число раз, но не менее
одного). Необходимо выполнить проектирование и исследование алгоритма
работы ЦУ для решения этой задачи.
При разработке алгоритма поиска совершенно не существенна двоичная
кодировка символов алфавита в реальной системе. Поэтому на данном эта-
пе удобно
работать с абстрактными входными сигналами.
Для разработки алгоритма с использованием СОМПА рекомендуется
выполнить следующие шаги проектирования.
На первом шаге запишем алгоритм поиска цепочек в последовательно-
сти символов регулярным выражением на языке РВАС (вопросы идентифи-
кации цепочек-образов рассмотрены в [4]):
s(y)=s
0
(z
1
z
2
{z
2
}z
1
∨z
3
z
2
z
1
∨z
3
{z
2
z
3
}z
1
).
На втором шаге в окне редактора РВАС введем это регулярное выра-
жение (рис. 3.1).
Рис. 3.1
На третьем шаге выполним преобразование описания алгоритма с язы-
ка РВАС на язык СКУ и СВФ. Следует обратить внимание, что полученный
алгоритм поиска является параллельным и для его описания используется
НДСКУ [2]. Поскольку выразительные возможности языка РВАС при запи-
не будет содержать операционный автомат, т. к. не осуществляется преоб-
разование входной информации, а осуществляется только её анализ. Такое
устройство относится к классу "автомат-распознаватель". Во втором приме-
ре проектируемое цифровое устройство реализует параллельный алгоритм
вычисления арифметического выражения. В этом случае цифровое устрой-
ство будет содержать как управляющий автомат, так и операционный авто-
мат.

                    3.1 Автомат-распознаватель
   Рассмотрим решение задачи, в которой требуется за один просмотр
входной последовательности символов, заканчивающейся специальным
символом "bottom", идентифицировать наличие в ней хотя бы одной из трёх
искомых цепочек-образов. Входной алфавит Z=(z1, ... ,z9). Искомые цепоч-
ки-образы: z1z2z2 ... z2z1; z3z2z1; z3z2z3 ... z2z3z1 (многоточие означает появле-
ние символа, стоящего слева и справа от него, любое число раз, но не менее
одного). Необходимо выполнить проектирование и исследование алгоритма
работы ЦУ для решения этой задачи.
   При разработке алгоритма поиска совершенно не существенна двоичная
кодировка символов алфавита в реальной системе. Поэтому на данном эта-
пе удобно работать с абстрактными входными сигналами.
   Для разработки алгоритма с использованием СОМПА рекомендуется
выполнить следующие шаги проектирования.
   На первом шаге запишем алгоритм поиска цепочек в последовательно-
сти символов регулярным выражением на языке РВАС (вопросы идентифи-
кации цепочек-образов рассмотрены в [4]):
                          s(y)=s0(z1z2{z2}z1∨z3z2z1∨z3{z2z3}z1).
   На втором шаге в окне редактора РВАС введем это регулярное выра-
жение (рис. 3.1).



                                       Рис. 3.1

   На третьем шаге выполним преобразование описания алгоритма с язы-
ка РВАС на язык СКУ и СВФ. Следует обратить внимание, что полученный
алгоритм поиска является параллельным и для его описания используется
НДСКУ [2]. Поскольку выразительные возможности языка РВАС при запи-



                                       32

Страницы