Систематические коды, рассмотренные выше (код Хэмминга и разделимый циклический код) удобно представить в виде матриц. Это свойство используется в процессах кодирования и декодирования. Практически все используемые коды являются линейными. Данный код также используется в системах передачи информации с обратной связью. Теперь поясним, как составить проверочные соотношения и определить коды ошибок si по известной проверочной матрице.

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

В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Если исходные k{\displaystyle k} бит код оставляет неизменными, и добавляет n−k{\displaystyle n-k}проверочных, такой код называется систематическим, иначе несистематическим.

Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую лёгкость кодирования и декодирования. Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку.

Помехоустойчивое кодирование

Код Рида-Маллера определяется при помощи порождающей матрицы, состоящей из базисных векторов. Циклические коды, кроме более простого декодирования, обладают и другими важными свойствами. Коды, удовлетворяющие этой границе с равенством, называются совершенными.

Если код порождён матрицей, не имеющей систематической формы (8.1.6), он называется несистематическим. Однако такая матрица эквивалентна матрице в систематической форме в том смысле, что одна может быть получена из другой элементарными операциями над строками и перемещением столбцов. Два линейных кода, порожденных двумя эквивалентными порождающими матрицами, называют эквивалентными и один может быть получен из другого перестановкой элементов.

Декодирование кода Хэмминга происходит по следующей схеме. Определяется синдромпринятой последовательностиS=y´, где — транспонированная проверочная матрица кода; y– принятый вектор. Помехоустойчивым (корректирующим) кодированием называется кодирование при котором осуществляется обнаружение либо обнаружение и исправление ошибок в принятых кодовых комбинациях. В избыточных кодах для передачи сообщений используется лишь часть кодовых комбинаций (разрешенные комбинации).

Непрерывные — коды, в которых сообщение не разбивается на блоки, а проверочные символы располагаются между информационными. В несистематических кодах эти условия не выполняются. Например, из принятых комбинаций 0110010, 1010010, 1000111 ошибочной является третья, т. к. W=4. Данный код способен обнаруживать все ошибки нечетной кратности и часть ошибок четной кратности.

В данном коде проверочные элементы bi находятся через линейные комбинации информационных символов ai, причем, для каждого проверочного символа определяется свое правило. В данном случае обведенные пунктиром проверочные элементы образуют единичную матрицу. Такое преобразование строк матрицы в столбцы называется транспонированием. При декодировании таких кодов (разделимых и неразделимых) используется Синдромный способ.

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

Разновидности ошибок

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

Число обнаруживаемых ошибок — число ошибок, при котором код может судить об ошибочной ситуации. Код Рида-Маллера — линейный двоичный блочный код. При определённом построении он может быть систематическим. В общем случае код Рида-Маллера не является циклическим. Для линейных кодов этот метод можно существенно упростить. Несмотря на то, что исправление ошибок в линейных кодах уже значительно проще исправления в большинстве нелинейных, для большинства кодов этот процесс все ещё достаточно сложен.

Коды CRC (cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Хотя линейные коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида-Соломона) не являются совершенными.

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

Это кодирование иллюстрируется рис. 8.1.1 для кода (7, 4) из примера (8.1.1). Систематический код может быть также укорочен размещением в начале информационного блока нулевых символов.

При передаче кодового слова по каналу связи возможно возникновение однократной ошибки в любом из его элементов. Для расчёта основных параметров кода Хэмминга можно задать количество проверочных элементов r, тогда длина кодовых слов n ≤ 2r-1, а количество информационных элементовk=n-r. Если синдром равен нулевому вектору, то считается, что слово передано без ошибок, иначезначение синдрома соответствует двоичному представлению номера разряда, в котором произошла ошибка.

Эти векторы образуют строки проверочной матрицы. Неразделимые — это коды, в кодовых комбинациях которых нельзя выделить проверочные разряды. Исторически «коды Хемминга» должны называться кодами Р. Фишера и были представлены в 1942г (Fisher R.A. The theory of confouding in factor to thr theory).