Методы кодирования данных (Понятие кодирования)

Содержание:

ВВЕДЕНИЕ

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

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

Глава 1. Понятие кодирования

В начале 20 века появляются теории кодирования и информации. В 1948 г. статьи К. Шеннона положили начало для развития этих теорий, а также для дальнейших работ в этой области.

Кодирование – способ представления информации в удобном для хранения и передачи виде [1]. Развитие информационных технологий повлияло на появление вопросов, связанных с кодированием. Вопросы присутствуют в различных задачах программирования, таких как:

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

На рисунке 1 представлена основная модель, которую изучает теория информации – модель системы передачи сигналов:

ШУМ

Источник

Кодер

источника

Канал

Приемник

Кодер

канала

Декодер

канала

Декодер

источника

Рисунок 1 – Модель системы передачи сигналов

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

• алфавит источника – множество различных символов, порождаемых некоторым источником [2].
• размер алфавита источника – количество символов в множестве всех символов.

Как пример можно привести текст на русском языке. Текст порождается источником с алфавитом из 33 русских букв, знаков препинания, а так же пробелами.

Кодирование дискретного источника заключается в сопоставлении символов алфавита А источника символам некоторого другого алфавита В. Обычно символу исходного алфавита ставится в соответствие группа символов алфавита В, которая называется кодовым словом. Сразу возникают два определения:

• Кодовый алфавит – множество различных символов, используемых для записи кодовых слов [3].
• Код – совокупность всех кодовых слов, которые применяются для представления порождаемых источником символов.

Самым популярным примером является Азбука Морзе, где каждой букве языка соответствуют кодовые слова (последовательности) из «точек» и «тире».

В случае, когда размер кодового алфавита равен двойке, рассматривается двоичное кодирование. Конечная последовательность битов (0 или 1) называется кодовым словом, а количество битов в этой последовательности – длиной кодового слова.

Дано строгое определение кодирования. Пусть даны алфавит источника , кодовый алфавит . обозначено, как множество всевозможных последовательностей в алфавите А (В). Множество всех возможных сообщений в алфавите А приняло значение S. Тогда отображение , которое преобразует множество сообщений в кодовые слова в алфавите В, называется кодированием. Если , то – кодовое слово. Обратное отображение (если оно существует) называется декодированием.

Обычно задача кодирования сообщения имеет следующий вид. Требуется при заданных алфавитах А и В и множестве сообщений S найти такое кодирование F, которое обладает определенными свойствами и оптимально в некотором смысле. Свойства, которые требуются от кодирования, могут быть различными. Самый распространённые из них:

1. существование декодирования;
2. помехоустойчивость или исправление ошибок при кодировании;
3. обладает заданной трудоемкостью (время, объем памяти).

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

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

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

Метод сжатия данных делится на две группы:

• статические методы, предназначенные для кодирования конкретных источников информации с известной статистической структурой, порождающих определенное множество сообщений. Методы этой группы основывается на знании статистической структуры первоначальных данных. Наиболее распространенные примеры: арифметический код, код Фано, Хаффмана, Шеннона.
• адаптивные методы используются при неизвестной статистики источника информации, либо она изменяется с течением времени. В этой группе методов, во время кодирования очередного символа, применяется информация о ранее закодированной части сообщения, что способствует определению вероятности появления очередного символа. Во время кодирования адаптивные методы адаптируются на статистическую структуру кодируемых сообщений, точнее коды символов меняются в зависимости от накопленной статистики данных. Что позволяет адаптивным методам продуктивно и скоро кодировать сообщение за один сеанс. К этой группе относится множество различных методов сжатия данных. Самые известные – адаптивный код Хаффмана, код «стопка книг», интервальный и частотный коды

Глава 2. Кодирование целых чисел

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

Основной идеей кодирования считается – отдельное кодирование порядка значения числа x_i («экспоненту» E_i) и отдельно – значащие цифры числа x_i («мантиссу» M_i). Значимые символы мантиссы начинаются с главной ненулевой цифры, а порядок определяется позицией этой ненулевой цифры в двоичной записи числа. Аналогично десятичной записи числа, порядок равен числу цифр в записи числа без предыдущих незначащих нулей. К примеру, число 000001101 имеет порядок – 4, а мантиссу равную 1101.

Методы кодирования целы чисел обычно делят на две группы:

• Fixed + Variable (фиксированная длина экспоненты + переменная длина мантиссы)
• Variable + Variable (переменная длина экспоненты + переменная длина мантиссы)

2.1 Коды класса Fixed + Variable

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

• определить порядок числа и количество бит мантиссы;
• иметь под рукой таблицу кодовых слов.

Лучше всего рассмотреть процесс построения кода на примере:

Пусть R = 15 – количество бит исходного числа. Отведено E = 4 бита под экспоненту, так как R≤2⁴. Для сохранения одного бита можно не использовать первую единицу, так как единица всегда ей остается. Это позволяет сократить количество бит мантиссы. Оно становится на один бит меньше, чем количество бит для порядка.

Таблица 1 – Код класса Fixed + Variable

число	двоичное представление	кодовое слово	длина кодового слова
0 1	000000000000000 000000000000001	0000 0001	4 4
2 3	000000000000010 000000000000011	0010 0 0010 1	5 5
4 5 6 7	000000000000100 000000000000101 000000000000110 000000000000111	0011 00 0011 01 0011 10 0011 11	6 6 6 6
8 9 10 … 15	000000000001000 000000000001001 000000000001010 … 000000000001111	0100 000 0100 001 0100 010 … 0100 111	7 7 7 .. 7
16 17 …	000000000010000 000000000010001 …	0101 0000 0101 0001 …	8 8 ..

2.2 Коды класса Variable + Variable

В этом классе за код берется двоичная последовательность, построенная определенным образом: количество нулей равное значению порядка числа; далее единица, как признак окончания экспоненты переменной длины; далее мантисса переменной длины (аналогично кодам Fixed + Variable). В таблице 2 представлено построение кода.

Таблица 2 – Код класса Variable + Variable

число	двоичное представление	кодовое слово	длина кодового слова
0 1	00000000000 00000000001	1 0 1	1 2
2 3	00000000010 00000000011	00 1 0 00 1 1	4 4
4 5 6 7	00000000100 00000000101 00000000110 00000000111	000 1 00 000 1 01 000 1 10 000 1 11	6 6 6 6
8 9 10 …	00000001000 00000001001 00000001010 …	0000 1 000 0000 1 001 0000 1 010 …	8 8 8

Если в кодах исключить кодовое слово для нуля, то можно уменьшить длины кодовых слов на 1 бит, убрав первый ноль. Таким образом строится гамма-код Элиаса (γ-код Элиаса).

Таблица 3 – Гамма-код Элиаса

число	кодовое слово	длина кодового слова
1	1	1
2 3	01 0 01 1	3 3
4 5 6 7	00 1 00 00 1 01 00 1 10 00 1 11	5 5 5 5
8 9 10 …	000 1 000 000 1 001 000 1 010 …	7 7 7

Еще одним примером кода класса Variable + Variable является омега-код Элиаса (ω-код Элиаса). В нем кодовое слово для единицы задается отдельно. Другие кодовые слова состоят из последовательности групп длиной L₁, L₂,…, L_m, начинающихся с единицы. Конец всей последовательности задается нулевым битом. Длина первой группы составляет 2 бита, длина каждой следующей группы равна двоичному значению битов предыдущей группы плюс 1. Значение битов последней группы является итоговым значением всей последовательности групп, т.е. первые m - 1 групп служат лишь для указания длины последней группы.

Таблица 4 – Омега-код Элиаса

число	кодовое слово	длина кодового слова
1 2 3	0 10 0 11 0	1 3 3
4 5 6 7	10 100 0 10 101 0 10 110 0 10 111 0	6 6 6 6
8 9 .. 15	11 1000 0 11 1001 0 … 11 1111 0	7 7 .. 7
16 17 .. 31	10 100 10000 0 10 100 10001 0 … 10 100 11111 0	11 11 .. 11
32	10 101 100000 0	12

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

Рассматриваемые виды кодов могут быть действенны в определенных ситуациях:

1. Вероятности чисел убывают с ростом значений элементов и их распределение близко к P(x)≥P(x+1), при любом x. Точнее маленькие числа встречаются чаще больших.
2. Диапазон значений входных элементов не ограничен или неизвестен. Например, при кодировании 32-битовых чисел реально большинство чисел маленькие, но могут быть и большие.
3. При использовании в составе других схем кодирования, например, кодирование длин серий.

2.3 Кодирование длин серий

Метод кодирования информации, известный как метод кодирования длин серий, его предложил П. Элиасом, при построении использует коды целых чисел [6]. Входным потоком для кодирования является последовательность из нулей и единиц. Идея кодирования заключается в кодирование последовательности одинаковых элементов, к примеру, нулей. Последовательность одинаковых элементов называется серией, количество элементов в ней – длиной серии.

Желательно рассмотреть пример:

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

000000 1 00000 1 0000000 1 1 00000000 1

Используется, например, γ-код Элиаса. Поскольку в коде нет кодового слова для нуля, то придется кодировать длину серии +1, точнее последовательность 7 6 8 1 9:

7 6 8 1 9 ⇒ 00111 00110 0001000 1 0001001

Длина полученной кодовой последовательности равна 25 бит.

Метод длин серий эффективен для кодирования данных, имющие длинные последовательности одинаковых бит.

Глава 3. Адаптивные методы кодирования

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

кодируемый символ

... a₃ a₂ a₅ a₂ a₄ a₁ a₁ a₃ a₂ a₂ a₂ a₄ a₃ a₁ a₂ ...

... a₃ a₂ a₅ a₂ a₄ a₁ a₁ a₃ a₂ a₂ a₂ a₄ a₃ a₁ a₂ ...

кодируемый символ

... a₃ a₂ a₅ a₂ a₄ a₁ a₁ a₃ a₂ a₂ a₂ a₄ a₃ a₁ a₂ ...

кодируемый символ

Рисунок 2 – Схема перемещения окна при кодировании

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

При рассматриваемом методе кодирования оценка избыточности становится непростой математической задачей, так как избыточность состоит из двух компонентов:

• Избыточности копирования;
• Избыточности, возникающей при рассмотрении оценки вероятностей появления символов.

Благодаря этим параметрам действенность методов адаптивного кодирования обычно определяют экспериментальным путем.

Для всех методов адаптивного кодирования существует следующая теорема: Величина средней длины кодового слова при адаптивном кодировании удовлетворяет неравенству L_cp ≤ H+C,

где Н – энтропия источника информации, C – константа, которая зависит от размера алфавита источника и длины окна.

3.1 Адаптивный код Хаффмана

Метод кодирования источников с меняющейся статистикой был предложен Р. Галлагером в 1978 г., и был основан на коде Хаффмана, поэтому и получил название «Адаптивный код Хаффмана» [8].

Рассматриваемый код используется во многих методах сжатия данных в роли составной части. Кодирование происходит на основе информации из окна длины W. Алгоритм представляет собой ряд действий:

1. Перед началом кодирования очередной буквы подсчитывается частота появления в окне всех символов исходного алфавита А= {a₁, a₂, ..., a_n}. Допустимо обозначить эти частоты как q(a₁), q(a₂), ..., q(a_n). Вероятности символов исходного алфавита оцениваются на основе значений частот символов в окне

P(a₁) = q(a₁)/W, P(a₂) =q(a₂)/W, ..., P(a_n)= q(a_n)/W.

1. По полученному распределению вероятностей строится код Хаффмана для алфавита А.
2. Очередная буква кодируется при помощи построенного кода.
3. Окно передвигается на один символ вправо, вновь подсчитываются частоты встреч в окне букв алфавита, строится новый код для очередного символа, и так далее, пока не будет получен код всего сообщения.

Здесь можно привести пример адаптивного кодирования с помощью метода Хаффмана для алфавита А= {a₁, a₂, a₃, a₄} и длины окна W=6.

кодируемый символ

... a₁ a₂ a₁ a₁ a₃ a₄ a₃ a₃ a₂ ...

... a₁ a₂ a₁ a₁ a₃ a₄ a₃ a₃ a₂ ...

кодируемый символ

... a₁ a₂ a₁ a₁ a₃ a₄ a₃ a₃ a₂ ...

кодируемый символ

Рисунок 3 – Кодирование адаптивным кодом Хаффмана

При кодировании буквы a₃ получается следующие частоты встреч символов в окне: q(a₁) =3, q(a₂) =1, q(a₃) =1, q(a₄) =1. Тогда вероятности символов алфавита A оцениваются так

P(a₁)= , P(a₂)= , P(a₃)= , P(a₄)= .

На рисунке 4а) построен код Хаффмана для полученного распределения вероятностей и кодируется символ а₃ с помощью кодового символа 001.

a)

Символы	Вероятности	Построение кода	Кодовые слова
а1	1/2	1	1
а2	1/6	1/2 0	01
а3	1/6	1/3	001
а4	1/6		000

б)

Символы	Вероятности	Построение кода	Кодовые слова
а1	1/3	1	1
а2	1/6	1/3 2/3 0	011
а3	1/3		00
а4	1/6		010

в)

Символы	Вероятности	Построение кода	Кодовые слова
а1	1/3	1/2 1	11
а2	0	1/6 0	101
а3	1/2		0
а4	1/6		100

Рисунок 4 – Построение адаптивного кода Хаффмана

На следующем шаге окно сдвигается на один знак вправо и обновляется подсчет частоты встреч символов в окне q(a₁) = 2, q(a₂) = 1, q(a₃) = 2, q(a₄) = 1 и оценивается вероятность:

P(a₁)= , P(a₂)= , P(a₃)= , P(a₄)= .

Далее происходит построение кода на основе полученного результата вероятного распределения, что представлено на рисунке 4б), кодируется символ а₃ кодовым словом «00». Следует увеличение частоты встречи символа а₃, соответственно длина кодового слова уменьшилась.

После окно снова движется вправо на один символ, что приводит к изменению частоты символов в окне q(a₁)=2, q(a₂)=0, q(a₃)=3, q(a₄)=1. Происходит оценка вероятности: P(a₁)= , P(a₂)=0 , P(a₃)= , P(a₄)= .

На рисунке 4в) представлен код, построенный на основе полученных оценок вероятностей. Происходит кодирование символа а₂ кодовым словом 101. В итоге выходит кодовая последовательность 00100101.

Алгоритм на псевдокоде с помощью адаптивного кода Хаффмана:

Обозначение:

w – окно;

mas – массив вероятностей символов и кодовых слов.

DO (i=1,…n) w[i]:=a[i] OD \\заполнение окна символами алфавита

DO (not EOF) \\ до конца входного файла

DO (i=1,…,n) mas[i].p:=0 OD

DO (i=1,…,n) mas[w[i]].p:= mas[w[i]].p +1 OD \\частоты встречи

символов в окне

DO (i=1,…,n) mas[w[i]].p:= mas[w[i]].p/n OD \\вероятности символов

в окне

Сортировка(mas)

DO (i=1,…,n) \\определение количества

IF (mas[i].p=0) OD ненулевых вероятностей

OD

Huffman(i,P) \\построение кода Хаффмана

C:=Read( ) \\чтение следующий символ из файла

Write(mas[C].code) \\код символа – в выходной файл

DO (i=1,…,n-1) w[i]:= w[i+1] OD

w[n]:=C \\включение в окно текущего символа

OD

3.2 Код «Стопка книг»

Метод «Стопка книг» был предложен Рябко Б.Я. в 1980 г. Благодаря аналогии со стопкой книг, код получил свое название [9]. Чем раньше использовалась книга, тем выше она лежит, и каждый раз использованная книга кладется сверху.

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

Описание кода можно представить с помощью алфавита A={a₁, a₂, a₃, a₄}. Пусть кодируется сообщение а₃а₃а₄а₄а₃.

• Символ а₃ находится в третьей позиции стопки, кодируется кодовым словом 110 и перемещается на первую позицию, при этом символы а₁ и а₂ смещаются на одну позицию вниз.
• Следующий символ а₃ уже находится в первой позиции стопки, кодируется кодовым словом 0, и стопка не изменяется.
• Символ а₄ находится в последней позиции стопки, кодируется кодовым словом 111 и перемещается на первую позицию в стопке, при этом символы а₁, а₂, а₃ смещаются на одну позицию вниз.
• Следующий символ а₄ уже находится в первой позиции стопки, кодируется кодовым словом 0, и стопка не изменяется.
• Символ а₃ находится во второй позиции стопки, кодируется кодовым словом 10 и перемещается на первую позицию в стопке, при этом символ а₄ смещается на одну позицию вниз.

№	Кодовое слово	Начальная «стопка»	Преобразования «стопки»
1	0	а1	а3	а3	а4	А4	а3
2	10	а2	а1	а1	а3	А3	а4
3	110	а3	а2	а2	а1	А1	а1
4	111	а4	а4	а4	а2	А2	а2

Рисунок 5− Кодирование методом «стопка книг»

Таким образом, закодированное сообщение имеет следующий вид:

110 0   111 0 10 …

а₃ а₃ а₄ а₄ a₃

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

Декодирование происходит по тому же принципу «стопки книг». При этом процессе производятся те же операции, что и при кодировании. Что позволяет восстановить, в случае необходимости, исходную последовательность.

Алгоритм на псевдокоде кодированием кодом «Стопка книг»

Обозначения:

code – массив кодовых слов для позиции «стопки»;

s_in – строка для кодирования;

s_out – результат кодирования;

S – строка, содержащая исходный алфавит.

l:=<длина s_in>

DO (i=1,…l)

T:=<номер символа s_in[i] в строке S>

s_out:=s_out+code[t]

stmp:=S[t]

delete(S,t,1) \\преобразование

insert(stmp,S,1) строки S

OD

3.3 Интервальный код

В 1987 г. Элиас П. предложил интервальный код [10]. В нем используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

При кодировании символа x_i определяется интервал до его предыдущей встречи в окне длины W, обозначается это расстояние λ(x_i). Если символ x_i есть в окне, то значение λ(x_i) равно номеру позиции символа в окне. Позиции в окне нумеруются справа налево. Если символа x_i нет в окне, то λ(x_i) присваивается значение W+1, а x_i кодируется словом, состоящим из λ(x_i) и самого символа x_i.
Окно сдвигается вправо после процесса кодирования.

Пример описания кода для исходного алфавита: A={a₁,a₂,a₃,a₄}, пусть длина окна W=3. Существует некоторый префиксный код для записи числа λ(X_i):

λ (хi)	1	2	3	4
σi	0	10	110	111

Пусть кодируется последовательность а₁а₁а₂а₃а₂а₂…

1. Сначала символа а₁ нет в окне, поэтому на выход кодера передается 111 и восьмибитовый ASCII-код символа а₁ Затем окно сдвигается на одну позицию вправо.
2. При кодировании следующего символа а₁ на выход кодера передается 0, так как теперь символ а₁ находится в первой позиции окна. Далее окно снова сдвигается на одну позицию вправо.
3. Следующий символ а₂ кодируется комбинацией 111 и восьмибитовым ASCII-кодом символа а₂, так как символа а₂ нет в окне. Окно снова сдвигается на одну позицию вправо.
4. Следующий символ а₃ кодируется комбинацией 111 и восьмибитовым ASCII-кодом символа а₃, так как символа а₃ нет в окне. Окно снова сдвигается на одну позицию вправо.
5. Следующий кодируемый символ а₂ находится во второй позиции окна и поэтому кодируется комбинацией 10. Окно снова сдвигается на одну позицию вправо.
6. И последний символ а₂ находится в первой позиции окна и поэтому кодируется комбинацией 0. Таким образом, закодированное сообщение имеет следующий вид: 111 a₁ 0 111 a₂ 111 a₃ 10 0

а₁ а₁ а₂ а₃ а₂ а_{2 …}

1

111 а₁

а₁ а₁ а₂ а₃ а₂ а_{2 …}

2

0

а₁ а₁ а₂ а₃ а₂ а_{2 …}

3

111 а₂

а₁ а₁ а₂ а₃ а₂ а_{2 …}

41

111 а₃

а₁ а₁ а₂ а₃ а₂ а_{2 …}

5

10

а₁ а₁ а₂ а₃ а₂ а_{2 …}

6

0

Рисунок 12 Кодирование интервальным кодом

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

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

Алгоритм на псевдокоде методом кодирования интервальным кодом

Обозначения:

code – массив кодовых слов для записи числа λ(X_i);

s_in – строка для кодирования;

s_out – результат кодирования.

l:=<длина s_in>

DO (i=1,…l)

t:=0

found:=нет

DO (j=i-1,…,i-W)

t:=t+1

IF (j>0) и (s_in[i]=s_in[j])

s_out:=s_out+code[t]

found:=да

OD

FI

OD

IF (not found) s_out:=s_out+code[n]+s_in[i] FI

OD

3.4 Частотный код

Частный код использует алфавитный код Гилберта-Мура, был предложен в 1990 г. Рябко Б.Я [11]. Для частотного кода избыточность - величина постоянная, а сам код реализует адаптивный метод сжатия. Длинна окна является параметром, определяющим среднюю длину кодового слова, а также позволяет оценивать статистику кодируемых данных. Также этот код характеризуется высокой скоростью операций кодирования и декодирования.

Пример построения алгоритма частотного кода для источника с алфавитом А={a₁, a₂, ..., a_n}: Пусть используется окно длины W, точнее при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

К примеру, размер окна определяется W=(2^r − 1)n, где n=2^k − размер исходного алфавита, r, k − целые числа [12].

Порядок построения кодовой последовательности следующий:

1. На первом шаге оценивается число встреч в окне x_i-W.…x_i-1 всех букв исходного алфавита. Обозначим эти величины через P(a_j), j=1…, n
2. P(a_j) увеличивается на единицу и обозначается как Р’(а_j) = P(а_j) + 1
3. Вычисление суммы Q_i, i=1…, n

Q₁= Р’(а₁),

Q₂= Р’(а₁) + ,

Q₃= Р’(а₁) + Р’(а₂)+ ,

…

Q_n= Р’(а₁) + … + Р’(а_n-1) + .

1. Для кодового слова символа а_j берется k знаков от двоичного разложения Q_j, где k=1 + log (n+W) – [log Р’(а_j) ].
2. Далее окно сдвигается на один символ вправо и для кодирования следующего символа алгоритм вновь повторяется.

Пусть А={a₁, a₂, a₃, a₄}, длина окна W=4. Необходимо закодировать последовательность символов

Строится кодовое слово для символа а₃.

1. Оценка частоты встреч в текущем "окне" всех символов алфавита:

Р’(а₁) = Р’(а₂) =1, Р’(а₃) =4, Р’(а₄)=2.

2. Вычисление суммы Q_j:

Q₁ = 1

Q₂ = 1 + 0.5 = 1.5

Q₃ = 1 + 1 + 2 = 4

Q₄ = 1 + 1 + 4 + 1 = 7

3. Определение длины кодового слова для а₃:

k = 1 + log (4+4) − [log 4] = 1 + 3 − 2 = 2

4. Двоичное разложение Q₃ =100₂ , осуществляется первыми 2 знаками. Таким образом, для текущего символа а₃ кодовое слово 10.

Алгоритм на псевдокоде. Частотный код

Обозначения:

w – окно;

W – размер окна;

P – массив частот символов;

Q – массив для величин Q_i..

DO (i=1,…n) w[i]:=a[i] OD \\заполнение окна символами алфавита

DO (not EOF) \\ до конца входного файла

DO (i=1,…,n) P [i]:=1 OD

DO (i=1,…,n) P [w[i]]:= P [w[i]] +1 OD \\частоты встречи

символов в окне

pr:=0

DO (i=1,…,n)

Q [i] := pr+ P [i] /2 \\вычисление суммы

pr:=pr+ P [i]

OD

C:=Read( ) \\чтение следующего символа из файла

DO (j=1,…,n)

IF (C= a[i]) m:=j FI \\определение номера символа в алфавите

OD

k = 1 + log₂ (n+W) − ⎣log₂ P[m] ⎦ \\длина кодового слова

DO (j=1,…,k) \\формирование кодового слова

Q [m]:=Q [m] _*2 в двоичном виде

code:= ⎣Q [m]⎦

IF (Q [m] >1) Q [m]:= Q [m] - 1 FI

OD

Write(code) \\код символа – в выходной файл

DO (i=0,…,n-1) w[i]:= w[i+1] OD

w[n]:=C \\включение в окно текущего символа

OD

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 2011 г. — 1296 стр. 
2. Джеймс Андерсон. «Дискретная математика и комбинаторика» — «Вильямс», 2004 г. 
3. Новиков. Ф.А. «Дискретная математика для программистов» — «Питер», 2001 г. — 304 стр.
4. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. 
5. Сальникова Н.А. Информатика. Основы информатики. Представление и кодирование информации. Часть 1 [Электронный ресурс]: учебное пособие/ Сальникова Н.А.— Электрон. текстовые данные.— Волгоград: Волгоградский институт бизнеса, Вузовское образование, 2009.— 94 c.— Режим доступа: http://www.iprbookshop.ru/11321.html.— ЭБС «IPRbooks»
6. Соколов В.П. Кодирование в системах защиты информации [Электронный ресурс]: учебное пособие/ Соколов В.П., Тарасова Н.П.— Электрон. текстовые данные.— М.: Московский технический университет связи и информатики, 2016.— 94 c.— Режим доступа: http://www.iprbookshop.ru/61485.html.— ЭБС «IPRbooks»
7. Голиков А.М. Кодирование и шифрование информации в системах связи. Часть 1. Кодирование [Электронный ресурс]: учебное пособие для специалитета: 210601.65 Радиоэлектронные системы и комплексы. Курс лекций, компьютерный практикум, задание на самостоятельную работу/ Голиков А.М.— Электрон. текстовые данные.— Томск: Томский государственный университет систем управления и радиоэлектроники, 2016.— 327 c.— Режим доступа: http://www.iprbookshop.ru/72112.html.— ЭБС «IPRbooks»
8.  Марков А. А. Введение в теорию кодирования. — М.: Наука, 1982. — 192 с.
9. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз
10. С.Коутинхо. Введение в теорию чисел. Алгоритм RSA. Москва: Постмаркет, 2001. — 328 с.
11. Костров Б. В. Основы цифровой передачи и кодирования информации. - ТехБук, 2007 г., 192 стр.
12. Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. - 1999. - Т.35, Вып. - С.95 - 108.