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

Коды, предназначенные для исправления коротких последовательных ошибок в канале связи.

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

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

Определения

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

Всплеск длиной ℓ ^[1]

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

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

Циклический пакет длиной ℓ ^[1]

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

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

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

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

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

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

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

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

Позвольте быть весом Хэмминга (или числом ненулевых записей) . Тогда есть именно описания ошибок. Ибо доказывать нечего. Поэтому мы предполагаем, что и описания не идентичны. Мы замечаем, что каждая ненулевая запись появится в шаблоне, и поэтому компоненты, не включенные в шаблон, будут образовывать циклический ряд нулей, начинающийся после последней ненулевой записи и продолжающийся непосредственно перед первой ненулевой записью шаблона. . Набор индексов, соответствующий этому прогону, мы называем нулевым прогоном. Мы сразу замечаем, что с каждым описанием пакета связана нулевая серия и что каждая нулевая серия не пересекается. Поскольку у нас есть нулевые серии, и каждая из них не пересекается, у нас есть общее количество различных элементов во всех нулевых сериях. С другой стороны, у нас есть: ${\displaystyle w}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle w}$ ${\displaystyle w=0,1,}$ ${\displaystyle w\geqslant 2}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle w}$ ${\displaystyle n-w}$

$${\displaystyle {\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}}}$$

Это противоречит. Таким образом, описания пакетов ошибок идентичны. ${\displaystyle w\geqslant 2.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$${\displaystyle n\leqslant 2^{n-k-\ell +1}-1.}$$

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

Для линейного кода существуют кодовые слова. Из нашего предыдущего результата мы знаем, что ${\displaystyle (n,k)}$ ${\displaystyle 2^{k}}$

$${\displaystyle 2^{k}\leqslant {\frac {2^{n}}{n2^{\ell -1}+1}}.}$$

Изолируя , мы получаем . Поскольку и должно быть целым числом, имеем . ${\displaystyle n}$ ${\displaystyle n\leqslant 2^{n-k-\ell +1}-2^{-\ell +1}}$ ${\displaystyle \ell \geqslant 1}$ ${\displaystyle n}$ ${\displaystyle n\leqslant 2^{n-k-\ell +1}-1}$

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

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

Источники: ^{[3] [4] [5]}

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

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

$${\displaystyle g(x)=\left(x^{2\ell -1}+1\right)p(x).}$$

Мы покажем, что это код, исправляющий -burst-ошибки. ${\displaystyle G}$ ${\displaystyle \ell }$

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

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

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

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

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

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

Теперь предположим . Затем, . Покажем, что делится на путем индукции по . Далее следует базовый случай . Поэтому предположим . Мы знаем, что делит оба (поскольку у него есть период ) ${\displaystyle p(x)|x^{k}-1}$ ${\displaystyle k\geqslant p}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle k=p}$ ${\displaystyle k>p}$ ${\displaystyle p(x)}$ ${\displaystyle p}$

$${\displaystyle 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).}$$

Но неприводимо, поэтому должно делить и и ; таким образом, он также делит разность последних двух многочленов, . Тогда следует, что делит . Наконец, он также делит: . По предположению индукции , тогда . ${\displaystyle p(x)}$ ${\displaystyle (1+x+\dots +x^{p-1})}$ ${\displaystyle (1+x+\dots +x^{k-1})}$ ${\displaystyle x^{p}(1+x+\dots +x^{p-k-1})}$ ${\displaystyle p(x)}$ ${\displaystyle (1+x+\cdots +x^{p-k-1})}$ ${\displaystyle x^{k-p}-1=(x-1)(1+x+\dots +x^{p-k-1})}$ ${\displaystyle p|k-p}$ ${\displaystyle p|k}$

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

Теорема  .  Кодекс пожарной безопасности предназначен для исправления пакетов ошибок ^{[4] [5]} ${\displaystyle \ell }$

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

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

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

$${\displaystyle 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)}$$

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

$${\displaystyle a(x)+x^{b}b(x)=d(x)(x^{2\ell -1}+1)}$$

Тогда мы можем написать:

$${\displaystyle {\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}}}$$

Приравнивая степени обеих сторон, мы получаем Поскольку мы можем сделать вывод , что подразумевает и . Обратите внимание, что в расширении: ${\displaystyle b=2\ell -\ell _{2}+\delta .}$ ${\displaystyle \ell _{1},\ell _{2}\leqslant \ell }$ ${\displaystyle b\geqslant \ell +\delta ,}$ ${\displaystyle b>\ell -1}$ ${\displaystyle b>\delta }$

$${\displaystyle 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).}$$

. ${\displaystyle x^{b}}$ ${\displaystyle \delta <b<2\ell -1}$ ${\displaystyle d(x)(x^{2\ell -1}+1)}$ ${\displaystyle x^{b}}$ ${\displaystyle d(x)=0}$ ${\displaystyle a(x)+x^{b}b(x)=0.}$ ${\displaystyle b=0}$ ${\displaystyle a(x)=b(x)}$ ${\displaystyle j-i}$ ${\displaystyle g(2\ell -1)}$ ${\displaystyle b=0,}$ ${\displaystyle j-i=g(2\ell -1)}$ ${\displaystyle v(x)}$

$${\displaystyle v(x)=x^{i}b(x)\left(x^{j-1}+1\right).}$$

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

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

Используя теорию, представленную в приведенном выше разделе, рассмотрим построение кода пожарной безопасности, исправляющего пакет ошибок. Помните, что для построения кода пожарной безопасности нам нужен неприводимый многочлен , целое число , представляющее способность нашего кода исправлять пакетные ошибки, и нам нужно удовлетворить свойству, которое не делится на период . Учитывая эти требования, рассмотрим неприводимый многочлен и пусть . Поскольку это примитивный полином, его период равен . Подтверждаем, что не делится на . Таким образом, ${\displaystyle 5}$ ${\displaystyle p(x)}$ ${\displaystyle \ell }$ ${\displaystyle 2\ell -1}$ ${\displaystyle p(x)}$ ${\displaystyle p(x)=1+x^{2}+x^{5}}$ ${\displaystyle \ell =5}$ ${\displaystyle p(x)}$ ${\displaystyle 2^{5}-1=31}$ ${\displaystyle 2\ell -1=9}$ ${\displaystyle 31}$

$${\displaystyle g(x)=(x^{9}+1)\left(1+x^{2}+x^{5}\right)=1+x^{2}+x^{5}+x^{9}+x^{11}+x^{14}}$$

${\displaystyle p}$ ${\displaystyle 2\ell -1}$ ${\displaystyle n={\text{lcm}}(9,31)=279}$ ${\displaystyle 5}$

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

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

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

Обратите внимание, что пакет ошибок может повлиять на большинство символов, а пакет ошибок может повлиять на большинство символов. Тогда всплеск может повлиять на большинство символов; это означает, что код исправления ошибок -symbols может исправить пакет длиной не более . ${\displaystyle (m+1)}$ ${\displaystyle 2}$ ${\displaystyle 2m+1}$ ${\displaystyle 3}$ ${\displaystyle tm+1}$ ${\displaystyle t+1}$ ${\displaystyle t}$ ${\displaystyle (t-1)m+1}$

В общем, код Рида – Соломона, исправляющий ошибки , может исправить любую комбинацию ошибок. ${\displaystyle t}$ ${\displaystyle \mathbb {F} _{2^{m}}}$

$${\displaystyle {\frac {t}{1+\lfloor (l+m-2)/m\rfloor }}}$$

${\displaystyle l}$ ${\displaystyle t}$

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

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

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

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

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

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

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

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

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

$${\displaystyle {\frac {2\lambda \ell }{\lambda n-\lambda k}}={\frac {2\ell }{n-k}}}$$

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

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

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

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

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

Эффективность блочного перемежителя ( ): ${\displaystyle \gamma }$ определяется отношением длины пакета, при которой декодер может выйти из строя, к памяти перемежителя. Таким образом, мы можем сформулировать как ${\displaystyle \gamma }$

$${\displaystyle \gamma ={\frac {Mt+1}{MN}}\approx {\frac {t}{N}}.}$$

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

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

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

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

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

Эффективность перекрестного перемежителя ( ): ${\displaystyle \gamma }$ определяется путем определения отношения длины пакета, при которой декодер может выйти из строя, к памяти перемежителя. В этом случае память перемежителя можно рассчитать как

$${\displaystyle (0+1+2+3+\cdots +(n-1))d={\frac {n(n-1)}{2}}d.}$$

Таким образом, мы можем сформулировать следующим образом: ${\displaystyle \gamma }$

$${\displaystyle \gamma ={\frac {(nd+1)(t-1)+1}{{\frac {n(n-1)}{2}}d}}.}$$

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Фонг, WH (2011). «Границы кодирования для кодов коррекции множественных фазовых пакетов и кодов коррекции одиночных пакетов». arXiv : 1104.1408 [cs.IT].
2. МакЭлис, Р.Дж. (2004). Теория информации и кодирования (Студенческая ред.). Издательство Кембриджского университета. ISBN 978-0-521-83185-7.
3. Линг, Сан; Син, Чаопин (2004). Теория кодирования: первый курс. Издательство Кембриджского университета. ISBN 978-0-521-52923-5.
4. Moon, Тодд К. (2005). Кодирование с коррекцией ошибок: математические методы и алгоритмы. Уайли. ISBN 978-0-471-64800-0.
5. Лин, Шу; Костелло, Дэниел Дж. (2004). Кодирование с контролем ошибок: основы и приложения (2-е изд.). Пирсон-Прентис Холл. ISBN 978-0-13-017973-9.
6. «Кассини: Какая коррекция ошибок?». quest.arc.nasa.gov . 1999. Архивировано из оригинала 27 июня 2012 г.
7. Алгебраические коды контроля ошибок (осень 2012 г.) - Раздаточные материалы Стэнфордского университета
8. МакЭлис, Роберт Дж. (1977). Теория информации и кодирования: математическая основа коммуникации . Расширенная книжная программа. Аддисон-Уэсли.