Основные характеристики кода. Алгоритмы декодирования

Кодом длины называется любое подмножество двоичных слов длины :

.

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

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

, , .

Определенное таким образом рас стояние удовлетворяет аксиомам метрики:

1°. , .

2°. .

3°. .

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

Если передавалось слово , а принято слово , то равно количеству разрядов, искаженных при передаче (число ошибок).

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

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

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

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

Рассмотрим главные параметры, характеризующие код.

1°. Мощность кода , то есть количество кодовых точек. Если код имеет мощность , то блоки информации, которые он кодирует должны иметь длину , такую, что , то есть . Примем физическую скорость передачи канала за единицу: передача одного двоичного символа занимает одну единицу времени. Применив кодирование, получим, что двоичных символов передаются за единиц времени, то есть скорость передачи информации равна

бит/ед. вр.

Следовательно, чем больше мощность кода, тем большую скорость передачи информации он обеспечивает.

2°. Кодовое расстояние, равное минимальному расстоянию между кодовыми словами:

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

Теорема 1. Если , то код исправляет ошибок.

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

Очевидно, что и будет ближайшим к кодовым словом, так как для любого другого кодового слова имеем

Теорема доказана.

Основной задачей теории кодирования является следующая:

Для заданных построить код максимальной мощности такой, что .