Надлишковий код

Надлишковий код (англ. Erasure code) — в теорії кодування завадостійкий код, здатний відновити цілі пакети даних у разі їх втрати. Такий код дозволяє боротися з витоками даних під час передачі каналами зв'язку або роботі з пам'яттю. Зазвичай він використовується, коли точна позиція втрачених даних відома апріорі.

Графічне представлення процесів кодування та декодування

Принцип роботи

Надлишковий код перетворює повідомлення з $k$ символів у довше повідомлення (кодове слово) з $n$ символів так, що вихідне повідомлення може бути відновлено за $k'$ будь-якими символами. Такий код називається $(n,k)$ кодом, вираз $r=k/n$ — кодовою часткою, вираз $k'/k$ — ефективністю прийому.

Надлишковий код зазвичай використовується на верхніх рівнях стека протоколів каналів передачі та зберігання інформації.

Оптимальний надлишковий код

Оптимальний надлишковий код відрізняється тим, що будь-яких $k$ з $n$ символів кодового слова достатньо для відновлення вихідного повідомлення, тобто вони мають оптимальну ефективність прийому.

Перевірка парності

Розглянемо випадок, коли $n=k+1$. За допомогою набору з $k$ значень $\{v_{i}\}_{1\leq i\leq k}$ обчислюється контрольна сума та додається до $k$ вихідних значеннь:

$v_{k+1}=-\sum _{i=1}^{k}v_{i}$ .

Тепер у набір $\{v_{i}\}_{1\leq i\leq k+1}$ з $k+1$ значень включено контрольну суму. У разі втрати одного із значень $v_{e}$, його можна буде з легкістю відновити за допомогою підсумовування:

$v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}$ .

Більш складні комбінації шуканих і отримуваних значень є Граф Таннера.

Лінійний код

Важливим підкласом надлишкового коду є лінійний код. Його назва пов'язана з тим, що він може бути проаналізований за допомогою лінійної алгебри. Нехай $x=x_{0}\dots x_{k-1}$ — вихідні дані, $G$ — матриця розміру $n\times k$ тоді закодовані дані $(n,k)$ — коди можуть бути представлені як ${\vec {y}}=G{\vec {x}}$. Припустимо, що приймач отримав $k$ компонент вектора ${\vec {y}}$, тоді вихідні дані можуть бути відновлені за допомогою $k$ рівнянь, пов'язаних із відомими компонентами вектора ${\vec {y}}$. Нехай матриця $G'$ розміру $k\times k$ відповідає цій системі рівнянь. Відновлення можливе, якщо всі ці рівняння лінійно незалежні і в загальному випадку це означає, що будь-яка матриця розміру $k\times k$ оборотна. Матриця $G$ називається генеруючою матрицею коду, тому що будь-який допустимий ${\vec {y}}$ може бути отриманий як лінійна комбінація стовпців матриці $G$. Оскільки її ранг дорівнює $k$, то будь-яка підмножина з $k$ закодованих елементів має містити інформацію про всі $k$ вихідних даних. Для отримання вихідних даних необхідно вирішити лінійну систему: ${\vec {y'}}=G'{\vec {x}}$, де ${\vec {y'}}$ — підмножина з $k$ елементів вектора ${\vec {y}}$, доступних на приймачі.

Поліноміальна передискретизація

Приклад: Несправна електронна пошта (англ. Faulty e-mail)

У випадку, коли $k=2$ надлишкові символи можуть бути створені як проміжні точки на відрізку, що з'єднує два вихідні символи. Це показано на простому прикладі, який називається несправною електронною поштою:

Аліса порахувала значення $f(1)$ і $f(2)$

Аліса хоче надіслати свій телефонний номер (555629) Бобу, використовуючи несправну електронну пошту. Цей вид пошти працює так само, як звичайна електронна пошта, за таким винятком:

1. Близько половини всіх повідомлень губляться.
2. Повідомлення довші за 5 символів заборонені.
3. Це дуже дорого.

Замість того, щоб запитати у Боба підтвердження повідомлення, яке вона надіслала, Аліса вигадує таку схему:

1. Вона розбиває свій телефонний номер на дві частини $a=555,b=629$ і надсилає 2 повідомлення Бобу — «A = 555» і «B = 629»
2. Вона будує лінійну функцію $f(i)=a+(b-a)(i-1)$, у цьому прикладі $f(i)=555+74(i-1)$. Таким чином $f(1)=555$ і $f(2)=629$.
3. Вона вважає значення $f(3)=703,f(4)=777$ і $f(5)=851$, а потім відправляє три надлишкові повідомлення: «C=703», «D=777» і «E=851».

Боб знає, що вираз для $f(k)$ наступне $f(i)=a+(b-a)(i-1)$, де $a$ і $b$ — дві частини телефонного номера. Тепер припустимо, що Боб отримує «D = 777» і «E = 851».

Боб отримує два повідомлення з $f(4)$ і $f(5)$

Боб може відновити телефонний номер Аліси за допомогою $a$ і $b$, використовуючи значення $f(4)$ і $f(5)$, які він отримав. Більш того, він може це зробити, використовуючи два будь-які отримані повідомлення. Отже, у цьому прикладі кодова частка дорівнює 40 %. Зауважимо, що Аліса не може закодувати свій номер телефону лише в одному повідомленні такої пошти, оскільки він складається з 6 символів, а максимальна довжина одного повідомлення — 5 символів. Якби вона відправляла свій номер телефону частинами, запитуючи підтвердження кожної частини від Боба, то було б відправлено мінімум 4 повідомлення (два від Аліси і два підтвердження від Боба).

Загальний випадок

Наведена вище лінійна конструкція може бути узагальнена до поліноміальної інтерполяції. У такому разі крапки тепер обчислюються над кінцевим полем $\mathbb {F} _{2^{m}}$, де $m$ — число біт у символі. Відправник нумерує символи даних від $0$ до $k-1$ і посилає їх. Потім він будує, наприклад, інтерполяційний многочлен Лагранжа $p(x)$ степеня $k$, так що $p(i)$ дорівнює $i$ -ому символу даних. Потім він відправляє $p(k),\ldots ,p(n-1)$. За допомогою поліноміальної інтерполяції одержувач зможе відновити втрачені дані у разі, якщо він успішно прийняв $k$ символів.

Реалізація у реальному світі

Цей процес реалізований у Коді Ріда — Соломона з кодовими словами, сконструйованими над кінцевим полем при використанні визначника Вандермонда.

Майже оптимальний надлишковий код

Майже оптимальний надлишковий код вимагає $(1+\varepsilon )k$ символів, щоб відновити повідомлення (де $\varepsilon >0$). Величина $\varepsilon$ може бути зменшена за рахунок додаткового часу роботи процесора. При використанні таких кодів необхідно вирішити, що краще: складність обчислень або можливість корекції повідомлень. У 2004 році існував тільки один майже оптимальний надлишковий код з лінійним часом кодування та декодування — код Торнадо.

Застосування

Надлишкові коди застосовуються в:

• Reliable Multicast (наприклад, у групі з надійного мультимовлення IETF)
• 3GPP (MBMS та eMBMS (Multimedia Broadcast Multicast Service)
• однорангові мережі, наприклад, для вирішення проблеми передачі останнього блоку даних
• Розподільні сховища.

Приклади

Тут наведено деякі приклади різних кодів.

Майже оптимальні надлишкові коди

• Код із малою щільністю перевірок на парність

Оптимальні надлишкові коди

• Біт парності
• Код Ріда — Соломона

Література

• Dave K. Kythe, Prem K. Kythe. Algebraic and Stochastic Coding Theory. — 1-е изд. — CRC Press, 2012. — С. 375—395. — ISBN 978-1439881811.