Устройство для сжатия двоичных векторов

 

Изобретение относится к вычислительной технике и может быть использовано в системах обработки и передачи двоичной информации. Изобретение решает задачу сокращения аппаратных затрат путем замены 2/V (где /V - разрядность операнда) трехвходовых элементов И двухвходовыми и исключения элементов ИЛИ. С этой целью в каждом из М одноразрядных 1 преобразователей устройства содержатся четыре элемента И 2-5, элемент ИЛИ 6 и два элемента НЕ 7, 8, причем единичное значение в ьм (, Л ) разряде выхода 10 результата появляется в тех случаях, когда есть единичное значение в /-м разряде входа 9 операнда и единичное значение в предыдущих (/-1) разрядах входа операнда или есть единичные значения в предыдущих (/-1) разрядах входа 9 операнда, нет в г -м разряде, но есть единица хотя бы в одном из последующих разрядов входа 9 операнда устройства. 1 ил. (Л 00 N3 05

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) (!) 4 G 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

В rl . М

<о

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4005628/24-24 (22) 07.0!.86 (46) 23.05.87. Бюл. № 19 (72) В. Г. Липский (53) 631.325(088.8) (56) Авторское свидетельство СССР № 943739, кл. G 06 F 15/20, 1981.

Авторское свидетельство СССР № l l 66133, кл. G 06 F l 5/20, 1984. (54) УСТРОЙСТВО ДЛЯ СЖАТИЯ ДВОИЧНЫХ ВЕКТОРОВ (57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки и передачи двоичной информации. Изобретение решает задачу сокращения аппаратных затрат путем замены 2N (где N — разрядность операнда) трехвходовых элементов И двухвходовыми и исключения элементов ИЛИ. С этой целью в каждом из Ю одноразрядных 1 преобразователей устройства содержатся четыре элемента И 2 — 5, элемент ИЛИ 6 и два элемента

НЕ 7 8, причем единичное значение в -м (i=1, N) разряде выхода 10 результата появляется в тех случаях, когда есть единичное значение в -м разряде входа 9 операнда и единичное значение в предыдущих (— 1) разрядах входа операнда или есть единичные значения в предыдущих (i — 1) разрядах входа 9 операнда, нет в i-м разряде, но есть единица хотя бы в одном из последующих разрядов входа 9 операнда устройства. 1 ил.

1312607

Фар.чу,га изобретения

УI=Х VXIZ.

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

Цель изобретения — сокращение аппаратных затрат за счет замены 2N трехвходовых элементов И двухвходовыми и исключения М элементов ИЛИ.

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

Устройство содержит одноразрядные преобразователи 1, каждый из которых содержит четыре элемента И 2 — 5, элемент ИЛИ 6 и два элемента НЕ 7 и 8.

Устройство имеет вход 9 операнда, выход !0 результаты, вход l l единичного переноса, выход 12 единичного переноса, вход 13 нулевого переноса, выход 14 нулевого переноса.

Устройство работает следующим образом.

Каждый одноразрядный преобразователь реализует на выходах своих элементов следующие функции: у,=/ (x,v.,z) — на выходе четвертого элемента И 5, где x — значение i-го разряда операнда; z значение нулевого переноса с вы ода третьего элемента И (i+1)-го одноразрядного преобразователя;

/,=х,f — значение единичного переноса

«выхода первого элемента И 2 (i — 1) одноразрядного преобразователя;

z =)",.i.,viz) — на выходе третьего элеМ«НТ3 И 4.

На вход 13 нулевого переноса устройства подается нулевой сигнал и на информационном выходе одноразрядного преобразователя реализуется функция

/ у»=1 х».

На вход 11 единичного переноса устройства подается единичный сигнал и на информационном выходе первого одноразрядного преобразователя 1 реализуется функция

Исходный двоичный вектор подается на вход операнда устройства. Единичное значение í i-v разряде выхода 10 результата появляетхя в тех случаях, когда есть единичное значение в i-м разряде входа 9 операнда и единичное значение в предыдущих (i 1) разрядах входа операнда или есть единичные значения в предыдущих (i — 1) разрядах входа 9 оперында и нет в i-м разряде, но есть единичное значение хотя бы в одном из последующих разрядов входа 9 операнда устройства.

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

Сокращение аппаратурных затрат, а именно н«ключение одного элемента ИЛИ в каж5

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

В результате перестройки удалось сократить число внутренних связей в одноразрядном преобразователе, поскольку исключен один элемент ИЛИ и два трехвходовых элемента И заменены на двухвходовые. Этот факт хорошо иллюстрирует сравнение общего количества логических входов элементов одноразрядного преобразователя в известном и предлагаемом устройствах: 16 и 12 соответственно. Кроме этого, замена трехвходовых элементов И на двухвходовые также позволяет сократить аппаратурные затраты. Рассмотрим реализацию восьмиразрядного устройства сжатия векторов в известном и предлагаемом устройствах на примере конкретной серии микросхем К555.

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

К555ЛИ2. В результате число корпусов микросхем сокращаетя вдвое.

Устройство для сжатия двоичных векторов, содержащее N одноразрядных преобразователей, где N — разрядность двоичного вектора, каждый из которых содержит четыре элемента И, элемент ИЛИ и два элемента НЕ, причем в каждом одноразрядном преобразователе первый вход первого элемента И является информационным входом одноразрядного преобразователя и подключен к входу первого элемента НЕ, выход которого подключен к первому входу второго элемента И, выход которого подключен к первому входу элемента ИЛИ, второй вход первого элемента И подключен к входу второго элемента НЕ, выход которого подключен к первому входу третьего элемента И, выход первого элемента И i-го (i=1, N) одноразрядного преобразователя подключен к входу второго элемента НЕ (i+1)-го одноразрядного преобразователя, информационный вход и информационный выход г -го одноразрядного преобразователя являются г-ми разрядами соответственно входа операнда и выхода результата устройства, вход второго элемента НЕ первого одноразрядного преобразователя является входом единичного переноса устройства, выход пер13J 2607

Составитель Н Захаревич

Редактор Н. Лазаренко Техред И Верее Корректор Е Рошко

Заказ 1845 49 Тираж 673 11однисное

ВНИИНИ Государственног<> комитета СССР но делам изобретений и открытий

113035, Москва, хк -35, Ра> н>скан наб, д 4 5

Производственно-полиграфическое нредприитие, г. Ужгород, ул. 11роектнаи, 4 вого элемента И N-ro одноразрядного преобразователя является выходом единичного переноса устройства, отличающееся тем, что, с целью сокращения аппаратных затрат за счет замены 2 N трехвходовых элементов

И двухвходовыми и исключения N элементов

ИЛИ, в каждом одноразрядном преобразователе устройства первый вход первого элемента И подключен к второму входу элемента ИЛИ, выход которого подключен к первому входу четвертого элемента И и к второму входу третьего элемента И, второй вход четвертого элемента И подключен к второму входу первого элемента И, а выход четвертого элемен-,а И является и нформационным выходом одноразрядного преобразователя, выход третьего элемента И 1-го (i=1, N) одноразрядного преобразователя подключен к второму вход> второго элемента И (< — 1)го одноразрядного преобразователя, вход второго элемента И N- го одноразрядного преобразователя является входом нулевого переноса устройства, выход третьего элемента И первого одноразрядного преобразователя является выходом нулевого переноса устройства.