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

 

 

 

 

 

 

 

 

 

 

 

 

 

КУРСОВОЙ  ПРОЕКТ

по  дисциплине:

«Теория  информации и кодирования»

 

 

 

 

 

Исполнитель:

 

 

Руководитель:

 

 

 

 

 

 

Оценка:__________________

Подпись:_________________

«___»__________2011 год

 

 

 

 

 

 

 

 

 

 

Введение

 

В данном курсовом проекте были программно реализованы  теоретические знания, полученные в течение всего семестра. Были рассмотрены методы нахождения энтропии  зависимых и независимых систем, основные способы кодирования информации. В частности были реализованы методы кодирования Шеннона-Фано и кодирование по Хаффману. Реализованы были также основные методы помехоустойчивого кодирования, коды с обнаружением одиночной ошибки, коды с обнаружение и возможностью исправления одиночной ошибки. Рассмотрены способы шифрования  входных сообщений, такие как метод шифрования со смещением, и RSA.

Перед  программной реализацией всех вышеуказанных  методов были проведены расчеты  по всем темам в программе Microsoft Excel 2003 , и была сделана проверка на  правильность расчетов. После этого приступили к программной реализации теоретических знаний.

Для программной  реализации был использован язык программирования С/С++ и система программирования Visual Studio 2010.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

 

Введение…………………………………………………………………………2

 

Глава 1. Информационные характеристики дискретных

               случайных величин…………………………………………………....4

1.1 Задание………….……………………………………………………………4

1.2 Теория………….…………………………………………………………….4

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

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

1.3.2 Алгоритмы и функции……………………………………………………...5

1.3.3 Тестирование………………………………………………………………..7

 

Глава 2. Оптимальное кодирование……………………………………………..8

2.1 Задание………………………………………………………………………...8

2.2 Теория…………………………………………………………………………8

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

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

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

2.3.3 Тестирование………………………………………………………………16

 

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

3.1 Задание……………………………………………………………………….19

3.2 Теория………………………………………………………………………...19

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

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

3.3.2 Алгоритмы и функции…………………………………………………….23

3.3.3 Тестирование………………………………………………………………27

 

Глава 4. Шифрование данных…….…………………………………………….27

4.1 Задание……………………………………………………………………….27

4.2 Теория………………………………………………………………………...27

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

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

4.3.2 Алгоритмы и функции…………………………………………………….30

4.3.3 Тестирование………………………………………………………………34

 

5. Заключение……………………………………………………………………35

 

Приложение 1……………………………………………………………………36

Приложение 2……………………………………………………………………37

Приложение 3……………………………………………………………………41

Приложение 4……………………………………………………………………43

 

Глава 1. Информационные характеристики дискретных

случайных величин.

 

1.1 Задание.

 

Для заданных систем X и Y с состояниями, определяемыми     

символами алфавита , и определить:

1.Энтропии независимых систем X и Y;

2.условные энтропии систем X и Y, считая , что каждому символу одной системы соответствует соответствующий по индексу символ второй системы;

3. энтропию объединения независимых систем X и Y ;

4. энтропию объединения зависимых систем X и Y ;

5. взаимную информацию систем X и Y ;

6. объем информации для систем X и Y , считая , что каждый символ алфавита  А кодируется двумя символами вторичного алфавита.

 

1.2 Теория.

 

Информацио́нная энтропи́я — мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

К.Шеннон ввел следующую формулу  для определения энтропии:

 

Свойства энтропии:

1. энтропия есть величина вещественная, ограниченная и неотрицательная;
2. энтропия минимальна и равна нулю, если хотя бы одно из состояний системы достоверно известно;
3. энтропия максимальна и равна логарифму числа состояний, если состояния системы равновероятны;
4. энтропия бинарных величин изменяется от 0 до 1 - она равна 0, если вероятность одного из состояний равна 0, затем возрастает и достигает максимума при вероятностях 0.5.

 

 

Пусть имеется сложная система, состоящая из двух систем X и Y :

          

 

  

• Энтропия сложной системы вычисляется по формуле:

 

                    

 

• Формулы для нахождения условную энтропию систем:

      

 

 

• В случае независимых систем X и Y энтропия сложной системы рассчитывается следующим образом:

 

 

• В случае зависимых систем X и Y энтропию сложной системы можно вычислить с помощью соотношений:

 

 

• Величина  называется полной взаимной информацией, содержащийся в системах X и Y ;

                                  

 где, – полная информация  о системе Y , содержащийся в системе X,

       – полная информация  о системе X , содержащийся в системе Y;

 

• Количество информации вычисляется по формуле:

       

где, – число символов, вторичного алфавита, используемых для   

   представления одного символа  первичного алфавита сообщения;

а – количество передаваемых букв первичного алфавита в сообщении.

 

 

 

 

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

 

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

 

Для запуска  программы необходимо кликнуть на файл названием tik_lab1.exe, после этого откроется консольное окно с решением задач. Для изменения входных данных системы, необходимо ввести системы X и Y непосредственно в код. Для этого нужно открыть файл tik_lab1.cpp и ввести необходимые данные в 8 и 9 строчки для X и Y соответственно. Сохранить файл.

 

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

 

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

 

 

• Описание алгоритма нахождения энтропии систем Х и У 

 

Задаем символьный массив для системы X

Задаем символьный массив для системы Y

Объявляем переменные для перебора

Объявляем переменные для  перебора символов

Объявляем переменные для  подсчета 

Объявляем переменные для  подсчета энтропий и задаем им значение 0

Объявляем массивы для  подсчета вероятностей

Объявляем переменные для  подсчета количества букв в системах

Выводим на консоль строчки:Veroyatnosti и  X     Y    

//цикл для перебора букв

for (ch=0;ch<=3;ch++) {

выводим на консоль текущий символ

c=0;

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

если находим такой  же символ, то увеличиваем с

пишем результат подсчета в массив для текущей буквы

         вычисляем вероятность по формуле

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

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

Аналогично для системы  Y

}

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

 

 

• Описание алгоритма нахождения условной энтропии систем Х и У и нахождения энтропии зависимых систем:

 

Вывод на консоль Uslovnoe kolvo и X|Y  a     b     c     d

for (ch1=0;ch1<=3;ch1++) {//перебираем  первую букву(строчку)

выводим на консоль текущий  символ

//перебираем вторую букву(столбец)

for (ch2=0;ch2<=3;ch2++) { 

задаем количество с=0

for (i=0;i<=strlen(a);i++) {//двигаемся  по сообщению

если в системе Х- первая буква, а в У-вторая, то с++

}

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

}

puts("");

}

//ниже правильным образом  считаются вероятности Х/У и  У/Х

Выводим на консоль: Uslovnie veroyatnosti и X/Y   a     b     c     d    

//Как в предыдущем цикле  перебираем первую букву (строчку)

for (ch1=0;ch1<=3;ch1++) {

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

//перебираем вторую букву(столбец) 

for (ch2=0;ch2<=3;ch2++) {

движемся по строчкам и делим на С(у)

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

}

puts("");

}

аналогично для YX 

}

//По матрицам P(X/Y) и P(Y/X) считаем H(X/Y) и H(Y/X)

for (j=0;j<4;j++) {

слагаемое энтропии:temp=0.0;

for (i=0;i<4;i++)

      если вероятность XY больше 0 подсчитываем слагаемое энтропии: 

temp+=-verXY[i][j]*log(verXY[i][j])/log(2.0);

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

}

Вывод на консоль значения энтропии X/Y

        for (j=0;j<4;j++) {

слагаемое энтропии:temp=0.0;

for (i=0;i<4;i++)

       если  вероятность YX больше 0 подсчитываем слагаемое энтропии:

temp+=-verYX[i][j]*log(verYX[i][j])/log(2.0);;

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

}

Вывод на консоль значения энтропии Y/X 

Вывод на консоль значения энтропии независимых (X,Y)

Вывод на консоль значения энтропии зависимых (X,Y)

Вывод на консоль значения взаимной информации Y->X

Вывод на консоль значения взаимной информации X->Y

Вывод на консоль значения объема

}

 

 

 

 

 

 

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

 

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

Система Х: abcaaaaabbacbaacccabaccbbaccbbddadd

Система Y: bcaddcdbabbbacbbddcbbaccbbdbdadacc

Результат работы программы представлен  на рисунке №1.

 

 

Рис.1

 

 

Глава 2. Оптимальное кодирование.

 

2.1 Задание.

 

1. Определить вероятности появления  символов заданного источника  с алфавитом A={a,b,c,d} ( использовать частоты символов).

2.Определить энтропию сообщения

3. Построить коды Шеннона-Фано  и Хаффмана для отдельных символов  сообщения и для двух- и трехбуквенных  сочетаний символов.

4. Определить среднюю длину и  избыточность для всех кодов.

 

2.2 Теория.

 

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

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

 

Принцип построения оптимальных кодов:

1.  Каждый элементарный символ должен переносить максимальное количество информации.

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

 

Способ кодирования по Шеннону-Фано.

 

Для построения этого кода необходимо в порядке  убывания вероятностей их появления. Затем  разбивают полученную таблицу на 2 группы так, чтобы суммы вероятностей групп были примерно одинаковыми. Для  символов первой группы присваивают 0, для второй-1. Полученные группы символов делят аналогичным образом и  опять кодируют. Это продолжается до тех пор пока в последних  подгруппах не останется по одному символу сообщений.

 

Пример кодирования Шеннона-Фано представлен в таблице 1

 

 

 

 

Таблица 1

X	P	Шаг				Коды
		1	2	3	4
-x1	1/4	0	0	-	-	00
-x2	1/4		1	-	-	01
-x3	1/8	1	0	0	-	100
-x4	1/8			1	-	101
-x5	1/16		1	0	0	1100
-x6	1/16				1	1101
-x7	1/16			1	0	1110
-x8	1/16				1	1111

 

 

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

 

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