Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Коди, стійкі до перешкод. Коди Хемінга
У цьому параграфі розглянемо один частковий випадок рівномірного двійкового кодування, а саме, уважатимемо, що не лише алфавіт В ={0, 1}, алейалфавіт А ={0, 1}. Розглянемосхему рівномірного кодування із параметрами k, n: де – слова довжини, відповідно, n та k (n ). Кажуть, що схема визначена кодом . Нормою двійкового вектора α = компонент. Отже, Операцію над двійковими розрядами (бітами)- додавання за модулем 2 (mod2) – означуютьтак: 0 0=0 . Якщо α та β – двійкові вектори, то α - порозрядне додавання за модулем 2. Припустимо, що в каналі зв’язкудієджерело адитивнихперешкод, яке описуютьмножиною P (n, t). Елементи цієї множини – двійкові вектори –помилки у яких норма будь-якого фрагмента, не більша, ніжt, якщодловжина фрагмента Ɩ ≤ n (тобто на n переданих поспіль двійкових символів припадає не більше, ніж tпомилок). Цеозначає, щоякщо на вході каналу зв’язку передано повідомлення|α, то на виходіможе бути отримано будь-яке слово ізмножини {α Припустимо, що в каналі зв'язку діє джерело адитивних перешкод, яке описують множиною Р(п, і). Елементи цієї множини - двійкові вектори-помилки x1x2...xs, у яких норма будь-якого фрагмента xixi+1…xi+ l -1 не більша, ніж t, якщо довжина фрагмента l ≤ n (тобто на n переданих поспіль двійкових символів припадає не більше, ніжt помилок). Це означає, що якщо на вході каналу зв'язку передано повідомлення а, то на виході може бути отримано будь-яке слово із множини {α . Оскільки проблема локалізації інформації (розділення закодованого повідомлення на елементарні коди) у моделі рівномірного кодування тривіальна, то виявлення помилок полягає в знаходженні незбігу локалізованої групи п символів з жодним елементарним кодом. Якщо внаслідок помилки елементарний код перейде в інший елементарний код, то помилку не буде виявлено. Іноді можливе виправлення помилки. Якщо групу символів локалізовано правильно, то для цього необхідно й достатньо, щоб помилкова група була " синонімом" єдиного елементарного коду. Канал зв'язку називають надійним, якщо будь-які помилки виявляються або виправляються відповідно до заданої мети декодування. Далі наведені головні положення побудови кодів, які забезпечують надійність найпростіших каналів зв'язку. З методичних міркувань у цьому параграфі зручно використовувати такі позначення. Елементи множини - двійкові вектори довжини п ~ позначатимемо великими латинськими буквами X, Y, Z, а їхні компоненти - відповідними малими буквами з індексами. Зокрема, елементарні коди будемо позначати як традиційно β 1, β 2, β 3, …, так і 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⊕ Z1=X⊕ Z для деякого Z1∈ P(n, t). Додамо до обох частин останньої рівностіX⊕ Z1тоді отримаємоX⊕ Y=Z1⊕ Z.Але, використовуючи (7.2), можемо записати , a . Суперечність. Навпаки, нехай𝜌 (Х, У)< 2 t для деяких різних X, Y ∈ V, тоді . Отже існують, Z1 та Z2 такі, що , (тобто Z1, Z2∈ P(n, t)) таX⊕ Y=Z1⊕ Z2. ЗвідсиX⊕ Z1=Y⊕ Z2=W, тобто в разі отримання спотвореного елементарного кодуW неможливо визначити, Xчи Y був переданий насправді. ▲ Доведений результат має геометричну інтерпретацію. МножинуSt (X) = {У|ρ (X, У) ≤ t} називають кулею радіуса t із центром у точці X. Теорема 7.8. Якщо в каналі зв'язку діє джерело адитивних перешкодP(n, t) то 1) для виявлення будь-яких помилок необхідно й достатньо, щоб для будь-якого Х, Y∈ V куляS1(X)не містила інших елементарних кодів, крім X; 2) для виправлення будь-яких помилок необхідно й достатньо, щоб для будь-яких Х, Y∈ V виконувалась умоваSt(X)∩ St(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 є одночасно лінійним підпростором простору над полем Е2. Усі лінійні коди - систематичні. Лінійні коди можна задавати простіше, ніж коди загального типу. Достатньо вказати твірні групи V. Їх можна подати матрицею з k рядками та п стовпцямиG(V) -- базисом векторного простору V. МатрицюG(V) називаютьпороджувальною матрицею коду V. За допомогою породжувальної матриціG=G(V) можна кодувати повідомлення. Якщо - повідомлення, то β =α G. Двоїстість, яка зв'язує ортогональні підпростори, приводить до ще одного способу задания лінійних кодів. Вектори Х, У∈ називають ортогональними, якщо (mod2). Ортогональний підпростірдля лінійного коду V називають двоїстим кодом для V. Його розмірність дорівнює п-k, і код визначає двоїсту схему алфавітного кодування σ n-k, n. Матрицю -- породжувальну матрицю коду -- називаютьперевірною матрицею коду V. Отже, маємо --двоїстий спосіб задания лінійного коду V перевірною матрицею Н=Н(V). Легко переконатись, що якщо С(V)=[ JkA ] де – Jk одинична k × k -матриця; то , де AT --транспонована матриця. Звідси випливає, що коли І -множина інформаційних розрядів для коду 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. Коди ХемінгаHd ete c t (n) для виявлення помилок у кана лі зв'язку із джерелом перешкод P (n, 1) визначені для будь-якого п: КодHd 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 розрядів, оскільки значення в довільному розряді слова х 1 х 2.. .х n ∈ НHd ete c t (n) однозначно визначається зазначеннями в інших розрядах із рівняння х 1 ⊕ х 2 ⊕... ⊕ х n =0. Маємо Як одну з породжувальних матриць можна взятии Якщовибрати I ={ 1, 2, j, n -1}, тоотримаємовідповіднусхемурівномірногокодування σ n-1, n: x1x2…xn-1→ x1x2…xn-1xn, де xn= х 1 ⊕ х 2 ⊕... ⊕ х n -1 НадлишковістьуразівикористанняHdetec t (n) становить R =(n -1)-1. У цьому коді Хемінга найбільш явно використана ідея перевірки на парність. Коди Хемінга для виправлення помилок у каналі зв'язку з джерелом перешкод Р(п, 1) будуються для значень п = 2s-1(s=2, З,...). Код (n) зручно задавати перевірною матрицею, яка має s рядків та 2s-1 стовпців. Стовпцями є всеможливі ненульові двійкові набори довжини s. Їх зручно розташовувати так, щоб i -й злівa стовпчик к був двійковим розкладом числа і (старші розряди зверху): Таке розташування стовпців перевірної матриці зумовлено вибором як контрольних тих розрядів, у яких номери є степенями двійки: {1, 2, 4, 8, 16,..., 2s-1}. Приклад 7.8. Для значейь n =3, 7 матимемо такі перевірні матриці коду Нсоrreсt(n): ▲ За допомогою перевірної матриці Н=H(Н соrreсt (п))код ХемінгаН соrreсt (п) задають так: (7.6) Приклад 7.9. Закодуємо повідомлення 1001 за допомогою коду Хемінга для n =7. Запишемо макет коду, беручи до уваги розташування контрольних розрядів: x 1 x 2l x 4001. Для знаходження значень контрольних розрядів використаємо умову (7.6) (доданки з нульовими коефіцієнтами не записані): звідки х 4⊕ 1=0, х 2⊕ 1⊕ 1=0, х 1⊕ 1⊕ 1=0. Отже, х 1=0, х 2=0, х 4=1 і отримаємо такий код заданого повідомлення: 0011001. ▲ Покажемо, що ρ (Нсоrreсt(n))≥ 3, тобто Нсоrreсt(n)забезпечує корекцію будь-яких помилок у каналі зв'язку з джерелом перешкодР(п, 1). Справді, якщоХ≠ 0таХ∈ Нсоrreсt(n), то , оскільки всі стовпці перевірної матриці ненульові. Далі, , оскільки якщо X має одиниці лише в двох розрядах, нехайхi=хj=1, тоhi⊕ hj = 0, що є рівносильним hi=hj а всі стовпці перевірної матриці різні. Отже, найменша вага ненульового вектора з Нсоrreсt(n)не менша трьох. Тоді на підставі (7.5) ρ (Нсоrreсt(n))≥ 3. Нехай в елементарному кодіX∈ Нсоrreсt(n) виникла помилка в i -му розряді: кодХ= x 1 x 2… xi …хп перейшов у код Х´ = Х ⊕ еi =х1х2... хi ⊕ 1…хп(тут еi — вектор, i -та компонента якого дорівнює 1, а решта компонент - нулі). Тоді , бо (mod 2). Звідси випливає, що коли локалізовано послідовність символів , то достатньо визначити вектор (mod2). Якщо він нульовий, то помилки немає, а ні, то цей вектор являє собою двійковий розклад номера розряду, у якому виникла помилка. Приклад 7.10. Нехай для п=7 локалізовано послідовність X =0110010. Знаходимо Робимо висновок, що виникла помилка в сьомому розряді елементарного коду, виправляємо її (інвертуємо помилковий розряд): 0110011. З відкоректованого коду виділяємо інформаційну групу розрядів (третій, п'ятий, шостий та сьомий розряди). У результаті отримуємо 1011. ▲ Надлишковість у разі використання коду Нсоrreсt(n) зменшується зі зростанням n: Якщо , то будуютьукорочений код Хемінга. Його задають перевірною матрицею, утвореною першимип стовпцями перевірної матриці Нсоrreсt(n), деп1 - найменше ціле із чисел, які більші ніжп і мають вигляд 2s-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), додаючи розряд к0 перевірки на парність (розширений (8, 4)-кодХемінга, див. зауваження до задачі 9). Під час передавання за розширеним кодом Хемінга отримані повідомлення: а) 00100001; б) 00110001. Що можна стверджувати у випадках а та б? 16. Побудувати код ХемінгаНсоrreсt(15) для передавання 11-розрядної інформаційної комбінації 10110110110. Показати процес виявлення помилки, яка відбулася в п'ятому розряді коду, отриманого на виході каналу зв'язку. Зауваження. Код ХемінгаНсоrreсt(15) називають також (15, 11)- кодом Хемінга.
|