Код Рида — Соломона

---

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

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

Код Рида — Соломона был изобретён в 1960 году сотрудниками лаборатории Линкольна Массачусетского технологического института Ирвингом Ридом^[англ.] и Густавом Соломоном^[англ.]. Идея использования этого кода была представлена в статье «Polynomial Codes over Certain Finite Fields». Эффективные алгоритмы декодирования были предложены в 1969 году Элвином Берлекэмпом и Джэймсом Месси (алгоритм Берлекэмпа — Мэсси) и в 1977 году Давидом Мандельбаумом^[англ.] (метод, использующий Алгоритм Евклида^[1]). Первое применение код Рида — Соломона получил в 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 l_{0}}$ — некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается ${\displaystyle l_{0}=1}$. Степень многочлена ${\displaystyle \textstyle g(x)}$ равна ${\displaystyle d-1}$.

---