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

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

 

       КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

 

 

 

 

Радиотехнический факультет

 

 

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

 

 

 

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

 

 

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

 

 

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

 

Задание 3

 

 

 

 

 

Выполнил студент гр. 5311:

Пономарев С.В.

 

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

    

                                                       

                                                        Казань 2007

                                            

                                                        Содержание.

 

1.  Задание                                                                                                        3 

2.  Введение                                                                                                     4

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание № 3.

 

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

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

Определить:

1. Пригодность кода для передачи сообщений в смысле их однозначного декодирования.
2. Степень сжатия кода по сравнению с равномерным двоичным кодом (в процентах).
3. Насколько код Шеннона-Фано длиннее оптимального (в процентах).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                          

 

 

 

                                                            Введение.

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

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

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

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

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

,                             (1)                       

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

 

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

                                     ,                                             (2)

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

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

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

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

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

             

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

 

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

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

             

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

 

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

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

           

 

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

           

 

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

     

 

 

 

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

 

Решение:

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

;

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

l=3

Сообщение	Рi
x1=1	0,149
x2=2	0,224
x3=3	0,224
x4=4	0,168
x5=5	0,101
x6=6	0,05
x7=7	0,022
x8=8	0,008
x9=9	0,002
x10=10	0,0008
x11=11	0,0002
x12=12	0,00005

По данной формуле  находим все 12 вероятностей и располагаем их в порядке убывания. Затем непосредственно кодируем сообщения кодом Шеннона-Фано.

Суть кодирования состоит в том, что:

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

Процесс кодирования  представлен в таблице.

 

 

 

 

 

 

Кодирование по методу Шеннона-Фано.

Символ	pi	Разбиение					Код.
а1 а2 а3 а4 а5 а6 а7 а8 а9 а10 а11 а12	0,224 0,224 0,168 0,149 0,101 0,05 0,022 0,008 0,002 0,0008 0,0002 0,00005		1 0	1 0	1 0	1 0 1 0	11 10 011 010 0011 0010 00011 00010 000011 000010 000001 000000

 

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

2. Степень  сжатия данного кода по сравнению с равномерным определяется так: сначала вычисляется средняя длина кодовой комбинации данного кода:

.

0,224*2+0,224*2+0,149*3+0,168*3+0,101*4+0,05*4+0,022*5+0,005*5+0,002*6+0,0008*6+ +0,0002*6+0,00005*6=2,6043

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

 

При оптимальном двоичном кодировании: ;

 

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

.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение.

 

В ходе проделанной работы были рассчитаны вероятности сообщений. Эти вероятности были необходимы для кодировки этих сообщений  кодом Шеннона-Фано. Установлено, что этот код Шеннона-Фано в данном случае пригоден для передачи сообщений в смысле их однозначного декодирования. Степень сжатия кода по сравнению с равномерным двоичным кодом составляет 54%. Код Шеннона-Фано длиннее оптимального на 1.55%.

 

 

 

 

 

 

 

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

 

1. Вентцель Е.С. «Теория вероятностей». – М.: Высш.шк., 2002г.
2. Зюко А.Г. «Теория передачи сигналов». – М.: Радио и связь, 1986г.
3. Зюко А.Г., Коробов Ю.Ф. «Теория передачи сигналов». – М.: Связь, 1972г.

4. Козлов С.В., Седов С.С. «Теория электрической связи».  Пособие по курсовой работе. Казань. 2003г.