Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
N
/(X'v, Y"U)< 2 ПХп\ Yп I -Sn-i, So)
п = 1
с равенством, когда входы независимы. Наконец, так как канал является не-разложимым, то / (Хп\ Yn I Sn-i. «о) / (Хп\ Yn \ Sn-i) при п -> со.
Это означает, что
С — max / (Хп\ Уп | Sn-i),
Qn (хп)
где распределение вероятностей для Sn-! является стационарным распределением вероятностей состояний q(sn-i). Поэтому пропускная способность равна пропускной способности ДКБП с
Р (Уп I хп) — 2 Р (Уп] хп, sn-i)q (sп -1) •
sn-1
635
6.1. (а)
*i=«i.
х2=и2,
Хз —Ы1 Ф и2. xt=u1,
¦*5 —Ы1 ® ы2-
Так как лгх = х2 = и2 и все символы являются линейными комбинациями их и ы2, то рассматриваемый код представляет собой систематический код с проверкой на четность.
(б)
(в)
10 111 0 110 1
Н--
1 1 1 1 0 1 1 о о 0 1 о 0 0 1
Синдром Шумовая последова Синдром Шумовая последова
тельность тельность
0 0 0 0 0 0 0 0 0 1 0 0 0 0 10
1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1
1 0 1 0 10 0 0 0 1 1 0 0 0 1 1 (или 10 10 0)
1 0 0 0 0 1 0 0 1 1 0 0 0 110 (или 1 0 0 0 1)
(г) Правильно декодируются пять конфигураций единичных ошибок и две конфигурации двойных ошибок; ни одна конфигурация тройных ошибок не декодируется правильно. Имеем
Ре = 1 —(1 —е)5 — 5в <1 —е)4—2е2 (1 — е)3.
6.2. Утверждение этой задачи трудно интерпретировать. Однако при тщательном изучении задачи легко заключить, что при вычислении хь в левой части регистра сдвига находятся четыре информационных символа, так что
=Ui @ И2 0 «4 .
После того как вычислено хд, все информационные символы сдвигаются на одну позицию вправо, а в левый разряд регистра подается нуль, так что хв = «10 ® «2 © и3. Аналогично *7 = и2 0 и3 ф ut.
“10 0 0 1 1 ol 0 10 0 111 0 0 10 0 1 1
0 0 0 1 1 0 1
t_ _
Н--
0 1 1 1 0 I
1 о о О 1 о О 0 1
Синдром Шумовая Синдром Шумовая
последовательность последовательность
0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0
1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 10 0
1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1
636
Pe=l—(I—e)7 — 7 (1—e)®8.
6.3.(а) Множество кодовых слов образуетгруппу (по сложению по модулю 2), а множество кодовых слов с четным числом единиц образует подгруппу^этой группы. Если рассматриваемая подгруппа не исчерпывает всей группы, то множество кодовых слов с нечетным числом единиц является смежным классом по этой подгруппе и, следовательно, имеет то же число элементов, что и сама подгруппа.
(б) При любом заданном п множество кодовых слов, для которых хт, tj. == О, образует подгруппу в группе кодовых слов. Если существуют какие-либо кодовые слова, у которых хт, п— 1, то множество таких кодовых слов образует смежный класс по рассмотренной выше подгруппе с числом элементов, равным числу элементов этой подгруппы. Отметим, что для любого имеющего смысл кода хт, п не должно быть равно нулю при всех т, поскольку в противном случае п-й символ может быть просто исключен из всех кодовых слов, без изменения величины Ре.
(в) Из результатов пункта (б) следует, что общее число единиц в коде не превышает MN12 (оно точно равно MN12 для любого имеющего смысл кода с проверкой на четность). Поэтому среднее число единиц в слове не превышает N/2.
6.4. (а) Пусть Xj(n), х2(п), ..., xi (я) являются кодовыми словами, лежащими
на расстоянии п от х0. Тогда ясно, что xt(rt) 0 xt.....х; (п) © хг различны,
лежат на расстоянии я от Xj и являются кодовыми словами. Если какое-либо другое кодовое слово, например х', лежит на расстоянии п от хх, то х" = х' © фх! лежит на расстоянии п от х0. Однако это предположение противоречит исходному, посколькух" должно принадлежать множеству х^я), ..., х; (я) и х" © ® Xi = х', поэтому число слов на расстоянии п от х0 равно числу слов на расстоянии п от Xj. Отметим, что этот результат справедлив также для патологического случая, когда существуют два или более кодовых слова, целиком состоящих из нулей. (Последнее может случиться лишь в несистематическом коде, у которого строки порождающей матрицы линейно зависимы. Естественно, что с практической точки зрения такие коды абсолютно бессмысленны.)
(б) Из пункта (а) следует, что если минимальное расстояние кода с провер* кой на четность равно dmin, то существует кодовое слово, лежащее на расстоянии dmin от х0, и не существует ни одного кодового слова (отличного от х0),. лежащего ближе к х0. Поэтому вес указанного выше слова равен dmin и не существует ни одного другого слова (отличного от х0), имеющего меньший вес.
