Методы декодирования

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

${\displaystyle C\subset \mathbb {F} _{2}^{n}}$считается двоичным кодом длиной ; должно быть элементов ; и — расстояние между этими элементами.${\displaystyle n}$${\displaystyle x,y}$${\displaystyle \mathbb {F} _{2}^{n}}$${\displaystyle d(x,y)}$

Можно дать сообщение , тогда идеальный наблюдатель декодирует кодовое слово . Результатом процесса является следующее решение:${\displaystyle x\in \mathbb {F} _{2}^{n}}$${\displaystyle y\in C}$

${\displaystyle \mathbb {P} (y{\mbox{ отправлено}}\mid x{\mbox{ получено}})}$

Например, человек может выбрать кодовое слово , которое с наибольшей вероятностью будет получено в качестве сообщения после передачи.${\displaystyle у}$${\displaystyle x}$

Каждое кодовое слово не имеет ожидаемой возможности: может быть более одного кодового слова с равной вероятностью мутации в полученное сообщение. В таком случае отправитель и получатель(и) должны заранее договориться о соглашении декодирования. Популярные соглашения включают:

1. Запросить повторную отправку кодового слова – автоматический повторный запрос .
2. Выберите любое случайное кодовое слово из набора наиболее вероятных кодовых слов, которое ближе к указанному.
3. Если следует другой код , отметьте неоднозначные биты кодового слова как стирания и надейтесь, что внешний код устранит их неоднозначность.
4. Сообщить системе об ошибке декодирования

При наличии полученного вектора максимального правдоподобия декодирование выбирает кодовое слово , которое максимизирует${\displaystyle x\in \mathbb {F} _{2}^{n}}$ ${\displaystyle y\in C}$

${\displaystyle \mathbb {P} (x{\mbox{ получено}}\mid y{\mbox{ отправлено}})}$,

то есть кодовое слово , которое максимизирует вероятность того, что было получено, учитывая, что было отправлено. Если все кодовые слова одинаково вероятно будут отправлены, то эта схема эквивалентна декодированию идеального наблюдателя. Фактически, по теореме Байеса ,${\displaystyle у}$${\displaystyle x}$ ${\displaystyle у}$

${\displaystyle {\begin{aligned}\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})&{}={\frac {\mathbb {P} (x{\mbox{ received}},y{\mbox{ sent}})}{\mathbb {P} (y{\mbox{ sent}})}}\\&{}=\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})\cdot {\frac {\mathbb {P} (x{\mbox{ received}})}{\mathbb {P} (y{\mbox{ sent}})}}.\end{aligned}}}$

При фиксации , реструктурируется и является константой, поскольку все кодовые слова с равной вероятностью будут отправлены. Следовательно, максимизируется как функция переменной именно тогда, когда максимизируется, и утверждение следует.${\displaystyle \mathbb {P} (x{\mbox{ received}})}$${\displaystyle x}$${\displaystyle \mathbb {P} (y{\mbox{ sent}})}$${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$${\displaystyle y}$${\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}$

Как и в случае декодирования идеальным наблюдателем, необходимо согласовать соглашение для неуникального декодирования.

Задача декодирования максимального правдоподобия также может быть смоделирована как задача целочисленного программирования . ^[1]

Алгоритм декодирования максимального правдоподобия является примером проблемы «маргинализации функции произведения», которая решается путем применения обобщенного закона распределения . ^[2]

При наличии полученного кодового слова декодирование по минимальному расстоянию выбирает кодовое слово, минимизирующее расстояние Хэмминга :${\displaystyle x\in \mathbb {F} _{2}^{n}}$${\displaystyle y\in C}$

${\displaystyle d(x,y)=\#\{i:x_{i}\not =y_{i}\}}$

т.е. выбрать кодовое слово , максимально близкое к .${\displaystyle y}$${\displaystyle x}$

Обратите внимание, что если вероятность ошибки на дискретном канале без памяти строго меньше половины, то декодирование по минимальному расстоянию эквивалентно декодированию по максимальному правдоподобию , поскольку если${\displaystyle p}$

${\displaystyle d(x,y)=d,\,}$

затем:

${\displaystyle {\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{n-d}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}}$

который (поскольку p меньше половины) максимизируется путем минимизации d .

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

1. Вероятность возникновения ошибки не зависит от положения символа.${\displaystyle p}$
2. Ошибки являются независимыми событиями — ошибка в одной позиции сообщения не влияет на другие позиции.

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

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

Синдромное декодирование — это высокоэффективный метод декодирования линейного кода по шумному каналу , т. е. по каналу, в котором допускаются ошибки. По сути, синдромное декодирование — это декодирование с минимальным расстоянием с использованием сокращенной таблицы поиска. Это допускается линейностью кода. ^[3]

Предположим, что — линейный код длины и минимального расстояния с матрицей проверки на четность . Тогда очевидно, что он способен исправлять до${\displaystyle C\subset \mathbb {F} _{2}^{n}}$${\displaystyle n}$${\displaystyle d}$ ${\displaystyle H}$${\displaystyle C}$

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }$

ошибки, допущенные каналом (поскольку если допущено не более ошибок, то декодирование на минимальном расстоянии все равно правильно декодирует неправильно переданное кодовое слово).${\displaystyle t}$

Теперь предположим, что кодовое слово отправлено по каналу и происходит шаблон ошибки. Затем получено. Обычное декодирование минимального расстояния будет искать вектор в таблице размера для ближайшего совпадения - т.е. элемента (не обязательно уникального) с${\displaystyle x\in \mathbb {F} _{2}^{n}}$${\displaystyle e\in \mathbb {F} _{2}^{n}}$${\displaystyle z=x+e}$${\displaystyle z}$${\displaystyle |C|}$${\displaystyle c\in C}$

${\displaystyle d(c,z)\leq d(y,z)}$

для всех . Синдромное декодирование использует свойство матрицы четности, которое:${\displaystyle y\in C}$

${\displaystyle Hx=0}$

для всех . Синдром полученного определяется как:${\displaystyle x\in C}$${\displaystyle z=x+e}$

${\displaystyle Hz=H(x+e)=Hx+He=0+He=He}$

Для выполнения ML-декодирования в двоичном симметричном канале необходимо найти предварительно вычисленную таблицу размера , соответствующую .${\displaystyle 2^{n-k}}$${\displaystyle He}$${\displaystyle e}$

Обратите внимание, что это уже значительно менее сложно, чем стандартное декодирование массива .

Однако, если предположить, что во время передачи было допущено не более ошибок, получатель может найти значение в еще более сокращенной таблице размера${\displaystyle t}$${\displaystyle He}$

${\displaystyle {\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}\\\end{matrix}}}$

Это семейство вероятностных методов Лас-Вегаса , основанных на наблюдении, что легче угадать достаточное количество позиций без ошибок, чем угадать все позиции с ошибками.

Простейшая форма принадлежит Прейнджу: Пусть будет генераторной матрицей используемой для кодирования. Выбираем столбцы случайным образом и обозначаем соответствующей подматрицей . С разумной вероятностью будет иметь полный ранг, что означает, что если мы позволим быть подвектором для соответствующих позиций любого кодового слова для сообщения , мы можем восстановить как . Следовательно, если нам повезло, что эти позиции полученного слова не содержали ошибок и, следовательно, совпадали с позициями отправленного кодового слова, то мы можем декодировать.${\displaystyle G}$${\displaystyle k\times n}$${\displaystyle C}$${\displaystyle k}$${\displaystyle G}$${\displaystyle G'}$${\displaystyle G}$${\displaystyle G'}$${\displaystyle c'}$${\displaystyle c=mG}$${\displaystyle C}$${\displaystyle m}$${\displaystyle m}$${\displaystyle m=c'G'^{-1}}$${\displaystyle k}$${\displaystyle y}$

Если произошли ошибки, вероятность такого удачного выбора столбцов определяется как .${\displaystyle t}$${\displaystyle \textstyle {\binom {n-t}{k}}/{\binom {n}{k}}}$

Этот метод был усовершенствован различными способами, например, Стерном ^[4] , Канто и Сендрие ^{[5] .}

Метод максимального правдоподобия с частичным откликом ( PRML ) — это метод преобразования слабого аналогового сигнала с головки магнитного диска или ленточного накопителя в цифровой сигнал.

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

Оптимальный алгоритм декодирования решений (ODDA) для асимметричной системы TWRC. ^{[ необходимо разъяснение ] [6]}

• Сигнализация "Не волнуйся"
• Обнаружение и исправление ошибок
• Запрещенный вход

• Хилл, Рэймонд (1986). Первый курс по теории кодирования . Oxford Applied Mathematics and Computing Science Series. Oxford University Press . ISBN 978-0-19-853803-5.
• Плесс, Вера (1982). Введение в теорию кодов, исправляющих ошибки . Серия Wiley-Interscience по дискретной математике. John Wiley & Sons . ISBN 978-0-471-08684-0.
• ван Линт, Якобус Х. (1992). Введение в теорию кодирования . Graduate Texts in Mathematics (GTM). Том 86 (2-е изд.). Springer-Verlag . ISBN 978-3-540-54894-2.