Последовательностная машина
Cтраница 1
Последовательностная машина называется машиной без потери информации порядка k, если k - наименьшее целое число, такое, что начальное состояние и первые k выходов однозначно определяют начальный вход. Используя его результат, можно показать, что для машин с п состояниями k ( 1 / 2) п ( п - 1) 1 однако машина, для которой эта оценка достигается, не была получена. В настоящей статье будет показано, что для любого п существует Последовательностная машина с п состояниями, для которой верхняя граница достигается. [1]
Последовательностная машина называется машиной без потери информации, если каждый раз входная последовательность определяется начальным состоянием, заключительным состоянием и выходной последовательностью. Очевидно, что машина без потери информации порядка k является машиной без потери информации. Однако известно ( Хаффмэн [2]), что существуют последо-вательностные машины без потери информации, не имеющие квазиобратных последовательностных машин. [2]
Обобщенной последовательностной машиной ( ОПМ) называется 0 - ПРВ. [3]
Функция, являющаяся откликом обобщенной последовательностной машины ( S. Если не ограничиваться случаем машин с конечным числом состояний, то обобщенная последовательность эквивалентна следующему свойству сохранения исходных подслое: для любых и, v из / функция / ( uxi) имеет вид f ( и) w при некотором w из О, где /, О - множества всех входных и выходных строк. [4]
С применением существующих видов конечных последовательностных машин, известных под названием цифровых вычислительных машин, задачи управления решаются путем программирования. [5]
 |
Двоичный сумматор. [6] |
На рис. 6.23 показана блок-схема последовательностной машины, складывающей двоичные числа. [7]
С помощью метода преобразования Лапласа нетрудно синтезировать, последовательностные машины, которые в состоянии либо распознавать периодические последовательности ( и последовательности из семейства, получающегося смещением на заранее обусловленную величину последовательности, генерируемой машиной), либо узнать число единиц в периодической последовательности, либо, наконец, просто узнать период последовательности. [8]
Наконец, покажем, что прообраз ЯРВ при отображении недетерминированной последовательностной машиной может не быть ЯРВ. Недетерминированная последовательностная машина есть шестерка U ( Q, 2, А, М, R, Q0), где Q - конечное множество состояний, 2 - входной, а А - выходной алфавиты, М - функция, отображающая Q X 2 в 2Q, R - отображение Q X 2 в Л и Qo s Q - множество начальных состояний. U действует очевидным способом. [9]
Определение таблицы переходов можно найти в работе Хаффмена [34] или в любом учебнике по теории последовательностных машин. [10]
Для более точного задания параметров программного обеспечения и самих микропроцессоров был разработан ряд формализованных методов и средств проектирования, к числу которых относится метод LCF-LSM ( Logic of Computable Functions, Logic of Sequential Machines - Логика вычисляемых функций, логика последовательностных машин), разработанный в Лаборатории вычислительных машин Кембриджского университета. Для этого МП был, кроме того, разработан специальный структурный язык ассемблера VISTA и предусмотрен контроль корректности программы. [11]
Любой автомат Мура путем добавления ряда состояний может быть преобразован в эквивалентный автомат Мили. Обобщенная последовательностная машина - это расширение понятия последовательностной машины: на каждой стадии здесь выводится строка символов, а не один символ. [12]
Таким образом, вопросы кодирования, коррекции ошибок, синтеза шифраторов и дешифраторов, которые ранее были далеки от общей теории управления, сейчас могут рассматриваться с единой точки зрения. На последовательностные машины распространяется понятие управляемости, оптимальности, устойчивости. Сейчас намечается тенденция установления непосредственной связи между системами управления и последовательностными машинами, конечными автоматами. [13]
Цифровой накапливающий сумматор являются простейшим узлом с памятью. Аналогично могут быть построены более сложные последовательностные машины. [14]
Любой автомат Мура путем добавления ряда состояний может быть преобразован в эквивалентный автомат Мили. Обобщенная последовательностная машина - это расширение понятия последовательностной машины: на каждой стадии здесь выводится строка символов, а не один символ. [15]
Страницы: 1 2