3.3. Основы матричного построения систематических кодов

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

Сложим по модулю два две разрешенные кодовые комбинации систематического кода:

Нетрудно видеть, что

Таким образом, проверочные разряды суммы по модулю два двух разрешенных комбинаций образуются по тому же правилу, что и для каждой разрешенной комбинации. Отсюда сумма двух разрешенных комбинаций систематического кода также является разрешенной комбинацией. Данное обстоятельство дает возможность определить все разрешенные кодовые комбинации, располагая лишь ограниченным количеством разрешенных комбинаций. Для этого данные исходные комбинации выбираются специальным образом [90, 122, 123, 140].

1. Все исходные комбинации должны быть различны.

2. Нулевая комбинация не должна входить в число исходных.

3. Все исходные комбинации должны быть линейно независимы, т. е. должно соблюдаться равенство

при всех значениях за исключением

4. Каждая исходная кодовая комбинация, как и любая ненулевая разрешенная комбинация, должна содержать количество единиц не менее

5. Кодовое расстояние между любыми парами исходных комбинаций не должно быть меньше Подобранные определенным образом исходных кодовых комбинаций однозначно определяют систематический код. Эти комбинации записывают в виде матрицы состоящей из строк и столбцов. Такая матрица называется производящей:

Производящая матрица может быть представлена двумя подматрицами — информационной и проверочной. Число столбцов информационной подматрицы равно число столбцов проверочной подматрицы равно

Теорией и практикой установлено [90], что в качестве информационной подматрицы удобно брать единичную матрицу в канонической форме

Эта матрица имеет столбцов и строк.

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

1. Количество единиц в строке должно быть не менее

2. Сумма по модулю два двух любых строк не должна иметь менее единиц.

При соблюдении перечисленных условий любую производящую матрицу систематического кода можно привести к следующему виду:

Пример. Построить матрицу систематического кеда, способного исправлять одиночную ошибку при передаче 16 сообщений

Так как то и число строк производящей матрицы С должно быть равно четырем. Число столбцов матрицы равно длине кода где Число проверочных разрядов.

Для Пользуясь табл. 15, находим Следовательно, число столбцов подматрицы равно трем.

Учитывая то, что количество единиц в строке подматрицы к должно быть не менее единиц, выбираем следующие комбинации:

Окончательный вид производящей матрицы:

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

Все 16 комбинаций кода с производящей матрицей выглядят следующим образом:

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

Алгоритм образования проверочных символов с помощью матрицы к по известным информационным может быть записан в виде

Для каждой конкретной матрицы существует своя, одна единственная система проверок. Проверки производятся по следующему правилу: в первую проверку вместе с проверочным разрядом входят информационные разряды, которые соответствуют единицам первого столбца подматрицы во вторую проверку входят второй проверочный разряд и информационные разряды, соответствующие единицам второго столбца подматрицы Число проверок равно числу проверочных разрядов кода (числу столбцов подматрицы

Пример. Производящая матрица кода имеет вид

Согласно приведенному выше правилу построения система проверки кода о матрицей имеет вид

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

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

Следовательно, проверочная матрица

С помощью этой матрицы операция кодирования осуществляется очень просто. Позиции, занимаемые единицами в -строке подматрицы определяют те информационные разряды, которые должны участвовать в формировании проверочного разряда.

Пример. Построить проверочную матрицу кода образующая матрица которого имеет вид

Находим сначала подматрицу которая является транспонированной по отношению к подматрице

Затем к ней справа приписываем единичную матрицу и получаем проверочную матрицу

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

Подводя итоги рассмотренному выше матричному представлению кодов, можно сделать следующие выводы.

1. Образующая матрица позволяет представить весь набор кодовых комбинаций в очень удобной и компактной форме. С помощью этой матрицы довольно просто построить любую кодовую комбинацию по известным информационным символам, т. е. представить неизбыточное сообщение в закодированном данным кодом виде.

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

Пример. Образующая матрица кода (11, 7) имеет вид

Найти закодированную комбинацию неизбыточного сообщения 1101001.

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

Таким образом, закодированное сообщение имеет вид 11010011100.

Пример. Найти соотношения для получения проверочных символов кода, матрица которого имеет вид

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