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

Союз СоветсиилСоциалистичесиикреспублик ОПИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕПЛЬСТВУ(5)М. Кл, 6 08 С 5/06 бвударетееилмб квинтет СССР пе делам иэебретенил и еткритийДата опубликования описания 07.06,82 ВСВСОЮЗИ а М вА%ИТНОИ 13 БИБЛИОТЕКА(71) Заявитель(54) УСТРОЙСТВО ДЛЯ СЖАТИЯ И ВОССТАНОВЛЕНИЯ ИНФОРМАЦИИИзобретение относится к области связи и может. быть использовано в вычислительной тех.нике в качестве запоминающего устройства,а также может найти применение в средствахотображения информации, автоматике и телемеханике. Известно устройство для сжатия и восста-, новления информации, содержащее регистр числа, блок псевдослучайного преобразования, выходы которого соединены с регистром адреса и первым входом регистра сдвига, второй вход регистра сдвига соединен с выходом зада ющего генератора, выход регистра адреса под.ключен к входу запоминающего блока, блок15 вычисления кодового расстояния, входы которого соединены с выходом задающего генератора и входом блока псевдослучайного преобразования, вход последнего соединен с одним иэ входов регистра числа, другие входы которого соединены соответственно с выходом запоминающего блока, регистра сдвита и двумя выходами блока вычисления кодового расстоя. ния 11. К недостаткам указанного устройства следует отнести низкий коэффициентвсжатия информа ции, большой объем оборудования на бит сжатой информации и высокую стоимость.Наиболее близким к предлагаемому является устройство для сжатия информации, содержащее и-образный входной регистр сдвига, вход которого соединен с информационным входом устройства, группы элементов И, выходной (п+ 1)-разрядный регистр сдвига, датчик случайных чисел, вход которого соединен с первым выходом блока управления, а выходы - с соответствующими входами схемы сравнения, (и+ 1)-разрядный счетчик н группу элементов ИЛИ, в которой выход каждого элемента ИЛИ соединен с одним из входов последующего, разрядные выходы входного сдвигающего регистра соединены с первыми входами элементов И первой группы, вторые входы которой соединены с вторым выхо.дом блока управления, выходы элементов И первой группы соединены с соответствующими 1 ходами счетчика, выходы счетчика соединены : соответствующими входами схемы сравне3 93452ния и с первыми входами элементов И второйгруппы, вторые входы которых соединены стретьим выходом блока управления, а третьи -с выходами элементов ИЛИ, вторые входыкоторых соединены с четвертым выходом,блока управления, выходы элементов И вто-рой группы соединены с входами выходногосдвигающего регистра, выходы схемы сравнениясоединены с первыми входами элементов Итретьей группы, вторые входы которых сое 10динены с пятым выходом блокауправления,а выходы - с вторыми разрядными входамисчетчика, начиная с второго разряда 23.К недостаткам известного устройства следуетотнести низкий коэффициент сжатия инфор эмации и большой объем оборудования,Цель изобретения - повышение эффективности сжатия информации,Поставленная цель достигается тем, что вустройство, содержащее блок памяти информа. 211цни, первый выход которого соединен с первым выходом устройства, блок сравнения ин.формационных. комбинаций, регистр комбинаций, регистр памяти постоянных информационных комбинаций, регистр памяти единиц, блокуправления и блок элементов ИЛИ введеныформирователь пакетов первичной информации,формирователь инфо 1 мационных комбинаций,.регистр памяти адрес и признака информационных комбинаций, преобразователь пакетов неупорядоченной информации в коды и блоквыдачи информации, первый вход формирователя пакетов первичной информации подключенк первому входу устройства, первый, второй,третий, четвертый и пятый выходы формирователя пакетов первичной информации соединены соответственно с первым входом преобразователя пакетов неупорядоченной информации в коды, первым входом блока памятиинформации, первым входом блока сравненияинформационных комбинаций, первым входомрегистра адреса информационных комбинацийи первым входом блока управления, первый,второй, третий, четвертый и пятый выходыблока управления соединены соответственнос вторым входом формирователя пакетовпервичной информации, объединенными вто.рым и третьим входами регистра памятиадреса и признака информационных комби.наций, вторым входом преобразователя пакетов неупорядоченной информации в коды, вто- Юрым входом блока памяти информации иобъединенными первыми входами регистра памяти постоянных информационных комбинаций и регистра памяти единиц, вторые входыкоторых соединеныс вторым и третьим вхо- Идами устройства, выходы которых соединеныс соответствующими входами формирователяинформационных комбинаций, выход которо. 3 4го соединен с пеовым входом блока выдачи ,информации и вторым входом блока сравне. ния информационных комбинаций, выход блока сравнения информационных комбинаций соединен с четвертым входом регистра памяти адреса и признака информационных комбинаций и через блок элементов ИЛИ с объединенными вторым входом блока управления и пятым входом регистра памяти адреса и при знака информационных комбинаций, выходкоторого соединен с третьими входами формирователяпакетов первичной информациии блока памяти информации, второй, третийи четвертый выходы блока памяти информации соединены соответственно с объединенными третьим входом блока управления и четвертым входом формирователя пакетов пер-вичной информации, вторым входом блока вы.дачи информации и третьим входом преобразователя пакетов неупорядоченной информации в коды, первый и второй выходы которого соединены соответственно с четвертымвходом блока памяти информации и третьимвходом блока выпачи информачи, первый,второй и третий выходы которого соединенысоответственно с пятым входом формирователя пакетов первичной информации, пятымвходом блока памяти информации и вторымвыходом устройства,На чертеже. приведена функциональная схемаустройства для сжатия и восстановления ин.формации.Устройство для сжатия и восстановленияинформации содержит формирователь 1 паке.тов первичной информации, блок 2 управления, регистр 3 памяти. постоянных информационных комбинаций, регисэр 4 памяти единиц,формирователь 5 информационных комбинаций, блок 6 сравнения информационных комбинаций, регистр 7 памяти адреса и признака информационных комбинаций, блок 8 элементов ИЛИ, блок 9 памяти информации, блок 10 выдачи информации, преобразователь 11пакетов неупорядоченной информации в коды,Формирователь 1 пакетов первичной информации предназначен для деления поступающей информации на пакеты возрастающей, убывающей, повторяющейся и неупорядоченной информации, а также для восстановления сжатой информации в пакеты первоначальной информации. Блок 2 управления предназначен для приема и передачи другим элементам устройства управляющих импульсов, Ре.гистр 3 памяти постоянных информационных комбинаций предназначен для приема, хранения и выдачи постоянных комбинаций сжатой информации в формирователь 5.Регистр 3 имеет возможность осуществлять сдвиги информации влево и вправо.111000101110010111010111 5 934523 6Постоянная Линейка сжатой информациидаются по единицам сжатой информации, по- пакет и разрядных комбинаций на все соче ступающей из блока 9 и преобразователя 11. тания, сжатый в 2 п-разрядную линейку, Преобразователь 11 предназначен для преНапример, пакет трехразрядных комбина. образования пакетов неупорядоченной инфор.,0 О О О 1 1 1 1 Устройство работает следующим образом, . 00110011 От внешних источников на первый вход 0 1 0 1 О 1 0 1 устройства периодически поступает информа16 ция. Формирователь 1 путем сравнения смеж содержит 24 разряда, а постоянная линейка ных комбинаций формирует сжимаемую и сжатой информации этого пакета содержит во- несжимаемую информации в переменные на. семь разрядов (00010111). Количество разря- кеты, К сжимаемой информации относятся дов в начальных пакетах возрастающей или переменные пакеты, возрастающей, убываю. убцвающей информации, относящееся к коли. 1 щей, повторяющейся и часть комбинаций нечеству разрядов соответствующей постоянной упорядоченной информации К несжимаемой ин комбинации. сжатой информации или ее части, формации относится часть комбинаций.неупоесть коэффициент сжатия информации, рядоченной информациие комбинации которыхсистематически редко применяются. В пакетах Регистр 4 памяти единиц предназначен для2 п возрастающей информации ко инации стол . приема, хранения и передачи едищщ в фор ) размещаются слева направо в порядке мирователь 5, который предозначен для фор возрастания их значений, например: ыяроаанпя еасгных слагаемых, оораеуюняглся ре е р 2 6 72 3 4 у а рееулагагне переыножеряя посгоянной поы. . р ррр р рбинации информации на комбинацию единиц О О 1 О О 1 1 1 01 0 1 Ниже приведен пример трехразрядных ком О 1 О 1 1 О 0 1 . г О 1 0 1 ит,д.2 чВ пакетах убывающей информации комби. 0 001111н . нации размещаются слева направо в поряд 0 0 1 1 0 О 1 1 - начальная информация (ком.ке убывания нх значений, например: О 1 О 1 О г 0 1 бинация на все сочетания) 000 1 0 1 1 1 - сжатая информация (посто- ЗО11100 11.10янная комбинация сжатой 10010 1000 1000 информации)11010 0101 1100 итд. - комбинация единиц, В пакетах повторяющейся информации одна, - расширеннаяинформация две и более комбинаций пакета являются по (частные слагаемые, образую. вторяющимися, например: щиеся приперемножениипо 0 0 0 0 О 0 0 0 0 стоянной комбинации сжатой 1 .1 1 1 1 1- 1 11 1 1 1 информации с комбинацией 1 1 1 1 1 О 0 0 0 0111 г.оооОБлок. 6 сравнения информационных комбина-,щ 1 1 1 1 1 11110000 ций выполнен, например, на элементах И, и 1 1 1 1 1 предназначен для сраврения комбинации фор. 11111 ггггоОоО мирователя 1 с комбинациями формировате Для распознавания пакетов сжатой инфор. ля 5. мации введены признаки: 00 - возрастаюРегистр 7 памяти адреса и признака инфор- м щая информация, 01 - убывающая информа. мационных комбинаций предназначен для фик. ция, 10 - повторяющаяся информация, 11 сации в соответствующих разрядах местополо- неупорядоченная информация, которые припижения комбинаций в формирователе, а. также сываются к комбинациям сжатой информадля запоминания признаков, определяющих ции, Число комбинаций в пакетах переменное. виды информации и части полей, Элементы р Процесс сжатия пакетов информации осущест. ИЛИ блока 8 предназначены для записи при- вляетсяследующимобраэом.формировательватель 1 знаков в старшие разряды регистра 7., подготовив пакет информации, информирует блокБлок 9 памяти информации предназначен 2 управления о том, что пакет информации для приема, хранения и выдачи соответствую относится к одному из видов информации н щи х блокам сжатой и несжатой информации. можно его подвергать сжатию,И Блок 10 выдачи информации предназначенсли пакет относится к возрастающей, убыдля выдачи разрешений на пропуск комбина-Если па р ей бповто яющейся информации, тоиз фо ми ователя 5 в формировательвающей или повтор щ фор 1 и внешним потребителям. Разрешения вы- блок 2 посылает формировате, ре рвателю 1, гист у23 7 9345 3 и регистру 4 общую команду "Считать". По этой команде из формирователя 1 считы. ваются признак пакета информации и начальная комбинация первого пакета информации н передаются в соответствующие разряды ре-гнстра 7 и на входы блока 6, А иэ регистров 3 и 4 считываются постоянная комбинация сжатой информации и комбинация единиц и одновременно" передаются на входы формирователя 5, в котором переданная информация перемножается, образуя, таким образом, част. ные слагаемые (пакет расширенной .информации), в которых содержатся п.разрядные ком. бинации на все сочетания. С.выходов.формиро- . вателя 5 комбинации пакета расширенной ин формации передаются на соответствующие элементы блока 6 и на вход блока 10. На эле. ментах И блока 6 производится сравнение начальной комбинации пакета формирователя 1 с комбинациями расширенной информа цни формирователя 5.Элемент И блока 6, на котором произошло совпадение .начальной комбинации формирователя 1 с комбинацией расширенной информации формирователя 5, записывает единицы И через элементы ИЛИ блока 8 и непосредствен. но в соответствующие разряды признаков и поля регистра 7, а т;кже в блок 2.Единица поля определяет адрес (местопо. ложение) комбйнации в пакете расшяреннноц информации блока 5, а единица признака. - часть поля регистра 7, в которую записана единица поля.Едншща, записанная в блок 2, информи. рует последний о совпадении сравниваемых комбинаций. По, этим сведениям блок 2 вновь3 посылает на входы формирователя 1, регистра 3, регистра 4 общую команду "Считать". По этой команде из формирователя 1 считывается вторая комбинация пакета и переда 46 . ется на входы блока 6, а из регистра 3 считывается постоянная комбинация сжатой информации иэ регистра .4, комбинация единиц и одновременно передаются на формирователь 5, Расширенная информация с выходов фор 4 мирователя 5 передается на блок 6, на элементах И которого осуществляется сравнение второй комбинации формирователя 1 с комбинацией расширенной информации формирователй 5.ЯЭлемент И блока 6, на котором,произошло совпадение сравниваемых комбинаций, вновь записывает две единицы в регистр 7, одна из которых указывает. адрес комбинации в пакете расширенной информации, другая - часть поля регистра 7, в которую записана единица поля. Если единица, определяющая адрес,комбинации в пакете расширенной информации, записана в ту часть поля регистра 7, в которую записана единица поля предыдущейкомбинации сжимаемого пакета, то в разрядеданного признака единичный уровень не меняется,. Если единица, определяющая адрес комбинации в пакете расширенной информациизаписана в другую часть поля регистра 7, тоединичныи уровень признаков, определяющий,часть поля регистра 7, через элементы ИЛИблока 8 записывается в. другой разряд признаков регистра 7,Процесс сжатия продолжается до тех пор,пока в сжимаемом пакете формирователя 1не останется ни одной комбинации.После считывания из формирователя 1 последней комбинации сжимаемого пакета ин.формации блок 2 посылает регистру 7 команду Считать". По этой команде в отведен.ную часть блока 9 иэ регистра, передаетсячасть или вся комбинация сжатой информации,Если в разрядах признаков, определяющихполя регистра 7, содержатся все единицы, то.йз регистра 7 считываются признаки и содержимое всех полей регистра 7. Если в разря..дах признаков регистра 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постоянную Комбинацию сжзтой информации и комбинацию единиц. Эта информация передается на входы формирователя 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 и блока 1 О.По эквивзлентному коду преобразователь 11 вырабатывает разрешзющие импульсы, которые поступают в блок 10. Блок 10 по этим импульсам пропускает из формирователя 5 только те комбинации, которые соответству 99345 ряющейся комбинации формирователя 1 с комбинациями пакета расширенной информации.Элемент И блока 6, на котором произошло совпадение сравниваемых комбинаций, зашесывает через элементы ИЛИ блока 8 и не. э посредственно в разряды признаков в части поля регистра 7, а также в блок 2 единич. ные уровни, указывающие часть поля регистра.7, в которую ззписан единичный уровень и адрес повторяющейся комбинации в пакете 1 Р расширенной информации.По импульсу с выходов элементов ИЛИ блока 8 блок 2 посылает команду Запись" формирователю 1. По этой команде формиро. ватель 1 записывает часть поля регистра 7,И где содержится единичный уровень, число, определяющее количество повторяющихся ком. бинзций. По команде блока 2 признаки и есть поля с записанной информзцией (единичный разряд, указывающий адрес повторя 26 ющейся комбинации в пакете расширенной информации,и число, определяющее количество повторяющихся комбинаций). считываются иэ регистра 7 и передаются в свободные ячей. ки блока 9 2Если очередной пакет формирователя 1 состоит иэ повторяющемся комбинации, то про. цесс сжатия информации повторяется аналогично вышеописанному. Если очередным пакетом формирователя 1 является неупорядочен. ный пакет информации, то он по команде блока 2 посылает пакет информации в преобразователь 11, который преобразовывает пакет неупорядоченной информации в эквива. лентйый код с меньшим числом разрядов, чем у пакета неупорядоченной информации, и передает ее в блок 9; блок 9 информирует об этом формирователь 1 и блок 2. Если в .преобразователе 11 не сформировался эквивалентный код. то неуморядоченмый пакет 3 4 р цреобрззователя 11 беэ изменения цередается . в блок 9. Этот пакет информации бтносится к чмслу редко. встречающихся пакетов информации. Так осуществляется процесс сжатия информации.4Процесс восстановления информации состоит в следующем. Блок 2 подает команду блоку 9 "Считать". Блок 9 по коду признаков определяет вид информзции Если информация является сжатой и она относится к возрастаю. щей нли убывающей информации, то блок 9 передает признаки сжатой информации в фор. мирователь 1, а сжатую информацию (часть или все части поля переменной комбинации сжатой информации) - в блок 10, информи.руя об этом блок 2, По этим сведениям блок 2 посылает на входы регистра 3 и ре. гистра 4 команду "Считать",. которая из указанных регистров считывает соответственноют комбинациям неупорядоченного пакета ин. формации.В блоке 9 могут встречаться несжатые пакеты информации. В этом случае блок 9 передает признаки и содержательную информацию э непосредственно на первый выход устройства к потребителю информации. Исследования показывают, что коэффициент сжатия зависит . от количества комбинации в пакетах иоэра.стающей, убывакяцей и повторяющейся инфор О мацни, а также от количества пакетов неупо. рядоченной информации, подлежащей сжатию.Коэффициент сжатия изменяется в следую. щих пределах: 1 ) Кж . 2 П, где и: - ко. личество разрядов в комбинации; 2 п - коли 13 чество комбинаций в пакете.Чем больше встречается. пакетов с комби-. нациями возрастающей, убывающец, повторяющейся и неупорядоченной информации, подлежащей сжатию, тем больше коэффициент сжа. 26 Формула изобретения 2Устройство для сжатия и восстановления информации, содержащее блок памяти информации, первый выход кморого соединен с пер. вым выходом устройства, блок сравнения информационных комбинаций, регистр комбина . ций, регистр памяти постоянных информацион ных комбинации, регистр памяти единиц, блок управления и блок элементов ИЛИ, о т л ия а ю щ е е с я тем, что, с целью повышения коэффициента сжатия информации, в устрой-:м Ц ство введены формирователь пакетов иврвичнои информации, формирователь информационных комбинаций, регистр памяти адреса и признака информационных. комбинаций, преобразователь пакетов неупорядоченной информации в коды и блок выдачи информации, первый вход фор. мирователя пакетов первичной информации подключен к первому входу устройства, первый, второй третий, четвертый и пятый выходы фор. мирователя пакетов первичной информации соеЗ единены соответственно с первым входом пре. образователя пакетов неупорядоченной инфор. мацки в коды, первым входом блока памяти информации, первым. входом блока сравнения информационных комбинаций, первым входом регистра адреса информационных комбинаций Эф и йервым входом блока управления, первый,второй, третий, четвертый и пятый выходыблока управления соединены соответственноо вторым входом формирователя пакетов пер.вичиой информации, объединенными вторым итретьим входами регистра памяти адреса ипризнака информационных комбинаций, вторымвходом преобразователя пакетов неупорядоченной инфоумации в коды, вторым входом блока,памяти информации и объединенными первыми входами регистра памяти постоянныхинформационных комбинащий и регистра па.мяти единиц, вторые входы которых соединеныс вторым и третьим входами устройства, выходы которых соединены с соответствующимивходами формирователя информационных ком.бинаций, выход которого соединен с первымвходом блока выдачи информации и вторымвходом блока сравнения информационных комбинаций, выход блока сравнения. информацион.ных комбинаций соединен с четвертым входомрегистра памяти адреса и признака информаци, оннйхкомбинаций и через блок элементовИЛИ с объединенными вторым входом блокауправления и пятым входом регистра памятиадреса и признака информационных колебаний,выход которого соединен с третьими входами формирователя пакетов первичной информа.ции и блока. памяти информации, второй, третий и четвертый выходы блока памяти информации соединены соответственно с объединенными третьим входом блока управления ичетвертым входом формирователя пакетов иер.вичной информации, вторым входом блока выдачи информации и третьим входом преобразователя пакетов неупорядоченной информациив коды, первый и второй выкоды которогосоединены соответственно с четвертым входомблока памяти информации и третьим входомблока выдачи информации, первый, второй итретий выходы которого соединены соответственно с пятым входом формирователя пакетов первичной информации, пятым входом бло,ка памяти информации и вторым выходомустройства,Исто анки информации,принятые во внимание при экспертизе1, Авторское свидетельство СССР Иф 482786,кл. 6 08 С 15/02, 1973.. 2. Авторское свидетельство СССР Иф 554549,кл. 6 08 С 15/00, 1974 (прототип),934523 оставителв Н. Бочароваехред Т. Маточка . Корректор В. Бутяга етраш к ПодписноР Заказ. 3944 13 Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 Тираж 642 Государственного лам изобретений и Москва, Ж, Раушкомитета СССогкрытий ская наб., д,