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

Вариант № 8.

1.       Дан алфавит из 8 букв. Пусть z1,z2,z3,z4,z5,z6,z7,z8 заданный алфавит.

Даны вероятности появления букв: .

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

В общем случае для алфавита из 8 букв средняя длина кодовой комбинации будет меньше 3, но больше энтропии алфавита.

Вычислим энтропию алфавита:

Вычислим среднюю длину кодовой комбинации:

Средняя длина кодовой комбинации в нашем случае точно равна энтропии.

2.       Дан циклический код (7,4) с производящим многочленом .

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

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

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

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

, где , а степень .

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

Будем варьировать .

1 степень.

. Видим, что в многочлене 4 ненулевых коэффициента.

2 степень.

Рассмотрим все возможные значения коэффициентов и .

Пусть . Тогда получаем , 4 ненулевых коэффициента.

Пусть . Тогда , 3 ненулевых коэффициента.

Пусть . Тогда , 3 ненулевых коэффициента.

Пусть . Тогда , 4 ненулевых коэффициента.

3 степень.

Рассмотрим все возможные значения коэффициентов , и . Для удобства оформим результаты в таблицу.

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