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

Алгоритмы декодирования сообщений

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

Обозначение

${\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. Если следует другой код , отметьте неоднозначные биты кодового слова как стирания и надейтесь, что внешний код устранит их неоднозначность.
4. Сообщить системе об ошибке декодирования

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

При наличии полученного вектора максимального правдоподобия декодирование выбирает кодовое слово , которое максимизирует ${\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}}}$

который (поскольку 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)

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

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

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

Ссылки

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

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

• Хилл, Рэймонд (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.