Материал: 6593
126
4.3.25.Передача осуществляется в двоичном симметричном канале с независимыми ошибками, битовая вероятность
ошибки р = 10–4. Таков же канал переспроса, но ро = 10–8. Найти вероятность повторной передачи кодовой комбинации, если в прямом канале применен линейный блочный (3,1)-код.
4.3.26.Передача осуществляется в двоичном симметричном канале с независимыми ошибками, битовая вероятность
ошибки р = 10–5. Таков же канал переспроса, но ро = 10–7. Найти вероятность правильного декодирования кодовой комбинации,
если в прямом канале применен код (32,31).
4.3.27. Циклический код (7,4) задан проверочным полиномом h(x) = 1 + x + x2 + x4. Декодировать принятое кодовое слово 0101010 по минимуму расстояния и методом вычисления синдрома, сравнить результаты.
4.3.28. Найти вероятность правильного декодирования кодового слова в СПИ с каналом переспроса, если в прямом канале используется код Хэмминга с пятью проверочными символами. Вероятность ошибки в одном символе в прямом канале р = 10–6, а в канале переспроса ро = 10–6, ошибки независимые.
4.3.29. Комбинации блочного (n,k)-кода заданы путем случайного выбора.
а) Найти вероятность того, что в кодовой таблице окажется более одной нулевой комбинации.
б) Найти математическое ожидание и СКО расстояния между комбинациями.
Решить задачу для случая n = 100, k = 10.
4.3.30. Систематический сверточный код, характеризуемый степенью кодирования k/n=1/3, задан полиномами g1(x) =1,
g2 (x) =1+ x, g3 (x) =1+ x2 . Определить битовую вероятность
ошибки при пороговом декодировании, если битовая вероятность ошибки в канале равна 10–3.
4.3.31.Записать обе проверочные последовательности для сверточного кода из задачи 4.3.30., если информационная последовательность на входе кодера – периодическая и имеет вид
…011110011110… .
4.3.32.Способ кодирования определен кодовой таблицей
Сообщение |
да |
нет |
127
Кодовая |
111 |
000 |
комбинация |
11 |
00 |
Является ли этот код систематическим и, если да, то записать для него производящую и проверочную матрицы.
4.3.33.Кодовую комбинацию, соответствующую десятичному числу 13, закодировать кодом Рида–Малера первого порядка так, чтобы в комбинации было не более 20 символов.
4.3.34.Кодовую таблицу, содержащую все возможные 5- разрядные двоичные комбинации, сократить (отобрать разре-
шенные к передаче кодовые слова) так, чтобы получившийся код позволял обнаруживать любые однократные и двукратные ошибки.
4.3.35. Кодовую таблицу, содержащую все возможные 15разрядные двоичные комбинации, сократить (отобрать разрешенные к передаче кодовые слова) так, чтобы получившийся код позволял исправлять любые однократные и двукратные ошибки.
128
5 ДРУГИЕ МЕРЫ ИНФОРМАЦИИ
5.1 Информация по Кульбаку
Определение. Свойства. Пусть наблюдаемый сигнал Y описывается системой непрерывных случайных величин
Y (1) ,Y (1) ,...,Y (n) , которые при гипотезе H1 |
имеют совместную |
|||||
плотность |
вероятности W (y(1) |
,..., y(n) ) , |
а |
при гипотезе Н2 – |
||
|
|
1 |
|
|
|
|
плотность |
W (y(1) |
,..., y(n) ) . |
Тогда |
логарифм отношения |
||
|
2 |
|
|
|
|
|
правдоподобия |
|
|
|
|
|
|
|
I(1: 2;y) |
= log |
W (y(1) ,..., y(n) ) |
(5.1.1) |
||
|
1 |
|
|
|||
|
|
|
W (y(1) ,..., y(n) ) |
|
||
|
|
|
2 |
|
|
|
называется информацией для различения в пользу Н1 против Н2, содержащейся в выборке y(1) ,..., y(n) . Эта величина случайна,
так как значение выборки неизвестно до опыта.
В качестве гипотез Н1 и Н2 могут выбираться любые предположения, в том числе такие:
Н1 – «переданное значение сообщения равно х1», Н2 – «переданное значение сообщения равно х2 ».
Математическое ожидание случайной величины (5.1.1) при условии, что справедливо предположение Н1,
I(1: 2) = MH1 |
|
W1 |
(y(1) ,..., y(n) ) |
|
log W |
(y(1) ,..., y(n) ) |
= |
||
|
|
2 |
|
(5.1.2) |
∞ |
∞ |
W |
(y(1) ,..., y(n) ) |
|
|||||
∫ |
... ∫W1(y(1) ,..., y(n) )log |
dy(1) ,..., dy(n) |
|||||||
1 |
(y |
(1) |
,..., y |
(n) |
) |
||||
−∞ |
−∞ |
W2 |
|
|
|
||||
называется средней информацией для различения в пользу Н1 против Н2.
Аналогично величина |
|
|
|
|
|
|
|
|
W2 |
(y(1) ,..., y(n) ) |
|
|
|
I(2 :1) = MH2 |
log |
|
|
= |
(5.1.3) |
|
W (y(1) ,..., y(n) ) |
||||||
|
|
1 |
|
|
|
|
129
∞ |
∞ |
W |
(y(1) ,..., y(n) ) |
|
|||||
∫ |
... ∫W2 (y(1) ,..., y(n) )log |
dy(1) ,..., dy(n) |
|||||||
2 |
(y |
(1) |
,..., y |
(n) |
) |
||||
−∞ |
−∞ |
W1 |
|
|
|
||||
называется средней информацией для различения в пользу Н2
против Н1.
Сумма (5.1.2) и (5.1.3)
J (1,2) = I(1: 2) + I(2 :1) |
(5.1.4) |
называется информационным расхождением между гипотезами
Н1 и Н2.
Формулы (5.1.1) – (5.1.4) можно использовать и для вычисления информации, содержащейся в системе дискретных случайных величин Y. При этом следует вместо плотностей вероятностей подставить соответствующие вероятности, а интегрирование заменить суммированием по всем возможным значениям системы дискретных случайных величин.
Перечислим основные свойства: 1) Выпуклость.
I(1: 2) ≥ 0, |
I(2≥:1) 0, ≥ J (1,2) 0. |
(5.1.5) |
Неравенства обращаются в равенства тогда и только тогда, когда Y не зависит от Н, т. е.
|
W (y(1) ,..., y(n) ) =W (y(1) |
,..., y(n) ). |
|
|||
|
1 |
2 |
|
|
|
|
2) Аддитивность. |
случайных величин Y (1) ,...,Y (k ) и |
|||||
Если подсистемы |
||||||
Y (k +1) ,...,Y (n) независимы при каждой из гипотез, т. е. |
|
|||||
W (y(1) |
,,.., y(k ) , y(k +1) |
,..., y(n) ) = |
|
|
|
|
i |
|
|
|
|
(5.1.6) |
|
W (y(1) |
,..., y(k ) ) W (y(k +1) ,..., y(n) ), |
ι |
=1,2, |
|||
|
||||||
i |
i |
|
|
|
|
|
то информация, содержащаяся в системе |
Y (1) ,...,Y (n) , равна |
|||||
сумме информаций, содержащихся в подсистемах.
Неравенство для ошибок первого и второго рода. Рас-
смотрим задачу проверки гипотез. Пространство всех возможных значений сигнала Y = (Y (1) ,...,Y (n) ) разбиваем на две непе-
ресекающиеся части: Е1 и Е2. Если выборка y попала в область Е1, то считаем, что справедлива гипотеза Н1, в противном случае принимаем гипотезу Н2. При использовании такого правила ре-
130
шения возможны ошибки двух видов. 1) Ошибка первого рода.
Если справедливо предположение Н1 (сигнал Y имеет плотность вероятности W1(y(1) ,..., y(n) ) , но в результате опыта выбо-
рочное значение y попало в область Е2 и, следовательно, была принята гипотеза Н2, то возникает ошибка первого рода (неправильное отклонение гипотезы Н1).
2) Ошибка второго рода.
Если справедливо предположение Н2, но выборочное значение y попало в область Е1 и была принята гипотеза Н1, то возникает ошибка второго рода.
Вероятность ошибки первого рода
α = |
∫ |
. . . |
∫ |
W1(y(1) |
,..., y(n) )dy(1) ...dy(n) |
(5.1.7) |
|
Ε2 |
|
|
|
есть вероятность попадания y в область Е2 при условии, что y имеет распределение W1(y).
Вероятность ошибки второго рода
β = |
∫ |
. . . |
∫ |
W2 (y(1) |
,..., y(n) )dy(1) ...dy(n) |
(5.1.8) |
|
Ε1 |
|
|
|
есть вероятность попадания y в область Е1 при условии, что y имеет распределение W2(y).
Вероятности ошибок первого и второго рода связаны с информационными мерами Кульбака следующими неравенствами:
I(2 :1) ≥ β log |
|
β |
|
+(1− β)log |
1− β |
, |
(5.1.9а) |
|||
1−α |
α |
|||||||||
|
|
|
|
|
|
|
||||
I(1: 2) ≥α log |
|
α |
|
+(1−α)log |
1−α |
. |
(5.1.9б) |
|||
1− β |
|
β |
||||||||
|
|
|
|
|
|
|
||||
Неравенства обращаются в равенства тогда и только тогда, |
||||||||||
когда плотности вероятности W1(y) |
и W2(y) |
таковы, что |
||||||||
W (y(1) |
,..., y(n) ) |
= С |
|
|
|
|||||
1 |
|
|
|
|
|
|
(5.1.10а) |
|||
W (y(1) |
,..., |
y(n) ) |
|
|
||||||
|
1 |
|
|
|
||||||
2 |
|
|
|
|
|
|
|
|
|
|
для всех у из области Е1 и