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

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

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

1) все символы записываются в порядке убывания их вероятностей;

2) вся совокупность символов разбивается на две примерно равновероятные группы;

3) всем символам верхней группы приписывается первый кодовый символ 1; символам нижней группы - кодовый символ 0;

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

5) эта процедура повторяется до тех пор, пока в каждой подгруппе не останется по одной букве;

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

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

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. Минимальная средняя длина кодовой комбинации оптимального эффективного кода численно равна энтропии источника сообщений:

.

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

ДАЛЕЕ ПЕРЕСЧИТАТЬ КОД ДЛЯ УМЕНЬШЕНИЯ ВЕРОЯТНОСТИ НИ В 100 РАЗ, А В 50!!

Средняя длина  кода полученного методом Шеннона-Фано равна и минимальное кодовое расстояние:

Для того чтобы построить  помехоустойчивый код, для  которого вероятность ошибочного декодирования по сравнению с кодом Шеннона-Фано будет в 100 раз меньше:

1. Допустим, что вероятность ошибки  в одном символе полученного кода:

Вероятность ошибки искомого кода будет равно:

2.Найдем - минимальное кодовое расстояние, для которого вероятность ошибки будет равна:

.

3.Методом подбора найдем ближайшее решение задачи для кода, полученного методом Шеннона-Фано:

Восспользуемся формулой:

Если ,

удовлетворяется условие:

Вероятности  той или иной ошибки:

Отсюда вероятность ошибочного декодирования, которая меньше в 100 раз:

Найдем разницу:

Погрешность составляет .

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

Опишем метод построения порождающей матрицы, для получения помехоустойчивых кодов, основываясь на теоретическом материале:

Приведем пример построение порождающей матрицы на примере кода-, для кода- построение порождающей матрицы аналогично.

1.В таблице№1 представлены все кодовые слова - кода (- информационные, а   - проверочные символы).

                                                                           Табл.№1.

2. Системой проверочных уравнений, определяющих правила формирования проверочных символов по известным информационным символам:

номер проверочного символа;

номер информационного символа;

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

Пример. Для кода проверочные уравнения имеют вид:

.

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

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

- код, который был представлен в таблице№1, может быть задан матрицей:

Остальные кодовые слова получаются сложением строк матриц в различных сочетаниях.

Общее количество различных вариантов порождающих матрицу определяется выражением:

Для исключения неоднозначности в записи вводят понятие о канонической или систематической форме матрицы, которая имеет вид

где - единичная матрица, содержащая информационные символы;

- прямоугольная матрица, составленная из проверочных символов.

Порождающая матрица в систематическом виде для (5,3) - кода

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

Проверочная матрица в систематическом виде имеет вид

где - единичная матрица;

- прямоугольная матрица в транспонированном виде матрицы , из порождающей матрицы.

Проверочная матрица (5,3) – кода

Произведение информационного слова на порождающую матрицу дает кодовое слово кода

Пример для кода (5,3):

Заключение.

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

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

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

1.      Вентцель Е.С. «Теория вероятностей». – М.: Высш.шк., 2002г.

2.      Зюко А.Г. «Теория передачи сигналов». – М.: Радио и связь, 1986г.

3.      Зюко А.Г., Коробов Ю.Ф. «Теория передачи сигналов». – М.: Связь, 1972г.

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

11