Отже. Завдання. Використовувати код Хеммінга для двійкового повідомлення, довжина слова у якого становить 16 біт. Оригінал тексту візьмемо таке «0100010000111101». Тобто в слові 16 «букв», кожна з яких може приймати значення або «0», або «1».
кодування
Спочатку в вихідне повідомлення додаємо контрольні біти і встановлюємо їх в нуль.
Контрольні біти розташовуються в тих номерах бітів, які дорівнюють ступенями двійки (бо алфавіт двійковий).
Тобто. Два в ступеня нуль - це одиниця, два в ступені 1 = два, два в ступені 2 = чотири, а два в ступені 3 = вісім, два в ступені 4 = 16
Значить контрольні біти будуть перебувати в «буквах» (бітах) під номерами 1, 2, 4, 8 і 16.
В інші номери біт переписуємо вихідне повідомлення.
Видно, що довжина «слова» через таку надмірності збільшилася на п'ять «букв». В даному випадку, звичайно. У вас кількість додаткових біт буде залежати від довжини вихідного «слова».
Тепер потрібно обчислити ці контрольні біти.
Кожен контрольний біт з номером N «контролює» безперервну послідовність з N бітів, через кожні N бітів.
Ось на зображенні відзначено іксами (X), які біти потрібно використовувати для обчислення першого контрольного біта (з номером «1»)
Для обчислення контрольно біта потрібно просто скласти всі «букви» нашого «слова», які він контролює, а потім прийняти нелегке рішення: якщо сума вийшла парна, то пишемо в результаті нуль, а якщо непарна - одиницю.
Обчислюємо перший біт.
Складаємо біти під номерами 3,5,7,9,11,13,15,17,19,21
Це буде 0 + 1 + 0 + 0 + 0 + 0 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 = 5
Вийшло 5 (п'ять). Сума непарна (на два остачі не ділиться). Значить пишемо в перший біт одиницю:
Тепер обчислимо контрольний біт номер 2. Для нього потрібно буде знайти суму кожних двох біт наступних один за одним безперервно, через кожні два біти. Такі біти я теж зазначив на зображенні.
Тобто будемо тепер підсумувати біти, Значить з третього по номеру, і далі ті, які відзначені іксом (X).
Їхні номери 3, 6, 7, 10, 11, 14, 15, 18, 19.
Це буде 0 + 0 + 0 + 1 + 0 + 0 + 1 + 1 + 1 = 4
Чотири - число парне, значить залишаємо в нашому другому бите нуль.
Переходимо до обчислення третього контрольного біта. Але це у нас він контрольний - третій. А в повідомленні цей біт записаний під номером 4 - чотири.
Значить і використовувати будемо всі потрапляють під наше правило біти, починаючи з п'ятого.
А це біти під номерами 5, 6, 7, 12, 13, 14, 15, 20, 21.
Складаємо їх: 1 + 0 + 0 + 0 + 0 + 0 + 1 + 0 + 1 = 3
В результаті у нас непарне число, значить пишемо в наш контрольний біт одиницю.
Залишилося всього нічого - обчислити два залишилися контрольних біта. які під номерами 8 і 16.
У восьмому залишаємо нуль тому, що в тій послідовності, яку ми використовуємо для обчислення присутні дві одиниці, що дають в сумі парне число.
А в 16-му теж сума біт виходить парної - залишаємо нуль:
У підсумку ми отримали слово з кодом Хеммінга, яке містить надлишкові біти (в сумі 21): «100110000100001011101».
декодування
А тепер уявімо, що до нас прийшло повідомлення з помилкою. Ось воно «100110001100001011101».
Ми знаємо, що в нього додані надлишкові біти за алгоритмом Хеммінга, і нам треба перевірити, чи є в ньому помилка чи ні.
Для цього потрібно поступити таким чином. Спочатку обчислюємо заново все контрольні біти за попереднім алгоритмом.
Для цього спочатку Обнуляємо все біти, що знаходяться на номерах ступенів двійки:
У першому залишаємо нуль, бо в підконтрольних бітах парне число одиниць.
Обчислюємо всі інші контрольні біти за описаним вище алгоритмом (мені лінь заново його описувати тут), і отримуємо, що не збігаються контрольні біти під номерами 1 і 8:
Тепер складаємо номера цих контрольних біт: 1 + 8, і отримуємо 9 - номер біта, в якому закралася помилка! Ура! Тепер просто міняємо дев'ятий біт на зворотний - з одиниці на нуль, - і отримуємо вихідне повідомлення!