Пакетный код исправления ошибок

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

Многие коды были разработаны для исправления случайных ошибок . Однако иногда каналы могут вносить ошибки, локализующиеся в течение короткого интервала времени. Такие ошибки возникают в пакете (так называемые пакетные ошибки ), поскольку они встречаются во многих последовательных битах. Примеры пакетных ошибок можно найти в различных носителях данных. Эти ошибки могут быть вызваны физическим повреждением, например царапиной на диске или ударом молнии в случае беспроводных каналов. Они не независимы; они имеют тенденцию быть пространственно сконцентрированными. Если в одном бите имеется ошибка, вполне вероятно, что соседние биты также могут быть повреждены. Методы, используемые для исправления случайных ошибок, неэффективны для исправления пакетных ошибок.

Определения

Взрыв длиной 5

Взрыв длиной ℓ

Скажи кодовое слово $C$ передается и принимается как $Y=C+E.$ Тогда вектор ошибки $E$ называется пакетом длины $\ell$ если ненулевые компоненты $E$ ограничиваются $\ell$ последовательные компоненты. Например, $E=(0{\textbf {1000011}}0)$ это взрыв длины $\ell =7.$

Хотя этого определения достаточно, чтобы описать, что такое пакетные ошибки, большинство инструментов, разработанных для исправления пакетных ошибок, основаны на циклических кодах. Это мотивирует наше следующее определение.

Циклический пакет длиной ℓ

Вектор ошибки $E$ называется циклическим пакетом ошибок длины $\ell$ если его ненулевые компоненты ограничены $\ell$ циклически последовательные компоненты. Например, ранее рассмотренный вектор ошибок $E=(010000110)$, представляет собой циклический пакет длины $\ell =5$, поскольку мы рассматриваем ошибку, начиная с позиции $6$ и заканчивается на позиции $1$. Обратите внимание, что индексы $0$-based, то есть первый элемент находится в позиции $0$.

В оставшейся части этой статьи мы будем использовать термин «пакет» для обозначения циклического пакета, если не указано иное.

Описание пакета

Часто бывает полезно иметь компактное определение пакета ошибок, охватывающее не только его длину, но также характер и местоположение такой ошибки. Мы определяем описание пакета как кортеж. $(P,L)$ где $P$ — шаблон ошибки (то есть строка символов, начинающаяся с первой ненулевой записи в шаблоне ошибки и заканчивающаяся последним ненулевым символом), и $L$ это место в кодовом слове, где можно найти пакет.

Например, пакетное описание шаблона ошибки $E=(010000110)$ является $D=(1000011,1)$. Обратите внимание, что такое описание не уникально, поскольку $D'=(11001,6)$ описывает ту же самую пакетную ошибку. В общем случае, если количество ненулевых компонентов в $E$ является $w$, затем $E$ будет иметь $w$ разные описания пакетов, каждое из которых начинается с другой ненулевой записи $E$. Чтобы устранить проблемы, возникающие из-за неоднозначности описаний пакетов, с помощью приведенной ниже теоремы, однако прежде чем делать это, нам сначала нужно дать определение.

Определение. Количество символов в заданном шаблоне ошибок $y,$ обозначается $\mathrm {length} (y).$

Теорема (единственность описаний пакетов) — Предположим , $E$ — вектор ошибок длины $n$ с двумя описаниями пакетов $(P_{1},L_{1})$ и $(P_{2},L_{2})$. Если $\mathrm {length} (P_{1})+\mathrm {length} (P_{2})\leqslant n+1,$ тогда два описания идентичны, то есть их компоненты эквивалентны.

Доказательство

Позволять $w$ быть весом Хэмминга (или количеством ненулевых записей) $E$. Затем $E$ имеет точно $w$ описания ошибок. Для $w=0,1,$ нечего доказывать. Итак, мы предполагаем, что $w\geqslant 2$ и что описания не идентичны. Мы замечаем, что каждая ненулевая запись $E$ появятся в узоре, и, таким образом, компоненты $E$ не включенные в шаблон, образуют циклическую серию нулей, начинающуюся после последней ненулевой записи и продолжающуюся непосредственно перед первой ненулевой записью шаблона. Набор индексов, соответствующий этому прогону, мы называем нулевым прогоном. Мы сразу замечаем, что с каждым описанием пакета связана нулевая серия и что каждая нулевая серия не пересекается. Поскольку у нас есть $w$ нулевых серий, и каждая из них не пересекается, в общей сложности мы имеем $n-w$ различные элементы во всех нулевых сериях. С другой стороны, у нас есть: $${\begin{aligned}n-w={\text{number of zeros in }}E&\geqslant (n-\mathrm {length} (P_{1}))+(n-\mathrm {length} (P_{2}))\\&=2n-\left(\mathrm {length} (P_{1})+\mathrm {length} (P_{2})\right)\\&\geqslant 2n-(n+1)&&\mathrm {length} (P_{1})+\mathrm {length} (P_{2})\leqslant n+1\\&=n-1\end{aligned}}$$Это противоречит $w\geqslant 2.$ Таким образом, описания пакетов ошибок идентичны.

Следствием приведенной выше теоремы является то , что мы не можем иметь два различных описания пакетов для пакетов длины ${\tfrac {1}{2}}(n+1).$

Циклические коды для исправления пакетов ошибок

Циклические коды определяются следующим образом: подумайте о $q$ символы как элементы в $\mathbb {F} _{q}$. Теперь мы можем думать о словах как о полиномах по $\mathbb {F} _{q},$ где отдельные символы слова соответствуют различным коэффициентам многочлена. Чтобы определить циклический код, мы выбираем фиксированный полином, называемый генераторным полиномом . Кодовыми словами этого циклического кода являются все полиномы, которые делятся на этот образующий полином.

Кодовые слова представляют собой полиномы степени $\leqslant n-1$. Предположим, что порождающий полином $g(x)$ имеет степень $r$. Полиномы степени $\leqslant n-1$ которые делятся на $g(x)$ результат умножения $g(x)$ полиномами степени $\leqslant n-1-r$. У нас есть $q^{n-r}$ такие многочлены. Каждому из них соответствует кодовое слово. Поэтому, $k=n-r$ для циклических кодов.

Циклические коды могут обнаруживать все пакеты длиной до $\ell =n-k=r$. Позже мы увидим, что способность любого устройства обнаруживать пакетные ошибки $(n,k)$ код ограничен сверху $\ell \leqslant n-k$. Циклические коды считаются оптимальными для обнаружения пакетов ошибок, поскольку они соответствуют этой верхней границе:

Теорема (возможность циклической коррекции пакетов) . Каждый циклический код с генераторным полиномом степени $r$ может обнаружить все пакеты длины $\leqslant r.$

Доказательство

Нам нужно доказать, что если вы добавите пакет длины $\leqslant r$ к кодовому слову (т.е. к многочлену, который делится на $g(x)$), то результатом не будет кодовое слово (т. е. соответствующий многочлен не делится на $g(x)$). Достаточно показать, что никакой всплеск длины $\leqslant r$ делится на $g(x)$. Такой всплеск имеет вид $x^{i}b(x)$, где $\deg(b(x))<r.$ Поэтому, $b(x)$ не делится на $g(x)$ (поскольку последний имеет степень $r$). $g(x)$ не делится на $x$ (В противном случае все кодовые слова начинались бы с $0$). Поэтому, $x^{i}$ не делится на $g(x)$ также.

Приведенное выше доказательство предлагает простой алгоритм обнаружения/коррекции пакетов ошибок в циклических кодах: по переданному слову (т. е. многочлену степени $\leqslant n-1$), вычислите остаток этого слова при делении на $g(x)$. Если остаток равен нулю (т.е. если слово делится на $g(x)$), то это допустимое кодовое слово. В противном случае сообщите об ошибке. Чтобы исправить эту ошибку, вычтите этот остаток из переданного слова. Результат вычитания будет делиться на $g(x)$ (т.е. это будет допустимое кодовое слово).

По верхней границе обнаружения пакетов ошибок ( $\ell \leqslant n-k=r$), мы знаем, что циклический код не может обнаружить все пакеты длиной $\ell >r$. Однако циклические коды действительно могут обнаружить большинство пакетов длины $>r$. Причина в том, что обнаружение не удается только тогда, когда пакет делится на $g(x)$. В двоичных алфавитах существуют $2^{\ell -2}$ всплески длины $\ell$. Из них только $2^{\ell -2-r}$ делятся на $g(x)$. Поэтому вероятность отказа обнаружения очень мала ( $2^{-r}$) при условии равномерного распределения по всем пакетам длины $\ell$.

Теперь мы рассмотрим фундаментальную теорему о циклических кодах, которая поможет в разработке эффективных кодов, исправляющих пакеты ошибок, путем категоризации пакетов по различным смежным классам.

Теорема (различные смежные классы ) — Линейный код $C$ это $\ell$-burst-error-исправляющий код, если все пакетные ошибки длины $\leqslant \ell$ лежат в различных классах смежных $C$.

Доказательство

Позволять $\mathbf {e} _{1},\mathbf {e} _{2}$ быть отчетливыми пакетными ошибками длины $\leqslant \ell$ которые лежат в одном классе кода $C$. Затем $\mathbf {c} =\mathbf {e} _{1}-\mathbf {e} _{2}$ является кодовым словом. Следовательно, если мы получим $\mathbf {e} _{1},$ мы можем декодировать его либо в $\mathbf {0}$ или $\mathbf {c}$. Напротив, если все пакетные ошибки $\mathbf {e} _{1}$ и $\mathbf {e} _{2}$ не лежат в одном смежном классе, то каждый пакет ошибок определяется своим синдромом. Ошибку затем можно исправить через ее синдром. Таким образом, линейный код $C$ это $\ell$-burst-error-correcting code тогда и только тогда, когда все пакетные ошибки длины $\leqslant \ell$ лежат в различных смежных классах $C$.

Теорема (классификация кодовых слов пакетных ошибок) — Пусть $C$ быть линейным $\ell$-код, исправляющий пакетные ошибки. Тогда никакой ненулевой пакет длины $\leqslant 2\ell$ может быть кодовым словом.

Доказательство

Позволять $c$ быть кодовым словом с большой длиной $\leqslant 2\ell$. Таким образом, он имеет образец $(0,1,u,v,1,0)$, где $u$ и $v$ это слова длины $\leqslant \ell -1.$ Следовательно, слова $w=(0,1,u,0,0,0)$ и $c-w=(0,0,0,v,1,0)$ это два пакета длины $\leqslant \ell$. Для двоичных линейных кодов они принадлежат одному и тому же классу. Это противоречит теореме о различных смежных классах, поэтому не существует ненулевого пакета длины. $\leqslant 2\ell$ может быть кодовым словом.

Границы коррекции пакетных ошибок

Верхние границы обнаружения и исправления пакетов ошибок

Под верхней границей мы подразумеваем предел нашей способности обнаруживать ошибки, за пределы которого мы никогда не сможем выйти. Предположим, мы хотим спроектировать $(n,k)$ код, который может обнаружить все пакетные ошибки длины $\leqslant \ell .$ Естественный вопрос, который следует задать: учитывая $n$ и $k$, какой максимум $\ell$ чего мы никогда не сможем достичь? Другими словами, какова верхняя граница длины $\ell$ всплесков, которые мы можем обнаружить с помощью любого $(n,k)$ код? Следующая теорема дает ответ на этот вопрос.

Теорема (возможность обнаружения пакетных ошибок) . Способность любого $(n,k)$ код $\ell \leqslant n-k.$

Доказательство

Сначала мы заметим, что код может обнаружить все пакеты длиной $\leqslant \ell$ тогда и только тогда, когда никакие два кодовых слова не отличаются по длине $\leqslant \ell$. Предположим, что у нас есть два кодовых слова $\mathbf {c} _{1}$ и $\mathbf {c} _{2}$ которые отличаются на всплеск $\mathbf {b}$ длины $\leqslant \ell$. При получении $\mathbf {c} _{1}$, мы не можем сказать, действительно ли переданное слово $\mathbf {c} _{1}$ без ошибок передачи, или это $\mathbf {c} _{2}$ с пакетной ошибкой $\mathbf {b}$ произошедшее во время передачи. Теперь предположим, что каждые два кодовых слова отличаются более чем на единицу длины. $\ell .$ Даже если переданное кодовое слово $\mathbf {c} _{1}$ поражен взрывом $\mathbf {b}$ длины $\ell$, оно не изменится на другое допустимое кодовое слово. Получив его, мы можем сказать, что это $\mathbf {c} _{1}$ со взрывом $\mathbf {b} .$ Из приведенного выше наблюдения мы знаем, что никакие два кодовых слова не могут иметь одно и то же первое кодовое слово. $n-\ell$ символы. Причина в том, что даже если они различаются во всех остальных $\ell$ символы, они все равно будут отличаться по длине $\ell .$ Следовательно, количество кодовых слов $q^{k}$ удовлетворяет $q^{k}\leqslant q^{n-\ell }.$ Применение $\log _{q}$ в обе стороны и переставляя, мы видим, что $\ell \leqslant n-k$.

Теперь повторяем тот же вопрос, но для исправления ошибок: учитывая $n$ и $k$, какова верхняя граница длины $\ell$ всплесков, которые мы можем исправить с помощью любого $(n,k)$ код? Следующая теорема дает предварительный ответ на этот вопрос:

Теорема (возможность исправления пакетных ошибок) . Способность любого $(n,k)$ код удовлетворяет $\ell \leqslant n-k-\log _{q}(n-\ell )+2$

Доказательство

Сначала мы заметим, что код может корректировать все пакеты длины $\leqslant \ell$ тогда и только тогда, когда никакие два кодовых слова не отличаются на сумму двух пакетов длины $\leqslant \ell .$ Предположим, что два кодовых слова $\mathbf {c} _{1}$ и $\mathbf {c} _{2}$ различаются всплесками $\mathbf {b} _{1}$ и $\mathbf {b} _{2}$ длины $\leqslant \ell$ каждый. При получении $\mathbf {c} _{1}$ поражен взрывом $\mathbf {b} _{1}$, мы могли бы интерпретировать это так, как будто это было $\mathbf {c} _{2}$ поражен взрывом $-\mathbf {b} _{2}$. Мы не можем определить, является ли переданное слово $\mathbf {c} _{1}$ или $\mathbf {c} _{2}$. Теперь предположим, что каждые два кодовых слова отличаются более чем на два пакета длины. $\ell$. Даже если переданное кодовое слово $\mathbf {c} _{1}$ поражен взрывом длины $\ell$, оно не будет похоже на еще одно кодовое слово, пораженное другим пакетом. Для каждого кодового слова $\mathbf {c} ,$ позволять $B(\mathbf {c} )$ обозначают совокупность всех слов, отличных от $\mathbf {c}$ по длине $\leqslant \ell .$ Обратите внимание, что $B(\mathbf {c} )$ включает в себя $\mathbf {c}$ сам. Из приведенного выше наблюдения мы знаем, что для двух разных кодовых слов $\mathbf {c} _{i}$ и $\mathbf {c} _{j},B(\mathbf {c} _{i})$ и $B(\mathbf {c} _{j})$ непересекающиеся. У нас есть $q^{k}$ кодовые слова. Поэтому мы можем сказать, что $q^{k}|B(\mathbf {c} )|\leqslant q^{n}$. Более того, у нас есть $(n-\ell )q^{\ell -2}\leqslant |B(\mathbf {c} )|$. Подставив последнее неравенство в первое, затем взяв базу $q$ логарифмируя и переставляя, получаем приведенную выше теорему.

Более сильный результат дает граница Ригера:

Теорема (оценка Ригера) — Если $\ell$ это способность корректировать пакетные ошибки $(n,k)$ линейный блочный код, тогда $2\ell \leqslant n-k$.

Доказательство

Любой линейный код, который может исправить любой пакетный шаблон длины. $\leqslant \ell$ не может иметь всплеск длины $\leqslant 2\ell$ как кодовое слово. Если бы у него был взрыв длины $\leqslant 2\ell$ как кодовое слово, затем пакет длины $\ell$ можно изменить кодовое слово на пакетный шаблон длиной $\ell$, что также может быть получено путем создания пакета ошибок длиной $\ell$ во всех нулевых кодовых словах. Если векторы не равны нулю в первую очередь $2\ell$ символов, то векторы должны быть из разных подмножеств массива, чтобы их разница не была кодовым словом пакетов длины $2\ell$. При обеспечении этого условия количество таких подмножеств как минимум равно числу векторов. Таким образом, количество подмножеств будет не менее $q^{2\ell }$. Следовательно, мы имеем по крайней мере $2\ell$ разные символы, в противном случае разница двух таких полиномов была бы кодовым словом, представляющим собой сумму двух пакетов длины $\leqslant \ell .$ Таким образом, это доказывает границу Ригера.

Определение. Линейный код, исправляющий пакетные ошибки, достигающий указанной выше границы Ригера, называется оптимальным кодом, исправляющим пакетные ошибки.

Дальнейшие ограничения на коррекцию пакетных ошибок

Существует более одной верхней границы достижимой скорости кодирования линейных блочных кодов для множественной коррекции фазированных пакетов (MPBC). Одна из таких границ ограничена максимальной корректируемой длиной циклического пакета в каждом подблоке или, что эквивалентно, ограничением минимальной безошибочной длины или промежутка в каждом фазированном пакете. Эта граница, если ее свести к частному случаю границы для коррекции одиночного пакета, является границей Абрамсона (следствие границы Хэмминга для коррекции пакета ошибок), когда длина циклического пакета меньше половины длины блока.

Теорема (количество всплесков) — Для $1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1),$ в двоичном алфавите существуют $n2^{\ell -1}+1$ векторы длины $n$ которые представляют собой всплески длины $\leqslant \ell$.

Доказательство

Поскольку длина пакета $\leqslant {\tfrac {1}{2}}(n+1),$ существует уникальное описание пакета, связанное с пакетом. Взрыв может начаться в любом из $n$ позиции узора. Каждый узор начинается с $1$ и содержать длину $\ell$. Мы можем думать об этом как о наборе всех строк, которые начинаются с $1$ и иметь длину $\ell$. Таким образом, всего имеется $2^{\ell -1}$ возможны такие закономерности, и в общей сложности $n2^{\ell -1}$ всплески длины $\leqslant \ell .$ Если мы учтем нулевой всплеск, мы получим $n2^{\ell -1}+1$ векторы, представляющие пакеты длины $\leqslant \ell .$

Теорема (ограничение на количество кодовых слов) — Если $1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1),$ двоичный файл $\ell$-код исправления пакетных ошибок имеет не более $2^{n}/(n2^{\ell -1}+1)$ кодовые слова.

Доказательство

С $\ell \leqslant {\tfrac {1}{2}}(n+1)$, мы знаем, что существуют $n2^{\ell -1}+1$ всплески длины $\leqslant \ell$. Скажем, код имеет $M$ кодовые слова, то есть $Mn2^{\ell -1}$ кодовые слова, которые отличаются от кодового слова набором длины $\leqslant \ell$. Каждый из $M$ слова должны быть разными, иначе код будет иметь расстояние $<1$. Поэтому, $M(2^{\ell -1}+1)\leqslant 2^{n}$ подразумевает $M\leqslant 2^{n}/(n2^{\ell -1}+1).$

Теорема (границы Абрамсона) — Если $1\leqslant \ell \leqslant {\tfrac {1}{2}}(n+1)$ представляет собой двоичную линейную $(n,k),\ell$-код исправления пакетных ошибок, длина его блока должна удовлетворять: $$n\leqslant 2^{n-k-\ell +1}-1.$$

Доказательство

Для линейного $(n,k)$ код, есть $2^{k}$ кодовые слова. Из нашего предыдущего результата мы знаем, что $$2^{k}\leqslant {\frac {2^{n}}{n2^{\ell -1}+1}}.$$изоляция $n$, мы получаем $n\leqslant 2^{n-k-\ell +1}-2^{-\ell +1}$. С $\ell \geqslant 1$ и $n$ должно быть целым числом, у нас есть $n\leqslant 2^{n-k-\ell +1}-1$.

Замечание. $r=n-k$ называется избыточностью кода и в альтернативной формулировке границ Абрамсона равна $r\geqslant \lceil \log _{2}(n+1)\rceil +\ell -1.$

Пожарные нормы

См. Также: Циклический код § Коды пожарной безопасности как циклические границы.

Источники:

Хотя циклические коды в целом являются мощными инструментами для обнаружения пакетов ошибок, теперь мы рассмотрим семейство двоичных циклических кодов, называемых пожарными кодами, которые обладают хорошими возможностями исправления одиночных пакетов ошибок. Одиночным пакетом, скажем, длиной $\ell$мы имеем в виду, что все ошибки, которыми обладает полученное кодовое слово, лежат в пределах фиксированного диапазона $\ell$ цифры.

Позволять $p(x)$ — неприводимый многочлен степени $m$ над $\mathbb {F} _{2}$, и пусть $p$ быть периодом $p(x)$. Период $p(x)$, как и любой полином, определяется как наименьшее положительное целое число $r$ такой, что $p(x)|x^{r}-1.$ Позволять $\ell$ быть положительным целым числом, удовлетворяющим $\ell \leqslant m$ и $2\ell -1$ не делится на $p$, где $p$ это период $p(x)$. Определите пожарный кодекс $G$ следующим полиномом генератора : $$g(x)=\left(x^{2\ell -1}+1\right)p(x).$$

Мы покажем это $G$ это $\ell$-код исправления пакетных ошибок.

Лемма 1 — $\gcd \left(p(x),x^{2\ell -1}+1\right)=1.$

Доказательство

Позволять $d(x)$ — наибольший общий делитель двух многочленов. С $p(x)$ является неприводимым, $\deg(d(x))=0$ или $\deg(p(x))$. Предполагать $\deg(d(x))\neq 0,$ затем $p(x)=cd(x)$ для некоторой константы $c$. Но, $(1/c)p(x)$ является делителем $x^{2\ell -1}+1$ с $d(x)$ является делителем $x^{2\ell -1}+1$. Но это противоречит нашему предположению, что $p(x)$ не делит $x^{2\ell -1}+1.$ Таким образом, $\deg(d(x))=0,$ доказательство леммы.

Лемма 2 — Если $p(x)$представляет собой полином периода $p$, затем $p(x)|x^{k}-1$ тогда и только тогда, когда $p|k.$

Доказательство

Если $p|k$, затем $x^{k}-1=(x^{p}-1)(1+x^{p}+x^{2p}+\dots +x^{k/p})$. Таким образом, $p(x)|x^{k}-1.$

Теперь предположим $p(x)|x^{k}-1$. Затем, $k\geqslant p$. Мы показываем, что $k$ делится на $p$ индукцией по $k$. Базовый случай $k=p$ следует. Поэтому предположим $k>p$. Мы знаем, что $p(x)$ делит оба (поскольку он имеет период $p$) $$x^{p}-1=(x-1)\left(1+x+\dots +x^{p-1}\right)\quad {\text{and}}\quad x^{k}-1=(x-1)\left(1+x+\dots +x^{k-1}\right).$$ Но $p(x)$ неприводима, поэтому должна делить обе $(1+x+\dots +x^{p-1})$ и $(1+x+\dots +x^{k-1})$; таким образом, он также делит разность двух последних многочленов, $x^{p}(1+x+\dots +x^{p-k-1})$. Тогда следует, что $p(x)$ делит $(1+x+\cdots +x^{p-k-1})$. Наконец, он также разделяет: $x^{k-p}-1=(x-1)(1+x+\dots +x^{p-k-1})$. По предположению индукции, $p|k-p$, затем $p|k$.

Следствием леммы 2 является то, что поскольку $p(x)=x^{p}-1$ имеет период $p$, затем $p(x)$ делит $x^{k}-1$ тогда и только тогда, когда $p|k$.

Теорема . Правила пожарной безопасности $\ell$- пакетное исправление ошибок

Если мы сможем показать, что все пакеты длины $\ell$ или менее встречаются в разных смежных классах , мы можем использовать их в качестве лидеров смежных классов , которые формируют исправимые шаблоны ошибок. Причина проста: мы знаем, что с каждым смежным классом связан уникальный синдром декодирования , и если все пакеты разной длины происходят в разных смежных классах, то все они имеют уникальные синдромы, что облегчает коррекцию ошибок.

Доказательство теоремы

Позволять $x^{i}a(x)$ и $x^{j}b(x)$ быть полиномами со степенями $\ell _{1}-1$ и $\ell _{2}-1$, представляющий всплески длины $\ell _{1}$ и $\ell _{2}$ соответственно с $\ell _{1},\ell _{2}\leqslant \ell .$ Целые числа $i,j$ представляют начальные позиции пакетов и меньше длины блока кода. Ради от противного предположим, что $x^{i}a(x)$ и $x^{j}b(x)$ находятся в одном классе. Затем, $v(x)=x^{i}a(x)+x^{j}b(x)$ является допустимым кодовым словом (поскольку оба термина находятся в одном смежном классе). Не ограничивая общности, выберем $i\leqslant j$. По теореме деления можно написать: $j-i=g(2\ell -1)+r,$ для целых чисел $g$ и $r,0\leqslant r<2\ell -1$. Перепишем многочлен $v(x)$ следующее: $$v(x)=x^{i}a(x)+x^{i+g(2\ell -1)+r}=x^{i}a(x)+x^{i+g(2\ell -1)+r}+2x^{i+r}b(x)=x^{i}\left(a(x)+x^{b}b(x)\right)+x^{i+r}b(x)\left(x^{g(2\ell -1)}+1\right)$$

Обратите внимание, что при второй манипуляции мы ввели термин $2x^{i+r}b(x)$. Нам разрешено это делать, поскольку пожарные нормы действуют на $\mathbb {F} _{2}$. По нашему предположению, $v(x)$ является допустимым кодовым словом и, следовательно, должно быть кратно $g(x)$. Как уже говорилось ранее, поскольку факторы $g(x)$ являются относительно простыми, $v(x)$ должно делиться на $x^{2\ell -1}+1$. Внимательно взглянув на последнее выражение, полученное для $v(x)$ мы замечаем, что $x^{g(2\ell -1)}+1$ делится на $x^{2\ell -1}+1$ (по следствию леммы 2). Поэтому, $a(x)+x^{b}b(x)$ либо делится на $x^{2\ell -1}+1$ или есть $0$. Применяя еще раз теорему деления, мы видим, что существует многочлен $d(x)$ со степенью $\delta$ такой, что: $$a(x)+x^{b}b(x)=d(x)(x^{2\ell -1}+1)$$

Тогда мы можем написать: $${\begin{aligned}\delta +2\ell -1&=\deg \left(d(x)\left(x^{2\ell -1}+1\right)\right)\\&=\deg \left(a(x)+x^{b}b(x)\right)\\&=\deg \left(x^{b}b(x)\right)&&\deg(a(x))=\ell _{1}-1<2\ell -1\\&=b+\ell _{2}-1\end{aligned}}$$

Приравнивая степени обеих сторон, мы получаем $b=2\ell -\ell _{2}+\delta .$ С $\ell _{1},\ell _{2}\leqslant \ell$ мы можем сделать вывод $b\geqslant \ell +\delta ,$ что подразумевает $b>\ell -1$ и $b>\delta$. Обратите внимание, что в расширении: $$a(x)+x^{b}b(x)=1+a_{1}x+a_{2}x^{2}+\dots +x^{\ell _{1}-1}+x^{b}\left(1+b_{1}x+b_{2}x^{2}+\dots +x^{\ell _{2}-1}\right).$$Термин $x^{b}$ появляется, но поскольку $\delta <b<2\ell -1$, полученное выражение $d(x)(x^{2\ell -1}+1)$ не содержит $x^{b}$, поэтому $d(x)=0$ и впоследствии $a(x)+x^{b}b(x)=0.$ Это требует, чтобы $b=0$, и $a(x)=b(x)$. Мы можем дополнительно пересмотреть наше разделение $j-i$ к $g(2\ell -1)$ отражать $b=0,$ то есть $j-i=g(2\ell -1)$. Подставляя обратно в $v(x)$ дает нам, $$v(x)=x^{i}b(x)\left(x^{j-1}+1\right).$$

С $\deg(b(x))=\ell _{2}-1<\ell$, у нас есть $\deg(b(x))<\deg(p(x))=m$. Но $p(x)$ неприводима, поэтому $b(x)$ и $p(x)$ должно быть относительно простым. С $v(x)$ это кодовое слово, $x^{j-1}+1$ должно делиться на $p(x)$, так как оно не может делиться на $x^{2\ell -1}+1$. Поэтому, $j-i$ должно быть кратно $p$. Но оно также должно быть кратно $2\ell -1$, что означает, что оно должно быть кратно $n={\text{lcm}}(2\ell -1,p)$ но это именно длина блока кода. Поэтому, $j-i$ не может быть кратным $n$ поскольку они оба меньше $n$. Таким образом, наше предположение о $v(x)$ быть кодовым словом неверно, и поэтому $x^{i}a(x)$ и $x^{j}b(x)$ находятся в разных классах, имеют уникальные синдромы и, следовательно, поддаются коррекции.

Пример: код пожарной безопасности с 5 пакетами ошибок, исправляющий ошибки.

Используя теорию, представленную в предыдущем разделе, рассмотрим построение $5$- пакетная ошибка, исправляющая пожарный код. Помните, что для построения Кодекса пожарной безопасности нам нужен неприводимый многочлен $p(x)$, целое число $\ell$, представляющий возможность исправления пакетов ошибок нашего кода, и нам необходимо удовлетворить свойству, которое $2\ell -1$ не делится на период $p(x)$. Учитывая эти требования, рассмотрим неприводимый полином $p(x)=1+x^{2}+x^{5}$, и пусть $\ell =5$. С $p(x)$ является примитивным полиномом, его период равен $2^{5}-1=31$. Мы подтверждаем это $2\ell -1=9$ не делится на $31$. Таким образом, $$g(x)=(x^{9}+1)\left(1+x^{2}+x^{5}\right)=1+x^{2}+x^{5}+x^{9}+x^{11}+x^{14}$$является генератором пожарного кода. Мы можем вычислить длину блока кода, вычислив наименьшее общее кратное $p$ и $2\ell -1$. Другими словами, $n={\text{lcm}}(9,31)=279$. Таким образом, приведенный выше код пожарной безопасности представляет собой циклический код, способный корректировать любой пакет длины $5$ или меньше.

Двоичные коды Рида – Соломона

Некоторые семейства кодов, такие как коды Рида-Соломона , работают с размерами алфавита, большими, чем двоичный. Это свойство наделяет такие коды мощными возможностями исправления пакетов ошибок. Рассмотрим код, работающий на $\mathbb {F} _{2^{m}}$. Каждый символ алфавита может быть представлен $m$ биты. Если $C$ это $(n,k)$ Код Рида – Соломона закончен $\mathbb {F} _{2^{m}}$, мы можем подумать о $C$ как $[mn,mk]_{2}$ кодировать $\mathbb {F} _{2}$.

Причина, по которой такие коды эффективны для исправления пакетов ошибок, заключается в том, что каждый символ представлен $m$ бит, и вообще неважно, сколько их $m$ биты ошибочны; будь то один бит или все $m$ биты содержат ошибки, с точки зрения декодирования это по-прежнему ошибка одного символа. Другими словами, поскольку пакетные ошибки обычно возникают в кластерах, существует большая вероятность того, что несколько двоичных ошибок будут способствовать возникновению ошибки одного символа.

Обратите внимание, что всплеск $(m+1)$ ошибки могут повлиять максимум $2$ символы и взрыв $2m+1$ может повлиять максимум $3$ символы. Затем произошел взрыв $tm+1$ может повлиять максимум $t+1$ символы; это означает, что $t$Код, исправляющий -symbols-error, может максимально исправить пакет длины $(t-1)m+1$.

В целом, $t$-исправление ошибок в коде Рида-Соломона $\mathbb {F} _{2^{m}}$ может исправить любую комбинацию $${\frac {t}{1+\lfloor (l+m-2)/m\rfloor }}$$или меньше всплесков длины $l$, помимо возможности исправить $t$-случайные ошибки в худшем случае.

Пример двоичного кода RS

Позволять $G$ быть $[255,223,33]$ Код RS закончился $\mathbb {F} _{2^{8}}$. Этот код использовался НАСА в космическом корабле Кассини-Гюйгенс . Он способен исправить $\lfloor 33/2\rfloor =16$ ошибки в символах. Теперь мы создадим двоичный код RS. $G'$ от $G$. Каждый символ будет записан с использованием $\lceil \log _{2}(255)\rceil =8$ биты. Следовательно, двоичный код RS будет иметь $[2040,1784,33]_{2}$ как его параметры. Он способен корректировать любой одиночный пакет длины. $l=121$.

Перемежающиеся коды

Перемежение используется для преобразования сверточных кодов из корректоров случайных ошибок в корректоры пакетных ошибок. Основная идея использования чередующихся кодов заключается в смешивании символов в передатчике. Это приводит к рандомизации пакетов принятых ошибок, которые расположены близко, и затем мы можем применить анализ для случайного канала. Таким образом, основная функция перемежителя на передатчике заключается в изменении последовательности входных символов. В приемнике обращенный перемежитель изменит принятую последовательность, чтобы вернуть исходную неизмененную последовательность на передатчике.

Способность перемежителя корректировать пакетные ошибки

Иллюстрация порядка строк и столбцов

Теорема . Если способность некоторого кода исправлять пакетные ошибки $\ell ,$ то его способность исправлять пакетные ошибки $\lambda$-способ чередования $\lambda \ell .$

Доказательство

Предположим, что у нас есть $(n,k)$ код, который может исправить все пакеты длины $\leqslant \ell .$ Чередование может дать нам $(\lambda n,\lambda k)$ код, который может исправить все пакеты длины $\leqslant \lambda \ell ,$ для любого данного $\lambda$. Если мы хотим закодировать сообщение произвольной длины с помощью чередования, сначала мы делим его на блоки длины $\lambda k$. Мы пишем $\lambda k$ записи каждого блока в $\lambda \times k$ матрица с использованием порядка строк. Затем мы кодируем каждую строку, используя $(n,k)$ код. Мы получим $\lambda \times n$ матрица. Теперь эта матрица считывается и передается в порядке столбцов. Хитрость в том, что если произойдет всплеск длины $h$ в передаваемом слове, то каждая строка будет содержать примерно ${\tfrac {h}{\lambda }}$ последовательные ошибки (более конкретно, каждая строка будет содержать пакет длиной не менее $\lfloor {\tfrac {h}{\lambda }}\rfloor$ и самое большее $\lceil {\tfrac {h}{\lambda }}\rceil$). Если $h\leqslant \lambda \ell ,$ затем ${\tfrac {h}{\lambda }}\leqslant \ell$ и $(n,k)$ код может исправить каждую строку. Таким образом, чередование $(\lambda n,\lambda k)$ код может исправить всплеск длины $h$. И наоборот, если $h>\lambda \ell ,$ то хотя бы одна строка будет содержать более ${\tfrac {h}{\lambda }}$ последовательные ошибки и $(n,k)$ код может не исправить их. Таким образом, способность исправления ошибок чередующегося $(\lambda n,\lambda k)$ код точно $\lambda \ell .$ Эффективность BEC чередующегося кода остается такой же, как и исходного. $(n,k)$ код. Это правда, потому что: $${\frac {2\lambda \ell }{\lambda n-\lambda k}}={\frac {2\ell }{n-k}}$$

Блочный перемежитель

На рисунке ниже показан перемежитель 4 на 3.

Пример перемежителя блоков

Вышеупомянутый перемежитель называется перемежителем блоков . Здесь входные символы записываются последовательно в строках, а выходные символы получаются путем последовательного чтения столбцов. Таким образом, это в форме $M\times N$ множество. В целом, $N$ длина кодового слова.

Производительность перемежителя блоков : Для $M\times N$ перемежитель блоков и пакетная длина $\ell ,$ верхний предел количества ошибок равен ${\tfrac {\ell }{M}}.$ Это очевидно из того факта, что мы читаем выходной столбец, а количество строк равно $M$. По приведенной выше теореме для корректирующей способности до $t,$ максимально допустимая длина пакета составляет $Mt.$ Для длительности пакета $Mt+1$, декодер может выйти из строя.

Эффективность перемежителя блоков ( $\gamma$): Его определяют путем определения отношения длины пакета, при которой декодер может выйти из строя, к памяти перемежителя. Таким образом, мы можем сформулировать $\gamma$ как $$\gamma ={\frac {Mt+1}{MN}}\approx {\frac {t}{N}}.$$

Недостатки блочного перемежителя: Как видно из рисунка, столбцы читаются последовательно, получатель может интерпретировать одну строку только после получения полного сообщения, а не раньше. Кроме того, получателю требуется значительный объем памяти для хранения полученных символов и он должен хранить все сообщение. Таким образом, эти факторы порождают два недостатка: один — задержка, а другой — хранилище (довольно большой объем памяти). Этих недостатков можно избежать, используя описанный ниже сверточный перемежитель.

Сверточный перемежитель

Кросс-перемежитель представляет собой разновидность системы мультиплексор-демультиплексор. В этой системе линии задержки используются для постепенного увеличения длины. Линия задержки — это, по сути, электронная схема, используемая для задержки сигнала на определенную продолжительность времени. Позволять $n$ быть числом линий задержки и $d$ быть количеством символов, введенных каждой линией задержки. Таким образом, расстояние между последовательными входами = $nd$ символы. Пусть длина кодового слова $\leqslant n.$ Таким образом, каждый символ во входном кодовом слове будет находиться на отдельной линии задержки. Пусть пакет ошибок длиной $\ell$ происходить. Поскольку расстояние между последовательными символами равно $nd,$ количество ошибок, которые может содержать вывод без чередования, равно ${\tfrac {\ell }{nd+1}}.$ По приведенной выше теореме для корректирующей способности до $t$, максимальная допустимая длина пакета составляет $(nd+1)(t-1).$ Для длительности пакета $(nd+1)(t-1)+1,$ декодер может выйти из строя.

Пример сверточного перемежителя

Пример деперемежителя

Эффективность перекрестного перемежителя ( $\gamma$): Его определяют путем определения отношения длины пакета, при которой декодер может выйти из строя, к памяти перемежителя. В этом случае память перемежителя можно рассчитать как $$(0+1+2+3+\cdots +(n-1))d={\frac {n(n-1)}{2}}d.$$

Таким образом, мы можем сформулировать $\gamma$ следующее: $$\gamma ={\frac {(nd+1)(t-1)+1}{{\frac {n(n-1)}{2}}d}}.$$

Производительность перекрестного перемежителя: Как показано на рисунке перемежителя выше, выходные данные представляют собой не что иное, как диагональные символы, генерируемые в конце каждой линии задержки. В этом случае, когда переключение входного мультиплексора завершается примерно наполовину, мы можем прочитать первую строку на приемнике. Таким образом, нам нужно сохранить максимум около половины сообщения в получателе, чтобы прочитать первую строку. Это радикально снижает потребность в хранилище вдвое. Поскольку теперь для чтения первой строки требуется только половина сообщения, задержка также уменьшается вдвое, что является хорошим улучшением по сравнению с перемежителем блоков. Таким образом, вся память перемежителя разделена между передатчиком и приемником.

Приложения

Компакт-диск

Без кодов, исправляющих ошибки, цифровое аудио было бы технически невозможно. Коды Рида-Соломона могут исправить поврежденный символ с ошибкой в ​​один бит так же легко, как они могут исправить символ, в котором все биты неправильны. Это делает коды RS особенно подходящими для исправления пакетов ошибок. Безусловно, наиболее распространенное применение кодов RS - компакт-диски. Помимо базовой коррекции ошибок, обеспечиваемой кодами RS, защиту от пакетных ошибок из-за царапин на диске обеспечивает перекрестный перемежитель.

Современная цифровая аудиосистема на компакт-диске была разработана компаниями NV Philips из Нидерландов и Sony Corporation из Японии (соглашение подписано в 1979 году).

Компакт-диск представляет собой алюминизированный диск диаметром 120 мм, покрытый прозрачным пластиковым покрытием, со спиральной дорожкой длиной около 5 км, который оптически сканируется лазером с длиной волны ~0,8 мкм с постоянной скоростью ~1,25 м/с. Для достижения этой постоянной скорости вращение диска варьируется от ~8 об/с при сканировании внутренней части дорожки до ~3,5 об/с на внешней части. Ямки и площадки — это впадины (глубиной 0,12 мкм) и плоские сегменты, составляющие бинарные данные вдоль дорожки (шириной 0,6 мкм).

Процесс CD можно абстрагировать как последовательность следующих подпроцессов:

• Канальное кодирование источника сигналов
• Механические подпроцессы подготовки мастер-диска, производства пользовательских дисков и восприятия сигналов, встроенных в пользовательские диски, во время воспроизведения – канал
• Декодирование сигналов, полученных с пользовательских дисков

Этот процесс подвержен как пакетным ошибкам, так и случайным ошибкам. Пакетные ошибки включают ошибки, связанные с материалом диска (дефекты алюминиевой отражающей пленки, плохой коэффициент отражения прозрачного материала диска), производством диска (дефекты во время формирования диска и резки диска и т. д.), обращением с диском (царапины – обычно тонкие, радиальные и ортогональные к диску). направлении записи) и вариации механизма воспроизведения. К случайным ошибкам относятся ошибки, возникающие из-за джиттера восстановленной волны сигнала и помех в сигнале. CIRC ( код Рида-Соломона с перекрестным чередованием ) является основой для обнаружения и исправления ошибок в процессе CD. Он последовательно исправляет пакеты ошибок длиной до 3500 бит (длиной 2,4 мм, если смотреть на поверхность компакт-диска) и компенсирует пакеты ошибок длиной до 12 000 бит (8,5 мм), которые могут быть вызваны небольшими царапинами.

Кодирование: звуковые волны дискретизируются и преобразуются в цифровую форму с помощью аналого-цифрового преобразователя. Звуковая волна дискретизируется по амплитуде (44,1 кГц или 44 100 пар, по одной для левого и правого каналов стереозвука). Амплитуда в экземпляре присваивается двоичной строке длиной 16. Таким образом, каждая выборка создает два двоичных вектора из $\mathbb {F} _{2}^{16}$ или 4 $\mathbb {F} _{2}^{8}$ байты данных. Каждая секунда записанного звука составляет 44 100 × 32 = 1 411 200 бит (176 400 байт) данных. Поток дискретизированных данных со скоростью 1,41 Мбит/с проходит через систему исправления ошибок и в конечном итоге преобразуется в поток со скоростью 1,88 Мбит/с.

Вход для кодера состоит из входных кадров по 24 8-битных символа каждый (12 16-битных отсчетов от аналого-цифрового преобразователя, по 6 от левого и правого источников данных (звука). Кадр может быть представлен $L_{1}R_{1}L_{2}R_{2}\ldots L_{6}R_{6}$ где $L_{i}$ и $R_{i}$ - это байты из левого и правого каналов из $i^{th}$ образец кадра.

Первоначально байты переставляются для формирования новых кадров, представленных $L_{1}L_{3}L_{5}R_{1}R_{3}R_{5}L_{2}L_{4}L_{6}R_{2}R_{4}R_{6}$ где $L_{i},R_{i}$представлять $i$-ые левые и правые выборки из кадра после двух промежуточных кадров.

Затем эти 24 символа сообщения кодируются с использованием кода Рида – Соломона C2 (28,24,5), который представляет собой сокращенный код RS. $\mathbb {F} _{256}$. Это исправление двух ошибок с минимальным расстоянием 5. Это добавляет 4 байта избыточности, $P_{1}P_{2}$ формируем новый кадр: $L_{1}L_{3}L_{5}R_{1}R_{3}R_{5}P_{1}P_{2}L_{2}L_{4}L_{6}R_{2}R_{4}R_{6}$. Результирующее кодовое слово из 28 символов проходит через перекрестный перемежитель (28.4), что приводит к 28 перемеженным символам. Затем они пропускаются через код RS C1 (32,28,5), в результате чего получаются кодовые слова из 32 кодированных выходных символов. Дальнейшая перегруппировка нечетных символов кодового слова с четными символами следующего кодового слова выполняется для разделения любых коротких пакетов, которые все еще могут присутствовать после вышеупомянутого перемежения с задержкой из 4 кадров. Таким образом, на каждые 24 входных символа будет приходиться 32 выходных символа, дающих $R=24/32$. Наконец, добавляется один байт информации управления и отображения. Каждый из 33 байтов затем преобразуется в 17 бит посредством EFM (модуляция от восьми до четырнадцати) и добавления 3 битов слияния. Таким образом, в результате кадра из шести выборок получается 33 байта × 17 бит (561 бит), к которым добавляются 24 бита синхронизации и 3 бита слияния, что в сумме дает 588 бит.

Декодирование: проигрыватель компакт-дисков (декодер CIRC) принимает поток данных из 32 выходных символов. Этот поток сначала проходит через декодер D1. Отдельные разработчики систем компакт-дисков должны сами выбирать методы декодирования и оптимизировать характеристики своих продуктов. Находится на минимальном расстоянии 5. Каждый из декодеров D1 и D2 может корректировать комбинацию $e$ ошибки и $f$ стирания такие, что $2e+f<5$. В большинстве решений декодирования D1 предназначен для исправления одиночной ошибки. А в случае более чем 1 ошибки этот декодер выдает 28 стираний. Обратный перемежитель на следующем этапе распределяет эти стирания по 28 кодовым словам D2. Опять же, в большинстве решений D2 настроен только на удаление (более простое и менее затратное решение). Если обнаружено более 4 стираний, D2 выводит 24 стирания. После этого система маскирования ошибок пытается выполнить интерполяцию (из соседних символов) в случае неисправимых символов, в результате чего звуки, соответствующие таким ошибочным символам, приглушаются.

Производительность CIRC: CIRC скрывает длинные ошибки с помощью простой линейной интерполяции. Длина дорожки 2,5 мм (4000 бит) — это максимальная полностью корректируемая длина пакета. Длина дорожки 7,7 мм (12 300 бит) — это максимальная длина пакета, которую можно интерполировать. Частота интерполяции выборки составляет одну каждые 10 часов при частоте битовых ошибок (BER). $=10^{-4}$ и 1000 выборок в минуту при BER = $10^{-3}$ Выборки необнаружимых ошибок (щелчки): менее одной каждые 750 часов при BER = $10^{-3}$ и пренебрежимо мал при BER = $10^{-4}$.

См. также

• Обнаружение и исправление ошибок
• Коды, исправляющие ошибки с обратной связью
• Скорость кода
• Исправление ошибок Рида – Соломона