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

 

УСТРОЙСТВО 7Ц1Я СЖАТИЯ ДВОИЧНЫХ ВЕКТОРОВ, содержащее ti ячеек , каждая из которых включает первый и второй элементы И, первый элемент ИЛИ и два элемента НЕ, о тличающее ся тем, что, с целью сокращения аппаратурных затрат , в каждую ячейку введены третий и четвертый элементы И и второй элемент ИЛИ, причем первые входы всех ячеек йвляются входами исходного; двоичного вектора устройства, второй вход П -и ячейки является входом нулевого значения сигнала устройства, второй вход каждой i ячейки соединен с первым выходом

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

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

РЕСПУБЛИК (>9> SU >> >> (5114 G 06 F 15/20 ф:,, //!>

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

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

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

ПО ДЕЛАМ ИЗОВРЕТЕНИЙ И ОТКРЫТИЙ (21) 3692983/24-24 (22) 20.01.84 (46) 07.07.85. Бюл. У 25 . (72) О.М. Омаров (71) Дагестанский политехнический институт (53) 681.325.7(088.8) (56) 1. Авторское свидетельство СССР

М 531158, кл. G 06 F 15/00, 1974.

2, Авторское свидетельство СССР

В 943739, кл. G 06 Р 15/20, 1980. (прототип). (54)(57) УСТРОЙСТВО ДЛЯ СЖАТИЯ

ДВОИЧНЫХ ВЕКТОРОВ, содержащее и ячеек, каждая из которых включает пер- . вый и второй элементы И, первый элемент ИЛИ и два элемента НЕ, о т- л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, в каждую ячейку введены третий и четвертый элементы И и второй элемент ИЛИ, причем первые входы всех ячеек являются входами исходйого-двоичного вектора устройства, второй вход tl -й ячейки является входом нулевого значения сигнала устройства,.второй вход каждой 6 --й ячейки соединен с первым выходом (i+1)-.й ячейки, третий вход первой ячейки является входом единичного значения сигнала устройства, третий вход 1 -й ячейки соединен .с вторым выходом (i-1)-й ячейки, третьи выходы всех ячеек являются выходами устройства, а в каждой ячейке первый ее вход оединен с первыми входами первого и второго элементов

И и с входом первого элемента НЕ, выход которого подключен к первым входам третьего и четвертого элементов И, вторые входы которых соединены с вторым входом ячейки, трегий вход которой соединен с вторым входом первого элемента И, с третьим входом четвертого элемента И и с входом второго элемента НЕ, выход которого соединен с вторь|м входом второго элемента И и с третьим входом третьего элемента И, выходы второго и третьего элементов И под. ключены соответственно к входам первого элемента ИЛИ, выход которого является первым выходом ячейки, выходы первого и четвертого элемен.тов И соединены соответственно с входами второго элемента ИЛИ, вы ход которого является третьим выходом ячейки, второй выход которой соединен с выходом первого элемента И, 1 1

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

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

Для реализации устройства требуются значительные затраты оборудования.

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

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

Ф

Цель изобретения — сокращение аппаратурных затрат..

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

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

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

55 та И и с входом второго элемента

НЕ, выход которого соединен с вторым входом второго элемента И и с третьим входом третьего элемента

И, выходы второго и третьего элементов И подключены соответственно к входам первого элемента ИЛИ, выход которого является первым выходом ячейки, выходы первого и четвертого элементов И соединены соответственно с входами второго элемента ИЛИ, выход которого является третьим выходом ячейки, второй выход которой соединен с выходом, первого элемента И.

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

Устройство содержит ячейки 1 — 1, выходы и входы 2-7 ячеек, элементы

ИЛИ 8, элементы И 9 и 10, элементы

НЕ 11 и 12, элементы И 13 и 14, элемент ИЛИ 15.

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

Каждая ячейка реализует следующие функции:

I — х,f v x;f z y< = х v х2

z =x f чх f z

На вход 3 верхней ячейки подается нулевой сигнал, йа вход 6 нижней ячейки — единичный сигнал.

Исходный двоичный вектор подается на входы 4 всех ячеек. Единичный сигнал на выходе 7 ячейки появляется в тех случаях, если есть единичный сигнал на входе 4 этой ячейки и единичный сигнал на входах предыдущих- ячеек или есть единичные сигналы на входах 4 предыдущих 1, -1„ > ячеек и нет на входе 4 ячейки 1;, но есть единичный потенциал хотя бы на одном из последующих входов

4 ячеек 1 1+ .1 °

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

Предлагаемое устройство путем введения в ячейку двух элементов

И, одного элемента ИЛИ и вследствие йзменения связей между ячейками позволяет выполнить его в виде линейки, а не в виде матрицы, что сокращает аппаратурные затраты. Например, для сжатия 8-разрядного двоичного вектора предлагаемое устройство содержит 32 элемента И, 16 элементов ИЛИ и 16 элементов НЕ, а известное устройство содержит

1166133 4

128 элементов И, 64 элемента ИЛИ и 128 элементов НЕ.

Таким образом, предлагаемое. устройство позволяет сэкономить 96 элементов И, 48 элементов HJIH u

112 элементов НЕ.

° °

1166133

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

Техред А.Бабинец Корректор Е. Рошко .

Редактор А. Козориз

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

Заказ 4312/45 Тираж 710 Подписное

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

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