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

СОЮЗ СОЬЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ЯО 1381564 А 1 А)4 б 08 С 15 ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(53) 621.398 (088.8) ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) УСТРОИСТВО ДЛЯ СЖАТИЯ ДАННЫХ(57) Изобретение относится к области цифровой вычислительной техники и может быть использовано в системах хранения информации. Устройство содержит блок 1 синхронизации, первый 2 и второй 3 регистры, первый 4, третий 5 и второй 6 счетчики, второй сумматор 7, блок 8 определения наименьшего целого, первый сумматор 9, компаратор 1 О, третий 11 и четвертый 12 регистры, накопитель 13, формирователь 14 сигнала на. правления сжатия. Устранение избыточности реализуется посредством сравнения между собой значений слова со значениями слов, структурно подчиненных этому слову, накопления относительных поправок и коррекции исходных значений слов на эту величину. В результате появляется возможность значительно (более чем в 2 раза) сократить требуемый объем памяти и сжимать повторяющиеся слова, 7 ил., 1 табл.5 1 О 15 20 25 30 35 40 45 50 55 Изобретенис относится к цифровой вычислительной технике и может быть использовано в системах хранения информации.Цель изобретениярасширение области применения устройства путем сжатия повторяющихся слов.Нд фиг. приведена функциональная схема устройства; на фиг. 2 - функциональная схема блока формирования; на фиг. 3-7 - таблицы, иллюстрирующие работу устройства.Устройство (фиг.) содержит блок 1 синхронизации, первый 2 и второй 3 регистры, первый 4, третий 5 и второй 6 счетчики, второй сумматор 7, блок 8 определения наименьшего целого, первый сумматор 9, компараторО, третий 11 и четвертый 12 регистры, накопитель 13 и формирователь4 сигнала направлении сжагияформирователь 14 (фиг. 2) включает синхронизатор5, счетчики 16 19, формирователь 20 сдвига, счетчик 21, сумматоры 22 24, триперы 25- 27, дешифратор 28 и счетчики 29 и 30.Устранение избыточности реализуется а устройстве посредством сравнения значений - слов со значениями всех структурно подчиненных ддному слову 1-х слов, учета отношений 5,( ,(, с накоплением относительны поправок Ю, и коррекции исходных значений словд эту величину. Выбранная для реализации структура характеризуется числом слов (элементов) структуры 11, числом уровней , числом элементом на каждом уровне гп - 2+ . Ветви структуры юдразделяются на левые, правые и диагональные. В составе любой ветви не допускается повторение слов. Если -е слово образует левую ветвь, то его смс р и номера структурно подчиненных ему )- слов определяются с использованием соотношения(2 ( Г) ( (1) для правых ветвей - по соотношению(У 2У) (2З) ( (2) для диагоналей с с.ьзовдне(1), (2) и соотнопц нияу 21 1 (3)Непосредственное сравнение ,Б производится в старших (левых) разрядах сумматора. Для этого ,)-е составляющие пар наборов нормализуются на сдвгающем регистре сдвигом влево на число разрядов, определяемое их смещением относительно нулевой позиции. Накопление относительных поправок , производится на регистре отношений в собственных для )-х слов позициях. При этом увеличение 3; осуществляется занесением единицы на сдвигающий регистр, установкой в 1-ю позицию и передачей ее на соответствующий вход регистра отношений, который рдботает в устройстве как 11-входовый счетчик. Образование новых ; значений слов производится на сумматоре вычитанием из исходных значений слов содержимого регистра отношений по выходу из циклов. Сборка 5, слов в устройстве осуществляется на сумматоре, начиная со старших (леРвых) разрядов. Каждому 5 с числу отводится столько разрядов, сколько их необходимо для представления номера уровня структу. ры, соответствующего данному числу.Рассмотрим работу устройства на конкретном примере.При исходной последовательности в шестнадцать слов число уровней выбранной структуры У = 4, разрядность слова )с = 2, общая длина последовательности К = 32 двоичных разряда. Соответственно, разрядность регистров 2, 3, 9, 11 и 12 равна тридцати двум, а число запоминаюцих элементов в накопителе 13 информации - тринадцати двоичным разрядам.На входной регистр 2 принимается последовательность 5 (фиг. 4), состоящая из шестнадцати двухразрядных двоичных слов. Реализация сжатия осуществляется в соответствии с режимами, приведенными в таблице параметров (см. таблицу). Попарное сравнение выполняется в цикле. Число циклов равняется числу наборов пар по структуре (фиг. 3). На фиг. 5 показаны все возможные в принятой структуре наборы. Таких наборов - девять. Состав каждого из них отмечен в правой части таблицы звездочками. Например, слову Я, структурно подчинены все слова последовательности, поэтому в одноименном наборе - пятнадцать пар, набор , образуется двумя парами (1 - 4.9), набор 5, содержит восемь пар (1 == 5,6,7,10,11,12,13,14) и т. д. По номеру цикла, который формируется на счетчике 6 циклов, определяется смещение -го слова для его нормализации и последующей передачи на сумматор 9. Одновременно норм ализова нное -е слово пе редается на выходной регистр 2, где сохраняется в течение цикла и используется для прямого восстановления на сумматоре на каждом шаге. Каждый цикл подразделяется на шаги по числу пар в наборе. Количество шагов и номера 1-х составляющих в парах определяются в блоке 14 с использованием соотноше. ний (1) - (3). По номеру )-го слова на счет чике 5 шагов формируются параметры сдви га (см. таблицу), которые передаются на счетчик 6 сдвигов для управления нормализацией ).х слов. В каждом цикле сравнения по сигналам блока 1 синхронизации с входного на сдвигающий регистр 3 по информационным шинам для восстановления передается исходная последовательность чисел. Первоначально сравниваются пары набора 5,. Здесь отношению ;5 удовлетворяют пары при 1 = 2, 8, 9. Учет этих отношений производится на регистре 11. В результате на регистре в позициях, соответствующих местоположению второго, восьмого, девятого слов, запоминаются единицы (см. пра,4,6,8 10,12,1 С,16,18,20,26,8,30 В,2 5,6,7,10,11,12,13,1 0,12,14,20,22,24,26,2 30- 2 6 11,12 0 О 14 2 3 вую часть таблицы на фиг, 5). Далее сравнивают слова набора 5,. Соответственно увеличивают на единицу поправку Ю становя. щуюся равной двум. В наборе 5 не обнаруживается отношений Я,5 и значения поправок остаются без изменений. В наборе этому отношению соответствует пара 1 = 8 и т. д. до завершения циклов сравнения. Значения относительных поправок представлены на фиг. 5 справа внизу. Непосредственное устранение избыточности производится на сумматоре вычитанием из исходных значений слов значений поправок, накопленных на регистре отношений. Слова с новыми значениями без избыточности сцепляются на сумматоре в старших разрядах. Так как сумматор (по выходу) не имеет в устройстве прямой связи с входами сдвигающего регистра, то перед началом сборки его содержимое с новыми значениями слов передается на выходной регистр 12, выполняющий функцию промежуточного звена. Каждое 5, (фиг. 6) принимает значение в пределах от нуля до значения номера уровня 1 структуры. Для их хранения в порядке следования необходимы 2, 2, 2, 2, 1, 1, 1, 1, 1, О, О, О, О, О, О, О двоичных разрядов (см. таблицу). При размещении Я; в соответствующих этим значениям позициях в блоке 14 вырабатывается присвоенный данному слову У номер уровня структуры. По этом номеру в блоке 8 наименьшего целого определяется разрядность Я значение которой далее суммиру,2,3,4,5,6,7,8,9,10,11,12,13,14,15 2 ется в сумматоре 7 и передается на счетчик сдвига, управляющий смещением слов. Параметры Ь сдвига приведены в таблице.Так, 5, отводят тридцать второй и тридцать первый разряды сумматора поэтому его передают без сдвига (Ь, = О). 5, предназначаются тридцатый и двадцать девятый разряды, для чего он сдвигается на два разряда (Ь, = 2). Затем сцепляется Я, со сдвигом на четыре разряда (Ь 1 = 4) и т. д. Наращивание величины сдвига в позиции обусловлено тем, что после выделения текущего слова оно располагается в старших разрядах сдвигающего раегистра. После выделения слов в устройстве предусматривается вос.3 становление содержимого сдвигающего регистра, для этоо сохраняемого на выходном регистре. Окончательный результат сжатия представлен на фиг. 7. Длина сжатой последовательности при выбранной для реализации структуре на девятнадцать разрядов короче исходной. Для ее хранения необходимы не тридцать два двоичных запоминающих элемента, а тринадцать, поэтому разрядность накопителя 13 информации, в который с сумматора через выходной регистр погружается информация, в устройстве принимается равной тринадцати.Таким образом, введение в предлагаемое устройство формирователя сигнала направления сжатия позволяет расширить область его применения для компактного представления данных.Форму,ги изобретения Устройство для сжатия данных, содержащее блок синхронизации, первый, второй, третий, четвертый, пятый, цгестой и седьмой выходы которого соединены с первыми входами соотвегственно первого, второго, третьего регистров, первого сумматора, компара. тора, четвертого регистра и накопителя, первый счетчик, псрвыи и второй выходы которого соединены с первыми входами соответственно второго и третьего счетчиков, блок определения наименьшего целого, выход которого соединен с первым входом второго сумматора, выход которого соединен с вторым входом второго счетчика, третий вход которого подклк)чен к выходу третьего счетчика, выход второго счетчика соединен с вторым входом второго регистра, третий вход которого подключен к выходу первого регистра, первый и второй выходы второго регистра соединены с вторыми входами соответственно первого сумматора и четверто-о регистра, первый выход которого соединен с вторым входом накопителя, первый и второй выходы компаратора соединены соответственно с входом запуска блока синхронизации и третьим входом первого сумматора, второй вход первого регистра является входом устройства, выход третьего регистра соединен с четвертым входом первого сумматора, отличающееся тем, что, с целью расширения области применения путем сжатия повторяющихся слов, в него введен формирователь сигнала направления сжатия, первый, второй, третий, четвертый и пятый выходы которого соединены с соответствующими входами группы входов изменения тактовой частоты блока синхронизации, восьмой и девятый выходы которого соединены соответственно с первым и вторым входами формирователя сигнала направления сжатия, шестой, седьмой, восьмой и девятый выходы которого соединены соответственно с входом первого счетчика, вторым входом третьего счетчика, входом блока определения наименьшего целого и вторым входом второго сумматора, десятый выход блока синхронизации соединен с четвертым входом второго 20 счетчика, третий выход второго регистрасоединен с вторым входом третьего регистра, выход первого сумматора соединен с третьим входом четвертого регистра, первый и второй выходы которого соединены соответственно с четвертыми входами второго регистра и пятым входом первого сумматора.Составитель В. БородинРедакгор Л Огар Текрсл И, Верес Корректор А. ЗимокосовВаказ 826,48 Тираж 558 11 одписноеБИИИПИ Государственного комитета СССР по девам изобретений и открытий113035, Москва, Ж 35, Рау шская наб., д. 451 роиводствснно.полиграфическое предприятие, г, Ужгород, ул. Гроектная, 4