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

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

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

Multiple digit multibit binary adder synthesis using multilevel decomposition methods is considered.

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

Итеративные преобразователи цифровой информации

Формальное описание рассматриваемых схем в виде системы логических уравнений или таблицы истинности и последующий их синтез представляют собой весьма сложную задачу, поскольку они имеют достаточно большое количество входов. Например, схема сложения четырёх восьмиразрядных чисел будет содержать в общем случае 34 входа и 10 выходов. Однако следует заметить, что преобразование информации, осуществляемое подобными многоразрядными цифровыми устройствами, как правило, носит итеративный характер, то есть может разделяться на отдельные шаги. На каждом шаге выполняются преобразования соответствующих разрядов, из которых составлены входные слова. В общем случае результат преобразования одних разрядов входных слов может зависеть от результата преобразования других. Поэтому, цепочка преобразований является направленной. В зависимости от направления этой цепочки итеративные преобразования слов разделяются на правые и левые [1].

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

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

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

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

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

Логический синтез многовходового сумматора

В качестве примера рассмотрим процедуру логического синтеза схемы сумматора для сложения четырёх многоразрядных двоичных чисел. Для этого построим числовую последовательность устройства суммирования четырёх трёхразрядных чисел, которая в дальнейшем будет использована в качестве исходного описания схемы при синтезе в САПР «Decomposer» [2, 3]. Указанная сумма вычисляется по формуле 1:

(1)

Формат входного слова и весовые коэффициенты соответствующих разрядов входных переменных приведены в таблице1.

Таблица 1

В таблице 2 представлен начальный фрагмент числовой последовательности синтезируемого цифрового устройства, получаемый в соответствии с формулой 1. Вся числовая последовательность содержит 2048 элементов.

Таблица 2

Фрагмент числовой последовательности сумматора четырёх трёхразрядных чисел

D=0, C=0										D=0, C=1
B	A	0	1	2	3	4	5	6	7	B	A	0	1	2	3	4	5	6	7
0		00	01	02	03	04	05	06	07	0		01	02	03	04	05	06	07	10
1		01	02	03	04	05	06	07	10	1		02	03	04	05	06	07	10	11
2		02	03	04	05	06	07	10	11	2		03	04	05	06	07	10	11	12
3		03	04	05	06	07	10	11	12	3		04	05	06	07	10	11	12	13
4		04	05	06	07	10	11	12	13	4		05	06	07	10	11	12	13	14
5		05	06	07	10	11	12	13	14	5		06	07	10	11	12	13	14	15
6		06	07	10	11	12	13	14	15	6		07	10	11	12	13	14	15	16
7		07	10	11	12	13	14	15	16	7		10	11	12	13	14	15	16	17
D=0, C=2										D=0, C=3
B	A	0	1	2	3	4	5	6	7	B	A	0	1	2	3	4	5	6	7
0		02	03	04	05	06	07	10	11	0		03	04	05	06	07	10	11	12
1		03	04	05	06	07	10	11	12	1		04	05	06	07	10	11	12	13
2		04	05	06	07	10	11	12	13	2		05	06	07	10	11	12	13	14
3		05	06	07	10	11	12	13	14	3		06	07	10	11	12	13	14	15
4		06	07	10	11	12	13	14	15	4		07	10	11	12	13	14	15	16
5		07	10	11	12	13	14	15	16	5		10	11	12	13	14	15	16	17
6		10	11	12	13	14	15	16	17	6		11	12	13	14	15	16	17	20
7		11	12	13	14	15	16	17	20	7		12	13	14	15	16	17	20	21
D=0, C=4										D=0, C=5
B	A	0	1	2	3	4	5	6	7	B	A	0	1	2	3	4	5	6	7
0		…	…	…	…	…	…	…	…	0		…	…	…	…	…	…	…	…

Результаты синтеза рассматриваемого цифрового устройства в САПР «Decomposer»представлены на рис. 1.

рис. 1. Результаты декомпозиции трёхразрядного сумматора

Приведённая на рис. 1 схема, носит ярко выраженный итеративный характер. Блок 1, описываемый числовой последовательностью

0123 1234 1234 2345 1234 2345 2345 3456 1234 2345 2345 3456 2345 3456 3456 4567

представляет собой искомое итеративное звено, с использованием которого можно построить схему сумматора требуемой разрядности. Внешними входными переменными этого звена являются старшие разряды (d₄, c₄, b₄ и a₄) суммируемых слагаемых, а внутренними переменными – сигналы переноса с выходов Блока 2, предназначенного для суммирования предыдущих (более младших по старшинству) разрядов d₂, c₂, b₂ и a₂. На выходах Блока 1 формируются старший разряд суммы s₄ и сигналы переноса в блок суммирования следующих по старшинству разрядов входного информационного слова.

Числовая последовательность Блока 2

012* 123* 123* 234* 123* 234* 234* 345* 123* 234* 234* 345* 234* 345* 345* 456*,

в свою очередь, не противоречит числовой последовательности Блока 1, и, следовательно, указанные блоки могут иметь одинаковую схемотехническую реализацию. Внешними входными переменными этого звена являются разряды d₂, c₂, b₂ и a₂ суммируемых слагаемых, а внутренними переменными – сигналы переноса с выходов Блока 3, предназначенного для суммирования самых младших по старшинству разрядов d₁, c₁, b₁ и a₁. На выходах Блока 2 формируются разряд суммы s₂ и сигналы переноса в блок суммирования следующих по старшинству разрядов входного информационного слова.

Блок 3 с числовой последовательностью

0112 1223 1223 2334

является частным случаем выделенного итеративного звена (Блок 1), при условии равенства нулю его внутренних входных переменных.

Логический синтез схемы одноразрядного четырёхвходового сумматора

Дальнейшую декомпозицию и логический синтез итеративного звена, полученного в результате описанных выше процедур, также можно провести с использованием САПР «Decomposer» [2, 3]. Результаты синтеза приведены на рис. 2.

рис. 2. Результаты декомпозиции одноразрядного четырёхвходового сумматора

Блоки 4 и 5 на рис. 2, описываемые числовыми последовательностями 0112 1223, представляют собой полные одноразрядные двоичные сумматоры. Блоки 2 и 3 с числовыми последовательностями 0112 – это полусумматоры. А Блок 1, в свою очередь, может быть реализован двухвходовым элементом ИЛИ.

Анализ фрагмента приведённой выше схемы, содержащего Блоки 1, 2 и 3 позволяет заменить указанные блоки одним полным двоичным сумматором. Окончательный вариант схемы итеративного звена, состоящий из трёх двоичных сумматоров, представлен на рис. 3.

рис. 3. Схема i-го разряда сумматора для сложения четырёх многоразрядных двоичных чисел (Sum4x1)

На рис. 4 представлена схема сумматора для сложения четырёх восьмиразрядных чисел, выполненная на основе полученного выше итеративного блока Sum4x1. Сложение выполняется по формуле 2.

(2)

рис. 4. Схема сумматора для сложения четырёх восьмиразрядных двоичных чисел

Литература

1. Голубев Ю.П. Автоматизация проектирования преобразователей дискретной информации. – Калуга: Издательство «Гриф», 2003. – 652 с.: ил.

2. Коновалов И.В., Коновалов В.Н. Методы и средства автоматизации проектирования комбинационных логических схем на основе многоуровневой декомпозиции // Материалы 3-й Научной конференции «Автоматизация в промышленности» – М: Институт проблем управления, 2009, С. 161–168.

3. САПР Decomposer для автоматизированного проектирования цифровых схем / В.Н. Коновалов, А.А. Белов, И.В. Коновалов [и др.] // Системный анализ и информационные технологии САИТ – 2007: труды второй междунар. конф. – М.: Изд. ЛКИ, 2007. – Т. 2. – С. 270–273.