ВУЗ:
Составители:
15
2.4. Код Хэмминга: идея построения
Код Хэмминга представляет собой один из важнейших классов линейных
кодов, нашедших широкое применение на практике и имеющих простой и
удобный для технической реализации алгоритм обнаружения и исправления
одиночной ошибки.
Предположим, необходимо исправить одиночную ошибку бинарного кода.
Такой код состоит из n
и
символов, несущих информацию, и n
к
контрольных
(избыточных) символов. Всего символов в коде
ки
nnn
+
=
(2.4)
При передаче кода может быть искажен любой информационный символ.
Однако может быть и такой вариант, что ни один из символов не будет
искажен, т. е. если всего n символов, то с помощью контрольных символов,
входящих в это число, должно быть создано такое число комбинаций
к
n
2
,
чтобы свободно различить n+1 вариант.
Поэтому n
к
должно удовлетворять неравенству
.1n2
к
n
+≥
(2.5)
Тогда, согласно (2.4)
.2222
икик
nnnn
n
⋅==
+
(2.6)
Используя (2.5), запишем
(
)
и
n
n
21n2 ⋅+≥
, (2.7)
где 2
n
– полное число комбинаций кода.
Отсюда число информационных символов кода, обнаруживающего и
корректирующего одиночную ошибку,
()
1
2
2
n
n
и
+
≤
n
. (2.8)
Для вычисления основных параметров кода Хэмминга задается количество
либо информационных символов, либо информационных комбинаций
и
n
2N =
.
При помощи формул вычисляют n и n
к
. Соотношения между n, n
и
и n
к
для кода
Хэмминга представлены в табл. 2.1.
Зная основные параметры корректирующего кода, определяют, какие
позиции сигналов будут рабочими, а какие – контрольными. Практика
показала, что номера контрольных символов удобно выбирать по закону 2
i
, где
i = 0, 1, 2, 3, ... – натуральный ряд чисел. Номера контрольных символов в этом
случае равны 1, 2, 4, 16, 32... Затем определяют значения контрольных
коэффициентов (0 или 1), руководствуясь следующим правилом: сумма единиц
на проверочных позициях должна быть четной. Если эта сумма четна –
значение контрольного коэффициента нуль, в противном случае – единица.
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
