Коди, стійкі до перешкод. Коди Хемінга

У цьому параграфі розглянемо один частковий випадок рівномірного двійкового кодування, а саме, уважатимемо, що не лише алфавіт В ={0, 1}, алейалфавіт А ={0, 1}. Розглянемосхему рівномірного кодування із параметрами k, n:

де – слова довжини, відповідно, n та k (n ). Кажуть, що схема визначена кодом .

Нормою двійкового вектора α = компонент. Отже,

Операцію над двійковими розрядами (бітами)- додавання за модулем 2 (mod2) – означуютьтак: 0 0=0 . Якщо α та β – двійкові вектори, то α - порозрядне додавання за модулем 2.

Припустимо, що в каналі зв’язкудієджерело адитивнихперешкод, яке описуютьмножиною P (n, t). Елементи цієї множини – двійкові вектори –помилки у яких норма будь-якого фрагмента, не більша, ніжt, якщодловжина фрагмента Ɩ ≤ n (тобто на n переданих поспіль двійкових символів припадає не більше, ніж tпомилок). Цеозначає, щоякщо на вході каналу зв’язку передано повідомлення|α, то на виходіможе бути отримано будь-яке слово ізмножини {α

Припустимо, що в каналі зв'язку діє джерело адитивних пере­шкод, яке описують множиною Р(п, і). Елементи цієї множини - двійкові вектори-помилки x₁x₂...x_s, у яких норма будь-якого фраг­мента x_ix_i+1…_{xi+ l -}1 не більша, ніж t, якщо довжина фрагмента l ≤ n (тобто на n переданих поспіль двійкових символів припадає не більше, ніжt помилок). Це означає, що якщо на вході каналу зв'язку передано повідомлення а, то на виході може бути отримано будь-яке слово із множини {α .

Оскільки проблема локалізації інформації (розділення закодо­ваного повідомлення на елементарні коди) у моделі рівномірного кодування тривіальна, то виявлення помилок полягає в знаходженні незбігу локалізованої групи п символів з жодним елементарним кодом. Якщо внаслідок помилки елементарний код перейде в ін­ший елементарний код, то помилку не буде виявлено. Іноді можливе виправлення помилки. Якщо групу символів локалізовано правиль­но, то для цього необхідно й достатньо, щоб помилкова група була " синонімом" єдиного елементарного коду.

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

З методичних міркувань у цьому параграфі зручно використовувати такі позначення. Елементи множини - двійкові вектори довжини п ~ позначатимемо великими латинськими буквами X, Y, Z, а їхні компоненти - відповідними малими буквами з індексами. Зокрема, елементарні коди будемо позначати як традиційно β ₁, β ₂, β ₃, …, так і X, Y, Z, залежно від контексту.

Віддаллю Хемінга називають функціюр(Х, Y) двох змінних, визначену на множині Е

: : ρ (X, Y)= (дорівнює кількості розрядів, у яких вектори Xта У не збігаються). Скалярний добутоквекторів Х, Y∈ Е визначають так: . Він дорівнюєкількості розрядів, у яких X та Y збігаються й дорівнюють 1.

Легко перевірити такі співвідношення:

де 0 (виділено напівжирним шрифтом) - n-вимірний вектор із нульо­вими компонентами,

, (7.2)

(7.3)

(7.4)

Для віддалі Хемінга виконуються аксіоми метрики:

, причому в тому й лише в тому випадку, якщо Х = У;

та нерівність трикутника

Метрика Хемінга є зручним математичним поняттям для форму­лювання умов надійності кодування в разі адитивних помилок. Нехай схемаσ ­­_{k, п} визначена кодом .Кодовоювіддаллю для коду V називають величину

Теорема 7.7. Якщо в каналі зв'язку діє джерело адитивних пере­шкодP(n, t)то

1) для виявлення будь-яких помилок необхідно й достатньо p(V)> t;

2) для виправлення будь-яких помилок необхідно й достатньо p(V)> 2t.

Зауваження. Іншими словами, код здатний виявляти будь-які комбінації зt і меншої кількості помилок тоді й лише тоді, коли його кодова віддаль більша ніжt; код здатний виправляти будь-які комбінації зt і меншої кількості помилок тоді й лише тоді, коли його кодова віддаль більша ніж 2 t.

Доведення. 1. Нехай ρ (V)> t. Якщо Х∈ V, Z∈ P(n, t), Z≠ 0, то, використовуючи спочатку (7.3), а потім (7.1), можемо записати . Отже, X ⊕ Z ∈ V i помилку виявле­но. Навпаки, нехай𝜌 (Х, Y)≤ t таX, Y∈ V, X≠ Y. Тоді, використовуючи (7.2), маємо , отже, Z=X⊕ Y∈ P(n, t). Звідси випливає, щоX⊕ Z=Y, тобто помилку в елементарному кодіYне можна виявити.

2. Нехай ρ (V)> 2 t. Якщо Х∈ V, Z∈ Р(п, t), то Х є єдиним елементар­ним кодом з V, який міг перейти внаслідок помилки вX⊕ Z. Справді, припустимо, що існує Y ≠ X такий, щоY∈ V таY⊕ Z₁=X⊕ Z для дея­кого Z₁∈ P(n, t). Додамо до обох частин останньої рівностіX⊕ Z₁тоді отримаємоX⊕ Y=Z₁⊕ Z.Але, використовуючи (7.2), можемо записати , a . Супе­речність. Навпаки, нехай𝜌 (Х, У)< 2 t для деяких різних X, Y ∈ V, тоді . Отже існують, Z₁ та Z₂ такі, що , (тобто Z₁, Z₂∈ P(n, t)) таX⊕ Y=Z₁⊕ Z₂. ЗвідсиX⊕ Z₁=Y⊕ Z₂=W, тобто в разі отримання спотвореного елементарного кодуW неможливо визначити, Xчи Y був переданий насправді. ▲

Доведений результат має геометричну інтерпретацію.

МножинуS_t (X) = {У|ρ (X, У) ≤ t} називають кулею радіуса t із центром у точці X.

Теорема 7.8. Якщо в каналі зв'язку діє джерело адитивних пере­шкодP(n, t) то

1) для виявлення будь-яких помилок необхідно й достатньо, щоб для будь-якого Х, Y∈ V куляS₁(X)не містила інших елементарних кодів, крім X;

2) для виправлення будь-яких помилок необхідно й достатньо, щоб для будь-яких Х, Y∈ V виконувалась умоваS_t(X)∩ S_t(Y) =∅.▲

Рівномірне кодування σ _{k, n}: α _i→ β _i (i =1, 2, 3,..., 2 ^k) називають систематичним, якщо можна виділити множину к розрядів , які називають інформаційними, так, що коли (i=1, 2, 3,..., 2 ^k), то . Решту розрядів у такому разі називають контрольними.

Рівномірне кодування σ _{k, n}: α → β _i (i =1, 2, 3,..., 2 ^k) називаютьлінійним, або груповим, якщо код утворює підгрупу відносно операції ⊕ порозрядного додавання векторів за модулем два. У такому разі код V є одночасно лінійним підпростором простору над полем Е₂. Усі лінійні коди - систематичні.

Лінійні коди можна задавати простіше, ніж коди загального типу. Достатньо вказати твірні групи V. Їх можна подати матрицею з k рядками та п стовпцямиG(V) -- базисом векторного простору V. МатрицюG(V) називаютьпороджувальною матрицею коду V. За допомогою породжувальної матриціG=G(V) можна кодувати пові­домлення. Якщо - повідомлення, то β =α G.

Двоїстість, яка зв'язує ортогональні підпростори, приводить до ще одного способу задания лінійних кодів. Вектори Х, У∈ нази­вають ортогональними, якщо (mod2). Ортогональний підпростірдля лінійного коду V називають двоїстим кодом для V. Його розмірність дорівнює п-k, і код визначає двоїсту схему алфавітного кодування σ _{n-k, n}. Матрицю -- породжувальну матрицю коду -- називаютьперевір­ною матрицею коду V. Отже, маємо --двоїстий спосіб задания лінійного коду V перевірною матрицею Н=Н(V). Легко переконатись, що якщо С(V)=[ J_kA ] де – J_k одинична k × k -матриця; то , де A^T --транспонована матриця. Звідси випливає, що коли І -множина інформаційних розрядів для коду V, то як множину інформаційних розрядів для двоїстого коду V^⊥ можна взяти .

Приклад 7.7. Для лінійного коду V ={000, 011, 101, 110}, який визна­чає схему лінійного рівномірного кодування σ _{2, 3}

00→ 000, 01→ 011, 10→ 101, 11→ 110

з інформаційними розрядами I ={1, 2}, маємо

і двоїсту схему σ _{1, 3}:

0→ 000, 1→ 111. ▲

Теорема 7.9. Для кодової віддалі лінійного коду виконується рів­ність

(7.5)

Доведення. Зазначимо, що нульовий вектор 0 міститься в будь- якому лінійному коді. Рівність (7.5) випливає з того, що

▲

P. Хемінг(R. Hamming) 1950 p. запропонував коди для виявлен­ня й виправлення помилок у разіt= 1. Коди Хемінга лінійні та мають найменшу надлишковість, можливу для даного k.

Коди ХемінгаH_{d ete c t} (n) для виявлення помилок у кана лі зв'язку із джерелом перешкод P (n, 1) визначені для будь-якого п:

КодH_{d ete c t} (n) - - лінійний. Справді, якщо Х, Y ∈ H _detect (n), то

Т обтоX⊕ Y∈ H _detect (n).Заспіввідношенням (7.5) ρ (H _detect (n))=2, тому, будь-якапомилкавканалізджереломперешкодР(n, 1) виявляється. Як інформаційні розряди для коду H _detect (n)можна взяти будь-які п-1 розрядів, оскільки значення в довільному розряді слова х ₁ х ₂.. .х _n ∈ НH_{d ete c t} (n) однозначно визначається зазначеннями в інших розрядах із рівняння х ₁ ⊕ х ₂ ⊕... ⊕ х _n =0. Маємо

Як одну з породжувальних матриць можна взятии

Якщовибрати I ={ 1, 2, j, n -1}, тоотримаємовідповіднусхемурівномірногокодування σ _{n-1, n}:

x₁x₂…x_n-1→ x₁x₂…x_n-1x_n,

де x_n= х ₁ ⊕ х ₂ ⊕... ⊕ х _{n -1} НадлишковістьуразівикористанняH_{detec t} (n) становить R =(n -1)^-1.

У цьому коді Хемінга найбільш явно використана ідея перевірки на парність.

Коди Хемінга для виправлення помилок у каналі зв'язку з джерелом перешкод Р(п, 1) будуються для значень п = 2^s-1(s=2, З,...). Код (n) зручно задавати перевірною матрицею, яка має s рядків та 2^s-1 стовпців. Стовпцями є всеможливі ненульові двійкові набори довжини s. Їх зручно розташовувати так, щоб i -й злівa стовпчик к був двійковим розкладом числа і (старші розряди зверху):

Таке розташування стовпців перевірної матриці зумовлено вибором як контрольних тих розрядів, у яких номери є степенями двійки: {1, 2, 4, 8, 16,..., 2^s-1}.

Приклад 7.8. Для значейь n =3, 7 матимемо такі перевірні матриці коду Н_соrreсt(n):

▲

За допомогою перевірної матриці Н=H(Н _соrreсt (п))код ХемінгаН _соrreсt (п) задають так:

(7.6)

Приклад 7.9. Закодуємо повідомлення 1001 за допомогою коду Хемінга для n =7. Запишемо макет коду, беручи до уваги розташу­вання контрольних розрядів: x ₁ x ₂l x ₄001. Для знаходження значень контрольних розрядів використаємо умову (7.6) (доданки з нульо­вими коефіцієнтами не записані):

звідки х ₄⊕ 1=0, х ₂⊕ 1⊕ 1=0, х ₁⊕ 1⊕ 1=0. Отже, х ₁=0, х ₂=0, х ₄=1 і отримаємо такий код заданого повідомлення: 0011001. ▲

Покажемо, що ρ (Н_соrreсt(n))≥ 3, тобто Н_соrreсt(n)забезпечує корекцію будь-яких помилок у каналі зв'язку з джерелом перешкодР(п, 1). Справді, якщоХ≠ 0таХ∈ Н_соrreсt(n), то , оскільки всі стовпці перевірної матриці ненульові. Далі, , оскільки якщо X має одиниці лише в двох розрядах, нехайх_i=х_j=1, тоh_i⊕ h_j = 0, що є рівносильним h_i=h_j а всі стовпці перевірної матриці різні. Отже, найменша вага ненульового вектора з Н_соrreсt(n)не менша трьох. Тоді на підставі (7.5) ρ (Н_соrreсt(n))≥ 3.

Нехай в елементарному кодіX∈ Н_соrreсt(n) виникла помилка в i -му розряді: кодХ= x ₁ x ₂… x_i …х_п перейшов у код Х´ = Х ⊕ е_i =х₁х₂... х_i ⊕ 1…х_п(тут е_i — вектор, i -та компонента якого дорівнює 1, а решта компонент - нулі).

Тоді , бо (mod 2). Звідси випливає, що коли локалізовано послідовність символів , то достатньо визначити вектор (mod2). Якщо він нульовий, то помилки немає, а ні, то цей вектор являє собою двій­ковий розклад номера розряду, у якому виникла помилка.

Приклад 7.10. Нехай для п=7 локалізовано послідовність X =0110010. Знаходимо

Робимо висновок, що виникла помилка в сьомому розряді елементарного коду, виправляємо її (інвертуємо помилковий роз­ряд): 0110011. З відкоректованого коду виділяємо інформаційну групу розрядів (третій, п'ятий, шостий та сьомий розряди). У резуль­таті отримуємо 1011. ▲

Надлишковість у разі використання коду Н_соrreсt(n) зменшується зі зростанням n:

Якщо , то будуютьукорочений код Хемінга. Його задають перевірною матрицею, утвореною першимип стовпцями перевірної матриці Н_соrreсt(n), деп₁ - найменше ціле із чисел, які більші ніжп і мають вигляд 2^s-1. Очевидно, що всі попередні міркування є правильними й для вкороченого коду Хемінга.

Задачі

1. Нехай числа 1, 2, 4, 17, 98 закодовані своїми двійковими розкладами мінімально можливої довжини. Наприклад, кодом оди­ниці є 1, кодом двійки є 10, кодом четвірки є 100. Чи є це кодування роздільним?

2. Для кожного з роздільних кодівV побудувати префіксний код із тим самим набором довжин елементарних кодіва-в:

а) V ={01, 10, 100, 111, 011};

б) V ={1, 10, 00, 0100};

в) V ={10, 101, 111, 1011}.

3. Для заданих розподілів імовірностей а - е появи букв побудувати коди за методом Фано:

а)Р={0.6, 0.1, 0.09, 0.08, 0.07, 0.06};

б) Р ={0.4, 0.4, 0.1, 0.03, 0.03, 0.02, 0.02};

в) P ={0.3, 0.2, 0.2, 0.1, 0.1, 0.05, 0.05};

г) P ={0.25, 0.2, 0.15, 0.15, 0.15, 0.1};

д) P ={0.4, 0.18, 0.1, 0.1, 0.07, 0.06, 0.05, 0.04};

е) P ={0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

Для кожного розподілу визначити .

4. Для розподілів імовірностей а - е задачі 3 побудувати опти­мальні коди за методом Хаффмана. Для кожного розподілу визна­чити та порівняти з відповідним значенням (див. задачу 3). Указа­ти розподіли, для яких метод Фано не дає оптимального коду.

5. Якщо ймовірності появи букв є степенями двійки , то довжини відповідних елементарних кодів, одержаних за мето­дами Фано і Хаффмана, збігаються й дорівнюють п_i.Довести.

6. Використовуючи алгоритм Хаффмана, стиснути текст а, б. Визначити коефіцієнт стиснення (вважати, що в нестисненому тексті кожний символ кодують одним байтом):

а) THIS IS A SIMPLE EXAMPLE OF HUFFMAN ENCODING;

б)МІНІМІЗАЦІЯ ЧАСУ ВИКОНАННЯ ПРОГРАМИ.

7. Використовуючи код Хемінга H _detect (n) для значення параметра n=8, закодувати повідомлення 011011110011010111101.

8. Повідомлення закодоване за допомогою коду Хемінга H _detect(8). На виході каналу зв'язку з джерелом адитивних перешкод Р (8, 1) отримано код 011010011001010011101110. Чи можна стверджувати, що під час його передавання виникла помилка? Якщо так, то в якій групі цифр?

9. Для повідомлень 1101 та 1011 побудувати код ХемінгаН_соrreсt(7), використовуючи перевірну матрицю Н.

Зауваження. Код ХемінгаН_соrreсt (7) часто називають (7, 4)-кодомХемінга.

10. За допомогою коду ХемінгаН_соrreсt (7) закодувати повідом­лення 110010111011. Для кодування використати перевірну матрицю H.

11. На виході каналу зв'язку з джерелом адитивних перешкод Р(7, 1) отримано такі комбінації в коді ХемінгаН_соrreсt (7):

а) 1001001; б)0110001; в) 0011111; г) 0110100.

Виконати корекцію кодів і декодувати ці повідомлення.

12. Знайти породжувальну матрицю G=G(Н_соrreсt (7)) коду ХемінгаН_соrreсt(7).

13. Для повідомлень 1101 та 1011 побудувати код ХемінгаН_соrreсt(7), використовуючи породжувальну матрицю G (див. задачу 12).

14. За допомогою коду ХемінгаН_соrreсt(7) закодувати повідом­лення 110010111011. Для кодування використати породжувальну матрицю G (див. задачу 12).

15. Побудувати код Хемінга для виправлення помилки в одному розряді, і виявлення помилки в двох розрядах під час передавання 4-розрядної двійкової комбінації. Записати перевірну матрицю цього кеду.

Вказівка. Використати код ХемінгаН_соrreсt(7), додаючи розряд к₀ перевірки на парність (розширений (8, 4)-кодХемінга, див. заува­ження до задачі 9).

Під час передавання за розширеним кодом Хемінга отримані повідомлення: а) 00100001; б) 00110001. Що можна стверджувати у випадках а та б?

16. Побудувати код ХемінгаН_соrreсt(15) для передавання 11-роз­рядної інформаційної комбінації 10110110110. Показати процес виявлення помилки, яка відбулася в п'ятому розряді коду, отрима­ного на виході каналу зв'язку.

Зауваження. Код ХемінгаН_соrreсt(15) називають також (15, 11)- кодом Хемінга.