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

 

Изобретение относится к области цифровой вычислительной техники и может быть использовано в системах хранения информации . Устройство содержит блок 1 синхронизации , первый 2 и второй 3 регистры, первый 4, третий 5 и второй 6 счетчики, второй сумматор 7, блок 8 определения наименьшего целого, первый сумматор 9, компаратор 10, третий 11 и четвертый 12 регистры, накопитель 13, формирователь 14 сигнала направления сжатия. Устранение +1збыточности реализуется посредством сравнения между собой значений слова со значениями слов, структурно подчиненных этому слову, накопления относительных поправок и коррекции исходных значений слов на эту величину. В результате появляется возможность значительно (более чем в 2 раза) сократить требуемый объем памяти и сжимать повторяющиеся слова. 7 ил., 1 табл.

СОЮЗ СОЬ ТСКИХ

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

РЕСПУБЛИК

„„SU„„1381564 А 1 (51)4 08 С 15

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

H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4041948/24-24 (22) 24.03.86 (46) 15.03.88. Бюл. № 10 (75) H. Н. Ярцев (53) 621.398 (088.8) ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (54) УСТРОИСТВО ДЛЯ СЖАТИЯ ДАННЫХ (57) Изобретение относится к области цифровой вычислительной техники и может быть использовано в системах хранения информации. Устройство содержит блок 1 синхронизации, первый 2 и второй 3 регистры, первый 4, третий 5 и второй 6 счетчики, второй сумматор 7, блок 8 определения наименьшего целого, первый сумматор 9, компаратор

10, третий 11 и четвертый 12 регистры, накопитель 13, формирователь 14 сигнала направления сжатия. Устранение избыточности реализуется посредством сравнения между собой значений слова со значениями слов, структурно подчиненных этому слову, накопления относительных поправок и коррекции исходных значений слов на эту величину.

В результате появляется возможность значительно (более чем в 2 раза) сократить требуемый объем памяти и сжимать повторяющиеся слова. 7 ил., 1 табл.

1381564

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

Цель изобретения -- расширение области применения устройства путем сжатия повторяющихся слов.

На фиг. I приведена функциональная схема устройства; на фиг. 2 — функциональная схема блока формирования; на фиг. 3 — 7— таблицы, иллюстрирующие работу устройства.

Устройство (фиг. ) содержит блок 1 синхронизации, первый 2 и второй 3 регистры, первый 4, третий 5 и второй 6 счетчики, второй сумматор 7, блок 8 определения наимеш.шего целого, первый сумматор 9, комnapaтор l0, третий 11 и четвертый 12 регистры, накопитель 13 и формирователь 14 сигнала направлении сжагия

Формирователь 14 (фиг. 2) включает синхронизатор 15, счетчики 16 19, формирователь 20 сдвига, счетчик 21, сумматоры 22

24, триперы 25- 27, дешифратор 28 и счетчики 29 и 30.

Устранение избыточности реализуется в устройстве посредством сравнения значений

I-x слов со значениями всех структурно подчиненных данному слову )-х слов, учета отношений S, S>, c накоплением относительных поправок <3, и коррекции исходных значений слов « а эту величину. Выбранная для реализации структура характеризуется числом слон (элементов) структуры N, числом уровней У, числом элементом на каждом уровне m — 2Y+ l. Ветви структуры подразделяются на левые, правые и диагональные.

В составе любой ветви не допускается повторение слов. Если I-е слово образует левую ветвь, то его номс р и номера структурно подчиненных ему )-x слов определяются с использованием соотношения (Y2 (Y) (2Y < I ) для правых ветвей — no соотношению (Y2 + Y) (2Y З) (1 (2) для диагоналей с использованием (1), (2) и соотнопц ния у 2 + (,1 (3)

Непосредственное сравнение S,

При этом увеличение 3; осуществляется занесением единицы на сдвигающий регистр, установкой в j-ю позицию и передачей ее на соответствующий вход регистра отношений, который работает в устройстве как N-входовый счетчик. Образование новых S; значений слов производится на сумматоре вычитанием из исходных значений слов содержи5

55 мого регистра отношений по выходу из i циклов. Сборка S слов в устройстве осуществляется на сумматоре, начиная со старших (леI вых) разрядов. Каждому S,. числу отводится столько разрядов, сколько их необходимо для представления номера уровня структуры, соответствующего данному числу.

Рассмотрим работу устройства на конкретном примере.

При исходной последовательности в шестнадцать слов число уровней выбранной структуры Y = 4, разрядность слова k = 2, общая длина последовательности К = 32 двоичных разряда. Соответственно, разрядность регистров 2, 3, 9, 11 и 12 равна тридцати двум, а число запоминающих элементов в накопителе 13 информации — тринадцати двоичным разрядам.

На входной регистр 2 принимается последовательность S (фиг. 4), состоящая из шестнадцати двухразрядных двоичных слов.

Реализация сжатия осуществляется в соответствии с режимами, приведенными в таблице параметров (см. таблицу) . Попарное сравнение выполняется в цикле. Число циклов равняется числу наборов пар по структуре (фиг. 3). На фиг. 5 показаны все возможные в принятой структуре наборы. Таких наборов — девять. Состав каждого из них отмечен в правой части таблицы «звездочками». Например, слову S структурно подчинены все слова последовательности, поэтому в одноименном наборе — пятнадцать пар, набор S образуется двумя парами (j — 4. 9), набор S, содержит восемь пар (j == 5, 6, 7, 10, 11, 12, 13, 14) и т. д. По номеру цикла, который формируется на счетчике 6 циклов, определяется смещение i ãî слова для его нормализации и последующей передачи на сумматор 9. Одновременно нормализованное i-e слово передается на выходной регистр 12, где сохраняется в течение цикла и используется для прямого восстановления на сумматоре на каждом шаге.

Каждый цикл подразделяется на шаги по числу пар в наборе. Количество шагов и номера j õ составляющих в парах определяются в блоке 14 с использованием соотношений (I) — (3). По номеру j-го слова на счет чике 5 шагов формируются параметры сдви. га (см. таблицу), которые передаются на счетчик 6 сдвигов для управления нормализацией I-х слов. В каждом цикле сравнения по сигналам блока 1 синхронизации с входного на сдвигающий регистр 3 по информационным шинам для восстановления передается исходная последовательность чисел.

Первоначально сравниваются пары набора

S.. Здесь отношению S;

Ночер уро яя

2,4,6,8 10,12,14,16,18,20,22,2

26,28,30

Р— 3 я 2 О,9

2 5,6,7,10,11,12,13,14

3 8, 15

5 10

6 11,12,13

7 14

8 15

О - 2

2 8,18

10,12,14,20,22,24,26,28

О - 2

6 16,30

8 18

Π— 2

Π— 1

10 20

Π— 1

12 22,24,26

0 —. !

Π— 1

14 28

16 30

Π— 1

0 — О!

1О

Π— О

22

О -, О

12

0-0

Π— О

26

14

П-:0

l3

О -. О

30 вую часть таблицы на фиг, 5). Далее сравнивают слова набора S Соответственно увеличивают на единицу поправку Я,, становящуюся равной двум. В наборе S не обнаруживается отношений S, S> è значения поправок остаются без изменений. В наборе этому отношению соответствует пара j = 8 и т. д. до завершения циклов сравнения. Значения относительных поправок представлены на фиг. 5 справа внизу. Непосредственное устранение избыточности производится на сумматоре вычитанием из исходных значений слов значений поправок, накопленных на регистре отношений. Слова с новыми значениями без избыточности сцепляются на сумматоре в старших разрядах. Так как сумматор (по выходу) не имеет в устройстве прямой связи с входами сдвигающего регистра, то перед началом сборки его содержимое с новыми значениями слов передается на выходной регистр 12, выполняющий функцию промежуточного звена. Каждое S (фиг. 6) принимает значение в пределах от нуля до значения номера уровня Y структуры. Для их хранения в порядке следования необходимы 2,2,2,2, 1, 1,1, 1, 1,0,0,0,0,0,0, 0 двоичных разрядов (см. таблицу). При размещении S; в соответствующих этим значениям позициях в блоке 14 вырабатывается присвоенный данному слову Y номер уровня структуры. По этом номеру в блоке 8 наименьшего целого определяется разрядность S,, значение которой далее суммиру1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 2 ется в сумматоре 7 и передается на счетчик сдвига, управляющий смещением слов. Параметры b сдвига приведены в таблице.

Так, S, отводят тридцать второй и тридцать первый разряды сумматора поэтому его передают без сдвига (b. = О). S, предназначаются тридцатый и двадцать девятый разряды, для чего он сдвигается на два разряда (b, = 2). Затем сцепляется S, со сдвигом

10 на четыре разряда (b = 4) и т. д. Наращивание величины сдвига в позиции обусловлено тем, что после выделения текущего слова оно располагается в старших разрядах сдвигающего раегистра. После выделения слов в устройстве предусматривается вос13 становление содержимого сдвигающего регистра, для это о сохраняемого на выходном регистре. Окончательный результат сжатия представлен на фиг. 7. Длина сжатой последовательности при выбранной для реализации структуре на девятнадцать разрядов короче исходной. Для ее хранения необходимы не тридцать два двоичных запоминающих элемента, а тринадцать, поэтому разрядность накопителя 13 информации, в который с сумматора через выходной регистр погружается информация, в устройстве принимается равной тринадцати.

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

1381564

Фор.чу.га изобретения

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

20 счетчика, третий выход второго регистра соединен с вторым входом третьего регистра, выход первого сумматора соединен с третьим входом четвертого регистра, первый и второй выходы которого соединены соответственно с четвертыми входами второго регистра и пятым входом первого сумматора.

1381564

Фиг. 5

138!564

Фиг. 7

Составите.чь В. Бородин

Рс акгор Л Огар Тскрсд И. Верес Корректор А. Зимокосоа . 3а кал 826 48 Тираж 558 11одписное

l3lll1l1fll1 Государственного комитета СССР по дсчам изобретений и открытий

l 13035, Мосина, Ж - 35, Раушская наб., д. 415

31роичводствснюополиграфическое предприятие, г. Ужгород, ул. Проектная, 4