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

 

Изобретение относится к вычислительной технике. Известные устройства имеют ограниченные функциональные возможности, поскольку они позволяют реализовать операцию сжатия двоичных векторов только в частном случае. В общем случае под сжатием понимается процедура, ставящая в соответствие двум исходным двоичным векторам: информационному и логическому некоторый результирующий двоичный вектор, который содержит только те разряды информационного вектора, которые соответствуют единичным значениям разрядов логического вектора. Известные устройства для сжатия двоичных векторов позволяют производить сжатие в частном случае, когда значения информационного и логического векторов равны. Тогда выходной вектор содержит разряды информационного вектора, имеющие значение единицы. Цель изобретения - расширение функциональных возможностей устройства за счет исключения ограничений на соотнощение кодов значений информационного и логического векторов. Устройство выполнено в виде матрицы, содержащей m строк и п столбцов и состоит из одинаковых я.чеек 1, соединенных между собой связями 2, 3, 4, 5, 6, 7, 8. Каждая ячейка памяти содержит два триггера, три элемента НЕ, два элемента ИЛИ, четыре элемента И. 2 ил. (Л 81 Г го сд Oi Вы/. /

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

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

РЕСПУБЛИК (gD 4 6 06 F 15/20, 15/347

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3860761/24-24 (22) 01.03.85 (46) 07.09.86. Бюл. № 33 (72) А. Я. Матов, С. Е. Карловский, А. М. Макарчук, В. Н. Дроник и И. M. Якуб (53) 681.325.22 (088.8) (56) Авторское свидетельство СССР № 531158, кл. G 06 F 15/00, 1974.

Авторское свидетельство СССР № 943739, кл. G 06 F 15/20, 1980. (54) УСТРОЙСТВО ДЛЯ СЖАТИЯ ДВОИЧНЫХ ВЕКТОРОВ (57) Изобретение относится к вычислительной технике. Известные устройства имеют ограниченные функциональные возможности, поскольку они позволяют реализовать операцию сжатия двоичных векторов только в частном случае. В общем случае под сжатием понимается процедура. ставящая в соответствие двум исходным двоичным векторам: информационному и логическому некоторый

„„ЯЦ„„1256041 результирующий двоичный вектор, который содержит только те разряды информационного вектора, которые соответствуют единичным значениям разрядов логического вектора, Известные устройства для сжатия двоичных векторов позволяют производить сжатие в частном случае, когда значения информационного и логического векторов равны. Тогда выходной вектор содержит разряды информационного вектора, имеющие значение единицы. Цель изобретения — расширение функциональных возможностей устройства за счет исключения ограничений на соотношение кодов значений информационного и логического векторов. Устройство выполнено в виде матрицы, содержащей m строк и и столбцов и состоит из одинаковых ячеек 1, соединенных между собой связями 2, 3, 4, 5, 6, 7, 8. Каждая ячейка памяти содержит два триггера, три элемента НЕ, два элемента ИЛИ. четыре элемента И. 2 ил.

1256041

Изобретение относится к вычислительной технике.

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

На фиг. 1 представлена схема устройства; на фиг. 2 — схема ячейки устройства.

Устройство содержит матрицу ячеек 1, включающую m строк и и столбцов; связи 2 — 8; триггер 9; элемент НЕ 10; триггер

11; элемент ИЛИ 12; элемент HE 13; элемент И 14; элемент ИЛИ 15; элементы

И 16 — 18; элемент НЕ 19.

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

Исходный информационный вектор подается на входы 2 и 3 ячеек первого столбца, причем i-й разряд вектора подается на вход

2(i, 1) ячейки и вход 3(i+ 1,1) ячейки. Логический вектор подается на входы 4 — 6 ячеек первого столбца, причем i-й разряд вектора подается на вход 6 (i, 1) ячейки, вход 5 (i — 1,1) ячейки и вход 4 (i + 1,1) ячейки. В каждом такте на тактирующие входы триггеров подается синхроимпульс. В результате двоичные информационный и логический векторы передаются в преобразованном виде в соседний справа столбец.

При этом значение i-го разряда логического вектора в j-ом столбце определяется значениями (i — 1)-го, i-го, (i + 1) разрядов логического вектора в (j — 1) столбце: единица переходит в нуль, если (i + 1)-й разряд логического вектора в (j — 1) столбце был равен нулю; нуль переходит в единицу, если (i — 1)-й разряд логического вектора в (j — 1) столбце содержит единицу;в остальных случаях i-й разряд логического вектора передается, без изменений.

Значение i-ro разряда информационного вектора в j-м столбце определяется по следующему правилу: если i-й разряд логического вектора изменился с единицы на нуль, то i-ый разряд информационного вектора

j-го столбца обнуляется; если i-й разряд логического вектора изменился с нуля на единицу, то i-му разряду информационного вектора j ãî столбца присваивается значение (i — 1) разряда информационного вектора (j- —; если значение i-ro разряда логического вектора в следующий столбец передается без изменений, то значение i-го разряда информационного вектора в следующий столбец также передается без изменений.

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

За (m — !) такт происходит сжатие mмерного двоичного вектора. Результат сжатия информационного вектора снимается с

Формула изобретения

15

Зо

45 выхода 7 ячеек последнего столбца устройства.

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

Устройство для сжатия двоичных векторов, содержащее матрицу ячеек из m строк и п столбцов, причем каждая ячейка включает два элемента И, первый элемент ИЛИ, два элемента НЕ, первый триггер, вход первого элемента НЕ соединен с первым входом первого элемента И, выход первого элемента НЕ соединен с первым входом второго элемента И, установочный вход первого триггера соединен с входом второго элемента НЕ и с входом первого элемента ИЛИ, первый и второй входы которого соединены с выходами первого и второго элементов И соответственно, выход второго элемента HE соединен с входом сброса первого триггера, единичный выход первого триггера (i, j) ячейки (i = 1, 2, ..., m; j =

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

1256041

Составитель .А. Жсрс иов

Редактор С. Патрушева Техред И. Верее Коррслт р Л. Обруиир

Заказ 4825!49 Тираж 671 1! о.ц и.с ни

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

113035, Москва, Ж вЂ” 35, Раушская наб., и. 4, 5

Филиал ППП «Патент», г. Ужгород, ул. 11роектная. 4

3 элемента и (1, i) ячейки соединен с единичным выходом второго триггера (i — 1, j — 1) ячейки, синхронизирующие входы первого и второго триггеров каждой ячейки соединены с синхронизирующим входом устройства.