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

В теории кодирования декодирование на обобщенном минимальном расстоянии (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\leq i\leq N$ , вычислить $y_{i}'=MLD_{C_{\text{in}}}(y_{i})$ .
Набор $\omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}})$ .
Для каждого $1\leq i\leq N$ , повтор: С вероятностью $2\omega _{i} \over d$ , набор $y_{i}''\leftarrow ?,$ в противном случае установить $y_{i}''=y_{i}'$ .
Ошибки запуска и алгоритм стирания для $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$ :

Набор $y_{i}'=MLD_{C_{\text{in}}}(y_{i})$ .
Вычислить $\omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})$ .
Если $\theta <{\tfrac {2\omega _{i}}{d}}$ , набор $y_{i}''\leftarrow ?,$ в противном случае установить $y_{i}''=y_{i}'$ .
Ошибки запуска и алгоритм стирания для $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$ , повторите следующее.

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

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