Неалгебраические методы помехоустойчивого декодирования

Рассмотренные коды предполагают использование алгебраических процедур кодирования-декодирования (то есть разного рода алгебраических уравнений). Эти способы не учитывают вероятностных характеристик передаваемых кодовых последовательностей и помех. Существует ряд методов противодействия помехам, использующих статистические характеристики сообщений, а также учитывающие последствия неверного декодирования.

Пусть по каналу связи передается некоторое сообщение U из алфавита A, а принимается кодовая последовательность Ŭ, содержащая искажения вследствие помех, то есть по отдельным символам приемник мог принять неправильные решения (вместо нулей – единицы и наоборот).

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

Пусть U_l − l -е кодовое слово используемого кода;

U _li − i -й символ этого кодового слова;

Ŭ - принятый сигнал, содержащий одно из кодовых слов и помеху.

Какое кодовое слово содержится в принятом сигнале, мы не знаем. Известны априорные вероятности передачи кодовых слов – P(U_l)

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

Декодер максимума апостериорной вероятности должен выбирать в качестве решения кодовое слово U * = U_j, которое максимизирует условную вероятность P(U_j|Ŭ) — вероятность того, что была передана последовательность U_j, если принята данная реализация сигнала Ŭ. U *=arg max{ P(U_j|Ŭ);U_jÎA}.

Поскольку P(U_j|Ŭ) P(Ŭ) = P(Ŭ|U_j) P(U_j), то по формуле Байеса

P(U_j|Ŭ) = P(Ŭ|U_j) P(U_j)/P(Ŭ).

P(Ŭ) – это полная безусловная вероятность появления сообщения Ŭ.

P(Ŭ)= ∑P(Ŭ|U_j) P(U_j).

Пример. Источник генерирует 3 кодовых слова: u₁=(0 1 0), u₂=(0 0 1), u₃=(1 1 1) с вероятностями p₁=0.4, p₂=0.4, p₃=0.2. Принята комбинация ũ=(1 1 0). Зная, что вероятность искажения одного бита р_и=0.1, определить оптимальное по критерию максимума апостериорной вероятности переданное слово.

Оптимальное решение – то, которое максимизирует величину P(u_i|ũ;i=1,2,3). По формуле Байеса P(u_i|ũ) = P(ũ|u_i)·P(u_i)/∑P(ũ|u_i)*P(u_i).

P(ũ|u₁)=0.1·0.9·0.9=0.081 (вероятность того, что исказится только первый бит)

P(ũ|u₂)=0.1·0.1·0.1=0.001 (вероятность того, что исказится первый, второй и третий биты)

P(ũ|u_i)=0.9·0.9·0.1=0.081 (вероятность того, что исказится только третий бит)

P(ũ)= ∑P(ũ/u_i)·P(u_i) = 0.081·0.4+0.001·0.4+0.081·0.2=0.049

P(u₁|ũ)=0.081·0.4/0.049=0.66

P(u₂|ũ)=0.001·0.4/0.049=0.01

P(u₃|ũ)=0.081·0.2/0.049=0.33.

Максимум апостериорной вероятности достигается для первого слова - u₁. Следовательно, это решение и будет принято.

Если считать, что все кодовые слова равновероятны - P(U_j) = const, а также, что безусловная плотность P(Ŭ) не зависит от U_j, то максимуму P (U_j |Ŭ) соответствует максимум P (Ŭ|U_j ), так называемой функции правдоподобия— условной вероятности того, что сигнал примет значение Ŭ, если передавалось кодовое слово U_j . Декодер максимального правдоподобия выбирает решение, максимизирующее функцию правдоподобия: U *=arg max{ P(Ŭ|U_j);U_jÎA}

Более развитые методы декодирования учитывают еще и последствия от ошибок декодирования.

Представьте, что кодовое слово u₃=(1 1 1) является сигналом боевой тревоги, тогда последствия от ошибочного декодирования могут быть очень велики, несмотря на то, что вероятность такой ошибки – мала.

Для этого вводится т.н. функция потерь L(U,U_j).

Функция потерь L(U,U_j) – это мера негативных последствий при де­ко­ди­ровании, являющихся результатом того, что вместо истинного пере­данного сообщения U_j принимается решение о приеме сообщения U.

В соответствии с критерием Байеса надо декодировать так, чтобы минимизировать средние потери от ошибочного декодирования. Средние потери от принятия решения U при получении сообщения Ŭ вычисляются по формуле: W(U|Ŭ) = ∑_j L(U,U_j)·P(U_j|Ŭ). Декодер Байеса выбирает решение, минимизирующее средние потери: U *=arg min{ W(U|Ŭ);UÎA}

Пример. Кодовые слова из предыдущего примера имеют следующий смысл: u₁ – проверка, u₂ – учебная тревога, u₃ – боевая тревога. Потери от ошибок декодирования сведены в матрицу потерь L(U,U_j):

L(U,Uj)=	Uj U	U1	U2	U3
U1
U2
U3

W(U₁|Ŭ) = ∑_j L(U₁,U_j)·P(U_j|Ŭ)=8·0.01+40·0.33=13.28

W(U₂|Ŭ) = ∑_j L(U₂,U_j)·P(U_j|Ŭ)=5·0.66+20·0.33=9.9

W(U₃|Ŭ) = ∑_j L(U₃,U_j)·P(U_j|Ŭ)=10·0.66+10·0.01=6.7

Минимальные средние потери при решении U*=u₃

Декодер Байеса имеет достаточно универсальный характер, так его вид зависит от функции потерь. Задавая функцию потерь тем или иным способом, можно получать различные критерии декодирования. Например, если функция потерь представляет собой кодовое расстояние между истинным и принимаемым сообщением (L(U,U_j)=∑U_kÅU_jk), то критерий Байеса превращается в критерий максимального правдоподобия.

Это примеры так называемого жесткого декодирования, когда в декодере сначала принимается решение относительно значения символов принятой последовательности, а уже затем – относительно значения кодового слова. При жестком декодировании по принятому сигналу сначала определяются символы принятой последовательности Ŭ, а потом эта последовательность поочередно сравнивается со всеми кодовыми словами данного кода. Решение принимается в пользу кодового слова, оптимизирующего принятый критерий декодирования.

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

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

Еще один подход к декодированию – использование совокупности критериев и формирование так называемых компромиссных решений на основе теории компромиссов В.Парето.

Декодирование сверточных кодов

Рассмотрим декодер, который состоит из двух частей:
1) схемы, вырабатывающей исправляющую последовательность;
2) схемы, производящей исправление (коррекцию) кода.
Первая схема приведена на рис. 3. Коммутатор Км декодера работает синхронно и синфазно с коммутатором кодера (рис. 2). Регистр сдвига декодера также состоит из четырех разрядов (ячеек).
На вход декодера подается последовательность символов (3), которая коммутатором Км разделяется на информационную (1) последовательность, подаваемую на вход регистра сдвига, и на последовательность контрольных символов (2), подаваемую на нижний вход выходного сумматора.

Рис. 1. Схема формирования исправляющей последовательности

В данной схеме четырехразрядный регистр сдвига имеет такую же схему, как и регистр сдвига в кодере. Поэтому, если ошибок нет, последовательность символов на выходе верхнего сумматора (рис. 3) совпадает с последовательностью контрольных символов (2), подаваемых на вход нижнего сумматора. В этом случае на Выходе 2 сумматора последовательность символов состоит из одних нулей, а последовательность символов на Выходе 1 – из последовательности неискаженных символов (1).

Если в канале связи между кодером и декодером возникают ошибки, то последовательность символов на Выходе 2 содержит единицы в определенном сочетании, которое позволяет исправлять ошибки. Следовательно, она служит исправляющей последовательностью.
Рассматриваемый код позволяет исправлять пакет ошибок длиной
Рассмотрим пример возникновения ошибок в наихудшем случае – серии длиной 2 l ₀=4. Такой пакет ошибок поражает только половину информационных символов длиной l₀=2 и половину контрольных символов длиной l ₀=2. Допустим, произошла последовательность ошибок

0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0. (4)

Суммируя последовательности символов (3) и (4), получаем принятую последовательность:

1 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1, (5)

которая в рассматриваемом примере подается на вход декодера.
Коммутатор Км в схеме на рис. 3 разделяет последовательность (5) на информационные

1 0 1 1 1 1 1 1 0 0 1 (6)

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

0 0 0 1 0 1 1 0 1 0 1. (7)

Последовательности символов (6) и (7) содержат ошибочные символы, которые подчеркнуты. Регистр сдвига (рис. 3) выдаст последовательность символов

0 0 1 0 0 1 0 0 0 0 1, (8)

которая в сумме с последовательностью (7) даст исправляющую последовательность

0 0 1 1 0 0 1 0 1 0 0. (9)

Автоматически операция исправления последовательности (6), возникающей на Выходе 1 декодера с помощью исправляющей последовательности (9) на Выходе 2 (рис. 3), осуществляется с помощью схемы исправления ошибок, приведенной на рис. 4. Эта схема является продолжением схемы, приведенной на рис. 3 (Выход 1 соединяется с Входом 1, а Выход 2 соединяется с Входом 2.).

Рис. 2. Схема декодера, исправляющего ошибки

Исправляющая последовательность (9) подается непосредственно на инвертирующий элемент НЕ, который преобразует символы 1 в 0, а 0 в 1 и подает их на левый вход логического элемента И в виде последовательности (10). Схема нижнего регистра сдвига такая же, как на рис. 3. С выхода ячейки 2 исправляющая последовательность (9) подается со сдвигом l ₀=2 шага на нижний вход элемента И в виде последовательности (11), а с выхода ячейки 4 регистра – на правый вход элемента И в виде последовательности (12), сдвинутой на 2 l ₀=4 шага. В результате на выходе элемента И получим последовательность (13)

1 1 0 0 1 1 0 1 0 1 1… (10)
.. 0 0 1 1 0 0 1 0 1… (11)
.... 0 0 1 1 0 0 1… (12)
.... 0 0 0 0 0 0 1… (13)

Точки в последовательностях слева обозначают сдвиг символов. Единица на выходе элемента И возникает только в тех случаях, когда на все его три входа подаются единицы. Она используется в качестве команды на исправление ошибки. Выдача этой команды должна быть согласована по времени с входной (ошибочной) последовательностью информационных символов, поступающей на Вход 1 декодера. Для этой цели служат ячейки 5 и 6 регистра сдвига на Входе 1, обеспечивающие l ₀=2.

Исправленная последовательность вырабатывается на выходе схемы в виде суммы последовательностей символов (14) и (15), которые являются последовательностями (13) и (6), сдвинутыми соответственно на 2 l ₀=4 и 3 l ₀=6 шагов в соответствии с числом ячеек регистров сдвига, включенных последовательно:

.... 0 0 0 0 0 0 1 0 0 0 0 0 0 (14)
...... 1 0 1 1 1 1 1 1 0 0 1 (15)
1 0 1 1 0 1 1 1 0 0 1 (16)

После автоматического исправления последовательность (16) совпадает с последовательностью (1). Как следует из (16), на пути информационных символов включено 3 l ₀=6 ячеек регистров сдвига.

Сложность аппаратуры для рекуррентного кода оценивается по числу ячеек регистров сдвига. Кодирующее устройство имеет 2 l ₀=4 ячейки регистра, а декодирующее – 5 l₀ =10 ячеек, из которых исправляющая схема имеет 3 l ₀=6 ячеек. Для увеличения защищенности и пакета исправляемых ошибок увеличивают n, т. е. используют коды [(n-1)/n]. Схемы таких кодирующих и декодирующих устройств несколько усложняются.

Алгоритм Возенкрафта и Фано. Ранее, до того как Витерби открыл оптимальный алгоритм декодирования сверточных кодов, существовали и другие алгоритмы. Самым первым был алгоритм последовательного декодирования, предложенный Уозенкрафтом (Wozencraft) и модифицированный Фано (Fano). В ходе работы последовательного декодера генерируется гипотеза о переданной последовательности кодовых слов и рассчитывается метрика между этой гипотезой и принятым сигналом. Эта процедура продолжается до тех пор, пока метрика показывает, что выбор гипотезы правдоподобен, в противном случае гипотеза последовательно заменяется, пока не будет найдена наиболее правдоподобная. Поиск при этом происходит методом проб и ошибок. Для мягкого или жесткого декодирования можно разработать последовательный декодер, но обычно мягкого декодирования стараются избегать из-за сложных расчетов и большой требовательности к памяти.

Мажоритарное декодирование. Этот метод заключается в многократной проверке каждого символа принятой кодовой комбинации по специальным таблицам коэффициентов, составленным для каждого варианта (n, k) циклического кода. Значение каждого символа определяется по мажоритарному принципу (слово «мажоритарный» означает большинство), т.е. по принципу голосования. Это означает, что если, например, один из пяти проверок данного символа три показали 1, а две- 0, то символу присваивается значение 1. Если все проверки показали 1 или 0, то символ считается неискаженным и принимается без изменения.

Если при какой-либо проверке окажется равное число 1 и 0, то это означает, что для данного кода произошла неисправимая комбинация ошибок и принятая комбинация должна быть забракована.

Дата добавления: 2014-10-22