Кодування інформації із застосуванням кодів Ріда-Соломона
Кодування інформації із застосуванням кодів Ріда-Соломона
Коди Ріда-Соломона відносяться до недвійкових, блокових, завадових кодів і можуть використовуватися в області зберігання інформації для уникнення втрати пошкодженої інформації. Попереджаю, що даний підхід не буде раціональний у багатьох випадках, але дозволить реалізувати завадостійке кодування даних з відсотком відновлюваної інформації, що варіюється.
Працюючи з кодами Ріда-Соломона відсоток надлишкових символів вдвічі більше відновлюваного обсягу даних. Поясню на прикладі: якщо ми маємо послідовність із 10 символів і хочемо мати можливість відновити помилки у 3-ох із них (30% вихідної інформації), то нам потрібно зберігати 10+3*2=16 символів. Назвемо кожну змінну: n – 10 кількість інформаційних символів; f – 3, кількість символів, що відновлюються; g - 16, довжина закодованої послідовності. Таким чином, формулу можна записати так: g = n + f * 2. Дані ходи компактніші за коди Хемінга на 1 символ.
Для роботи з інформацією при кодуванні та декодуванні даних усі арифметичніоперації виконуються на полях Галуа. Застосовується так звана поліноміальна арифметика чи арифметика полів Галуа. Таким чином, результат будь-якої операції є елементом даного поля. Конкретне поле Галуа складається із фіксованого діапазону чисел. Характеристикою поля називають деяке просте число p. порядок поля, тобто. кількість його елементів є деяким натуральним ступенем характеристики pm, де m N. При m=1 поле називається простим. У випадках, коли m>1, для утворення поля необхідний ще породжує поліном ступеня m, таке поле називається розширеним. GF(p m ) - Позначення поля Галуа.
p align="justify"> Для роботи з цифровими даними природно використовувати p = 2 в якості характеристики поля. При m=1 елементом кодової послідовності буде біт, при m=8 – 8 біт, тобто байт. Власне коди Ріда-Соломона працюють із байтами і є найпоширенішими.
Для зручності підрахунків наведу 2 таблиці зі статті, присвяченої полям Галуа.
Таблиця множення
Таблиця ступенів
Перед початком кодування визначилися з необхідним полем GF(q), де q=p m . Довжина кодової послідовності має бути q-1. Таким чином, у нашому випадку з GF(8) кодова послідовність складається з 7 елементів. Далі потрібно з'ясувати, які елементи будуть інформаційними, а які перевірочні (надлишкові). На самому початку ми говорили про те, що кількість надлишкових символів має бути вдвічі більшою, ніж кількість помилкових символів, яку ми хочемо відновити. Якщо необхідно виправити дворазову помилку (t=2 – кратність помилки), то, відповідно, слід використовувати чотири перевірочні символи. Застосуємо це до нашого прикладу: із семи елементів для виправлення дворазовоїпомилки необхідні чотири надлишкові, а отже три інформаційні. Кодова послідовність виглядає так:
Хочу звернути увагу на той факт, що виправлення дворазової помилки в кодовій послідовності з семи елементів означає, що можна боротися з помилкою, ймовірність виникнення якої не більше ніж рош = 2/7 ≈ 0,29. Якщо ймовірність виникнення помилки вища, то потрібно збільшувати кількість перевірочних символів, інакше відновити спотворену інформацію все одно не вдасться.
Закодуємо послідовність С=( 4, 6, 7, 0, 0, 0, 0), чотири останні символи – перевірочні, рівні нулю.
Представимо нашу послідовність у вигляді полінома:
С(x)=4∙x 0 +6∙x 1 +7∙x 2 +0∙x 3 +0∙x 4 +0∙x 5 +0∙x 6 =4+6∙x+7∙x 2
Кодування здійснюється за допомогою зворотного дискретного перетворення Фур'є (>j), де z=2 – примітивний елемент поля.
Отримали закодовану послідовність: C'=(5,2,5,3,3,2,4). У вигляді полінома: С (x) = 5 x 0 +2 x 1 +5 x 2 +3 x 3 +3 x 4 +2 x 5 +4 x 6 .
Формула для декодування cj = C '(z-j).
При декодуванні отримали послідовність (4, 6, 7, 0, 0, 0, 0), що відповідає вихідній. Щоб перевірити, чи не відбулося спотворення інформації, достатньо подивитися на надлишкові символи. Якщо вони досі нульові, то помилки відсутні.
Помилка є іншою послідовністю, яка підсумовується із закодованою. Припустимо, вектор помилка має вигляд: f' =(0, 0, 5, 0, 3, 0, 0), тоді кодова послідовність з помилкою:
Спробуємо декодувати отримане кодове слово: Cf'=5∙x 0 +2∙x 1 +0∙x 2 +3∙x 3 +0∙x 4 +2∙x 5 +4∙x 6 =5+2∙x 1 +3∙x 3 +2∙x 5 +4∙x 6
Cf = (2, 5, 7, 6, 5, 5, 3) - декодована послідовність. Якбачимо, останні чотири елементи не дорівнюють нулю, що, власне, і свідчить про наявність помилки. Для виправлення помилки спочатку необхідно визначити позиції спотворених символів. Для цього необхідно обчислити поліном локаторів помилок, коріння якого вказують на позиції помилок. У матричному вигляді поліном локаторів помилок має вигляд L=[1, l1, l2, … lt]. Оскільки у прикладі хочемо виправити помилку кратності 2, то L=[1, l1, l2].
Випишемо останні чотири символи – синдром помилки: