Моделирование сжатия сообщений в одностороннем канале передачи дискретных сообщений

Размещено на http://www.allbest.ru/

Моделирование сжатия сообщений в одностороннем канале передачи дискретных сообщений

Орлов В.А., Иванов В.А., Стельмах Э.П.

Сжатие данных при их передаче в канал связи позволяет не только уменьшить их объем, но и сократить время передачи. Однако получить существенный выигрыш от сжатия можно лишь за счет увеличения сложности обработки сообщения. При этом одним из недостатков сжатия является чувствительность к ошибкам в теле сжатого сообщения. Например, если при передаче произошла ошибка хотя бы в одном бите сжатых данных, то в этом случае весь восстановленный фрагмент сообщения после нее оказывается искаженным и его уже невозможно восстановить даже при условии дополнительного ресурса времени обработки. Поэтому для каналов связи с передачей сжатых дискретных сообщений (СДС), задают требование к минимальной вероятности ошибки. В двухсторонних каналах связи реализация данных требований достигается за счет организации обратного канала. Под обратным каналом будем понимать канал, с помощью которого приемная сторона оказывает управляющее воздействие на параметры передачи с целью достижения требуемой минимальной вероятности ошибки (подтверждение приема и перезапрос, адаптация параметров передачи). Однако не всегда имеется возможность организации такого канала. Каналы без обратной связи существуют в системах радиомониторинга, при организации симплексной связи и, в ряде случаев, при получении информации пользователем с удаленного сервера, например, при работе в сети Интернет, при хранении информации в сжатом виде.

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

При наличии ресурса времени на обработку искаженного сжатого сообщения для исправления обнаруженных ошибок можно воспользоваться структурной, алгоритмической и остаточной избыточностью сжатого сообщения, которая определяется статистическими свойствами источника сообщений (ИС).

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

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

Во-первых, обработка осуществляется в отложенном режиме,

(возможно ),

Во-вторых, максимизация точности локализации,

,

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

В-третьих, максимизация вероятности исправления ошибки,

,

где - число исправленных ошибок, - общее число ошибок.

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

Формат архивов RAR поддерживает специальный тип избыточных данных, называемой информацией для восстановления. Достоинство этого подхода заключаются в возможности восстановления информации даже в случае последовательного повреждения до 0,7% от общего объема сжатых данных. Недостаток - увеличения объема сжатого сообщения до 10% от объема архива [1]. Однако внесение дополнительной избыточности не всегда позволяет исправить ошибку в сжатых данных, а в большинстве случаев пользователь и вовсе не обращает внимания на такую информацию.

Для решения задачи исправления ошибок в СДС авторы предлагают подход, основанный на разладке [2,3], под которой понимается любое отступление от однородности наблюдений, скачкообразное изменение какой-либо вероятностной характеристики [3].

Классическая модель канала передачи сжатых сообщений [4] не дает знаний, на основе которых можно получить данные о разладке в процессе декомпрессии искаженного сжатого сообщения.

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

Рисунок 1 - Канал со сжатием

На рисунке 1 ИС - источник сообщений, К - компрессор, КПК - кодер помехоустойчивого кода, ДСК - двоичный симметричный канал, ДПК - декодер помехоустойчивого кода, Д - декомпрессор, ПС - получатель сообщения.

Модель ДСК, включенная в состав модели канала передачи со сжатием, позволяет описать большинство физических каналов связи. Разработчики, для описания математической модели канала со сжатием, определили множество возможных сигналов на входе канала (множество входов) X, множество сигналов на выходе Y и для каждого сигнала на входе X рассчитана совместная вероятность появления символов на множестве сигналов на выходе Y. При этом каждый символ выходной последовательности статистически зависит только от символа стоящего на соответствующей позиции во входной последовательности. Канал полностью описывается матрицей переходных вероятностей:

,

где - вероятность ошибочного перехода и равна и/или ().

Исходя из структуры формата сжатия Deflate [5], получившего наибольшее распространение в системах передачи данных, авторы выявили два основных класса ошибок.

Первый - это одиночные ошибки, которые происходят, в случае если искажению подвергся литерал (отдельный некодируемый символ). При декомпрессии сообщения с таким искажением происходит единичные замещения символов и восстановленное сообщение практически не изменяет своих статистических свойств по сравнению с исходным, изменение характеристик достигает 3 %. В связи с этим распознать ошибку, произошедшую в литерале, не представляется возможным.

Второй - пакеты ошибок, которые возникают, если искажению подвергается ссылка на словарь (значение длины и смещения). Длина пакетов ограничена, если в качестве словаря сжатия используется статический словарь. Если в качестве словаря используется ранее декомпрессированный сегмент (динамическое сжатие), то длина пакетов неограничена. Во втором случае статистические свойства восстановленного сообщения изменяются значительно, в ряде случаев изменения превышают 90%, и само восстановленное сообщение существенно отличается от исходного. При этом, чем ближе к началу сжатых данных произошла ошибка, тем больше искажений в восстановленном сообщении.

На рисунке 2 приведены полученные авторами результаты экспериментов, на основе расчета энтропии восстановленного сообщения в зависимости от места ошибки. Ошибка в теле СДС обнаруживается на основании сравнения контрольной суммы (CRC) распакованных данных и исходного сообщения. В то же время это позволяет только обнаружить наличие некоторого неизвестного числа ошибок, местоположение же ошибок CRC определить не позволяет.

Рисунок 2 - Расчет энтропии восстановленного сообщения в зависимости от места ошибки

Реализации алгоритмов для известных методов восстановления СДС основаны на детерминированном подходе (4), при этом не предусматривается какого-либо статистического решения, поскольку отсутствует информация, необходимая для данного решения.

вi=T-1(Si,Ci),

где вi - символ восстановленного сообщения, T-1 - алгоритм декомпрессии, Si,Ci - модель источника сообщений и символ сжатого сообщения соответственно. дискретный сообщение сжатие энтропия

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

вi'=T-1(Si,Ci,Iis),

где Iis - дополнительная информация о разладке между исходным и восстановленным файлом.

В этом случае схема декомпрессии на основе использования информации о разладке представлена на рис. 3.

Рисунок 3 - Схема декомпрессии на основе использования информации о разладке

В разработанной схеме сжатое дискретное сообщение с ошибкой поступает на декомпрессор, с выхода которого поступает восстановленное сообщение (ВС). Блок сравнения и принятия решения вычисляет информацию о разладке и определяет интервал, в котором произошла ошибка в теле принятого сообщения.

Традиционно для описания каналов передачи используется концепция двух связанных источников. По отношению к каналу со сжатием авторами в качестве Iis рассматривается совместная вероятность, представляемая в качестве матрицы переходных вероятностей, и меры информационных потоков, представленные в выражениях 6 - 10.

Информация пары символов совместных событий

Энтропия при совместных событиях

Условная информация

Условная энтропия

Взаимная информация пары событий

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

Структурная модель канала со сжатием, предложенная авторами на рисунке 2, описывается матрицей переходных вероятностей. На ее основе экспериментально получена зависимость переходных вероятностей от позиции ошибки в теле СДС, представленная на рисунке 4.

Рисунок 4 - Зависимость переходных вероятностей от позиции ошибки в теле СДС

Анализ полученных авторами результатов позволяет разделить переходные вероятности на два условных подкласса. Первый - переходные вероятности, группирующиеся около 0 и около 1 - при ошибке в литерале. Второй - переходные вероятности при ошибке в значении длины и смещения, распределяющиеся по нелинейному закону.

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

,

где , - центрированные реализации, а и - математическое ожидание соответствующих случайных процессов Y и X [6].

Анализ предложенной модели канала со сжатием позволяет сделать следующие выводы:

Для оценки влияния ошибки в СДС на восстановленное сообщение необходимо агрегировать компрессор, канал без шума и декомпрессор в канал со сжатием.

Локализация ошибок в сжатых данных возможна за счет структурной, алгоритмической и естественной (остаточной) избыточности сжатого сообщения, при условии наличия временного ресурса на усложнение обработки.

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

Литература

1. Корецкий, А.А. Архивирование данных на персональном компьютере. [Текст] / А.А. Корецкий. - М.: Познавательная книга плюс, 2002. - 224 с.

2. Ширяев, А.Н. Статистический последовательный анализ. [Текст] / А.Н. Ширяев. - М.: Наука, 1969. - 231 с.

3. Васильченко, С.Г. Алгоритм обнаружения разладки случайной последовательности [Текст] / С.Г. Васильченко. - Фундаментальная и прикладная математика. 2002, том 8, № 3, с 655--665.

4. Шеннон, К. Работы по теории информации и кибернетики. [Текст] / К. Шеннон. - М.: Иностранная литература, 1963, 824 с.

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

6. Большаков А.А. Методы обработки многомерных данных и временных рядов[Текст]: Учебное пособие для вузов. / А.А. Большаков, Р.Н. Каримов. - М.: Горячая линия - Телеком, 2007. - 522с.: ил.

Аннотация

The model of one-way channel for transmitting discrete compressed messages Different methods of designing the model of one-way channel for transmitting discrete compressed messages aggregating compressor channel and decompressor in compressed data channel are considered. The transition probability alteration and information flow measures when bugs appear in discrete compressed message are described. The results of using the designed model are given in the article.

Размещено на Allbest.ru