Реферат: Основные параметры помехоустойчивого кодирования. Основные параметры помехоустойчивых кодов
11010
10001
10010
01101
01110
10110
10101
01010
01001
Причина, по которой таблица декодирования должна строиться именно таким образом, очень проста. Вероятность появления фиксированной комбинации из i ошибок равна Рt e (1 -Рe )5-i Заметим что при Рe<1/2 (1 -Рe )5 Pe (1 -Рe )4 Рe 2 (1 -Рe )3 ...
Таким образом, появление фиксированной одиночной ошибки более вероятно, чем фиксированной комбинации двух ошибок, и т. д. Это значит, что декодер, который декодирует каждую принятую последовательность в ближайшее к ней по расстоянию Хемминга кодовое слово, выбирает в действительности то кодовое слово, вероятность передачи которого максимальна (в предположении, что все кодовые слова равновероятны). Декодер, реализующий это правило декодирования, является декодером максимального правдоподобия, и в указанных предположениях он минимизирует вероятность появления ошибки декодирования принятой последовательности. В этом смысле такой декодер является оптимальным. Это понятие очень важно, поскольку декодеры максимального правдоподобия часто используются для коротких кодов. Кроме того, параметры декодера максимального правдоподобия могут служить эталоном, с которым сравниваются параметры других, неоптимальных декодеров. Если декодирование ведется с помощью таблицы декодирования, то элементы таблицы можно расположить так, чтобы получить декодирование по максимуму правдоподобия. К сожалению, объем таблицы растет экспоненциально с ростом длины блока, так что использование таблицы декодирования для длинных кодов нецелесообразно. Однако таблица декодирования часто оказывается полезной для выяснения важных свойств блоковых кодов.
Множество кодовых слов в таблице декодирования является подмножеством (первой строкой таблицы декодирования) множества всех 2n последовательностей длиной n. В процессе построения таблицы декодирования множество всех последовательностей длиной n разбивается на непересекающиеся подмножества (столбцы таблицы декодирования). В случае когда код исправляет t ошибок, число Ne последовательностей длиной n в каждом подмножестве удовлетворяет неравенству
Ne >=1+n+Cn 2 +...+Cn t , (2)
где Cn i - i-й биномиальный коэффициент.
Неравенство (2) следует непосредственно из того, что имеется ровно n различных последовательностей, отличающихся от данной последовательности в одной позиции, Cn 2 последовательностей, отличающихся в двух позициях, и т. д. Как и в приведенном выше простом примере, после размещения всех последовательностей, отличающихся от кодовых в t или менее позициях, почти всегда остаются неразмещенные последовательности [отсюда неравенство в (2)]. Теперь можно связать избыточность кода c числом ошибок, которые им исправляются Заметим сначала, что число всех возможных последовательностей равно 2n . Каждый столбец таблицы декодирования содержит Ne таких последовательностей, поэтому общее число кодовых слов должно удовлетворять неравенству
Ne <=<2n /(1+n+Cn 2 +...+Cn t ), (3)
Это неравенство называется границей Хемминга или границей сферической упаковки. Равенство в (3) достигается только для так называемых совершенных кодов. Эти коды исправляют все наборы из t или менее ошибок и не исправляют никаких других наборов. Число известных совершенных кодов очень невелико, так что равенство в (1.3) достигается в очень редких случаях.
Процесс кодирования состоит в том, что наборы k информационных символов отображаются в кодовые последовательности, состоящие из n символов. Любое такое отображение будем называть (n, k)-кодом, хотя обычно такое название применяется только к линейным кодам (которые обсуждаются позже). Поскольку число последовательностей длиной k равно 2k , неравенство (3) можно переписать следующим образом:
2k <=2n /(1+n+Cn 2 +...+Cn t ), (4)
Мера эффективности кода определяется отношением R=k/n (5)
и называется скоростью кода. Доля избыточно передаваемых символов равна 1-R.
Отображение, возникающее при кодировании, можно задавать таблицей кодирования. Например, код с четырьмя кодовыми словами задается табл. 2.
Таблица 2. Таблица поиска при декодировании
| Входная последовательность | Кодовая последовательность |
|
00 01 10 11 |
00100 01111 11011 К-во Просмотров: 175
Бесплатно скачать Реферат: Основные параметры помехоустойчивого кодирования. Основные параметры помехоустойчивых кодов
|