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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

 

 

 

 

 

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

 

 

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

 

 

 

 

 

 

Оценка:__________________

Подпись:_________________

«___»__________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