Классификация способов кодирования

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:53, 10 августа 2016.

Различия

Коды
Блочные Потоковые
Есть двоичное сообщение:


кодирование:

Блоки длины преобразуются независимо друг от друга в блоки длины
Здесь нельзя разделить на блоки независимо

Есть двоичное сообщение:


— проверочный символ

Пример

— длина закодированного сообщения.
Оно обнаруживает 1 или 2 ошибки.
Если возникнет ошибка в одном из информационных символов , то будет 2 ошибки
Если ошибка в , то ошибка только внешняя → 1 ошибка

Потоковый код

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

TemplateExampleIcon.svg Пример потокового кода
Есть конечный автомат:
Рис. 1. Пример потокового кода.

Пусть каждому состоянию соответствует какой-то абстрактный проверочный символ. Тогда закодировав указанное слово, получим (начальное состояние - А):


Блочный код

TemplateDifinitionIcon.svg Определение «Блочный код»
Кодирование -

Раскодирование -

- длина кода

- количество кодовых слов

- нельзя раскодировать

- код

- мощность кода

- получаются какие-то ошибки

, если

, если ,т.ч. вероятность ошибки переводящая - максимальна

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

Систематический код

TemplateDifinitionIcon.svg Определение «Определение - Cистематический код»
Коды, где начальная часть длины кодового слова совпадает с кодируемым словом - систематический код. Иными словами в порождающей матрице левая часть является единичной матрицей.
TemplateExampleIcon.svg Пример систематического кода

где: — информационное слово, — кодовое слово, — проверочные символы


TemplateExampleIcon.svg Пример метода наибольшего правдоподобия

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

Принято : .

1-вариант:

вероятность, что это было кодируемым словом.

2-вариант:

3-вариант:

самый лучший вариант

4-вариант:

т.к. следовательно, - лучший вариант (если , то на выходе сплошной шум).

Метод наибольшего правдоподобия основан на выборе входа с максимальной условной вероятностью.


Литература

Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.