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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 19) (И) О 06 Г 15 20 ОПИСАНИЕ ИЗОБРЕТЕНИЯ ВУ УДАРСТВЕННЫЙ КОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ А ВТОРСКОМУ СВИДЕТЕЛ(54) УСТРОЙСТВО ДЛЯ СЖАТИЯ ДВО. ИЧНЫХ ВЕКТОРОВ(57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки и передачи двоичной информации. Изобретение решает задачу сокращения аппаратных затрат путем замены 2% (где М - разрядность операнда) трехвходовых элементов И двухвходовыми и исключения элементов ИЛИ. С этой целью в каждом из Ю одноразрядных 1 преобразователей устройства содержатся четыре элемента И 2 - 5, элемент ИЛИ 6 и два элемента НЕ 7 8, причем единичное значение в -м (=1, М) разряде выхода 10 результата появляется в тех случаях, когда есть единичное значение в -м разряде входа 9 операнда и единичное значение в предыдуших ( - 1) разрядах входа операнда или есть единичные значения в предыдущих ( - 1) разрядах входа 9 операнда, нет в -м разряде, но есть единица хотя бы в одном из последующих разрядов входа 9 операнда устройства. 1 ил.фор.чу,га изобретения у=х .хг. Изобретение относится к вычислительной технике и может быть использовано в систе. мах обработки и передачи двоичной информации.Цель изобретения - сокращение аппаратных затрат за счет замены 2 М трехвходовых элементов И двухвходовыми и исключения М элементов ИЛИ.На чертеже приведена функциональная схема предлагаемого устройства.Устройство содержит одноразрядные преобразователи 1, каждый из которых содержит четыре элемента И 2 - 5, элемент ИЛИ 6 и лва элемента НЕ 7 и 8.Устройство имеет вход 9 операнда, выход 0 результата, вход 11 единичного переноса, выход 12 единичного переноса, вход 13 нулевого переноса, выход 14 нулевого переноса.Устройство работает следующим образом.Каждый одноразрядный преобразователь реализует на выходах своих элементов следующие функции:у,=)(х,у.,г) - на выходе четвертого элемента И 5, где х - значение -го разряда операнда; г значение нулевого переноса с выхода третьего элемента И (+1) -го одноразрядного преобразователя;),=х,) - значение единичного переноса с выхола первого элемента И 2 (г - 1) одноразрялного преобразователя;г=)",.с,чти) - на выходе третьего элемента И 4.На вход 13 нулевого переноса устройства полается нулевой сигнал и на информационном выходе одноразрядного преобразователя реализуется функция/ун 1 хн На вход 11 единичного переноса устройства полается единичный сигнал и на информационном выходе первого одноразрядного преобразователя 1 реализуется функция Исходный двоичный вектор подается на в.ход операнда устройства. Единичное нацепив в г-и разряде выхода 10 результата появляется н тех случаях, когда есть едипичпое значение в -м разряде входа 9 операнда и единичное значение в предыдущих ( 1) разрялах вхола операнда или есть единичные значения в предыдуших (г - 1) разрядах входа 9 операнда и нет в г-м разряле, но есть единичное значение хотя бы в од. пом из последующих разрядов входа 9 операнда устройства.Таким образом, каждая единица, под которой находятся нули, продвигается вниз, пока не встретится единица, т. е. осуществляется, например, следующее преобразование: двоичный вектор на входе 01100010 преобразуется в вектор 00000111 на выходе.Сокращение аппаратурных затрат, а именно нключение одного элемента ИЛИ в каж 5 О 5 20 25 30 35 40 45 50 55 дом одноразрядном преобразователе достигается за счет перестройки внутренних связей в нем, причем реализуемые на выходах элементов одноразрядного преобразователя логические функции остаются такими же как и у известного устройства. Таким образом, в случае, если реализовано устройство для сжатия восьми разрядных векторов, будет сэкономлено восемь элементов ИЛИ.В результате перестройки удалось сократить число внутренних связей в одноразрядном преобразователе, поскольку исключен один элемент ИЛИ и два трехвходовых элемента И заменены на двухвходовые. Этот факт хорошо иллюстрирует сравнение общего количества логических входов элемен. тов одноразрядного преобразователя в известном и предлагаемом устройствах: 16 и 12 соответственно. Кроме этого, замена трехвходовых элементов И на двухвходовые также позволяет сократить аппаратурные затраты. Рассмотрим реализацию восьмиразрядного устройства сжатия векторов в известном и предлагаемом устройствах на примере конкретной серии микросхем К 555. Реализация известного устройства требует шесть микросхем типа К 555 ЛИЗ, каждая из которых содержит три трехвходовых элемента И (всего же требуется 16 трехвходовых элементов). В предлагаемом устройстве 16 трехвходовых элементов И заменены на6 двухвходовых элементов И, которые размещаются в четырех микросхемах типа К 555 ЛИ 2. В результате число корпусов микросхем сокращаетя вдвое. Устройство для сжатия двоичных векторов, содержащее М одноразрядных преобразователей, где Лl - разрядность двоичного вектора, каждый из которых содержит четыре элемента И, элемент ИЛИ и два элемента НЕ, причем в каждом одноразрядном преобразователе первый вход первого элемента И является информационным входом одноразрядного преобразователя и подключен к входу первого элемента НЕ, выход которого подключен к первому входу второго элемента И, выход которого подключен к первому входу элемента ИЛИ, второй вход первого элемента И подключен к входу второго элемента НЕ, выход которого подключен к первому входу третьего элемента И, выход первого элемента И с-го (ю=1, ,У) одноразрядного преобразователя подключен к входу второго элемента НЕ +)-го одноразрядного преобразователя, информационный вход и информационный выход г-го одноразрядного преобразователя являются г-ми разрядами соответственно входа операнда и выхода результата устройства, вход второго элемента НЕ первого одноразрядного преобразователя является входом единичного переноса устройства, выход пер132607 Составитель Н Захаревич Редактор Н. Лазаренко Техред И Верее Корректор Е Рошко Заказ 1845/49 Тираж 673 11 од и и с не ВНИИНИ Государственного комитета СССР но делам изобретений и открьтий 1 3035, Москва, хк 35, Ра шскаи наб, д 4 5 11 роизводственно.полиграфическое нредприитие, г, Ужгород, ул. 1 роектнаи, 4вого элемента И Л-го одноразрядного преобразователя является выходом единичного переноса устройства, отличающееся тем, что, с целью сокращения аппаратных затрат за счет замены 2 Л трехвходовых элементов И двухвходовыми и исключения Лl элементов ИЛИ, в каждом одноразрядном преобразователе устройства первый вход первого элемента И подключен к второму входу элемента ИЛИ, выход которого подключен к первому входу четвертого элемента И и к второму входу третьего элемента И, второй вход четвертого элемента И подключен к второму входу первого элемента И, а выход четвертого элемента И является информационным выходом одноразрядного преобразователя, выход третьего элемента И -го (=1, Л 1) одноразрядного преобразователя подключен к второму входх второго элемента И ( - 1)- го одноразрядного преобразователя, вход второго элемента И Л-го одноразрядного преобразователя является входом нулевого переноса устройства, выход третьего эле- О мента И первого одноразрядного преобразователя является выходом нулевого переноса устройства.