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

)4 С 06 Р 15/20 ННЫЙ КОМИТЕТ СССР Ретений и ОтнРытий ГОСУДАРСТВЕ ДЕЛАМОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ етельство СССР15/00, 1974.ельство СССР15/20, 1980. ключены соответстве ервого элемента ИЛИ м о к выход которого является первым выходом еики, лемен ерто вого выходы пе.тов И соедвходами в ены соответствен срого элем го являетс ки, второй выт ход кот оходом ячсоединента И,выторой(54)(57) УСТРОЙСТВО ДЛЯ СЖАТИЯ ДВОИЧНЫХ ВЕКТОРОВ, содержащее и яче ек, каждая из которых включает первый и второй элементы И, первый элемент ИЛИ и два элемента НЕ, о т- л и ч а ю щ е е ся тем, что, с целью сокращения аппаратурных затрат, в каждую ячейку введены третий и четвертый элементы И и второй элемент ИЛИ, причем первые входы всех ячеек являются входами исходного двоичного вектора устройства, второй вход П -й ячейки является входом нулевого значения сигнала устройства,.второй вход каждой , -й ячейки соединен с первым выходом (+1)-.й ячейки, третий вход первойячейки является входом единичного значения сигнала устройства, третий вход 1 -й ячейки соединен .с вторым выходом (1-1)-й ячейки, третьи выходы всехячеек являются выходами устройства, а в каждой ячейке первый ее вход соединен с первыми входами первого и второго элементов И и с входом первого элемента НЕ, выход которого подключен к первым входам третьего и четвертого элементов И, вторые входы которых соединены с вторым входом ячейки, трегий вход которой соединен с вторым входом первого элемента И, с третьим входом четвертого элемента И и с входом второго элемента НЕ, выход которого соединен с вторым входом второго элемента И и с третьим входом третьего элемента И, выходы второго и третьего элементов И под 1 1Изобретение относится к вычислительной технике и предназначено для сжатия двоичных векторов.Известно устройство для обработки и сжатия информации, содержащее регистр текущей выборки, сумматор, оперативную память, регистр числа, буферную память, счетчик заполнения, элементы И-НЕ, схему сравнения, элементы ИЛИ, И 1.Для реализации устройства требуются значительные затраты оборудования.Наиболее близким по технической сущности к изобретению является устройство, выполненное в виде матрицы запоминающих ячеек, содержащей в строк и и столбцов, причем каждая ячейка содержит два элемента И, элемент ИЛИ, два элемента НЕ, триггер 2Однако известное устройство обладает большим количеством оборудования, так как выполнено в ниде матрицы.Цель изобретения - сокращение аппаратурных затратПоставленная цель достигается тем, что в устройстве, содержащем и ячеек, каждая из которых включает первый и второй элементы И, элемент ИЛИ и два элемента НЕ, в каждую ячейку введены третий и четвертый элементы И и второй элемент ИЛИ, причем первые входы всех ячеек.являются входами исходного двоичного вектора устройства, второй вход и-й ячейки является входом нулевого значения сигнала устройства, второй вход каздой д-й ячейки соединен с первым выходом+ 1-й ячейки, третий вход первой ячейки является входом единичного значения сигнала устройства, третий вход ь-й ячейки соединен с вторым выходом 1-1-й ячейки, третьи выходы всех ячеек являются выходами устройства, а в каждой ячейке первый ее вход соединен с первыми входами первого и второго элементов И и с входом первого элемента НЕ, выход которого подключен к первым входам третьего и четвертого элементов И, вторые входы которых соединены с вторым входом ячейки, третий вход которой соединен с вторым входом первого элемента И, с третьим входом четвертого элемен 166133 1 О 15 20 30 35 40 45 50 55 та И и с входом второго элемента НЕ, выход которого соединен с вторым входом второго элемента И и с третьим входом третьего элемента И, выходы второго и третьего элементов И подключены соответственно к входам первого элемента ИЛИ, выход которого является первым выходом ячейки, выходы первого и четвертого элементов И соединены соответственно с входами второго элемента ИЛИ, выход которого является третьим выходом ячейки, второй выход которой соединен с выходом, первого элемента И.На фиг. 1 представлена структурная схема предлагаемого устройстваф на фиг. 2 - схема ячейки.Устройство содержит ячейки 1 - 1, выходы и входы 2-7 ячеек, элементы ИЛИ 8, элементы И 9 и 10, элементы НЕ 11 и 12, элементы И 13 и 14, элемент ИЛИ 15.Устройство работает следующим образом.Каждая ячейка реализует следующие функции:Ву = хй ч хЙ г у = х ч хг г = х;Г,ч хЕ гНа вход 3 верхней ячейки подается нулевой сигнал, йа вход 6 нижней ячейки - единичный сигнал. Исходный двоичный вектор подается на входы 4 всех ячеек. Единичный сигнал на выходе 7 ячейки появляется в тех случаях, если есть единичный сигнал на входе 4 этой ячейки и единичный сигнал на входах предыдущих. ячеек или есть единичные сигналы на входах 4 предыдущих 1, -1ячеек и нет на входе 4 ячейки 1;, но есть единичный потенциал хотя бы на одном из последующих входов 4 ячеек 1;- .1.Таким образом, каждая единица, под которой находятся нули, продвигается вниз, пока не встретитсясединица, т.е. осуществится следующее преобразование, например, двоичный вектор на входе 01100010, на выходе 00000111.Предлагаемое устройство путем введения в ячейку двух элементов И, одного элемента ИЛИ и вследствие йзменения связей между ячейками позволяет выполнить его в виде ли3 нейки, а не в виде матрицы, чтосокращает аппаратурные затраты, Например, для сжатия 8-разрядногодвоичного вектора предлагаемое устройство содержит 32 элемента И,16 элементов ИЛИ и 16 элементовНЕ, а известное устройство содержит 1166133 4 128 элементов И, 64 элемента ЙЛИ и 128 элементов НЕ. Таким образом, предлагаемое уст ройство позволяет сэкономить 96элементов И, 48 элементов ИЛИ и112 элементов НЕ.1166133 Составитель А. Жереновор А. Козориз Техред А.Бабинец Корректор Е. Рошк одпи 5 филиал ППП "Патент", г, Ужгород, ул. Проектная, 4 акаэ 4312/45 Тираж ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, Рау