Устройство для сжатия данных Советский патент 1988 года по МПК G08C15/00 

00

сх

СП

05

20

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

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

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

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

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

Устранение избыточности реализуется в устройстве посредством сравнения значений i-x слов со значениями всех структурно подчиненных данному слову j-x слов, учета отношений , с накоп;1ением относительных поправок и коррекции исходных значений слов па эту ве;1ичину. Выбранная для реализации структура характеризуется числом слов (элементов) структуры N, числом уровней Y, числом -:)лементом на каждом уровне m 2Y+1. Ветви структуры подразделяются на левые, правые и диагональные. В составе любой ветви не допускается повторение слов. Если i-e слово образует левую ветвь, то ei o помер и номе)а структурно подчиненных ему j-x слов определяются с исполь зование.м соотношения

i - (Y2 + Y) 4 (2Y + 1)N, для правых ветвей - по соотношению

i (Y2 + Y) + (2Y + 3)N, для диагоналейс псиользоваппем

(2) и соот}1С)шения

i Y2 + .

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

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

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

На входной регистр 2 принимается последовательность S (фиг. 4), состоящая из шестнадцати двухразрядных двоичных слов. Реализация сжатия осуществляется в соответствии с режимами, нриведеиными в таблице параметров (см. таблицу). Попарное сравнение выполняется в цикле. Число циклов равняется числу наборов пар по струк- 25 туре (фиг. 3). На фиг. 5 показаны все возможные в принятой структуре наборы. Таких наборов - девять. Состав каждого из них отмечен в правой части таблицы «звездочками. Например, слову S структурно подчинены все слова последовательности, поэтому в одноименном наборе - пятнадцать пар, набор S, образуется двумя парами (J - 4.9), набор Sj содержит восемь пар (J - 5,6,7, 10, 11, 12, 13, 14) и т. д. По номеру цикла, который формируется на счетчике 6 циклов, определяется смещение i-ro слова для его нормализации и последующей передачи на сумматор 9. Одновременно нормализованное i-e слово передается на выходной регистр 12, где сохраняется в течение цикла и используется для прямого восстановления на сум.маторе на каждом шаге. Каждый цикл подразделяется на шаги по числу пар в наборе. Количество шагов и номера j-x составляющих в парах определяются в блоке 14 с использованием соотношеизводится в старших (левых) разрядах сум- 45 О - ( номеру j-ro слова на счет чике 5 шагов формируются параметры сдвига (см. таблицу), которые передаются на счетчик 6 сдвигов для управления нормализацией j-x слов. В каждом цикле сравнения по сигналам блока 1 синхронизации с вход35

(П (2)

40

(3) Непосредственное сравнение проматора. Для этого i, j-e составляющие пар наборов нормализуются на сдвигающем регистре сдвигом влево на число разрядов, определяемое их смещением относительно нулевой позиции. Накопление относительных

поправок Si производится на регистре отно- 50 ного на сдвигающий регистр 3 по информашений в собственных для j-x слов позициях. При этом увеличение Sj осуществляется занесением единицы на сдвигающий регистр, установкой в j-ю позицию и передачей ее на соответствующий вход регистра отношений.

ционным шинам для восстановления передается исходная последовательность чисел. Первоначально сравниваются пары набора So. Здесь отношению удовлетворяют пары при j 2, 8, 9. Учет этих отношений

который работает и устройстве как N-БХОДО- производится на регистре 11. В результате

вый счетчик. Образование новых S{ значений слов производится на сумматоре вычитанием из исходных значений слов содержина регистре в позициях, соответствующих .местоположению второго, восьмого, девятого слов, запоминаются единицы (см. прационным шинам для восстановления передается исходная последовательность чисел. Первоначально сравниваются пары набора So. Здесь отношению удовлетворяют пары при j 2, 8, 9. Учет этих отношений

на регистре в позициях, соответствующих .местоположению второго, восьмого, девятого слов, запоминаются единицы (см. правую часть таблицы на фиг. 5). Далее сравнивают слова набора 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, О двоичных разрядов (см. таблицу). При размепхении S в соответствующих этим значениям позициях в блоке 14 вырабатывается присвоенный данному слову Y номер уровня структуры. По этом номеру в блоке 8 наименьшего целого определяется разрядность S, значение которой далее суммиру

Q 5

0

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

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

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

4,9

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

8,15

9

10

11,12,13

U

15

4,20,22,24,26,28

6

2

4

6

7

8

9

10

11

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

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

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

риг.2

Фиг.З

ФигЛ

Фиг. 5

Фиг. 6