Понятие проверочной матрицы

Приведенные соотношения можно компактно отобразить в виде так называемой проверочной матрицы Н. Она содержит n столб­цов и r строк.

Проверочная матрица состоит из двух частей:

1. Запись в компактной форме соотношений для нахождения проверочных элементов b_i – подматрица размера (rk), расположена слева от пунктирной линии в матрице H. Каждый столбец приписывается определенному информационному элементу, начиная с a₁. Если данный информационный элемент участвует в определении рассматриваемого проверочного элемента (проверочный элемент определяет номер строки матрицы), то в соответствующем столбце ставится единица.

2. Единичная матрица размера (rr) – слева от пунктирной линии в проверочной матрице H. Строки единичной матрицы практически представляют собой синдромы проверочных элементов (см. таблицу), т.е. первая строка 1000 – синдром проверочного элемента b_1, вторая строка 0100 – синдром проверочного элемента b₂ и т.д.

Для рассмат­риваемого кода (9, 5) имеем матрицу H размером (49):

Из 1-й стро­ки матрицы H следует, что для формирования b₁ нужно взять элемент a₅: b₁=a₅. Из 2-й строки следует, что

Соответственно из 3-й и 4-й строк следуют соотношения:

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

C = ( C₁ , C₂ , … , C_r ) = A  H^T,

где А – принятая кодовая комбинация,

H^Т – транспонированная проверочная матрица.

При этом А является разрешенной кодовой комбинацией тогда, и только тогда, когда С = (00..0), и не является разрешенной кодовой комбинацией данного кода, если С  0.

Пример

Пусть принята кодовая комбинация 11001 1111 кода (9,5). По условиям предыдущего примера она является разрешенной. Проверочная матрица указанного кода приведена выше и имеет вид:

Найдем синдром полученной кодовой комбинации:

Равенство синдрома нулю подтверждает, что полученная кодовая комбинация является разрешенной.

Предположим, что принята комбинация с ошибкой в информационном элементе а₃ (см. предыдущий пример), т.е. приняли комбинацию вида 11101 1111. Найдем синдром полученной кодовой комбинации:

Ненулевой синдром свидетельствует о том, что полученная кодовая комбинация принята с ошибкой. Синдром совпадает с синдромом, найденным в предыдущем примере. Дальнейшие действия аналогичны: 0110 – в десятичной системе есть число 6. На 6-м условном номере согласно таблице стоит инфор­мационный элемент а₃. Следовательно, значение принятого элемента а'₃ нужно исправить: вместо «1» поставить «0». В результате кодовая комбинация принята правильно, т.е. ошибка исправлена: 11001.

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

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