Декомпозиция комбинационных логических схем

 

2.4.1. Оценка сложности синтезируемой схемы.

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

(бит),

где – количество входов, а – количество выходов КЛС (рис. 2.1).

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

(бит).

Для рассмотренного выше двоичного сумматора (рис. 2.2) сложность схемы равна 16 бит ( ).

 

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

 

Структурная схема комбинационного устройства, получаемая в результате параллельной декомпозиции, представлена на рис. 2.3.

 

 

Рис. 2.3. Параллельная декомпозиция логических блоков

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

Исходная сложность КЛС равна

(бит). (2.9)

После разделения на два блока сложность схемы составляет

(бит).

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

Доказательство. Чтобы сложность схемы после разделения уменьшилась, должно выполняться неравенство (2.10):

. (2.10)

После несложных преобразований неравенство (2.10) может быть записано в виде (2.11):

. (2.11)

Поскольку неравенство (2.11) может быть преобразовано к виду (2.12):

. (2.12)

Из выражения (2.12) следует, что для обеспечения уменьшения сложности схемы в результате параллельной декомпозиции должно быть меньше . В этом случае целесообразно выделение параллельного блока. Это означает, что выходов схемы зависят фиктивно от входов.

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

Указанную проверку удобно делать с помощью поочерёдного разложения логической последовательности в матрицу по каждой из входных переменных (см. разделы 2.2.3 и 2.2.6). В полученной таким образом матрице содержатся две строки. Далее элементы первого столбца поразрядно (в двоичном представлении) суммируются по модулю два и полученное число заносится в столбец таблицы, соответствующий переменной, по которой проводилось разложение. Единичные разряды полученного числа отмечают те выходы, которые существенно зависят от рассматриваемого входа. Затем операция суммирования выполняется над элементами второго столбца, и полученная сумма объединяется по «ИЛИ» с уже записанным в столбец таблицы числом.

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

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

Для определения числовой последовательности блока из числовой последовательности устройства сначала выделяются двоичные последовательности выделенных выходов, объединяются, если их несколько, и из полученной таким образом числовой последовательности исключаются фиктивные переменные (см. разделы 2.2.6, 2.2.9 и 2.2.10). Числовая последовательность первого из параллельных блоков, выходы которого существенно зависят от всех входов, получается из исходной числовой последовательности путём исключения двоичных последовательностей, соответствующих выходам второго блока.

Учитывая то, что при параллельной декомпозиции , можно сформулировать лемму 2.1.

Лемма 2.1.При параллельной декомпозиции сложность описания схемы всегда уменьшается.

В качестве примера исследуем зависимость выходных сигналов для КЛС с числовой последовательностью (рис. 2.4):

 

 

Рис. 2.4

Построим матрицы разложения числовой последовательности рассматриваемого блока по каждой из входных переменных:

; ; .

Результаты проверки зависимости выходов от входов приведены в таблице 2.2.

Таблица 2.2

Таблица зависимости выходов схемы от её входов

 

В результате анализа указанной таблицы можно сделать вывод о том, что выход фиктивно зависит от входной переменной .

Структурная схема, полученная в результате декомпозиции рассматриваемого устройства, представлена на рис. 2.5.

 

 

Рис. 2.5

Для определения логической последовательности блока 1 (рис. 2.5) необходимо с помощью выполнения операции разделения числовой последовательности на старшую (выход ) и младшую (выход ) составляющие из исходной последовательности выделить выход , зависящий от всех входных переменных. Количество элементов в последовательности блока 1 будет равно исходному количеству элементов, поскольку выходы этого блока зависят от всех входных переменных существенно:

.

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

.

 

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

 

При последовательной декомпозиции выходы одного блока являются входами другого и схема может быть представлена в виде рис. 2.6, соответствующего -кратной разделительной декомпозиции системы логических функций, описывающих рассматриваемое комбинационное устройство. Первый из последовательных блоков (блок 1) будем считать старшим, а второй (блок 2) – младшим, поскольку старший управляет работой младшего.

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

Сложность схемы после разделения определяется соотношением (2.13):

(2.13)

 

Рис.2.6. Последовательная декомпозиция

После некоторых преобразований соотношение (2.13) может быть записано в виде (2.14):

. (2.14)

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

,

которое справедливо при

. (2.15)

Утверждение 2.4.Выделение последовательного блока будем считать целесообразным, если число различимых комбинаций входных переменных, по крайней мере, вдвое меньше общего числа всех комбинаций этих же переменных.

Доказательство. Выполнение неравенства (2.15) свидетельствует о том, что число состояний на выходе старшего (первого) блока, равное , хотя бы в два раза меньше, чем количество состояний на его входах, равное . Это говорит о том, что среди всевозможных комбинаций состояний входных переменных старшего блока есть такие наборы, которые порождают одну и ту же комбинацию выходных сигналов. Такие комбинации входных переменных будем называть неразличимыми блоком 1 (в противном случае – различимые комбинации). Очевидно, что если какие-либо наборы неразличимы блоком 1, то они неразличимы и всем комбинационным устройством.

Соотношение (2.15) является необходимым, но недостаточным условием уменьшения сложности при последовательной декомпозиции комбинационного устройства. Достаточным условием является выполнение соотношения (2.14). В общем случае неравенство (2.14) может быть нестрогим. И в случае равенства разделение схемы на последовательные блоки также является целесообразным, поскольку сложность каждого из полученных при декомпозиции блоков меньше исходной сложности схемы.

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

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

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

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

Процедуру последовательной декомпозиции можно проиллюстрировать на примере синтеза логической схемы с последовательностью

.

Структурная схема синтезируемого устройства представлена на рис. 2.7.

 

 

Рис. 2.7

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

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

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

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

 

 

Рис. 2.8

 

Для определения собственной числовой последовательности старшего (выделенного) блока 1 необходимо закодировать, начиная с нуля, двоичными символами строки указанной матрицы. При этом, одинаковым строкам сопоставляются во взаимнооднозначное соответствие одинаковые числа. Прочитав указанные числа сверху вниз, мы получим искомую последовательность выделенного блока – .

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

Таким образом, у младшего блока 2 осталось три входа. Введём для них новые обозначения – , и (рис 2.8). Такое разделение целесообразно, поскольку сложность схемы с 16 бит сократилась в результате декомпозиции до 12 бит.

Для определения логической последовательности младшего блока 2 из матрицы разложения, определяющей выделенный блок, необходимо получить сокращённую матрицу, в которой остаются только различные строки. Далее полученная матрица разворачивается по столбцам, поскольку она соответствует разложению последовательности младшего блока по входной переменной с весом , являющейся выходом старшего блока 1:

.

Логическую последовательность младшего блока – .

В общем случае в сокращённой матрице должно остаться строк, где – количество выходов старшего блока при последовательной декомпозиции. Если количество строк не кратно степени 2, то в сокращённую матрицу добавляются строки, состоящие из символов «звёздочка» (*).

Далее проведём разделение младшего блока 2, для чего построим матрицу разложения его последовательности по входным переменным :

Содержащиеся в полученной матрице две различные строки говорят о возможности проведения последовательной декомпозиции. Логическая последовательность старшего блока 3 определяется кодированием строк матрицы – . Сокращённая матрица имеет следующий вид:

.

Разворачиваем её по столбцам и получаем последовательность младшего блока 4 – . Результат декомпозиции блока 2 представлен на рис 2.9.

 

 

Рис. 2.9

Сложность схемы на этом этапе не изменилась, однако полученные в результате декомпозиции блоки 3 и 4 являются более простыми, по сравнению с исходным блоком 2.

Общая схема рассматриваемого комбинационного устройства представлена на рис. 2.10. Для удобства проведения в дальнейшем анализа синтезированной схемы блоки получили буквенные обозначения: блок 1 – , блок 3 – , блок 4 – .

 

 

Рис. 2.10

 

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

Пример синтеза рассматриваемой схемы классическим методом (с использованием карты Карно) приведен на рис. 2.11.

 

 

Рис. 2.11

 

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

.

Реализация указанной функции в базисе «И», «ИЛИ», «НЕ» представлена на рис. 2.12:

 

 

Рис. 2.12

 

Сложность схемы на рис. 2.12 составляет 16 бит. Если выполнить некоторые алгебраические преобразования ( ), то эту схему можно свести к виду, изображённому на рис. 2.10.

 

2.4.4. Параллельно-последовательная декомпозиция комбинационных устройств.

Используя рассмотренные выше алгоритмы параллельной и последовательной декомпозиции, из исходной схемы можно выделить блоки 1 и 2, зависящие от одних и тех же входных переменных (рис. 2.13).

 

Рис. 2.13. Параллельно-последовательная декомпозиция

 

Два выделенных блока целесообразно объединить в один параллельно-последовательный блок, поскольку сложность схемы при этом не увеличится, а количество блоков сократится (рис. 2.14).

 

 

Рис. 2.14. Объединение блоков при параллельно-последовательной декомпозиции

 

В общем случае число входов выделенных параллельного (1) и последовательного (2) блоков (рис. 2.13) может быть различным. Тогда в один из блоков добавляются фиктивные переменные для выравнивания количества входов. В качестве примера на рис. 2.15 представлена блок-схема комбинационного устройства, у которого последовательный блок 1 зависел до объединения от входов, а параллельный блок 2 – от ( ) входов. При объединении в последовательный блок 1 было добавлено фиктивных переменных.

 

 

Рис. 2.15. Объединение блоков при параллельно-последовательной декомпозиции с добавлением фиктивных переменных

 

2.4.5. Алгоритм декомпозиции логических схем.

 

1 этап. Выделение параллельного блока.

Процедура выделения параллельного блока из комбинационного устройства менее трудоёмка по сравнению с процедурой выделения последовательного блока. При параллельной декомпозиции производятся всевозможные разложения числовой последовательности комбинационного устройства по одному аргументу. Матриц разложения по одному из аргументов будет гораздо меньше, чем в случае разложения сразу по нескольким аргументам, которые приходится строить при выделении последовательного блока. Кроме того, сами матрицы разложения по группам переменных строятся сложнее. Поэтому начинать декомпозицию целесообразно с выделения из устройства параллельных блоков.

Кроме того, как было доказано выше (см. раздел 2.4.2), при параллельной декомпозиции всегда уменьшается сложность описания схемы. Уменьшив, таким образом, сложность синтезируемого устройства, мы тем самым облегчаем задачу последовательной декомпозиции.

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

3 этап. Объединение выделенных параллельного и последовательного блоков. При этом сложность схемы не изменится, а число блоков уменьшится. При необходимости уравнивается число входов параллельного и последовательного блоков путем добавления к одному из блоков фиктивных переменных (см. раздел 2.4.4).

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

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