В теории кодирования , декодирование , представляет собой процесс преобразования принятых сообщений в кодовые слова данного кода . Было много распространенных методов отображения сообщений на кодовые слова. Они часто используются для восстановления сообщений, отправленных по зашумленному каналу , например по двоичному симметричному каналу .
Обозначение
считается двоичным кодом длины; должны быть элементами ; а также расстояние между этими элементами.
Идеальное декодирование наблюдателя
Можно передать сообщение , то декодирование идеальным наблюдателем генерирует кодовое слово. Результатом процесса является следующее решение:
Например, человек может выбрать кодовое слово который, скорее всего, будет получен как сообщение после передачи.
Соглашения о декодировании
Каждое кодовое слово не имеет ожидаемой возможности: может быть более одного кодового слова с равной вероятностью преобразования в полученное сообщение. В таком случае отправитель и получатель (и) должны заранее согласовать соглашение о декодировании. Популярные соглашения включают:
- Запрос на повторную отправку кодового слова - автоматический повторный запрос .
- Выберите любое случайное кодовое слово из набора наиболее вероятных кодовых слов, которое ближе к нему.
- Если следует другой код , отметьте неоднозначные биты кодового слова как стирание и надейтесь, что внешний код устраняет их неоднозначность.
Декодирование методом максимального правдоподобия
Учитывая полученный вектор декодирование с максимальной вероятностью выбирает кодовое словочто максимизирует
- ,
то есть кодовое слово что максимизирует вероятность того, что был получен, учитывая, что было отправлено. Если все кодовые слова будут отправлены с одинаковой вероятностью, то эта схема эквивалентна декодированию идеальным наблюдателем. Фактически, согласно теореме Байеса ,
При фиксации , реструктурирован и является постоянным, так как все кодовые слова будут отправлены с одинаковой вероятностью. Следовательно, максимизируется как функция переменной именно когда максимизируется, и утверждение следует.
Как и в случае с идеальным декодированием наблюдателя, необходимо согласовать соглашение для неуникального декодирования.
Задачу декодирования максимального правдоподобия можно также смоделировать как задачу целочисленного программирования . [1]
Алгоритм декодирования максимального правдоподобия является примером проблемы «маргинализации функции продукта», которая решается путем применения обобщенного закона распределения . [2]
Минимальное расстояние декодирования
Учитывая полученное кодовое слово , декодирование на минимальном расстоянии выбирает кодовое словочтобы минимизировать расстояние Хэмминга :
т.е. выберите кодовое слово это как можно ближе к .
Обратите внимание, что если вероятность ошибки на дискретном канале без памяти строго меньше половины, то декодирование с минимальным расстоянием эквивалентно декодированию с максимальным правдоподобием , поскольку если
тогда:
который (поскольку p меньше половины) максимизируется за счет минимизации d .
Декодирование минимального расстояния также известно как декодирование ближайшего соседа . Это может быть поддержано или автоматизировано с помощью стандартного массива . Декодирование с минимальным расстоянием является разумным методом декодирования при соблюдении следующих условий:
- Вероятность то, что возникает ошибка, не зависит от положения символа.
- Ошибки являются независимыми событиями - ошибка в одной позиции сообщения не влияет на другие позиции.
Эти предположения могут быть разумными для передач по двоичному симметричному каналу . Они могут быть нецелесообразными для других носителей, таких как DVD, где одна царапина на диске может вызвать ошибку во многих соседних символах или кодовых словах.
Как и в случае с другими методами декодирования, необходимо согласовать соглашение для неуникального декодирования.
Расшифровка синдрома
Синдромное декодирование - это высокоэффективный метод декодирования линейного кода в зашумленном канале , то есть коде , в котором допускаются ошибки. По сути, синдромное декодирование - это декодирование на минимальном расстоянии с использованием сокращенной справочной таблицы. Это допускается линейностью кода. [3]
Предположим, что линейный код длины и минимальное расстояние с проверочной матрицей . Тогда ясно способен исправлять до
ошибок, допущенных каналом (т. к. если не более ошибки, то декодирование с минимальным расстоянием по-прежнему будет правильно декодировать неправильно переданное кодовое слово).
Теперь предположим, что кодовое слово отправляется по каналу, и шаблон ошибки имеет место. потомполучен. Обычное декодирование с минимальным расстоянием будет искать вектор в таблице размеров для ближайшего совпадения - т.е. элемента (не обязательно уникального) с участием
для всех . При декодировании синдрома используется свойство матрицы четности, которое:
для всех . Синдром принимаемого определяется как:
Чтобы выполнить декодирование ML в двоичном симметричном канале , необходимо просмотреть предварительно вычисленную таблицу размеров, отображение к .
Обратите внимание, что это уже значительно менее сложно, чем декодирование стандартного массива .
Однако в предположении, что не более были допущены ошибки во время передачи, получатель может найти значение в еще более уменьшенной таблице размеров
Расшифровка списка
Расшифровка набора информации
Это семейство вероятностных методов Лас-Вегаса, основанных на наблюдении, что легче угадать достаточно безошибочных положений, чем угадать все положения с ошибками.
Простейшая форма принадлежит Прейнджу: пусть быть генераторная матрица используется для кодирования. Выбирать столбцы случайным образом и обозначим через соответствующая подматрица . С разумной вероятностью будет иметь полный ранг, а это значит, что если мы позволим быть субвектором для соответствующих позиций любого кодового слова из для сообщения , мы можем восстановить в виде . Следовательно, если нам повезло, что эти позиции полученного слова не содержал ошибок и, следовательно, уравнял позиции отправленного кодового слова, тогда мы можем декодировать.
Если произошли ошибки, вероятность такого удачного выбора столбцов определяется выражением .
Этот метод был усовершенствован различными способами, например, Штерн [4] и Canteaut и Sendrier. [5]
Максимальная вероятность частичного ответа
Максимальное правдоподобие частичного отклика ( PRML ) - это метод преобразования слабого аналогового сигнала от головки магнитного диска или накопителя на магнитной ленте в цифровой сигнал.
Декодер Витерби
Декодер Витерби использует алгоритм Витерби для декодирования потока битов, который был закодирован с использованием прямого исправления ошибок на основе сверточного кода. Расстояние Хэмминга используется в качестве метрики для декодеров Витерби с жестким решением. Квадрат евклидова расстояния используется в качестве метрики для мягкого решения декодеров.
Смотрите также
Рекомендации
- ^ Фельдман, Джон; Уэйнрайт, Мартин Дж .; Каргер, Дэвид Р. (март 2005 г.). «Использование линейного программирования для декодирования двоичных линейных кодов». IEEE Transactions по теории информации . 51 (3). С. 954–972. DOI : 10.1109 / TIT.2004.842696 .
- ^ Aji, Srinivas M .; МакЭлис, Роберт Дж. (Март 2000 г.). «Обобщенный распределительный закон» (PDF) . IEEE Transactions по теории информации . 46 (2): 325–343. DOI : 10.1109 / 18.825794 .
- ^ Бойтельшпахер, Альбрехт ; Розенбаум, Юте (1998). Проективная геометрия . Издательство Кембриджского университета . п. 190. ISBN 0-521-48277-1.
- ^ Стерн, Жак (1989). «Метод поиска кодовых слов небольшого веса». Теория кодирования и приложения . Конспект лекций по информатике. 388 . Springer-Verlag . С. 106–113. DOI : 10.1007 / BFb0019850 . ISBN 978-3-540-51643-9.
- ^ Охта, Кадзуо; Пей, Динъи, ред. (1998). Криптоанализ исходной криптосистемы Мак-Элиса . Достижения в криптологии - ASIACRYPT'98 . Конспект лекций по информатике. 1514 . С. 187–199. DOI : 10.1007 / 3-540-49649-1 . ISBN 978-3-540-65109-3. S2CID 37257901 .
дальнейшее чтение
- Хилл, Раймонд (1986). Первый курс теории кодирования . Oxford Applied Mathematics and Computing Science Series. Издательство Оксфордского университета . ISBN 978-0-19-853803-5.
- Плесс, Вера (1982). Введение в теорию кодов с исправлением ошибок . Серия Wiley-Interscience по дискретной математике. Джон Вили и сыновья . ISBN 978-0-471-08684-0.
- ван Линт, Якобус Х. (1992). Введение в теорию кодирования . Тексты для выпускников по математике (GTM). 86 (2-е изд.). Springer-Verlag . ISBN 978-3-540-54894-2.