Методическое пособие 362
.pdfИнформационная избыточность — обычно явление естественное, заложена она в первичном алфавите. Корректирующая избыточность – явление искусственное, заложена она в кодах, представленных во вторичном алфавите.
Наиболее эффективным способом уменьшения избыточности сообщения является построение оптимальных кодов.
Оптимальные коды - коды с практически нулевой избыточностью. Оптимальные коды имеют минимальную среднюю длину кодовых слов – L. Верхняя и нижняя границы L определяются из неравенства
|
≤ ≤ |
|
+ 1 |
|
|
||
log |
|
log |
|
где Н — энтропия первичного алфавита, m — число качественных признаков вторичного алфавита.
В случае поблочного кодирования, где каждый из блоков состоит из М независимых буква1, а2, ..., ам, минимальная средняя длина кодового блока лежит в пределах
|
≤ |
|
< |
|
+ 1. |
(4.10) |
|
log |
|
log |
|||||
|
|
|
|
||||
|
|
|
|
|
Общее выражение среднего числа элементарных символов на букву сообщения при блочном кодировании
|
≤ < |
|
+ |
1 |
. |
(4.11) |
log |
log |
|
||||
|
|
|
|
|||
С точки зрения информационной нагрузки на символ сообщения поблочное кодирование всегда выгоднее, чем побуквенное.
39
4.2. Типовые примеры
Пример 4.2.1. По двоичному симметричному каналу связи с помехами передаются два сигнала x1 и x2 с априорными вероятностями P(x1)=3/4 и P(x2)=1/4. Из-за наличия помех вероятность правильного приема каждого из сигналов уменьшается до 7/8. Длительность одного сигнала τ = 0.1 сек. Требуется определить:
1)производительность и избыточность источника;
2)скорость передачи информации и пропускную способность канала связи.
Решение. Воспользуемся результатами решения примера 3.2.1, в котором получены:
• условные вероятности P(yj/xi) приема сообщений y1, y2 при условии передачи сообщений x1, x2
( 1⁄ 1) = |
7 |
; ( 1⁄ 2) = |
1 |
; ( 2⁄ 1) = |
1 |
; ( 2⁄ 2) = |
7 |
. |
||
|
|
|
|
|
|
|||||
8 |
8 |
8 |
|
|||||||
|
|
|
|
8 |
||||||
• количество информации на входе канала в расчете на одно сообщение
I(X) = 0.811 бит;
• среднее количество взаимной информации I(YX) в расчете на одно сообщение
I(YX) = I(X) – H(X/Y);I(YX) = 0.352 бит.
Рассчитаем на их основе информационные характеристики источника и канала связи:
1) согласно (4.2), производительность источника
Ĩ( ) = ( ) ( ) = |
( ) |
; Ĩ( ) = 8.113 бит⁄сек. |
|
40
2) согласно (4.1), избыточность источника при максимальном количестве его информации I max= 1.
= 1 − |
( ) |
; |
= 0.189. |
|
|
|
|||
|
||||
|
|
|
|
|
3) согласно (4.3), скорость передачи информации
( ) = |
( ) |
; |
( ) = 3.525 бит⁄сек. |
|
4) согласно (4.6), при вероятности ошибки p0= P(y1/ x2) илиp0= P(y2/ x1) пропускная способность канала на сигнал
С1 = 1 + 0 log2 0 + (1 − 0) log2(1 − 0)
и составляет C1 = 0.456 бит на один сигнал, а пропускная способность в единицу времени
= 1 ; = 4.564 бит⁄сек.
Сравнение C и Ĩ показывает, что пропускная способность данного канала не обеспечивает передачи информации со сколь угодно малой вероятностью ошибки путем помехоустойчивого кодирования, поскольку Ĩ>C (согласно теореме Шеннона).
Пример 4.2.2. Число символов алфавита источника i = 1 .. 4 (или j = 1 .. 4). Вероятности появления символов источника
P(x1) = 0.5, P(x2) = 0.25, P(x3) = 0.125 и P(x4) = 0.125 .
Между соседними символами имеются корреляционные связи, которые описываются матрицей условных вероятностей
P(xi/xj):
41
|
|
13⁄ |
3⁄ |
0 |
0 |
|
|
|
16 |
16 |
|
|
|
( ⁄ ) = |
1⁄ |
1⁄ |
3⁄ |
0 |
, |
|
8 |
2 |
8 |
|
|||
|
|
0 |
0 |
0 |
|
|
|
|
1 |
|
|||
|
|
[ 1⁄2 |
1⁄4 |
1⁄4 |
|
|
|
|
0] |
|
|||
например, P(x2/x2) = 0.5.
Требуется определить избыточность источника R1 при статистической независимости символов и R2 при учете зависимости между символами.
Решение. Для оценки избыточности нужно найти безусловную энтропию H1(X) и условную энтропию H2(X/X) источника.
В случае не учета статистической связи на основании (2.1) для H1(X) имеем
4
1( ) = − ∑ ( ) log2 ( );
=1
H1(X) = 1.75 бит.
С учетом корреляционной связи на основании (2.5) или
(2.7)
4 4
2( ⁄ ) = − ∑ ( ) ∑ ( ⁄ ) log2 ( ⁄ );
=1 =1
H2(X/X) = 0.887 бит.
Максимально возможная энтропия источника с четырьмя символами определяется мерой Хартли
Hmax = 2 бит.
42
Cледовательно, |
|
|
|
|
|
|
1 = 1 − |
1( ) |
; |
|
1 = 0125. |
||
|
|
|
||||
|
|
|
|
|
||
|
|
|
|
|
|
|
2 = 1 − |
2( ⁄ ) |
; |
2 = 0.556. |
|||
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пример 4.2.3. По каналу связи передается ансамбль из 3-х сигналов xi, i= 1 .. 3 с длительностью τ= 0.01 сек и частотой следования F = 1/τ. Источник сигналов имеет матрицу P(X) безусловных вероятностей матрицу P(x) безусловных вероятностей
0.4
( ) = (0.3) ; т. е. ( 2) = 0.3. 0.3
Канал связи характеризуется при p1= 10 -2, p2= 2·10 -2, p3= 0.97 и матрицей условных вероятностей P(yj/xi), где yj, j= 1 .. 3 − ансамбль сигналов на выходе канала (т.е. приемника). Определить пропускную способность канала. Сравнить производительность источника и пропускную способность канала.
Решение. По условию задачи скорость v(x) создания сигналов и скорость v(k) их передачи по каналу равны, т.е. v(x)=v(k). Эти скорости соответствуют частоте следования сиг-
налов, т.е. v(x) = F и v(k) = F.
Согласно определению (4.5), пропускная способность
C = v(k) max{I(YX)}=Fmax{I(YX)},
где максимум ищется по всем распределениям вероятностей
P(X) и P(Y).
Найдем безусловные вероятности P(yi):
43
3
( ) = ∑ ( ) ( ⁄ ) →
=1
→ ( 1) ( ⁄ 1) + ( 2) ( ⁄ 2) + ( 3) ( ⁄ 3).
Следовательно,
( 1) = ( 1) 3 + ( 2) 2 + ( 3) 1;( 2) = ( 1) 1 + ( 2) 3 + ( 3) 2;( 3) = ( 1) 2 + ( 2) 1 + ( 3) 3;
0.397( ) = (0.301).
0.302
Согласно (2.1), безусловная энтропия H(Y) выходного сигнала
( ) = − ∑ ( ) log2 ( );
H(Y) = 1.572 bit.
На основании (2.7) с учетом P(xi,yj)=P(xi)P(yj/xi) условная энтропияH(Y/X) выходного сигнала Y относительно входного
X
3 3
( ⁄ ) = ∑ ∑ ( ) ( ⁄ ) log2 ( ⁄ ).
=1 =1
Раскрывая знак суммы при P(x)(p1 , p2 , p3), имеем
( ⁄ ) = −( ( 3) + ( 1) +
+ ( 2))( 1 log2 1 + 2 log2 2 + 3 log2 3).
Так как сумма вероятностей
44
( ( 3) + ( 2) + ( 1)) = 1,
то условная энтропия принимает вид
( ⁄ ) = − 3 log2 3 − 1 log2 1 − 2 log2 2
и не зависит от статистик входного и выходного сигналов. Она полностьюопределяется параметрами канальной матрицы.
Согласно (3.3), количество информации на выходе канала
связи
I(XY)=H(Y)-H(Y/X)
будет максимально при максимуме энтропии приемника H(Y). Энтропия H(Y)максимальна в случае равной вероятности сигналов на выходе канала, т.е.когда при числе сигналов N= 3 их вероятности
P(yj) = 1 / N; P(y1) = 0.333 ; P(y2) = 0.333 ; P(y3) = 0.333.
В этом случае энтропия выходных сигналов канала соответствует мере Хартли и равна log2 , т.е.
H(Y)max= l·log2 ; H(Y)max = 1.585 бит.
Таким образом, максимальное количество информации на выходе каналасвязи, определяемое как
I(X,Y)max=H(Y)max-H(Y/X),
Будет
( ) = log2 + 3 log2 3 + 1 log2 1 + 2 log2 2.
Пропускная способность канала
= (log2 + 3 log2 3 + 1 log2 1 + 2 log2 2)
45
= (log + log + log + log )
и составляет C = 136.302 бит/сек.
Согласно (2.1), безусловная энтропия H(X) входного сигнала
( ) = − ( )log ( );
H(X) = 1.571 бит.
При этом, согласно (4.2) и (3.2), производительность Ĩ источника
Ĩ = ( ) → (− log − log − log )
и составляет Ĩ = 157.095 бит.
Так как Ĩ >C, то канал связи нельзя использовать для передачи информации от данного источника.
Пример 4.2.4. Определить максимально возможную скорость передачи информации по радиотехническому каналу связи пункта управления с телеуправляемой ракетой, если полоса пропускания канала связи равна F=3MHz, а минимальное отношение сигнал/шум по мощности Pxξ=Px/Pξв процессе наведения ракеты на цель Pxξ= 3.
Решение. На основании (4.8) пропускная способность данного непрерывного канала
C= F · log2( 1+ Pxξ)
и составляет C = 6 · 106бит/сек.
46
Пример 4.2.5. Сообщения составлены из пяти качественных признаков (m1 = 5). Длительность элементарной посылки τ = 20 мсек. Определить:
а) чему равна скорость передачи сигналов; б) чему равна скорость передачи информации. Решение. Скорость передачи сигналов
1= = 50 символ/сек.
Скорость передачи информации
= = log2 = log2 5 = 116 бит/сек.0.02
Задача 4.2.6. Сообщения, составленные из букв русского алфавита, передаются в коде Бодо при помощи стартстопного телеграфного аппарата. В начале передачи идет стартовая посылка, а в конце— стоповая. Буква передается пятью элементарными посылками длительностью τ1 = 20мсек(каждая). Длина стартовой посылки τ2 = 30мсек, стоповой — τ3 = 45мсек. Определить:
а) чему равна скорость передачи информации; б) чему равна скорость передачи информационных симво-
лов;
в) время передачи сообщения, состоящего из 450 букв. Решение. а) Скорость передачи информации
4.36
= 0.02 · 5 = 43.6 бит/сек.
б) Скорость передачи информационных символов
= |
1 |
= |
1 |
= 50 символов/сек. |
|
|
|
|
|||
|
0.02 |
||||
в) Время передачи сообщения, состоящего из 450 букв,
= 1 · 5 · 450 + 2 + 3 = 45.075 сек.
47
Задача 4.2.7. Сообщения передаются в двоичном коде (т = 2). Время передачи 0 τ0 = 1 сек, длительность импульса, соответствующего 1, τ1 = 5 сек. Определить скорость передачи информации для случаев:
а) когда символы равновероятны и независимы; б) вероятность появления символа 0 р0 = 0,37, вероятность
появления символа 1 р1= 0,63;
в) р0 = 0,2; р1 = 0,8; г) р0 = 0,02; р1 = 0,98.
Решение. Символы равновероятныи независимы:
а) = |
|
|
= |
|
|
|
log2 2 |
= |
1 |
≈ 0.33 бит/сек. |
|||||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
ср |
1 |
( |
|
|
+ ) |
3 |
||||||||||
|
|
|
|
|
0 |
|
|
|
|
||||||||
|
|
|
2 |
|
|
|
1 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
− ∑ |
log |
|
|
||||
|
б) = |
|
|
|
|
= |
|
=1 |
|
|
|
2 |
= |
||||
|
|
|
|
∑ |
|
|
|||||||||||
|
|
|
|
|
|
|
ср |
|
|
=1 |
|
|
|
||||
=−(0.37 log2 0.37 + 0.63 log2 0.63) = 0.27 бит/сек.
0.63∙ 5 + 0.2 ∙ 1
в) = |
2 |
= |
−(0.8 log2 0.8 + 0.2 log2 0.2) |
= 0.4 бит/сек. |
|||||||
ср |
0.8 ∙ 5 + 0.2 ∙ 1 |
|
|||||||||
|
|
|
|
|
|
|
|||||
г) = |
2 |
= |
|
−(0.98 log2 0.98 + 0.02 log2 0.02) |
= 0.3 бит/сек. |
||||||
|
|
|
|
|
|
|
|||||
|
ср |
|
|
0.98 ∙ 5 + 0.02 ∙ 1 |
|
|
|
||||
Задача 4.2.8. Чему равна пропускная способность симметричного канала, если источник вырабатывает со скоростью 2 знака в секунду сообщения, закодированные кодом с основанием m= 10, а вероятность ложного приема рл = 0,03?
Решение.
|
= [log + log |
0 |
+ (1 − |
) log(1 − )] = |
|
|
|
||||
п |
0 |
− 1 |
0 |
0 |
|
|
|
|
|
||
48