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

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

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

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

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

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

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

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

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

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

Лінійний код

Важливим підкласом надлишкового коду є лінійний код. Його назва пов'язана з тим, що він може бути проаналізований за допомогою лінійної алгебри. Нехай ${\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}}}$, доступних на приймачі.

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

Приклад: Несправна електронна пошта (англ. 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 повідомлення (два від Аліси і два підтвердження від Боба).

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

Наведена вище лінійна конструкція може бути узагальнена до поліноміальної інтерполяції. У такому разі крапки тепер обчислюються над кінцевим полем ${\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}$ символів.

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

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

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

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

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

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

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

Приклади

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

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

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

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

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

Примітки

1. Шинкаренко К.В., Кориков A.M. Помехоустойчивое кодирование мультимедиа данных в компьютерных сетях // Известия Томского политехнического университета [Известия ТПУ] : журнал. — 2008. — Т. 313, № 5, Число 29 (сентябрь). — С. 37—41. — ISSN 1684-8519. з джерела 31 січня 2022. Процитовано 31 січня 2022.
2. Шинкаренко Константин Всеволодович, Кориков Анатолий Михайлович. Исследование эффективности помехоустойчивых кодов Лаби // Доклады Томского государственного университета систем управления и радиоэлектроники : журнал. — 2009. — 16 июня. — С. 185-192. з джерела 11 грудня 2019. Процитовано 31 січня 2022.
3. Katina Kralevska. Applied Erasure Coding in Networks and Distributed Storage // ResearchGate : thesis for the degree of Philosophiae Doctor. — 2018. — Март. — P. 7. з джерела 31 січня 2022. Процитовано 31 січня 2022.
4. J.S. Plank ; A.L. Buchsbaum ; R.L. Collins ; M.G. Thomason. Small parity-check erasure codes - exploration and observations // 2005 International Conference on Dependable Systems and Networks (DSN'05) : conference. — 2005. — . — Июль. — P. 2. — ISSN 1530-0889. з джерела 31 січня 2022. Процитовано 31 січня 2022.
5. Dave K. Kythe, Prem K. Kythe. Algebraic and Stochastic Coding Theory. — 1-е изд. — CRC Press, 2012. — С. 377—378. — .
6. Alexandros G. Dimakis, P. Brighten Godfrey, Martin J. Wainwright and Kannan Ramchandran. Network Coding for Distributed Storage Systems // IEEE Transactions on Information Theory : journal. — 2007. — Vol. 56, no. 9, (Август). — P. 4539—4551. — ISSN 0018-9448. — DOI:10.1109/TIT.2010.2054295. з джерела 31 січня 2022. Процитовано 31 січня 2022.
7. N. Alon ; J. Edmonds ; M. Luby. Linear time erasure codes with nearly optimal recovery // Proceedings of IEEE 36th Annual Foundations of Computer Science : symposium. — 1995. — . — Октябрь. — P. 1. — ISSN 0272-5428. — DOI:10.1109/SFCS.1995.492581. з джерела 31 січня 2022. Процитовано 31 січня 2022.
8. Petar Maymounkov, David Mazi`eres. Rateless Codes And Big Downloads // 2nd International Workshop on Peer-to-Peer Systems : conference. — 2004. — Vol. 2735 (Август). — P. 2. — DOI:10.1007/978-3-540-45172-3_23. з джерела 31 січня 2022. Процитовано 31 січня 2022.
9. Luigi Rizzo. Effective Erasure Codes for Reliable Computer Communication Protocols // ACM SIGCOMM Computer Communication Review : newsletter. — 1997. — Vol. 27, no. 2 (Апрель). — P. 24—36. — DOI:10.1145/263876.263881. з джерела 13 березня 2022. Процитовано 31 січня 2022.
10. Hamid Jafarkhani, Mahdi Hajiaghayi (22.10.2015). (PDF). COST-EFFICIENT REPAIR FOR STORAGE SYSTEMS USING PROGRESSIVE ENGAGEMENT. The Regents of the University of California,Oakland,CA (US). с. 1. Архів оригіналу (PDF) за 4 травня 2022. Процитовано 31 січня 2022.
11. Dave K.Kythe, Prem K. Kythe. Algebraic and Stochastic Coding Theory. — 1-е изд. — CRC Press,, 2012. — С. 380—381. — .

Література

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