ВУЗ:
Составители:
Рубрика:
83
4. КОРРЕКТИРУЮЩЕЕ КОДИРОВАНИЕ
4.1. Коды Хемминга
Первые корректирующие коды были разработаны Р. Хеммингом и
носят его имя. Если блочный код имеет
k
информационных символов, то
для обнаружения и исправления одиночной ошибки или ошибок большей
кратности в источник следует ввести избыточность или избыточные
символы. Количество избыточных символов можно определить по
формуле, которую называют формулой границы Хемминга,
κ
2
1
2
+
≤
Е
n
,
где n- общее количество символов в кодовой комбинации, Е – количество
ошибок ожидаемой кратности. При одиночной ошибке Е = n. Если k = 7, то
n =11, откуда количество добавочных символов равно четырем, n – k = 4.
Код Хемминга является
систематическим, это означает, что для
обнаружения и исправления ошибок должна быть
составлена система
уравнений,
которая должна иметь n+1 решения, из которых n решений
показывают номера ошибочных символов, и одно решение о правильно
принятой комбинации,
Формулу границы Хемминга можно записать в виде
≥
−kn
2 n+1.
Видно, что код n,k=11,7 является избыточным, а код 15,11 –
безызбыточным или совершенным.
Блочные систематические коды могут быть заданы
образующей и
проверочной
матрицами G и H, причем проверочная Н позволяет
составлять уравнения кодирования и декодирования,
Проверочная матрица Н должна иметь n – k строк и n столбцов, а
поскольку код является
разделимым, информационные и проверочные
символы должны располагаться на определенных местах, например,
четыре проверочных должны следовать за информационными. В матрице
каждый столбец обозначается номером
1
а ,
2
а и т.д. Последние n – k
столбцов представляют
единичную матрицу, остальные столбцы матрицы
должны представлять произвольные (n – k) четырех-символьные
комбинации, которые не могут быть нулевыми и повторяющимися.
Строим эту матрицу для кода n, k = 11, 7.
10001001100
01001111010
00101110001
00010100111
1110987654321
aaaaaaaaaaa
H =
Страницы
- « первая
- ‹ предыдущая
- …
- 81
- 82
- 83
- 84
- 85
- …
- следующая ›
- последняя »
