Эффективное кодирование. Код Шеннона - Фано

Министерство образования и науки Российской Федерации

КАЗАНСКИЙ НАУЧНО - ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. А.Н.ТУПОЛЕВА

Институт радиоэлектроники и телекоммуникаций

Кафедра радиоэлектронных и телекоммуникационных систем

“Эффективное кодирование. Код Шеннона - Фано”

                                                  Курсовая работа

По курсу “Теория электрической связи”

Задание 3

Выполнила студентка группы 5305

Безденежных Н.Е.

                                                                                Проверил:         Седов С.С.

Казань 2011

Содержание

1.  Задание                                                                                                        3             

2.  Введение                                                                                                     4

3.  Теоретическая  часть                                                                                 5

4.  Практическая часть                                                                                  10

5.  Заключение                                                                                               10

6.  Список использованной литературы                                                       10

Задание  3

Источник сообщений выдает целые значения xi (i=1,2,...9) случайной величины Х, распределение которой подчиняется закону Пуассона с параметром =3.

Закодировать сообщения кодом Шеннона-Фано.

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

Определить:

1) Пригодность кода для передачи сообщений в смысле их однозначного декодирования.

2) Степень сжатия кода по сравнению с равномерным двоичным кодом (в процентах).

3) Насколько код Шеннона-Фано длиннее оптимального (в процентах).

Введение

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

Принцип решения изложен в теоретической части, а результаты расчетов представлены в виде графиков и таблиц практической части.

Теоретическая часть.

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

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

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

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

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

     Средняя информация, содержащаяся в одном сообщении, т.е. энтропия, вычисляется по формуле [1,стр507]:

,                             (1)                       

где pi - вероятность того, что будет передаваться определённое сообщение.

     Среднее число элементарных символов на сообщение [1,стр507]:

                                    ,                                             (2)

где  pi - вероятность того, что будет передаваться это сообщение,

ni – количество элементарных символов в данном сообщении.

   Если  nmin > nср , то это означает, что данный код непригоден для передачи информации, потому что его нельзя однозначно понимать при декодировании. Недостаток такого кода в том, что некоторые кодовые комбинации являются началом (префиксом) для других.

    В алгоритме Шеннона-Фано необходимо знать вероятности передаваемых сообщений. Сообщения записываются в столбец в порядке убывания вероятности  передаваемых сообщений . Расставленные сообщения разбивают на две группы так, чтобы суммарные вероятности сообщений в каждой группе были равны. Верхней присваивают кодовый символ 1, а нижней 0, деление продолжается пока в каждой группе не останется по одному сообщению.

    Вероятности случайных величин, распределенных по закону Пуассона вычисляются по формуле:

где - параметр распределения.

Степень сжатия кода по сравнению с равномерным определяется так:

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

где - длинна -ого сообщения, - вероятность появления -ого сообщения.

Минимальная длинна кодовой комбинации равномерного кода , которым можно закодировать сообщений, определяется как наибольшее целое к .

Таким образом, степень сжатия кода можно определить по формуле:

Минимальная средняя длина кодовой комбинации оптимального эффективного кода численно равна энтропии источника сообщений:

Таким образом, полученный код длиннее оптимального (в процентах):

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

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

При  принципе обнаружения определяется код, в котором  присутствует  ошибка, но разряд не указывается. При принципе исправления определяется код и разряд, в котором  присутствует  ошибка.

Основой любого помехоустойчивого кода является обычный двоичный код. К каждой кодовой комбинации двоичного кода добавляются избыточные символы. Зачет них решается задача помехоустойчивого кодирования.

где - длина помехоустойчивого кода

     -простой код (количество информационных символов)

-добавочные символы

Формула для нахождения вероятность той или иной ошибки:

Для нахождения вероятности любой ошибки:

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

Линейные двоичные блоковые коды удобны тем, что, представляя информационные и кодовые слова в форме двоичных векторов, мы можем описать процессы кодирования и декодирования с помощью аппарата линейной алгебры. При этом компонентами вводимых векторов и матриц являются символы 0 и 1 [4,стр133]:

Операции над двоичными компонентами производятся по правилам арифметики - „исключающие или” (по модулю 2) Табл.№1.                                                                                                                

                                                                                               Таблица№1.

Кодер двоичного блокового - кода отображает множество

возможных двоичных информационных слов во множество - мерных кодовых слов. В теории кодирования между этими множествами всегда существует взаимно однозначное соответствие. Рис.1.

Рис.1. Кодер двоичного блокового - кода.

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

Чем ниже скорость, тем больше избыточность кода, и тем большими возможностями для защиты от ошибок он обладает.

Структура кодовых векторных пространств:

Исходным материалом для построения кодовых конструкций служит -мерное двоичное векторное пространство, в котором заданы операция -„исключающие или”(арифметика по модулю 2 - mod2). В него вложено -мерное линейное пространство, содержащее кодовых слов. Код образуется с помощью комбинаций линейно независимых базисных векторов .

Эти векторы образуют строки порождающей матрицы кода .

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

Рис.2. -мерное двоичное векторное пространство.

Дуальное векторное подпространство «натянуто» на линейно независимые базисные векторы . Эти векторы образуют строки проверочной матрицы.

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

Кодовое слово - и информационное слово - связаны соотношением:

где — порождающая матрица.

Практическая часть.

Решение:

Для создания кода Шеннона-Фано найдем сначала вероятности, с которыми появляются 12 сообщений xi от x1 =1 до x9 =9. Закон Пуассона определяется выражением:

;

где а= - параметр закона.

=3