Способ сжатия последовательности информационных сигналов

 

Изобретение относится к преобразованию кодов и может быть использовано для сжатия передаваемой информации в системах передачи данных сложных информационных систем. Цель изобретения - сжатие минимальных двоичных информационных объемов для передачи не ожидая окончания сжатия всего объема данных входного источника. Сущность изобретения: введены следующие операции: разбиение последовательности информационных сигналов на последовательности заданной длительности L анализа на поэлементное сравнение с содержанием вводимого статиcтического словаря потоков размером 2^L и динамического словаря потоков размером 2^M - 2^L, преобразование кодовыми словами фиксированной длины М; запись последовательностей информационных сигналов длительностью M + L в динамический словарь потоков и последующей передачи, причем в динамический словарь дополнительно вводятся величины соответствия полученного отображения видоизменений двоичный поток - кодовое слово фиксированной длины M количеству использований потока. 2 ил.

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

Известен способ сжатия информации [1] Хаффмана. Способ использует префиксную схему кодирования для обозначения кодовыми словами длины переменных. Минимальная избыточность достигается, если обозначать самыми короткими кодами наиболее вероятные символы, а самые длинные коды использовать для наименее коротких символов.

Основным недостатком способа Хаффмана является необходимость предварительной фиксации вероятности появления символов.

Наиболее близким по технической сущности является способ сжатия Лемпеля-Зива [2] Способ сжатия информации Лемпеля-Зива использует синтаксический метод для устранения поточной избыточности путем динамического кодирования данных выходного источника. При этом способ потоки символов синтетически анализируются в данных и используются для построения динамического словаря потоков хранящего кодовые отображения поток-слово.

Каждый поток обозначается кодовым словом, основанным на адресе потока в словаре. Чаще встречающиеся потоки группируются в более длинные потоки, которые дают много символов, представляемых некоторым простым кодовым словом. Длина кодового слова зависит от размера динамического словаря потоков и принимает значения 9-13 бит. В свою очередь кодовое слово является просто словарным адресом соответствующего потока.

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

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

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

Новыми существенными признаками изобретения являются операция последовательного разбиения двоичного информационного потока на элементарные потоки не превышающие заданной длины L, полученные элементарные потоки группируются и претерпевают видоизменение путем операции анализа на поэлементное сравнение с содержимым вводимого статического словаря потоков, содержащего соответствие 2^L двоичных комбинаций кодовым словам фиксированной длины М, динамического словаря потоков размером 2^M-2^L, и операции перекодирования кодовыми словами фиксированной длины М, видоизмененный двоичный поток длины M+L заносится в динамический словарь потоков и передается, причем в динамический словарь дополнительно вводится соответствие полученного отображения видоизменений двоичный поток - кодовое слово фиксированной длины M, количеству использований потока.

Последовательность операций способа сжатия передаваемых данных рассмотрим для случая: кодовое слово фиксированной длины M=3, а элементарный поток заданной длины L=2.

На фиг. 1 представлена операция разбиения выбранного информационного потока; на фиг.2 совокупность операций составляющих сущность способа.

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

На фиг.2 показан вводимый статический словарь потоков размером 2^L=4, где позиция 1 возможные элементарные потоки заданной длины и им соответствующие кодовые слова фиксированной длины позиция 2. По итогам операции анализа на поэлементарное сравнение с содержимым статического словаря потоков, а затем и с имеющимися значениями в динамическом словаре потоков, который дополняется новыми строками до размера 2^M-2^L. В позиции 1 фиксируется количество использований анализируемой группы элементарных потоков при следующих построениях в динамическом словаре потоков, в позиции 2 записывается кодовое слово фиксированной длины, в позиции 3 показан соответствующий исходный вид анализируемый группы элементарных потоков, в позиции 4 сжатое кодовое отображение сохраняемое и используемое для передачи.

Согласно выбранному примеру в первой строке динамического словаря потоков в позиции 2 записывается следующее по порядку кодовое слово фиксированной длины 100, в позиции 3 соответствующее ему анализируемое объединение элементарных потоков длина которого на один элементарный поток больше, чем можно закодировать известными кодовыми словами фиксированной длины из статического словаря потоков или динамического словаря потоков 0001. В позиции 4 000 01, первому элементарному потоку из объединения 00 в статическом словаре потоков соответствует кодовое слово фиксированной длины - 000, а второй элементарный поток из объединения 01 просто переписывается. Полученное сжатое кодовое отображение постоянной длины 000 01 готово к передаче. Затем из данных входного источника выбирается следующее объединение элементарных потоков длина которого на один элементарный поток больше, чем можно закодировать известными кодовыми словами фиксированной длины из статического словаря потоков и динамического словаря потоков 00 01 10. Во второй строке динамического словаря потоков, в позиции 2 записывается следующее по порядку кодовое слово фиксированной длины 101, в позиции 3 соответствующее ему выбранное объединение 00 01 10. Слиянию первых двух элементарных потоков из выбранного объединения, в первой строке динамического словаря потоков соответствует кодовое слово фиксированной длины 100, поэтому в позицию 1 первой строки заносится 1 количество использований объединенного потока, а третий элементарный поток из объединения 10 просто переписывается. Таким образом во второй строке динамического словаря потоков в позиции 4 получается сжатое кодовое отображение постоянной длины 100 10 готовое к передаче. Подобным образом осуществляется анализ и сжатие всего двоичного информационного потока поступающего от входного источника, дальнейшие этапы сжатия показаны в оставшихся строках динамического словаря потоков.

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

Согласно выбранному примеру фиг.2 S 3/4.

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

Таким образом введение новых существенных признаков позволяет сочетать сжатие двоичных информационных потоков минимальной длины 2·L и более с возможностью передачи сжатого объема постоянной длины M+L, сохраняемого в периодически корректируемом динамическом словаре потоков, что видно из примера (фиг.1-2) и ниже приведенного расчета коэффициента сжатия: K_сж=(1-C/R)·100% (1) где C сумма длин сжатия потоков фиг.2 позиция 4, R сумма длин исходных элементарных потоков фиг.1.

По соотношению (1): K_сж=(1-20/26)·100%23% Очевидно, что изобретение не ограничивается вышеописанным примером его осуществления, исходя из него могут быть предусмотрены и другие варианты, не выходящие за рамки предмета изобретения, например в зависимости от стандартных длин используемых слов, для информационного обмена в сложных информационных системах, величины M и L могут принимать значения L=8, M=12.

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

Способ сжатия последовательности информационных сигналов, основанный на приеме исходных последовательностей сигналов, формировании последовательности кодовых сигналов одинаковой длительности, соответствующих последовательностям информационных сигналов и их последующей передаче, отличающийся тем, что принимаемые последовательности информационных сигналов разбивают на подпоследовательности заданной длительности L, в исходном состоянии построчно формируют статический словарь кодовых сигналов, содержащий 2^L всевозможных комбинаций подпоследовательностей информационных сигналов длительностью L и им соответствующих 2^L подпоследовательностей кодовых сигналов длительностью М, где М≥ L + 1, формируют динамический словарь кодовых сигналов, который построчно заполняют до объема 2^M 2^L подпоследовательностями информационных сигналов различной длительности и им однозначно соответствующими кодовыми сигналами длительностью М + L, по мере формирования которых осуществляют их передачу, кодовые сигналы длительностью М + L формируют путем k-кратного последовательного объединения подпоследовательностей информационных сигналов по результатам анализа на поэлементное сравнение с содержимым динамического и статического словарей кодовых сигналов, причем последовательно выполняемые операции объединения и анализа заканчивают при получении объединенной подпоследовательности информационных сигналов длительности k · L на одну больше, чем можно обнаружить в словарях, записи полученной объединенной подпоследовательности в первую свободную строку динамического словаря с однозначным присвоением кодового сигнала длительности М + L, включающего номер строки статического или динамического словаря, представленного подпоследовательностью кодовых сигналов длительности М, в которой была осуществлена последняя операция анализа, и последнюю подпоследовательность информационных сигналов длительности L, записанных в текущую строку, причем номер первой строки динамического словаря больше на единицу номера последней строки статического словаря кодовых сигналов, при этом в каждой заполненной строке динамического словаря формируют сигнал А_i, соответствующий количеству повторяемости содержащегося объединения подпоследовательности информационных сигналов в последующих его строках, динамический словарь кодовых сигналов преобразуют при превышении его объема путем исключения тех строк, у которых значение A_i меньше S, где

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

РИСУНКИ

Рисунок 1, Рисунок 2