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

⇐ ПредыдущаяСтр 3 из 6Следующая ⇒

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

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

. (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.

Сдвиг

Вход

Ключ

R₁

R₂

R₃

S₁

S₂

S₃

S₄

S₅

S₆

S₇

Выход

Рис. 17.4

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

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

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

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

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

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

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

; (8.16)

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

(8.17)

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

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

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

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

C(p) = c_n_-1∙ pⁿ^-1+ c_n_-2∙ pⁿ^-2+ …+ c₁∙ p+ c₀, (3.30)

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

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

pC(p) = c_n_-1∙ pⁿ+ c_n_-2∙ pⁿ^-1+ …+ c₁∙ p²+ c₀p.

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

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

(3.31)

С_п-1 р^п + С_п-2 р^п-1 +…С₀ р│ P^п+1

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

С_п-2 р^п-1 +…С₀р+ С_п-1- остаток

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

C₁(p) = c_n_-2∙ pⁿ^-1+ c_n_-3∙ pⁿ^-2+ …+ c₀∙ p+ c_n_-1.

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

C₁= [ c_n_-2 c_n_-3… c₀ c_n_-1] _,

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

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

C₁(p) = pC(p) mod (pⁿ+1),

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

C_i(p) = pⁱ C(p) mod (pⁿ+1) (3.32)

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

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

pⁱ C(p) = Q(p) (pⁿ+1)+C_i(p), (3.33)

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

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

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

(pⁿ+1) = g(p)∙ h(p), (3.34)

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

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

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

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

(3.35)

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

, (3.36)

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

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

(3.37)

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

17.6. Коды Голея

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

Коды Голея

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

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

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

⇐ Предыдущая 1 234 5 6 Следующая ⇒