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

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

TransmitЗв'язок може призвести до пошкодження даних. На них може вплинути зовнішній шум або інші фізичні збої. У такій ситуації вхідні дані не можуть збігатися з вихідними. Така невідповідність називається «помилкою».

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

Типи помилок

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

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

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

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

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

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

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

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

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

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

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

Виявлення помилок це метод пошуку помилок, присутніх у даних transmitТед з transmitтер до приймача в Передача даних системи.

Для пошуку цих помилок використовуються коди надмірності шляхом додавання додаткових бітів до даних, коли вони transmitз джерела. Ці додаткові біти називаються «кодами виявлення помилок». Три найпоширеніші типи коду виявлення помилок:

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

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

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

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

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

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

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

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

Що таке Хеммінг Code?

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

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

Історія Геммінга Code

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

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

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

• Супутники
• Комп'ютерна пам'ять (ECC RAM)
• модеми
• PlasmaCAM
• Відкриті роз'єми
• Екранований провід
• Вбудовані процесори

Переваги Хеммінга Code

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

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

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

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

Процес, який відправник використовує для кодування повідомлення, включає такі три кроки:

• Обчисліть загальну кількість надлишкових бітів.
• Визначте положення надлишкових бітів.
• Обчисліть значення кожного надлишкового біта.

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

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

Припустимо, що повідомлення містить n біти даних та p надлишкові біти, додані так, щоб 2^p може вказувати щонайменше (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) Обчисліть значення кожного надлишкового біта.

Кожен надлишковий біт є бітом парності, який робить кількість одиниць у його групі парною або непарною. Існує два типи парності:

• Паритет: Загальна кількість одиниць у покритих позиціях стає парною.
• Непарна парність: Загальна кількість одиниць у покритих позиціях робиться непарною.

Кожен біт парності охоплює певний набір позицій, що визначається двійковим представленням номерів позицій:

• p₁ перевіряє кожну позицію, двійкове значення якої має 1 у найменш значущому біті — позиції 1, 3, 5, 7, 9, 11 тощо.
• p₂ перевіряє кожну позицію, двійкове значення якої має 1 у другому біті справа — позиції 2, 3, 6, 7, 10, 11 тощо.
• p₃ перевіряє кожну позицію, двійкове значення якої має 1 у третьому біті справа — позиції з 4 по 7, з 12 по 15 тощо.

Розроблений приклад (7,4): Розглянемо чотири біти даних 1011Потрібні три біти парності (2³ = 8 ≥ 4 + 3 + 1), що дає семибітове кодове слово, представлене як p₁ p₂ d₁ p₃ d₂ d₃ d₄Розміщення даних розміщує позиції 3, 5, 6, 7 = 1, 0, 1, 1. Використання парної парності: p₁ охоплює позиції 1, 3, 5, 7 (біти 1, 0, 1 → p₁ = 0); p₂ охоплює 2, 3, 6, 7 (біти 1, 1, 1 → p₂ = 1); p₃ охоплює 4, 5, 6, 7 (біти 0, 1, 1 → p₃ = 0). transmitтому кодове слово ted є 0110011.

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

Отримувач приймає вхідне повідомлення та виконує перерахунки, щоб знайти та виправити помилки. Процес перерахунку використовує такі кроки:

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

Крок 1) Підрахуйте кількість надлишкових бітів. Використовуйте ту саму формулу, що й для кодування: 2^p ≥ n + p + 1, де n – кількість бітів даних, а p – кількість надлишкових бітів.

Крок 2) Правильно розташуйте всі зайві біти. Кожен надлишковий біт знаходиться в бітовій позиції, яка є степенем числа 2, наприклад, 1, 2, 4 та 8.

Крок 3) Виконайте перевірку парності. Біти парності перераховуються з бітів даних та отриманих надлишкових бітів:

• p₁ = парність(1, 3, 5, 7, 9, 11, …)
• p₂ = парність(2, 3, 6, 7, 10, 11, …)
• p₃ = парність(4–7, 12–15, 20–23, …)

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

Поширені запитання