Побудова коду Хеммінга

Вважатимемо, що в каналі зв'язку при передачі повідомлення може відбутися не більш ніж одна помилка. Це означає, що якщо початкове повідомлення a₁a₂...a_m кодується набором b₁b₂...b_l (l = m + k), то на виході можливі наступні варіанти кода: ́́́́́  . Таким чином, число варіантів рівне l+1. Це пояснюється тим, що помилка може не відбутися, або вона відбудеться в одному з l розрядів і символ b_i заміниться на протилежний . Число додаткових розрядів для побудови коду Хеммінга потрібно вибрати так, щоб їх вистачило для кодування перерахованих l+1 випадків. Отже, необхідно, щоб 2^k≥ l+1 або 2^m ≤ 2^l/(l+1). Тому, знаючи m, l вибираємо як найменше ціле число, що задовольняє умову: 2^m ≤ 2^l/(l+1). Число l називається довжиною коду Хеммінга. Число m – число інформаційних символів. Враховуючи, що l=m+k, можна вибирати не l, а число k, яке називається числом контрольних символів і є найменшим цілим числом, що задовольняє умові: 2^k > k + m + 1. Наприклад, якщо m = 4, то l = 7, k = 3; якщо m = 9, то l = 13, k = 4. Таким чином, при побудові кода Хеммінга, перше, що потрібно зробити: це по числу t визначити числа k і l. Нехай для повідомлення а = a₁a₂...a_m довжини m необхідно побудувати код Хеммінга. Візьмемо m=9; початкове повідомлення а=101110111=a₁a₂a₃a₄a₅a₆a₇a₈a₉.

Тоді l = 13, k = 4; код Хеммінга b = b₁b₂b₃b₄b₅b₆b₇b₈b₉b₁₀b₁₁b₁₂b₁₃.

Крок 1. Представимо кожне число і з множини L = {1,2...,l} у вигляді к-розрядного двійкового числа w = V_k-1V_k-2...V₁V₀. Результати запишемо у вигляді таблиці

w/i	1	2	3	4	5	6	7	8	9	10	11	12	13
V0	1	0	1	0	1	0	1	0	1	0	1	0	1
V1	0	1	1	0	0	1	1	0	0	1	1	0	0
V2	0	0	0	1	1	1	1	0	0	0	0	1	1
V3	0	0	0	0	0	0	0	1	1	1	1	1	1

Крок 2. Розіб’ємо множину L на k підмножин таким чином: L₀ = {і ∈ L₀ : V₀ = 1}; L₀ = {1, 3, 5, 7, 9, 11, 13}, L₁ = {і ∈ L₁ : V₁ = 1}; L₁ = {2, 3, 6, 7, 10, 11}, L₂ = {і ∈ L₂ : V₂ = 1}; L₂ = {4, 5, 6, 7, 12, 13}, L₃ = {і ∈ L₃ : V₃ = 1}; L₃ = {8, 9, 10, 11, 12, 13}.

Крок 3. Перші елементи (їх рівно k) цих множин є степенем числа 2; вони визначають номери контрольних розрядів коду Хеммінга. Решта елементів множини L визначають номери інформаційних розрядів. Отже, в коді Хеммінга розряди b₁b₂b₄b₈ – контрольні, решта розрядів b₃b₅b₆b₇b₉b₁₀b₁₁b₁₂b₁₃ – інформаційні.

Крок 4. Формування значень інформаційних символів. Інформаційні символи коду Хеммінга формуються природним чином з символів початкового повідомлення a₁a₂...a_m . А саме: b₃=a₁, b₅=a₂, b₆=a₃, b₇=a₄, b₉=a₅, b₁₀=a₆, b₁₁=a₇, b₁₂=a₈, b₁₃=a₉. Оскільки початкове повідомлення а = 101110111, то b₃=1 b₅=0, b₆=1, b₇=1, b₉=1, b₁₀=0, b₁₁=1, b₁₂=1, b₁₃=1.

Крок 5. Формування значень контрольних символів. Після визначення інформаційних символів контрольні символи визначаються таким чином: b₁= ⊕ ∑ b_j ; j ∈ L₀ ; j ≠ 1 b₂= ⊕ ∑ b_j ; j ∈ L₁ ; j ≠ 2 b₄= ⊕ ∑ b_j ; j ∈ L₂ ; j ≠ 4 b₈= ⊕ ∑ b_j ; j ∈ L₃ ; j ≠ 8. Тут ⊕ ∑ – сума по модулю два, b_j – розряди, що мають номери з відповідної множини L_j. У розглянутому прикладі матимемо: b₁ = b₃ ⊕ b₅ ⊕ b₇ ⊕ b₉ ⊕ b₁₁ ⊕ b₁₃ = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 1 b₂ = b₃ ⊕ b₆ ⊕ b₇ ⊕ b₁₀ ⊕ b₁₁ =1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1= 0 b₄ = b₅ ⊕ b₆ ⊕ b₇ ⊕ b₁₂ ⊕ b₁₃ = 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 b₈ = b₉ ⊕ b₁₀ ⊕ b₁₁ ⊕ b₁₂ ⊕ b₁₃ = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 = 0

Крок 6. Остаточно, для повідомлення а = 101110111 код Хеммінга b буде наступним: b=b₁b₂b₃b₄b₅b₆b₇b₈b₉b₁₀b₁₁b₁₂b₁₃ = 1010011010111. Таким чином можна побудувати код Хеммінга для довільного повідомлення довжиною m.