Задача кодирования. Хотя существующие на данный момент системы передачи данных отвечают всем основным стандартам и требованиям, они все же не являются совершенными. Причин тому влияние помех в канале связи
 Скачать 1.21 Mb.
|
|
2.2 Пример построения кода Шеннона В таблице 2.2 приведены промежуточные вычисления и результат построения кода Шеннона. Средняя длина кодовых слов l = 2,95. В данном случае избыточность кода Шеннона на 0,5 бита больше, чем избыточность кода Хаффмена. Из этого рисунка понятно, почему код неэффективен. Кодовые слова для букв b , d , e , f могут быть укорочены на 1 бит без потери свойства однозначной декодируемости. Таблица 2.2 Построение кода Шеннона
Докажем однозначную декодируемость кода Шеннона. Для этого выберем сообщения с номерами i и j , i < j . Кодовое слово ci для i заведомо короче, чем слово cj для j , поэтому достаточно доказать, что эти слова отличаются в одном из первых li символов. Рассмотрим разность qj − qi =Σ pk − Σ pk =Σ pk ≥ pi Вспомним, что длина слова и его вероятность связаны соотношением li = [− log pi ]≥ − log pi . Поэтому pi ≥2-li . С учетом этого неравенства q j − q i ≥ 2-li В двоичной записи числа в правой части мы имеем после запятой li −1 нулей и единицу в позиции с номером li. Это означает, что по меньшей мере в одном из li разрядов слова ci и cj отличаются и, следовательно, ci не является префиксом для cj. Поскольку это верно для любой пары слов, то код является префиксным. Заметим, что длины кодовых слов в коде Шеннона точно такие же, какие были выбраны при доказательстве прямой теоремы кодирования. Повторяя выкладки, получим уже известную оценку для средней длины кодовых слов 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.Согласование скорости передачи информации с пропускной способностью канала Задача кодирования является одним из главных понятий информатики, так как кодирование предшествует передаче и хранению информации, и, соответственно, является основой их успешного осуществления. При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Эта проблема решается с помощью помехоустойчивого кодирования. Помехоустойчивое кодирование передаваемой информации позволяет в приемной части системы обнаруживать и исправлять ошибки. Коды, применяемые при помехоустойчивом кодировании, называются корректирующими кодами. Впервые, исследование эффективного кодирования произвел Клод Шеннон. Для теории связи важнейшее значение имеют две теоремы, доказанные Шенноном. В работе были рассмотрены эти теоремы, и можно прийти к выводу, что первая – затрагивает ситуацию с кодированием при передаче сообщения по линии связи, в которой отсутствуют помехи, искажающие информацию, т.е. эта теорема является эталоном, какими должны быть помехоустойчивые коды, Вторая теорема относится к реальным линиям связи с помехами. В ходе курсовой работы были составлены примеры кодирования, на основе первой теоремы Шеннона. Это кодирования является достаточно эффективным, так как получаемый код практически не имеет избыточности, но, к сожалению, в реальных линиях связи множество помех, и такой результат недостижим. Поэтому код Шеннона не является таким же эффективным как, например код Хафмена. Но, несмотря на это нужно отметить, что Клод Шеннон был одним из основателей теории кодирования и его работы внесли огромный вклад в развитие информатики. |