Синдромное декодирование линейных блоковых кодов

 

В линейном блоковом коде l -й символ выходного слова кодера представляет собой линейную комбинацию k информационных входных символов. В матричной форме записи это выглядит как:

,                                          (3.10)

где – порождающая матрица (n, k) кода, содержащая k строк и n  столбцов; – вектор информационной последовательности.

При этом, код может быть представлен в эквивалентных систематической и несистематической формах.

Для систематического (n, k) кода первые k символов кодового слова являются информационными. Порождающая матрица систематического кода имеет вид:

        (3.11)

или                ,                                              (3.12)

где - единичная матрица k × k; ® k ×(n -k) матрица, определяющая (n -k) столбцов избыточных (проверочных) символов кода.

Матрицу в несистематической форме можно привести к систематической форме операциями над строками, перестановкой столбцов.

Пример. Линейный блоковый код Хемминга (7,4) задан порождающей матрицей кодера:

 

.

=[х _{m 1} , х _{m 2} , х _{m 3} , х _{m 4} ] – входное информационное слово кодера.

Привести матрицу к систематической форме, найти выходное m -ое кодовое слово кодера и проверочные биты этого слова.

Решение:

Матрицу приведем к систематической форме перестановкой строк

                             (3.13)

Выходное кодовое слово  кодера в систематической форме равно

             .

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

                                  (3.14)

 

Найдем алгоритм синдромного декодирования.

По определению векторного пространства (3.2) набор из всех векторов с n элементами образует векторное пространство S.

Выберем набор из k < n линейно независимых векторов из S и из них сформируем набор всех линейных комбинаций этих векторов. Результирующий набор образует подпространство S_c размерности k в пространстве S.

Любой набор из k  линейно независимых векторов образует базис подпространства S_c.

Набор векторов из пространства S, которые ортогональны каждому вектору базиса в S_{c ,}   образует ортогональное к S_c подпространство (нуль - пространство) размерности ( n -k).

Таким образом, линейному ( n, k ) коду из подпространства S_c соответствует дуальный ( n, n - k ) код из нуль - пространства, т.е. любое кодовое слово Y_m из множества ( n, k ) кода ортогонально любому кодовому слову дуального кода, т.е. строке матрицы  :

                            (3.15)

где - означает вектор-столбец из (n - k) нулевых элементов.

Поскольку эта ортогональность справедлива для любого кодового слова ( n, k ) кода, формируемого матрицей, то можно записать

                            (3.16)

где - матрица k ×(n - k) со всеми нулевыми элементами.

Таким образом, матрица H^T является проверочной (синдромом) для порождающей матрицы систематического ( n, k ) кода и определяется в систематической форме из уравнения (3.16) в виде:

              (3.17)

поскольку она удовлетворяет этому уравнению:

 

где 

 .                           (3.18)

Для линейного блокового кода можно, на основании условия ортогональности (3.15) при, определить верхнюю границу                                                        (3.19)

Следовательно, если d_min нечетно, то можно увеличивать его на 1 и сформировать расширенный код (n +1, k). Его проверочная матрица

                        (3.20)

где - проверочная матрица исходного (n, k) кода.

Расширение реализуется добавлением дополнительного проверочного символа (например, проверки на четность) к каждому кодовому слову. Систематический ( n, k) код может быть укорочен до (n - l, k - l) кода, если установить первые l информационных символов нулями (т.е. не передавать). Тогда можно удалить первые l строк матрицы и первые l столбцов матрицы и получить 2^{( k - l )} кодовых слов. При этом d_min не меньше, чем для исходного (n, k) кода.

Синдромное декодирование линейного кода осуществляется согласно (3.15) умножением последовательности символов   Z с выхода демодулятора приемника на проверочную матрицу:

                                                       (3.21)

Принятая последовательность Z для двоичного кода представляет сумму по модулю 2 переданного кодового слова и n -символьной последовательности ошибок, т.е.

.

Результат: (n - k) -мерный вектор

 ,                                         (3.22)

который называют синдромом образца ошибки.

Известно, что для линейного блокового кода может быть построена синдромная таблица декодирования, которая содержит 2^{( n - k )} синдромов и соответствующие им   2^{( n - k )} образца ошибок с минимальным весом.

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

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