1 Біт перевіряє біти 1,3,5,7,9,11,13,15,17,19,21.
Біт 2 перевіряє біти 2,3,6,7,10, 11, 14,15,18,19.
Біт 4 перевіряє біти 4,5,6,7,12,13,14,15,20,21.
Біт 8 перевіряє біти 8,9, 10, 11,12,13,14,15.
Біт 16 перевіряє біти 16,17,18,19,20,21.
Біт |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
1 |
● |
|
● |
|
● |
|
● |
|
● |
|
● |
|
● |
|
● |
|
● |
|
● |
|
● |
2 |
|
● |
● |
|
|
● |
● |
|
|
● |
● |
|
|
● |
● |
|
|
● |
● |
|
|
4 |
|
|
|
● |
● |
● |
● |
|
|
|
|
● |
● |
● |
● |
|
|
|
|
● |
● |
8 |
|
|
|
|
|
|
|
● |
● |
● |
● |
● |
● |
● |
● |
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
● |
● |
● |
● |
● |
● |
Рис.1.6 — Схема розміщення бітів парності
У загальному випадку біт b перевіряється бітами b1, b2,..., bj, такими що b1+b2+...+bj=b.
Наприклад, біт 5 перевіряється бітами 1 і 4, оскільки 1+4=5. Біт 15 перевіряється бітами 1,2,4 і 8, оскільки 1+2+4+8=15 і т. д.
На рис. 1.10 показано побудова коду Хеммінга для 16-бітного слова
1111000010101110
Відповідним 21-бітним кодованими словом є
001011100000101101110
Щоб побачити, як відбувається виправлення помилок, розглянемо, що станеться, якщо біт 5 змінить значення через різкий стрибок напруги на лінії електропередачі.
У результаті замість кодованого слова
001011100000101101110 Вийде 001001100000101101110
Будуть перевірені 5 біт парності. Ось результати перевірки:
Біт парності 1 неправильний (біти 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 містять п'ять одиниць).
Біт парності 2 правильний (біти 2,3,6,7,10,11,14,15,18,19 містять шість одиниць).
Біт парності 4 неправильний (біти 4,5,6,7,12,13,14,15,20,21 містять п'ять одиниць).
Біт парності 8 правильний (біти 8,9,10,11,12,13,14,15 містять дві одиниці).
Біт парності 16 правильний (біти 16,17,18,19,20,21 містять чотири одиниці включаючи біт парності).
Біт |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
4 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
8 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
16 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Рис.1.7 — Схема розміщення коду з помилкою
Біт |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
1 |
0 |
|
1 |
|
0 |
|
1 |
|
0 |
|
0 |
|
1 |
|
1 |
|
0 |
|
1 |
|
0 |
2 |
|
0 |
1 |
|
|
1 |
1 |
|
|
0 |
0 |
|
|
0 |
1 |
|
|
1 |
1 |
|
|
4 |
|
|
|
0 |
0 |
1 |
1 |
|
|
|
|
0 |
1 |
0 |
1 |
|
|
|
|
1 |
0 |
8 |
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
1 |
1 |
0 |
Рис.1.8 — Схема перевірки бітів парності
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
1 |
0 |
|
1 |
|
0 |
|
1 |
|
0 |
|
0 |
|
1 |
|
1 |
|
0 |
|
1 |
|
0 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
0 |
0 |
1 |
1 |
|
|
|
|
0 |
1 |
0 |
1 |
|
|
|
|
1 |
0 |
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
● |
|
◌ |
|
|
|
|
|
● |
|
◌ |
|
|
|
|
|
● |
8 |
|
|
|
|
● |
|
|
|
|
|
|
|
◌ |
|
|
|
|
|
|
|
● |
16 |
|
|
|
|
● |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
◌ |
Рис.1.9 — Схема пошуку та виправлення помилок
Загальна кількість одиниць в бітах 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 і 21 повинна бути парною, оскільки в даному випадку використовується позитивна парність. Неправильним повинен бути один з бітів, що перевіряються бітом парності 1 (а саме 1,3,5,7,9,11,13,15,17,19 і 21). Біт парності 4 теж неправильний. Це означає, що змінив значення один з наступних бітів: 4,5,6,7,12,13,14,15,20,21. Помилка повинна бути в біті, який міститься в обох списках. В даному випадку є загальними біти 5,7,13,15 і 21. Оскільки біт парності 2 правильний, біти 7 і 15 виключаються. Правильність біта парності 8 виключає наявність помилки в біті 13. Нарешті, біт 21 також виключається, оскільки біт парності 16 правильний. У результаті залишається біт 5, в якому міститься помилка. Оскільки цей біт має значення 1, він повинен прийняти значення 0. Саме таким чином виправляються помилки.
Рис. 1.10 – Побудова коду Хеммінга для слова 1111000010101110 за допомогою додавання 5 контрольних розрядів до бітів даних
Щоб знайти неправильний біт, спочатку потрібно підрахувати всі біти парності. Якщо вони правильні, помилки немає (або є, але більше однієї). Якщо виявилися неправильні біти парності, то потрібно скласти їх номери. Сума, отримана в результаті, дасть номер позиції неправильного біта. Наприклад, якщо біт парності 1 і 4 неправильні, а 2, 8 і 16 правильні, то помилка сталася в біті 5 (1+4).