12.8. СТРУКТУРНЫЙ СИНТЕЗ ЭКОНОМИЧНЫХ СХЕМ АВТОМАТОВ С ПАМЯТЬЮ

Сложность реализации комбинационных схем автомата с памятью во многом определяется способом кодирования его состояний. Дадим ряд рекомендаций, связанных с выбором такого варианта кодирования состояний автомата, который обеспечивает получение экономичных по сложности реализации его комбинационных схем. Излагаемый материал ориентирован на использование О-триггеров в качестве элементов памяти автомата, однако легко может быть модифицирован и на применение элементов памяти других типов. Все операции будут проводиться над таблицей кодирования состояний автомата и таблицей его функций возбуждения. Однако эти таблицы представляются несколько иначе. В традиционном представлении таблицы кодирования состояний автомата (табл. 12.3) считается, что каждому состоянию абстрактного автомата ставится в соответствие некоторый двоичный вектор. Применительно к табл. 12.3 состоянию поставлен в

Таблица 12.22

соответствие вектор 00, состоянию — вектор и состоянию — вектор 10. Однако таблицу кодирования можно рассматривать не по строкам, а по столбцам. Обозначим каждый столбец таблицы кодирования состояний автомата (табл. 12.3) буквами (табл. 12.22). Тогда таблица кодирования состояний автомата может быть представлена совокупностью разбиений:

Состояния автомата и соответствующие нулям столбца объединяются в один блок, отмечаемый чертой разбиения а состояния (в данном случае — состояние соответствующие единицам столбца объединяются во второй блок разбиения Аналогично для разбиения Очевидно, некоторый вариант кодирования состояний автомата определяется совокупностью -разбиений, а экономичная реализация комбинационной схемы возбуждения автомата зависит от выбора этой совокупности.

Метод r-разбиений

Утверждение. Двухблочное -разбиение допустимо для кодирования состояний автомата, если мощность любого блока -разбиения не превышает величины где к — число элементов памяти, используемых для синтеза автомата на структурном уровне.

Пусть и автомат имеет восемь состояний, обозначенных для удобства изложения цифрами: . Тогда Иными словами, максимальная мощность любого из двух блоков разбиения (максимальное число состояний автомата в блоке) не должна превышать числа 4. Действительно, пусть Тогда, в соответствии с этим разбиением получаем следующую таблицу кодирования состояний автомата (табл, 12.23).

Какие бы разбиения для кодирования состояний автомата не выбирались, всегда будет иметь место ситуации, когда два различных состояния автомата будут закодированы одинаковыми двоичными векторами. Действительно, пять состояний автомата: 3, 4, 5, 6, 7 нужно закодировать различными двухразрядными векторами (по разбиениям что невозможно, так как имеется только четыре различных двухразрядных вектора: 00, 01, 10, 11. Следовательно, выбранное разбиение недопустимо для кодирования состояний автомата. В общем случае, если для синтеза автомата требуется использовать элементов памяти — минимально возможное число элементов памяти) и выбрано некоторое у-разбиение для кодирования состояний автомата, то различных -разрядных двоичных векторов для кодирования состояний автомата по оставшимся столбцам таблицы кодирования может быть получено не более чем Следовательно, для образования допустимого варианта кодирования состояний автомата

Таблица 12.28

Таблица 12.24

необходимо выполнение утверждения по отношению к разбиению

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

Разбиения недопустимы, так как содержат только один блок, мощность которого больше четырех:

Разбиения можно исключить при составлении варианта кодирования состояний автомата, так как повторяют разбиения соответственно. Следовательно, допустимыми -разбиениями являются разбиения

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

Пусть задана совокупность -разбиений:

Заданная совокупность разбиений не является допустимой, тая как блок 174 является общим для всех трех разбиений. Следовательно, такая совокупность не дает вариант кодирования состояний автомата.

Действительно, в соответствии с приведенной совокупностью, получаем вариант кодирования (табл. 12.25), в котором состояния автомата 1 и 4 кодируются одинаково, что недопустимо. Допустимые совокупности -разбиений определяют возможные варианты кодирования состояний томата. Каждый вариант кодирования позволяет реализовать комбинационную схему автомата с определенной сложностью.

Таблица 12.25

Из всех возможных реализаций оптимальной является та, которая приводит к минимальным аппаратурным затратам на реализацию структурной схемы автомата. Таким образом, метод -разбиений позволяет сократить перебор возможных вариантов кодирования состояний автомата за счет получения допустимых совокупностей -разбиений. Для каждой из допустимых совокупностей -разбиений строится структурная схема автомата. Схема автомата, реализованная с минимальными аппаратурными затратами, выбирается как окончательный вариант структурного синтеза автомата. Так, для автомата с пятью различными состояниями (без учета метода -разбиений) существует 6720 различных вариантов кодирования состояний. Применение метода -разбиений позволяет рассматривать только 140 вариантов кодирования состояния автомата. Метод -разбиений на практике в чистом виде не используется из-за сохранения достаточно большого перебора при выборе оптимальной структурной схемы автомата. Однако метод -разбиений является вспомогательным средством для более эффективного метода — метода -разбиений.

Метод П-разбиений

Суть метода -разбиений сводится к следующему: по -разбиениям находят специальные -разбиения, структура которых определяет сложность реализации комбинационной схемы возбуждения автомата о памятью. Применяя специальный алгоритм, выбирают совокупность -разбиений, удовлетворяющую требованиям минимума аппаратурных затрат на реализацию структурной схемы автомата. По выбранной совокупности -разбиений однозначно восстанавливают допустимую совокупность -разбиений, определяющую оптимальный вариант кодирования состояний синтезируемого автомата. Работу метода -разбиений рассмотрим на конкретном примере. Пусть задана таблица переходов автомата с памятью (табл. 12.26). Найдем оптимальный вариант кодирования состояний автомата с помощью метода -разбиений. В качестве элементов памяти автомата будем использовать D-триггеры.

Метод -разбиений реализуется следующим алгоритмом:

1. Выписать все допустимые -разбиения. Так автомат имеет

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

2. Для каждого -разбиения по таблице переходов автомата построить ягразбиение. Для этого состояниям автомата из первого блока Ггразбиения приписать значение — ноль, а состояниям автомата из второго блока -разбиения — значение — единица. Заменить состояния автомата, расположенные внутри таблицы переходов, на нули и единицы в соответствии с Все состояния автомата, которым соответствуют одинаковые строки преобразованной таблицы переходов, объединить в один блок разбиения

Рассмотрим разбиение Состояниям автомата из первого блока разбиения припишем 0, состояниям автомата из второго блока припишем значение — единица. Преобразуем таблицу переходов автомата в соответствии с заменой (табл. 12.27).

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

Таблица 12.26

Таблица 12.27

Таблица 12.28

автомата будем называть структурной таблицей переходов автомата по элементу памяти. Так как в качестве элементов памяти используются D-триггеры (структурная таблица переходов автомата совпадает с таблицей функций возбуждения), то получаемая структурная таблица переходов автомата по элементу памяти является таблицей функции возбуждения элемента памяти. Поэтому структура -разбиения определяет сложность реализации функции воз! буждения элемента памяти автомата (о чем будет сказано ниже).

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

Действительно, так как разбиение одноблочно, то в структурной таблице переходов автомата по первому элементу памяти (для рассматриваемого в примере автомата с двумя входными сигналами) могут быть либо только строки вида 00, либо либо 10, либо 11. Соответственно и функция возбуждения первого элемента памяти будет иметь вид:

т. е. зависеть только от входных сигналов автомата. В рассматриваемом примере такая пара разбиений имеется: После кодирования состояний автомата по первому элементу памяти в соответствии с -разбиением, получаем следующую структурную таблицу переходов автомата (табл. 12.28). Иными словами, функция возбуждения первого элемента памяти имеет вид Если где — одноблочно, несколько, то для кодирования состояний автомата целесообразно использовать все входящие в такие пары При этом следует помнить, что число разбиений гима должно быть равно а образуемая совокупность -разбиений должна быть допустимой В рассматриваемом примере другие пары с одноблочным -разбиением отсутствуют

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

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

5. Проверить наличие пары где Если такая пара разбиений есть, то кодирование состояний автомата по второму элементу

«памяти осуществить в соответствии с разбиением В этом случае функция возбуждения второго элемента памяти автомата будет зависеть от входных сигналов автомата и второго элемента памяти.

В нашем примере такие пары разбиений отсутствуют.

6. Будем искать варианты кодирования состояний автомата, при которых функция возбуждения второго элемента памяти зависит от входных сигналов и третьего элемента памяти. Для этого следует выбрать пару где — двухблочно. Если такая пара разбиений есть, то кодирование состояний автомата по второму элементу памяти осуществить в соответствии с разбиением а по третьему элементу памяти в соответствии с разбиением . В этом случае функция возбуждения второго элемента памяти будет зависеть от входных сигналов и третьего элемента памяти. Но такое кодирование может быть неоднозначным. Для нахождения всех вариантов однозначного кодирования выпишем пары , где разбиение — двухблочно.

Для рассматриваемого примера имеем следующие пары разбиений!

Определим допустимые совокупности пар разбиений Если для кодирования состояний автомата по двум элементам памяти выбрана пара разбиений а общее число элементов памяти автомата равно к, то различных (к — -разрядных двоичных векторов для кодирования состояний автомата по оставшимся столбцам таблицы кодирования может быть получено не более чем Следовательно, максимальная мощность блока, являющегося общим для пары разбиений не должна превышать

Нахождение всех таких блоков связано о понятием произведения разбиений.

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

Введя понятие произведения разбиений, легко определить допустимую совокупность пар разбиений . Очевидно, максимальная мощность блока разбиения, являющегося произведением разбиений не должна превышать Для рассматриваемого случая имеем . Найдем все произведения вида

Очевидно, допустимыми являются только пары разбиений»

В результате получаем три варианта кодирования:

Полученные совокупности разбиений необходимо проверить на до» пустимость Для этого достаточно взять произведение всех разбиений рассматриваемой совокупности Максимальная мощность любого блока из такого произведения должна быть равна единице. Имеем

В результате получаем, что второй вариант недопустим для кодирования состояний автомата.

Таблица кодирования состояний автомата по первому варианту представлена табл. 12.29, а по третьему варианту — табл 12 30 Функции возбуждения автомата (по первому варианту кодирования) представляются уравнениями

Таблица 12.29

Таблица 12.30

а по третьему варианту кодирования — уравнениями

Метод нормальных разбиений

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

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

Пусть граф переходов автомата имеет вид (рис. 12.26). Для простоты рассмотрим автомат без выходов. На графе переходов существует -разбиение вида где — блоки -разбиения. В существовании последнего можно легко убедиться, проверив выполнение определения -разбиения к полученному разбиению.

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

1. Нумерацию строк треугольной таблицы начать с состояния 2 и окончить состоянием Нумерацию столбцов треугольной таблицы начать с состояния 1 покончить состоянием клетка треугольной таблицы образуется на пересечении строки и столбца таблицы.

2. В клетке треугольной таблицы записать пары состояний автомата, которые являются результатом его перехода:

Рис. 12.26

Рис. 12.27

а) из состояния I в состояние под воздействием входного сигнала

б) из состояния в состояние под воздействием входного сигнала

Пары состояний вида в клетку треугольной таблицы не заносить.

Пример. Треугольная таблица переходов автомата (рис. 12.26) представлена рис. 12.27.

-разбиение по треугольной таблице находится с помощью следующего алгоритма:

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

Для примера возьмем пару состояний автомата (1,3) и отнесем ее в блок образуемого разбиения

2. Если в клетке треугольной таблицы есть пары (I, А); либо то укрупнить блок разбиения преобразовав его в блок либо в блок Если в клетке треугольной таблицы нет пар состояний автомата, содержащих в качестве элемента пары состояние либо состояние то образовать новый блок разбиения

Для примера в клетке (1,3) треугольной таблицы стоят пары и (1,2). Следовательно, блок укрупняется и принимает вид , при этом образуется блок та

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

Для примера указанная процедура иллюстрируется рис. 12.28. Таким образом, имеем

4. Процесс формирования блоков -разбиения прекратить, когда число состояний в одном из блоков будет равно: — число элементов памяти автомата). Если , то вычеркнуть клетку треугольной таблицы и все клетки, содержащие пары состояний так как они не могут быть объединены в один блок разбиения

5. Если в результате вычеркивания окажутся зачеркнутыми все клетки треугольной таблицы, соответствующие строке и

Рис. 12.28.

Рис. 12.29

Таблица 12.31

Таблица 12.32

столбцу, то процесс нахождения разбиения заканчивается. Это значит, что состояние I автомата не может входить в один блок разбиения ни с каким другим состоянием. Иными словами, отсутствует.

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

7. Разбиения не обязательно будут двухблочными. Для получения двухблочного разбиения нужно объединить блоки полученного нормального разбиения так, чтобы при объединении в один блок не попали состояния, соответствующие перечеркнутым клеткам треугольной таблицы, а мощность блока -разбиения была бы 2/2. Пусть автомат задан таблицей переходов (табл. 12.31). Найдем оптимальный вариант кодирования его состояний с помощью -разбиений.

Треугольная таблица переходов автомата представлена на рис. 12.29. После применения алгоритма получим два нормальных разбиения: Полученная совокупность разбиений является допустимой, так как Поэтому кодирование состояний автомата по первым двум элементам памяти осуществляется с помощью разбиений а по третьему элементу памяти — произвольно. Таблица кодирования состояний автомата представлена в табл. 12.32. После проведения структурного синтеза имеем следующие уравнения для функций возбуждения элементов памяти автомата)