Skip to main content
LibreTexts - Ukrayinska

4.6.3: Коди Хеммінга

  1. Last updated
  2. Save as PDF
  • Page ID
    29930

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Припустимо, ми бажаємо виправити поодинокі помилки, і готові ігнорувати можливість множинних помилок. Набір кодів був придуманий Річардом Хеммінгом з мінімальною кількістю додаткових бітів парності.

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

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

    У таблиці 4.2 наведено деякі коди Хеммінга. Тривіальний випадок 1 біта парності не відображається, оскільки немає місця для будь-яких даних. Перший запис простий, і ми його вже бачили. Це потрійне резервування, де блок з трьох бітів відправляється за один біт даних. Як ми бачили раніше, дана схема здатна виправляти одну помилку або виявлення подвійних помилок, але не обидві (це справедливо для всіх кодів Хеммінга). Другий запис представляє значний інтерес, оскільки це найпростіший Кодекс Хеммінга з розумною ефективністю.

    Давайте розробимо (7, 4, 3) код Хеммінга. Існує кілька способів зробити це, але, напевно, найпростіше почати з декодера. Декодер отримує сім біт і виконує три перевірки парності на групи з них

    Біти парності Розмір блоку корисне навантаження Швидкість коду Тип коду блоку
    2 3 1 0,33 (3, 1, 3)
    3 7 4 0,57 (7, 4, 3)
    4 15 11 0,73 (15, 11, 3)
    5 31 26 0,84 (31, 26, 3)
    6 63 57 0,90 (63, 57, 3)
    7 127 120 0,94 (127, 120, 3)
    8 255 247 0,97 (255, 247, 3)
    Таблиця 4.2: Ідеальні коди Хеммінга

    біти з наміром визначити, де сталася помилка, якщо вона є. Давайте позначимо біти з 1 по 7. Якщо результати всі рівні парності, декодер робить висновок, що ніякої помилки не сталося. В іншому випадку ідентичність зміненого біта виводиться, знаючи, які операції парності не вдалося. З ідеальних кодів Хеммінга з трьома бітами парності один особливо елегантний:

    • Перша перевірка парності використовує біти 4, 5, 6 або 7 і тому не вдається, якщо один з них змінився
    • Друга перевірка парності використовує біти 2, 3, 6 або 7 і тому не вдається, якщо один з них змінився
    • Третя перевірка парності використовує біти 1, 3, 5 або 7 і тому не вдається, якщо один з них змінився

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

    Тепер розглянемо енкодер. З цих семи бітів чотири є вихідними даними, а три додаються кодером. Якщо початкові біти даних 3 5 6 7, кодер легко обчислити біти 1 2 4, знаючи правила, наведені трохи вище - наприклад, біт 2 встановлюється на все необхідне, щоб зробити парність бітів 2 3 6 7 навіть що означає 0, якщо парність бітів 3 6 7 вже навіть і 1 в іншому випадку. Кодер обчислює біти парності і розташовує всі біти в потрібному порядку. Тоді декодер, трохи виправивши при необхідності, може витягти біти даних і відкинути біти парності, які виконали свою роботу і більше не потрібні.