Код Хеммінга: виявлення та виправлення помилок із прикладами

Що таке помилка?

Передані дані можуть бути пошкоджені під час зв'язку. Ймовірно, на нього впливає зовнішній шум або інші фізичні збої. У такій ситуації вхідні дані не можуть збігатися з вихідними даними. Ця невідповідність відома як «Помилка».

Помилки даних можуть призвести до втрати важливих або безпечних даних. Більша частина передачі даних у цифрових системах відбуватиметься у формі «бітової передачі». Навіть невелика зміна може вплинути на роботу всієї системи. У послідовності даних, якщо 1 змінюється на 0 або 0 змінюється на 1, це називається «бітовою помилкою».

Типи помилок

Існує в основному три типи бітових помилок, які виникають під час передачі даних від відправника до одержувача.

• Помилки одного біта
• Кілька бітових помилок
• Вибухові помилки

Однобітові помилки

Зміна, внесена в один біт у всій послідовності даних, відома як «помилка одного біта». Однак однобітна помилка не така вже й поширена. Крім того, ця помилка виникає лише в системі паралельного зв’язку, оскільки дані передаються побітово в одному рядку. Таким чином, є більше шансів, що один рядок може бути шумним.

Кілька бітових помилок

У послідовності даних, якщо є зміна двох або більше бітів послідовності даних передавача до приймача, це відомо як «багатобітові помилки».

Цей тип помилки здебільшого виникає як у послідовних, так і в паралельних мережах передачі даних.

Вибухові помилки

Зміна набору бітів у послідовності даних відома як «вибухова помилка». Цей тип помилки даних обчислюється від зміни першого біта до зміни останнього біта.

Що таке виявлення та виправлення помилок?

У цифровій системі зв'язку помилка буде передаватися з однієї системи зв'язку в іншу. Якщо ці помилки не виявити та не виправити, дані будуть втрачені. Для ефективного зв'язку системні дані повинні передаватись з високою точністю. Це буде зроблено, спочатку виявивши помилки та виправивши їх.

Виявлення помилок — це метод виявлення помилок, які присутні в даних, що передаються від передавача до приймача в системі передачі даних.

Тут ви можете використовувати коди надмірності, щоб знайти ці помилки, додаючи дані, коли вони передаються з джерела. Ці коди називаються «Коди виявлення помилок».

Існує три типи кодів виявлення помилок:

• Перевірка парності
• Перевірка циклічного резервування (CRC)
• Поздовжня перевірка надмірності (LRC)

Перевірка парності

• Він також відомий як перевірка парності.
• Він має економічно ефективний механізм виявлення помилок.
• У цій техніці надлишковий біт відомий як біт парності. Він додається до кожного блоку даних. Загальна кількість одиниць в одиниці має стати парною, що називається бітом парності.

Перевірка поздовжньої надлишковості

У цьому методі виявлення помилок блок бітів організований у табличному форматі. Метод LRC допомагає обчислити біт парності для кожного стовпця. Набір цієї парності також надсилається разом із вихідними даними. Блок парності допомагає перевірити надмірність.

Циклічна перевірка надмірності

Перевірка циклічної надлишковості — це послідовність надлишкових елементів, які необхідно додати в кінець блоку. Ось чому отримана одиниця даних повинна ділитися на друге, заздалегідь визначене двійкове число.

У пункті призначення вхідні дані потрібно розділити на однакове число. Якщо залишок немає, блок даних вважається правильним і приймається. В іншому випадку це вказує на те, що блок даних пошкоджено під час передачі, і, отже, його потрібно відхилити.

У коді Хеммінга джерело кодує повідомлення, додаючи до нього зайві біти. Ці надлишкові біти здебільшого вставляються та генеруються в певних позиціях у повідомленні для виконання процесу виявлення та виправлення помилок.

Історія коду Хеммінга

• Код Хеммінга — це техніка, створена RWHamming для виявлення помилок.
• Код Хеммінга слід застосовувати до блоків даних будь-якої довжини та використовувати зв’язок між даними та надлишковими бітами.
• Він працював над проблемою методу виправлення помилок і розробив дедалі потужніший набір алгоритмів під назвою код Хеммінга.
• У 1950 році він опублікував код Хеммінга, який сьогодні широко використовується в програмах, таких як пам'ять ECC.

Застосування коду Хеммінга

Ось кілька поширених застосувань коду Хеммінга:

• Супутники
• Пам'ять комп’ютера
• модеми
• PlasmaCAM
• Відкриті роз'єми
• Екрануючий дріт
• Вбудований процесор

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

• Метод коду Хеммінга ефективний у мережах, де потоки даних надаються для однобітових помилок.
• Код Хеммінга не тільки забезпечує виявлення бітової помилки, але також допомагає вам відступити бітову помилку, щоб її можна було виправити.
• Простота використання кодів Хеммінга робить їх найкращими для використання в пам’яті комп’ютера та виправлення одноразових помилок.

Недоліки коду Хеммінга

• Однорозрядний код виявлення та виправлення помилок. Однак, якщо кілька бітів є знайденою помилкою, результат може призвести до іншого біта, який має бути правильним для зміни. Це може призвести до подальших помилок у даних.
• Алгоритм коду Хеммінга може вирішити лише однобітові проблеми.

Як закодувати повідомлення в коді Хеммінга

Процес кодування повідомлення відправником складається з трьох кроків:

• Розрахунок загальної кількості надлишкових бітів.
• Перевірка положення зайвих бітів.
• Нарешті, обчислення значень цих надлишкових бітів.

Коли зазначені вище надлишкові біти вбудовані в повідомлення, воно надсилається користувачеві.

Крок 1) Розрахунок загальної кількості надлишкових бітів.

Припустимо, що повідомлення містить:

• n– кількість бітів даних
• p – кількість надлишкових бітів, які додаються до нього, щоб np могло вказувати щонайменше (n + p + 1) різних станів.

Тут (n + p) зображує розташування помилки в кожній із (n + p) позицій біта, а один додатковий стан вказує на відсутність помилки. Оскільки p бітів може означати 2^p держави, 2^p має принаймні дорівнювати (n + p + 1).

Крок 2) Розміщення зайвих бітів у правильному положенні.

P зайвих бітів слід розміщувати в позиціях бітів ступенів 2. Наприклад, 1, 2, 4, 8, 16 тощо. Вони називаються p₁ (на позиції 1), с₂ (на позиції 2), с₃ (на позиції 4) тощо.

Крок 3) Розрахунок значень надлишкового розряду.

Надлишкові біти мають бути бітами парності, що робить число 1 парним або непарним.

Є два типи паритету?

• Загальна кількість бітів у повідомленні, яка є парною, називається парною парністю.
• Загальна кількість бітів у повідомленні, зроблена непарною, називається непарною парністю.

Тут весь надлишковий біт, p1, повинен обчислюватися як парність. Він повинен охоплювати всі позиції бітів, двійкове представлення яких має містити 1 у першій позиції, за винятком позиції p1.

P1 — це біт парності для кожного біта даних у позиціях, двійкове представлення яких включає 1 у менш важливій позиції, не враховуючи 1 Like (3, 5, 7, 9, ….)

P2 — це біт парності для кожного біта даних у позиціях, двійкове представлення яких включає 1 у позиції 2 справа, не включаючи 2 Like (3, 6, 7, 10, 11,…)

P3 — це біт парності для кожного біта в позиціях, двійкове представлення яких включає 1 у позиції 3 справа, але не включає 4, як (5-7, 12-15,…)

Дешифрування повідомлення в коді Хеммінга

Одержувач отримує вхідні повідомлення, які вимагають виконання перерахунків для пошуку та виправлення помилок.

Процес перерахунку здійснюється в наступні кроки:

• Підрахунок кількості зайвих бітів.
• Правильне розташування всіх зайвих бітів.
• Честність перевірки

Крок 1) Підрахунок кількості зайвих бітів

Ви можете використовувати ту ж формулу для кодування кількості зайвих бітів

2^p ? n + p + 1

Тут кількість бітів даних, а p — кількість зайвих бітів.

Крок 2) Правильне розміщення всіх зайвих бітів

Тут p — надлишковий біт, який розташований у позиціях бітів ступенів 2, наприклад, 1, 2, 4, 8 тощо.

Крок 3) Честність перевірки

Біти парності потрібно обчислити на основі бітів даних і надлишкових бітів.

p1 = парність (1, 3, 5, 7, 9, 11…)

p2 = парність (2, 3, 6, 7, 10, 11… )

p3 = парність (4-7, 12-15, 20-23… )

Підсумки

• Передані дані можуть бути пошкоджені під час зв'язку
• Три типи бітових помилок: 1) однобітові помилки 2) багатобітові помилки 3) пакетні бітові помилки
• Зміна, внесена в один біт у всій послідовності даних, відома як «помилка одного біта».
• У послідовності даних, якщо є зміна двох або більше бітів послідовності даних передавача до приймача, це відомо як «багатобітові помилки».
• Зміна набору бітів у послідовності даних відома як «вибухова помилка».
• Виявлення помилок — це метод виявлення помилок, які присутні в даних, що передаються від передавача до приймача в системі передачі даних.
• Три типи кодів виявлення помилок: 1) Перевірка парності 2) Перевірка циклічної надлишковості (CRC) 3) Перевірка поздовжньої надлишковості (LRC)
• Код Хеммінга — це лінійний код, який корисний для виявлення помилок до двох негайних бітових помилок. Він здатний до однобітових помилок.
• Код Хеммінга — це техніка, створена RWHamming для виявлення помилок.
• Поширені програми використання коду Хеммінга – супутникова комп’ютерна пам’ять, модеми, вбудований процесор тощо.
• Найбільша перевага методу коду Хеммінга ефективна в мережах, де потоки даних надаються для однобітових помилок.
• Найбільшим недоліком методу коду Хеммінга є те, що він може вирішувати проблеми лише з одними бітами.
• Ми можемо виконати процес шифрування та декодування повідомлення за допомогою коду Хеммінга.