Синтез схемы двоичного сумматора по модулю 4 с использованием алгоритмов декомпозиции
Рассмотрим реализацию алгоритмов многоуровневой декомпозиции на примере синтеза схемы двоичного сумматора по модулю 4. Синтезируемая схема имеет пять входов и три выхода (рис. 2.16).
Рис. 2.16
Сложность исходной схемы
Абстрактный синтез. В процессе решения задачи абстрактного синтеза построим числовую последовательность синтезируемой схемы. Допустим
Числовая (логическая) последовательность синтезируемого сумматора имеет вид строки, состоящей из 32-х элементов
Структурный синтез
Так как схема имеет три выхода, попытаемся выделить параллельный блок. Для этого проверим наличие существенной или фиктивной зависимости выходных функций сумматора от входных аргументов. Присвоим входным переменным весовые коэффициенты, равные степени 2 (рис. 2.16) и построим матрицы разложения числовой последовательности синтезируемого сумматора по всем входным переменным (см. разд. 2.2.3):
Результаты проверки заносятся в специальную таблицу, строки которой отмечены именами выходов, а столбцы – весами входных переменных (табл. 2.3).
Таблица 2.3
Заполнение каждого из столбцов указанной таблицы производится по следующему алгоритму: 1) для построенной выше матрицы разложения по старшей входной переменной ( 2) операция суммирования выполняется над элементами второго столбца матрицы разложения, и полученная сумма объединяется по «ИЛИ» с уже записанным в соответствующий столбец таблицы числом; 3) процедура повторяется для всех последующих столбцов матрицы разложения до тех пор, пока не окажутся заполненными единицами все строки рассматриваемого столбца таблицы; 4) пункты 1 – 3 повторяются для всех остальных матриц разложения и таким же образом заполняются оставшиеся столбцы таблицы. Если после просмотра всех столбцов всех матриц разложения в какой-либо строке таблицы остался символ «0», то это означает, что соответствующий выход зависит фиктивно от рассматриваемой входной переменной. Построенная таким образом таблица позволяет выбрать группу выходов устройства, которые зависят не от всех входов. В рассматриваемом примере выход Схема, получаемая в результате параллельной декомпозиции синтезируемого устройства, представлена на рис. 2.17.
Рис. 2.17 Для определения числовой последовательности блока 2 из последовательности устройства (2.16) сначала выделяется двоичная последовательность младшего выхода
А затем из неё исключаются фиктивные переменные, для чего необходимо построить матрицу разложения по соответствующим входным переменным (см. разд. 2.2.8):
В матрице (2.17) содержатся четыре одинаковые строки, что ещё раз подтверждает фиктивную зависимость числовой последовательности Числовая последовательность блока 1, выходы которого существенно зависят от всех входных переменных, получается из исходной числовой последовательности путём исключения двоичной последовательности, соответствующей выходам второго блока. Для этого необходимо каждый элемент последовательности (2.16) разделить на два и взять целую часть от деления:
Сложность схемы после разделения будет составлять
Далее, в соответствии с приведённым выше алгоритмом структурного синтеза КЛС, из блока 1 попытаемся выделить последовательный блок с теми же входами, которые относятся к блоку 2. Для этого необходимо числовую последовательность блока 1 разложить в матрицу по входным переменным
По вертикали в матрице (2.18) изменяют свои значения выделенные входные переменные, относящиеся к старшему блоку (блок 3 на рис. 2.18), а по горизонтали – те переменные, которые не вошли в старший блок. Если два каких-либо набора значений входных переменных старшего блока неразличимы, то они неразличимы при любых значениях, не вошедших в этот блок переменных. Поэтому неразличимые комбинации переменных старшего блока будут давать в матрице одинаковые строки. В матрице (2.18) две различных строки из восьми, поэтому из блока 1 можно выделить последовательный блок 3 с тремя входами и одним выходом (рис. 2.18).
Рис. 2.18 Сложность схемы после разделения:
Для определения последовательности блока 3 следует закодировать строки матрицы (3) по элементам первого столбца – Для определения последовательности блока 4 строится сокращённая матрица разложения, которая образуется путём исключения из матрицы (2.18) повторяющихся строк: Последовательность блока 4 получается развёртыванием по столбцам сокращённой матрицы разложения – Объединим параллельный блок 2 с последовательным блоком 3, поскольку эти блоки зависят от одних и тех же входных переменных. Выход последовательного блока будем считать старшим, поэтому при выполнении указанной операции необходимо каждый элемент последовательности блока 3 умножить на два и прибавить к результату соответствующий элемент параллельного блока 2 –
Рис. 2.19
Оба блока на рис. 2.19 имеют одинаковые последовательности ( Дальнейший процесс декомпозиции целесообразно рассматривать для одного из блоков, поскольку они характеризуются одинаковыми числовыми последовательностями. Для входов двоичного сумматора необходимо ввести новые обозначения, совпадающие с их весовыми коэффициентами – Для оценки возможности проведения параллельной декомпозиции построим матрицы разложения числовой последовательности двоичного сумматора по каждой входной переменной:
По построенным матрицам заполняется табл. 2.4, которая свидетельствует о существенной зависимости выходов двоичного сумматора от всех его входов.
Таблица 2.4
Для оценки возможности проведения последовательной декомпозиции строятся матрицы разложения числовой последовательности двоичного сумматора по всем возможным парам входных переменных: В матрицах разложения по три различимых строки из четырёх, и поэтому из двоичного сумматора нельзя выделить последовательный блок. На этом этап декомпозиции двоичного сумматора по модулю 4 заканчивается, поскольку дальнейшее разделение синтезируемой схемы с учётом критерия уменьшения сложности невозможно. Результирующая схема рассматриваемого комбинационного устройства представлена на рис. 2.20.
Рис. 2.20. Схема двоичного сумматора по модулю 4
Анализ синтезированной схемы
Чтобы убедиться в правильности результатов синтеза, а также в качестве примера проанализируем блок-схему двухразрядного двоичного сумматора, представленную на рис. 2.20. Каждый разряд двоичного сумматора характеризуется следующей собственной числовой последовательностью:
К первому ярусу относится блок номер 1. На его входы поступают переменные
С помощью двоичной матрицы (2.20) и собственной числовой последовательности блока 1 (2.19) построим реализуемую им числовую последовательность. Первый столбец двоичной матрицы (2.20) даёт нулевое значение индекса
Удобно реализуемую блоком числовую последовательность строить прямо под двоичной матрицей входных последовательностей, отделив её чертой: На старшие (верхние) входы блока 2-го яруса поступают входные переменные Выпишем одна под другой входные последовательности, поступающие не входы второго блока и определим состояния выходов в соответствии с его собственной числовой последовательностью – Два старших выхода анализируемого устройства связаны с выходами блока 2, а младший выход устройства – с выходом блока 1. Поэтому, результирующая последовательность исследуемой схемы получается в результате объединения последовательности Полученная в результате анализа выходная последовательность полностью совпадает с исходной логической последовательностью, что доказывает правильность функционирования представленной на рис. 2.20 схемы.
Популярное: Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... ![]() ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1170)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |