Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
211
Удобно рассматривать эти проверки на четность или нечетность в терминах арифметических действий по модулю 2. В арифметике по модулю 2 существуют лишь два числа 0 и 1; сложение (обозначаемое 0) определяется по правилу
Нетрудно заметить, что это сложение совпадает с обычным, если не считать того, что 101 = 0. Умножение аналогично умножению в обычной арифметике и обозначается тем же знаком.
Легко убедиться (кто сомневается, может это непосредственно проверить), что обычные ассоциативный, коммутативный и дистрибутивный арифметические законы справедливы в арифметике по модулю 2. Это значит, что если а, b и с — двоичные числа, то
Существует несколько интерпретаций арифметических действий по модулю 2. Если интерпретировать 0 как четное, а 1 как нечетное число, то эти действия сложения и умножения задают правила комбинирования четных и нечетных чисел. Кроме того, можно интерпретировать сумму по модулю 2 последовательности двоичных чисел как остаток от деления на 2 их суммы в обычном смысле. Тогда легко убедиться, что проверочный символ в рассмотренном выше примере выбирается таким образом, чтобы сумма по модулю 2 всех символов равнялась 0. Если сумма по модулю 2 информационных символов равна 0, то проверочный символ выбирается равным 0; если сумма по модулю 2 информационных символов равна 1, то проверочный символ выбирается равным 1. Поэтому проверочный символ равен сумме по модулю 2 информационных символов.
В качестве простого (но чрезвычайно сильного) обобщения использования одной проверки на четность применительно к проверке последовательности информационных символов рассмотрим такое использование множества символов проверки на четность, при котором каждый из символов проверяет некоторое предварительно определенное множество информационных символов. Точнее, пусть и = = (uL, ..., Ui) обозначает последовательность L двоичных информационных символов; рассмотрим образование кодового слова х с длиной блока N > L из последовательности и по правилу
где 2 означает здесь сумму по модулю 2.
Элементы п при 1 ^ L и в соотношении
(6.1.2) представляют собой фиксированные двоичные символы, не за-
212
0 © 0 = 0; 001 = 1; 100 = 1; 101=0.
, /. /У . —'avvuunainDn^ it),
(ab) с = а (be) J
a®b = b®a\ ab = Ьа—коммутативность,
(а© Ь) с — ас © Ъс—дистрибутивность.
(6.1.1)
L
2 и, gi,nl L+l<ns^N,
(6.1.2)
Информационные Кодовые
последовательности слова
*1 = «1 ООО 000000
х2 = и2 001 001U0
010 010101
х3 = и3 011 011011
100 100011
#4 = ^2 ©^3 101 101101
*5 = «1®«з ПО 110110
*e = «i©«2 HI 111000
Рис. 6.1.1.
висящие от и; поэтому соотношения (6.1.1) и (6.1.2) задают отображение множества 2Ь возможных информационных последовательностей в множество 2L кодовых слов с длиной блока N. Назовем первые L символов в каждом кодовом слове информационными символами, а последние N—L символов проверочными символами.
Систематическим кодом с проверкой на четность называется двоичный блоковый код с произвольной длиной блока N, для которого множество сообщений представляет собой множество 2L двоичных последовательностей некоторой фиксированной длины L < N и в котором каждому сообщению u = (и1у ..., uL) сопоставлено кодовое слово х == (хъ ..., xN), определяемое соотношениями (6.1.1) и (6.1.2), где множество двоичных символов {g;,n} для 1 ^ I ^ L, L + 1 ^ п N является произвольным, но фиксированным и независимым от и. Разумеется, при каждом выборе совокупности {g; „} получаются различные систематические коды с проверкой на четность.
Например, пусть для L — 3, N = 6 вектор и = (иг, и2, %) обозначает информационную последовательность, а вектор х = (хх, х2, хз> х4, х5> хе) — соответствующее кодовое слово, образуемое так, как показано на рис. 6.1.1.
Общий код с проверкой на четность определяется так же, как систематический код с проверкой на четность, за исключением того, что при вычислении в нем кодовых слов по последовательностям сообщений используются не соотношения (6.1.1) и (6.1.2), а соотношение
х„ - -ijUiSi, l<n^N, (6.1.3)
/= 1
