Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Алгоритм максимальной апостериорной вероятности (МАП).



Если априорная матрица потерь П не известна, то можно определить апостериорные вероятности гипотез по формуле Байеса (1.2)

.

Алгоритм δМАП, оптимальный по критерию МАП (идеального наблюдателя), реализует такое разбиение пространства Х, при котором принимается решение γk о гипотезе Hk, если эта гипотеза имеет наибольшую апостериорную вероятность

. (2.4)

Критерий идеального наблюдателя

 


Пусть объективные данные для установления потерь отсутствуют. Тогда разумно стремиться к тому, чтобы различитель сигналов ошибался как можно реже, т.е. чтобы полная вероятность появления ошибки

(33)

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

.

Минимизация среднего риска равносильна минимизации . Вероятность правильного приема сообщения

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

(34)

где , как и ранее, m - мерный вектор. Анализ m-1 условий (34) показывает, что они равносильны алгоритму

(35)

заключающемуся в том, что регистрируется тот сигнал , для которого априорная вероятность максимальна.

 

Циклические коды. Циклический код Голея.

17.4 Циклические коды.

Также относятся к классу линейных блоковых кодов и наиболее распространены. Особенность этих кодов: если некоторое кодовое слово принадлежит коду, то и его циклические перестановки также принадлежат коду. Иными словами, (n - 1) кодовых слов могут быть сформированы путем циклического сдвига одного кодового слова.

Все множество кодовых слов может быть получено путем циклических сдвигов других кодовых слов.

Достоинство: относительно простая реализация кодеков, основными элементами которых являются регистры сдвига и сумматоры по модулю 2.

Кодирование и вычисление синдрома при декодировании могут быть осуществлены с помощью либо k -разрядного, либо (n - k) -разрядного сдвига.

Рассмотрим пример кодирования циклическим кодом.

Пример. На рис. 17.4 приведена структурная схема кодера циклического кода (7,4), в которой используется трехразрядный регистр сдвига. Работа кодера показана для входного слова 1010. Для первых четырех сдвигов ключи замкнуты (положение С) , а переключатель находится в положении А. В течение этого интервала информационная последовательность поступает на вход канального модулятора и регистра сдвига. Затем ключи размыкаются (положение 0), а переключатель переводится в положение В. Три проверочных символа подаются на выход и завершают процедуру формирования кодового слова. Информационной последовательности [1010] соответствует проверочная последовательность [011].

Полное кодовое слово имеет вид: 1010011.

Структурная схема декодера приведена на рис. 17.4.

 


Сдвиг Вход Ключ R1 R2 R3 И S1 S2 S3 S4 S5 S6 S7 Выход
С - - - - - - - -
С - - - - - - -
С - - - - - -
С - - - - -
С - - - -
С - - -
С - -
- -
- - -
- - - -
- - - - -
- - - - - -
- - - - - - -
- - - - - - - -

Рис. 17.4

Рассмотрим работу декодера, предполагая, что ошибка произошла в четвертой позиции и принимаемая последовательность имеет вид: [1011011] . Обработка полного кодового слова осуществляется за 14 сдвигов. Состояние ключей и регистров для всех 14 сдвигов приведена на рис. 17.4.

На выходе логической схемы ''И'' единица появилась при наличии трех единиц на входе. Поэтому для формирования единицы на выходе схемы И необходимо, чтобы содержимое регистра R было [100]. Это условие выполнимо при 11 сдвиге, поэтому четвертый символ принятой последовательности инвертируется в процессе ее продвижения на выходе декодера.

Если для заданного декодера построить порождающую и проверочную матрицы, то легко убедиться, что четвертой позиции будет соответствовать синдром [011].

Таким образом, верхняя часть декодера фактически представляет собой генератор синдрома.

ЦИКЛИЧЕСКИЕ КОДЫ

Разрешенные кодовые комбинации циклического кода F(x)могут быть получены двумя способами [46, 68]:

умножением кодовой комбинации Q(x) простого кода на одно­член xr, и добавлением к этому произведению остатка R (х), полученного в результате деления произведения Q(x)xr на образую­щий полином Р(х):

; (8.16)

умножением кодовой комбинации Q(x)простого кода на обра­зующий полином:

(8.17)

Циклические коды

Циклические коды (ЦК) относятся к подклассу линейных блоковых кодов и наиболее просты в реализации. Если некоторое кодовое слово принадлежит ЦК, то его циклические перестановки также принадлежат ЦК. Иными словами, (n − 1) кодовых слов ЦК могут быть сформированы в кодеке путем циклического сдвига одного кодового слова, т.е. на регистрах сдвига и сумматорах по модулю 2.

Покажем, что для циклического кода можно также построить порождающие и проверочные матрицы и реализовать синдромное декодирование более простым способом, чем для линейных блоковых кодов.

Кодовое слово C = [cn-1 cn-2 … c1 c0] циклического кода с n элементами связывают с полиномом C(p) степени (n−1):

C(p) = cn-1∙pn-1+ cn-2pn-2+ …+ c1∙p+ c0 , (3.30)

где для двоичного кода коэффициенты сi являются нулем или единицей.

Циклическому сдвигу кодового слова на одну позицию соответствует умножение этого полинома на р

pC(p) = cn-1∙pn+ cn-2pn-1+ …+ c1∙p2+ c0p.

 

Полученный полином при сn-1 =1 не может соответствовать кодовому слову по условию (3.30), так как его степень n.

Если его разделить на (pn+1), то получим частное и остаток

 

(3.31)

Сп-1 р п + Сп-2 рп-1 +…С0 р│Pп +1

Сп-1 р п + Сп-1 Сп-1-частное

Сп-2 р п-1 +…С0р+ Сп-1 - остаток

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

C1(p) = cn-2∙pn-1+ cn-3pn-2+ …+ c0∙p+ cn-1.

 

Этот остаток представляет согласно (3.30) кодовое слово

C1 = [ cn-2 cn-3 … c0 cn-1],

полученное сдвигом на одну позицию.

В этом случае этот остаток от деления можно записать согласно уравнению (3.31) в виде:

C1(p) = pC(p) mod (pn +1),

соответственно при i циклических сдвигах

 

Ci (p) = pi C(p) mod (pn +1) (3.32)

 

где полином Ci (p) также представляет кодовое слово Ci ЦК.

Таким образом, умноженный на pi полином C(p) ЦК удовлетворяет согласно (3.31) условию циклического сдвига:

 

pi C(p) = Q(p) (pn +1)+Ci (p), (3.33)

 

где Q(p)-частное от деления полиномов;

Ci (p) - остаточный от деления полином, представляющий кодовое слово Ci ЦК.

Известно, что полином (pn +1) можно факторизовать (представить произведением сомножителей) в виде:

(pn+1) = g(p)h(p) , (3.34)

где g(p) - порождающий полином степени (nk) ЦК (n, k);

h(p) - проверочный полином степени k, который можно использовать для генерации дуального ЦК (n, n−k) .

Покажем, что генерируемые этими полиномами ЦК удовлетворяют условию циклического сдвига (3.33).

Циклический (n, k) код будем генерировать, используя в качестве порождающего полином g(p) с двоичным коэффициентами:

(3.35)

Пусть полином информационного сообщения

, (3.36)

где [xk-1, xk-2,…x1, x0] определяют k информационных бит кодового слова ЦК и соответственно 2k полиномов .

Тогда произведение полиномов

(3.37)

формирует 2k полиномов степени ≤(n 1), каждому из которых соответствует кодовое слово Cm ЦК, т.к. каждое из них удовлетворяет условию циклического сдвига (3.33).

 

17.6. Коды Голея

Код Голея относится к числу наиболее интересных, т.к. он позволяет исправлять ошибки высокой кратности и является совершенным кодом. Код Голея (23, 12) является циклическим и исправляет все конфигурации ошибок, кратность которых не больше трех. Код(24, 12) образуется из кода (23, 12) добавлением символа проверки на четность к кодовым словам кода (23, 12). Эти коды имеют минимальное кодовое расстояние, равное 7 и 8, соответственно. Поэтому код (24,12) кроме исправления ошибок кратности 3 обеспечивает обнаружение ошибок кратности 4 при незначительном изменении кодовой скорости. Код (24, 12) является одним из наиболее распространенных.

Коды Голея

Код Голея позволяет исправлять ошибки высокой кратности и является совершенным ЦК.

Код Голея (23, 12) может генерироваться порождающим полиномом g(p)=p11+p9+p7+p6+p5+p+1 и исправляет все конфигурации ошибок, кратность которых не больше трех. Расширенный код (24, 12) образуется из кода (23,12) добавлением символа проверки на четность к словам кода

(23, 12). Эти коды имеют минимальное кодовое расстояние, равное 7 и 8 соответственно. Поэтому код (24,12) кроме исправления ошибок кратности 3 обеспечивает обнаружение ошибок кратности 4 при незначительном изменении кодовой скорости и является одним из наиболее известных.

 






Читайте также:

Последнее изменение этой страницы: 2016-03-17; Просмотров: 247; Нарушение авторского права страницы


lektsia.com 2007 - 2017 год. Все права принадлежат их авторам! (0.1 с.) Главная | Обратная связь