Исправление ошибок. Общий метод исправления ошибок применяется для кратности не более t

Общий метод исправления ошибок применяется для кратности не более t. Число возможных кодовых комбинаций помехоустойчивого кода разбивается на классы по числу разрешённых кодовых комбинаций. Класс это одна разрешённая кодовая комбинация и ближайшие к ней запрещённые. При декодировании определяется, какому классу принадлежит принятая кодовая комбинация. Если она принята с ошибкой, т.е. является запрещённой, то исправляется на разрешённую кодовую комбинацию, принадлежащую тому же классу.

Например, для исправления одиночной ошибки (t=1) каждой разрешённой КК сопоставим подмножество запрещённых. Чтобы эти подмножества не пересекались, d между разрешёнными КК должно быть не менее трёх, т.е.. Тогда за разрешённые КК можно принять A₀ = 000₂ и A₇ = 111₂ и приписать каждой из них подмножество тех запрещённых комбинаций, к которым может привести одиночная ошибка.

После приёма сообщения КК отождествляется с той разрешённой, которая находится от неё на минимальном кодовом расстоянии (d_min). Такое декодирование называется декодированием по методу максимального правдоподобия.

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

Методы эффективного кодирования

Одной из основных характеристик кода является избыточность. Это полезное свойство, так как оно повышает помехоустойчивость кода. Однако для передачи избыточных кодов по КС требуется больше времени.

Устранения избыточности называется - эффективным кодированием.

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

Алгоритмы, позволяющие автоматически строить неравномерные коды на основании известных частот появления символов, были впервые рассмотрены К. Шенноном и Н. Фано. Эффективный код так и называется – код Шеннона Фано.

Эффективность кода определяют через коэффициент избыточности

,

где n_ср, n_min – средняя и минимальная длина кодовой комбинации соответственно.

Описание методики.

1. Буквы алфавита сообщения выписываются в столбец в порядке убывания их вероятностей (см. табл. 3.4).

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

3. При соответствующем разбиении принадлежность к верхней половине обозначается символом 0, а к нижней – 1.

Пример.

Пример. Сообщения Х₁, Х₂, Х₃, Х₄ с вероятностями появления символов Р(Х₁) = 0,5, Р(Х₂) = 0,25, Р(Х₃) = 0,125, Р(Х₄) = 0,125 закодировать по Шеннону-Фано.

Xi	P(Xi)	N деления	Символ кода	n(Xi)
1	2	3	1	2	3
X1	0.5	I   II	I II	I II		‑	‑
X2	0.25			‑
X3	0.125
X4	0.125

X₁ = 0₂, X₂ = 10₂, X₃ = 110₂, X₄ = 111₂ (табл. 3.4). Среднее число символов, т.е. средняя длина КК

Дата добавления: 2014-01-11