Коди, що виправляють помилки
Коди, що виправляють помилки (коди з корекцією помилок. Коригувальні коди. Перешкодостійкі коди) - коди, службовці для виправлення помилок, що виникають при передачі інформації під впливом перешкод, а також при її зберіганні.
Для цього під час запису (передачі) в корисні дані додають спеціальним чином структуровану надлишкову інформацію, а при читанні (прийомі) її використовують для того, щоб виявити і виправити помилки. Природно, що число помилок, яке можна виправити, обмежена і залежить від конкретного застосовуваного коду.
З кодами, виправляють помилки тісно пов'язані коди виявлення помилок. На відміну від перших, останні можуть тільки встановити факт наявності помилки в переданих даних, але не виправити її.
Насправді, використовувані коди виявлення помилок належать до тих же класів кодів, що і коди, що виправляють помилки. Більш того, будь-який код, що виправляє помилки, може бути використаний і для виявлення помилок. Тому має сенс розглядати ці поняття разом.
За способом роботи з даними коди, що виправляють помилки діляться на блокові. ділять інформацію на фрагменти постійної довжини і обробні кожен з них окремо, і згорткові. що працюють з даними як з безперервним потоком.
Як приклад найпростішого блокового коду можна вказати код-повторення. при якому кожен символ або блок інформації передається кілька разів. Однак, такий код має вкрай низькою ефективністю (див. Нижче).
блокові коди
Нехай кодується інформація ділиться на фрагменти довжиною k біт, які перетворюються в кодові слова довжиною n біт. Тоді відповідний блоковий код зазвичай позначають (n, k). При цьому число \ frac називається швидкістю коду.
Якщо вихідні k біт код залишає незмінними, і додає n - kпроверочних. такий код називається систематичним. інакше несистематическим.
Задати блоковий код можна по-різному, в тому числі таблицею, де кожної сукупності з k інформаційних біт зіставляється n біт кодового слова. Однак, хороший код повинен задовольняти, як мінімум, наступними критеріями:
- здатність виправляти якомога більше число помилок,
- якомога менша надмірність,
- простота кодування і декодування.
Неважко бачити, що наведені вимоги суперечать один одному. Саме тому існує велика кількість кодів, кожен з яких придатний для свого кола завдань.
Практично всі використовувані коди є лінійними. Це пов'язано з тим, що нелінійні коди значно складніше досліджувати, і для них важко забезпечити прийнятну легкість кодування і декодування.
Лінійні коди загального вигляду
Лінійний блоковий код - такий код, що безліч його кодових слів утворює k -мірним лінійне підпростір (назвемо його C) в n-мірному лінійному просторі. изоморфное простору k -бітний векторів.
Це означає, що операція кодування відповідає множенню вихідного k -бітний вектора на невироджених матрицю G. звану породжує матрицею.
Нехай C ^ - ортогональное підпростір по відношенню до C. а H - матриця, що задає базис цього підпростору. Тоді для будь-якого вектора \ overrightarrow \ in C справедливо:
Мінімальна відстань і коригуюча здатність
Відстанню Хеммінга (метрикою Хемминга) між двома кодовими словами \ overrightarrow і \ overrightarrow називається кількість відмінних біт на відповідних позиціях, тобто число «одиниць» в векторі \ overrightarrow \ oplus \ overrightarrow.
Мінімальна відстань Хеммінга (dmin) є важливою характеристикою лінійного блокового коду. Вона визначає іншу, не менш важливу характеристику - коригувальну здатність:
- t = \ mathcal \ frac-1> \ mathcal. тут кутові дужки позначають округлення «вниз».
Коригувальна здатність визначає, скільки помилок код може гарантовано виправити.
Пояснимо на прикладі. Припустимо, що є два кодових слова A і B, відстань Хеммінга між ними дорівнює 3. Якщо було передано слово A, і канал вніс помилку в одному бите, вона може бути виправлена, так як навіть в цьому випадку прийняте слово ближче до кодовому слову A , ніж B. Але якщо каналом були внесені помилки в двох бітах, декодер може порахувати, що було передано слово B.
коди Хеммінга
Коди Хеммінга - найпростіші лінійні коди з мінімальним відстанню 3, тобто здатні виправити одну помилку. Код Хеммінга може бути представлений в такому вигляді, що синдром
- \ Overrightarrow = \ overrightarrow H ^ T. де \ overrightarrow - прийнятий вектор,
буде дорівнює номеру позиції, в якій сталася помилка. Це властивість дозволяє зробити декодування дуже простим.
Загальний метод декодування лінійних кодів
Будь-код (в тому числі нелінійний) можна декодувати за допомогою звичайної таблиці, де кожному значенню прийнятого слова \ overrightarrow відповідає найбільш ймовірне передане слово \ overrightarrow. Однак, даний метод вимагає застосування величезних таблиць вже для кодових слів порівняно невеликої довжини.
Для лінійних кодів цей метод можна істотно спростити. При цьому для кожного прийнятого вектора \ overrightarrow обчислюється синдром \ overrightarrow = \ overrightarrow H ^ T. Оскільки \ overrightarrow = \ overrightarrow + \ overrightarrow. де \ overrightarrow - кодове слово, а \ overrightarrow - вектор помилки, то \ overrightarrow = \ overrightarrow H ^ T. Потім за допомогою таблиці по синдрому визначається вектор помилки, за допомогою якого визначається передане кодове слово. При цьому таблиця виходить набагато менше, ніж при використанні попереднього методу.
Лінійні циклічні коди
Незважаючи на те, що декодування лінійних кодів вже значно простіше декодування більшості нелінійних, для більшості кодів цей процес все ще досить складний. Циклічні коди, крім більш простого декодування, володіють і іншими важливими властивостями.
Циклічним кодом є лінійний код, що володіє наступною властивістю: якщо \ overrightarrow є кодовим словом, то його циклічна перестановка також є кодовим словом.
Слова циклічного коду зручно представляти у вигляді многочленів. Наприклад, кодове слово \ overrightarrow = (v_0, v_1. V_) представляється у вигляді полінома v (x) = v0 + v1x +. + Vn - 1xn - 1. При цьому циклічний зсув кодового слова еквівалентний множенню многочлена на x по модулю xn - 1.
Надалі, якщо не вказано інше, ми будемо вважати, що циклічний код є двійковим. тобто v0, v1 ... можуть приймати значення 0 або 1.
породжує поліном
Можна показати, що все кодові слова конкретного циклічного коду кратні певному породжує поліномуg (x). Породжує поліном є дільником xn - 1.
За допомогою породжує полінома здійснюється кодування циклічним кодом. Зокрема:
Коди CRC (cyclic redundancy check - циклічна надлишкова перевірка) є систематичними кодами, призначеними не для виправлення помилок, а для їх виявлення. Вони використовують спосіб систематичного кодування, викладений вище: «контрольна сума» обчислюється шляхом ділення xn - ku (x) на g (x). З огляду на те, що виправлення помилок не потрібно, перевірка правильності передачі може проводитися точно так же.
Таким чином, вид полінома g (x) задає конкретний код CRC. Приклади найбільш популярних поліномів:
Коди Боуза-Чоудхурі-хоквінгема (БЧХ) є підкласом довічних циклічних кодів. Їх відмітна властивість - можливість побудови коду БЧХ з мінімальним відстанню не менш заданого. Це важливо, тому що, взагалі кажучи, визначення мінімального відстані коду є дуже складне завдання.
Математично побудова кодів БЧХ та їх декодування використовують розкладання породжує полінома g (x) на множники в полі Галуа.
Коди Ріда-Соломона
Коди Ріда-Соломона (РС-коди) фактично є недвійковий кодами БЧХ, тобто елементи кодового вектора не є бітами, а групами бітів. Дуже поширені коди Ріда-Соломона, що працюють з байтами (октетами).
Переваги та недоліки блокових кодів
Хоча блокові коди, як правило, добре справляються з рідкісними, але великими пачками помилок. їх ефективність при частих, але невеликих помилках (наприклад, в каналі з білим шумом), менш висока.
згорткові коди
Згорткові коди, на відміну від блокових, не ділять інформацію на фрагменти і працюють з нею як із суцільним потоком даних.
Згорткові коди. як правило, породжуються дискретної лінійної інваріантної в часі системою. Тому, на відміну від більшості блокових кодів, сверточное кодування - дуже проста операція, чого не можна сказати про декодуванні.
Кодування сверточних кодом проводиться за допомогою регістра зсуву, відводи від якого підсумовуються по модулю два. Таких сум може бути дві (найчастіше) або більше.
Декодування сверточних кодів, як правило, проводиться за алгоритмом Вітербо, який намагається відновити передану послідовність згідно з критерієм максимальної правдоподібності.
Переваги та недоліки сверточних кодів
Згорткові коди ефективно працюють в каналі з білим шумом, але погано справляються з пачками помилок. Більш того, якщо декодер помиляється, на його виході завжди виникає пачка помилок.
Каскадне кодування. Турбо-коди
Переваги різних способів кодування можна об'єднати, застосувавши каскадне кодування. При цьому інформація спочатку кодується одним кодом, а потім іншим, в результаті виходить код-твір.
Наприклад, популярною є наступна конструкція: дані кодуються кодом Ріда-Соломона, потім перемежовуються (при цьому символи, розташовані близько, поміщаються далеко один від одного) і кодуються сверточних кодом. На приймачі спочатку декодується сверточних код, потім здійснюється зворотне перемежение (при цьому пачки помилок на виході сверточного декодера потрапляють в різні кодові слова коду Ріда-Соломона), і потім здійснюється декодування коду Ріда-Соломона.
Деякі коди-твори спеціально сконструйовані для ітеративного декодування. при якому декодування здійснюється в кілька проходів, кожен з яких використовує інформацію від попереднього. Такі коди називаються «турбо-кодами» і дозволяють домогтися більшої ефективності, однак, їх декодування вимагає великих ресурсів.
Оцінка ефективності кодів
Ефективність кодів визначається кількістю помилок, які той може виправити, кількістю надлишкової інформації, додавання якої потрібно, а також складністю реалізації кодування і декодування (як апаратної, так і у вигляді програми для ЕОМ).
Кордон Хеммінга і досконалі коди
Нехай є двійковий блоковий (n, k) код коректуючу здатністю t. Тоді справедливо нерівність (зване кордоном Хемминга):
Коди, що задовольняють цій кордоні з рівністю, називаються досконалими. До досконалим кодами відносяться, наприклад, коди Хеммінга. Часто застосовуються на практиці коди з великою коректує здатністю (такі, як коди Ріда-Соломона) не є досконалими.
енергетичний виграш
Оскільки завадостійке кодування дозволяє виправляти помилки, при його застосуванні потужність передавача можна знизити, залишаючи швидкість передачі інформації незмінною. Енергетичний виграш визначається як різниця величин \ frac при наявності і відсутності коду. Тут Eb - енергія біта (потужність сигналу, віднесена до швидкості передачі інформації), а N0 - спектральна щільність потужності шуму.
Застосування кодів, що виправляють помилки
Коди, що виправляють помилки, застосовуються:
Коди, що виявляють помилки, застосовуються в мережевих протоколах різних рівнів.