Зміст
Коди Хеммінга використовуються для вставки інформації про виправлення помилок у потоки даних. Коди розроблені таким чином, що помилка не тільки виявляється, але й виправляється. Додавання інформації про виправлення помилок збільшує обсяг даних, але це також підвищує надійність зв'язку через носії з високим рівнем помилок.
Кодування Хеммінга може бути складним у реалізації, але це можна зробити дуже швидко, використовуючи арифметичні прийоми на рівні бітів. Це дозволяє створити корисну та високошвидкісну систему корекції помилок, яка використовуватиметься у вбудованих додатках.
Крок 1
Створіть слово даних. Будь-який біт із позицією, яка має ступінь двох (перший, другий, четвертий тощо), повинен бути зарезервований для інформації про паритет. Використовуйте стільки, скільки потрібно для того, щоб слово мало вихідні дані та біти парності.
Приклад:
1 1 0 1 0 0 1 0 стає _ _ 1 _ 1 0 1 _ 0 0 1 0
Вихідні біти залишаються в тому ж порядку, але були розподілені, щоб вставити біти парності.
Крок 2
Обчисліть перший біт парності. Починаючи з першого біта, біт читається, а потім біт пропускається, і процедура повторюється до кінця. Тим часом підраховується кількість знайдених. Біти парності в цьому процесі не враховуються.
Якщо число одиничних парне, встановіть перший біт на нуль. В іншому випадку встановіть його на одиницю.
Приклад:
Біти 1, 3, 5, 7, 9 і 11 _ _ 1 _ 1 0 1 _ 0 0 1 0, _11101, містять чотири одиниці. Це парно, тому для першого біта встановлено нуль: 0 _ 1 _ 1 0 1 _ 0 0 1 0
Крок 3
Обчисліть інші біти парності. Починаючи з другого біта, зчитуються два біти, а потім два біти пропускаються, і процедура повторюється до кінця. Четвертий біт читає чотири біти, пропускає ще чотири, починаючи з біта чотири. За тією ж схемою дотримуються всі біти парності, поки всі вони не обчислюються.
Приклад:
Біт 2: 0 _ 1 _ 1 0 1 _ 0 0 1 0 перевіряє _1, 01, 01, які містять три одиниці, тому біт 2 встановлюється як один. Біт 4: _ 0 1 1 1 0 1 _ 0 0 1 0 перевіряє _101, 0, який містить два одиниці, тому біт 4 встановлюється рівним нулю. Біт 8: 0 1 1 0 1 0 1 _ 0 0 1 0 перевіряє _0010, який містить лише один, тому біт 8 встановлюється як один.
Тому слово кодується як 011010110010.
Крок 4
Підтвердьте слово. Якщо слово пошкоджене, біти парності не будуть відповідати очікуваному. Щоб підтвердити, що слово не пошкоджене, просто обчисліть біти парності, використовуючи кроки другий і третій. Якщо біти не однакові, запишіть їх позиції.
Крок 5
Виправте неправильний біт. Якщо ви виявили неправильні біти парності, просто додайте положення бітів. Значення суми - це позиція неправильного біта. Змініть бітове значення в цьому положенні.
Наприклад, якщо неправильні біти парності - один і чотири, зміна значення п'ятого біта виправить помилку.