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

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

Цель изобретения - повышение коэф- 5 лов. Нормализация j-x слов осуществляется на регистре 3 аналогично нормализации i-x слов. Непосредственное сравнение S, производится вычитанием из содержимого сумматора 9 зна- 0 чения нормализованного на регистре 3 i-ro слова. Отношение имеет место быть при , 4, 5, 6. Относительная поправка 6. накапливается на регистре 11. Потребность регистрации

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

На чертеже приведена функциональная схема предлагаемого устройства.

Устройство для сжатия данных содержит блок 1 синхронизации, первый

регистр 2, второй регистр 3 (-выполненный в виде сдвигающего регистра), пер- - отношений выявляется в компараторе вый 4 и второй 5. счетчики, блок 6 оп- 10 по результату сравнения. При нали- ределения наименьшего целого, первый сумматор 7, третий счетчик 8, второй сумматор 9, компаратор 10, третий 11 и четвертый 12 регистры и накопитель 13. 20

Устранение избыточности представления реализуется в устройстве соотчии такой потребности содержание регистра 11 передается на сумматор 9, где увеличивается на единицу, а затем возвращается обратно. В рассматриваемом цикле 4. Новое S. слово получается уменьшением исходного значения на величину его относительной поправки. Это выполняется на сумматоре 9 передачей поправки с регистра 11 на сумматор 9 дополнительным кодом. В указанном цикле новое значение слова

несением значений слов посредством групповых операций попарного сравнения

S -S- при учетом отношений S Sj с накоплением относительной поправки 5; и коррекцией значений слов- на эту величину.

Работу устройства рассмотрим на конкретном примере, в котором число слов полного словаря , разрядность слова , исходная длина последовательности двоичного разряда. Соответственно разрядность регистров 2 и 3 равна двадцати четырем, сумматора 9 и регистра 11 - трем, регистра 12 и накопителя 13 - семнадцати двоичным разрядам.

. На входной регистр 2 по сигналу

блока 1 синхронизации принимается по- следовательность S, состоящая из восьми произвольно расположенных относительно друг друга трехразрядных дво- ичных слов. Попарное сравнение выполняется в цикле на сумматоре 9. Количество циклов i в примере по числу наборов пар равно семи. По номеру цикла, который формируется на счетчике 4 циклов, и с учетом разрядности слов определяется адрес i-ro слова в исходной последовательности для его нормализации на сдвигающем регистре 3 в

старшие (левые) разряды и последую- 5 этора передается в двадцать второй щей передачи на сумматор 9 для срав- разряд сдвигающего регистра, сдвига- нения.ется (В 2) на два разряда влево и по

Каждый цикл подразделяется на шаги информационным шинам направляется на по числу слов в последовательности выходной регистр. Следующему 5„ предот данного слова справа. Номера шагов формируются на счетчике 5. В начале циклов содержание счетчика 5 обновляется текущим значением счетчика цик- отношений выявляется в компараторе 10 по результату сравнения. При нали- 0

5

30

35

40

. 5

чии такой потребности содержание регистра 11 передается на сумматор 9, где увеличивается на единицу, а затем возвращается обратно. В рассматриваемом цикле 4. Новое S. слово получается уменьшением исходного значения на величину его относительной поправки. Это выполняется на сумматоре 9 передачей поправки с регистра 11 на сумматор 9 дополнительным кодом. В указанном цикле новое значение слова

s; 0.

Для образования пар и выполнения сравнения слова из своего исходного положения нормализуются на регистре 3. Сжатые слова собираются на реги- . стре 12 и устанавливаются в тех его позициях, которые соответствуют их расположению в новом представлении, без избыточности. Определение параметров сдвига производится в блоке 6 и сумматоре 7. Первый из них реализует функцию наименьшего целого от log(i+ +1), а второй - формирует адрес S-, передавая его в качестве параметра на счетчик 8. Направление сдвига определяется содержанием сумматора 7, которое первоначально задается равным

К в дополнительном коде.

1

Каждое 5 слово может принимать значение от нуля до i . Для хранения S слов в порядке следования необхо- JQ ДИМЫ О, 1, 2, 2, 3, 3, 3, 3 двоичных разрядов. Например, 5 слово хранению не подлежит, слову S отводится только один старший разряд выходного регистра. Для этого его значение с сумназначаются двадцать третий и двадцать второй разряды. Смещение этого слова . Затем сдвигается 5 на два разряда вправо и т.д. Длина сжатого словаря короче на семь разрядов исходной длины. Для его хранения необходимы не двадцать четыре, а семнадцать двоичных запоминающих элементов, поэтому разрядность регистра 12

наименьшего целого, третий, четвертый, пятый, шестой, седьмой и восьмой выходы блока синхронизации соединены с вторым входом первого регистра и первыми входами соответственно второго регистра, второго счетчика, блока определения наименьшего целого, первого и второго сумматоров, девятый и десядинен с первым входом третьего счетчика, первый, второй и третий выходы . первого счетчика соединены с вторыми входами соответственно второго счеттый выходы блока синхронизации соеди- и накопителя 13 информации, в который 10 иены соответственно с первьм и вторым . погружается словарь, при принима- входами компаратора, одиннадцатый и ется равной семнадцати.двенадцатый выходы блока синхронизаТаким образом, предлагаемое уст- ции соединены с первьии входами соот- ройство для сжатия данных позволяет ветстаенно третьего.и четвертого ре- расширить о,бласть применения компакт- 15 гистров, выход второго счетчика сое- ного представления полных словарей. При этом благодаря обеспечению независимости местоположения слова в последовательности от его содержания число вариантов представляемой информа- 20 чика, третьего счетчика и блока определения наименьшего целого, выход которого соединен с вторым входом первого сумматора, выход первого сумма- Использование известного устрой- тора соединен с третьим входом треть- ства дает число вариантов представля- gpo счетчика, выход которого соединен

2 К f

емой информации только , с вторым входом второго регистра, выход компаратора соединен с вторым входом второго сумматора, первый выход которого соединен с третьим вхо- 3Q дом второго регистра, первый и второй выходы второго регистра соединены соответственно с третьим входом второго сумматора и вторым входом четвертого регистра, выход которого соединен с

ции равно числу перестановок К-раз- рядных слов (чисел) словаря Р .

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

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

Редактор И.Шулла

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

Техред А.Кравчук Корректор Н.Король

Заказ 1457/50Тираж 544 Подписное

ВРШИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д. 4/5

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

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

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

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