Коды Рида — Соломона ( англ. Reed–Solomon codes ) — недвоичные циклические коды , позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).

Код Рида — Соломона является частным случаем БЧХ-кода .

В настоящее время широко используется в системах восстановления данных с компакт-дисков , при создании архивов с информацией для восстановления в случае повреждений, в помехоустойчивом кодировании .

История

Код Рида — Соломона был изобретён в 1960 году сотрудниками лаборатории Линкольна Массачусетского технологического института и . Идея использования этого кода была представлена в статье «Polynomial Codes over Certain Finite Fields». Эффективные алгоритмы декодирования были предложены в 1969 году Элвином Берлекэмпом и Джэймсом Месси ( алгоритм Берлекэмпа — Мэсси ) и в 1977 году (метод, использующий Алгоритм Евклида ). Первое применение код Рида — Соломона получил в 1982 году в серийном выпуске компакт-дисков.

Формальное описание

Коды Рида — Соломона являются важным частным случаем БЧХ-кода , корни порождающего полинома которого лежат в том же поле , над которым строится код ( ${\displaystyle m=1}$ ). Пусть ${\displaystyle \alpha }$ — элемент поля ${\displaystyle \textstyle GF(q)}$ , имеющий порядок ${\displaystyle \textstyle n}$ . Если ${\displaystyle \alpha }$ — примитивный элемент, то его порядок равен ${\displaystyle q-1}$ , то есть ${\displaystyle \alpha ^{q-1}=1,\quad \alpha ^{i}\neq 1,0<i<q-1}$ . Тогда нормированный полином ${\displaystyle g(x)}$ минимальной степени над полем ${\displaystyle \textstyle GF(q)}$ , корнями которого являются ${\displaystyle d-1}$ подряд идущих степеней ${\displaystyle \alpha ^{l_{0}},\alpha ^{l_{0}+1},...,\alpha ^{l_{0}+d-2}}$ элемента ${\displaystyle \alpha }$ , является порождающим полиномом кода Рида — Соломона над полем ${\displaystyle \textstyle GF(q)}$ :

${\displaystyle g(x)=(x-\alpha ^{l_{0}})(x-\alpha ^{l_{0}+1})\dots (x-\alpha ^{l_{0}+d-2}),}$

где ${\displaystyle l_{0}}$ — некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается ${\displaystyle l_{0}=1}$ . Степень многочлена ${\displaystyle \textstyle g(x)}$ равна ${\displaystyle d-1}$ .

Длина полученного кода ${\displaystyle n}$ , минимальное расстояние ${\displaystyle d}$ (является минимальным из всех расстояний Хемминга всех пар кодовых слов, см. Линейный код ). Код содержит ${\displaystyle r=d-1=\deg(g(x))}$ проверочных символов, где ${\displaystyle \deg()}$ обозначает степень полинома; число информационных символов ${\displaystyle k=n-r=n-d+1}$ . Таким образом ${\displaystyle \textstyle d=n-k+1}$ и код Рида — Соломона является разделимым кодом с максимальным расстоянием (является оптимальным в смысле границы Синглтона ).

Кодовый полином ${\displaystyle c(x)}$ может быть получен из информационного полинома ${\displaystyle m(x)}$ , ${\displaystyle \deg m(x)\leqslant k-1}$ , путём перемножения ${\displaystyle m(x)}$ и ${\displaystyle g(x)}$ :

${\displaystyle c(x)=m(x)g(x).}$

Свойства

Код Рида — Соломона над ${\displaystyle \textstyle GF(q^{m})}$ , исправляющий ${\displaystyle t}$ ошибок, требует ${\displaystyle 2t}$ проверочных символов и с его помощью исправляются произвольные пакеты ошибок длиной ${\displaystyle t}$ и меньше. Согласно теореме о границе Рейгера, коды Рида — Соломона являются оптимальными с точки зрения соотношения длины пакета и возможности исправления ошибок — используя ${\displaystyle 2t}$ дополнительных проверочных символов, исправляется ${\displaystyle t}$ ошибок (и менее).

Теорема (граница Рейгера) . Каждый линейный блоковый код, исправляющий все пакеты длиной ${\displaystyle t}$ и менее, должен содержать, по меньшей мере, ${\displaystyle 2t}$ проверочных символов.

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

Матрица ${\displaystyle G=[{\begin{array}{cc}I_{k*k}&P_{k*(n-k)}\\\end{array}}]}$ порождает код Рида — Соломона тогда и только тогда когда любой минор матрицы ${\displaystyle P_{k*(n-k)}}$ отличен от нуля.

При выкалывании или укорочении кода Рида — Соломона снова получается код Рида — Соломона. Выкалывание — операция, состоящая в удалении одного проверочного символа. Длина ${\displaystyle n}$ кода уменьшается на единицу, размерность ${\displaystyle k}$ сохраняется. Расстояние кода ${\displaystyle d}$ должно уменьшиться на единицу, ибо в противном случае удаленный символ был бы бесполезен. Укорочение — фиксируем произвольный столбец ${\displaystyle (n,k,d)}$ кода и выбираем только те векторы, которые в данном столбце содержат 0. Это множество векторов образует подпространство .

Исправление многократных ошибок

Код Рида — Соломона является одним из наиболее мощных кодов, исправляющих многократные пакеты ошибок. Применяется в каналах, где пакеты ошибок могут образовываться столь часто, что их уже нельзя исправлять с помощью кодов, исправляющих одиночные ошибки.

Код Рида — Соломона ${\displaystyle (q^{m}-1,q^{m}-1-2t)}$ над полем ${\displaystyle \textstyle GF(q^{m})}$ с кодовым расстоянием ${\displaystyle d=2t+1}$ можно рассматривать как ${\displaystyle ((q^{m}-1)m,(q^{m}-1-2t)m)}$ -код над полем ${\displaystyle \textstyle GF(q)}$ , который может исправлять любую комбинацию ошибок, сосредоточенную в ${\displaystyle t}$ или меньшем числе блоков из m символов. Наибольшее число блоков длины ${\displaystyle m}$ , которые может затронуть пакет длины ${\displaystyle l_{i}}$ , где ${\displaystyle l_{i}\leqslant mt_{i}-(m-1)}$ , не превосходит ${\displaystyle t_{i}}$ , поэтому код, который может исправить ${\displaystyle t}$ блоков ошибок, всегда может исправить и любую комбинацию из ${\displaystyle p}$ пакетов общей длины ${\displaystyle l}$ , если ${\displaystyle l+(m-1)\leqslant mt}$ .

Практическая реализация

Кодирование с помощью кода Рида — Соломона может быть реализовано двумя способами: систематическим и несистематическим (см. , описание кодировщика).

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

При систематическом кодировании к информационному блоку из ${\displaystyle k}$ символов приписываются ${\displaystyle 2t}$ проверочных символов, при вычислении каждого проверочного символа используются все ${\displaystyle k}$ символов исходного блока. В этом случае нет затрат ресурсов при извлечении исходного блока, если информационное слово не содержит ошибок, но кодировщик/декодировщик должен выполнить ${\displaystyle k(n-k)}$ операций сложения и умножения для генерации проверочных символов. Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка ${\displaystyle O(ln^{2}{n})}$ .

Кодирование

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

• К исходному слову приписываются ${\displaystyle 2t}$ нулей, получается полином ${\displaystyle \textstyle T=Sx^{2t}}$ .
• Этот полином делится на порождающий полином ${\displaystyle G}$ , находится остаток ${\displaystyle R}$ , ${\displaystyle \textstyle Sx^{2t}=QG+R}$ , где ${\displaystyle Q}$ — частное.
• Этот остаток и будет корректирующим кодом Рида — Соломона, он приписывается к исходному блоку символов. Полученное кодовое слово ${\displaystyle \textstyle C=Sx^{2t}+R}$ .

Кодировщик строится из сдвиговых регистров, сумматоров и умножителей. Сдвиговый регистр состоит из ячеек памяти, в каждой из которых находится один элемент поля Галуа.

Существует и другая процедура кодирования (более практичная и простая). Положим ${\displaystyle a_{i}\in GF(q),(i=1,2,\ldots ,k-1),\alpha \in GF(q)}$ — примитивный элемент поля ${\displaystyle GF(q)}$ , и пусть ${\displaystyle a=(a_{0},a_{1},\ldots ,a_{k-1})}$ — вектор информационных символов, а значит ${\displaystyle a(x)=a_{0}+a_{1}x+\ldots +a_{k-1}x^{k-1}}$ — информационный многочлен. Тогда вектор ${\displaystyle u=(a(1),a(\alpha ),\ldots ,a(\alpha ^{q-2}))}$ есть вектор кода Рида — Соломона, соответствующий информационному вектору ${\displaystyle a}$ . Этот способ кодирования показывает, что для кода РС вообще не нужно знать порождающего многочлена и порождающей матрицы кода, достаточно знать разложение поля ${\displaystyle GF(q)}$ по примитивному элементу ${\displaystyle \alpha }$ и размерность кода ${\displaystyle k}$ (длина кода в этом случае определяется как ${\displaystyle n=q-1}$ ). Все дело в том, что за разностью ${\displaystyle n-k}$ полностью скрывается порождающий многочлен ${\displaystyle g(x)}$ и кодовое расстояние.

Декодирование

Декодировщик, работающий по авторегрессивному спектральному методу декодирования, последовательно выполняет следующие действия:

• Вычисляет синдром ошибки
• Строит полином ошибки
• Находит корни данного полинома
• Определяет характер ошибки
• Исправляет ошибки

Вычисление синдрома ошибки

Вычисление синдрома ошибки выполняется синдромным декодером, который делит кодовое слово на порождающий многочлен. Если при делении возникает остаток, то в слове есть ошибка. Остаток от деления является синдромом ошибки.

Построение полинома ошибки

Вычисленный синдром ошибки не указывает на положение ошибок. Степень полинома синдрома равна ${\displaystyle 2t}$ , что много меньше степени кодового слова ${\displaystyle n}$ . Для получения соответствия между ошибкой и её положением в сообщении строится полином ошибок. Полином ошибок реализуется с помощью алгоритма Берлекэмпа — Месси либо с помощью алгоритма Евклида. Алгоритм Евклида имеет простую реализацию, но требует больших затрат ресурсов. Поэтому чаще применяется более сложный, но менее затратоемкий алгоритм Берлекэмпа — Месси. Коэффициенты найденного полинома непосредственно соответствуют коэффициентам ошибочных символов в кодовом слове.

Нахождение корней

На этом этапе ищутся корни полинома ошибки, определяющие положение искаженных символов в кодовом слове. Реализуется с помощью процедуры Ченя, равносильной полному перебору. В полином ошибок последовательно подставляются все возможные значения, когда полином обращается в ноль — корни найдены.

Определение характера ошибки и её исправление

По синдрому ошибки и найденным корням полинома с помощью алгоритма Форни определяется характер ошибки и строится маска искаженных символов. Однако для кодов РС существует более простой способ отыскания характера ошибок. Как показано в для кодов РС с произвольным множеством ${\displaystyle 2t_{d}}$ последовательных нулей ${\displaystyle \alpha ^{b},\alpha ^{b+1},\ldots ,\alpha ^{b+\delta },\delta =2t_{d}-1}$ :

где ${\displaystyle \sigma '(x)}$ формальная производная по ${\displaystyle x}$ многочлена локаторов ошибок ${\displaystyle \sigma (x)}$ , а ${\displaystyle \Lambda (x)=\sigma (x)S(x)\mod x^{2t_{d}+1}.}$

Далее после того как маска найдена, она накладывается на кодовое слово с помощью операции XOR и искаженные символы восстанавливаются. После этого отбрасываются проверочные символы и получается восстановленное информационное слово.

Алгоритм Судана

В данное время стали применяться принципиально новые методы декодирования, например, алгоритм, предложенный в 1997 году Мадху Суданом .

Удлинение кодов РС

Удлинение кодов РС — это процедура, при которой увеличивается длина и расстояние кода (при этом код ещё находится на границе Синглтона и алфавит кода не изменяется), а количество информационных символов кода не изменяется . Такая процедура увеличивает корректирующую способность кода . Рассмотрим удлинение кода РС на один символ. Пусть ${\displaystyle \upsilon =(c_{0},c_{1},\ldots ,c_{q-2})}$ — вектор кода РС, порождающий многочлен которого есть ${\displaystyle g(x)=(x-\alpha )(x-\alpha ^{2})\ldots (x-\alpha ^{d-1}),\deg g(x)=d-1=r=n-k,n=q-1}$ . Пусть теперь ${\displaystyle c_{q-1}=-\sum _{i=1}^{q-2}c_{i}}$ . Покажем, что добавление к вектору ${\displaystyle \upsilon }$ символа ${\displaystyle c_{q-1}}$ увеличит его вес до ${\displaystyle d+1}$ , если ${\displaystyle c_{q-1}\neq 0}$ . Многочлен, соответствующий вектору кода, можно расписать как ${\displaystyle \upsilon (x)=g(x)*z(x)}$ , но тогда с учётом выражения для ${\displaystyle c_{q-1}}$ получим ${\displaystyle \upsilon (1)=g(1)z(1)=-c_{q-1}}$ . ${\displaystyle g(1)\neq 0}$ , так как 1 не принадлежит списку корней порождающего многочлена. Но и ${\displaystyle z(1)\neq 0}$ , так как в этом случае ${\displaystyle (x-1)g(x)|\upsilon (x)}$ , что увеличило бы расстояние кода вопреки условию, это значит что ${\displaystyle c_{q-1}\neq 0}$ и вес кода увеличился, за счёт добавления нового символа ${\displaystyle c_{q-1}}$ . Новые параметры кода ${\displaystyle n_{1}=n+1,k_{1}=k,d_{1}=d+1}$ , удлиненный вектор ${\displaystyle v_{1}=(c_{0},c_{1},\ldots ,c_{q-2},c_{q-1})}$ . Проверочная матрица не удлиненного кода имеет вид

      ${\displaystyle H={\begin{Vmatrix}1&\alpha &\alpha ^{2}&\cdots &\alpha ^{q-2}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(q-2)}\\\cdots &\cdots &\cdots &\cdots &\cdots \\1&\alpha ^{d-1}&\alpha ^{2(d-1)}&\cdots &\alpha ^{(d-1)(q-2)}\end{Vmatrix}}}$

Тогда проверочная матрица, удлиненного на один символ РС кода будет

      ${\displaystyle H_{1}={\begin{Vmatrix}1&1&1&\cdots &1&1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{q-2}&0\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(q-2)}&0\\\cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\1&\alpha ^{d-1}&\alpha ^{2(d-1)}&\cdots &\alpha ^{(d-1)(q-2)}&0\end{Vmatrix}}}$

Применение

Сразу после появления (60-е годы XX века) коды Рида — Соломона стали применяться в качестве внешних кодов в каскадных конструкциях, использующихся в спутниковой связи. В подобных конструкциях ${\displaystyle q}$ -е символы РС (их может быть несколько) кодируются внутренними сверточными кодами . На приемном конце эти символы декодируются мягким алгоритмом Витерби (эффективный в каналах с АБГШ ) . Такой декодер будет исправлять одиночные ошибки в q-ричных символах, когда же возникнут пакетные ошибки и некоторые пакеты q-ричных символов будут декодированы неправильно, тогда внешний декодер Рида — Соломона исправит пакеты этих ошибок. Таким образом будет достигнута требуемая надежность передачи информации ( ).

В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря своей способности находить и исправлять многократные пакеты ошибок.

Запись и хранение информации

Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти ( ECC ), при архивировании данных, записи информации на жесткие диски, записи на CD/DVD диски. Даже если поврежден значительный объем информации, испорчено несколько секторов дискового носителя, то коды Рида — Соломона позволяют восстановить большую часть потерянной информации. Также используется при записи на такие носители, как магнитные ленты и штрихкоды.

Запись на CD-ROM

Возможные ошибки при чтении с диска появляются уже на этапе производства диска, так как сделать идеальный диск при современных технологиях невозможно. Также ошибки могут быть вызваны царапинами на поверхности диска, пылью и т. д. Поэтому при изготовлении читаемого компакт-диска используется система коррекции CIRC (Cross Interleaved Reed Solomon Code). Эта коррекция реализована во всех устройствах, позволяющих считывать данные с CD-дисков, в виде чипа с прошивкой firmware. Нахождение и коррекция ошибок основана на избыточности и перемежении (redundancy & interleaving). Избыточность — примерно 25 % от исходной информации.

При записи на аудиокомпакт-диски используется стандарт Red Book . Коррекция ошибок происходит на двух уровнях, C1 и C2. При кодировании на первом этапе происходит добавление проверочных символов к исходным данным, на втором этапе информация снова кодируется. Кроме кодирования, осуществляется также перемешивание ( перемежение ) байтов, чтобы при коррекции блоки ошибок распались на отдельные биты, которые легче исправляются. На первом уровне обнаруживаются и исправляются ошибочные блоки длиной один и два байта (один и два ошибочных символа, соответственно). Ошибочные блоки длиной три байта обнаруживаются и передаются на следующий уровень. На втором уровне обнаруживаются и исправляются ошибочные блоки, возникшие в C2, длиной 1 и 2 байта. Обнаружение трех ошибочных символов является фатальной ошибкой и не может быть исправлено.

Беспроводная и мобильная связь

Этот алгоритм кодирования используется при передаче данных по сетям WiMAX , в оптических линиях связи , в спутниковой и радиорелейной связи . Метод прямой коррекции ошибок в проходящем трафике (Forward Error Correction, FEC) основывается на кодах Рида — Соломона.

Примеры кодирования

16-ричный (15,11) код Рида — Соломона

Пусть ${\displaystyle t=2,l_{0}=1}$ . Тогда

Степень ${\displaystyle g(x)}$ равна 4, ${\displaystyle n-k=4}$ и ${\displaystyle k=11}$ . Каждому элементу поля ${\displaystyle \mathrm {GF} (16)}$ можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из ${\displaystyle \mathrm {GF} (16)}$ , что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.

8-ричный (7,3) код Рида — Соломона

Пусть ${\displaystyle t=2,l_{0}=4}$ . Тогда

Пусть информационный многочлен имеет вид:

Кодовое слово несистематического кода запишется в виде:

что представляет собой последовательность семи восьмеричных символов.

Альтернативный метод кодирования 9-ричного (8,4) кода Рида — Соломона

Построим поле Галуа ${\displaystyle GF(3^{2})}$ по модулю многочлена ${\displaystyle x^{2}+x+2}$ . Пусть ${\displaystyle \alpha }$ его корень, тогда ${\displaystyle \alpha ^{2}+\alpha +2=0}$ , таблица поля имеет вид:

      ${\displaystyle 0=0=(00),}$
      ${\displaystyle \alpha ^{0}=1=(10),}$
      ${\displaystyle \alpha ^{1}=\alpha =(01),}$
      ${\displaystyle \alpha ^{2}=1+2\alpha =(12),}$ 
      ${\displaystyle \alpha ^{3}=2+2\alpha =(22),}$
      ${\displaystyle \alpha ^{4}=2=(20),}$
      ${\displaystyle \alpha ^{5}=2\alpha =(02),}$
      ${\displaystyle \alpha ^{6}=2+\alpha =(21),}$
      ${\displaystyle \alpha ^{7}=1+\alpha =(11).}$

Пусть информационный многочлен ${\displaystyle a(x)=1+\alpha x+\alpha ^{2}x^{2}+\alpha ^{3}x^{3}}$ , далее производя соответствующие вычисления над построенным полем получим: ${\displaystyle a(1)=\alpha ^{2},\ a(\alpha )=0,\ a(\alpha ^{2})=\alpha ^{6},\ a(\alpha ^{3})=0,\ a(\alpha ^{4})=\alpha ^{5},\ a(\alpha ^{5})=0,\ a(\alpha ^{6})=\alpha ^{7},\ a(\alpha ^{7})=1.}$

В итоге построен вектор кода РС с параметрами ${\displaystyle n=8,\ k=4,\ d=5}$ . На этом кодирование закончено. Заметим, что при этом способе нам не потребовался порождающий многочлен кода .

Примеры декодирования

Пусть поле ${\displaystyle GF(2^{3})}$ генерируется примитивным элементом, неприводимый многочлен которого ${\displaystyle p(x)=x^{3}+x+1}$ . Тогда ${\displaystyle p(\alpha )=\alpha ^{3}+\alpha +1=0}$ . Пусть ${\displaystyle b=0,\ t_{d}=2}$ . Тогда порождающий многочлен кода РС равен ${\displaystyle g(x)=(x+1)(x+\alpha )(x+\alpha ^{2})(x+\alpha ^{3})=x^{4}+\alpha ^{2}x^{3}+\alpha ^{5}x^{2}+\alpha ^{5}x+\alpha ^{6}}$ . Пусть теперь принят многочлен ${\displaystyle r(x)=\alpha x^{2}+\alpha ^{5}x^{4}}$ . Тогда ${\displaystyle S_{1}=r(1)=\alpha +\alpha ^{5}=\alpha ^{6},\ S_{2}=r(\alpha )=\alpha ^{5},\ S_{3}=\alpha ,\ S_{4}=\alpha }$ . Тогда ключевая система уравнений получается в виде:

Теперь рассмотрим Евклидов алгоритм решения этой системы уравнений.

• Начальные условия :

                   ${\displaystyle r_{0}(x)=x^{5},\ r1(x)=S(x)=1+\alpha ^{6}x+\alpha ^{5}x^{2}+\alpha x^{3}+\alpha x^{4},}$
                   ${\displaystyle b_{0}(x)=0,\ b_{1}(x)=1;}$

• ${\displaystyle i=2}$

${\displaystyle x^{5}=(1+\alpha ^{6}x+\alpha ^{5}x^{2}+\alpha x^{3}+\alpha x^{4})(\alpha ^{6}x+\alpha ^{6})+\alpha ^{5}x+x^{2}+\alpha x+\alpha ^{6},}$
 ${\displaystyle r_{2}(x)=\alpha ^{5}x^{3}+x^{2}+\alpha x+\alpha ^{6},}$
 ${\displaystyle q_{2}(x)=\alpha ^{6}x+\alpha ^{6},}$
 ${\displaystyle b_{2}(x)=0+(\alpha ^{6}x+\alpha ^{6})(1)=\alpha ^{6}x+\alpha ^{6};}$

• ${\displaystyle i=3}$

Алгоритм останавливается, так как ${\displaystyle \deg[r_{3}(x)]=2=t_{d}}$ , отсюда следует, что ${\displaystyle \sigma (x)=\alpha ^{3}+\alpha ^{4}x+\alpha ^{2}x^{2}.}$

Далее полный перебор по алгоритму Чени выдает нам позиции ошибок, это ${\displaystyle j_{1}=2,\quad j_{2}=4}$ . Потом по формуле ${\displaystyle (*)}$ получаем что ${\displaystyle e_{2}=\alpha ,\ e_{4}=\alpha .}$

Таким образом декодированный вектор ${\displaystyle c(x)=r(x)+e(x)=0}$ . Декодирование завершено, исправлены две ошибки .

Применение

• Код Рида — Соломона используется в некоторых прикладных программах в области хранения данных, например в RAID 6 ;

См. также

• Конечное поле
• Обнаружение и исправление ошибок
• Циклический код
• Код Боуза — Чоудхури — Хоквингема
• Турбо-код
• Код Хэмминга

Примечания

Литература

• Питерсон У., Уэлдон Э. . — М. : Мир, 1976. — С. .
• Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М. : Мир , 1986. — 576 с.
• Берлекэмп Э. = Algebraic Coding Theory. — М. : Мир, 1971. — С. .
• Егоров С.И. Коррекция ошибок в информационных каналах периферийных устройств ЭВМ. — Курск: КурскГТУ, 2008. — С. 252.
• — М. : МФТИ , 2007. — 262 с. — ISBN 978-5-7417-0191-1
• Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. . — М. : Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0 .
• М. Вернер. Основы кодирования. — Техносфера, 2004. — 288 с. — ISBN 5-94836-019-9 .

Ссылки

• — использование par2 , утилиты восстановления файлов методом Кода Рида-Соломона (рус.)