КОДИРОВАНИЕ СОСТОЯНИЙ АВТОМАТА
— установление соответствия между состояниями автомата и наборами значений кодирующих их переменных. К. с. а. — один из этапов синтеза автоматов структурного.
Каждой кодирующей переменной соответствует элементарный автомат композиции, которая реализует (или должна реализовать) исходный абстрактный автомат. Мн-во значений каждой кодирующей переменной совпадает с мн-вом состояний соответствующего элементарного автомата. Количество кодирующих переменных (количество элементарных автоматов) определяет длину кода. Задача К. с. а. состоит в отыскании такого кодирования, которое удовлетворяло бы некоторым заданным условиям. Эти условия, напр., могут выражать ограничения, накладываемые физ. особенностями элементарных автоматов, требованиями надежности схемы и т. п. Наиболее распространенным является двоичное кодирование. В этом случае кодирующие переменные принимают значения во мн-ве, состоящем из двух элементов (двоичный структурный алфавит), а элементарные автоматы имеют по два состояния.
В качестве конкретных примеров задач кодирования можно назвать: задачу противогоночного кодирования, задачу монотонного кодирования и задачу экономичного кодирования состояний. Условия противогоночного кодирования запрещают возникновение гонок в структурном автомате и выражаются в том, что различие во временах переключения элементарных автоматов не должны влиять на результат при переходе из одного состояния в другое. Монотонное кодирование требует монотонности ф-ций возбуждения структурного автомата. Задача экономичного кодирования состоит в отыскании такого кодирования, которое бы минимизировало функционал аппаратурных затрат в реализации структурного автомата. Т. к. для некоторых автоматов невозможно найти кодирование, удовлетворяющее заданным условиям, задача кодирования тесно связана с задачей отыскания достаточных условий существования кодирования с заданными свойствами и алгоритмов проверки этих условий. Проверка существования и отыскание нужного кодирования, как правило, связаны с перебором и имеют характер последовательного анализа вариантов кодирования. В виду трудоемкости этих задач при их решении приходится пользоваться ЦВМ.
Лит.: Мацевитый Л. В., Денисенко Е. Л. О кодировании внутренних состояний Некоторых многотактных устройств. «Кибернетика», 1966; Лазарев В. Г., Пийль Е. И. Синтез управляющих автоматов. М., 1970 [библиогр. с. 392—398]. Ю. В. Капитонова.
