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

Розглянемо випадок, коли ${\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}}$ .

Більш складні комбінації шуканих і отримуваних значень є Граф Таннера[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].

У випадку, коли ${\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].