Код Хеммінга

Приклад 7.1. Визначити позиції контрольних розрядів та їх кількість в коді Хеммінга, якщо повідомлення, що кодується, складається з трьох інформаційних розрядів.

Розв’язок.

Для наочності домовимось позначати інформаційні розряди літерою І, контрольні – літерою К, а номер позиції, яку займає певний розряд, зазначати у нижньому індексі літер. Представлене таким чином вихідне повідомлення буде мати вигляд:

І₃ І₂ І₁

Згідно з методикою Хеммінга номери позицій контрольних розрядів визначаються як 2ⁿ (n=0,1,2,3...) і дорівнюють 1, 2, 4, 8,... Як видно, у вихідному повідомленні із зазначених позицій зайняті інформаційними розрядами позиції 1 та 2. Для їх звільнення необхідно зсунути всі інформаційні розряди повідомлення на дві позиції вліво. В результаті виконання операції зсуву отримуємо:

І₅ І₄ І₃ К₂ К₁

Аналіз отриманого формату повідомлення дозволяє побачити, що в ньому інформаційним розрядом зайнята позиція 4 (2²). Це означає, що розряди І₄ та І₅ необхідно зсунути вліво на одну позицію. Отримуємо:

І₆ І₅ К₄ І₃ К₂ К₁

Як видно, наведений формат повідомлення відповідає умові знаходження контрольних розрядів на позиціях 2ⁿ (n=0,1,2,3,...). Робимо висновок, що для кодування кодом Хеммінга повідомлення з трьох інформаційних розрядів до нього необхідно додати три контрольних розряди, при цьому контрольні розряди повинні розташовуватись на позиціях 1, 2, 4.

Приклад 7.2. Закодувати кодом Хеммінга повідомлення 1001.

Розв’язок.

За аналогією з прикладом 7.1 визначаємо формат повідомлення:

І₇ І₆ І₅ К₄ І₃ К₂ К₁

де І₇=1, І₆=0, І₅=0, І₃=1 (І₇І₆І₅І₃=1001).

Переведемо номери позицій в двійкову систему. Отримуємо:

7₁₀=111₂ 6₁₀=110₂ 5₁₀=101₂ 4₁₀=100₂

3₁₀=011₂ 2₁₀=010₂ 1₁₀=001₂

В позиції 1 значення розряду дорівнює 1 в комбінаціях 111, 101, 011, 001 (001 – позиція контрольного розряду, що розраховується). Тобто, значення контрольного розряду на позиції 1 обчислюється в нашому прикладі таким чином, щоб кількість одиниць на позиціях 1, 3, 5 та 7 була парною. Цю умову можна записати виразом:

І₇  І₅  І₃  К₁ = 0

Звідси отримуємо:

К₁ = І₇  І₅  І₃ = 1  0  1 = 0

В позиції 2 значення розряду дорівнює 1 в комбінаціях 111, 110, 011, 010 (010 – позиція контрольного розряду), тому для другого контрольного розряду отримуємо:

К₂ = І₇  І₆  І₃ = 1  0  1 = 0

Аналогічно для третього розряду:

К₃ = І₇  І₆  І₅ = 1  0  0 = 1

Таким чином, закодоване повідомлення буде мати вигляд: 1001100 (контрольні розряди підкреслено).

Приклад 7.3. Повідомлення 1001100 отримане в результаті кодування кодом Хеммінга (див. приклад 7.2). Перевірити, чи відповідає слово коду помилки номеру позиції викривленого розряду для розрядів на позиціях 6 (інформаційний розряд) та 4 (контрольний розряд).

Розв’язок.

Перед тим, як перейти до перевірки повідомлень визначимо позиції контрольних розрядів в повідомленні. Номери позицій контрольних розрядів визначаються як 2ⁿ (n=0,1,2,3...) і дорівнюють 1, 2, 4, 8,... У нашому випадку в повідомлені присутні розряди на позиціях 1, 2 та 4, які і є контрольними.

З наведеного аналізу можна зробити висновок, що слово коду помилки повинне складатися з трьох розрядів, при чому перший розряд цього слова (позначимо його Е₁) визначається відповідно до контрольного розряду на позиції 1; другий (Е₂) – до контрольного розряду на позиції 2; третій (Е₃) – до контрольного розряду на позиції 4.

Значення контрольного розряду (див. приклад 7.2) на позиції 4 визначається згідно з правилом контролю на парність інформаційних розрядів І₇, І₅, І₃ та, відповідно, самого контрольного розряду К₁:

І₇  І₅  І₃  К₁ = 0

Оскільки розряд слова коду помилки Е₁ повинен доповнювати значення перелічених розрядів до парності, його значення можна розрахувати за формулою:

Е₁ = І₇  І₅  І₃  К₁

Аналогічним чином для розрядів Е₂ та Е₃ отримуємо:

Е₂ = І₇  І₆  І₃  К₂

Е₃ = І₇  І₆  І₅  К₄

У випадку викривлення розряду на позиції 6 повідомлення 1001100 прийме вигляд 1101100. За отриманими формулами розрахуємо значення розрядів слова коду помилки:

Е₁ = 1  0  1  0 = 0

Е₂ = 1  1  1  0 = 1

Е₃ = 1  1  0  1 = 1

Упорядкувавши розряди слова коду помилки (у вигляді Е₃Е₂Е₁), отримуємо значення 110, що дорівнює 6 – номеру викривленого розряду.

У випадку викривлення розряду на позиції 4 повідомлення 1001100 прийме вигляд 1000100. Розраховуємо значення розрядів слова коду помилки:

Е₁ = 1  0  1  0 = 0

Е₂ = 1  0  1  0 = 0

Е₃ = 1  0  0  0 = 1

Отримуємо код помилки 100, що дорівнює номеру викривленого розряду.