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

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

Обозначение

${\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{ sent}}\mid x{\mbox{ received}})}$

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

Соглашения о декодировании

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

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

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

Дальнейшая информация: Максимальная вероятность

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

${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$,

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

${\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}}}$

который (поскольку п меньше половины) максимизируется за счет минимизации 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}}<|C|\\\end{matrix}}}$

только (для двоичного кода). Таблица приведена против предварительно вычисленных значений ${\displaystyle He}$ для всех возможных шаблонов ошибок ${\displaystyle e\in \mathbb {F} _{2}^{n}}$.

Зная, что ${\displaystyle e}$ есть, тогда расшифровать ${\displaystyle x}$ в качестве:

${\displaystyle x=z-e}$

За Двоичный коды, если оба ${\displaystyle k}$ и ${\displaystyle n-k}$ не слишком велики, и если предположить, что матрица генерации кода имеет стандартную форму, синдромное декодирование может быть вычислено с использованием 2 предварительно вычисленных таблиц поиска и только 2 XOR. ^[4]

Позволять ${\displaystyle z}$ быть принятым зашумленным кодовым словом, т.е. ${\displaystyle z=x\oplus e}$. Использование таблицы поиска кодировки размера ${\displaystyle 2^{k}}$, кодовое слово ${\displaystyle z'}$ что соответствует первому ${\displaystyle k}$ кусочки ${\displaystyle z}$ находится.

Затем синдром рассчитывается как последний ${\displaystyle n-k}$ кусочки ${\displaystyle s=z\oplus z'}$ (первый ${\displaystyle k}$ биты XOR равны нулю [поскольку порождающая матрица имеет стандартную форму] и отбрасываются). Используя синдром, ошибка ${\displaystyle e}$ вычисляется с использованием поисковой таблицы синдромов размера ${\displaystyle 2^{n-k}}$, а затем декодирование вычисляется через ${\displaystyle x=z\oplus e}$ (для кодового слова или первого ${\displaystyle k}$ кусочки ${\displaystyle x}$ за исходное слово).

Количество записей в двух таблицах поиска равно ${\displaystyle 2^{k}+2^{n-k}}$, что значительно меньше, чем ${\displaystyle 2^{n}}$ требующийся для стандартное декодирование массива это требует только ${\displaystyle 1}$ искать. Кроме того, для кодирования можно использовать предварительно вычисленную справочную таблицу кодирования, и поэтому ее часто бывает полезно иметь.

Расшифровка набора информации

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

Простейшая форма принадлежит Прейнджу: пусть ${\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}}}$.

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

Максимальная вероятность частичного ответа

Основная статья: PRML

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

Декодер Витерби

Основная статья: Декодер Витерби

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

Смотрите также

• Плевать будильник
• Обнаружение и исправление ошибок
• Запрещенный ввод

Источники

• Хилл, Раймонд (1986). Первый курс теории кодирования. Oxford Applied Mathematics and Computing Science Series. Oxford University Press. ISBN  978-0-19-853803-5.
• Плесс, Вера (1982). Введение в теорию кодов с исправлением ошибок. Серия Wiley-Interscience по дискретной математике. Джон Уайли и сыновья. ISBN  978-0-471-08684-0.
• J.H. ван Линт (1992). Введение в теорию кодирования. GTM. 86 (2-е изд.). Springer-Verlag. ISBN  978-3-540-54894-2.

Рекомендации

1. Фельдман, Джон; Уэйнрайт, Мартин Дж .; Каргер, Дэвид Р. (март 2005 г.). «Использование линейного программирования для декодирования двоичных линейных кодов». IEEE Transactions по теории информации. 51 (3). С. 954–972. Дои:10.1109 / TIT.2004.842696.
2. Aji, Srinivas M .; МакЭлис, Роберт Дж. (Март 2000 г.). «Обобщенный распределительный закон» (PDF). IEEE Transactions по теории информации. 46 (2): 325–343. Дои:10.1109/18.825794.
3. Альбрехт Бойтельшпахер И Уте Розенбаум (1998) Проективная геометрия, стр. 190, Издательство Кембриджского университета ISBN  0-521-48277-1
4. Джек Кейл Вольф (2008) Введение в коды исправления ошибок, Курс: Коммуникационные системы III, UCSD, http://circuit.ucsd.edu/~yhk/ece154c-spr17/pdfs/ErrorCorrectionI.pdf
5. Жак Стерн (1989). «Метод поиска кодовых слов небольшого веса». Теория кодирования и приложения. Конспект лекций по информатике. 388. Springer Verlag. С. 106–113. Дои:10.1007 / BFb0019850. ISBN  978-3-540-51643-9. Отсутствует или пусто | название = (помощь)
6. Охта, Кадзуо; Пей, Динъи (1998). Охта, Кадзуо; Пей, Динъи (ред.). Криптоанализ исходной криптосистемы Мак-Элиса. Достижения в криптологии - ASIACRYPT'98. Конспект лекций по информатике. 1514. С. 187–199. Дои:10.1007/3-540-49649-1. ISBN  978-3-540-65109-3. S2CID  37257901.