Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 308

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 302 303 304 305 306 307 < 308 > 309 310 311 312 313 314 .. 355 >> Следующая


(в) Чтобы преобразовать одно кодовое слово в другое, необходимо изменить в нем не менее dmin символов. Если при передаче произошло менее чем dmin/2 ошибок, то для того, чтобы перевести принятую последовательность в кодовое слово, отличное от переданного, необходимо еще изменить в ней более чем dmin/2 других символов. Поэтому декодер, декодирующий в ближайшее кодовое слово, во всех случаях, когда произошло менее чем dmin!2 ошибок, декодирует правильно.

(г) Если существует лишь одно кодовое слово, совпадающее с принятой последовательностью во всех нестертых позициях, то стирание может быть исправлено однозначно. Так как никакие два кодовых слова не могут совпадать более чем в N — dmin позициях, то декодирование будет правильным во всех случаях, когда произошло менее чем dmin стираний.

6.5. Дополнительный проверочный символ изменяет проверочную матрицу Я, превращая ее в матрицу Н

Н’= Н

Для того чтобы хН' = 0, необходимо, как это следует из рассмотрения послед-N

него столбца Н', чтобы 2 хп =0; отсюда вытекает, что любое кодовое слово имеет

п= 1

четное число единиц. В свою очередь, из последнего утверждения следует, что

637
вес ненулевого слова с минимальным весом является четным и что последняя проверка па четность увеличивает на единицу вес каждого обладающего нечетным весом слова первоначального кода.

6.6 (а) Число синдромных последовательностей (N,L)-Kojxa с проверкой на четность равно 2N~L (мы исключаем тривиальный случай, когда строки матрицы G линейно зависимы и когда даже при отсутствии ошибок декодирование может, быть неправильным). Число различных шумовых последовательностей, состоя-

?, / N\

1цих из е или менее ошибок, равно 2 ; для того чтооы исправлять все

/= о\ / 1

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

(б) Пусть для произвольного двоичного кода существует последовательность, которая лежит на расстоянии е или меньшем от каждого из двух кодовых слов, тогда при приеме этой последовательности, независимо от того, какое кодовое слово было декодировано, может произойти ошибка декодирования, когда число ошибок при передаче было равным или меньшим е, если передавалось другое кодовое слово. Поэтому вокруг каждого кодового слова должно быть множе-%(N\

ство 2 последовательностей, лежащих на расстоянии е или меньшем от этого

/=о\ ])

слова, и эти множества, относящиеся к различным кодовым словам,не должны пересекаться. Так как существуют 2N различных последовательностей и М кодовых слов, то

(в) Для кода с четным минимальным расстоянием dmin существует последовательность, лежащая на расстоянии dmin/2 от каждого из двух ближайших кодовых слов, и поэтому e<dmin/2. Для кода с нечетным минимальным расстоянием существует последовательность, лежащая на расстоянии (dmin + 1)/2 от одного кодового слова и на расстоянии (dmin — 1)/2 от другого кодового слова; поэтому снова е < dmin!2. Сопоставляя этот результат с результатом задачи 6.4. (в), dmin 1 I

----2---- |; поэтому из пункта (б) данной задачи следует, что для

получаем е=

любого двоичного кода с М кодовыми словами, длиной блока N и минимальным расстоянием dmin справедливо

V iN

/Й, \1> М

6.7. (а) Согласно задаче 6.3. (в), общее число единиц во всех кодовых словах (N, ?)-кода не превышает (2lN)/2. Так как число ненулевых слов равно 2l — 1 (снова исключаем тривиальный случай, когда строки порождающей матрицы

N 2l

зависимы), то средний вес ненулевого слова не превышает ----------------. Так как

все ненулевые слова не могут одновременно иметь веса, превышающие средний N 21

вес, то dmin ¦; _ i'

638
(б) По существу, к указанию, приведенному в задаче, нечего добавить. Заметим, что в произвольном двоичном коде с длиной блока N и 2L кодовыми словами, первые L — / символов кодовых слов могут принимать лишь 2L~' различных значений; поэтому должно существовать по крайней мере 2! кодовых слов, совпадающих в первых (L — /) символах. Рассматривая оставшиеся N ¦— L + + / символов этих 21 кодовых слов как код, мы убедимся, что два из этих кодовых

N ~ L + ] ( У \

слов отличаются не более чем в -----2----' \2f~I~lJ позициях. Так как эти

два кодовых слова совпадают в первых L — j символах, то имеем

N-L+j{ 2> . .

при всех /, 1 / <; L.
Предыдущая << 1 .. 302 303 304 305 306 307 < 308 > 309 310 311 312 313 314 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed