Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
2! — 1
(в) Преобразуя приведенную выше границу, получаем нижнюю границу для числа проверочных символов N — L при заданном dmin
N — L > 2dmin (l —2~~ i) — j, i j I..
При /= L log2 dmin J-f- 1 она принимает вид
N — L > 2dmin—2{log*d™in~ -log2d™ni J) _[¦ .l0g2dmjn J+l],
Нетрудно увидеть, что 2 dmin = 2'‘I°S2rfm*n~* Теперь заметим, что все слагаемые правой части, кроме среднего, являются целыми числами. Однако среднее слагаемое строго меньше 2, поэтому N — L > 2dmin — 2—log2dOT;n+l _]¦ Теперь обе части неравенства целочисленные, так что можно увеличить правую часть на 1 и заменить знак > на >, N — L > 2dmin ¦— 2 — L log2dmin J-
(г) Разделив обе части приведенного выше неравенства на N и подставив R — L/N, получаем
1 г. 2dmin . 2-j-log2 d.min J i ?\ ^ ~ •
N N
Зафиксировав R, получим в пределе при N ->- оо , что последнее слагаемое исчезает; это приводит к неравенству
2dmjn
R
N
6.8. (а) Способ построения кода гарантирует нам, что все множества d — 1 строк в матрице являются множествами линейно независимых строк. Если обозначить через h„ п-ю строку матрицы Я, то для того чтобы х=(*1, ..., xN) было ко-
N
довым словом, необходимо, чтобы хН = 2 xnhn = 0. Отсюда видно, что для
п— 1
того чтобы х было кодовым словом, необходимо, чтобы строки Я, соответствующие тем позициям, в которых х имеет единицы, были бы линейно зависимыми. Поэтому не существует ненулевого кодового слова, имеющего вес, меньший или равный d — 1, и поэтому dmin > d.
(б) Существенным является здесь вопрос об интерпретации, так как, например, можно рассматривать hj 0 h2 и как линейную комбинацию первых двух строк, и как линейную комбинацию какого-либо множества строк, в которое входят первые две строки. В интересующей нас задаче нужно при подсчете учесть hi 0 h2 (и каждую другую комбинацию) только один раз. Для этого найдем число подмножеств из d — 2 или меньшего числа строк, которые могут быть составлены из N строк; оно равно
d — 2
Если это число линейных комбинаций меньше чем 2Г, т. е. меньше общего числа возможных строк, то можно выбрать другую строку. Поэтому при окончании процесса выбора строк имеем
1^\ > 2r — 2N~L. г "S'О ' ' /
6.9. (а)
1 1 о Г 10 11 0 111 10 0 0.
0 10 0 0 0 10 0 0 0 1
(б)
G =
“10 0 1 10 1 0 10 10 11 0 0 10 111
Н--
Синдром Шумовая Синдром Шумовая
последовательность поел едовательн ост
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0
о
1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0
1 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0
0 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0
1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0
0 1 0 0 0 0 0 0 1 0 0 1 I 0 0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0
0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0
Для кода I Ре _ -(1- -е у --- 7е (1- е)6 --- 7г2 (1 --- е)5 -8 ч 1 ---
Для кода II Ре — \—(1—е)7 — 7е(1—е)° — 8е2(1—в)5. Ре (код 1) — Ре (код II) = в2 (1 — е)5—s3 (1 —е)4 = е2 {1 —е)5
Поэтому вероятность ошибки для кода I больше.
>0.
(г) Для кода 1 dnlin = 4, Дл« кода II dmin= 3.
(д) Рассмотренные два кода дают требуемый контрпример.
6.10. Пусть g1( g2, ..., gL — строки порождающей матрицы. Так как по предположению они линейно зависимы, то существует двоичная ненулевая последовательность и.г, ..., uL, такая, что
Таким образом, ненулевая информационная последовательность и = (иj, ..., uL) отображается в кодовое слово, целиком состоящее из нулей. Если и'— произвольная информационная последовательность, то информационная последовательность и' ® и отображается в то же самое кодовое слово, что и и'.
6.11. (а) Пусть 1тг, .... hд?_^—столбцы матрицы Яг. Тогда из соотношения
640
xtfa=0 вытекает равенство xh, = 0 при 1 <i<N—L xh; = 0 означает, что
Это доказывает, что х Н2 = 0 => хЯ, = 0; аналогичные рассуждения, на; чинающиеся с рассмотрения Н1г доказывают, что хНг = 0 =>хЯ2 = 0.
(б) Соотношение ejW2 Ф е2#2 выполняется тогда и только тогда, когда
