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

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

Обозначения

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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

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

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

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

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

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

то есть выбрать кодовое слово $y$ это максимально близко к $x$ .

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

d(x,y)=d,\,

затем:

{\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 .

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

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

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

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

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

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

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

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

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

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

d(c,z)\leq d(y,z)

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

Hx=0

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

Hz=H(x+e)=Hx+He=0+He=He

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

Заметим, что это уже существенно меньшая сложность, чем декодирование стандартного массива .

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

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

Декодирование списка

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

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

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

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

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

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

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

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

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

Алгоритм декодирования оптимального решения (ODDA)

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

См. также

Ссылки

^ Фельдман, Джон; Уэйнрайт, Мартин Дж.; Каргер, Дэвид Р. (март 2005 г.). «Использование линейного программирования для декодирования двоичных линейных кодов». Транзакции IEEE по теории информации . 51 (3): 954–972. CiteSeerX 10.1.1.111.6585 . дои : 10.1109/TIT.2004.842696 . S2CID 3120399 .
^ Аджи, Шринивас М.; МакЭлис, Роберт Дж. (март 2000 г.). «Обобщенный распределительный закон» (PDF) . Транзакции IEEE по теории информации . 46 (2): 325–343. дои : 10.1109/18.825794 .
^ Бойтельспехер, Альбрехт ; Розенбаум, Юте (1998). Проективная геометрия . Издательство Кембриджского университета . п. 190. ИСБН 0-521-48277-1 .
^ Стерн, Жак (1989). «Метод поиска кодовых слов малого веса». Теория кодирования и ее приложения . Конспекты лекций по информатике. Том. 388. Шпрингер-Верлаг . стр. 106–113. дои : 10.1007/BFb0019850 . ISBN 978-3-540-51643-9 .
^ Охта, Кадзуо; Пей, Динъи, ред. (1998). Достижения криптологии — ASIACRYPT'98 . Конспекты лекций по информатике. Том. 1514. стр. 187–199. дои : 10.1007/3-540-49649-1 . ISBN 978-3-540-65109-3 . S2CID 37257901 .
^ Сиамак Гадими (2020), Алгоритм декодирования оптимального решения (ODDA) для асимметричной системы TWRC; , Универсальный журнал электротехники и электроники

Дальнейшее чтение

Хилл, Раймонд (1986). Первый курс теории кодирования . Оксфордская серия по прикладной математике и информатике. Издательство Оксфордского университета . ISBN 978-0-19-853803-5 .
Плесс, Вера (1982). Введение в теорию кодов, исправляющих ошибки . Серия Wiley-Interscience по дискретной математике. Джон Уайли и сыновья . ISBN 978-0-471-08684-0 .
ван Линт, Якобус Х. (1992). Введение в теорию кодирования . Тексты для выпускников по математике (GTM). Том. 86 (2-е изд.). Спрингер-Верлаг . ISBN 978-3-540-54894-2 .

[Feldman_2005-1] Фельдман, Джон; Уэйнрайт, Мартин Дж.; Каргер, Дэвид Р. (март 2005 г.). «Использование линейного программирования для декодирования двоичных линейных кодов». Транзакции IEEE по теории информации . 51 (3): 954–972. CiteSeerX 10.1.1.111.6585 . дои : 10.1109/TIT.2004.842696 . S2CID 3120399 .

[Aji-McEliece_2000-2] Аджи, Шринивас М.; МакЭлис, Роберт Дж. (март 2000 г.). «Обобщенный распределительный закон» (PDF) . Транзакции IEEE по теории информации . 46 (2): 325–343. дои : 10.1109/18.825794 .

[Beutelspacher-Rosenbaum_1998-3] Бойтельспехер, Альбрехт ; Розенбаум, Юте (1998). Проективная геометрия . Издательство Кембриджского университета . п. 190. ИСБН 0-521-48277-1 .

[Stern_1989-4] Стерн, Жак (1989). «Метод поиска кодовых слов малого веса». Теория кодирования и ее приложения . Конспекты лекций по информатике. Том. 388. Шпрингер-Верлаг . стр. 106–113. дои : 10.1007/BFb0019850 . ISBN 978-3-540-51643-9 .

[Ohta_1998-5] Охта, Кадзуо; Пей, Динъи, ред. (1998). Достижения криптологии — ASIACRYPT'98 . Конспекты лекций по информатике. Том. 1514. стр. 187–199. дои : 10.1007/3-540-49649-1 . ISBN 978-3-540-65109-3 . S2CID 37257901 .

[6] Сиамак Гадими (2020), Алгоритм декодирования оптимального решения (ODDA) для асимметричной системы TWRC; , Универсальный журнал электротехники и электроники

[1]

[2]

[3]

[4]

[5]

[6]