Теория кодирования

     Вспомним, что длина слова и его вероятность  связаны соотношением 

     l_i = [− log p_i ]≥ − log p_i . 

     Поэтому p_i ≥2^-li .

     С учетом этого неравенства 

     q _j − q _i ≥ 2^-li 

     В двоичной записи числа в правой части  мы имеем после запятой l_i −1 нулей и единицу в позиции с номером li. Это означает, что по меньшей мере в одном из l_i разрядов слова c_i и c_j отличаются и, следовательно, c_i не является префиксом для c_j. Поскольку это верно для любой пары слов, то код является префиксным.

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

     l ≤ H +1. 

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

     

     2.3 Пример Кода Шеннона 

     Допустим, нужно закодировать некоторое сообщение: AABCDAABC

     Имеем :

     A - 5 5/10 = 0.5

     B - 2 2/10 = 0.2

     C - 2 2/10 = 0.2

     D - 1 1/10 = 0.1

     Длина всего сообщения 10 (Вычисляется веpоятность встpечаемости каждого символа  и pасполагаем их в столбик в поpядке yбывания веpоятностей)

     После этого стpоим кодовые комбинации пpостым методом. Делим столбик  с веpоятностями таким обpазмо, чтобы  сyмма веpоятностей веpхней части pавнялась пpиблизительно сyмме веpоятностей нижней части

     0.5 - пеpвая часть = 0.5

     -----

     0.2 \

     0.2 | - втоpая часть = 0.5

     0.1 /

     Напpитив веpоятностей веpхней части пpоставляем  нyли, напpотив нижней - еденицы. В нашем  пpимеpе полyчим.

     0.5 0

     0.2 1

     0.2 1

     0.1 1

     Пpделываем потом то же с pазделенными частями. В конце-концов пpидем к томy, что  делить больше нечего.

     А 0.5 0

     B 0.2 10

     C 0.2 110

     D 0.1 111

     Итого - AABCDAABC = 0 0 10 110 111 0 0 10 110

     Пpичем закодиpованное сообщение (это видно) не может быть pаскодиpовано несколькими способами, хотя длина кодов символов отличается. Чтобы пpочитать закодиpованное сообщение стpоится бинаpное деpево. В нашем слyчае оно бyдет такое.

       ()

       / \

       0(A) 1

       / \

       0(B) 1

       / \

       0(C) 1(D)

     Вот еще пpимеp составления кодовых комбинаций по веpоятносям:

     0.3 00

     0.25 01

     --------------- (пеpвое деление)

     0.1 100

     0.1 101

     ------------- (втоpое деление)

     0.1 1100

     0.05 1101

     ----------- (тpетье деление)

     0.05 1110

     0.05 1111 

     2.4 Пример кодирования  и декодирования  методом Шеннона-Фано 

     С помощью табл. 4 можно закодировать и декодировать любое сообщение. В виде примера запишем двоичным кодом фразу: "Теория информаций"

     0 111 010000 11 01 000 11 011 11 0000

     01101000111111 111 00110 100

     11 0000 10111111 10101100110

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

     10011100110011001001111010000

     1011100111001001101010000110101

     010110000110110110

     Результат декодирования - фраза "способ кодирования". При таком кодировании любая  ошибка (случайное перепутывание  знаков 0 и 1) губительна, т.к. декодирование  всего следующего за ошибкой текста становится невозможным. Поэтому данный принцип кодирования используется тогда, когда ошибки при кодировании и передаче сообщения исключены. 

 

     

     Заключение 

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

     1.Обеспечение экономичности передачи информации посредством устранения избыточности.

     2. Обеспечение надежности (помехоустойчивости) передачи информации

     3.Согласование скорости передачи информации с пропускной способностью канала

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

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

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

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