Устройство для сжатия двоичных векторов Советский патент 1986 года по МПК G06F17/16 

Фи2.1

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

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

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

Устройство содержит матрицу ячеек 1, включающую m строк и п столбцов; связи 2-8; триггер 9; элемент НЕ 10; триггер 11; элемент ИЛИ 12; элемент НЕ 13; элемент И 14; элемент ИЛИ 15; элементы И 16-18; элемент НЕ 19.

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

10

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

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

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

Устройство для сжатия двоичных векторов, содержащее матрицу ячеек из m строк и п столбцов, причем каждая ячейка включает два элемента И, первый элемент ИЛИ, два элемента НЕ, первый триггер, вход перИсходный информационный вектор пода- 15 вого элемента НЕ соединен с первым вхоется на входы 2 и 3 ячеек первого столбца, причем i-й разряд вектора подается на вход 2(i, 1) ячейки и вход 3(1 + 1,1) ячейки. Логический вектор подается на входы 4-6 ячеек первого столбца, причем i-й разряд вектора подается на вход 6 (i, 1) ячейки, вход 5 (i- 1,1) ячейки и вход 4 (i + 1,1) ячейки. В каждом такте на тактирующие входы триггеров подается синхроимпульс. В результате двоичные информационный и логический векторы передаются в преобразованном виде в соседний справа столбец. При этом значение i-ro разряда логического вектора в j-ом столбце определяется значениями (i-1)-го, i-ro, (i + 1) разрядов логического вектора в (j - 1) столбце: единица переходит в нуль, если (i -J- 1)-й разряд логического вектора в (j - 1) столбце был равен нулю; нуль переходит в единицу, если (i-1)-й разряд логического вектора в (j - 1) столбце содержит единицу;в остальных случаях i-й разряд логического вектора передается, без изменений.

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

20

25

дом первого элемента И, выход первого элемента НЕ соединен с первым входом второго элемента И, установочный вход первого триггера соединен с входом второго элемента НЕ и с входом первого элемента ИЛИ, первый и второй входы которого соединены с выходами первого и второго элементов И соответственно, выход второго элемента НЕ соединен с входом сброса первого триггера, единичный выход первого триггера (i, j) ячейки (i 1, 2, ..., m; j 1, 2. ..., n) подключен к первому входу первого элемента И (i, j -|- 1) ячейки, к второму входу второго элемента И (i + 1, j + 1) ячейки и к второму входу первого элемента И (i-1, j -} 1) ячейки, к перво.му

30 входу первого элемента И (i, j) ячейки подключен единичный выход первого триггера (i, j - 1) ячейки, к второму входу второго элемента И подключен единичный выход первого триггера (i-1, j-1) ячейки, к второму входу первого элемента И подключен еди35 ничный выход первого триггера (i -Ь 1, j - - 1) ячейки, отличающееся тем, что, с целью расширения функциональных возможностей за счет исключения ограничений на соотношение кодов значений информационного И логического векторов, в каждую ячейку устройства введены третий и четвертый элементы И, второй элемент ИЛИ, третий элемент НЕ и второй триггер, установочный вход которого соединен с выходом второго элемента ИЛИ и с входом третьего эле40

(j - 1) столбца; если значение i-ro разряда мента НЕ, первый и второй входы второго логического вектора в следующий столбецт,,-г,,

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

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

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

элемента ИЛИ подключены соответственно к выходам третьего и четвертого элементов И, выход третьего элемента НЕ соединен с входом сброса второго триггера, первый вход- третьего элемента И подключен к выходу

50 первого элемента И, к первому входу четвертого элемента И подключен выход второго элемента И, единичный выход второго триггера (i, j) ячейки подключен к второму входу третьего элемента И (i, j + i) ячейки и к второму входу четвертого эле55 мента И (1 -|- 1, j -f- 1) ячейки, к второму входу третьего элемента И {i, j) ячейки подключен единичный выход второго триггера (i, j - 1) ячейки, второй вход четвертого

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

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

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

Устройство для сжатия двоичных векторов, содержащее матрицу ячеек из m строк и п столбцов, причем каждая ячейка включает два элемента И, первый элемент ИЛИ, два элемента НЕ, первый триггер, вход первого элемента НЕ соединен с первым вхового элемента НЕ соединен с первым вхо

дом первого элемента И, выход первого элемента НЕ соединен с первым входом второго элемента И, установочный вход первого триггера соединен с входом второго элемента НЕ и с входом первого элемента ИЛИ, первый и второй входы которого соединены с выходами первого и второго элементов И соответственно, выход второго элемента НЕ соединен с входом сброса первого триггера, единичный выход первого триггера (i, j) ячейки (i 1, 2, ..., m; j 1, 2. ..., n) подключен к первому входу первого элемента И (i, j -|- 1) ячейки, к второму входу второго элемента И (i + 1, j + 1) ячейки и к второму входу первого элемента И (i-1, j -} 1) ячейки, к перво.му

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

мента НЕ, первый и второй входы второго т,,-г,,

мента НЕ, первый и второй входы второго т,,-г,,

элемента ИЛИ подключены соответственно к выходам третьего и четвертого элементов И, выход третьего элемента НЕ соединен с вхоом сброса второго триггера, первый вход- ретьего элемента И подключен к выходу

первого элемента И, к первому входу четвертого элемента И подключен выход второго элемента И, единичный выход второго триггера (i, j) ячейки подключен к второму входу третьего элемента И (i, j + i) ячейки и к второму входу четвертого элемента И (1 -|- 1, j -f- 1) ячейки, к второму входу третьего элемента И {i, j) ячейки подключен единичный выход второго триггера (i, j - 1) ячейки, второй вход четвертого

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

(риг.2.

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