Обобщенное декодирование минимального расстояния

В теории кодирования декодирование на обобщенном минимальном расстоянии (GMD) обеспечивает эффективный алгоритм декодирования составных кодов , который основан на использовании декодера ошибок и стираний для внешнего кода .

Наивный алгоритм декодирования составных кодов не может быть оптимальным способом декодирования, поскольку не учитывает информацию, которую дает декодирование максимального правдоподобия (MLD). Другими словами, в простом алгоритме внутренние полученные кодовые слова обрабатываются одинаково, независимо от разницы между их расстояниями Хэмминга . Интуитивно понятно, что внешний декодер должен с большей уверенностью относиться к символам, внутренняя кодировка которых близка к полученному слову. Дэвид Форни в 1966 году разработал лучший алгоритм, называемый декодированием на обобщенном минимальном расстоянии (GMD), который лучше использует эту информацию. Этот метод достигается путем измерения достоверности каждого полученного кодового слова и стирания символов, достоверность которых ниже желаемого значения. Алгоритм декодирования GMD был одним из первых примеров декодеров с мягким решением . Мы представим три версии алгоритма декодирования GMD. Первые два будут рандомизированными алгоритмами , а последний — детерминированным .

Настраивать

• Расстояние Хэмминга : даны два вектора. $u,v\in \Sigma ^{n}$ расстояние Хэмминга между $u$ и $v$, обозначенный $\Delta (u,v)$, определяется как количество позиций, в которых $u$ и $v$ различаются.
• Минимальное расстояние: Пусть $C\subseteq \Sigma ^{n}$ быть кодом . Минимальное расстояние кода $C$ определяется как $d=\min \Delta (c_{1},c_{2})$ где $c_{1}\neq c_{2}\in C$
• Конкатенация кода: задано $m=(m_{1},\cdots ,m_{K})\in [Q]^{K}$, рассмотрим два кода, которые мы называем внешним кодом и внутренним кодом.

$C_{\text{out}}=[Q]^{K}\to [Q]^{N},\qquad C_{\text{in}}:[q]^{k}\to [q]^{n},$

и их расстояния $D$ и $d$. Объединенный код может быть получен путем $C_{\text{out}}\circ C_{\text{in}}(m)=(C_{\text{in}}(C_{\text{out}}(m)_{1}),\ldots ,C_{\text{in}}(C_{\text{out}}(m)_{N}))$ где $C_{\text{out}}(m)=((C_{\text{out}}(m)_{1},\ldots ,(m)_{N})).$ Наконец мы возьмем $C_{\text{out}}$ быть кодом RS , который имеет декодер ошибок и стирания, и $K=O(\log N)$, что, в свою очередь, означает, что MLD внутреннего кода будет полиномиальным по $N$ время.

• Декодирование максимального правдоподобия (MLD): MLD — это метод декодирования кодов с исправлением ошибок, который выводит кодовое слово, ближайшее к полученному слову на расстоянии Хэмминга. Функция MLD, обозначаемая $D_{MLD}:\Sigma ^{n}\to C$ определяется следующим образом. Для каждого $y\in \Sigma ^{n},D_{MLD}(y)=\arg \min _{c\in C}\Delta (c,y)$.
• Функция плотности вероятности : распределение вероятностей $\Pr$ на выборочном пространстве $S$ представляет собой отображение событий $S$ к действительным числам таким, что $\Pr[A]\geq 0$ для любого мероприятия $A,\Pr[S]=1$, и $\Pr[A\cup B]=\Pr[A]+\Pr[B]$ для любых двух взаимоисключающих событий $A$ и $B$
• Ожидаемое значение : ожидаемое значение дискретной случайной величины. $X$ является

$\mathbb {E} [X]=\sum _{x}\Pr[X=x].$

Рандомизированный алгоритм

Рассмотрим полученное слово $\mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}$ который был поврежден шумным каналом . Ниже приводится описание алгоритма для общего случая. В этом алгоритме мы можем декодировать y, просто объявляя стирание в каждой плохой позиции и запуская алгоритм декодирования ошибок и стирания для $C_{\text{out}}$ на результирующем векторе.

Рандомизированный_декодер
Данный : $\mathbf {y} =(y_{1},\dots ,y_{N})\in [q^{n}]^{N}$.

1. Для каждого $1\leq i\leq N$, вычислить $y_{i}'=MLD_{C_{\text{in}}}(y_{i})$.
2. Набор $\omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}})$.
3. Для каждого $1\leq i\leq N$, повтор: С вероятностью $2\omega _{i} \over d$, набор $y_{i}''\leftarrow ?,$ в противном случае установить $y_{i}''=y_{i}'$.
4. Ошибки запуска и алгоритм стирания для $C_{\text{out}}$ на $\mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')$.

Теорема 1. Пусть y — полученное слово такое, что существует кодовое слово $\mathbf {c} =(c_{1},\cdots ,c_{N})\in C_{\text{out}}\circ {C_{\text{in}}}\subseteq [q^{n}]^{N}$ такой, что $\Delta (\mathbf {c} ,\mathbf {y} )<{\tfrac {Dd}{2}}$. Тогда детерминированный алгоритм GMD выдает $\mathbf {c}$.

Обратите внимание, что простой алгоритм декодирования составных кодов может корректировать до ${\tfrac {Dd}{4}}$ ошибки.

Лемма 1. Пусть выполнены предположения теоремы 1. И если $\mathbf {y} ''$ имеет $e'$ ошибки и $s'$ стирания (по сравнению с $\mathbf {c}$) после шага 1 , тогда $\mathbb {E} [2e'+s']<D.$

Замечание. Если $2e'+s'<D$, то алгоритм на шаге 2 выведет $\mathbf {c}$. Лемма выше говорит, что в ожидании это действительно так. Обратите внимание, что этого недостаточно для доказательства теоремы 1 , но может иметь решающее значение при разработке будущих вариантов алгоритма.

Доказательство леммы 1. Для каждого $1\leq i\leq N,$ определять $e_{i}=\Delta (y_{i},c_{i}).$ Это означает, что

$$\sum _{i=1}^{N}e_{i}<{\frac {Dd}{2}}\qquad \qquad (1)$$ Далее для каждого $1\leq i\leq N$мы определяем две индикаторные переменные :

$${\begin{aligned}X{_{i}^{?}}=1&\Leftrightarrow y_{i}''=?\\X{_{i}^{e}}=1&\Leftrightarrow C_{\text{in}}(y_{i}'')\neq c_{i}\ {\text{and}}\ y_{i}''\neq ?\end{aligned}}$$ Мы утверждаем, что закончили, если сможем показать, что для каждого $1\leq i\leq N$:

$$\mathbb {E} \left[2X{_{i}^{e}+X{_{i}^{?}}}\right]\leqslant {2e_{i} \over d}\qquad \qquad (2)$$ Понятно, что по определению

$$e'=\sum _{i}X_{i}^{e}\quad {\text{and}}\quad s'=\sum _{i}X_{i}^{?}.$$ Далее, в силу линейности ожидания, получаем

$$\mathbb {E} [2e'+s']\leqslant {\frac {2}{d}}\sum _{i}e_{i}<D.$$ Для доказательства (2) рассмотрим два случая: $i$-й блок правильно декодирован ( Случай 1 ), $i$-й блок неправильно декодирован ( Случай 2 ):

Случай 1: $(c_{i}=C_{\text{in}}(y_{i}'))$

Обратите внимание, что если $y_{i}''=?$ затем $X_{i}^{e}=0$, и $\Pr[y_{i}''=?]={\tfrac {2\omega _{i}}{d}}$ подразумевает $\mathbb {E} [X_{i}^{?}]=\Pr[X_{i}^{?}=1]={\tfrac {2\omega _{i}}{d}},$ и $\mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=0$.

Далее, по определению имеем

$$\omega _{i}=\min \left(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}}\right)\leqslant \Delta (C_{\text{in}}(y_{i}'),y_{i})=\Delta (c_{i},y_{i})=e_{i}$$ Случай 2: $(c_{i}\neq C_{\text{in}}(y_{i}'))$

В этом случае, $\mathbb {E} [X_{i}^{?}]={\tfrac {2\omega _{i}}{d}}$ и $\mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=1-{\tfrac {2\omega _{i}}{d}}.$

С $c_{i}\neq C_{\text{in}}(y_{i}'),e_{i}+\omega _{i}\geqslant d$. Это следует за другим анализом случая , когда $(\omega _{i}=\Delta (C_{\text{in}}(y_{i}'),y_{i})<{\tfrac {d}{2}})$ или нет.

Наконец, это подразумевает

$$\mathbb {E} [2X_{i}^{e}+X_{i}^{?}]=2-{2\omega _{i} \over d}\leq {2e_{i} \over d}.$$ В следующих разделах мы, наконец, покажем, что детерминированная версия приведенного выше алгоритма может выполнять уникальное декодирование $C_{\text{out}}\circ C_{\text{in}}$ до половины расчетного расстояния.

Модифицированный рандомизированный алгоритм

Обратите внимание, что в предыдущей версии алгоритма GMD на шаге «3» нам не обязательно использовать «свежую» случайность для каждого $i$. Теперь мы придумаем еще одну рандомизированную версию алгоритма GMD, которая использует одну и ту же случайность для каждого $i$. Эта идея следует алгоритму, приведенному ниже.

Модифицированный_рандомизированный_декодер
Данный : $\mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}$, выбирать $\theta \in [0,1]$ случайным образом. Тогда каждый за каждый $1\leq i\leq N$:

1. Набор $y_{i}'=MLD_{C_{\text{in}}}(y_{i})$.
2. Вычислить $\omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})$.
3. Если $\theta <{\tfrac {2\omega _{i}}{d}}$, набор $y_{i}''\leftarrow ?,$ в противном случае установить $y_{i}''=y_{i}'$.
4. Ошибки запуска и алгоритм стирания для $C_{\text{out}}$ на $\mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')$.

Для доказательства леммы 1 мы используем случайность только для того, чтобы показать, что

$$\Pr[y_{i}''=?]={2\omega _{i} \over d}.$$ В этой версии алгоритма GMD отметим, что

$$\Pr[y_{i}''=?]=\Pr \left[\theta \in \left[0,{\tfrac {2\omega _{i}}{d}}\right]\right]={\tfrac {2\omega _{i}}{d}}.$$ Второе равенство следует из выбора $\theta$. Доказательство леммы 1 можно использовать и для того, чтобы показать $\mathbb {E} [2e'+s']<D$ для версии 2 GMD. В следующем разделе мы увидим, как получить детерминированную версию алгоритма GMD, выбрав $\theta$ из набора полиномиального размера в отличие от текущего бесконечного набора $[0,1]$.

Детерминированный алгоритм

Позволять $Q=\{0,1\}\cup \{{2\omega _{1} \over d},\ldots ,{2\omega _{N} \over d}\}$. Поскольку для каждого $i,\omega _{i}=\min(\Delta (\mathbf {y_{i}'} ,\mathbf {y_{i}} ),{d \over 2})$, у нас есть

$$Q=\{0,1\}\cup \{q_{1},\ldots ,q_{m}\}$$ где $q_{1}<\cdots <q_{m}$ для некоторых $m\leq \left\lfloor {\frac {d}{2}}\right\rfloor$. Обратите внимание, что для каждого $\theta \in [q_{i},q_{i+1}]$, шаг 1 второй версии рандомизированного алгоритма выдает то же самое $\mathbf {y} ''.$. Таким образом, нам необходимо рассмотреть все возможные значения $\theta \in Q$. Это дает детерминированный алгоритм ниже.

Детерминированный_декодер
Данный : $\mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}$, для каждого $\theta \in Q$, повторите следующее.

1. Вычислить $y_{i}'=MLD_{C_{\text{in}}}(y_{i})$ для $1\leq i\leq N$.
2. Набор $\omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})$ для каждого $1\leq i\leq N$.
3. Если $\theta <{2\omega _{i} \over d}$, набор $y_{i}''\leftarrow ?,$ в противном случае установить $y_{i}''=y_{i}'$.
4. Запустите алгоритм устранения ошибок и стираний для $C_{\text{out}}$ на $\mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')$. Позволять $c_{\theta }$ быть кодовым словом в $C_{\text{out}}\circ C_{\text{in}}$ соответствующий выходу алгоритма, если таковой имеется.
5. Среди всех $c_{\theta }$ выведите в 4, выведите тот, который ближе всего к $\mathbf {y}$

Каждый цикл от 1 до 4 может выполняться за полиномиальное время . Приведенный выше алгоритм также можно вычислить за полиномиальное время. В частности, каждый вызов декодера ошибок и стираний $<dD/2$ ошибки принимает $O(d)$ время. Наконец, время выполнения приведенного выше алгоритма равно $O(NQn^{O(1)}+NT_{\text{out}})$ где $T_{\text{out}}$ — время работы декодера внешних ошибок и стираний.

См. также

• Составные коды
• Исправление ошибок Рида Соломона
• Алгоритм Уэлча Берлекэмпа

Ссылки

• Конспект лекций по теории кодирования в Университете Буффало - Атри Рудра
• Конспекты лекций Массачусетского технологического института по основной теории кодирования - Мадху Судан
• Вашингтонский университет – Венкатесан Гурусвами
• Дж. Дэвид Форни. Обобщенное декодирование минимального расстояния. Транзакции IEEE по теории информации , 12:125–131, 1966 г.