§ 5.4. Метод и реализация Хафмана
Работа Хафмана [170] по релейно-контактным схемам не содержит еще понятий последовательностной машинь или конечного автомата, или каких-либо иных эквивалентных им понятий. Приводя ряд примеров задания на синтез релейно-контактной схемы, Хафман показывает, как может быть в этих случаях построена специальная таблица — Хафман называет ее таблицей переходов (flow table), — которая является исходной в его методе. Считая далее, что таблица переходов задана, Хафман показывает, как она может быть упрощена (но не доказывает, что это упрощение предельно возможное), и разрабатывает универсальный способ построения релейноконтактной схемы, реализующей эту таблицу переходов. В работе Хафмана релейно-контактная схема реализует задание своими равновесными состояниями. Однако, не вводя понятий конечного автомата и последовательностной машины, Хафман, естественно, не мог сказать, что по существу метод его состоит в пострбёнии П-Машины, работающей в быстрой тактности, которая реализует устойчивыми состояниями заданную П-машину, работающую в медленной тактности, определяемой сменой состояний входа.
Используя понятия конечного автомата, последовательностной машины и преобразования тактности, мы изложим метод Хафмана на этой основе. Будем считать исходными данными для проектирования релейной схемы таблицу автомата и выходного преобразователя реализуемой последовательностной машины. Кроме того, излагая метод Хафмана, мы будем иллюстрировать его на каждом этапе соответствующим преобразованием схемы П-машины.
Пусть задана П-машина, т. е. две таблицы: основная таблица конечного автомата и таблица выходного преобразователя. Тактность работы автомата определяется моментами смены состояний входа. Требуется построить релейную схему, которая на устойчивых состояниях, по принципу, изложенному в § 5.3, реализовала бы заданную П-машину.
Решение этой задачи методом Хафмана дается на одном простом примере, однако из дальнейшего изложения будет ясно, что метод является общим и совершенно аналогично применяется в любом другом случае.
