Построение двоичного линейного кода

Когда речь идет о линейных кодах, кодовые комбинации принято называть кодовыми векторами (КВ).

Линейный код обычно обозначают как , где – значность КВ, – число информационных символов. Следовательно, число проверочных (контрольных) символов .

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

В случае передачи двоичным кодом величина должна удовлетворять неравенству:

(2.9)

(единица вычитается из потому, что нулевая комбинация обычно не используется при передаче, т.к. не изменяет состояния канала).

После выбора определяется число контрольных разрядов , необходимое для получения требуемой корректирующей способности кода.

Если требуется исправлять все одиночные ошибки (кодовое расстояние кода ), величина выбирается из следующих соображений. Под действием помех может быть искажен любой символ в n-значном КВ, т.е. для каждого кодового вектора возможно исходов передачи ( учитывает правильную передачу). С помощью контрольных символов нужно различать все возможные исходы передачи. Это возможно, если выполняется условие:

, (2.10)

где – число сочетаний из по 1.

Уравнение (2.10) является трансцендентным относительно , поэтому при небольших величину определяют простым подбором, принимая минимальное значение , удовлетворяющие (2.10).

При больших для определения при можно использовать эмпирическое соотношение:

, (2.11)

где – знак округления до ближайшего большего числа.

Если необходимо исправлять не только все единичные, но и все двойные независимые ошибки, величина должна выбираться в соответствии с условием:

(2.12)

После определения составляется образующая матрица, состоящая из строк и столбцов. В общем виде образующая матрица имеет вид:

(2.13)

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

В качестве строк образующей матрицы могут быть взяты любые КВ, отвечающие следующим условиям. Они должны быть:

1) n-значными;

2) отстоящими друг от друга на заданное кодовое расстояние;

3) ненулевыми;

4) иметь вес не менее заданного кодового расстояния кода;

5) линейно-независимыми.

Последним шагом в построении линейного кода является составление проверочной (контрольной) матрицы, имеющей n столбцов и m строк. В общем виде контрольная матрица имеет вид:

(2.14)

Элементы , составляющие контрольную матрицу, представляют собой элементы КВ, ортогональных любым разрешенным кодовым векторам. Если обозначить через V-разрешенные КВ данного линейного кода, а через U-вектор контрольной матрицы, то условие ортогональности КВ V и U в математической форме записывается так:

, (2.15)

где и , , – соответственно, элементы разрешенных КВ и векторов контрольной матрицы.

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

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

Пример

Построить линейный -код, позволяющий исправлять все одиночные ошибки, если требуемый объем кода .

Решение.

1. Определяем требуемое число информационных разрядов. Согласно (2.9) имеем: , , откуда .

2. В соответствии с (2.11) определяем требуемое число контрольных разрядов:

, .

Следовательно, , а код имеет формат (7, 4).

3. Составляем образующую матрицу .

Так как линейный код должен исправлять однократные ошибки, то кодовое расстояние между комбинациями образующей матрицы должно удовлетворять условию (2.8): . Учитывая, что векторы образующей матрицы (2.13) являются разрешенными, в дальнейшем на основании условия ортогональности векторов V и U подбираются коэффициенты так, чтобы в контрольной матрице не было нулевых и одинаковых столбцов. В результате выполнения этих действий получена контрольная матрица (2.16). (При выполнении контрольной работы матрица Н будет задана.)

(2.16)

Кодирование

Разрешенные КВ должны быть ортогональны векторам контрольной матрицы. Исходя из этого, найдем условия, которым должны удовлетворять КВ кода, построенного по контрольной матрице (2.16):

–

–

=

–

–

=

–

–

=

Итак, любой формируемый КВ должен удовлетворять условиям:

(2.17)

Для любой информационной части равенства (2.17) достигаются путем подбора контрольных разрядов, в качестве которых выбираются разряды, встречающиеся только в одной проверке. Таковыми являются 1, 4 и 7 разряды (соответствуют столбцам контрольной матрицы , содержащим только одну 1). Разряд обеспечивает ортогональность с вектором ; – с ; – с .

Из системы проверочных равенств (2.17) определяем, какими должны быть проверочные символы при формировании конкретной комбинации безизбыточного кода:

(2.18)

Пример

Закодировать число линейным кодом, использующим контрольную матрицу (2.16).

Решение

.

Начиная со старших разрядов, располагаем полученную безизбыточную двоичную комбинацию на отведенные ей позиции (2, 3, 5 и 6 разряды).

Контрольные разряды

Подставляя значения информационных символов в уравнения (2.18), находим значения проверочных символов:

Подставив полученные значения контрольных разрядов на отведенные позиции, получаем: