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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советсник

Социалистические

Республик (i i) 943739

Г (б! ) Дополнительное к авт. свнд-ву (22) Заявлено 23.10.80 (2l ) 3218408/18-24 (5t)M. Кл. 06 Р 15/20 с присоединением заявки М (23) Приоритет ееоудерстееены3 комитет

СССР ао делам нэоеретенвй и откритея (53) УД К 681.325 (088.8) Опубликовано. 15.07,82. Бюллетень ¹ 26

Дата опубликования описания 18.07.82 (72) Автор. изобретения

Я. И. Фет

Институт математики Сибирского отделения АН СССР (7! ) Заявитель (54) УСТРОЙСТВО ДЛЯ СЖАТИЯ

ДВОИЧНЫХ ВЕКТОРОВ

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

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

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

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

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

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

Поставленная цель достигается тем, что в устройство для сжатия двоичных векторов, выполненое в виде матрицы запоминающих ячеек, содержащей, Е строк и 2D

ll столбцов (pie 8 ), причем каждая ячейка содержит два элемента И, элемент

ИЛИ и. два элемента НЕ, вход первого элемента HE соединен с первым информа2 ционным входом ячейки и первым входом первого элемента И, выход первого элемента НЕ соединен с первым входом второго элемента И, второй вход которого соединен со вторым информационным входом ячейки, в каждую ячейку введен триггер, выход которого соединен с информационным выходом ячейки, установочный вход триггера соединен со входом второго элемента НЕ и выходом элемента ИЛИ, первый и второй входы которого соединены с выходами первого и второго элементов И соответственно, второй вход первого элемента И соединен с третьим информационным входом ячейки, выход второго элемента HE соединен со входом сброса, триггера, а выход (1, j )-й ячейки (= 1, ..., 5 = 1Д..., и ) подключен ко второму. информационному входу ((+ 1, ) + 1) ячейки и третьему информационному входу (4 -1, ) + 1) ячейки, к первому входу (4$ )-й ячейки подключен выход (4, 3 - 1) ячейки, ко второму информационному входу - выход (1 + 1,j - -1) ячейки, бец и на входы может быть подан третий исходный вектор и т. д. Начиная с (tl-1)го такта с выходов 12 (tl -1)-ro столбца будут последовательно, с интервалом

, выдаваться результаты сжатия 1-го, 2-го и других исходных векторов.

Таким образом, предлагаемое устройство обеспечивает увеличение быстродействия при обработке (сжатии) последовательности двоичных векторов.

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

Устройство для сжатия двоичных векторов, выполненное в виде матрицы запоминающих ячеек, содержащей ttt строк и tl столбцов (N < П), причем каждая ячейка содержит два элемента И, элемент ИЛИ и два элемента НЕ, вход первого элемента НЕ соединен с первым информационным входом ячейки и первым входом первого элемента И, выход первого элемента HE соединен.с первым входом второго элемента И, второй вход которого соединен с вторым информационным входом ячейки, отличающееся тем, что, с целью повышения быстродействия, в каждую ячейку введен триггер, выход которого соединен с информационным выходом ячейки, установочный вход триггера соединен с входом второго элемента HE и выходом элемента ИЛИ, первый и второй входы которого соединены с выходами первого и второго элементов И соответственно, второй вход первого элемента И соединен с третьим информационным входом ячейки, выход второго элемента НЕ соединен с входом сброса триггера, а выход (, ) )-й ячейки (j = 1,..., N, ) = 1,..., П ) подключен к второму информационному входу (< + 1, ) + 1)-й ячейки и третьему информационному входу ((- 1, ) + 1)-й ячейки, к первому информационному входу (<, f )-й ячейки подкпючен выход (<, ) -1)-й ячейки, к второму: информационному входу -выход (+

+ 1, ) - 1)-й ячейки, а к третьему информационному входу - выход (<- 1, j - 1)-й ячейки.

Источники информации, принятые во внимание при экспертизе

1.1ЕЕЕ Тгаоа hAagtl. Ч1 О, 1974, ¹ 12. р. 1059-1066.

2. Авторское свидетельство СССР № 590747, кл. Q 06 V 15/20, 1978 (прототип).

3 943739 ф а к третьему информационному входувыход ({ -1, 1 - 1) ячейки.

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

Устройство состоит, из одинаковых ячеек 1, связанных между собой связями 2.

Ячейка содержит элементы И 3 и 4, элемент HE 5, элемент ИЛИ 6, элемент ttt

HE 7 и триггер 8, входы 9, 10, 11, выход 12.

Yc TpoRc TBQ работает следующим об» разом.

Исходный двоичный вектор подается на 1з входы 9 ячеек левой границы матрицы.

В каждом такте на тактовые входы всех триггеров 8 подается синхронизирующий импульс.,В результате двоичный вектор, хранившийся в триггерах 8 каждого столб-20 ца матрицы, передается в преобразован: ном виде в соседний справа столбец. Преобразование происходит в ячейке следующим образом. В каждой ячейке 1 анализируется содержимое триггеров 8 трех ячеек 1, расположенных в соседнем слева столбце в трех смежных строках. При этом нри передаче вектора в соседний столбец в каждой, строке единица переходит в нуль, если непосредственно под ней был нуль; нуль переходит в единицу, если непосредственно над ним была единица, в остальных случаях информация передается без изменений.

После такого преобразования каждая

35 единица, под которой непосредственно был нуль, занимает его место. Таким образом, в каждом такте в очередной столбец устройства переписывается двоичный вектор, в котором все единицы, которые

"могли", опустились на одну позицию.

Очевидно, что за tl -1 такт (в наихудшем случае) выполняется сжатие tl -мерного двоичного вектора, При этом результат сжатия окажется в (П -1) - ttt столбце

45 ус тройс тва.

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

Поскольку во 2-м такте частично преобразованный исходный вектор передается во 2-й столбец, на входы устройства может быть подан 2-й исходный вектор. В 3-м такте 1-й вектор передается в 3-и столбец, 2-й - во 2-й стол55

943739

Составитель П. Чистобородов

Техред. З.Папий Корректор Г. Огар

Редактор A Иолинич

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

Заказ 5113/57 Тираж 73 1 . Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5