Материал: Ковригин Теория автоматов Лабораторный практикум 2012

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

DATA

Рис. 5.1. Условное графическое обозначение автомата проверки делимости на K

В случае если число K представимо в виде K = k1×k2×…×km, где ki – взаимно простые числа, то можно минимизировать количество состояний ДКА (D), разбив его на m отдельных ДКА (D1,…Dm), которые проверяют число N на делимость на ki, и комбинационную схему с m входами и одним выходом, реализующую логическую функцию И, на вход которой подаются выходы с Di. При этом суммарное количество состояний будет равно k1+k2+…+km, а количество переходов между состояниями не превышает M×(k1+k2+…+km), что, в общем случае, значительно меньше, чем количество состояний и переходов между ними в исходном конечном автомате (k1×k2×…×km и M×( k1×k2×…×km) соответственно). Например, для числа K=42 схема проверки делимости будет выглядеть так, как представлена на рис. 5.2. При этом суммарное количество состояний автоматов будет равно 12 = 7 + 3 + 2 вместо 42.

57

В случае если число K представимо как K= k1×k2×…×km, где k1 = k2 = … = km, то для сокращения числа состояний конечного автомата можно воспользоваться следующим приемом: преобразовать конечный автомат в устройство, которое, помимо результата проверки делимости, возвращает и результат деления; соединить устройства последовательно, при этом сигнал корректности данных и результат делимости должны передаваться на очередной этап обработки с задержкой в один такт (задержка реализуется при помощи D-триггеров). На рис. 5.3 представлена схема проверки делимости числа на 25: результат целочисленного деления первой ступени в виде последовательного кода (выход DNEXT) подается на вход второго автомата.

Отметим, что количество состояний автомата для устройств, формирующих и не формирующих результат деления, одинаково;

58

результат деления формируется при выполнении переходов, т.е. зависит не только от текущего состояния, но и от предыдущего. Следовательно, при проектировании данного устройства, вопервых, надо описать дополнительно M×K условий формирования сигнала, т.е. возрастает сложность проектирования. Во-вторых, результат нужно сохранить в буферных регистрах (опция Registered, при указании типа выхода в FSM Editor), т.е. в данном автомате необходим один дополнительный элемент памяти.

R

Рис. 5.3. Схема проверки делимости числа на 25

В случае если один из компонентов, на которые раскладывается K, является основанием системы счисления, в которой представлены числа (либо является степенью основания системы счисления), то целесообразно использовать внедрение проверки на делимость на этот компонент в принимающее состояние одного из ДКА для компонента разложения K на взаимно простые сомножители. В этом случае суммарное количество состояний автомата уменьшается на kM logM(kM), где kM – член разложения K на простые сомножители, являющийся степенью M. В этом случае, например, схема проверки делимости на 42 будет содержать 11 = 7 + (3 + 1) состояний вместо 42. Данная схема представлена на рис. 5.4.

59

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

Рис. 5.4. Схема проверки делимости числа на 42 (оптимизированный вариант)

Пример

Постановка задачи. Спроектировать устройство, определяющее, делится ли нацело на 36 двоичный код большой размерности, поступающий последовательно со старших разрядов (число 0 также принимается устройством).

60