Студенти, аспіранти, молоді вчені, які використовують базу знань в своє навчання і роботи, будуть вам дуже вдячні.
Визначення 1. Систематичними називаються коди, в яких інформаційні та контрольні символи займають строго певні місця в кодових комбінаціях.
Визначення 2. Лінійними називаються коди, в яких контрольні символи являють собою лінійні комбінації інформаційних символів:
Лінійні двійкові коди утворюють алгебраїчну групу по відношенню до операції додавання по модулю 2, тому що сума кодових слів лінійного коду дає кодове слово, що належить даному коду. Це властивість дає можливість побудувати всі дозволені комбінації лінійного коду, маючи лише обмежене їх число.
Визначення 3. Вагою кодового слова називається число його ненульових елементів.
Відзначимо важливу властивість групових кодів: мінімальна кодова відстань між кодовими словами групового коду одно мінімальній вазі ненульових кодових слів.
Побудова лінійного коду здійснюється за допомогою так званої що утворює (породжує, виробляє) матриці.
При побудові породжує матриці слід керуватися наступними правилами:
1) кількість початкових кодових слів має дорівнювати числу інформаційних символів;
2) все початкові кодові слова повинні бути різні;
3) серед початкових кодових слів не повинно бути нульового;
4) всі початкові кодові слова повинні бути лінійно незалежними;
5) кількість одиниць в кожній початковій кодової комбінації має бути не менше;
6) кодове відстань між будь-якими парами початкових кодових слів повинно бути не менше.
Підібрані за цими правилами початкові кодові слова записують у вигляді утворює матриці. містить рядків і стовпців:
Код, породжений даної матрицею, називається-кодом.
Будь-яку породжує матрицю можна привести до так званої лівої канонічної чи наведеної ступінчастою формі
де - одинична подматріца порядку. - перевірочна подматріца, що містить рядків і стовпців.
Канонічний вигляд породжує матриці можна отримати, взявши в якості початкових кодових слів ті слова, які містять одну одиницю в інформаційній частині. В цьому випадку рядками перевірочної подматріци повинні бути розрядні комбінації з числом одиниць, не меншим, ніж. Хеммінга код декодування лінійний
Метод кодування за допомогою породжує матриці полягає в наступному: перша комбінація - нульова, рядки породжує матриці представляють собою комбінацій шуканого коду, інші комбінації знаходять підсумовуванням всіх можливих комбінацій рядків породжує матриці.
Приклад 1. За допомогою породжує матриці побудувати систематичний лінійний код, здатний виправляти одиночну помилку при передачі 16 повідомлень ().
Рішення. Відомо що. Значить, і.
За табл. визначаємо число контрольних символів.
Згідно з правилом побудови перевірочної подматріци кількість одиниць в рядку повинно бути не менше, ніж. З трьохелементної комбінацій вибираємо тільки ті, в яких кількість одиниць більше або дорівнює двом: 110, 101, 011, 111.
Будуємо породжує матрицю
Рядки в перевірочної матриці можна міняти місцями. При цьому отримаємо кілька варіантів породжують матриць і, отже, кілька варіантів лінійних кодів для розглянутого прикладу.
Алгоритм освіти контрольних символів за відомою інформаційної частини може бути записаний у такий спосіб:
Контрольний символ являє собою суму інформаційних символів, відповідних одиницям першого стовпчика перевірочної подматріци. другий контрольний символ - суму інформаційних символів, відповідних одиницям другого шпальти перевірочної подматріци, і т.д.
Приклад 2. Закодувати в лінійному коді комбінацію чотиризначного двійкового коду 1100 (.
Рішення. Число інформаційних символів. З табл. 3.1.
Породжує матрицею може служити матриця (3) з прикладу 3. Тоді згідно (4)
Отже, шукана повна комбінація коду: 1100110.
Зауваження. Нехай - інформаційні символи, тоді кодове слово лінійного коду може бути знайдено за формулою
Закодируем комбінацію 1100 по формулі (5):
Корекція помилок виконується за допомогою перевірок
Число перевірок дорівнює числу контрольних символів коригуючого коду.
В результаті перевірок утворюється комбінація символів. звана синдромом. Якщо вага синдрому дорівнює нулю, то прийнята комбінація вважається безпомилковою, в іншому випадку прийнята комбінація містить помилку.
Виправлення помилок проводиться по виду синдрому за допомогою контрольної матриці. яка складається з двох підматриць: і одиничної подматріци -го порядку:
Стовпці такої матриці є значення синдрому для розряду, що відповідає номеру стовпця матриці.
Приклад 3. Показати процес виправлення помилки в довільному розряді будь-якої кодової комбінації коригуючого коду, побудованого в прикладі 3.3.
Рішення. Згідно з принципом побудови системи перевірок (6) система перевірок для побудованого коду буде мати вигляд
Будуємо контрольну матрицю:
Якщо розряди синдрому відповідають на одну матриці. тобто то помилка - в першому розряді прийнятої комбінації, якщо синдром має вигляд. що відповідає дві колонки матриці. то помилка - у другому розряді, а синдром 001 відповідає помилку в третьому контрольному розряді кодової комбінації, і т.д.
Для перевірки коригувальних властивостей коду використовуємо комбінацію під номером 7: 1010101.
Нехай стався збій в четвертому розряді, тобто комбінація прийнята в наступному вигляді: 1011101.
Синдром 111 збігається з четвертим стовпчиком контрольної матриці, отже, в четвертому розряді символ слід замінити на зворотний.
Зауваження. Нехай - кодове слово лінійного коду, тоді синдром може бути знайдений за формулою
Знайдемо синдром прийнятої комбінації за формулою (3.8):
Зауваження. Кодування можливо і за допомогою контрольної матриці: контрольний символ () дорівнює сумі інформаційних символів, відповідних одиницям го рядка матриці.
код Хеммінга
Код Хеммінга є одним з важливих класів лінійних кодів. Він знайшов широке застосування на практиці, має простий і зручний для технічної реалізації алгоритм виявлення та виправлення одиночної помилки ().
Хеммінга запропонував розташувати стовпці контрольної матриці так, щоб номер -го стовпця матриці і номер розряду кодової комбінації відповідали бінарного поданням числа. Тоді синдром, знайдений за допомогою перевірочних рівнянь, буде двійковим поданням номера розряду кодової комбінації, в якій виникла помилка. Для цього контрольні символи повинні знаходитися не в кінці кодової комбінації, а на номерах позицій, вибраних за законом. тобто на номерах 1, 2, 4, 8, .... Таким чином, характерна особливість контрольної матриці коду Хеммінга полягає в тому, що її стовпцями є номери символів кодового слова в двійковому коді довжини.
Приклад 4. Побудувати код Хеммінга для однієї з комбінацій чотирирозрядний двійкового коду.
Рішення. Оскільки. значить.
Вихідна комбінація з чотирьох інформаційних символів набуває вигляду. де - контрольні символи; - інформаційні символи.
Будуємо контрольну матрицю. її стовпцями є номери символів кодового слова в Трехразрядное двійковому коді.
Зауваження. Десяткове число можна представити у вигляді
де можуть приймати два значення: 0 або 1.
Тоді - розрядних двійкове подання числа.
Наприклад. значить, 001 - Трехразрядное двійкове подання 1; 6 110, так як. тоді
Після перестановки стовпців, що мають одну одиницю, контрольна матриця набуде вигляду
Контрольні символи визначаються формулами
Система перевірок має вигляд
Зауваження. При передачі по каналу зв'язку в кодовому слові може виникнути подвійна і більш помилка. В цьому випадку синдром може прийняти будь-яке значення, в тому числі і нульове. При цьому відбудеться виправлення випадкового символу. Для виключення такого автоматичного виправлення вводиться ще один символ для перевірки всієї комбінації на парність. Кодова відстань збільшується.
Приклад 5. Закодувати в коді Хеммінга комбінацію 1101.
Рішення. За умовою. отже. Контрольними символами будуть. Інформаційні символи.
Для знаходження контрольних символів використовуємо контрольну матрицю (3.9) з попереднього прикладу.
Із системи (10)
Кодове слово матиме вигляд 1010101.
Припустимо, що при передачі виникла помилка, і ми прийняли невірну комбінацію: 101011 1 (виникла помилка в шостому розряді).
За допомогою системи перевірок (3.11) знаходимо значення розрядів синдрому:
Синдром вказує на те, що в шостому розряді прийнятої комбінації сталася помилка ().
Якби нам знадобилося побудувати код і для перевірки подвійних помилок, то необхідно було б ввести ще один додатковий нульовий розряд:
Отримаємо код 01010101.
Нехай при передачі і виникненні помилки код буде мати вигляд 0101011 1.
Перевірка в цьому випадку показала б, що синдром дорівнює 110, а перевірка всієї комбінації на парність = 0 + 1 + 0 + 1 + 0 + 1 + 1 + 1 = 1. Це вказує на одиночну помилку. Допускається автоматичне виправлення помилки.
Існує наступний алгоритм декодування коду Хеммінга з кодовою відстанню (табл. 3.2).
Таблиця 3.2
Для нечіткого пошуку можуть бути використані широко відомі алгоритми та коди Хеммінга. Коди Хеммінга давно і успішно застосовуються при кодуванні і декодуванні інформації, дозволяючи успішно відновити втрачену пре передачі інформацію.
Мережі Хеммінга так само активно використовуються для оптичного розпізнавання символів (OСR).
Однак алгоритми Хемминга можуть бути застосовані не тільки в теорії кодування інформації, а й в питаннях інформаційного пошуку. Особливо ефективно коди Хеммінга працюють разом з апаратом нечіткої логіки.
Коди Хеммінга - найпростіші лінійні коди з мінімальним відстанню 3, тобто здатні виправити одну помилку [2].
Мережі Хеммінга являють собою одну з різновидів нейронних мереж. Принцип роботи мереж Хеммінга заснований на визначенні відстані Хеммінга між об'єктами і знаходженні найбільш близького.
Алгоритми Хемминга в своїй роботі використовують лінійний код, який в порівнянні з іншими кодами, дозволяють реалізовувати більш ефективні алгоритми кодування і декодування інформації.
У процесі пошуку і видачі інформації неминуче виникають помилки, тому контроль цілісності даних і виправлення помилок - важливі завдання на багатьох рівнях роботи з інформацією.
Актуальною є задача розробки системи нечіткого пошуку, яка може знаходити слово в списку, навіть якщо воно спотворене або містить помилки і пропущені символи.
Для виявлення помилок в мережах Хемминга використовують коди виявлення помилок, для виправлення - коригувальні коди.
Для цього під час запису і передачі інформації в корисні дані додають спеціальним чином структуровану надлишкову інформацію, а при читанні (прийомі) її використовують для того, щоб виявити або виправити помилки. Природно, що число помилок, яке можна виправити, обмежена і залежить від конкретного застосовуваного коду.
Таким чином, алгоритми Хеммінга можуть бути використані для пошуку слів, які в початковому запиті набрані з помилками.
Припустимо у нас на вході є словник і необхідно знайти шукане слово в цьому словнику, навіть якщо воно було набрано з помилкою. Для цього потрібно спочатку продумати і розробити систему кодування символьної інформації в вектора. Задамо для кожного символу його бітову маску:
При кодуванні символьної інформації необхідно враховувати джерело для отримання даної інформації. Якщо, припустимо, ми вводимо символи використовую клавіатуру, то доцільно буде задавати коди символів таким чином, що б у символів, розташованих поруч на клавіатурі, були б і близькі по Хеммінг коди. Якщо ж джерелом є програма розпізнавання образів (OCR), то близькі коди повинні бути у схожих за написанням символів. Після кодування, таким чином, подаємо отримані вектора на вхід нейронної мережі.
Однак необхідно враховувати одну особливість мереж Хеммінга. Якщо при написанні була помилка або навіть дві, то алгоритм працює добре, але якщо був пропущений символ або доданий зайвий, то Хемінгово відстань може виявитися занадто великим. Для того, щоб усунути цей недолік, ми будемо подавати на вхід, як саме шукане слово, так і це ж слово, виключаючи по черзі по одному символу в кожній позиції і додаючи по одній букві в кожну позицію. Такий підхід дозволить знайти практично всі випадки помилок - помилка, пропуск символу, зайвий символ.
Слід зазначити, що, не дивлячись на велику ефективність кодів Хеммінга, вони не позбавлені певних недоліків. Лінійні коди, як правило, добре справляються з рідкісними і великими помилками [4]. Однак їх ефективність при порівняно частотних, але невеликих помилках менш висока.
Завдяки лінійності для запам'ятовування або перерахування всіх кодових слів досить зберігати в пам'яті кодера або декодера істотно меншу їх частину, а саме тільки ті слова, які утворюють базис відповідного лінійного простору. Це істотно спрощує реалізацію пристроїв кодування та декодування і робить лінійні коди вельми привабливими з точки зору практичних завдань інформаційного пошуку.
Розміщено на Allbest.ru