Способ сжатия информации

Способ сжатия информации

Иллюстрации

Показать все

Реферат

Предлагаемое изобретение относится к области информационных технологий, информационной техники, телемеханики и др.

Известны следующие способы сжатия информации: дельта-кодирование [1], алгоритм Лемпеля-Зива-Велча [2], кодирование методом Хаффмана [1], арифметическое кодирование [3] и др. При дельта-кодировании используются разницы между последовательными данными вместо самих данных. Это помогает в случае дальнейшей компрессии этих данных, в которых часто встречаются повторяющиеся значения, и не очень полезно в случае, когда используется само по себе. Алгоритм Лемпеля-Зива-Велча при сжатии динамически создает таблицу преобразования строк. Для каждого конкретного случая она индивидуальна. При кодировании методом Хаффмана и арифметическом кодировании необходимо проводить анализ текста с целью определения частот появления символов в данном тексте с последующим определением вероятности их появления. Во-первых, это создает дополнительные трудности. Во-вторых, в разных текстах одни и те же символы будут закодированы по-разному. В-третьих, закодированный текст передается вместе с кодовой таблицей данных символов, что увеличивает объем передаваемой информации.

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

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

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

Способ осуществляется следующим образом. Кодируемые символы размещают в узлах матрицы размерностью m×n (фиг.1). Максимальное число кодируемых символов N=m·n. Порядковые номера строк и столбцов матрицы представляют в двоичном виде: 000, 001, 010… и т.д. Совокупность кода строки и кода столбца, на пересечении которых расположен символ, есть кодовое представление данного символа. Например, код символа z₂₃ будет представлять собой комбинацию 010011. При кодировании какого-либо сообщения каждый элемент данного сообщения представляют соответствующим кодом. Например, кодовая комбинация символов сообщения z₂₁z₂₀z₂₃ будет иметь вид 010001010000010011. При наличии в сообщении группы нескольких последовательно расположенных символов, находящихся на одной строке (одном столбце) матрицы, данная группа символов образует общий код, состоящий из кода общей строки и кодов столбцов (из кода общего столбца и кодов строк). Причем элементы общего кода группы символов располагают последовательно с выделением кода строки от кодов столбцов (кода столбца от кодов строк) по тому или иному признаку: изменение полярности, амплитуды, частоты, фазы электрических сигналов. Например, кодовая комбинация символов сообщения z₂₁z₂₀z₂₃ будет иметь вид 010001010000010011 в промежуточном варианте и окончательно 010001000011. Это позволяет более компактно сжать необходимую информацию.

Пример 1. Разместим в узлах матрицы размерностью 4×4 буквы русского алфавита (фиг.2). Далее закодируем предлагаемым способом слово «зима». Получим промежуточный результат 1001100001010100 и окончательно 100100010100. В данном случае кодовая комбинация сократилась с 16 до 12 знаков.

Составленную матрицу можно использовать для кодирования любой информации, содержащей символы, расположенные в узлах данной матрицы. Матрицу можно расширить до необходимой размерности m×n, чтобы поместить в ее узлы все символы, которые используются для передачи соответствующей информации.

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

Возможна следующая техническая реализация данного способа сжатия информации (фиг.3). Через каждый узел матрицы проходит 3 разновидности шин: общая шина сообщений и координатные шины - шины x и шины y. В каждом узле матрицы расположен регистр кода (память) сообщения и элемент «И», на один вход которого подается код сжимаемого сообщения S и на другой вход подается код сообщения, хранимый в регистре данного узла (фиг.4). При совпадении этих двух кодов на выходе элемента «И» формируется единица, которая поступает на координатные шины x и y, и осуществляет через элементы «И» включение триггеров и регистра данной шины x и регистра данной шины y. С одного выхода триггера поступает сигнал на второй вход элемента «И» данного триггера, а с другого входа снимается код адреса данной шины. При поступлении следующего сообщения, код которого находится в регистре узла, связанного с этой же шиной, вызывающего появление единицы, переключение триггера уже не происходит. При поступлении нескольких единиц последовательно на данный триггер с выхода мы снимаем не совокупность кодов адреса триггера, а всего лишь один код (эффект сжатия). При поступлении нового сообщения, код которого отличается от предыдущего и единицы будут расположены в других шинах, происходит включение других триггеров и сброс ранее включенных триггеров. На выходе регистра шины сообщения происходит запись кодовой комбинации S' из кодов адресов x и кодов адресов y. На приемной стороне принятая сжатая комбинация вновь воспроизводится в исходную.

Источники информации

1. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. - М.: ДИАЛОГ-МИФИ, 2003. - 384 с.

2. Основы кодирования. Вернер М. - М.: Техносфера, 2004. - 288 с.

3. Теория информации. Кодирование дискретных вероятностных источников. Учебное пособие. В.Н.Потапов. Новосибирск. 1999. - 71 с.

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