Устройство для сжатия и восстановления информации

 

Союз Советсиил

Социалистичесиик республик

Oh ИСАНИ Е (н)934523

ИЗО6РЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6l ) Дополнительное к авт. свид-ву— (22) Заявлено 10.10.80 (21) 2992319/18-14 с присоединением заявки М— (5l)M. Кл.

G 08 С 15/06

60аудэрстваильМ камнтат

СССР пе делам лэабретенил и еткритнй (23) Приоритет

Опубликовано 07.06.82. Бюллетень М 21 (53) УД К 62!.398 (088.8) Дата опубликования описания 07.06.82

ВСВМЮЗИ a% в А %ИТНО-!

3 „„„„„ „,,Ä 13

ЬИЬАНОТЕКА (72) Автор. изобретения

А. В. Кайма (71) Заявмтель (54) УСТРОЙСТВО ДЛЯ СЖАТИЯ И ВОССТАНОВЛЕНИЯ

ИНФОРМАЦИИ

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

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

15 вычисления кодового расстояния, входы которого соединены с выходом задающего генератора и входом блока псевдослучайного преобразования, вход последнего соединен с одним иэ входов регистра числа, другие входы которого соединены соответственно с выходом запоминающего блока, регистра сдвита и двумя выходами блока вычисления кодового расстояния !1).

К недостаткам указанного устройства следует отнести низкий коэффициентвсжатия информа ции, большой объем оборудования на бит сжатой информации и высокую стоимость.

Наиболее близким к предлагаемому является устройство для сжатия информации, содержащее и-образный входной регистр сдвига, вход которого соединен с информационным входом устройства, группы элементов И, выходной (п+ 1)-разрядный регистр сдвига, датчик случайных чисел, вход которого соединен с первым выходом блока управления, а выходы — с соответствующими входами схемы сравнения, (n+ 1)-разрядный счетчик н группу элементов ИЛИ, в которой выход каждого элемента ИЛИ соединен с одним из входов последующего, разрядные выходы входного сдвигающего регистра соединены с первыми входами элементов И первой группы, вторые входы которой соединены с вторым выходом блока управления, выходы элементов И первой группы соединены с соответствующими тходами счетчика, выходы счетчика соединены

: соответствующими входами схемы сравне3 93452 ния и с первыми входами элементов И второй группы, вторые входы которых соединены с третьим выходом блока управления, а третьи— с выходами элементов ИЛИ, вторые входы которых соединены с четвертым выходом, блока управления, выходы элементов И второй группы соединены с входами выходного сдвигающего регистра, выходы схемы сравнения соединены с первыми входами элементов И третьей группы, вторые входы которых сое- 1й динены с пятым выходом блока управления, а выходы — с вторыми разрядными входами счетчика, начиная с второго разряда (2).

К недостаткам известного устройства следует отнести низкий коэффициент сжатия инфор- 15 мации и большой объем оборудования.

Цель изобретения — повышение эффективно сти сжатия информации.

Поставленная цель достигается тем, что в устройство, содержащее блок памяти информа- 211 цнн, первый выход которого соединен с первым выходом устройства, блок сравнения информационных. комбинаций, регистр комбинаций, регистр памяти постоянных информационных комбинаций, регистр памяти единиц, блок управления и блок элементов ИЛИ„ введены формирователь пакетов первичной информации, формирователь инфо1 мационных комбинаций,. регистр памяти адрес и признака информационных комбинаций, преобразователь пакетов неупорядоченной информации в коды и блок выдачи информации, первый вход формирователя пакетов первичной информации подключен к первому входу устройства, первый, второй, третий, четвертый и пятый выходы формирователя пакетов первичной информации соединены соответственно с первым входом преобразователя пакетов неупорядоченной информации в коды, первым входом блока памяти информации, первым входом блока сравнения информационных комбинаций, первым входом регистра адреса информационных комбинаций и первым входом блока управления, первый, второй, третий, четвертый и пятый выходы блока управления соединены соответственно с вторым входом формирователя пакетов первичной информации, объединенными вто.рым и третьим входами регистра памяти адреса и признака информационных комбинаций, вторым входом преобразователя пакетов неупорядоченной информации в коды, вто- 5О рым входом блока памяти информации и объединенными первыми входами регистра памяти постоянных информационных комбинаций и регистра памяти единиц, вторые входы которых соединены с вторым и третьим вхо- 55 дами устройства, выходы которых соединены с соответствующими входами формирователя информационных комбинаций, выход которо3 4 го соединен с первым входом блока выдачи ,информации и вторым входом блока сравнения информационных комбинаций, выход блока сравнения информационных комбинаций соединен с четвертым входом регистра памяти адреса и признака информационных комбинаций и через блок элементов ИЛИ с объединенными вторым входом блока управления и пятым входом регистра памятиадреса и признака информационных комбинаций, выход которого соединен с третьими входами формирователя пакетов первичной информации и блока памяти информации, второй, третий и четвертый выходы блока памяти информации соединены соответственно .с объединенными третьим входом блока управления и четвертым входом формирователя пакетов первичной информации, вторым входом блока выдачи информации и третьим входом преобразователя пакетов неупорядоченной информации в коды, первый и второй выходы которого соединены соответственно с четвертым входом блока памяти информации и третьим входом блока выпачи информации, первый, второй и третий выходы которого соединены соответственно с пятым входом формирователя пакетов первичной информации, пятым входом блока памяти информации и вторым выходом устройства.

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

Устройство для сжатия и восстановления информации содержит формирователь 1 пакетов первичной информации, блок 2 управления, регистр 3 памяти постоянных информационных комбинаций, регистр 4 памяти единиц, формирователь 5 информационных комбинаций, блок 6 сравнения информационных комбинаций, регистр 7 памяти адреса и признака информационных комбинаций, блок 8 элементов ИЛИ, блок 9 памяти информации, блок

10 выдачи информации, преобразователь 11 пакетов неупорядоченной информации в коды.

Формирователь 1 пакетов первичной информации предназначен для деления поступающей информации на пакеты возрастающей, убывающей, повторяющейся и неупорядоченной информации, а также для восстановления сжатой информации в пакеты первоначальной информации. Блок 2 управления предназначен для приема и передачи другим элементам устройства управляющих импульсов. Регистр 3 памяти постоянных информационных комбинаций предназначен для приема, хранения и выдачи постоянных комбинаций сжатой информации в формирователь 5.

Регистр 3 имеет возможность осуществлять сдвиги информации влево и вправо.

111

00010111

0010111

010111

5 934523 6

Постоянная Линейка сжатой информации -- даются по единицам сжатой информации, по- пакет и-разрядных комбинаций на все соче- ступающей из блока 9 и преобразователя 11. тания, сжатый в 2"-разрядную линейку. Преобразователь 11 предназначен для преНапример, пакет трехразрядных комбина- образования пакетов неупорядоченной информации в эквивалентные коды с меньшим чис01234567 лом разрядов. ,00001 11 1 Устройство работает следующим образом, .

00110011 От внешних источников на первый вход

0 1 0 1 0 1 0 1 устройства периодически поступает информа.

1© ция. Формирователь 1 путем сравнения смеж. содержит 24 разряда, а постоянная линейка ных комбинаций формирует сжимаемую и сжатой информации этого пакета содержит во- несжимаемую информации в переменные насемь разрядов (00010111). Количество разря- кеты. К сжимаемой информации относятся дов в начальных пакетах возрастающей или переменные пакеты, возрастающей, убываюубцвающей информации, относящееся к коли- 15 щей, повторяющейся и часть комбинаций нечеству разрядов соответствующей постоянной упорядоченной информации.. К несжимаемой ин. комбинации. сжатой информации или ее части, формации относится часть комбинаций.неупоесть коэффициент сжатия информации. рядоченной информации, комбинации которых систематически редко применяются. В пакетах

Регистр 4 памяти единиц предназначен для

gQ возрастающей информации ко инации столприейа, хранения и передачи едипщ в фон ) змещаются слева направо в порядке р ватель 5 который предназначен я фор возра„ания их эначенй, н„ример мнг.тнаннн настнмх слагасьнлх, образуюнпгхсл О 1 б О 2 б 7 2 3 4 у и результате псрсмножарлн постланной ломб" agwi""форма "на комб""а "ю е н 0010 0111 О! 101

Н е пршеден пример Чхразр"дрых ком- 0 1 0 1 1001 1 0 1 0 1ит.д . 2S

В пакетах убывающей информации комбн0 001111 н „нация размещаются слева направо в поряд.

0 0 1 l 0 O 1 1 — начальная информация (ком.ке убывания нх значений, например:

0 1 0 1 0 1 0 1 бинация на все сочетания)

0 0 0 1 0 1 1 1 — сжатая информация (посто- 30

11100 11.10 янная комбинация сжатой 10010 1000 1000 информации)... 1 1 0 1 0 0 1 0 1 1 1 0 0 H т.д. — комбинация единиц. В пакетах повторяющейся информации одна, — расширеннаяинформация две и более комбинаций пакета являются цо. (частные слагаемые, образую-SS вторяющимися, например: щиесяприперемножениипо- 0 0 0 0 0 0 0 0 0 0 стоянной комбинации сжатой 1 .1 1 1 1 1- 1 1

1 1 1 1 информациискомбинацией 1 1 1 1 1 О 0 0 0 0

11 11.00ОО

Блок.б сравнения информационных комбина-,щ 1 1 1 1 1 1 1 1 1 0000 ций выполнен, например, на элементах И, и 1 1 1 1 1 предназначен для сраврения комбинации фор- 11111 1? 110000 мирователя 1 с комбинациями формировате- . Для распознавания пакетов сжатой инфорл я 5. мации введены признаки: 00 — возрастаюРегистр 7 памяти адреса и признака инфор- м щая информация, 01 — убывающая информамационных комбинаций предназначен для фик- ция, 10 — повторяющаяся информация, 11 сации в соответствующих разрядах местополо- неупорядоченная информация, которые припижения комбинаций в формирователе, а. также сываются к комбинациям сжатой информадля запоминания признаков, определяющих ции. Число комбишщий в пакетах переменное. виды информации и части полей. Элементы SO Процесс сжатия пакетов информации осущестИЛИ блока 8 предназначены для записи при- вляетсяследующимобраэом.Формирователь ватель 1 знаков в старшие разряды регистра 7., подготовив пакет информации, информирует блок

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

SS

Блок 10 выдачи информации предназначен сли пакет относится к возрастающей, убыдля выдачи разрешений на пропуск комбина- Если па р ей бповто яющейся информации, то из фо ми ователя 5 в формирователь вающей или повтор щ фор

1 и внешним потребителям. Разрешения вы- блок 2 посылает формировате, ре р вателю 1, гист у

7 9345

3 и регистру 4 общую команду "Считать".

По этой команде из формирователя 1 считываются признак пакета информации и начальная комбинация первого пакета информации н передаются в соответствующие разряды регистра 7 и на входы блока 6. А иэ регистров

3 и 4 считываются постоянная комбинация сжатой информации и комбинация единиц и одновременно" передаются на входы формирователя 5, в котором переданная информация перемножается, образуя, таким образом, частные слагаемые (пакет расширенной информации), в которых содержатся и-разрядные комбинации íà все сочетания. С выходов формиро- . вателя 5 комбинации пакета расширенной информации передаются на соответствующие weменты блока 6 и на вход блока 10. На элементах И блока 6 производится сравнение начальной комбинации пакета формирователя 1 с комбинациями расширенной информа- 20 цни формирователя 5.

Элемент И блока 6, на котором произошло совпадение .начальной комбинации формирователя 1 с комбинацией расширенной информации формирователя 5, записывает единицы 33 через элементы ИЛИ блока 8 и непосредственно в соответствующие разряды признаков и поля регистра 7, а т;кже .в блок 2.

Единица поля определяет: адрес (местоположение) комбйнации в пакете расширеннноц информации блока 5, а единица признака .— часть поля регистра 7, в которую записана единица поля.

Едншща, записанная в блок 2, информирует последний о совпадении сравниваемых комбинаций. По, этим сведениям блок 2 вновь

3$ посылает на входы формирователя 1, регистра 3, регистра 4 общую команду "Считать".

По этой команде а3 формирователя 1 считывается вторая комбинация пакета и переда49, ется на входы блока 6, а из регистра 3 считывается постоянная комбинация сжатой информации иэ регистра .4, комбинация единиц и одновременно передаются на формирователь

5. Расширенная информация с выходов фор1$ мирователя 5 передается на блок 6, на элементах И которого осуществляется сравнение второй комбинации формирователя 1 с комбинацией расширенной информации формирователй 5.

SO

Элемент И блока 6, на котором,произошло совпадение сравниваемых комбинаций, вновь записывает две единицы в регистр 7, одна из которых указывает. адрес комбинации в пакете расширенной информации, другая — часть поля регистра 7, в которую записана единица поля. Если единица, определяющая адрес,комбинации в пакете расширенной информации, записана в ту часть поля регистра 7, в которую записана единица поля предыдущей комбинации сжимаемого пакета, то в разряде данного признака единичный уровень не меняется.. Если единица, определяющая адрес комбинации в пакете расширенной информации записана в другую часть поля регистра 7, то единичныи уровень признаков, определяющий ,часть поля регистра 7, через элементы ИЛИ блока 8 записывается в. другой разряд признаков регистра 7.

Процесс сжатия продолжается до тех пор, пока в сжимаемом пакете формирователя 1 не останется ни одной комбинации.

После считывания из формирователя 1. последней комбинации сжимаемого пакета информации блок 2 посылает регистру 7 команду Считать". По этой команде в отведенную часть блока 9 иэ регистра, передается часть или вся комбинация сжатой информации.

Если в разрядах признаков, определяющих поля регистра 7, содержатся все единицы, то. йз регистра 7 считываются признаки и содержимое всех полей регистра 7. Если s разря.дах признаков регистра 7 содержится одна, две или три смежные единицы, то нз регистра

7 считываются признаки: и содержимое первых, вторых и третьих частей поля переменной комбинации сжатой информации; содержимое других частеи поля не считывается. После считывания информации из регистра 7 все его разряды устанавливаются в нулевые положения. Блок 9 информирует формирователь 1 о том, что переменная комбинация сжатой информации считана из регистра 7 и передана в блок 9. По этой инфощиации формирователь 1 подготавливает очередной пакет ин, формации, информируя об этом блок 2. Если

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

Если очередной пакет информации состоит нэ повторяющихся комбинаций, то блок 2 передает на входы формирователя 1, регистра 3 и регистра 4 общую команду "Считать".

По этой команде из формирователя 1 считываются и передаются в соответствующие разряды признаков регистра 7 и на элементы

И блока 6 код признаков и одна из повторяющихся комбинаций. А из регистра 3 и регистра 4 считываются и передаются на входы формирователя 5 постоянная комбинация сжатой информации и .комбинации единиц.

Расширенная информация считывается из формирователя 5 и одновременно передается на входы элементов И блока 6 н блока 10;

В блоке 6- осуществляется сравнение повто23 10 постоянную 1сомбинацню сжатой информации и комбинацию единиц. Эта информация передается на входы формирователя 5, где информация расширяется и передается на входы блока 6 и блока 10.

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

Если сжатая информация относится к новторяющейся информации, то блок 9 по команде блока 2 передает признаки и код, определяющий количество повторяющихся комбинаций сжатой информации, непосредственно в формирователь 1, а единичный уровень части поля переменной комбинации сжатой информации, определяющий адрес расширенной информации, — в соответствующие разряды блока.10. Одновременно с этим блок 9 информирует блок 2 о записи части сжатой информации в блок 10. По этим сведениям блок 2 посылает на входы регистра 3 и регистра 4 команду "Считать", которая из указанных регистров считывает информацию и передает ее на входы формирователя 5. Расширенная информация с выходов формирователя 5 передается на входы элемента И блока 6 и блока 10.

Единичным уровнем части цоля комбинации сжатой информации блок 10 пропускает соответствующую комбинацию иэ формирователя 5 в формирователь 1. Формирователь 1 . по признакам и коду, определяющему число повторяющих ". комбинаций, восстанавливает первоначальный пакет информации.

Если сжатая информация относится к неупорядоченной информации, то блок 9 передает признак информации и эквивалентный код соответственно в формирователь 1 и преобразователь 11, информируя об этом блок

2. По этим сведениям блок 2 посылает на входы регистра 3 и регистра 4 команду "Считать", которая из укаэанных регистров считывает соответственно постоянную комбинацию сжатой информации и комбинацию единиц и одновременно передает их в формирователь

5. Расширенная информация иэ формирователя 5 передается иа входы элементов И блока 6 и блока 10.

По эквивалентному коду преобразователь

11 вырабатывает разрешающие импульсы, которые поступают в блок 10. Блок 10 по этим импульсам пропускает из формирователя 5 только те комбинации, которые соответству9 9345 ряющейся комбинации формирователя 1 с комбинациями пакета расширенной информации.

Элемент И блока 6, на котором проиэопшо совпадение сравниваемых комбинаций, sannсывает через элементы ИЛИ блока 8 и не- S посредственно в разряды признаков в части поля регистра 7, а также в блок 2 единичные уровни, указывающие часть поля регистра.

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

По импульсу с выходов элементов ИЛИ блока 8 блок 2 посылает команду * Запись" формирователю 1. По этой команде формирователь 1 записывает часть поля регистра 7, где содержится единичный уровень, число, определяющее количество повторяющихся комбинаций. По команде блока 2 признаки и часть поля с записанной информацией (единичный разряд, указывающий адрес повторя- 2р ющейся комбинации в пакете расширенной информации,и число, определяющее количество повторяющихся комбинаций). считываются иэ регистра 7 и передаются в свободные-ячейки блока 9.. 2S

Если очередной пакет формирователя -1 состоит иэ повторяющемся комбинации, то процесс сжатия информации повторяется аналогично вышеописанному. Если очередным пакетом формирователя 1 является неупорядоченный пакет информации, то он по команде блока 2 посылает пакет информации в преобразователь 11, который преобразовывает пакет неупорядоченной информации в эквивалентйый код с меньшим числом разрядов, чем у пакета неупорядоченной информации, и передает ее в блок 9; блок 9 информирует об этом формирователь 1 и блок 2. Если в .преобразователе 11 не сформировался эквивал и ый код. то неуморщдчемьй пакет «3 4р преобразователя 11 без изменения мередается . в блок 9. Этот пакет информации бтносится к чмслу редко. встречающихся пакетов информации. Так осуществляется процесс сжатия информации.

Процесс восстановления информации состоит в следующем. Блок 2 подает команду блоку 9 "Считать". Блок 9 по коду признаков определяет вид информации.. Если информация является сжатой и она относится к возрастающей нли убывающей информации, то блок 9 передает признаки сжатой информации в формирователь 1, а сжатую информацию (часть или все части поля переменной комбинации сжатой информации) — в блок 10„информируя об этом блок 2. По этим сведениям блок 2 посылает на входы регистра 3 и регистра 4 команду "Считать",. которая из указанных регистров считывает соответственно

:93452

12 ют комбинациям неупорядоченного пакета информации.

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

Коэффициент сжатия изменяется в следующих пределах: 1 > К„.ж > 2", где и: — количество разрядов s комбинации; 2" — коли. 1$ чество комбинаций в пакете.

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

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

2$

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

-$$ ство введены формирователь пакетов иврвичнои информации, формирователь информационных комбинаций, регистр памяти адреса и признака информационных. комбинаций, преобразователь пакетов неупорядоченной информации в коды и блок выдачи информации, первый вход формирователя пакетов первичной информации подключен к первому входу устройства, первый, второй третий, четвертый и пятый выходы фор. мирователя пакетов первичной информации со4$ единены соответственно с первым входом преобразователя пакетов неупорядоченной информации в коды, первым входом блока памяти информации, первым. входом блока сравнения информационных комбинаций, первым входом регистра адреса информационных комбинаций и йервым входом блока управления, первый, второй, третий, четвертый и пятый выходы блока управления соединены соответственно о вторым входом формирователя пакетов первичной информации, объединенными вторым и третьим входами регистра памяти адреса и признака информационных комбинаций, вторым входом преобразователя пакетов неупорядоченной инфоумации в коды, вторым входом блока. памяти информации и объединенными первыми входами регистра памяти постоянных информационных комбинащий и регистра памяти единиц, вторые входы которых соединены с вторым и третьим входами устройства, выходы которых соединены с соответствующими входами формирователя информационных комбинаций, выход которого соединен с первым входом блока выдачи информации и вторым входом блока сравнения информационных комбинаций, выход блока сравнения. информационных комбинаций соединен с четвертым входом регистра памяти адреса и признака информаци-., онных комбинаций и через блок элементов ИЛИ с объединенными вторым входом блока управления и пятым. входом регистра памяти

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР л 482786, кл. G 08 С 15/02, 1973. . 2. Авторское свидетельство СССР No 554549, кл. G 08 С 15/00, 1974 (прототип).

934523

Составитель Н. Бочарова

Техред Т. Маточка . Корректор S. Бутяга

Редактор В. Петраш

Заказ. 3944/47

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Тираж 642 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и огкрытий

113035, Москва, Ж-35, Раушская наб., д. 4/5