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

(54) УСТРОЙСТВО ДЛЯ СЖАТИЯ ДВОИЧНЫХ ВЕКТОРСВ

1

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

Известно устройство, выполняющее операцию сжатия .

Однако оно обладает большим количеством оборудования.

Наиболее близким по своей технической сути является устройство для сжатия двоичных векторов 2J ,

Недостатком этого устройства является низкое быстродействие, обусловленное непрерывным характером передачи информашш.

Цель изобретения - увеличение быст- 15 родействия.

Поставленная цель достигается тем, что в устройство для сжатия двоичных векторов, вьшолненое в виде матрицы запоминающих ячеек, содержащей-, тстрсж и 20 Пстолбцов. (ГП П), причем каждая ячейка содержит два .элемента И, элемент ИЛИ и два элемента НЕ, вход первого элемента НЕ соединен с первым информационным входом ячейки и первым входом первого элемента И, выход первого элемента НЕ соединен с первым входом второго элемента И, второй вход которого соединен со вторым информационным входом ячейки, в каждую ячейку введен триггер, выход которого соединен с информационным выходом ячейки, установочный вход триггера соединен со входом второго элемента НЕ и выходом элемента ИЛИ, первый и второй входы которого соединены с выходами первого н второго элементов И соответственно, второй вход первого элемента И соединен с третьим информационным входом ячейки, выход второго элемента НЕ соединен со входом сброса . триггера, а выход ( д , j )-й ячейки ( 1, ..... m , I Ij..., я ) подключен ко второму шформационному входу ( i + 1, j +1) ячейки и тре тьему информационному входу ( -1, j +1) ячейки, к nejpBOMy входу ( j )-й ячейки подключен выход ( , f-1) ячейки, ко второму информационному входу - выход ( i + l,) ячейки. а к третьему информационному входу выход ( -1, I - 1) ячейки. На фиг. 1 приведена структура yci ройства; на фиг. 2 - функциональная схе ма ячейки. Устройство состоит из одинаковых ячеек 1, связанных между собой связями 2. Ячейка содержит элементы И 3 и 4, элемент НЕ 5, элемент ИЛИ 6, элемент НЕ 7 и триггер 8, входы 9, 1О, 11, выход 12. Устройство работает следующим образом. Исходный двоичный вектор подается н входы 9 ячеек левой границы матрицы. В каждом такте на тактовые входы всех триггеров 8 подается синхронизируюишй импульс. .В результате двоичный вектор, хранившийся в триггерах 8 казвдого стол да матрицы, передается в преобразованном виде в соседний справа столбец. Пре образование происходит в ячейке следую щим образом. В каждой ячейке 1 анализируется содержимое триггеров 8 трех ячеек 1, расположенных в соседнем слев столбце в трех смежных строках. При этом при передаче вектора в соседний столбец в каждой, с троке единица переходит в нуль, если непосредственно под ней был нуль; нуль переходит в единицу если непосредственно над ним была единица; в остальных случаях информация передается без изменений. После такого преобразования каждая единииа, под которой непосредственно бы нуль, занимает его место. Таким образом, в каждом такте в очередной столбец ycTpoJteTBa переписывается двоичный вектор, в котором все единицы, которые могли, опустились на одну позицию. Очевидно, что за П - 1 такт (в наихудше случае) выполняется сжатие П -мерного двоичного вектора. При этом результат сжатия окажется в (n-l)-m столбце устройства. Последовательное сжатие множества двоичных векторов вьшолняется устройством в конвейерном режиме следующим образом. Поскольку во 2-м такте частично преобразованный исходный вектор передается во 2-й столбец, на входы устрой ства может быть подан 2-й исходный вектор В 3-м такте 1-й вектор передается в 3-й столбец, 2-й - во 2-й сто бец и на входы может быть подан третий исходный вектор и т. д. Начиная с (п-1)го такта с выходов 12 ( ii - l)-ro столбца будут последовательно, с интервалом D , выдаваться результаты сжатия 1-го, 2-го и других исходных векторов. Таким образом, предлагаемое устройство обеспечивает увеличение быстродействия при обработке (сжатии) последовательности двоичных векторов. Формула изобретения Устройство для сжатия двоичных аекторов, вьшолненное в виде матрицы запоминающих ячеек, содержащей Гп строк и П столбцов (Ш П ), причем каждая ячейка содержит два элемента И, элемент ИЛИ и два элемента НЕ, вход первого элемента НЕ соединен с первым информационным входом ячейки и первым входом первого элемента И, выход первого элемента НЕ соединен .с первым входом второго элемента И, второй вход которого соединен с вторым информационным входом ячейки, отличающееся тем, что, с целью повышения быстродействия, в каждую ячейку введен триггер, выход которого соединен с информационным выходом ячейки, установочный вход триггера соединен с входом второго элемента НЕ и выходом элемента ИЛИ, первый и второй входы которого соединены с выходами первого и второго элементов И соответственно, второй Вход первого элемента И соединен с третьим информационным входом ячейки, выход второго элемента НЕ соединен с входом сброса триггера, а выход ( -(, j )-й ячейки ( 1, ..., m , j 1,..., П ) подключен к второму информационному входу ( +1, I +1)-й ячейки и третьему информационному входу (-, + 1)-й ячейки, к первому информационному входу ( i , j )-й ячейки подключен выход { i , j -1)-й ячейки, 1 второму : информационному входу -выхой (I + + 1, - 1)-й ячейки, а к третьему информационному входу - выход (i- 1, j - 1)-й ячейки. Источники информации, принятые во внимание при экспертизе 1.1ЕЕЕ Trans Майп. V Ю, 1974, № 12. р. 1059-1О66. 2. Авторское свидетельство СССР № 590747, кл.О 06 Р 15/20, 1978 (прототип).