Свернутый код Рида – Соломона

В теории кодирования сложенные коды Рида – Соломона похожи на Коды Рида – Соломона, которые получаются отображением $m\; \{\backslash \; displaystyle\; m\}$кодовых слов Рида – Соломона на более крупный алфавит путем тщательного объединения символов кодовых слов.

Свернутые коды Рида – Соломона также являются частным случаем кодов Парвареша – Варди.

Используя оптимальные параметры, можно декодировать со скоростью R и достичь радиуса декодирования of 1 - R.

Термин «свернутые коды Рида – Соломона» был введен в обращение В.Ю. Крачковского с алгоритмом, который представил коды Рида – Соломона со множеством случайных "фазированных пакетов" ошибок [1]. Алгоритм декодирования списка для свернутых кодов RS корректирует за пределами $1\; -\; R\; \{\backslash \; displaystyle\; 1\; -\; \{\backslash \; sqrt\; \{R\}\}\}$границы для кодов Рида – Соломона, достигнутых Гурусвами - Суданский алгоритм для таких фазированных пакетных ошибок.

• 1 История
• 2 Определение
  • 2.1 Графическое описание
• 3 Свернутые коды Рида – Соломона и одноэлементная граница
  • 3.1 Почему складывание может помочь?
• 4 Как сложено Reed– Коды Соломона (FRS) и коды Парвареша Варди (PV) связаны
• 5 Краткий обзор свернутых кодов Рида – Соломона со списком декодирования
• 6 Алгоритм декодирования линейно-алгебраическим списком
  • 6.1 Шаг 1: Шаг интерполяции
  • 6.2 Шаг 2: Шаг поиска корня
  • 6.3 Шаг 3: Шаг сокращения
  • 6.4 Резюме
• 7 См. Также
• 8 Ссылки

Один из Текущие проблемы в теории кодирования состоят в том, чтобы коды с исправлением ошибок обеспечивали оптимальный компромисс между скоростью (кодирования) и радиусом исправления ошибок. Хотя это может оказаться невозможным практически (из-за проблем теории кодирования каналов с шумом), квазиоптимальные компромиссы могут быть достигнуты теоретически.

До разработки свернутых кодов Рида-Соломона наилучший радиус коррекции ошибок был $1\; -\; R\; \{\backslash \; displaystyle\; 1\; -\; \{\backslash \; sqrt\; \{R\}\}\}$, на коды Рида – Соломона для всех коэффициентов $R\; \{\backslash \; displaystyle\; R\}$.

Улучшение этого была достигнута Парварешем и Варди для коэффициентов

. Для $R\; \to \; 0\; \{\backslash \; displaystyle\; R\; \backslash \; to\; 0\}$алгоритм Парвареша – Варди может декодировать дробь $1\; -\; O\; (R\; log\; \; (1\; /\; R))\; \{\backslash \; displaystyle\; 1-O\; (R\; \backslash \; log\; (1\; /\; R))\}$ошибок.

Сложенные коды Рида – Соломона улучшают эти предыдущие конструкции и могут быть декодированы по списку за полиномиальное время для дроби $(1\; -\; R\; -\; \epsilon )\; \{\backslash \; displaystyle\; (1-R-\; \backslash \; varepsilon)\}$ошибок для любой константы $\epsilon >0\; \{\backslash \; displaystyle\; \backslash \; varepsilon>0\}$.

$f\; (X)\; \mapsto \; [f\; (1)\; f\; (\gamma )\; ⋮\; f\; (\gamma \; m\; -\; 1)],\; [f\; (\gamma \; m)\; f\; (\gamma \; m\; +\; 1)\; ⋮\; f\; (\gamma \; 2\; m\; -\; 1)],\dots ,\; [f\; (\gamma \; n\; -\; m)\; f\; (\gamma \; n\; -\; m\; +\; 1)\; ⋮\; е\; (\gamma \; N\; -\; 1)]\; \{\backslash \; Displaystyle\; F\; (X)\; \backslash \; mapsto\; \{\backslash \; begin\; \{bmatrix\}\; f\; (1)\; \backslash \backslash \; f\; (\backslash \; gamma)\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; f\; (\backslash \; gamma\; ^\; \{m\; -1\})\; \backslash \; end\; \{bmatrix\}\},\; \{\backslash \; begin\; \{bmatrix\}\; f\; (\backslash \; gamma\; ^\; \{m\})\; \backslash \backslash \; f\; (\backslash \; gamma\; ^\; \{m\; +\; 1\})\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; f\; (\backslash \; gamma\; ^\; \{2m-1\})\; \backslash \; end\; \{bmatrix\}\},\; \backslash \; ldots,\; \{\backslash \; begin\; \{bmatrix\}\; f\; (\backslash \; gamma\; ^\; \{nm\})\; \backslash \backslash \; f\; (\backslash \; gamma\; ^\; \{n-m\; +\; 1\})\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; f\; (\backslash \; gamma\; ^\; \{n-1\})\; \backslash \; end\; \{bmatrix\}\}\}$

Рассмотрим формулу Рида – Соломона $[n\; =\; q\; -\; 1,\; k]\; q\; \{\backslash \; displaystyle\; [n\; =\; q-1,\; k]\; \_\; \{q\}\}$код длина $n\; \{\backslash \; displaystyle\; n\}$и размер $k\; \{\backslash \; displaystyle\; k\}$и параметр сворачивания $m\; \ge \; 1\; \{\; \backslash \; Displaystyle\; m\; \backslash \; geq\; 1\}$. Предположим, что $m\; \{\backslash \; displaystyle\; m\}$делит $n\; \{\backslash \; displaystyle\; n\}$.

Отображение для кодов Рида – Соломона следующим образом:

$f\; \mapsto \; ⟨f\; (1),\; е\; (\gamma \; 1),\; е\; (\gamma \; 2),\dots \; е\; (\gamma \; N\; -\; 1)⟩\; \{\backslash \; Displaystyle\; f\; \backslash \; mapsto\; \backslash \; left\; \backslash \; langle\; f\; (1),\; f\; \backslash \; left\; (\backslash \; gamma\; ^\; \{1\}\; \backslash \; right),\; f\; \backslash \; left\; (\backslash \; gamma\; ^\; \{2\}\; \backslash \; right),\; \backslash \; ldots,\; f\; \backslash \; left\; (\backslash \; gamma\; ^\; \{n-1\}\; \backslash \; right)\; \backslash \; right\; \backslash \; rangle\}$

где $\gamma \; \in \; F\; q\; \{\; \backslash \; displaystyle\; \backslash \; gamma\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\}$- примитивный элемент в

$F\; q\; =\; \{0,\; 1,\; \gamma ,\; \gamma \; 2,\dots ,\; \gamma \; N\; -\; 1\}\; \{\backslash \; Displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; =\; \backslash \; left\; \backslash \; \{0,1,\; \backslash \; gamma,\; \backslash \; gamma\; ^\; \{2\},\; \backslash \; ldots,\; \backslash \; gamma\; ^\; \{n-1\}\; \backslash \; right\; \backslash \}\}$.

$m\; \{\backslash \; displaystyle\; m\}$свернутый вариант кода Рида-Соломона $C\; \{\backslash \; displaystyle\; C\}$, обозначенный $FRSF,\; \gamma ,\; m,\; k\; \{\backslash \; displaystyle\; FRS\; \_\; \{\backslash \; mathbb\; \{F\},\; \backslash \; gamma,\; m,\; k\}\}$- это код длины блока $N\; =\; n\; /\; m\; \{\backslash \; displaystyle\; N\; =\; n\; /\; m\}$более $F\; m\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; ^\; \{m\}\}$. $FRSF,\; \gamma ,\; m,\; k\; \{\backslash \; displaystyle\; FRS\; \_\; \{\backslash \; mathbb\; \{F\},\; \backslash \; гамма,\; м,\; k\}\}$ar е просто $[q\; -\; 1,\; k]\; \{\backslash \; displaystyle\; [q-1,\; k]\}$коды Рида-Соломона с $m\; \{\backslash \; displaystyle\; m\}$последовательные символы из кодовых слов RS, сгруппированных вместе.

Графическое описание

Сворачивание кода Рида – Соломона с параметром сворачивания m = 3

Приведенное выше определение становится более ясным с помощью диаграммы с $m\; =\; 3\; \{\backslash \; displaystyle\; m\; =\; 3\}$, где $m\; \{\backslash \; displaystyle\; m\}$- параметр сворачивания.

Сообщение обозначается тегом $f\; (X)\; \{\backslash \; displaystyle\; f\; (X)\}$, который при кодировании с использованием кодировки Рида – Соломона состоит из значений $f.\; \{\backslash \; displaystyle\; f\}$at $x\; 0,\; x\; 1,\; x\; 2,\dots ,\; xn\; -\; 1\; \{\backslash \; displaystyle\; x\_\; \{0\},\; x\_\; \{1\},\; x\_\; \{2\},\; \backslash \; ldots,\; x\_\; \{n-1\}\}$, где $xi\; =\; \gamma \; i\; \{\backslash \; displaystyle\; x\_\; \{i\}\; =\; \backslash \; gamma\; ^\; \{i\}\}$.

Затем объединение выполняется группами по 3 элемента, чтобы задать кодовое слово длиной $n\; /\; 3\; \{\backslash \; displaystyle\; n\; /\; 3\}$над алфавитом $F\; q\; 3\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{3\}\; \}$.

Здесь следует отметить то, что продемонстрированная операция сворачивания не изменяет скорость $R\; \{\backslash \; displaystyle\; R\}$исходного кода Рида – Соломона.

Чтобы доказать это, рассмотрим линейный код $[n,\; k,\; d]\; q\; \{\backslash \; displaystyle\; [n,\; k,\; d]\; \_\; \{q\}\}$длиной $n\; \{\backslash \; displaystyle\; n\}$, dimension $k\; \{\backslash \; displaystyle\; k\}$и distance $d\; \{\backslash \; displaystyle\; d\}$. Операция сворачивания $m\; \{\backslash \; displaystyle\; m\}$сделает его $[нм,\; км,\; дм]\; qm\; \{\backslash \; displaystyle\; \backslash \; left\; [\{\backslash \; tfrac\; \{n\}\; \{m\}\},\; \{\backslash \; tfrac\; \{k\}\; \{m\}\},\; \{\backslash \; tfrac\; \{d\}\; \{m\}\}\; \backslash \; right]\; \_\; \{q\; ^\; \{m\}\}\}$код. Таким образом, rate $R\; =\; n\; k\; \{\backslash \; displaystyle\; R\; =\; \{\backslash \; tfrac\; \{n\}\; \{k\}\}\}$будет таким же.

Согласно асимптотической версии одноэлементной границы известно, что относительное расстояние $\delta \; \{\backslash \; displaystyle\; \backslash \; delta\}$, код должен удовлетворять $R\; ⩽\; 1\; -\; \delta \; +\; o\; (1)\; \{\backslash \; displaystyle\; R\; \backslash \; leqslant\; 1-\; \backslash \; delta\; +\; o\; (1)\; \}$, где $R\; \{\backslash \; displaystyle\; R\}$- скорость кода. Как было доказано ранее, поскольку скорость $R\; \{\backslash \; displaystyle\; R\}$сохраняется, относительное расстояние $\delta \; ⩾\; 1\; -\; R\; \{\backslash \; displaystyle\; \backslash \; delta\; \backslash \; geqslant\; 1-R\}$также соответствует границе Синглтона.

Почему складывание может помочь?

Декодирование свернутого кода Рида-Соломона

Свернутые коды Рида-Соломона в основном такие же, как коды Рида-Соломона, только просматриваемые через больший алфавит. Чтобы показать, как это может помочь, рассмотрим свернутый код Рида – Соломона с $m\; =\; 3\; \{\backslash \; displaystyle\; m\; =\; 3\}$. Расшифровка кода Рида – Соломона и свернутого кода Рида – Соломона с одинаковой долей ошибок $\rho \; \{\backslash \; displaystyle\; \backslash \; rho\}$- задачи почти одинаковой вычислительной интенсивности: можно развернуть полученное слово свернутого кода Рида-Соломона, рассматривать его как полученное слово исходного кода Рида-Соломона и запускать алгоритм декодирования списка Рида-Соломона на нем. Очевидно, этот список будет содержать все свернутые кодовые слова Рида – Соломона на расстоянии $\rho \; \{\backslash \; displaystyle\; \backslash \; rho\}$от полученного слова, а также некоторые дополнения, которые мы можем удалить.

Кроме того, декодирование свернутого кода Рида – Соломона - более простая задача. Допустим, мы хотим исправить треть ошибок. Выбранный алгоритм декодирования должен исправить шаблон ошибок, который исправляет каждый третий символ в кодировании Рида-Соломона. Но после сворачивания этот шаблон ошибки приведет к повреждению всех символов над $F\; q\; 3\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{3\}\}$и устранит необходимость исправления ошибок. Это распространение ошибок обозначено синим цветом в графическом описании. Это доказывает, что для фиксированной доли ошибок $\rho ,\; \{\backslash \; displaystyle\; \backslash \; rho,\}$операция сворачивания снижает гибкость канала для распределения ошибок, что, в свою очередь, приводит к уменьшению количества шаблоны ошибок, которые необходимо исправить.

Мы можем связать свернутые коды Рида-Соломона с кодами Парвареша Варди, которые кодируют многочлен $f\; \{\backslash \; displaystyle\; f\}$степени $k\; \{\backslash \; displaystyle\; k\}$с многочленами $f\; 0\; =\; f,\; f\; 1,\dots ,\; fs\; -\; 1\; (s\; ⩾\; 2)\; \{\backslash \; displaystyle\; f\_\; \{0\}\; =\; f,\; f\_\; \{1\},\; \backslash \; ldots,\; f\_\; \{s-1\}\; (s\; \backslash \; geqslant\; 2)\}$где $fi\; (X)\; =\; fi\; -\; 1\; (X)\; d\; mod\; E\; (X)\; \{\backslash \; displaystyle\; f\_\; \{i\}\; (X)\; =\; f\_\; \{i-1\}\; (X)\; ^\; \{d\}\; \backslash \; mod\; E\; (X)\}$где $E\; (X)\; \{\backslash \; displaystyle\; E\; (X)\}$- это неприводимый многочлен. При выборе неприводимого многочлена $E\; (X)\; =\; X\; q\; -\; \gamma \; \{\backslash \; displaystyle\; E\; (X)\; =\; X\; ^\; \{q\}\; -\; \backslash \; gamma\}$и параметра $d\; \{\backslash \; displaystyle\; d\}$мы должны проверить, каждый ли многочлен $f\; \{\backslash \; displaystyle\; f\}$степени не выше $k\; \{\backslash \; displaystyle\; k\}$удовлетворяет $е\; (\gamma \; Икс)\; знак\; равно\; е\; (Икс)\; d\; mod\; E\; (X)\; \{\backslash \; Displaystyle\; f\; (\backslash \; gamma\; X)\; =\; f\; (X)\; ^\; \{d\}\; \backslash \; mod\; E\; (X)\}$с $f\; (\gamma \; X)\; \{\backslash \; displaystyle\; f\; (\backslash \; gamma\; X)\}$- это просто сдвинутый аналог $f\; (X)\; \{\backslash \; displaystyle\; f\; (X)\}$где $\gamma \; \{\backslash \; displaystyle\; \backslash \; gamma\}$- примитивный элемент в $F\; q.\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}.\}$Сложенный таким образом код RS с объединением вместе кодовых символов является кодом PV порядка $s\; =\; m\; \{\backslash \; displaystyle\; s\; =\; m\}$для набора точек оценки

$\{1,\; \gamma ,\; \gamma \; 2\; m,\dots ,\; \gamma \; (nm\; -\; 1)\; m\}\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{1,\; \backslash \; gamma,\; \backslash \; gamma\; ^\; \{2m\},\; \backslash \; ldots,\; \backslash \; gamma\; ^\; \{\backslash \; left\; (\{\backslash \; frac\; \{n\}\; \{m\}\}\; -\; 1\; \backslash \; right)\; m\}\; \backslash \; right\; \backslash \}\}$.

Если сравнить свернутый код RS с PV-кодом порядка 2 для множество точек оценки

$\{1,\; \gamma ,\dots ,\; \gamma \; m\; -\; 2,\; \gamma \; m,\; \gamma \; m\; +\; 1,\dots ,\; \gamma \; 2\; m\; -\; 2,\dots ,\; \gamma \; n\; -\; m,\; \gamma \; n\; -\; m\; +\; 1,\; \dots ,\; \Gamma \; N\; -\; 2\}\; \{\backslash \; Displaystyle\; \backslash \; left\; \backslash \; \{1,\; \backslash \; gamma,\; \backslash \; ldots,\; \backslash \; gamma\; ^\; \{m-2\},\; \backslash \; gamma\; ^\; \{m\},\; \backslash \; gamma\; ^\; \{m\; +\; 1\},\; \backslash \; ldots,\; \backslash \; gamma\; ^\; \{2m-2\},\; \backslash \; ldots,\; \backslash \; gamma\; ^\; \{nm\},\; \backslash \; gamma\; ^\; \{n-m\; +\; 1\},\; \backslash \; ldots,\; \backslash \; gamma\; ^\; \{n-2\}\; \backslash \; right\; \backslash \}\}$

мы можно увидеть, что в кодировке PV $f\; \{\backslash \; displaystyle\; f\}$для каждого $0\; \le \; i\; \le \; n\; /\; m\; -\; 1\; \{\backslash \; displaystyle\; 0\; \backslash \; leq\; i\; \backslash \; leq\; n\; /\; m-\; 1\}$и каждый появляется в $f\; (\gamma \; mi\; +\; j)\; \{\backslash \; displaystyle\; f\; (\backslash \; gamma\; ^\; \{mi\; +\; j\})\}$и $f\; 1\; (\gamma \; -\; 1\; \gamma \; mi\; +\; j)\; \{\backslash \; displayst\; yle\; f\_\; \{1\}\; (\backslash \; gamma\; ^\; \{-\; 1\}\; \backslash \; gamma\; ^\; \{mi\; +\; j\})\}$,

Связь между кодами PV и кодами FRS

в отличие от свернутой кодировки FRS, в которой она встречается только один раз. Таким образом, коды PV и свернутые коды RS имеют одинаковую информацию, но только скорость FRS больше в $2\; (м\; -\; 1)\; /\; м\; \{\backslash \; displaystyle\; 2\; (m-1)\; /\; m\}$, и, следовательно, компромисс радиуса декодирования списка лучше для свернутого кода RS, просто используя возможность декодирования списка кодов PV. Плюс заключается в выборе кода FRS таким образом, чтобы они представляли собой сжатые формы подходящего PV-кода с аналогичной эффективностью исправления ошибок с лучшей скоростью, чем соответствующий PV-код. Эту идею можно использовать для построения свернутых кодов RS со скоростью $R\; \{\backslash \; displaystyle\; R\}$, которые декодируются списком до радиуса приблизительно $1\; -\; R\; s\; /\; [s\; +\; 1]\; \{\; \backslash \; displaystyle\; 1-R\; ^\; \{s\; /\; [s\; +\; 1]\}\}$для $s\; \ge \; 1\; \{\backslash \; displaystyle\; s\; \backslash \; geq\; 1\}$. [2]

A список декодирования алгоритм, который выполняется за квадратичное время для декодирования кода FRS до радиуса $1\; -\; R\; -\; \epsilon \; \{\backslash \; displaystyle\; 1-R-\; \backslash \; varepsilon\}$представлен Гурусвами. По сути, алгоритм состоит из трех этапов, а именно этапа интерполяции, на котором используется интерполяция в стиле Уэлча-Берлекампа для интерполяции ненулевого многочлена

$Q\; (X,\; Y\; 1,\; Y\; 2,\dots ,\; Y\; s)\; =\; A\; 0\; (X)\; +\; A\; 1\; (X)\; Y\; 1\; +\; A\; 2\; (X)\; Y\; 2\; +\; \cdots \; +\; A\; s\; (X)\; Y\; s,\; \{\backslash \; displaystyle\; Q\; (X,\; Y\_\; \{1\},\; Y\_\; \{2\},\; \backslash \; ldots,\; Y\_\; \{s\}))\; =\; A\_\; \{0\}\; (X)\; +\; A\_\; \{1\}\; (X)\; Y\_\; \{1\}\; +\; A\_\; \{2\}\; (X)\; Y\_\; \{2\}\; +\; \backslash \; cdots\; +\; A\_\; \{s\}\; (X)\; Y\_\; \{s\},\}$

, после чего все многочлены $f\; \in \; F\; q\; [X]\; \{\backslash \; displaystyle\; f\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; [X]\}$со степенью $k\; -\; Найдено\; 1\; \{\backslash \; displaystyle\; k-1\}$, удовлетворяющее уравнению, полученному при интерполяции. На третьем этапе фактический список ближайших кодовых слов известен путем сокращения подпространства решения, которое занимает $q\; s\; \{\backslash \; displaystyle\; q\; ^\; \{s\}\}$времени.

Гурусвами представляет $n\; \Omega \; (1\; /\; \epsilon \; 2)\; \{\backslash \; displaystyle\; n\; ^\; \{\backslash \; Omega\; (1\; /\; \backslash \; varepsilon\; ^\; \{2\})\; \}\}$алгоритм декодирования временного списка на основе линейной алгебры, который может декодировать свернутый код Рида – Соломона до радиуса $1\; -\; R\; -\; \epsilon \; \{\backslash \; displaystyle\; 1-R-\; \backslash \; varepsilon\}$с размером списка $n\; O\; (1\; /\; \epsilon \; 2)\; \{\backslash \; displaystyle\; \{n\; ^\; \{O\; (1\; /\; \backslash \; varepsilon\; ^\; \{2\})\}\}\}$. В этом алгоритме есть три шага: шаг интерполяции, шаг поиска корня и шаг сокращения. На этапе интерполяции он попытается найти кандидатный многочлен сообщения $f\; (x)\; \{\backslash \; displaystyle\; f\; (x)\}$путем решения линейной системы. На этапе поиска корня он попытается найти подпространство решения, решая другую линейную систему. Последний шаг попытается сократить подпространство решения, полученное на втором шаге. Ниже мы подробно расскажем о каждом шаге.

Шаг 1: Шаг интерполяции

Это интерполяция в стиле Велча – Берлекампа (поскольку ее можно рассматривать как многомерное обобщение метода Велча – Берлекампа алгоритм). Предположим, мы получили кодовое слово $y\; \{\backslash \; displaystyle\; y\}$из $m\; \{\backslash \; displaystyle\; m\}$-складчатого кода Рида – Соломона, как показано ниже

$(\; [y\; 0\; y\; 1\; y\; 2\; \cdots \; ym\; -\; 1],\; [ymym\; +\; 1\; ym\; +\; 2\; \cdots \; y\; 2\; m\; -\; 1],\dots ,\; [yn\; -\; myn\; -\; m\; +\; 1\; yn\; -\; m\; +\; 2\; \cdots \; yn\; -\; 1])\; \{\; \backslash \; displaystyle\; \backslash \; left\; (\{\backslash \; begin\; \{bmatrix\}\; y\_\; \{0\}\; \backslash \backslash \; y\_\; \{1\}\; \backslash \backslash \; y\_\; \{2\}\; \backslash \backslash \backslash \; cdots\; \backslash \backslash \; y\_\; \{m-1\}\; \backslash \; end\; \{bmatrix\}\},\; \{\backslash \; begin\; \{\; bmatrix\}\; y\_\; \{m\}\; \backslash \backslash \; y\_\; \{m\; +\; 1\}\; \backslash \backslash \; y\_\; \{m\; +\; 2\}\; \backslash \backslash \backslash \; cdots\; \backslash \backslash \; y\_\; \{2m-1\}\; \backslash \; end\; \{bmatrix\}\},\; \backslash \; ldots,\; \{\backslash \; begin\; \{bmatrix\}\; y\_\; \{nm\}\; \backslash \backslash \; y\_\; \{n-m\; +\; 1\}\; \backslash \backslash \; y\_\; \{n-m\; +\; 2\}\; \backslash \backslash \backslash \; cdots\; \backslash \backslash \; y\_\; \{n-1\}\; \backslash \; end\; \{bmatrix\}\}\; \backslash \; right)\}$

Мы интерполировать ненулевой многочлен

$Q\; (X,\; Y\; 1,\dots ,\; Y\; s)\; =\; A\; 0\; (X)\; +\; A\; 1\; (X)\; Y\; 1\; +\; \cdots \; +\; A\; s\; (X)\; Y\; s,\; \{deg\; \; (A\; i)\; ⩽\; D\; 1\; ⩽\; я\; ⩽\; s\; град\; \; (A\; 0)\; ⩽\; D\; +\; k\; -\; 1\; \{\backslash \; displaystyle\; Q\; (X,\; Y\_\; \{1\},\; \backslash \; ldots,\; Y\_\; \{s\})\; =\; A\_\; \{0\}\; (X)\; +\; A\_\; \{1\}\; (X)\; Y\_\; \{1\}\; +\; \backslash \; cdots\; +\; A\_\; \{s\}\; (X)\; Y\_\; \{s\},\; \backslash \; qquad\; \{\backslash \; begin\; \{cases\}\; \backslash \; deg\; (A\_\; \{i\})\; \backslash \; leqslant\; D\; 1\; \backslash \; leqslant\; i\; \backslash \; leqslant\; s\; \backslash \backslash \backslash \; deg\; (A\_\; \{0\})\; \backslash \; leqslant\; D\; +\; k-1\; \backslash \; end\; \{cases\}\}\}$

с помощью тщательно подобранного параметра степени $D\; \{\backslash \; displaystyle\; D\}$.

$D\; =\; \lfloor \; N\; (м\; -\; с\; +\; 1)\; -\; к\; +\; 1\; s\; +\; 1\; \rfloor \; \{\backslash \; displaystyle\; D\; =\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{N\; (m-s\; +\; 1)\; -k\; +\; 1\}\; \{s\; +\; 1\}\}\; \backslash \; right\; \backslash \; rfloor\}$

Таким образом, требования к интерполяции будут такими:

$Q\; (\gamma \; im\; +\; j,\; yim\; +\; j,\; yim\; +\; j\; +\; 1,\dots ,\; yim\; +\; j\; +\; s\; -\; 1)\; =\; 0,\; для\; i\; =\; 0,\; 1,\dots ,\; nm\; -\; 1,\; j\; =\; 0,\; 1,\dots ,\; м\; -\; с.\; \{\backslash \; displaystyle\; Q\; \backslash \; left\; (\backslash \; gamma\; ^\; \{im\; +\; j\},\; y\_\; \{im\; +\; j\},\; y\_\; \{im\; +\; j\; +\; 1\},\; \backslash \; ldots,\; y\_\; \{im\; +\; j\; +\; s-1\}\; \backslash \; right)\; =\; 0,\; \backslash \; quad\; \{\backslash \; text\; \{for\}\}\; \backslash \; quad\; i\; =\; 0,1,\; \backslash \; ldots,\; \{\backslash \; tfrac\; \{n\}\; \{m\}\}\; -\; 1,\; j\; =\; 0,1,\; \backslash \; ldots,\; ms.\}$

Тогда количество одночленов в $Q\; (X,\; Y\; 1,\dots ,\; Y\; s)\; \{\backslash \; displaystyle\; Q\; (X,\; Y\_\; \{1\},\; \backslash \; ldots,\; Y\_\; \{s\})\}$равно

$(D\; +\; 1)\; s\; +\; D\; +\; К\; знак\; равно\; (D\; +\; 1)\; (s\; +\; 1)\; +\; к\; -\; 1>N\; (м\; -\; s\; +\; 1)\; \{\backslash \; displaystyle\; (D\; +\; 1)\; s\; +\; D\; +\; k\; =\; (\; D\; +\; 1)\; (s\; +\; 1)\; +\; k-1>N\; (m-s\; +\; 1)\}$

Поскольку количество мономов в $Q\; (X,\; Y\; 1,\dots ,\; Y\; s)\; \{\backslash \; displaystyle\; Q\; (X,\; Y\_\; \{1\},\; \backslash \; ldots,\; Y\_\; \{s\})\}$больше, чем количество условий интерполяции. Ниже мы имеем лемму

Лемма 1. $0\; \ne \; Q\; \in \; F\; q\; [X,\; Y\; 1,\dots ,\; Y\; s]\; \{\backslash \; displaystyle\; 0\; \backslash \; neq\; Q\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; [X,\; Y\_\; \{1\},\; \backslash \; ldots,\; Y\_\; \{s\}]\}$, удовлетворяющее вышеуказанному условию интерполяции, может быть найдено путем решения однородной линейной системы более $F\; q\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\}$с не более чем $N\; m\; \{\backslash \; displaystyle\; Nm\}$ограничениями и переменными. Более того, эту интерполяцию можно выполнить в $O\; (N\; m\; log\; 2\; \; (N\; m)\; log\; \; log\; \; (N\; m))\; \{\backslash \; displaystyle\; O\; (Nm\; \backslash \; log\; ^\; \{2\}\; (Nm)\; \backslash \; log\; \backslash \; log\; (\; Нм))\}$операции над $F\; q\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\}$.

Эта лемма показывает нам, что шаг интерполяции может быть выполнен за почти линейное время.

Сейчас мы обсудили все, что нам нужно для многомерного многочлена $Q\; (X,\; Y\; 1,\dots ,\; Y\; s)\; \{\backslash \; displaystyle\; Q\; (X,\; Y\_\; \{1\},\; \backslash \; ldots,\; Y\_\; \{s\})\}$. Оставшаяся задача - сосредоточиться на многочленах сообщений $f\; (X)\; \{\backslash \; displaystyle\; f\; (X)\}$.

Лемма 2. Если кандидат многочленов сообщений $f\; (X)\; \in \; F\; [X\; ]\; \{\backslash \; displaystyle\; f\; (X)\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; [X]\}$- многочлен степени не выше $k\; -\; 1\; \{\backslash \; displaystyle\; k-1\}$, чья свернутая кодировка Рида-Соломона согласуется с полученным словом $y\; \{\backslash \; displaystyle\; y\}$как минимум в $t\; \{\backslash \; displaystyle\; t\}$столбцах с

$t>D\; +\; k\; -\; 1\; m\; -\; s\; +\; 1,\; \{\backslash \; displaystyle\; t>\{\{D\; +\; k-1\}\; \backslash \; over\; \{m-s\; +\; 1\}\},\}$

затем $Q\; (X,\; f\; (X),\; f\; (\gamma \; X),\dots ,\; f\; (\gamma \; s\; -\; 1\; X))\; =\; 0.\; \{\backslash \; displaystyle\; Q\; (X,\; f\; (\; X),\; е\; (\backslash \; gamma\; X),\; \backslash \; ldots,\; f\; (\backslash \; gamma\; \_\; \{s-1\}\; X))\; =\; 0.\}$

Здесь «согласен» означает, что все $m\; \{\backslash \; displaystyle\; m\}$значения в столбце должны соответствовать соответствующим значениям в кодовом слове $y\; \{\backslash \; displa\; ystyle\; y\}$.

Эта лемма показывает нам, что любой такой многочлен $Q\; (X,\; Y\; 1,\dots ,\; Y\; s)\; \{\backslash \; displaystyle\; Q\; (X,\; Y\_\; \{1\},\; \backslash \; ldots,\; Y\_\; \{s\})\}$представляет алгебраическое условие, которое должно быть выполнено для тех многочленов сообщений $f\; (x)\; \{\backslash \; displaystyle\; f\; (x)\}$, которые нас интересуют в декодировании списка.

Комбинируя лемму 2 и параметр $D\; \{\backslash \; displaystyle\; D\}$, получаем

$t\; (m\; -\; s\; +\; 1)>N\; (m\; -\; s\; +\; 1)\; +\; s\; (к\; -\; 1)\; s\; +\; 1\; \{\backslash \; displaystyle\; t\; (m-s\; +\; 1)>\{\backslash \; frac\; \{N\; (m-s\; +\; 1)\; +\; s\; (k-1)\}\; \{s\; +\; 1\}\}\}$

Далее мы можем получить границу декодирования

$t\; ⩾\; N\; s\; +\; 1\; +\; ss\; +\; 1\; \cdot \; km\; -\; s\; +\; 1\; знак\; равно\; N\; (1\; s\; +\; 1\; +\; ss\; +\; 1\; \cdot \; м\; р\; м\; -\; s\; +\; 1)\; \{\backslash \; displaystyle\; t\; \backslash \; geqslant\; \{\backslash \; frac\; \{N\}\; \{s\; +\; 1\}\}\; +\; \{\backslash \; frac\; \{s\}\; \{s\; +\; 1\; \}\}\; \backslash \; cdot\; \{\backslash \; frac\; \{k\}\; \{m-s\; +\; 1\}\}\; =\; N\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{s\; +\; 1\}\}\; +\; \{\backslash \; frac\; \{s\}\; \{s\; +\; 1\}\}\; \backslash \; cdot\; \{\backslash \; frac\; \{mR\}\; \{m-s\; +\; 1\}\}\; \backslash \; right)\}$

Мы замечаем, что дробное согласие составляет

$1\; s\; +\; 1\; +\; ss\; +\; 1\; \cdot \; m\; R\; m\; -\; s\; +\; 1\; \{\backslash \; displaystyle\; \{\backslash \; dfrac\; \{1\}\; \{s\; +\; 1\}\}\; +\; \{\backslash \; dfrac\; \{s\}\; \{s\; +\; 1\}\}\; \backslash \; cdot\; \{\backslash \; dfrac\; \{mR\}\; \{m-s\; +\; 1\}\}\}$

Шаг 2. Корень -этап поиска

На этом этапе наша задача сосредоточена на том, как найти все многочлены $f\; \in \; F\; q\; [X]\; \{\backslash \; displaystyle\; f\; \backslash \; in\; \{\backslash \; mathbb\; \{F\}\; \_\; \{q\; \}\; [X]\}\}$со степенью не выше $k\; -\; 1\; \{\backslash \; displaystyle\; k-1\}$и удовлетворяет уравнению, полученному на шаге 1, а именно

$A\; 0\; (Икс)\; +\; A\; 1\; (X)\; е\; (Икс)\; +\; A\; 2\; (X)\; f\; (\gamma \; X)\; +\; \cdots \; +\; A\; s\; (X)\; f\; (\gamma \; s\; -\; 1\; X)\; =\; 0\; \{\backslash \; displaystyle\; A\_\; \{0\; \}\; (X)\; +\; A\_\; \{1\}\; (X)\; f\; (X)\; +\; A\_\; \{2\}\; (X)\; f\; (\backslash \; gamma\; X)\; +\; \backslash \; cdots\; +\; A\_\; \{s\}\; (X)\; f\; (\backslash \; gamma\; ^\; \{s-1\; \}\; X)\; =\; 0\}$

Поскольку приведенное выше уравнение образует линейную систему уравнений над $F\; q\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\}$в коэффициентах $f\; 0,\; f\; 1,\dots ,\; fk\; -\; 1\; \{\backslash \; displaystyle\; f\_\; \{0\},\; f\_\; \{1\},\; \backslash \; ldots,\; f\_\; \{k-1\}\}$полинома

$f\; (X)\; =\; е\; 0\; +\; е\; 1\; Икс\; +\; \cdots \; +\; fk\; -\; 1\; Икс\; К\; -\; 1,\; \{\backslash \; displaystyle\; f\; (X)\; =\; f\_\; \{0\}\; +\; f\_\; \{1\}\; X\; +\; \backslash \; cdots\; +\; f\_\; \{k-1\}\; X\; ^\; \{k-1\; \},\}$

решением вышеуказанного уравнения является аффинное подпространство в $F\; qk\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{k\}\}$. Этот факт является ключевым моментом, который дает начало эффективному алгоритму - мы можем решить линейную систему.

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

На самом деле он действительно имеет верхнюю границу, как утверждает лемма ниже.

Лемма 3. Если порядок $\gamma \; \{\backslash \; displaystyle\; \backslash \; gamma\}$не менее $k\; \{\backslash \; displaystyle\; k\}$(в частности когда $\gamma \; \{\backslash \; displaystyle\; \backslash \; gamma\}$является примитивным), тогда размерность решения не превышает $s\; -\; 1\; \{\backslash \; displaystyle\; s-1\}$.

Эта лемма показывает нам верхняя граница размерности пространства решений.

Наконец, на основе приведенного выше анализа мы имеем следующую теорему

Теорема 1. Для свернутого кода Рида – Соломона $FRS\; q\; (m)\; [n,\; k]\; \{\backslash \; displaystyle\; FRS\_\; \{q\}\; ^\; \{(m)\}\; [n,\; k]\}$длины блока $N\; =\; нм\; \{\backslash \; displaystyle\; N\; =\; \{\backslash \; tfrac\; \{n\}\; \{m\}\}\}$и ставка $R\; =\; kn,\; \{\backslash \; displaystyle\; R\; =\; \{\backslash \; tfrac\; \{k\}\; \{n\}\},\}$для всех целых чисел $s,\; 1\; ⩽\; s\; ⩽\; м\; \{\backslash \; Displaystyle\; s,\; 1\; \backslash \; leqslant\; s\; \backslash \; leqslant\; m\}$. Для полученного слова $y\; \in \; (F\; qm)\; N\; \{\backslash \; displaystyle\; y\; \backslash \; in\; (\backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{m\})\; ^\; \{N\}\}$, in $O\; ((N\; m\; log\; \; q)\; 2)\; \{\backslash \; displaystyle\; O\; ((Nm\; \backslash \; log\; q)\; ^\; \{2\})\}$время, можно найти основу для подпространства размерности не более $s\; -\; 1\; \{\backslash \; displaystyle\; s-1\}$, который содержит все многочлены сообщений $f\; \in \; F\; q\; [X]\; \{\backslash \; displaystyle\; f\; \backslash \; in\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; [X\; ]\}$степени меньше $k\; \{\backslash \; displaystyle\; k\}$, чья кодировка FRS отличается от $y\; \{\backslash \; displaystyle\; y\}$не более чем на дробь

$ss\; +\; 1\; (1\; -\; m\; R\; m\; -\; s\; +\; 1)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{s\}\; \{s\; +\; 1\}\}\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{mR\}\; \{m-s\; +\; 1\}\}\; \backslash \; right)\}$

из $N\; \{\backslash \; displaystyle\; N\}$позиций кодового слова.

Когда $s\; =\; m\; =\; 1\; \{\backslash \; displaystyle\; s\; =\; m\; =\; 1\; \}$, мы замечаем, что это сводится к уникальному алгоритму декодирования с точностью до дроби $(1\; -\; R)\; /\; 2\; \{\backslash \; displaystyle\; (1-R)\; /\; 2\}$ошибок. Другими словами, мы можем рассматривать уникальный алгоритм декодирования как особенность алгоритма декодирования списка. Количество составляет примерно $n\; O\; (1\; /\; \epsilon )\; \{\backslash \; displaystyle\; n\; ^\; \{O\; (1\; /\; \backslash \; varepsilon)\}\}$для вариантов выбора параметров, которые достигают радиуса декодирования списка $1.\; -\; R\; -\; \epsilon \; \{\backslash \; displaystyle\; 1-R-\; \backslash \; varepsilon\}$.

Теорема 1 точно говорит нам, насколько велик будет радиус ошибки.

Теперь мы наконец получили подпространство решения. Однако остается еще одна проблема. Размер списка в худшем случае равен $n\; \Omega \; (1\; /\; \epsilon )\; \{\backslash \; displaystyle\; n\; ^\; \{\backslash \; Omega\; (1\; /\; \backslash \; varepsilon)\}\}$. Но фактический список ближайших кодовых слов - это лишь небольшой набор в этом подпространстве. Итак, нам нужен какой-то процесс, чтобы обрезать подпространство, чтобы сузить его. Этот процесс сокращения занимает $q\; s\; \{\backslash \; displaystyle\; q\; ^\; \{s\}\}$времени в худшем случае. К сожалению, не известно, как улучшить время выполнения, потому что мы не знаем, как улучшить границу размера списка для свернутого кода Рида-Соломона.

Все станет лучше, если мы изменим код, тщательно выбрав подмножество всех возможных степеней $k\; -\; 1\; \{\backslash \; displaystyle\; k-1\}$многочленов в виде сообщений, размер списка показывает быть намного меньше, только немного теряя в скорости. Мы кратко поговорим об этом на следующем шаге.

Шаг 3: Шаг сокращения

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

На шаге 2 было упомянуто, что если тщательно выбрать в качестве сообщений только подмножество всех возможных степеней $k\; -\; 1\; \{\backslash \; displaystyle\; k-1\}$полиномов, размер списка можно значительно уменьшить. Здесь мы расширим наше обсуждение.

Для достижения этой цели идея состоит в том, чтобы ограничить вектор коэффициентов $(f\; 0,\; f\; 1,\dots ,\; fk\; -\; 1)\; \{\backslash \; displaystyle\; (f\_\; \{0\},\; f\_\; \{1\},\; \backslash \; ldots,\; f\_\; \{k-1\})\}$в специальное подмножество $\nu \; \subseteq \; F\; qk\; \{\backslash \; displaystyle\; \backslash \; nu\; \backslash \; substeq\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{k\}\}$, который удовлетворяет следующим двум условиям:

Условие 1. Набор $\nu \; \{\backslash \; displaystyle\; \backslash \; nu\}$должен быть достаточно большим ($|\; \nu \; |\; \ge \; q\; (1\; -\; \epsilon )\; k\; \{\backslash \; displaystyle\; |\; \backslash \; nu\; |\; \backslash \; geq\; q\; ^\; \{(1-\; \backslash \; varepsilon)\; k\}\}$).

Это необходимо для того, чтобы убедиться, что скорость будет уменьшена не более чем в $раз\; (1\; -\; \epsilon )\; \{\backslash \; displaystyle\; (1-\; \backslash \; varepsilon)\}$.

Условие 2. Набор $\nu \; \{\backslash \; displaystyle\; \backslash \; nu\}$должен иметь низкое пересечение с любым подпространством $S\; \{\backslash \; displaystyle\; S\}$размерности $s\; \{\backslash \; displaystyle\; s\}$удовлетворяет $S\; \subset \; F\; qk\; \{\backslash \; displaystyle\; S\; \backslash \; subset\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\; ^\; \{k\}\}$и $|\; S\; \cap \; \nu \; |\; ⩽\; L.\; \{\backslash \; displaystyle\; |\; S\; \backslash \; cap\; \backslash \; nu\; |\; \backslash \; leqslant\; L.\}$Такой подмножество называется подмножеством, уклоняющимся от подпространства.

Граница размера списка в худшем случае равна $n\; \Omega \; (1\; /\; \epsilon )\; \{\backslash \; displaystyle\; n\; ^\; \{\backslash \; Omega\; (1\; /\; \backslash \; varepsilon)\}\}$, и ее можно уменьшить к относительной малой границе $O\; (1\; /\; \epsilon \; 2)\; \{\backslash \; displaystyle\; O\; (1\; /\; \backslash \; varepsilon\; ^\; \{2\})\}$с помощью подмножеств с уклонением от подпространства.

На этом этапе, поскольку он должен проверить каждый элемент подпространства решения, которое мы получаем на этапе 2, требуется $qs\; \{\backslash \; displaystyle\; q\; ^\; \{s\}\}$времени в худшем случае ($s\; \{\backslash \; displaystyle\; s\}$- размер подпространства решения).

Двир и Ловетт улучшили результат на основе работы Гурусвами, который может уменьшить размер списка до постоянного.

Здесь представлена ​​только идея, которая используется для сокращения подпространства решения. Для получения подробной информации о процессе обрезки, пожалуйста, обратитесь к статьям Гурусвами, Двира и Ловетта, которые перечислены в ссылке.

Резюме

Если мы не рассматриваем шаг 3, этот алгоритм может работать в квадратичном времени. Краткое описание этого алгоритма приведено ниже.

Обзор алгоритма декодирования линейно-алгебраического списка для кода FRS

Шаги	Интерполяция Поиск корня Prune
Время выполнения	$n\; \Omega \; (1\; /\; \epsilon \; 2)\; \{\backslash \; displaystyle\; n\; ^\; \{\backslash \; Omega\; (1\; /\; \backslash \; varepsilon\; ^\; \{2\})\}\}$
Радиус ошибки	$1\; -\; R\; -\; \epsilon \; \{\backslash \; displaystyle\; 1-R-\; \backslash \; varepsilon\}$
Размер списка	$n\; O\; (1\; /\; \epsilon \; 2)\; \{\backslash \; displaystyle\; n\; ^\; \{O\; (1\; /\; \backslash \; varepsilon\; ^\; \{2\})\}\}$

• Исправление ошибок Рида – Соломона
• Граница синглтона
• Теория кодирования
• Расшифровка списка

1. Лекционные заметки Атри Рудры : Свернутые коды Рида – Соломона
2. Лекционные заметки Атри Рудры: Границы
3. Статья автор Атри Рудра и Венкатесан Гурусвами : Декодирование свернутых кодов Рида – Соломона
4. Глава о декодировании списком свернутых кодов Рида – Соломона: Списочное декодирование сложенных кодов Коды Рида – Соломона
5. Заметки к лекциям Венкатесана Гурусвами: Элементарные ограничения кодов
6. Заметки к лекциям Венкатесана Гурусвами: Список декодирования сложенных кодов Рида-Соломона
7. Гурусвами, Венкатеса п (2011). "Линейно-алгебраическое списочное декодирование свернутых кодов Рида – Соломона". 26-я ежегодная конференция IEEE 2011 г. по вычислительной сложности: 77–85. arXiv : 1106.0436. Bibcode : 2011arXiv1106.0436G. DOI : 10.1109 / CCC.2011.22. ISBN 978-1-4577-0179-5.
8. Двирл, Зеев; Ловетт, Шахар (2011). «Подпространственные уклоняющиеся множества». arXiv : 1110.5696 [cs.CC ].
9. Докторская диссертация Кристиана Брандера : Интерполяция и декодирование списком алгебраических кодов
10. Крачковский, В. Я. (2003). «Коды Рида – Соломона для исправления фазированных пакетов ошибок». IEEE Trans. Инф. Теория. 49 (11): 2975–2984. doi :10.1109/TIT.2003.819333.