Устройство для сжатия и восстановления информации Советский патент 1982 года по МПК G08C15/06 

(54) УСТГОЙСТВО ДЛЯ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ИНФОРМАЦИИ

Изобретение относится к области связи и м жет быть использовано в вычислительной технике в качестве запоминающего устройства, а также может найти применение в средствах отображения информации, автоматике и телемеханике. Известно устройство для сжатия и восстановления информации, содержащее регистр числа, блок псевдослучайного преобразования, выходы которого соединены с регистром адреса и первым входом регистра сдвига, второй вход регистра сдвига соединен с выходом зада ющего генератора, выход регистра адреса подключен к входу запоминающего блока, блок вычисления кодового расстояния, входы которого соединены с выходом задающего генератора и входом блока псевдослучайного преобразования, вход последнего соединен с одним из входов регистра числа, другие входы которого соединены соотЬетственно с выходом запоминающего блока, регистра сдвига и двумя выходами блока вычисления кодового расстоя ния {1. К Недостаткам указанного устройства следует отнести низкий козффициент «сжатия информа ции, большой объем оборудования на бит сжатой информации к высокую стоимость. Наиболее близким к предлагаемому является устройство для сжатия информации, содержащее п-образный входной регистр сдвига, вход которого соединен с информационным входом устройства, группы элементов И, вы- ходной (п + 1)-разрядный регистр сдвига, датчик случайных чисел, вход которого соединен с первым выходом блока управления, а выходы - с соответствующими входами схемы сравнения, (п + 1)-разрядный счетчик и группу элементов ИЛИ, в которой выход каждого элемента ИЛИ соединен с одним из входов последующего, разрядные выходы входного сдвигающего регистра соединены с первыми входами элементов И первой группы, вторые входы которой соединены с вторым выходом блока управления, выходы элементов И первой группы соединены с соответствующими }ходами счетчика, выходы счетчика соединены ; соответствующими входами схемы сравне39ПИЯ и с лервыми входами элементов И второй группы, вторые входы которых соединены с третьим выходом блока управления, а третьи с выходами элементов ИЛИ, вторые входы которых соединены с четвертьш выходом, блока управления, выходы элементов И второй группы соедш1ены с входами выходного сдвигающего регистра, выходы схемы сравнени соединены с первыми входами элементов И третьей группы, вторые входы которых соедииены с пятым выходом блока управления, а выходы - с вторыми разрядными входами счетчика, начиная с второго разряда 2. К недостаткам известного устройства следуе отнести низкий коэффициент сжатия информадии и большой объем оборудования. Цель изобретения - повышение эффективно сти сжатия информации. Поставленная цель достигается тем, что в устройство, содержащее блок палляти информации, первый выход которого соединен с перBbSM выходом устройства, блок сравнения информационных комбинаций, регистр комбинаций, регистр памяти постоянных информационных комбинаций, регистр памяти единиц, блок управления и блок элементов ИЛИ, введены формирователь пакетов первичной информации формирователь информационных комбинаций, регистр памяти адресг и признака информацио ных комбинаций, преобразователь пакетов неупорядоченной информации в коды и блок выдачи информации, первый вход формирователя пакетов первичной информации подключе к первому входу устройства, первьт, второй, третий, четвертый и пятый выходы формирователя пакетов первичной информации соединены соответственно с первым входом преобразователя пакетов неупорядоченной информации в коды, первым входом блока памяти информации, первым входом блока сравнения информационных комбинаций, первым в ;одом регистра адреса информационных комбинаций и nepBbiM входом блока управления, первый, второй, третий, четвертый и пятый выходы блока управления соединены соответственно с вторым входом формирователя пакетов первичной информации, объединенными вторым и третьим входами регистра памяти адреса и признака информационных комбинаций, 1зторым входом преобразователя пакетов неупорядоченной информации в коды, вт рым входом блока памяти информации и объединенными первыми входами регастра па мяти постоянных информационных комбинаций и регистра памяти единиц, вторые входы которых соединеныс вторым и третьим входами устройства, выходы которых соединены с соответствующими входами формировг теля информационных комбинаций, выход котороГО соединен с первым входом блока выдачи Информации и вторым входом блока сравнения информационных комбинаций, выход блока сравнения информационных комбинаций соединен с четвертым входом регистра памяти адреса и признака информационных комбинаций и через блок элементов ИЛИ с объединенными вторым входом блока управления и пятым входом регистра памяти адреса и признака информационных комбинаций, выход которого соединен с третьими входами формирователя пакетов первичной информации и блока памяти информации, второй, третий и четвертый выходы блока памяти информации соединены соответств.енно -с объединенными третьим входом блока управления и четвертым входом формирователя пакетов пер-. вичной информации, вторым входом блока выдачи информащш и третьим входом преобразователя пакетов неупорядоченной информации в коды, первый и второй выходы которого соединены соответственно с четвертым входом блока памяти информащйс и третьим входом блока вьцкачя информащш, первый, второй и третий выходы которого соединены соответственно с пятым входом формирователя пакетов первичной информации, пятым входом блока памяти информации и вторым выходом устройства. На чертеже приведена функциональная схема устройства для сжатия и восстановления информации. Устройство для сжатия и восстановления информации содержит формирователь I пакетов первичной информации, блок 2 управления, регистр 3 памяти постоянных информационных комбинаций, регистр 4 памяти единиц, формирователь 5 информационных комбинаций, блок б сравнения информационных комбинаций, регистр 7 памяти адреса и признака информационных комбинаций, бло1с 8 элементов ИЛИ, блок 9 памяти информации, блок 10 выдачи информации, преобразователь 11 пакетов неупорядоченной информации в коды. Формирователь 1 пакетов первичной информации предназначен для деления поступающей информации на пакеты возрастающей, убывающей, повторяющейся и неупорядоченной информации, а также для восстановления сжатой информации в пакеты первоначальной информации. Блок 2 управлегшя предназначен для приема и передачи другим элементам устройства управляющих импзльсов. Регистр 3 памяти постоянных информационных комбинаций предназначен для приема, хранения и выдачи постоянных комбинаций сжатой информации в формирователь 5. Регистр 3 имеет возможность осуществлять сдвиги информации влево и вправо. Постоянная Линейка сжатой информации - пакет п-раэрядных комбинаций на все сочетания, сжатый в 2 -разрядкую линейку. Например, пакет трехразрядных комбииа- ций на все сочетания 01234567 .00001111 00110011 01010101 содержит 24 разряда, а постоянная линейка сжатой информации этого пакета содержит во семь разрядов (00010111). Количество разрядов в начальных пакетах возрастающей или убивающей информации, относящееся к количеству разр1ядов соответствующей постоянной комбинации сжатой информации или ее части, есть коэффициент сжатия информации. Регистр 4 памяти единиц предназначен для приема, хранения и передачи единиц в формирователь 5, который предназначен для формирования частных слагаемых, образующихся в результате перемноже я постоянной комбинации щсформашш на комбинацию единиц. Ниже приведен пример трехразряд|{ых комбинации. 00001 1 1 П 00110011I - начальная информация (ком 01 О 101 О и бинация на все сочетания) 00010111 - с(сатая информация (постоянная комбинация сжатой информации). 111 - комбинащк единиц. 1 О 1 11| - расашреНная информация OUldlll т (частныеслагаемые,образую 010111 1 щиеся при перемножении постоянной комбинации сжатой информации с комбинацией единиц). Блок 6 сравнения информационных комбина ций. вьшолнен, например, на элементах И, и предназначен для сраврения комбинации формирователя 1с комбинациями формирователя 5. Регистр 7 памяти адреса и признака инфор мационных комбинаций предназначен для фкк сации в соответствуюццсх разрядах местоположения комбинаций в формирователе, а также для запоминания признаков, определяющих виды информации и части полей. Элементы ИЛИ блока 8 предназначены для записи признаков в старшие разряды регистра 7. Блок 9 памяти информации предназначен для приема, хранения и вьщачи соответствующих блокам сжатой и несжатой информации Блок 10 выдачи информации предназначен для выдачи разрешений на пропуск комбинаций из формирователя 5 в формирователь 1 и внешним потребителям. Разрешения выдаются по единицам сжатой информации, поступающей из блока 9 и преобразователя i 1. Преобразователь 11 предназначен для преобразования пакетов неупорядоченной информации в эквивалентные коды с меньцшм числом разрядов. Устройство работает следующим образом. От внешних источников на первый вход устройства периодически поступает информа ция. Формирователь 1 путем сравнения смежных комбинаций формирует сжимаемую и несжимаемую информации в переменные пакеты. К сжимаемой информашш отиосятся переменные пакеты, возрастающей, убывающей, повторяющейся и часть комбинаций неупорядоченной информации.. К несжимаемой ян формации относится часть комбинаций неупорядоченной информашш, комбинации которых систематически рещсо применяются. В Пакетах возрастающей информации комбинации (столбцы) размещаются слева направо в порядке возрастания их значений, например: 0125 02671 2347 000 1 . О О 1 I00011 0010 О 1 J l01101 01 01 10011010 1 НТ.Д. В пакетах убывающей информации комбинации размещаются слева направо в порядке убывания их значений, например: 1110011101110 1О р 1 010001000 110100101I 1 00 и т.д. В пакетах Повторяющейся Ш1формации одна, две и более комбинаций пакета являются повторяющимися, например: 00000 00000 1 1111 1 1111 1111 00000 111111110000 1111111 1.0 О 00 111111110000 Для распознавания пакетов сжатой информации признаки: 00 - возрастающая информация, 01 - убывающая информация, 10 - повторяющаяся информация, 1 неупорядоченная информация, которые приписываются к ком&1нациям сжатой информации. Число ком&таций в пакетах переменное. Процесс сжатия пакетов информации осуществляется следующим образом, формирователь 1, подготовив пакет информации, информирует блок 2 управления о том, что пакет информации относится к одному из видов информации и можно его подвергать сжатию. Если пакет относится к возрастающей, убывающей или повторяющейся информации, то блок 2 посьшает формирователю 1, регистру

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

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

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

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

-

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

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

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

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

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

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

Если очередной пакет информации состоит из повторяющихся комбинаций, то блок 2 передает на входы формирователя 1, регистра 3 и регистра 4 общую комаНду Считать. По этой команде из формирователя il считываются и передаются в соответствующие разряды признаков регистра 7 и на элементы И блока 6 код признаков и одна из повторяющихся комбинаций. А из регистра 3 и регистра 4 считываются и передаются на входы формирователя 5 постоянная комбинация сжатой информации и комбинации .

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

8блоке & осуществляется сравненне повторяющёКся комбинации формирователя 1 с ком бйнациями пакета расширениой информации. Элемент И блока б, на котором произошло совпадеиие сравниваемых комбина1ШЙ, записывает через элементы ИЛИ блока 8 и не посредственно в разряды признаков в част поля регистра 7, а Также в блок 2 единич ные уровни, указывающие часть поля регистра 7, в которую записан единичный уровень и адрес повторяющейся комбинации в пакете . расширенной информации. По икшульсу с выходов элементов ИЛИ блока 8 блок 2 посылает команду Запись формирователю 1. По этой команде формиро ва1ель 1 записывает часть поля регистра 7, где содержится единичный уровень wcno, определяющее количество повторяющихся ком бинаций. По команде блока 2 признаки и часть поля с записанной информацией (еди ничнь1й разряд, указывающий адрес повторя ющейся комбината в пакете расширенной информации,и число, определяющее количест во Повторяющихся комбинаций), считываются из регистра 7 и передаются в свободные, ячей ки блока 9. Если очередной пакет формирователя 1 со стоит из повторяющейся комбинащш, то про цесс сжатия информации повторяется анало гично вышеописанному. Если очередным паке том формирователя 1 является неупорядочеи ный пакет информащш, то он по команде блока 2 посылает пакет информации в пре образователь 11, который преобразовывает пакет неупорядоченной информации в эквива лентйый код с меньшим числом разрядов, чем у пакета неупорядоченной информации, и пе редает ее в блок 9; блок 9 информирует об ЭТОМ формирователь 1 я блок 2. Если в .преобразователе 11 не сфоришровался зквива .лентный код, то неутрядрченНый пакет яз преобразоб.ателя 11 без изкюнения передается в блок 9. Этот пакет информации относится к шслу редко встречающихся пакетов инфор мации. Так осуществляется процесс сжатия информации. Процесс восстановления информащш состо ит в следующем. Блок 2 подает команду бло ку 9 Считать. Блок 9 по коду признаков определяет вид информации. Если информация является сжатой и она относится к возрастаю щей или убывающей информации, то блок 9 передает признаки сжатой информации в фор мирователь 1, а сжатую информацию (часть или все части поля переменной комбинации сжатой информации) - в блок 10, информируя об этом блок 2. По этим сведениям блок 2 посылает на входы регистра 3 и регистра 4 команду Считать, которая из ука занных регистров считывает соответственно постоянную koмбинaцию сжатой информации и комбинацию единиц. Эта информация передается на входы формирователя 5, где инфорМ31ШЯ расишряетсй и передается на входы блока 6 и блока 10. Блок 10 по единичным уровням части или всего поля сжатой информащт вещает разрешения соответствующим комбинациям пакета расширенной информации. Комбинации, получившие разрешение ,переда|ртся в формирователь 1, который по признакам информащш путем .сравнения и перестановок комбинаций осуществляет восстановление первоначальных пакетов.. Если сжатая информация относится к повторяющейся информации, то блок 9 по команде блока 2 передает признаки и код, определяющий количество повторяющихся комбинаций сжатой информации, непосредственно в формирователь 1, а единичньгй уровень части ПОЛЯ переменной комбинации сжатой информации, определяющий адрес расширенной информации, - в соответствующие разряды блока 10. Одновременно с зтим блок 9 информирует блок 2 о записи части сжатой информации в блок 10. По зтим сведениям блок 2 посылает на входь регистра 3 и регистра 4 команду Считать, которая из указанных регистров считывает информацию и передает ее на входы формирователя 5. Расашренная информация с выходов формирователя S передается на входы элемента И блока 6 и блока 10. Единичным уровнем части поля комбинации сжатой информации блок 10 пропускает соответствующую комбинацию ю формирователя 5 в формирователь 1. Формирователь 1 по признакам и коду, определяющему число повторяющихг . комбинаций, восстанавливает первоначальньгй пакет информации. Если сжатая информация относится к неупорядоченной информации, то блок 9 передает признак информации и эквивалентный код соответственно в формирователь 1 ir преобразователь 11, информируя об этом блок 2. По этим сведениям блок 2 посылает на входы регистра 3 и регистра 4 команду Считать, которая из указанных регистров считывает соответственно постоянную комбинацию сжатой информации и комбинацию единиц и одновременно передает их в формирователь 5. Расширенная информация из формирователя 5 передается на входы элементов И блока б и блока 10. По эквивалентному коду преобразователь 11 вырабатьшает разрешающие импульсы, которые поступают в блок 10. Блок 10 по этим импульсам пропускает из формирователя 5 только те комбинации, которые соответствуют комбшоциям неупорядоченного пакета информации. В блоке 9 могут встречаться несжатые пакеты информации. В этом случае блок 9 пере дает признаки и содержательную информацию непосредственно на первый выход устройства к потребителю инфор1 ции. Исследования показывают, что коэффициент сжатия зависит от количества комбинации в пакетах возрастающей, убьшающо} и повторяющейся информации, а также от количества пакетов неупорядоченной информации, подлежащей сжатию Козффициент сжатия изменяется в следующих пределах: I Ксж 2, где п - количество разрядов в к умбинации; 2 - количестно комбинаций в пакете. Чем больще встр&юется пакетов с комби-, нациями возрастающей, убьшающей, повторяющейся и неупорядоченной информации, подлежащей сжатию, тем больще коэффИ1Щент ежатия. Формула и 3 о б р С т е н и я Устройство для сжатия и восстановления информации, содержапаее блок памяти инфор|у1ацни, первый выход к..торого соединен с первым выходом устройства, блок сравнения информационных комбинаций, регистр комбинаций, регистр памяти постоянных информ:ационных комбинаций, регистр памяти единиц, блок управления и блок элементов ИЛИ, о т л и чающееся тем, что, с целью повышения коэффициента сжатия информации, в устройство введены формирователь пакетов первичной информации, формирователь информащюцных комбинаций, регистр памяти адреса и признака информационных ком&шаиий, преобразователь пакетов неупорядоченной информации в коды и блок выдазд информации, первый.вход формирователя пакетов первичной информации 1юд ключен к первому входу устройства, первый, второй третий, четвертый и пятый выходы фор мирователя пакетов первичной информации ооединены соответственно с первым входом преобразователя пакетов неупорядоченной информации в коды, первым входом блока памяти информации, первым входом блока сравнения информационных комбинаций, первым входом рггистра адреса информационных комбинаций и первым входом блока управления, первый, второй, третий, четвертый и пятый выходы блока управления соединены соответственно 0вторым Уходом формирователя пакетов первичной информации, объединенными вторым и третьим входам регистра памяти адреса н признака информационных комбинаций, вторым входом преобразователя пакетов неупорядоченной информации в коды, вторым- входом блоiC9.. памяти информации и объединенными первыми входами регистра, памяти постоянных информационных комбинаций и регистра памяти единиц, вторые входы которых соединены с вторым и третьим входаАШ устройства, выходы которых соединены с соответствующими входами формирователя информационных комбинаций, выход которого соединен с первым входом блока выдаф информщии и вторым входом блока сравнения информацио шых комбинаций, выход блока сравнения информационных комбинаций соединен с четвертым входом регистра памяти адреса и признака информациг оннЫх комбинаций и через блок элементов ИЛИ с объединен1|1 1ми вторым входом блока управления и пятым входом регистра памяти адреса и признака инфЬрмационньа колебаний, выход которого соединен с третьими входами формирователя пакетов первичной информации и блрка.памятиинформащщ, второй, третий и четвертый выходы памяти 1Шформации соединены соответственно с объединенными третьим входом блока управления и чугъбрЩм входом форм1фователя пакетов первичной информации, BTopbiM входом блока выдачи информации и третьим входом преобразователя пакетов неупорядоченной информации в коды, первый и вторЫ) вьосоды которого, соединены соответственно с четвертым входом блока памяти информации и третьим ; ходом блока выдачи информации, первый, второй и i третий выходы которого соединены соответственно с пятым входом формирователя пакетов первичной инфор мации, пятым входом бло,ка памяти информации и вторым выходом устройства. Истотаики информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР N 482786, кл. G 08 С 15/02, 1973. 2.Авторское свидетельство СССР № 554549, кл. G 08 С 15/00, 1974 (прототип).