Файл: Методы кодирования данных (ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ КОДИРОВАНИЯ ДАННЫХ).pdf

Биты	Четверичный символ	Уровень, В
00	-3	-2,5
01	-1	-0,883
10	+3	+2,5
11	+1	+0,883

4B3T

4B3T — блок из 4 бит (16 состояний) кодируется тремя троичными символами (27 символов). Из множества возможных методов изменений рассмотрим MMS43, который используется в интерфейсе BRI сетей ISDN (таблица). Тут применяются специальные методы для исключения постоянной составляющей напряжения в линии, в следствии чего кодирования ряда комбинаций зависит от предыстории — состояния, где находится кодер. Пример: последовательность бит 1100 1101 будет представлена как: + + + — 0 -.

Таблица 3 - Специальные методы для исключения постоянной составляющей напряжения в линии

Двоичный код	S1	Переход	S2	Переход	S3	Переход	S4	Переход
0001	0 — +	S1	0 — +	S2	0 — +	S3	0 — +	S4
0111	— 0 +	S1	— 0 +	S2	— 0 +	S3	— 0 +	S4
0100	— + 0	S1	— + 0	S2	— + 0	S3	— + 0	S4
0010	+ — 0	S1	+ — 0	S2	+ — 0	S3	+ — 0	S4
1011	+ 0 —	S1	+ 0 —	S2	+ 0 —	S3	+ 0 —	S4
1110	0 + —	S1	0 + —	S2	0 + —	S3	0 + —	S4
1001	+ — +	S2	+ — +	S3	+ — +	S4	— — —	S1
0011	0 0 +	S2	0 0 +	S3	0 0 +	S4	— — 0	S2
1101	0 + 0	S2	0 + 0	S3	0 + 0	S4	— 0 —	S2
1000	+ 0 0	S2	+ 0 0	S3	+ 0 0	S4	0 — —	S2
0110	— + +	S2	— + +	S3	— — +	S2	— — +	S3
1010	+ + —	S2	+ + —	S3	+ — —	S2	+ — —	S3
1111	+ + 0	S3	0 0 —	S1	0 0 —	S1	0 0 —	S3
0000	+ 0 +	S3	0 — 0	S1	0 — 0	S2	0 — 0	S3
0101	0 + +	S3	— 0 0	S1	— 0 0	S2	— 0 0	S3
1100	+ + +	S4	— + —	S1	— + —	S2	— + —	S3

---

Итог

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

ГЛАВА 2 АНАЛИЗ МЕТОДОВ КОДИРОВАНИЯ ДАННЫХ В РАЗЛИЧНЫХ СФЕРАХ ДЕЯТЕЛЬНОСТИ

2.1 Кодирование графической информации

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

Высокое качество изображений, полученных цифровой фотокамерой, характеризуется большим разрешением (порядка 4000 х 3000, т.е. 8 мегапикселей) и глубиной цвета 24 бита на пиксель. Технические характеристики профессиональных фотоаппаратов, которые набирают популярность среди рядовых потребителей, позволяют делать снимки с глубиной цвета 48 бит на пиксель, из-за чего размер фотоснимка может превышать 200 мегабайт. Таким образом, на первый план выходит проблема сжатия изображений. Основные форматы сжатия изображений имеют ряд недостатков^[1], которые можно устранить за счет модификации существующих алгоритмов сжатия изображений.

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

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

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

---

Алгоритм Лемпеля-Зива (LZ-compression) является основой целого семейства алгоритмов словарного сжатия данных^[3]. В его основе лежит упаковщик, который содержит в себе определенное число символов в буфере. Используя поиск по словарю, находят самую длинную подстроку входного потока, которая совпадает с одной из подстрок, находящихся в буфере, после чего выводят индекс подстроки, вычтенный из размера буфера. В случае отсутствия совпадений, в выходной поток символов копируется следующий символ и т.д.

Не смотря на простоту алгоритма, при поиске совпадений он подразумевает перебор всех символов, находящихся в буфере, за счет чего увеличивается время сжатия.

Стандарт сжатия изображений JPEG включает два способа сжатия: первый предназначен для сжатия без потерь, второй – сжатия с потерей качества. Метод сжатия без потерь, используемый в стандарте lossless JPEG основан на методе разностного (дифференциального) кодирования. Основная идея дифференциального кодирования состоит в следующем. Обычно изображения характеризуются сильной корреляцией между точками изображения. Этот факт учитывается при разностном кодировании, а именно, вместо сжатия последовательности точек изображения x₁,x₂,....x_n, сжатию подвергается последовательность разностей y_i=x_i-x_i-1, i=1,2,...N, x₀=0. Числа y_i называют ошибками предсказания x_i. В стандарте losslessJPEG предусмотрено формирование ошибок предсказания с использованием предыдущих закодированных точек в текущей строке и\или в предыдущей строке. Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и разархивированного изображений.

Для текстовых файлов чаще других употребляется кодировка Хаффмана, заключающаяся в том, что символы текста заменяются цепочками бит разной длины. Методика Хаффмана гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву^[4]. Применительно к сжатию изображений в основе такого метода лежит учет частоты появления одинаковых байт в изображении. При этом пикселям исходного изображения, которые встречаются большее число раз, сопоставляется код меньшей длины, а встречающимся редко - код большей длины (т.е. формируется префиксный код переменной длины). Для сбора статистики требуется два прохода по файлу - один для просмотра и сбора 16 статистической информации, второй - для кодирования. Коэффициенты сжатия: 1/8, 2/3, 1. При использовании такого метода требуется запись в файл и таблицы соответствия кодируемых пикселов и кодирующих цепочек. Такое кодирование применяется в качестве последнего этапа архивации в JPEG. Методы Хаффмана дают достаточно высокую скорость и умеренно хорошее качество сжатия. Основным недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к величине 2-м, поскольку каждый символ кодируется целым числом бит. Так, при кодировании данных с двухсимвольным алфавитом сжатие всегда отсутствует, т.к. несмотря на различные вероятности появления символов во входном потоке алгоритм фактически сводит их до 1/2. Такой алгоритм реализован в формате TIFF.

---

Наиболее известный и простой алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE)^[5]. Суть данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при работе, и быстро выполняется. Данный метод, как правило, достаточно эффективен для сжатия растровых графических изображений (BMP, PCX, TIFF), т.к. последние содержат достаточно длинные серии повторяющихся последовательностей байтов.

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

Для повышения эффективности работы RLE-алгоритма предлагается использовать реализацию классического решения, основанную на простановке меток (служебных байт) вначале кодированных цепочек. Один бит выделяется под тип последовательности (одиночный символ или серия), а в оставшихся 7 битах хранится длина последовательности. Таким образом, максимальная длина кодируемой последовательности – 127 байт. Однако есть два важных момента, на которые стоит обратить внимание. Не может быть последовательностей с нулевой длиной. Для решения этой проблемы можно увеличить максимальную длину до 128 байт, отнимая от длины единицу при кодировании и прибавляя при декодировании. Второе, что можно заметить – не бывает последовательностей одинаковых элементов единичной длины^[6]. Поэтому, от значения длины таких последовательностей при кодировании мы будем отнимать ещё единичку, увеличив тем самым их максимальную длину до 129 (максимальная длина цепочки одиночных элементов по-прежнему равна 128). Таким образом, цепочки одинаковых элементов могут иметь длину от 2 до 129.

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

---

Рис. 1. Схема модифицированного RLE-алгоритма

На битовом уровне в служебном байте СБ1 (Рис.1) выделяется ещё один бит под индикацию длинной цепочки. Если индикатор выставлен в единицу, то добавляется ещё один служебный байт СБ2, который хранит в себе длину цепочки. Таким образом, уменьшается длина коротких цепочек (65 элементов вместо 129), однако появляется возможность всего тремя байтами закодировать цепочки длиною до 16386 элементов (2¹⁴ + 2).

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

2.2 Применение циклического кодирования

Циклические коды нашли свое применение при передаче информации по каналам связи. Стандартами международных организаций ITU-T и МОС установлено, что вероятность ошибки при телеграфной связи не должна превышать 3*10^-5 на знак, а при передаче данных – 10^-6 на единичный элемент, бит. На практике допустимая вероятность ошибки при передаче данных может быть еще меньше – 10^-9. Однако возможности каналов связи часто не соответствуют требованиям, предъявляемым к верности принимаемой информации. Каналы связи, особенно проводные каналы большой протяженности и радиоканалы, обеспечивают вероятность ошибки на уровне 10^-3...10^-4 даже при использовании устройств, улучшающих качество каналов связи.

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

Помехоустойчивый код характеризуется тройкой чисел ( n, k, d₀ ), где n – общее число разрядов в передаваемом сообщении, включая проверочные, k – число информационных разрядов, d₀ – минимальное кодовое расстояние между разрешенными кодовыми комбинациями. Число обнаруживаемых и/или исправляемых ошибок связано с минимальным кодовым расстоянием соотношениями:

---