Кодирование повторов

8.2.4.1 Кодирование последовательностей повторяющихся символов, метод RLE предусматривает замену последовательности повторяющихся символов на строку, содержащую этот символ, и число, соответствующее количеству его повторений. В качестве примера рассмотрим сжатие последовательности символов ACCOUNTbbbbbbbMOUNT, в которой b означает символ пробела. Если для обозначения выполненного сжатия символов пробела модем использует специальный символ , то между модемами будет передана последовательность символов ACCONTSc7MOUNT. Символ в этой последовательности означает, что было произведено сжатие символов пробела, а число 7 указывает, сколько именно символов пробела заменено символом . С помощью этой информации принимающий модем может восстановить данные.

Однако в последовательности передаваемых символов может встретиться пара символов S и с, которые являются частью данных, а не специальным символом , обозначающим сжатие. Чтобы принимающий модем воспринимал эти символы как данные, передающий модем при обнаружении пары символов добавляет в передаваемую последовательность еще одну такую пару. Таким образом, если модем принял от терминала поток данных XYZScABC, то по телефонному каналу он передаст следующую последовательность символов: XYZScScABC. На принимающем модеме при обнаружении первого специального символа Sc проверяется следующий символ. Если им окажется не число, а еще один такой символ, модем отбросит второй символ и восстановит первоначальный поток данных.

Сжатие позволяет увеличить пропускную способность систем передачи данных, но если один или более символов будут переданы с ошибкой, это может привести к очень печальным последствиям при восстановлении потока данных. В качестве примера покажем, к чему может привести ошибка при передаче последовательности символов AAAAAAAA. Предположим, что используется алгоритм сжатия RLE, в котором символ, означающий сжатие, представлен последовательностью битов 11111111, а символ A – последовательностью 01000001 (табл. 8.6.).

На рис. 8.6 демонстрируется, к чему может привести ошибка всего лишь в одном символе переданной последовательности битов.

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

 

– Последовательность одинаковых символов: АААААААА

– Последовательность символов после сжатия: Sc 8 A

– Двоичное представление передаваемых данных: 11111111 00001000 01000001

 

– Ошибка в символе: 11111111 00001000 01000011

– Принятая последовательность символов: Sc 8 C

 

– Распакованная последовательность символов: СССССССС

 

 

Рис. 8.6. Последствие ошибки в одном бите переданной сжатой строки

 

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

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

Предположим, что нужно закодировать двоичное (двухцветное) изображение размером 8 х 8 элементов, приведенное на рис. 8.2.

 

 


Рис.8.2. Двухцветное изображение 8 х 8 элементов

 

Просканируем это изображение по строкам (двум цветам на изображении будут соответствовать 0 и 1), в результате получим двоичный вектор данных

X=(0111000011110000000100000001000000010000000111100011110111101111)

длиной 64 бита (скорость исходного кода составляет 1 бит на элемент изображения).

Выделим в векторе X участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирующая последовательность длин участков - положительных целых чисел, соответствующих исходному вектору данных X, - будет иметь вид r = (1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 4, 3, 4, 1, 4, 1, 4). Теперь эту последовательность, в которой заметна определенная повторяемость (единиц и четверок гораздо больше, чем других символов), можно закодировать каким-либо статистическим кодом, например, кодом Хаффмена без памяти, имеющим таблицу кодированием (табл. 8.6.)

 

Таблица 8.6

 

Таблица кодирования длин участков

 

Кодер
Длина участка Кодовое слово

 

Для того, чтобы указать, что кодируемая последовательность начинается с нуля, добавим в начале кодового слова префиксный символ 0. В результате получим кодовое слово B (r)= (01 00011010110101101011001110100100 ) длиной в 34 бита, то есть результирующая скорость кода Rсоставит 34/64, или немногим более 0,5 бита на элемент изображения. При сжатии изображений большего размера и содержащих множество повторяющихся элементов эффективность сжатия может оказаться существенно более высокой.

Ниже приведен другой пример использования кодирования длин повторений, когда в цифровых данных встречаются участки с большим количеством нулевых значений. Всякий раз, когда в потоке данных встречается “ноль”, он кодируется двумя числами. Первое - 0, являющееся флагом начала кодирования длины потока нулей, и второе – количество нулей в очередной группе. Если среднее число нулей в группе больше двух, будет иметь место сжатие. С другой стороны, большое число отдельных нулей может привести даже к увеличению размера кодируемого файла:

 

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








Дата добавления: 2016-02-04; просмотров: 2294;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.