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

И.В. Коновалов,
аспир., ivan-k85@mail.ru,
ИПУ РАН, г. Москва,
В.Н. Коновалов,
ст. препод., v.konovalov@list.ru
КФ МГТУ им. Н.Э. Баумана, г. Калуга

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

 

A method of combinational circuit implementation is considered. Method allows representing combinational circuit as interconnection of combinational device and output decoder. This implementation provides parallel decomposition of both blocks with following reduction of overall circuit complexity.

 

Одним из основных этапов логического проектирования комбинационных устройств является этап декомпозиции, в процессе которого производится разделение сложной схемы на более простые части. Декомпозиционные методы позволяют получать многоуровневые представления логических функций и являются наиболее общими методами логического синтеза цифровых схем [1 – 3].

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

рис. 1. Структурная схема синтезируемого устройства

Числовые последовательности блоков КУ1 и КП строятся таким образом, чтобы не нарушалась последовательность, заданная для исходного КУ. Если на входное воздействие i КУ должно давать отклик j, то необходимо потребовать, чтобы КУ1 в ответ на воздействие i давало некоторый отклик k, а кодопреобразователь КП в ответ на воздействие k давал отклик j.

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

Рассмотрим процедуру кодирования состояний выхода КУ. Состояния кодируются m-разрядными двоичными кодовыми комбинациями. Чтобы это было возможно, число различных состояний не должно превышать 2m. Будем иметь в виду однозначное кодирование, когда каждому состоянию выхода КУ1 однозначно соответствует состояние выхода КУ и наоборот. Каждый двоичный разряд m-разрядного кода разделяет множество состояний выхода КУ1, а следовательно и КУ, на два подмножества, в каждом из которых содержится не более 2m-1 элементов. На одном из этих подмножеств выбранный разряд кода имеет значение 0, а на втором – 1.

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

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

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

Во-вторых, это может быть пара «число-звездочка». Звездочку можно заменить любым числом и этот случай свести к предыдущему.

В-третьих, это быть пара «звездочка-звездочка». Ее можно не выписывать, так как она может быть отождествлена с любой другой парой, уже выписанной. Может быть пара «число-число», причем, числа различные. Такую пару нужно выписать, если она уже не выписана раньше.

Пусть мы имеем пересекающиеся пары (a,b) и (b,c). Тогда, очевидно, что все три числа a, b и c должны иметь одинаковые значения кодов в рассматриваемом разряде. То же самое относится и к случаю, когда мы имеем не две, а несколько попарно пересекающихся пар, например, (a,b), (b,c), (c,d) и так далее. Множество попарно пересекающихся пар объединяется в связанное подмножество чисел. Все эти числа в рассматриваемом разряде кода должны иметь одинаковые значения.

Итак, после объединения связанных пар чисел мы имеем множество замкнутых связанных подмножеств чисел. Может оказаться, что какое-то одно из этих подмножеств включает в себя более 2m-1 чисел. В этом случае при однозначном кодировании m-разрядными кодовыми комбинациями выполнить требование фиктивной зависимости выбранного разряда кода от переменной с весом p невозможно. Если мы имеем более двух связанных: подмножеств чисел, каждое из которых содержит не более чем 2m-1 чисел, то нужно объединить эти связанные подмножества в два подмножества, содержащие не более 2m-1 элементов. Числа одного из этих подмножеств кодируются нулем в рассматриваемом разряде, а другого – единицей.

Замкнутые связанные подмножества чисел нужно найти для каждого p от 1 до 2n-1. При объединении связанных подмножеств в два подмножества можно иногда выполнить требования фиктивной зависимости рассматриваемого разряда кода сразу от нескольких входных переменных.

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

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

Кодирующая таблица позволяет построить числовую последовательность КУ1. При этом, вместо чисел в числовой последовательности КУ ставятся соответствующие кодовые комбинации, записанные в какой-то удобной для нас системе счисления. Используя кодирующую таблицу, как таблицу вход-выход, мы можем построить числовую последовательность кодопреобразователя КП.

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

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

0011  2566  77**  ****.                                                                                   (1)

Попытаемся уменьшить зависимость выходов от входов с помощью разделения схемы на два блока – КУ1 и КП.

Числовую последовательность (1) разложим по переменной с весом 1 [5]:

.

Из построенной матрицы найдём связанные пары чисел.

1   –   (0), (1), (2,5), (6), (7).                                                                           (2)

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

Последовательность (1) разложим по переменной с весом 2:

.

Выпишем множество пар связанных состояний выхода.

2   –   (0,1), (2,6), (5,6), (7).

Объединив пересекающиеся пары, получим:

2   –   (0,1), (2,5,6), (7).                                                                                 (3)

Далее разложим числовую последовательность проектируемого комбинационного устройства КУ по переменной с весом 4:

.

Отсюда получим множество пар связанных состояний выхода.

4   –   (0,2), (0,5), (1,6), (7).

Объединим пересекающиеся пары.

4   –   (0,2,5), (1,6), (7).                                                                                 (4)

Осталось разложить последовательность (1) по переменной с весом 8:

.

Получается следующее множество пар связанных состояний выхода:

8   –   (0,7), (1), (2), (5), (6).                                                                           (5)

Пересекающихся пар нет.

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

(0,2,5,7), (1,6).                                                                                               (6)

мы одновременно удовлетворим условиям (2), (4) и (5), сделав фиктивными для младшего разряда кода переменные с весами 1, 4 и 8.

В соответствии с разбиением (6) заполним третью строку таблицы 1.

Для кодирования второго разряда необходимо построить новое разбиение, в котором подмножества (0,2,5,7) и (1,6) должны быть разделены пополам и по-новому сгруппированы в два подмножества. Сначала просто разделим их пополам, учитывая то, что в качестве условий фиктивной зависимости у нас встречаются пары (0,7) и (2,5).

(0,7), (2,5), (1), (6).

Таблица 1

Кодирующая таблица для блока КУ1

 

0

1

2

5

6

7

1

0

0

0

1

1

1

2

0

0

1

1

1

0

3

0

1

0

0

1

0

 

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

(0,1,7), (2,5,6).                                                                                               (7)

Разбиение (7) удовлетворяет условиям (2), (3) и (5), из чего следует, что второй разряд кода будет фиктивно зависеть от переменных с весами 1, 2 и 8. В соответствии с этим разбиением заполним вторую строку таблицы 1.

Две пары чисел (0,7) и (2,5) имеют одинаковые коды в двух младших разрядах. Значит, числа этих пар должны различаться в старшем разряде, то есть в новом разбиении мы должны эти пары разделить. Разбиение

(0,1,2), (5,6,7)                                                                                                (8)

удовлетворяет этому требованию. Однако, это разбиение не удовлетворяет ни одному из условий фиктивной зависимости и, поэтому, старший разряд кода будет существенно зависеть от всех переменных. В соответствии с (8) заполняем первую строку таблицы 1.

С помощью таблицы 1 перекодируем исходную числовую последовательность (1) и построим последовательность блока КУ1:

0011  2677  44**  ****.

Как видно из кодирующей таблицы, коды чисел 0, 1 и 2 являются двоичными эквивалентами этих чисел. Поэтому в числовой последовательности они не изменяются. Числу 5 соответствует код (110), десятичным эквивалентом которого является число 6. Потому в последовательности вместо числа 5 мы ставим 6. Число 6 имеет код (111), который в десятичной системе записывается как число 7. Вместо шестёрки в последовательности ставим семёрку. И так далее.

Построим теперь числовую последовательность выходного кодопреобразователя, пользуясь таблицей 1, как его таблицей вход-выход. При подаче на входы выходного кодопреобразователя комбинации (000), на его выходе мы должны получить число 0. Поэтому на нулевом месте в числовой последовательности ставим ноль. При подаче комбинации (001) мы должны получить число 1 и поэтому на первом месте последовательности ставим единицу. Если мы подадим комбинацию (010), на выходе должно получиться число 2. На втором месте последовательности стоит число 2. Комбинация (011) на входах выходного кодопреобразователя невозможна. Поэтому на третьем месте стоит звёздочка. И так далее. Числовая последовательность кодопреобразователя КП имеет следующий вид:

012*  7*56.

Теперь нужно провести декомпозицию блока КУ1 и выходного кодопреобразователя КП [5, 6]. Это можно сделать в произвольном порядке. Полученная в результате подобных преобразований схема содержит пять двухвходовых блоков (рис. 2).

 

рис. 2. Блок-схема схема синтезируемого устройства

Литература

1.   Бибило П.Н., Енин С.В. Синтез комбинационных схем методами функциональной декомпозиции / под ред. А.Д. Закревского. – Мн.: Наука и техника, 1987. 189 с.

2.   Бибило П.Н. Декомпозиция булевых функций на основе решения логических уравнений. – Минск: Беларус. навука, 2009. – 211 с.

3.   Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств. – М.: ФИЗМАТЛИТ, 2007. – 592 с.

4.   Логический синтез комбинационных схем на основе методов декомпозиции / Коновалов В.Н., Коновалов И.В., Белов А.А. [и др.] // Известия ТулГУ. Серия: Вычислительная техника. Информационные технологии. Системы управления. – Тула: Издательство ТулГУ, 2006. – Вып. 3: Системы управления. – Т. 1. – С. 231–233.

5.   Коновалов В.Н., Коновалов И.В., Белов А.А., Нежельский П.Н. Проблемы автоматизированного синтеза комбинационных схем и конечных автоматов // Труды V Российской НТК «Новые информационные технологии в системах связи и управления», часть 2 – Калуга, 2006, С. 188-190.

6.   Система автоматизированного проектирования комбинационных логических схем на основе методов многоуровневой декомпозиции / Коновалов В.Н., Белов А.А., Коновалов И.В. [и др.] // Автоматизация проектирования дискретных систем: материалы шестой междунар. конф. – Мн.: ОИПИ НАН Беларуси, 2007. – Т. 2. – С. 130–137.