Файл: Методы кодирования данных (Понятие кодирования).pdf

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

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

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):

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

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.