В теории кодирования, декодирование - это процесс преобразования полученных сообщений в кодовые слова данного кода. Было много распространенных методов отображения сообщений на кодовые слова. Они часто используются для восстановления сообщений, отправленных по зашумленному каналу, например по двоичному симметричному каналу.
считается двоичный код с длиной ; должен быть элементами ; и - расстояние между этими элементами.
Можно дать сообщение , тогда декодирование идеальным наблюдателем генерирует кодовое слово . Результатом процесса является следующее решение:
Например, человек может выбрать кодовое слово , которое с наибольшей вероятностью будет получено как сообщение после передача инфекции.
Каждое кодовое слово не имеет ожидаемой возможности: может быть более одного кодового слова с равной вероятностью преобразования в полученное сообщение. В таком случае отправитель и получатель (и) должны заранее согласовать соглашение о декодировании. Популярные соглашения включают:
Учитывая полученное кодовое слово максимальная вероятность декодирования выбирает кодовое слово , который максимизирует
то есть кодовое слово , которое максимизирует вероятность того, что было получено, с учетом того, что отправлен. Если все кодовые слова будут отправлены с одинаковой вероятностью, то эта схема эквивалентна декодированию идеальным наблюдателем. Фактически, согласно теореме Байеса,
После исправления , реструктурирован, а является постоянным, поскольку все кодовые слова будут отправлены с одинаковой вероятностью. Следовательно, максимизируется как функция переменной точно, когда развернуто, и утверждение следует.
Как и в случае с идеальным декодированием наблюдателя, необходимо согласовать соглашение для неуникального декодирования.
Задача декодирования максимального правдоподобия также может быть смоделирована как проблема целочисленного программирования.
Алгоритм декодирования максимального правдоподобия является примером проблемы «маргинализации функции продукта» который решается применением обобщенного закона распределения.
с учетом полученного кодового слова , декодирование минимального расстояния выбирает кодовое слово , чтобы минимизировать расстояние Хэмминга :
т.е. выберите кодовое слово , которое как можно ближе к .
Обратите внимание, что если вероятность ошибки на строго меньше половины, тогда декодирование с минимальным расстоянием эквивалентно декодированию с максимальным правдоподобием, поскольку если
тогда:
который (поскольку p меньше половины) максимизируется путем минимизации d.
Декодирование минимального расстояния также известно как декодирование ближайшего соседа. Это может быть поддержано или автоматизировано с помощью стандартного массива . Декодирование с минимальным расстоянием является разумным методом декодирования при соблюдении следующих условий:
Эти предположения могут быть разумными для передач по двоичному симметричному каналу. Они могут быть нецелесообразными для других носителей, таких как DVD, где одна царапина на диске может вызвать ошибку во многих соседних символах или кодовых словах.
Как и в случае с другими методами декодирования, необходимо согласовать соглашение для неуникального декодирования.
Синдромное декодирование - это высокоэффективный метод декодирования линейного кода по зашумленному каналу, т. По сути, синдромное декодирование - это декодирование на минимальном расстоянии с использованием сокращенной справочной таблицы. Это допускается линейностью кода.
Предположим, что - линейный код длины и минимального расстояния с матрицей проверки на четность . Тогда очевидно, что способен исправлять до
ошибок, допущенных каналом (поскольку, если сделано не более ошибок, то декодирование с минимальным расстоянием все равно будет правильно декодировать неверно переданное кодовое слово).
Теперь предположим, что кодовое слово отправлено по каналу и возникает шаблон ошибки . Затем принимается . Обычное декодирование с минимальным расстоянием будет искать вектор в таблице размера для ближайшего совпадения, т. е. элемента (не обязательно уникального) с
для всех . Синдромное декодирование использует свойство матрицы четности:
для всех . Синдром полученного определяется как:
Для выполнения декодирования ML в двоичном формате . симметричный канал, необходимо найти предварительно вычисленную таблицу размера , отображение до .
Обратите внимание, что это уже значительно менее сложное решение, чем декодирование стандартного массива .
Однако при условии, что не более чем были допущены ошибки во время передачи, получатель может найти значение в дополнительной сокращенной таблице только размера
(для двоичного кода). В таблице приведены предварительно вычисленные значения для всех возможных шаблонов ошибок .
Зная, что такое , декодировать <97 тривиально.>как:
Для двоичных кодов, если оба и не слишком велики, и, если предположить, что матрица генерации кода имеет стандартную форму, декодирование синдрома можно вычислить с использованием 2 предварительно вычисленных таблиц поиска и только 2 операций XOR.
Пусть будет принятым кодовым словом с шумом, т.е. . Используя поисковую таблицу кодирования размера , кодовое слово , которое соответствует найдены первые биты .
Затем синдром вычисляется как последние биты (первые биты XOR равны нулю [поскольку порождающая матрица имеет стандартную форму] и отбрасываются). Используя синдром, ошибка вычисляется с помощью поисковой таблицы синдромов размера , а затем декодирование вычисляется с помощью (для кодового слова или первого биты для исходного слова).
Количество записей в двух таблицах поиска равно , что составляет значительно меньше, чем , необходимого для декодирования стандартного массива, для которого требуется только поиск. Кроме того, для кодирования можно использовать предварительно вычисленную поисковую таблицу кодирования, и поэтому ее часто бывает полезно иметь.
Это семейство Лас-Вегас -вероятностных методов, основанных на наблюдении, что легче угадать достаточно безошибочных позиций, чем угадать все ошибочные позиции.
Простейшая форма принадлежит Прейнджу: пусть будет порождающая матрица , используемая для кодирования. Выбрать столбцы наугад и обозначить соответствующая подматрица . С разумной вероятностью будет иметь полный ранг, что означает, что если мы позволим быть субвектор для соответствующих позиций любого кодового слова of для сообщения , мы можем восстановить как . Следовательно, если нам повезло, что эти позиции полученного слова не содержали ошибок и, следовательно, равнялись позиции отправленного кодового слова, затем мы можем декодировать.
Если произошли ошибки, вероятность такого удачного выбора столбцов определяется как .
Этот метод был улучшен различными способами, например Стерном и Канто и Сендриером.
Максимальная вероятность частичного ответа (PRML ) - это метод преобразования слабого аналога сигнал с головки магнитного диска или стримера в цифровой сигнал.
Декодер Витерби использует алгоритм Витерби для декодирования потока битов, который был закодирован с использованием прямого исправления ошибок на основе сверточного кода. Расстояние Хэмминга используется в качестве метрики для декодеров Витерби с жестким решением. Квадрат евклидова расстояния используется в качестве метрики для декодеров мягких решений.