Самым простым линейным блочным кодом является
(n,n-1)-код,
построенный с помощью одной общей проверки на четность. Например, кодовое слово
(4,3)-кода
можно записать в виде вектора-столбца:
= ( m0, m1,
m2, m0+m1+m2 ),(1.1)
гдеmi-символы информационной
последовательности, принимающие значения 0 и 1, а суммирование производится по
модулю 2 ( mod2 ).
Поясним
основную идею проверки на четность.
Пусть
информационная последовательность источника имеет вид
m= ( 1 0 1 ).(1.2)
Тогда
соответствующая ей кодовая последовательность будет выглядеть следующим образом
:
U= ( U0, U1,
U2, U3 ) = ( 1 0 1 0 ),(1.3)
где
проверочный символ U3 формируется путем суммирования по mod2
символов информационной последовательностиm :
U3 = m0
+m1 + m2 .(1.4)
Нетрудно
заметить, что если число единиц в последовательностиmчетно, то результатом суммирования будет 0, если
нечетно — 1, то есть проверочный символ дополняет кодовую последовательность
таким образом, чтобы количество единиц в
ней было четным.
При передаче по каналам
связи в принятой последовательностивозможно появление ошибок, то есть символы принятой последовательности
могут отличаться от соответствующих символов переданной кодовой последовательности
(нульпереходит в единицу, а 1 −в 0).
Если ошибки в символах
имеют одинаковую вероятность и независимы, то вероятность того, что в n-позиционном
коде произойдет только одна ошибка, составит
P1 = n× Pош× (1- Pош)n-1(1.5)
(то есть в
одном бите ошибка есть, а во всех остальных n - 1битах ошибки нет).
Вероятность того, что произойдет две ошибки,
определяется уже числом возможных сочетаний ошибок по две (в двух произвольных
битах ошибка есть, а во всех остальных n - 2битах ошибки нет):
P2 = Cn2× Pош× (1- Pош)n-2,(1.6)
и аналогично
для ошибок более высокой кратности.
Если считать, что вероятность ошибки на символ
принятой последовательности Pош достаточно мала (Pош<<1),
а в противном случае передача информации не имеет смысла, то вероятность
выпадения ровно lошибок составит Pl@ Pошl.
Отсюда видно, что наиболее вероятными
являются одиночные ошибки, менее вероятными — двойные, еще меньшую вероятность
будут иметь трехкратные ошибкии т. д.
Если
при передаче рассматриваемого (4,3)-кода произошла одна ошибка,
причем неважно, в какой его позиции, то общее число единиц в принятой
последовательности rуже не будет четным.
Таким
образом, признаком отсутствия ошибки в
принятой последовательности может служить четность числа единиц. Поэтому
такие коды и называются кодами с
проверкой на четность.
Правда,
если в принятой последовательности rпроизошло две ошибки,
то общее число единиц в ней снова станет четным и ошибка обнаружена не будет.
Однако вероятность двойной ошибки значительно меньше вероятности одиночной,
поэтому наиболее вероятные одиночные ошибки таким кодом обнаруживаться все же
будут.
На
основании общей идеи проверки на четность и проверочного уравнения (1.4)легко организовать схему кодирования - декодирования
для произвольного кода с простой проверкой на четность.