Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
6.4. Вес двоичной последовательности длины N определяется как число единиц в этой последовательности. Расстояние (Хэмминга) между двумя двоичными последовательностями длины N определяется как вес их суммы по модулю 2.
(а) Пусть Xi — произвольное кодовое слово в блоковом коде длины N с проверкой на четность и пусть х0 — кодовое слово, целиком состоящее из нулей, которое соответствует информационной последовательности, целиком состоящей из нулей. Показать, что при любом п < N число кодовых слов, лежащих на расстоянии п от хь совпадает с числом кодовых слов, лежащих на рассто-янии п от х0.
(б) Наименьшее расстояние dmin в двоичном коде определяется как наименьшее расстояние между всеми возможными парами кодовых слов. Показать, что для кода с проверкой на четность равно наименьшему весу кодовых слов, отличных от х0 = (0, 0, ..., 0).
(в) Показать, что если двоичный код с наименьшим расстоянием dmin используется в каком-либо канале с двоичной выходной последовательностью, то можно исправлять все комбинации, содержащие менее чем dmin!2 ошибок.
Указание: покажите, что если произошло менее чем dminj2 ошибок, то принятая последовательность будет ближе в смысле расстояния Хэмминга к переданному кодовому слову, чем к любому другому кодовому слову.
(г) Показать, что если двоичный код с наименьшим расстоянием dmin используется в двоичном стирающем канале, то можно исправлять все комбинации, содержащие менее чем dmin стираний.
6.5. Показать, что если код с проверкой на четность имеет нечетный наименьший вес, то прибавление проверочного символа, участвующего в проверке каждого символа в коде, увеличивает наименьший вес на 1.
6.6. (Граница Хэмминга.) Исправляющая способность двоичного блокового кода определяется как наибольшее целое е, такое, что все комбинации не более чем е ошибок в блоке могут быть исправлены.
(а) Сколько различных синдромных последовательностей имеется в (N, L)-коде с проверкой на четность? Сколько различных конфигураций из j ошибок могут появиться в последовательности N символов? Показать на основе этого, что исправляющая способность е для (N, L)-кода с проверкой на четность должна удовлетворять неравенству
(б) Показать, что в произвольном двоичном коде с длиной блока N и М кодовыми словами е должно удовлетворять соответствующему неравенству
553
Указание: рассмотреть множество последовательностей, расположенных на расстоянии, не большем е от каждого кодового слова и показать, что эти множества не должны пересекаться.
(в) Используя пункт (б) и задачу 6.4. (в), показать, что
L 2 J Л7
N \ 2
. / ) < М ’
/= о
6.7. (Граница Плоткина) (а). Используя решение задачи 6.3 (в), показать, что средний вес ненулевого кодового слова в (N, L)-коде с проверкой на четность N 2l
не превышает — ^------------j . Показать отсюда, что справедливо следующее неравен-
ство для djYiin:
N 2L \
dmin < 2 [ 2l-\ ) ' (I)
Заметим, что эта оценка согласуется с оценкой (5.8.1), справедливой для произвольных двоичных кодов.
(б) Приведенная выше оценка эффективна, когда L мало по сравнению с N. При больших значениях L более точной является приводимая ниже оценка. Показать, что при всех /, 1 < j < L,
N—L + j ( 2)
2J— 1
(П)
Указание: рассмотрите 21 кодовых слов в коде, у которых первые L — / информационных символов равны 0. Считая это множество кодовых слов с опущенными первыми L — / информационными символами (N — L + /, /)-кодом с проверкой на четность, примените оценку, полученную в пункте (а).
Дополнение. Показать, что (II) выполняется для любого двоичного кода с длиной блока N и числом кодовых слов, равным 2L.
(в) Пусть N и dmin фиксированы и N > 2dmin — 1. Показать, что число проверочных символов должно удовлетворять неравенству
N L > 2dmin 2 |_ log2 dmin _|.
Указание: положите /= 1 + Llogadmjn_| и воспользуйтесь тем, что числа N — L, dmin и j целые.
(г) Показать, что при фиксированном dmin/N < V2 при переходе к пределу jV оо получим, что скорость в двоичных единицах R = UN должна удовлетворять неравенству
р 1 2dmin
R<1~ N ¦
6.8. (Граница Варшамова (1957) — Гилберта.) Рассмотрим следующий метод построения проверочной матрицы для кода с проверкой на четность. При заданном числе г проверочных символов возьмем диагональную матрицу г X г и начнем добавлять строки по г двоичных символов выше этой совокупности из г строк. До некоторого заданного числа d имеется гарантия того, что каждая вновь выбираемая строка не является линейной комбинацией каких-либо d — 2 ранее выбранных строк. Процедура заканчивается, когда не найдется более строк, удовлетворяющих этому условию; длина блока N в коде равна общему числу строк, из которых состоит матрица.
