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

НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ СЖАТИЯ ИНФОРМАЦИИ(73) Патентообладатель Денисенко Олег Федорович Костюченко Александр Иванович Михальченко Александр Николаевич(57) Устройство для сжатия информации, включающее последовательно соединенные узел подготовки информации к сжатию, узел сжатия информации и узел хранения результата, причем узел подготовки информации к сжатию содержит последовательно соединенные блок формирования входной битовой последовательности, состоящий из преобразователя исходной информации в битовую, вход которого является входом устройства, и преобразователя параллельной информации в последовательную, блок преобразования последовательной информации в локально-параллельную и ОЗУ, причем узел сжатия информации содержит Фиг. 1 выходной мультиплексор на два входа, а узел хранения результата выполнен в виде буферной памяти с адресацией по плюс единице, выход которой служит выходом устройства, отличающееся тем, что в блок формирования входной битовой последовательности введен мультиплексор на два входа, выход которого соединен 4681 1 со входом преобразователя параллельной информации в последовательную, а первый вход соединен с выходом преобразователя исходной информации в битовую, блок преобразования последовательной информации в локально-параллельную выполнен в виде последовательно соединенных формирователя пяти векторов и преобразователя пяти векторов в пять метрических величин, причем выход преобразователя параллельной информации в последовательную соединен со входом формирователя пяти векторов, а выход преобразователя пяти векторов в пять метрических величин соединен со входом ОЗУ, ОЗУ выполнено с адресацией по плюс единице, с расположением локально-параллельной информации в пяти последовательных ячейках памяти, узел сжатия информации выполнен в виде сумматора, делителя на 2 и последовательно соединенных двухвходового формирователя пяти точек на окружности, вычислителя пяти центральных углов, вычислителя углов, образованных тремя точками на окружности, вычислителя синусов этих углов и вычислителя ангармонических отношений пяти точек окружности, причем выход ОЗУ соединен со входом сумматора и первым входом формирователя пяти точек на окружности, выход сумматора соединен со входом делителя на 2, выход которого соединен со вторым входом формирователя пяти точек окружности и первым входом мультиплексора, второй вход которого соединен с выходом вычислителя ангармонических отношений пяти точек окружности, выход узла хранения результата соединен со вторым входом мультиплексора блока формирования входной битовой последовательности, причем ячейки буферной памяти с результатами сжатия пяти метрических величин этого угла выполнены с одинаковым количеством разрядов. Изобретение относится к устройствам кодирования, в частности к устройствам сжатия любой информации, которая может быть представлена в виде битовой последовательности, и может быть использовано при разработке устройств для предварительной обработки больших массивов первичных данных. Наиболее целесообразно использовать его для сжатия первичной информации перед ее передачей по каналу связи. Существуют теоретические алгоритмы 1, позволяющие сжимать и, при необходимости, полностью восстанавливать исходную избыточную информацию. При этом параметры избыточности должны быть известны априори. Степень сжатия при этом определяется избыточностью источника, т.е. величиной энтропии исходного сообщения. Известны устройства для сжатия информации 2, 3. Известен цифровой компандер 4 для систем цифрового радиовещания и звукозаписи, содержащий анализатор старших разрядов, формирователь порядка мантисс, блок управления, формирователь адресов, первый и второй блоки оперативной памяти и блок вывода. Поскольку степень сжатия обратно пропорциональна качеству (разборчивости) восстановленного звука, которое субъективно определяется человеческим ухом, то реально достигаемая этим устройством степень сжатия информации не превышает десяти раз. Известна система сжатия избыточной информации 5, которая предназначена для сжатия факсимильной информации перед ее передачей по каналам связи. Система сжатия избыточной информации состоит из узла подготовки информации к сжатию, узла сжатия информации и узла хранения результата. Узел подготовки информации к сжатию состоит из блока формирования входной битовой последовательности, блока преобразования последовательной информации в локально-параллельную и ОЗУ. Блок формирования входной битовой последовательности состоит из преобразователя исходной информации в битовую и преобразователя параллельной информации в последовательную. Блок преобразования последовательной информации в локальнопараллельную состоит из матричного переключателя и блока выделения распознанных точек изображения,который выделяет из последовательности только биты, равные единице, соответствующие распознанным точкам исходного изображения, которые запускают матричный переключатель, вычисляющий не только соответствующий выделенной точке локально-параллельной блок в ОЗУ с произвольной выборкой, но и адрес выделенной точки внутри этого блока. Таким образом внутри каждого блока в ОЗУ формируется локальнопараллельная двухкоординатная информация о каждом знаке входной информации. Узел сжатия информации состоит из блока выделения восьми базовых точек, пятибитовый выход которого соединен с первым входом выходного мультиплексора и первым входом вычислителя М-разрядовой координатыи разрядной координаты У, выход которого соединен со вторым входом мультиплексора, вход блока выделения 8 базовых точек и второй вход координат соединены с выходом ОЗУ, а выход мультиплексора соединен со входом узла хранения результата. Блок выделения восьми базовых точек выделяет самые информативные точки из локально-параллельной двухкоординатной информации каждого блока ОЗУ, по которым возможно последующее восстановление(распознание) исходного знака, а вычислитель координат восьми базовых точек вычисляет -разрядный вектор по координатеи -разрядный вектор по координате У, причеми У являются внутренними локальными координатами локально-параллельными пространства, а проекции выделенных восьми точек на эти локальные оси координат будут задаваться единичными значениями битов в векторахи , которые через мультиплексор заносятся в узел хранения результата. Узел хранения результата выполнен в виде буферной памяти с адресацией по плюс единице, в которой сжатая информация длиной 5 бит ставится в соответствие каждому локально-параллельному блоку в ОЗУ и этим достигается достаточно большое сжатие исходной 4681 1 избыточной информации. По сжатой информации можно восстановить исходную информацию в порядке обратном сжатию. Недостатком предложенной системы сжатия избыточной информации является обязательная необходимость предварительного обучения ее (системы) распознаванию каждого знака, т.е. возможность распознавать информацию в локально- параллельном пространстве и поставить ей в соответствие 5 битовый вектор. Если информация в локально-параллельном пространстве будет представлена в разорванном виде, т.е. принцип слитности знака не соблюден, то сжатия, т.е. формирования вектора 5 бит, не произойдет. Поэтому известная система сжатия избыточной информации не сможет уже сжатую информацию снова подвергнуть повторному сжатию, а значит не способна к рекурсивному сжатию. В основу изобретения положена задача создания устройства, которое позволяло бы при введении как новых блоков, так и новых связей сжимать произвольную битовую последовательность, на основе которой обеспечивается рекурсивность этого процесса. Сжатие произвольной битовой информации достигается таким соединением известных и новых блоков,вычисляющих три числа, которые, при необходимости, позволяют путем поиска восстановить исходную битовую информацию. Степень сжатия информации за один цикл сжатия невелика и равна примерно 20 . Однако возможность рекурсивного повторения циклов сжатия позволяет говорить о возможности принципиально неограниченного сжатия. В предлагаемом устройстве степень сжатия ограничивается только емкостью промежуточного и буферного ОЗУ, а также последующим временем восстановления исходной информации. Существо изобретения заключается в том, что устройство для сжатия информации состоит из последовательно соединенных узла подготовки информации к сжатию, узла сжатия информации и узла хранения результата. Узел подготовки информации к сжатию содержит последовательно соединенные блок формирования входной битовой последовательности, состоящей из преобразователя исходной информации в битовую, вход которого является входом устройства, и преобразователя параллельной информации в последовательную, блок преобразования последовательной информации в локально-параллельную и ОЗУ. Узел сжатия информации содержит выходной мультиплексор на два входа, а узел хранения результата выполнен в виде буферной памяти с адресацией по плюс единице, выход которой служит выходом устройства. Согласно изобретению, в блок формирования входной битовой последовательности введен мультиплексор на два входа, выход которого соединен со входом преобразователя параллельной информации в последовательную, а первый вход соединен с выходом преобразователя исходной информации в битовую. Блок преобразователя последовательной информации в локально-параллельную выполнен в виде последовательно соединенных формирователя пяти векторов и преобразователя пяти векторов в пять метрических величин, причем выход преобразователя параллельной информации в последовательную соединен со входом формирователя пяти векторов, а выход преобразователя пяти векторов в пять метрических величин соединен со входом ОЗУ. ОЗУ выполнено с адресацией по плюс единице, с расположением локально-параллельной информации в пяти последовательных ячейках памяти. Узел сжатия информации выполнен в виде сумматора, делителя на 2 и последовательно соединенных двухвходового формирователя пяти точек на окружности, вычислителя пяти центральных углов, вычислителя углов, образованных тремя точками на окружности, вычислителя синусов этих углов и вычислителя ангормонических отношений пяти точек окружности, причем выход ОЗУ соединен со входом сумматора и первым входом формирователя пяти точек на окружности, выход сумматора соединен со входом делителя на 2, выход которого соединен со вторым входом формирователя пяти точек окружности и первым входом мультиплексора, второй вход которого соединен с выходом вычислителя ангармонических отношений пяти точек окружности. Выход узла хранения результата соединен со вторым входом мультиплексора блока формирования входной битовой последовательности, причем ячейки буферной памяти с результатами сжатия пяти метрических величин выполнены с одинаковым количеством разрядов. Техническим результатом реализации устройства для сжатия информации будет создание принципиально новых информационных технологий, позволяющих рекурсивно-неограниченно сжимать большие массивы первичной информации в реальном масштабе времени для передачи их по каналам связи. Изложенная сущность изобретения поясняется фиг. 1, 2, где на фиг. 1 изображена блок-схема устройства для сжатия информации, а на фиг. 2 изображена расчетная окружность с пятью точками, расстояния между которыми соответствуют пяти метрическим величинам, хранящимся в ячейках ОЗУ. Предлагаемое устройство(фиг. 1) включает узел подготовки информации к сжатию 1, узел сжатия информации 2 и узел хранения результата 3. В свою очередь узел подготовки информации к сжатию 1 состоит из блока формирования входной битовой последовательности 4, блока преобразования последовательной информации в локально-параллельную 5 и ОЗУ 6. Блок формирования входной битовой последовательности 4 состоит из преобразователя исходной информации в битовую 7, который унифицирует исходную текстовую, телеметрическую, видео- и прочую ин 3 4681 1 формацию, преобразователя параллельной информации в последовательную 8 и мультиплексора 9, который позволяет подключать к процессу сжатия не только исходную, но и уже подвергнутую сжатию информацию из узла хранения результата 3. Блок преобразования последовательной информации в локально-параллельную 5 состоит из формирователя пяти векторов 10, который входную последовательность нарезает на битовые вектора фиксированной длины, и преобразователя пяти векторов в пять метрических величин 11, который превращает вектор фиксированной длины в дробную часть метрической величины, целая часть которой всегда равна единице. Это необходимо для исключения равенства нулю метрических величин. ОЗУ 6 хранит промежуточную, т.е. подготовленную к сжатию информацию в виде локально-параллельных блоков информации из пяти метрических величин, хранящихся в рядом расположенных ячейках памяти. Узел сжатия информации 2 состоит из сумматора 12, который вычисляет сумму пяти метрических величин из локально-паралленого блока информации, делителя на 2 13, который делит вычисленную выше сумму на 2 и получает радиус окружности (фиг. 2), длина которой равна сумме пяти метрических величин,формирователя пяти точек на окружности 14, который определяет местонахождение пяти точек А, В, С,и Е на окружности, вычислитель пяти центральных углов, соответствующих пяти дугам на окружности, вычислитель углов 16, образованных тремя точками на окружности, вычислитель синусов 17 этих углов, вычислитель двух ангармонических отношений пяти точек на окружности 18, который вычисляет две числовые величины, которые через мультиплексор 19 заносятся в узел хранения результата 3. Третьей результирующей величиной, которая записывается в узел хранения результата через второй вход мультиплексора 19, является радиус окружности, вычисляемый в делителе на 2 13. Узел хранения результата 3 состоит из буферной памяти, в которой хранится результирующая сжатая информация. Использование для сжатия именно пяти метрических величин (векторов) позволяет после построения окружности, длина которой равна сумме пяти метрических величин, определять на ней ровно пять точек. Математически доказано 6, что два числовых значения инвариантов, названных ангармоническим отношением пяти точек на плоскости, являются уникальными для того расположения на окружности, по которому они были вычислены. Таким образом, знание двух числовых значений инвариантов позволяет однозначно восстановить путем поиска исходное положение точек на окружности. Если было бы выбрано шесть метрических величин, то пришлось бы вычислять уже не площади, а объемы или объемные углы, что серьезно усложнит вычисления. При выборе четырех метрических величин в качестве функции связи можно выбрать только проективное сложное отношение. А два произвольно выбранные сложные отношения не обладают свойством уникальности, и практически достижимая величина, сжатая за одну процедуру, составила бы всего несколько процентов,что неприемлемо уже практически. В предлагаемом устройстве можно в явном виде выделить два временных этапа его работы. На первом этапе работает только узел подготовки информации к сжатию 1, а на втором - узел сжатия информации 2, который сжимает подготовленную и расположенную в ОЗУ 6 информацию. Подготовка информации к сжатию начинается в преобразователе исходной информации в битовую 7. Здесь знаковая информация перекодируется в битовую, многоканальная телеметрия не только перекодируется, но и выстраивается в одну очередь и т.д. Формирование пяти векторов, преобразование их в пять метрических величин и запись в ОЗУ 6 производится последовательно, и этап заканчивается после заполнения ОЗУ, причем количество заполненных ячеек должно быть кратно пяти. Если этого не будет, то фиксируется ошибка. Обозначим через К количество локально-параллельных блоков информации из пяти метрических величин, записанных в ОЗУ. Теперь можно определить произвольный локально-параллельный блок информации как где -1-,-1-5. После заполнения ОЗУ начинается второй этап, то есть непосредственный процесс сжатия. 1 загружается в сумматор 12 и на его выходе получается сумма пяти метрических величин. После деления ее на 2 в делителе 13 вычислителя первая составляющая выходного сжатого представления 1. Математически это записывается как 1,11,21,31,41,51 Отметим, что вычисление радиуса окружности принципиально не зависит от особенностей исходной битовой информации. После вычисления величина 1 через мультиплексор 19 записывается в первую ячейку буферной памяти 3. Формирователь пяти точек 14 определяет положение всех пяти точек на окружности путем отложения на окружности радиусаметрических величин из 1. Затем вычисляются все пять центральных углов по формулам 1,1,1 Полученная окружность (фиг. 2) содержит пять точек А, В, С, ,и пять центральных углов. 4681 1 Для вычисления ангармонических отношений пяти точек на окружности необходимо предварительно вычислить величины углов, образованных тремя точками на окружности. Это и производится в вычислителе 16. Например, один из углов в радианах вычисляется по формуле 1/21)(45 Вычислитель синусов 17 вычисляет синусы углов, образованных тремя точками на окружности. Далее последовательно вычисляются две величины ангармонического отношения пяти точек на окружности по формулам 1( ) и через мультиплексор 19 записываются в буферную память узла хранения результата 3, причем А 1 - во вторую, а В 1 - в третью. Из всех приведенных формул следует, что как и 1, так и А 1 и 1 могут быть вычислены для произвольной исходной битовой информации, т.е. работа предлагаемого устройства принципиально не зависит от особенностей исходной битовой последовательности. Таким образом, пять метрических величин 1 сжимаются в 1 А 1 и В 1. Далее аналогично производится сжатие всех остальных 1 из ОЗУ. После сжатия последних пяти метрических величин на ОЗУ производится переключение мультиплексора 9 на прием информации с выхода с буферной памяти 20 до окончания сжатия. Теперь в узле подготовки информации к сжатию 1 в качестве исходной информации используется информация, хранящаяся в буферной памяти 20, которая сначала превращается в метрические величины, а затем и в рекурсивно сжатую информацию, которая снова записывается в буферную память 3 результата на место считанной. Эта рекурсивная процедура продолжается до тех пор, пока вся исходная информация не будет сжата до величины, равной 1 А 1 В 1 бит. На этом работа устройства для сжатия информации прекращается, а информация готова к передаче ее по каналам связи. Таким образом, предлагаемое устройство сжатия информации позволяет рекурсивно сжимать произвольную информацию, представленную в виде битовой последовательности, без предварительного обучения системы распознаванию элементов входной информации. Степень сжатия информации за один цикл сжатия равна примерно 20 . Однако возможность рекурсивного повторения циклов сжатия позволяет осуществить принципиально неограниченное сжатие. Описание чертежа на фиг. 1 Предлагаемое устройство (фиг. 1) включает узел подготовки информации к сжатию 1, узел сжатия информации 2 и узел хранения результата 3. Узел подготовки информации к сжатию 1 состоит из блока формирования входной битовой последовательности 4, блока преобразования последовательной информации в локально-параллельную 5 и ОЗУ 6. Блок формирования входной битовой последовательности 4 состоит из преобразователя исходной информации в битовую 7, преобразователя параллельной информации в последовательную 8 и мультиплексора 9. Блок преобразования последовательной информации в локально-параллельную 5 состоит из формирователя пяти векторов 10 и преобразователя пяти векторов в пять метрических величин 11. ОЗУ 6 хранит промежуточную, т.е. подготовительную к сжатию информацию. Узел сжатия информации 2 состоит из сумматора 12, формирователя пяти точек на окружности 14, вычислителя углов 16 и вычислителя синусов 17 этих углов, вычислителя двух ангормонических отношений пяти точек на окружности 18, мультиплексора 19 и узла хранения результата 3. Источники информации 1. Кричевский Р.Е. Сжатие и поиск информации. - М. Радио и связь, 1989. 2. А.с. СССР 13323546 МПК 08 С 19/16, 1987. 3. А.с. СССР 1456983 МПК 08 С 19/28, 1989. 4. А.с. СССР 1427575, МПК Н 03 М 7/50, 1988. 5. Заявка Японии 59-167180, Н 04 М 1/41, 0615/20, 1983. 6. Колмогоров Н.А. Теория ангормонического отношения пяти точек на плоскости / Труды Кировского зоотехниковетеринарного института, 1938. - Т. 3. Вып. 2-3. - С. 161-169. Национальный центр интеллектуальной собственности. 220072, г. Минск, проспект Ф. Скорины, 66. 6