Коди Хемінга

Відомо кілька різновидів коду Хэмінга, характеризуються різною коригувальною здатністю. До цих код звичайно ставляться коди з виправленням однократних помилок і коди з виправленням однократних і виявленням дворазових помилок.

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

де “k” - кількість інформаційних символів.

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

Результат першої перевірки дає цифру молодшого розряду синдрому у двійковому записі. Якщо результат цієї перевірки дасть 1, то один із символів перевіреної групи перекручений. Таким чином, першою перевіркою повинні бути охоплені символи з номерами, що містять у двійковому записі одиниці в першому розряді: 1,3,5,7,9 і т.д. результатом другої перевірки дає цифру другого розряду синдрому. Отже, другою перевіркою повинні бути охоплені символи з номерами, що містять у двійковому записі одиниці в другому розряді: 2,3,6,7,10 і т.д.

Аналогічно при третій перевірці повинні перевіряться символи, номери яких у двійковому записі містять одиниці в третьому розряді: 4,5,6,7,12 і т.д.

Таким чином, перевірочні групи повинні мати вигляд

……………………………………..

Перевірочна матриця коду повинна мати стовпців і рядків.

Кожний стовпець повинен становити двійкову комбінацію, що вказує позиції коду.

Наприклад, для коду довжиною t wx:val="Cambria Math"/><w:i/><w:sz w:val="32"/><w:sz-cs w:val="32"/><w:lang w:val="UK"/></w:rPr><m:t>n</m:t></m:r><m:r><w:rPr><w:rFonts w:ascii="Cambria Math"/><wx:font wx:val="Cambria Math"/><w:i/><w:sz w:val="32"/><w:sz-cs w:val="32"/><w:lang w:val="UK"/></w:rPr><m:t>=9</m:t></m:r></m:oMath></m:oMathPara></w:p><w:sectPr wsp:rsidR="00000000"><w:pgSz w:w="12240" w:h="15840"/><w:pgMar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> , що забезпечує виправлення однократних помилок, кількість надлишкових символів . При цьому в якості перевірочної може бути обрана наступна матриця

Представимо як приклад просту двійкову комбінацію 10011 кодом Хемінга. Тому що інформаційними повинні бути третій, п'ятий, шостий, сьомий і дев'ятий символи, то для розглянутого коду З умови забезпечення парності сум, одержимо наступне значення перевірочних символів:

. Отже, простому п’ятиелементному коду 11011 відповідає дев’ятиелементний код Хемінга 101100111.

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

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

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

Для розглянутого раніше коду з перевірочна матриця може мати вигляд

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

Надмірність коду Хемінга залежить від кількості інформаційних символів і при зміні k від 4 до 1013 змінюється від 0,429 до 0,098 при й від 0,5 до 0,0107 при .

<== попередня сторінка	\|	наступна сторінка ==>
Код з подвоєнням елементів	\|	Методичні вказівки

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.