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

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

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

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

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

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

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

Оптимальний надлишковий код відрізняється тим, що будь-яких ${\displaystyle k}$ з ${\displaystyle n}$ символів кодового слова достатньо для відновлення вихідного повідомлення^[7], тобто вони мають оптимальну ефективність прийому^[5][8].

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

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

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

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

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

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

Лінійний код

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклади

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

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

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

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

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