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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 09) 01) ОПИСАНИЕ ИЗОБРЕТЕНИК АВТОРСКОМУ СВйдЕТЕЛЬСТВУ 886243/249.03.853.04.87.(21) (22) (46) (75) (53) ент етс л. В его 88.8) итсяько н ССР 83.Шипи- апоми- инфор- машипорядк словар синхро регистр ки, бло целого, счетчик ратор 1 регистр избыточ(54) УСТРОЙ (57) Изобре вычислитель ,использован ных для хра формации, С ИЯ ДАННЫХ ся к цифро может быт обработки объемов и ения коэфф ЖА носи ениеой те ного ике н -в дную ия о стемах льши вели ени с целью ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетельство999471, кл. С 08 С 15/00, 1Бузулов 10,А., Буренков Н.Глов Н,Н. Некоторые структурынающих устройств с уплотнениемации. - Управляющие системыны, 1983, В 1, с.21-24. сжатия в устроистве обеспечинезависимость местоположения их содержания, в результате я каждого сжатого слова отвотолько двоичных разрядов, скообходимо для представления вого номера данного слова вУстройство содержит блок 1 изации, первый 2 и второй 3 ы, первый 4 и второй 5 счетчик 6 определения наименьшего первый сумматор 7, третий 8, второй сумматор 9, компа- О, третий 11 и четвертый 12 ы и накопитель 13, Устранение ности осуществляется путем по- сравнения слов, образующих последовательность, и опредетносительной поправки и коррекв на эту величину. 1 ил.разрядам. 40 1 130574 Изобретение относится к цифровой вычислительной технике и может бытьиспользовано в системах хранения информации,Цель изобретения - повышение коэффициента сжатия информации за счет обеспечения независимости местоположения слова в входной последовательности от его содержимого.На чертеже приведена функциональ О ная схема предлагаемого устройства.Устройство для сжатия данных содержит блок 1 синхронизации, первый регистр 2, второй регистр 3 (выполненный в виде сдвигающего регистра), пер вый 4 и второй 5. счетчики, блок 6 определения наименьшего целого, первый сумматор 7, третий счетчик 8, второй сумматор 9, компаратор 10, третий 11 и четвертый 12 регистры и накопитель 13, 20Устранение избыточности представления реализуется в устройстве соотнесением значений слов посредством групповых операций попарного сравнения25ББпри Ос 1 сИ - 2 Ы 3 с 1-1 учетом отношений БЯ с накоплением относительной поправки о и коррекцией значений слов на эту величину.Работу устройства рассмотрим на конкретном примере, в котором число слов полного словаря И=8, разрядность слова К=З, исходная длина последовательности К=24 двоичного разряда. Соотнетственно разрядность регистров 2 35 и 3 равна двадцати четырем, сумматора 9 и регистра 11 - трем, регистра 12 и накопителя 13 - семнадцати двоичным На входной регистр 2 по сигналу блока 1 синхронизации принимается последовательность Б, состоящая из восьми произвольно расположенных относительно друг друга трехразрядных двоичных слов. Попарное сравнение выполняется в цикле на сумматоре 9. Количество циклов 1 в примере по числу наборов пар равно семи, По номеру цикла, который формируется на счетчике 4 циклов, и с учетом разрядности слов определяется адрес 1-го слова в исходной последовательности для его нормализации на сдвигающем регистре 3 в старшие (левые) разряды и последующей передачи на сумматор 9 для сравнения.Каждый цикл подразделяется на шаги по числу слов в последовательности 6 2от данного слова справа, Номера шагов формируются на счетчике 5, В начале циклов содержание счетчика 5 обновляется текущим значением счетчика циклов. Нормализация 3 -х слов осуществляется на регистре 3 аналогично нормализации 1-х слов. Непосредственное сравнение Я Я производится вычита 1нием из содержимого сумматора 9 значения нормализованного на регистре 3 1-го слова. Отношение Б Я имеет место быть при 3=2, 4, 5, 6. Относительная поправка. О. накапливается на1регистре 11. Потребность регистрации отношений выявляется в компараторе 10 по результату сравнения. При наличии такой потребности содержание регистра 11 передается на сумматор 9, где увеличивается на единицу, а затем возвращается обратно. В рассматриваемом цикле 8 =4. Новое Б, слово полу 1чается уменьшением исходного значения на величину его относительной поправки. Это выполняется на сумматоре 9 передачей поправки с регистра 11 на сумматор 9 дополнительным кодом. В указанном цикле новое значение слова оДля образования пар и выполнения сравнения слова из своего исходного положения нормализуются на регистре 3, Сжатые слова собираются на регистре 12 и устанавливаются в тех его позициях, которые соответствуют их расположению н новом предстанлении, без избыточности. Определение параметров сдвига производится в блоке 6 и сумматоре 7. Первый из них реализует функцию наименьшего целого от 1 о 8(1+ +1), а второй - формирует адрес Б;, передавая его в качестве параметра на счетчик 8, Направление сдвига определяется содержанием сумматора 7, которое первоначально задается равным К н дополнительном коде.1Каждое 5 слово может принимать1Фзначение от нуля до. Для хранения 5 слов в порядке следования необходимы О, 1, 2, 2, 3, 3, 3, 3 двоичных разрядов. Например, 5 слово хранению не подлежит, слову 5 отводится только один старший разряд выходного регистра. Для этого его значение с сумматора передается н двадцать второй разряд сднигающего регистра, сдвигается (В, =2) на два разряда влево и по информационным шинам направляется на выходной регистр. Следующему 5 пред13057 46 формула изобретения Составитель В.БородинТехред А.Кравчук Корректор Н.Король Редактор И,Шулла Заказ 1457/50 Тираж 544 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб д. 4/5Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 зназначаются двадцать третий и двадцать второй разряды. Смещение этого слова В =О, Затем сдвигается 5 на два разряда вправо и т.д. Длина сжатого словаря короче на семь разрядов исходной длины. Для его хранения необходимы не двадцать четыре, а семнадцать двоичных запоминающих элементов, поэтому разрядность регистра 12 и накопителя 13 информации, в который 10 погружается словарь, при К=З принимается равной семнадцати.Таким образом, предлагаемое устройство для сжатия данных позволяет расширить область применения компакт ного представления полных словарей. При этом благодаря обеспечению независимости местоположения слова в последовательности от его содержания число вариантов представляемой информа ции равно числу перестановок К-раз/ к рядных слов (чисел) словаря Р -2 Использование известного устройства дает число вариантов представля емой информации только Р=2якУстройство для сжатия данных, со- М держащее компаратор, блок синхронизации, первый и второй выходы которого соединены с первыми входами соответственно первого счетчика и накопителя, первый вход первого регистра яв ляется входом устройства, о т л и - ч а ю щ е е с я тем, что, с целью повышения коэффициента сжатия, в устройство введены второй, третий и четвертый регистры, второй и третий сче тчики, сумматоры и блок определения наименьшего целого, третий, четвертый,пятый, шестой, седьмой и восьмой выходы блока синхронизации соединены свторым входом первого регистра и первыми входами соответственно второгорегистра, второго счетчика, блока определения наименьшего целого, первогои второго сумматоров, девятый и десятый выходы блока синхронизации соединены соответственно с первым и вторым .входами компаратора, одиннадцатый идвенадцатый выходы блока синхронизации соединены с первыми входами соответственно третьего.и четвертого регистров, выход второго счетчика соединен с первым входом третьего счетчика, первый, второй и третий выходы .первого счетчика соединены с вторымивходами соответственно второго счетчика, третьего счетчика и блока определения наименьшего целого, выходкоторого соединен с вторым входом первого сумматора, выход первого сумматора соединен с третьим входом третьего счетчика, выход которого соединенс вторым входом второго регистра, выход компаратора соединен с вторымвходом второго сумматора, первый выход которого соединен с третьим входом второго регистра, первый и второйвыходы второго регистра соединены соответственно с третьим входом второгосумматора и вторым входом четвертогорегистра, выход которого соединен свторым входом накопителя, второй вы"ход второго сумматора соединен с вторым входом третьего регистра, выходкоторого соединен с-четвертым входомвторого сумматора, выход первого регистра соединен с четвертым входомвторого регистра.