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

редактировать

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

Содержание

1 Обозначение
2 Идеальное декодирование наблюдателем
- 2.1 Соглашения о декодировании
3 Декодирование максимального правдоподобия
4 Декодирование минимального расстояния
5 Декодирование синдрома
6 Декодирование набора информации
7 Максимальное правдоподобие частичного ответа
8 Декодер Витерби
9 См. Также
10 Источники
11 Ссылки

Обозначение

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

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

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

P (y отправлено ∣ x получено) {\ displaystyle \ mathbb {P} (y {\ t_dv {sent}} \ mid x {\ t_dv {receive}})}

{\ mathbb {P}} (y ​​{\ t_dv {sent}} \ mid x {\ t_dv {Received}})

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

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

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

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

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

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

P (x получено ∣ y отправлено) {\ displaystyle \ mathbb {P} (x {\ t_dv {receive}} \ mid y {\ t_dv {sent}})}

{\ mathbb {P}} (x {\ t_dv {принято}} \ mid y {\ t_dv {отправлено }})

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

P (x получено ∣ y отправлено) = P (x получено, y отправлено) P (y отправлено) = P (y отправлено ∣ x получено) ⋅ P (x получено) P (у отправлено). {\ displaystyle {\ begin {align} \ mathbb {P} (x {\ t_dv {Received}} \ mid y {\ t_dv {sent}}) {} = {\ frac {\ mathbb {P} (x { \ t_dv {selected}}, y {\ t_dv {sent}})} {\ mathbb {P} (y {\ t_dv {sent}})}} \\ {} = \ mathbb {P} (y {\ t_dv {отправлено}} \ mid x {\ t_dv {получено}}) \ cdot {\ frac {\ mathbb {P} (x {\ t_dv {Received}})} {\ mathbb {P} (y {\ t_dv { отправлено}})}}. \ end {align}}}

{\ begin {align} {\ mathbb {P}} (x {\ t_dv {Received}} \ mid y {\ t_dv {отправлено}}) {} = {\ frac {{\ mathbb {P}} (x {\ t_dv {Received}}, y {\ t_dv {sent}})} {{\ mathbb {P}} (y {\ t_dv {отправлено}})}} \\ {} = {\ mathbb {P}} (y ​​{\ t_dv {отправлено}} \ mid x {\ t_dv {принято}}) \ cdot {\ frac {{ \ mathbb {P}} (x {\ t_dv {got}})} {{\ mathbb {P}} (y ​​{\ t_dv {sent}})}}. \ end {align}}

После исправления $P (x получено) {\ displaystyle \ mathbb {P} (x {\ t_dv {Received}})}$ ${\ mathbb {P}} (x {\ t_dv {got}})$ , $x {\ displaystyle x}$ $x$ реструктурирован, а $P (y отправлено) {\ displaystyle \ mathbb {P} (y {\ t_dv {sent}})}$ ${ \ mathbb {P}} (y {\ t_dv {отправлено}})$ является постоянным, поскольку все кодовые слова будут отправлены с одинаковой вероятностью. Следовательно, $P (x получено ∣ y отправлено) {\ displaystyle \ mathbb {P} (x {\ t_dv {receive}} \ mid y {\ t_dv {sent}})}$ ${\ mathbb {P}} (x {\ t_dv {принято}} \ mid y {\ t_dv {отправлено }})$ максимизируется как функция переменной $y {\ displaystyle y}$ $y$ точно, когда $P (y отправлено ∣ x получено) {\ displaystyle \ mathbb {P} (y {\ t_dv {sent} } \ mid x {\ t_dv {receive}})}$ ${\ mathbb {P}} (y {\ t_dv {sent}} \ mid x {\ t_dv {Received}})$ развернуто, и утверждение следует.

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

Задача декодирования максимального правдоподобия также может быть смоделирована как проблема целочисленного программирования.

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

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

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

d (Икс, Y) = # {я: xi ≠ yi} {\ displaystyle d (x, y) = \ # \ {i: x_ {i} \ not = y_ {i} \}}

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

т.е. выберите кодовое слово $y {\ displaystyle y}$ $y$ , которое как можно ближе к $x {\ displaystyle x}$ $x$ .

Обратите внимание, что если вероятность ошибки на $p {\ displaystyle p}$ $p$ строго меньше половины, тогда декодирование с минимальным расстоянием эквивалентно декодированию с максимальным правдоподобием, поскольку если

d (x, y) = d, {\ displaystyle d (x, y) = d, \,}

d (x, y) = d, \,

тогда:

P (y получено ∣ x отправлено) = (1 - p) n - d ⋅ pd = (1 - p) n ⋅ (p 1 - p) d {\ displaystyle {\ begin {align} \ mathbb {P} (y {\ t_dv {Received}} \ mid x {\ t_dv {sent}}) {} = (1-p) ^ {nd} \ cdot p ^ {d} \\ {} = (1-p) ^ {n} \ cdot \ left ({\ frac {p} {1-p}} \ right) ^ {d} \\\ конец {выровнено} }}

{\ begin {align} {\ mathbb {P} } (y {\ t_dv {selected}} \ mid x {\ t_dv {sent}}) {} = (1-p) ^ {{nd}} \ cdot p ^ {d} \\ {} = ( 1-p) ^ {n} \ cdot \ left ({\ frac {p} {1-p}} \ right) ^ {d} \\\ конец {выровнено}}

который (поскольку p меньше половины) максимизируется путем минимизации d.

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

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

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

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

Синдромное декодирование

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

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

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

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

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

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

d (c, z) ≤ d (y, z) {\ displaystyle d (c, z) \ leq d (y, z)}

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

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

H x = 0 {\ displaystyle Hx = 0}

Hx = 0

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

H z = H (x + e) ​​= H x + H e = 0 + H e = H e {\ displaystyle Hz = H (x + e) ​​= Hx + He = 0 + He = He}

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

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

Обратите внимание, что это уже значительно менее сложное решение, чем декодирование стандартного массива .

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

∑ i = 0 t (ni) < | C | {\displaystyle {\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}<|C|\\\end{matrix}}}

{\ begin {matrix} \ sum _ {{i = 0}} ^ {t} {\ binom {n} {i}} <| C | \\\ конец {матрица}}

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

Зная, что такое $e {\ displaystyle e}$ $e$ , декодировать $x {\ displaystyle x}$ <97 тривиально.>как:

x = z - e {\ displaystyle x = ze}

x = ze

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

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

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

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

Декодирование информационного набора

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

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

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

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

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

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

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

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

См. Также

Источники

Hill, Raymond (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.

Ссылки