ВУЗ:
Составители:
ходится) и, естественно, ее устранить. Подобные коды, исправляющие одиночную ошибку, стали на-
зываться кодами Хемминга.
Основная идея состоит в добавлении к информационным битам не одного, а нескольких битов
четности, каждый из которых контролирует определенные информационные биты. Если пронумеро-
вать все биты передаваемые биты, начиная с 1 слева направо (стоит напомнить, что информацион-
ные биты нумеруются с 0 и справа налево), то контрольными (проверочными) оказываются биты, но-
мера которых равны степеням числа 2, а все остальные являются информационными. Например, для 8-
битного информационного кода контрольными окажутся биты с номерами 1, 2, 4 и 8:
1 2 3 4 5 6 7 8 9 10 11 12
0 0 0 1 1 1 0 1 1 1 0 1
7 6 5 4 3 2 1 0
Номера контролируемых битов для каждого проверочного приведены в табл. 1. При этом в пере-
чень контролируемых битов входит и тот, в котором располагается проверочный. При этом состояние
проверочного бита устанавливается таким образом, чтобы суммарное количество единиц в контроли-
руемых им битах было бы четным.
1 Проверочные и контролируемые биты передаваемого сообщения
Про
в.
би-
ты
Контролируемые биты
1
1 3 5 7 9 11 13 15 17 19 21 …
2
2 3 6 7 10 11 14 15 18 19 22 …
4
4 5 6 7 12 13 14 15 20 21 22 …
8
8 9 10 11 12 13 14 15 24 25 26 …
16
16 17 18 19 20 21 22 23 24 25 26 …
32
32 33 34 35 36 37 38 39 40 41 42 …
Пусть, например, вместо указанной выше последовательности пришла следующая (в 5-м бите 1 за-
менилась 0):
1 2 3 4 5 6 7 8 9 10 11 12
0 0 0 1 0 1 0 1 1 1 0 1
Бит 1 указывает на наличие ошибки в каком-либо бите с нечетным номером.
Бит 2 свидетельствует о том, что из них 3, 7 и 11 верны (т.е. ошибка в 5-м или 9-м бите).
Бит 4 указывает, что ошибка не в 9-м бите.
Таким образом, однозначно устанавливается, что ошибочным является 5-й бит – можно исправить
его значение на противоположное и, тем самым, восстановить правильную последовательность.
Более детальное рассмотрение кодов Хемминга позволяет сформулировать простой алгоритм про-
верки и исправления передаваемой последовательности бит:
(a) произвести проверку всех битов четности;
(b) если все биты четности верны, то перейти к пункту (e);
(c) вычислить сумму номеров всех неправильных битов четности;
(d) инвертировать содержимое бита, номер которого равен сумме, найденной в пункте (c);
(e) исключить биты четности, передать правильный информационный код.
Номера битов
кода Хемминга
Номера информа-
ционных битов
Передаваемые
биты
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
