Курсовая работа по «Теории информации и кодирования»

 

 

Кодирование по Хаффману.

 

Еще одним  способом построения оптимальных кодов  является метод Хаффмана.  Буквы  располагаются в порядке убывания их вероятностей. Складывают вероятности двух последних букв и из них образуют новую (составную) букву с вероятностью, равной полученной сумме. Затем ряд переписывают с учетом того, что вместо двух букв появилась  одна новая со своей вероятностью. Далее операцию повторяю до тех пор, пока не останется одна буква с вероятностью равной 1.

После этого  выполняют приписывание компонентам  составных букв символов 0 и 1: первой букве всегда приписывают 0, а второй -1.

Ниже показан  пример кодирования по Хаффману:

 

a	0,3142	c-d	0,4	a-b	0,6	ab-cd	1
b	0,2857	а	0,3146	c-d	0,4
c	0,2	b	0,2857
d	0,2
			ab-cd	ab	0	cd	1	a	00
				cd	1	a	00	b	01
						b	01	c	10
								d	11

Формула для нахождения средней  длины кода :

 

Формула для нахождения избыточности:

(1-H/n)*100%

 

 

 

 

2.3 Программная реализация и алгоритмы.

 

2.3.1 Запуск программы, входные и выходные данные.

 

Для запуска  программы необходимо кликнуть на файл названием tik_lab2.exe, после этого откроется консольное окно с кодами,  закодированными и декодированными сообщениями.

Для изменения  исходных данных нужно открыть файл lab2.cpp и изменить данные для массива str в основной функцие main.

 

 

2.3.2 Алгоритмы и функции.

 

Программа состоит и нескольких функций, которые  вызываются в главной функции  main(). Далее представлены эти функции:

 

• Show – функция вывода на экран.
• Encode- функция кодирования сообщения.
• Decode- функция декодирования сообщения
• Haffman- функция построения кодов методом Хаффмана.
• Fano_rec- функция построения кодов методом Шеннона-Фано (рекурсия).
• Fano-функция построения кодов методом Шеннона-Фано (в ней также вызывается функция Fano_rec).

 

 

• Описание алгоритма кодирования Шеннона-Фано.

 

Алгоритм  Шеннона-Фано, основан на теоретических  знаниях. В функцию передается вся  таблица, а также 2 важных параметра: размер блока и индекс начала этого  блока. Принцип действия основан  на рекурсии- то есть вызов функцией самой себя. В начале функции стоят  проверки на размеры блоков:1,2,3-это  особые случаи, в других случаях  функция выполняет действия по разделу  входного блока на 2 блока и присвоением  первому блоку кода «0», а второму  «1». На вход могут подаваться таблицы одно- двух- и трехбуквенных сочетаний символов, при этом нужно указывать размер первичного блока: 4, 16, 64 соответственно. При первом вызове рекурсивной функции начало блока ставится 0.

 

Построение кодов Шеннона-Фано: рекурсивная функция

Аргументы:указатель на сочетания,начало и конец кодируемого участка, сумма вер-тей, номер шага(глубина)

void fano_rec(soch *sochet[],int first,int last,double sump,int k){

Задаем сумму первой группы =0

разница между группами=2.0

номер рассматриваемой комбинации

количество комбинаций в  первой группе=-1

 

//в первую группу заносим  новые комбинации, пока разница  сумм вероятностей у групп  не будет минимальна

//Т.е. если при добавлении  новой комбинации разница групп  уменьшится, то добавляем

while (((razn > fabs(sump-2*(sum+sochet[i]->ver)) ) && (i<last))) {

увеличиваем суммму вер-стей первой группы

пишем ноль в код комбинации (она уже в первой группе)

увеличиваем количество комбинаций в первой группе на 1

вычисляем разницу между  группами

i++;

}

while (i<=last) {sochet[i]->code[k]='1';i++;}//во  второй группе прописываем нули

//запускаем рекурсию в  каждой из групп или заканчиваем  коды

    if (ss>0) fano_rec(sochet,first,first+ss,sum,k+1);

else sochet[first]->code[k+1]='\0';

    if (last-first-ss>1) fano_rec(sochet,first+ss+1,last,sump-sum,k+1);

else sochet[last]->code[k+1]='\0';

}

 

//Построение кодов Шеннона-Фано

void fano(soch *sochet[],int n){

//Сортируем вероятности

soch *t;

for(int i=0; i<n; i++)

for(int j=n-1; j>i; j--)

if ((sochet[j-1]->ver < sochet[j]->ver)){

t=sochet[j];sochet[j]=sochet[j-1];sochet[j-1]=t;

}

//Запускаем рекурсивную функцию

fano_rec(sochet,0,n-1,1.0,0);

}

 

 

 

 

• Описание алгоритма кодирования Хаффмана.

 

//Построение кодов хаффмана

void haffman(soch *sochet[],int n){

//Сортируем вероятности  (методом пузырька)

soch *t;

for(int i=0; i<n; i++)

for(int j=n-1; j>i; j--)

if ((sochet[j-1]->ver < sochet[j]->ver)){

t=sochet[j];sochet[j]=sochet[j-1];sochet[j-1]=t;

}

//создаем дерево (с помощью  параллельных массивов)

Задаем родителя вершины

Задаем бит вершины (символ)

Задаем вероятность

int res_ver[2*MAXL]={0};

int res_i[2*MAXL]={0};

//задаем листья (все исходные  комбинации)

for (int i=0; i<n; i++) {

бит вершиы=-1;

родитель вршины=-1;

вероятность=sochet[i]->ver;

}

//начинаем кодировку

Задаем колличество

while (1) {

задаем переменные minn1 и minn2

находим 2 минимальные вершины  без кодов

//первая вершина

Задаем min=2.0

for (int i=0; i<count; i++) {

if (бит вершины==-1 && вероятность<=min) {min=вероятнсти;minn1=i;}

}

//вторая вершина

Задаем min=2.0;

for (int i=0; i<count; i++) {

if (бит вершины==-1 && вероятность<=min && minn1!=i) {min=вероятности;minn2=i;}

}

Присваеваем биту вершины[minn1]=1;

Присваеваем биту вершины[minn2]=0;

 

если постороенно полное дерево, то выходим

иначе добавляем родителя

бит родителя пока неизвестен

родителей пока нет

приписываем первому сыну номер родителя

приписываем второму сыну номер родителя

вероятность родителя = сумме вероятностей сыновей

 

count++; 

}

//от каждого листа идём  к корню дерева и запоминаем  код

for (int i=0; i<n; i++) {

задаем переменные p=i,k=0;

while (p!=-1) {//пока не придём  к корню

sochet[i]->code[k]='0'+der_bit[p];//приписываем  символ 1 или 0

p=der_rod[p];

k++;

}

приписываем символ конца  строки

"разворачиваем" код

for (int j=0;j<k/2;j++) {

char temp=sochet[i]->code[j];

sochet[i]->code[j]=sochet[i]->code[k-1-j];

sochet[i]->code[k-1-j]=temp;

}

}

}

 

• Алгоритм кодирования сообщения

//soch- сочетания, n- колво, in- входная  строка, out- полученный код, k- количество  символов в комбинации

//Примечание: Из строки  берётся количество символов  кратное k, остальные отбрасываются

void encode(soch *sochet[],int n,char in[MAXL],char out[MAXL*5],int k) {

задаем массив типа char

задаем переменные i=0 и j

out[0]='\0';

while (i<strlen(in)/k*k) {//отбрасываем  неполные комбинации

 

берём нужную нам комбинацию из строки

 

for (j=0;(strcmp(tofind,sochet[j]->x));j++);//находим  соответсвующий код

 

strcpy(out+strlen(out),sochet[j]->code);//приписываем код

i+=k;

}

}

 

 

• Алгоритм декодирования сообщения

 

void decode(soch *sochet[],int n,char in[MAXL*5],char out[MAXL]) {

char tofind[MAXL];

soch *sortsochet[MAXL]; //копия входных сочетаний, будет отсортирована

int i=0,j,ncode=0,scode=0;

char ch;

out[0]='\0';

//Sort

for(i=0; i<n; i++) sortsochet[i]=sochet[i];

soch *t;

for(i=0; i<n; i++) {

for(int j=n-1; j>i; j--)

if (strcmp(sortsochet[j-1]->code,sortsochet[j]->code)>0){

t=sortsochet[j];sortsochet[j]=sortsochet[j-1];sortsochet[j-1]=t;

}

}

//

i=0;

while (i<strlen(in)) {//пока не  прочитаем всё сообщение

ch=in[i];//берём символ текущий  (1 или 0)

//находим подходящую комбинацию

while (sortsochet[ncode]->code[scode]!=ch)

ncode++;

scode++;//сдвигаемся к следующему  символу

//Если код полный, значит  мы нашли комбинацию символов

if (sortsochet[ncode]->code[scode]=='\0') {

strcpy(out+strlen(out),sortsochet[ncode]->x);//сохраняем её

scode=0;

ncode=0;

}

i++;

}

}

 

• Алгоритм вывода кодов.

 

void show(soch *sochet[],int n)

{

Задаем среднее=0

Задаем энтропию=0

for (int i=0; i<n; i++) {

копим среднюю длину

вычисляем энтропию

 

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

}

выводим энтропию

выводим среднюю длину

Выводим избыточность

}

 

 

 

 

• Описание главного модуля Main().

 

 

int main(){

задае сообщение в массив в соответствии с вариантом

задаем переменные i,j,n1=0,n2=0,n3=0;

задаем переменные символьного  типа ch,ch1,ch2,ch3;

задаем перееменную c;

задаем энтропию ent=0;

задаем массив вероятностей p[4];

soch *sochet3[64],*sochet2[16], *sochet1[4];

 

выводим на консоль Veroyatnosti и p

for (ch='a';ch<='d';ch++) {

выводим на консоль символ

c=0;

for (i=0;i<=strlen(str);i++)

if (str[i]==ch) c++;

         считаем вероятность

выводим значение

считаем энтропию

}

Выводим значение энтропии на консоль

 

//формирование сочетаний

for (ch1='a';ch1<='d';ch1++) {

sochet1[n1]= new soch;

вероятность=p[ch1-'a'];

записываем символ

следующий столбец – конец  строки

n1++;

for (ch2='a';ch2<='d';ch2++) {

sochet2[n2]= new soch;

вероятность=p[ch1-'a']*p[ch2-'a'];

записываем первый символ в первый столбец

записываем второй символ во второй столбец

3й столбец – конец  строки

n2++;

for (ch3='a';ch3<='d';ch3++) {

sochet3[n3]= new soch;

вероятность=p[ch1-'a']*p[ch2-'a']*p[ch3-'a'];

записываем в первый столбец  первый символ

записываем во второй столбец  второй символ

записываем в третий столбец  третий символ

записываем в последний  столбец конец строки

n3++;

}

}

}

Задаем массив кода

Задаем массив докодированного  сообщения

вызываем фунцию fano(sochet1,n1);

вызываем функцию fano(sochet2,n2);

вызываем функцию fano(sochet3,n3);

выводим на консоль Fano 1sim:

вызываем функцию show(sochet1,n1);

вызываем функцию encode(sochet1,n1,str,kod,1);

выводим на консоль kod:

вызываем функцию decode(sochet1,n1,kod,source);

выводим на консоль str:

Выводим на консоль Fano 2sim

вызываем функцию show(sochet2,n2);

вызываем функцию encode(sochet2,n2,str,kod,2);

выводим на консоль kod:

вызываем функцию decode(sochet2,n2,kod,source);

выводим на консоль str:

выводим на консоль Fano 3sim:

вызываем функцию show(sochet3,n3);

вызываем функцию encode(sochet3,n3,str,kod,3);

выводим на консоль kod:

вызываем функцию decode(sochet3,n3,kod,source);

выводим на консоль str:

 

вызываем функцию haffman(sochet1,n1);

вызываем функцию haffman(sochet2,n2);

вызываем функцию haffman(sochet3,n3);

выводим на консоль Haffman 1sim:

вызываем функцию show(sochet1,n1);

вызываем функцию encode(sochet1,n1,str,kod,1);

выводим на консль kod:

вызываем функцию decode(sochet1,n1,kod,source);

выводим на консоль str:

выводим на консоль Haffman 2sim:

вызываем функцию show(sochet2,n2);

вызываем функцию encode(sochet2,n2,str,kod,2);

выводим на консоль kod:

вызываем функцию decode(sochet2,n2,kod,source);

выводим на консоль str:

выводим на консоль Haffman 3sim:

вызываем функцию show(sochet3,n3);

вызываем функцию encode(sochet3,n3,str,kod,3);

выводим на консоль kod:

вызываем функцию decode(sochet3,n3,kod,source);

выводим на консоль str:

 

getch();

for (i=0;i<n1;i++) delete sochet1[i];

for (i=0;i<n2;i++) delete sochet2[i];

for (i=0;i<n3;i++) delete sochet3[i];

}

 

 

2.3.3 Тестирование.

 

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

Система Х: abcaaaaabbacbaacccabaccbbaccbbddadda

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 3.  Помехоустойчивое кодирование.

 

3.1 Задание.

 

1.Определить  исходные кодовые комбинации, соответствующие  заданному неприводимому полиному.

2. Построить  циклические коды, соответствующие  исходным кодовым комбинациям.

3. Выполнить  декодирование циклических кодов.

4. Внести  ошибку в одну из кодовых  комбинаций циклического кода.

5. Выполнить  декодирование циклического кода  с ошибкой.

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

 

3.2 Теория.

 

  Основные сведения о  методах  помехоустойчивого кодирования.

Помехоустойчивые коды применяют для уменьшения влияния  помех на сообщения. Построение помехоустойчивых кодов основано на добавлении к исходной комбинации из k символов r контрольных символов. Закодированная комбинация будет составлять n символов. Поэтому помехоустойчивые коды часто называют (n, k)-коды.