Стирающий код: различия между версиями

[непроверенная версия]

Содержимое удалено Содержимое добавлено

Линейный

Версия от 13:19, 7 декабря 2019

В теории кодирования удаляющий (избыточный) код (англ. Erasure code) — это избыточный код^[1], использующий в качестве избыточной информации исходные данные.^[2] Такой код позволяет бороться с утечками (потерей) данных при передаче по каналам связи или работе с памятью. Обычно он используется, когда точная позиция потерянных данных известна априори^[3].

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

Удаляющий код преобразует сообщение из $k$ символов в более длинное сообщение (кодовое слово) из $n$ символов, так что исходное сообщение может быть восстановлено по $k'$ любым символам. Такой код называется $(n,k)$ кодом, выражение $r=k/n$ - кодовой долей^[4], выражение $k'/k$ - эффективностью приема^[1]^[5].

В отличие от кодов коррекции ошибок (например, прямой коррекции ошибок), которые обычно используются на нижних уровнях стека протоколов каналов передачи и хранения информации, удаляющий код нашел широкое применение на верхних уровнях^[3].

Оптимальный удаляющий код

Оптимальный удаляющий код обладает тем свойством, что любых $k$ из $n$ символов кодового слова достаточно для восстановления исходного сообщения, то есть они имеют оптимальную эффективность приема^[6].

Простейшая реализация

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

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

.

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

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

.

Более сложные комбинации искомых и получаемых значений представляют собой Граф Таннера^[4].

Линейный код

Интересным подклассом удаляющего кода является линейный код. Его название связано с тем, что он может быть проанализирован с помощью линейной алгебры. Пусть $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}}$ , доступных на приемнике^[2].

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

Пример: Err-mail (k = 2)

В простом случае, когда $k=2$ , избыточные символы могут быть созданы путем выбора разных точек вдоль линии между двумя исходными символами. Это показано на простом примере, называемом err-mail:

Алиса хочет отправить свой телефонный номер (555629) Бобу, используя err-mail. Err-mail работает так же, как e-mail (электронная почта), за следующим исключением:

Около половины всех сообщений теряются.
Сообщения длиннее 5 символов запрещены.
Это очень дорого.

Вместо того, чтобы спросить у Боба подтверждения сообщения, которое она отправила, Алиса придумывает следующую схему:

Она разбивает свой телефонный номер на две части $a=555,b=629$ и отправляет 2 сообщения Бобу — "A=555" и "B=629"
Она строит линейную функцию $f(i)=a+(b-a)(i-1)$ , в этом примере $f(i)=555+74(i-1)$ . Таким образом $f(1)=555$ и $f(2)=629$ .
Она считает значения $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".

Боб может восстановить телефонный номер Алисы с помощью $a$ и $b$ , используя значения $f(4)$ и $f(5)$ , которые он получил. Боб может проделать эту операцию, используя любые два сообщения err-mail. Значит, в этом примере кодовая доля составляет 40%. Заметим, что Алиса не может закодировать свой номер телефона только в одном сообщении err-mail, так как он состоит из 6 символов, а максимальная длина одного сообщения err-mail — 5 символов. Если бы она отправляла свой номер телефона по частям, запрашивая подтверждения каждой части от Боба, то было бы отправлено минимум 4 сообщения (два от Алисы и два подтверждения от Боба). Таким образом, удаляющий код, представленный в этом примере, довольно экономичный^[7].

Общий случай

Приведенная выше линейная конструкция может быть обобщена до полиномиальной интерполяции. Кроме того, точки теперь вычисляются по конечному полю^[8].

Сначала мы выбираем конечное поле $F$ с порядком не менее $n$ (обычно степень 2). Отправитель нумерует символы данных от $0$ до $k-1$ и отправляет их. Затем он строит интерполяционный многочлен Лагранжа $p(x)$ степени $k$ , так что $p(i)$ равен $i$ -ому символу данных. Потом он отправляет $p(k),\ldots ,p(n-1)$ . Получатель теперь также может использовать полиномиальную интерполяцию для восстановления потерянных пакетов, если он успешно принял $k$ сообщений. Если порядок полинома $F$ меньше $2^{b}$ , где $b$ - число бит в символе, то можно использовать несколько полиномов.

Реализация в реальном мире

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

Почти оптимальный удаляющий код

Почти оптимальный удаляющий код требует $(1+\varepsilon )k$ символов, чтобы восстановить сообщение (где $\varepsilon >0$ ). Величина $\varepsilon$ может быть уменьшена за счет дополнительного времени работы процессора. При использовании таких кодов необходимо решить, что предпочтительнее: сложность вычислений или возможность коррекции сообщений. В 2004 году существовал только один почти оптимальный удаляющий код с линейным временем - код Торнадо^[6].

Удаляющий код для передачи медиа-информации в режиме реального времени

На качество передачи аудио и видео данных в режиме реального времени влияет по большой мере не число общих потерь в канале связи, а так называемые "взрывные потери" - те, что произошли последовательно. Согласно исследованиям, проведенным с распределениями Бернулли и Гильберта-Эллиота для потерь при передаче, ожидаемая величина длины последовательных потерь при использовании удаляющего кода выше, чем без него^[9].

Таким образом, удаляющий код не всегда помогает бороться с потерями, а, наоборот, иногда увеличивает их.

Примеры

Здесь приведены некоторые примеры различных кодов:

Почти оптимальные удаляющие коды

Код с малой плотностью проверок на чётность

Оптимальные удаляющие коды

Ссылки

↑ ¹ ² Университет ИТМО. Избыточное кодирование, код Хэмминга (неопр.). Университет ИТМО. Университет ИТМО (29 октября 2015).
↑ ¹ ² 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.
↑ ¹ ² Katina Kralevska. [https://arxiv.org/pdf/1803.01358.pdf Applied Erasure Coding in Networks and Distributed Storage] (англ.) // ResearchGate : Thesis for the degree of Philosophiae Doctor. — 2018. — Март. — P. 7.
↑ ¹ ² 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. — 25 июль. — P. 2. — ISSN 1530-0889.
↑ Alexandros G. Dimakis, P. Brighten Godfrey, Martin J. Wainwright and Kannan Ramchandran. [https://ieeexplore.ieee.org/document/5550492 Network Coding for Distributed Storage Systems] (англ.) // IEEE Transactions on Information Theory : journal. — 2007. — 16 Август (vol. 56, no. 9). — P. 4539-4551. — ISSN 0018-9448. — doi:10.1109/TIT.2010.2054295.
↑ ¹ ² 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.
↑ Hamid Jafarkhani, Mahdi Hajiaghayi. United States Patent Application Publication (неопр.). COST-EFFICIENT REPAIR FOR STORAGE SYSTEMS USING PROGRESSIVE ENGAGEMENT 1. The Regents of the University of California,Oakland,CA (US) (22 октября 2015).
↑ Jonathan Detchart. Improving the coding speed of erasure codes with polynomial ring transforms (англ.). — 2018. — 2 октября. — С. 1.
↑ Bobak McCann, Kerry Fendick. The Effect of Erasure Coding on the Burstiness of Packet Loss. — 2019. — Октябрь. — С. 6.

[ITMO-1] ¹ ² Университет ИТМО. Избыточное кодирование, код Хэмминга (неопр.). Университет ИТМО. Университет ИТМО (29 октября 2015).

[Luigi-2] ¹ ² 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.

[kralevska-3] ¹ ² Katina Kralevska. [https://arxiv.org/pdf/1803.01358.pdf Applied Erasure Coding in Networks and Distributed Storage] (англ.) // ResearchGate : Thesis for the degree of Philosophiae Doctor. — 2018. — Март. — P. 7.

[parityCheck-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. — 25 июль. — P. 2. — ISSN 1530-0889.

[5] Alexandros G. Dimakis, P. Brighten Godfrey, Martin J. Wainwright and Kannan Ramchandran. [https://ieeexplore.ieee.org/document/5550492 Network Coding for Distributed Storage Systems] (англ.) // IEEE Transactions on Information Theory : journal. — 2007. — 16 Август (vol. 56, no. 9). — P. 4539-4551. — ISSN 0018-9448. — doi:10.1109/TIT.2010.2054295.

[:0-6] ¹ ² 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.

[7] Hamid Jafarkhani, Mahdi Hajiaghayi. United States Patent Application Publication (неопр.). COST-EFFICIENT REPAIR FOR STORAGE SYSTEMS USING PROGRESSIVE ENGAGEMENT 1. The Regents of the University of California,Oakland,CA (US) (22 октября 2015).

[8] Jonathan Detchart. Improving the coding speed of erasure codes with polynomial ring transforms (англ.). — 2018. — 2 октября. — С. 1.

[9] Bobak McCann, Kerry Fendick. The Effect of Erasure Coding on the Burstiness of Packet Loss. — 2019. — Октябрь. — С. 6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Строка 10: / Строка 10: @@
 == Оптимальный удаляющий код ==
-Оптимальный удаляющий код обладает тем свойством, что любых <math>k</math> из <math>n</math> символов кодового слова достаточно для восстановления исходного сообщения, то есть они имеют оптимальную эффективность приема.<ref name="euro">{{cite web|url=https://www.snia.org/sites/default/files/SDCIndia/2017/Slides/Prof%20Kumar%20-%20IISc%20-%20Erasure%20codes.pdf|title=Codes for Big Data: Erasure Coding for Distributed Storage|publisher=P. Vijay Kumar|accessdate=2019-11-08}}</ref>???
+Оптимальный удаляющий код обладает тем свойством, что любых <math>k</math> из <math>n</math> символов кодового слова достаточно для восстановления исходного сообщения, то есть они имеют оптимальную эффективность приема<ref name=":0">{{Статья|ссылка=https://www.researchgate.net/publication/2942086_Rateless_Codes_And_Big_Downloads|автор=Petar Maymounkov, David Mazi`eres|заглавие=Rateless Codes And Big Downloads|год=2004|язык=en|издание=2nd International Workshop on Peer-to-Peer Systems|тип=conference|месяц=Август|число=|том=2735|номер=|страницы=2|issn=|doi=10.1007/978-3-540-45172-3_23}}</ref>.
 === Простейшая реализация ===
@@ Строка 24: / Строка 24: @@
 === Линейный код ===
-Интересным подклассом удаляющего кода является линейный код. Его название связано с тем, что он может быть проанализирован с помощью [[Линейная алгебра|линейной алгебры.]] Пусть <math>x = x_0 \dots x_{k-1}</math> - исходные данные, <math>G</math> - матрица размера <math>n \times k</math>, тогда закодированные данные  <math>(n, k)</math>- кода могут быть представлены как  <math>\vec{y}=G\vec{x}</math>. Предположим, что приемник получил <math>k</math> компонент вектора <math>\vec{y}</math>, тогда исходные данные могут быть восстановлены с помощью <math>k</math> уравнений, связанных с известными компонентами вектора <math>\vec{y}</math>. Пусть матрица <math>G'</math> размера <math>k \times k</math> соответствует этой системе уравнений. Восстановление возможно, если все эти уравнения линейно независимые и, в общем случае, это означает, что любая матрица размера <math>k \times k</math> обратима.  Матрица <math>G</math> называется генерирующей матрицей кода, так как любой допустимый  <math>\vec{y}</math> является линейной комбинацией столбцов матрицы <math>G</math>. Поскольку ее ранг равен <math>k</math>, любое подмножество из <math>k</math> закодированных элементов должно содержать информацию о всех <math>k</math> исходных данных. Для получения исходных данных необходимо решить линейную систему: <math>\vec{y'}=G'\vec{x}</math>, где <math>\vec{y'}</math> - подмножество из <math>k</math> элементов вектора  <math>\vec{y}</math>, доступных на приемнике.<ref name="Luigi">{{Статья|ссылка=http://pages.cs.wisc.edu/~suman/courses/740/papers/rizzo97ccr.pdf|автор=Luigi Rizzo|заглавие=Effective Erasure Codes for Reliable Computer Communication Protocols|год=1997|язык=en|издание=ACM SIGCOMM Computer Communication Review|тип=Newsletter|месяц=Апрель|число=|том=27|номер=2|страницы=24-36|issn=|doi=10.1145/263876.263881}}</ref>
+Интересным подклассом удаляющего кода является линейный код. Его название связано с тем, что он может быть проанализирован с помощью [[Линейная алгебра|линейной алгебры.]] Пусть <math>x = x_0 \dots x_{k-1}</math> - исходные данные, <math>G</math> - матрица размера <math>n \times k</math>, тогда закодированные данные  <math>(n, k)</math>- кода могут быть представлены как  <math>\vec{y}=G\vec{x}</math>. Предположим, что приемник получил <math>k</math> компонент вектора <math>\vec{y}</math>, тогда исходные данные могут быть восстановлены с помощью <math>k</math> уравнений, связанных с известными компонентами вектора <math>\vec{y}</math>. Пусть матрица <math>G'</math> размера <math>k \times k</math> соответствует этой системе уравнений. Восстановление возможно, если все эти уравнения линейно независимые и, в общем случае, это означает, что любая матрица размера <math>k \times k</math> обратима.  Матрица <math>G</math> называется генерирующей матрицей кода, так как любой допустимый  <math>\vec{y}</math> является линейной комбинацией столбцов матрицы <math>G</math>. Поскольку ее ранг равен <math>k</math>, любое подмножество из <math>k</math> закодированных элементов должно содержать информацию о всех <math>k</math> исходных данных. Для получения исходных данных необходимо решить линейную систему: <math>\vec{y'}=G'\vec{x}</math>, где <math>\vec{y'}</math> - подмножество из <math>k</math> элементов вектора  <math>\vec{y}</math>, доступных на приемнике<ref name="Luigi">{{Статья|ссылка=http://pages.cs.wisc.edu/~suman/courses/740/papers/rizzo97ccr.pdf|автор=Luigi Rizzo|заглавие=Effective Erasure Codes for Reliable Computer Communication Protocols|год=1997|язык=en|издание=ACM SIGCOMM Computer Communication Review|тип=Newsletter|месяц=Апрель|число=|том=27|номер=2|страницы=24-36|issn=|doi=10.1145/263876.263881}}</ref>.
 === Полиномиальная [[передискретизация]] ===
@@ Строка 56: / Строка 56: @@
 == Почти оптимальный удаляющий код ==
-Почти оптимальный удаляющий код требует <math>(1+\varepsilon)k</math> символов, чтобы восстановить сообщение (где <math>\varepsilon > 0</math>). Величина <math>\varepsilon</math> может быть уменьшена за счет дополнительного времени работы процессора. При использовании таких кодов необходимо решить, что предпочтительнее: сложность вычислений или возможность коррекции сообщений. Так, практические алгоритмы могут кодировать и декодировать данные с линейной временной сложностью.<ref>{{Статья|ссылка=https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6195814|автор=Ning Cao, Shucheng Yu, Zhenyu Yang, Wenjing Lou, Y. Thomas Hou|заглавие=LT Codes-based Secure and Reliable
+Почти оптимальный удаляющий код требует <math>(1+\varepsilon)k</math> символов, чтобы восстановить сообщение (где <math>\varepsilon > 0</math>). Величина <math>\varepsilon</math> может быть уменьшена за счет дополнительного времени работы процессора. При использовании таких кодов необходимо решить, что предпочтительнее: сложность вычислений или возможность коррекции сообщений. В 2004 году существовал только один почти оптимальный удаляющий код с линейным временем - код Торнадо<ref name=":0" />.
-Cloud Storage Service|год=2012|язык=English|издание=IEEE|тип=|месяц=|число=|том=|номер=|страницы=696|issn=}}</ref>
 == Удаляющий код для передачи медиа-информации в режиме реального времени ==
-На качество передачи аудио и видео данных в режиме реального времени влияет по большой мере не число общих потерь в канале связи, а так называемые "взрывные потери" - те, что произошли последовательно. Согласно исследованиям, проведенным с распределениями [[Распределение Бернулли|Бернулли]] и Гильберта-Эллиота для потерь при передаче, ожидаемая величина длины последовательных потерь при использовании удаляющего кода выше, чем без него.<ref>{{Статья|ссылка=https://www.researchgate.net/publication/337157804_The_Effect_of_Erasure_Coding_on_the_Burstiness_of_Packet_Loss|автор=Bobak McCann, Kerry Fendick|заглавие=The Effect of Erasure Coding on the Burstiness of Packet Loss|год=2019|язык=|издание=|тип=|месяц=Октябрь|число=|том=|номер=|страницы=6|issn=}}</ref>
+На качество передачи аудио и видео данных в режиме реального времени влияет по большой мере не число общих потерь в канале связи, а так называемые "взрывные потери" - те, что произошли последовательно. Согласно исследованиям, проведенным с распределениями [[Распределение Бернулли|Бернулли]] и Гильберта-Эллиота для потерь при передаче, ожидаемая величина длины последовательных потерь при использовании удаляющего кода выше, чем без него<ref>{{Статья|ссылка=https://www.researchgate.net/publication/337157804_The_Effect_of_Erasure_Coding_on_the_Burstiness_of_Packet_Loss|автор=Bobak McCann, Kerry Fendick|заглавие=The Effect of Erasure Coding on the Burstiness of Packet Loss|год=2019|язык=|издание=|тип=|месяц=Октябрь|число=|том=|номер=|страницы=6|issn=}}</ref>.
 Таким образом, удаляющий код не всегда помогает бороться с потерями, а, наоборот, иногда увеличивает их.

Стирающий код: различия между версиями

Версия от 13:19, 7 декабря 2019

Содержание

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