5.4.6. Простейшие блочные линейные коды
Коды длины
и размерности
могут иметь разные значения кодового расстояния
и обладать поэтому разной помехоустойчивостью. Оптимальными называются коды, обеспечивающие при заданных
и
максимальную вероятность правильного приема кодового слова. Они, как правило, имеют наибольшее кодовое расстояние. Числа
и
определяют скорость кода, равную
двоичных единиц на 1 символ.
При заданной величине кодового расстояния
существует нижняя граница необходимого количества избыточных символов в кодовых комбинациях. Выражение для нижней границы
получается в результате приравнивания числа
различных ненулевых синдромов количеству
исправляемых кодом ошибок, начиная с их нулевой кратности.
Коды, для которых достигается нижняя граница, называются совершенными или плотноупакованными. Такие коды исправляют все ошибки кратности до
включительно и ни одной ошибки более высоких кратностей.
Рассмотрим некоторые простейшие оптимальные коды.
Код с простой проверкой на четность обозначается
и содержит слова с одним проверочным символом
. Проверочный символ есть сумма по модулю 2 информационных:
.
|
|
Видно, что
, если число единиц в информационной последовательности нечетное, и
, если число единиц – четное. Таким образом, наличие проверочного символа позволяет всем кодовым словам придать общий признак: четность числа единиц в слове.
Порождающая матрица кода имеет
строки
столбцов:
.
|
|
Любые строки матрицы содержат 2 единицы и отличаются значениями символов на двух позициях, поэтому кодовое расстояние равно 2. Следовательно, код может лишь обнаруживать однократные ошибки
.
Проверочная матрица кода содержит одну строку
.
|
|
и указывает, что для проверки основного признака кодовых слов надо сложить по модулю 2 все принятые символы.
Декодирование кода основано на проверке четности числа единиц в принятой последовательности
. Для этого вычисляется синдром, содержащий один компонент
,
|
|
или с учетом
и 
.
|
|
Значение
соответствует четному числу единиц в
. В этом случае принимается решение об отсутствии ошибок, т.е. полагается
. Ясно, что при действии ошибки четной кратности
, и данное решение будет неправильным.
Если
, то фиксируется наличие ошибки. Очевидно, значение
даст любая ошибка нечетной кратности, т.е. код обнаруживает часть ошибок большей кратности, чем
. Несомненным достоинством этого кода является высокая скорость, характеризуемая величиной
.
Код нечетной длины с повторением обозначается
, имеет кодовые слова
с одним информационным символом и
проверочными, которые повторяют информационный:
.
|
|
Порождающая матрица состоит из одной строки
, так что код с повторением имеет всего два слова: одно содержит только нули, второе – только единицы. Понятно, что кодовое расстояние равно
, отсюда
, .
|
|
Проверочная матрица кода:
.
|
|
имеет
строк и
столбцов и указывает, что сумма первого и любого другого символов кодового слова должна равняться 0. Число избыточных символов в коде достигает нижней границы, следовательно, коды нечетной длины с повторением относятся к совершенным.
Проверочная матрица кода
с простой проверкой на четность совпадает с порождающей матрицей кода с повторением
, а порождающая матрица первого кода подобна проверочной матрице второго. Такие коды называются дуальными.
Коды Хэмминга имеют кодовое расстояние
, исправляют все однократные ошибки или обнаруживают двукратные, т.е.
,
. Зависимости проверочных символов от информационных выбраны так, что каждой однократной ошибке соответствует свое ненулевое значение синдрома. Поэтому для кодов Хэмминга число ненулевых синдромов равно числу символов в кодовых комбинациях (числу однократных ошибок):
.
|
(5.24)
|
Следовательно, для кодов Хэмминга достигается нижняя граница числа
избыточных символов, а сами коды являются совершенными. Примеры кодов: (3, 1,3), (7,4, 3), (15, И, 3), (31,26, 3), (63, 57, 3),....
Единственный код Голея (23, 12, 7) завершает ряд совершенных кодов.
Расширенный код Хэмминга образуется из совершенного путем добавления общей проверки на четность, т. е. проверочного символа, равного сумме всех символов кода Хэмминга. Код имеет кодовое расстояние
, что позволяет исправить все однократные и одновременно обнаружить все двукратные ошибки. Такой режим целесообразен, в частности, в системах передачи информации с обратной связью.
При добавлении проверочного символа длина кода становится четной, а соотношение (5.24) преобразуется к виду
. Расширенные коды Хэмминга образуют ряд: (4, 1,4), (8,4,4), (16, 11,4), (32, 26,4), (64,57,4),....
Коды этого вида относятся к квазисовершенным, т.е. исправляющим все ошибки кратности по
включительно и часть ошибок кратности
.