Узагальнені завадостійкі лишково – Хеммінгові коди

Завадостійкі коди. Перемежування та виграш від кодування

Лекція № 1.4

Теорія інформації

Вступ

В попередніх лекціях розглянуті найбільш відомі двійкові коди: контроль на парність (на непарність), матричні, Хеммінга та циклічні коди, які надають змогу виявляти чи виявляти та виправляти спотворення окремих двійкових символів при умові наявності одного із спотворень в інформаційному блоці – базовому кодовому слові (БКС). Окрім того, уже розглянуто декілька узагальнених кодів, які, використовуючи алгоритми відомих двійкових, надають змоги виявляти чи виявляти та виправляти спотворення груп (пакетів) двійкових символів при умові наявності спотворень в одному із узагальнених символів інформаційного блоку – в базовому кодовому слові: зокрема контрольне додавання та лишкові – матричні коди.

Сьогодні буде розглянуто ще один із таких узагальнених кодів − лишково – Хеммінгів код. Окрім того, розглянемо ситуацію, коли, в силу тих чи інших обставин, пакет спотворень перевищить можливості відомих чи доступних кодів. Тоді якимось чином слід звести ситуацію до можливостей застосування уже відомих кодів. Тобто, розглянемо так званий метод перемежування.

Окрім блокових кодів, які мають обмежену довжину, тобто застосовуються по відношенню до БКС, досить широке розповсюдження мають безперервні коди, одним із представників яких є так звані згортальні коди.

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

Лекція № 1.4 − “ Завадостійкі коди. Перемежування та виграш від кодування ”. В лекції будуть розглянуті наступні учбові питання:

1. Узагальнені завадостійкі лишково – Хеммінгові коди. 3

2. Метод перемежування. 6

3. Згортальні двійкові коди. 9

4. Виграш від кодування. 16

У лишково - Хеммінгових (ЛХ) кодах, як і при контрольному додаванні, двійкові базові кодові слова розбиваються на n b − розрядних узагальнених символів і записуються у вигляді α₁, α₂,..., α_n, де α _i ≤ 2 ^b – 1, а
N = bn. Так само, як і в двійковому коді Хеммінга (класична форма запису коду) узагальнені символи з номерами 2 ^j (j = 0, 1,…) є перевірочними, решта символів - інформаційні. Причому для отримання перевірочних символів при кодування використовується алгоритм, аналогічний алгоритму для двійкового коду Хеммінга, тобто для отримання першого перевірочного символу необхідно скласти по деякому модулю (одержати лишки) всі узагальнені символи, що мають в коді свого номера одиницю в першому (молодшому) розряді; для отримання другого перевірочного символу - скласти по модулю усі символи, що мають в коді свого номера одиницю в другому розряді і т.д.

Як модуль для отримання контрольних символів необхідно використовувати величину s = 2 ^b, тобто

α₁ = {α₃ + α₅ + α₇ + ………………} _{s ,}

α₂ = {α₃ + α₆ + α₇ + …………} _{s ,}

………………………………

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

Якщо приписати результатам порівняння значення 0, а результатам не порівняння - значення 1, то одержана сукупність нулів і одиниць утворює код, який також, як і в двійковому коді Хеммінга, є номером спотвореного символу.

Приклад. Хай необхідно закодувати ЛХ-кодом восьми розрядну
(N = 8) послідовність 10001101 Якщо код орієнтований на виправлення двократних спотворень, то b = 2, а s = 4. Кількість узагальнених символів
n = N / b = 4 (10.00.11.01). Відомо, що при цьому потрібно три перевірочні символи α₁, α₂, α₄, а інформаційними символами є α₃ = 10, α₅ = 00, α₆ = 11,
α₇ = 01: 00. 00. 10. 00. 00.11.01.

Для отримання першого перевірочного символу складемо по модулю чотири α₃, α₅, α₇ (00.00. 10. 00. 00. 11. 01).

α₁ = {α₃ + α₅ + α₇}₄ = 11

Аналогічно цьому

(00.00. 10. 00.00. 11. 01)

α₂ = {α₃ + α₆ + α₇}₄ = 00,

(00.00.10.00. 00. 11. 01)

α₄ = {α₅ + α₆ + α₇}₄ = 10.

Після кодування одержано код

11. 00. 10. 10. 00. 11 01 = α₁, α₂, α₃, α₄, α₅, α₆, α₇,

який повинен бути записаним в ЗП, переданим в канал зв’язку і т.д.

Хай зчитаний або прийнятий з каналу зв’язку код має спотворення у п’ятому символі:

α₁, α₂, α₃, α₄, ά₅, α₆, α₇ = 11. 00. 10. 10. 10. 11 01.

Після обчислення нових контрольних символів, одержимо

α₁ = {α₃ + ά₅ + α₇}₄ = 01

α₂ = {α₃ + α₆ + α₇}₄ = 00,

α₄ = {ά₅ + α₆ + α₇}₄ = 00.

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

Неважко визначити і величину спотворення. Насправді, будь-який з перевірочних символів, наприклад α_i, при спотворенні будь-якого інформаційного, наприклад α_j, що приймає участь у формуванні символу α_i, має величину

ά_і = {α_c + α_d + …… + { α_j + Δα_j } + ……}_s = { α_і + Δα_j } _s. (1)

Звідки

Δα_j = {ά_i − α_i} _{s .} (2)

Для вищерозглянутого прикладу

Δα₅ = {ά₁ – α₁}₄ = {01 − 11}₄ = 10

або

Δα₅ = {ά₄ – α₄}₄ = {00 − 10}₄ = 10.

Знаючи величину (ά_i) і місце спотворення (i), легко здійснити корекцію, оскільки з (2) слідує

Α_i = { ά_i − Δα_j } _{s .}

У нашому прикладі

α₅ = {ά₅ – Δα₅}₄ = {10 – 10}₄ = 00.

Алгоритм декодування ЛХ − коду може бути спрощеним, якщо при кодуванні замість перевірочних символів α_i в записану або передану послідовність записувати величину

Δα _і = { s − Δα_j } _s.

а при декодуванні використовувати алгоритм, повністю відповідний алгоритму Хеммінга, тобто включати в перевірку і необхідні перевірочні символи.

Для вже розглянутого прикладу Δα₁ = 11, Δα₂ = 00, Δα₄ = 10 необхідно записати (передати) код

α₁, α₂, α₃, α₄, α₅, α₆, α₇ = 11. 00. 10. 10. 00. 11. 01.

Якщо зчитано або прийнято слово з тим же спотворенням, що і раніше, тобто

α₁, α₂, α₃, α₄, ά₅, α₆, α₇, = 11. 00. 10. 10. 10. 11 01,

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

Δ α ₁ = { α ₁ + α₃ + ά₅ + α₇}₄ = 10,

Δ α ₂ = { α ₂ + α₃ + α₆ + α₇}₄ = 00,

Δ α ₄ = { α ₄ + ά₅ + α₆ + α₇}₄ = 10.

При цьому, якщо відмінним від нуля перевірочним символам приписати значення 1, а іншим - код 0, то одержимо код і = 101, що визначає місце спотворення, величина якого дорівнює значенню будь-якого ненульового перевірочного символу. Для розглянутого прикладу величина спотворення
Δα_і = 10, корекція якого нескладна.

Дата добавления: 2014-01-11