Контрольные вопросы

4.1. Коды с порождающими матрицами (4.3) и (4.4) имеют одинаковое минимальное расстояние. Чем это объясняется?

4.2. Изменяются ли корректирующие свойства блокового кода при перестановке столбцов порождающей матрицы?

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

4.4. Какой вид имеет порождающая матрица систематического блокового кода?

Задания

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

4.2. Следуя методу, изложенному в упражнении 4.3, сформируйте порождающую матрицу систематического кода, обнаруживающего трехкратные ошибки. Является ли найденный Вами код единственным?

5. Кодирование и декодирование блоковых кодов

5.1. Кодирование и декодирование блоковых кодов [2, разд. 3.3].

5.2. синдромное декодирование блоковых кодов [2, разд. 3.3].

5.3. Мажоритарное декодирование блоковых кодов [2, разд. 3.3].

5.1. Кодирование и декодирование блоковых кодов

В основе теории кодирования блоковых кодов лежит понятие порождающей матрицы кода вида (4.1) и (4.2).

Если a = |a₀, a₁,..., a_k| – матрица-строка первичного кода, то правило кодирования блокового кода определяется произведением:

b = a·G, (5.1)

где: a =|a₀, a₁,..., a_k|– матрица-строка первичного кода на входе кодера;

b =|b₀, b₁,..., b_n|– матрица-строка кодового слова на выходе кодера;

G – порождающая матрица линейного (n, k) кода.

Пример 5.1. Кодер кода (7, 4). Структура кодера систематического кода (7, 4) определяется порождающей матрицей (4.4) и правилом кодирования (5.1). Если на входе кодера действует строка символов первичного кода a = (a₁, a₂, a₃, a₄), то символы разрешенной кодовой комбинации на его выходе b = (b₁, b₂, b₃, b₄, b₅, b₆, b₇) определяются следующими равенствами:

b₁ = a₁, b₂ = a₂, b₃ = a₃, b₄ = a₄,

b₅ = a₁a₂a₄, b₆ = a₁a₂a₄, b₇ = a₁a₃a₄. (5.2)

На рис. 5.1 показана структура кодера систематического кода (7, 4), в которой реализованы равенства (5.2).

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

G·H^T = 0. (5.3)

Здесь индекс ^T – символ транспонирования.

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

G·H^T = 0.

Если порождающая матрица задана в форме (4.2), то для выполнения условия ортогональности проверочная матрица должна иметь вид:

H = |P^TI_n–k|, (5.4)

где P^T – транспонированная подматрица P порождающей матрицы G;

I_n–k – единичная матрица размером [(n – k)(n – k)].

Упражнение 5.1. Проверочная матрица систематического кода (7, 4).

Задана порождающая матрица систематического кода вида (4.6):

.

В соответствии с правилами формирования проверочной матрицы (5.4) сформируйте проверочную матрицу этого кода.

Решение. Последовательно находим подматрицы, входящие в формулу (5.4):

– транспонированная подматрица размером [(n – k)  k]:

;

– единичная подматрица размером [(n – k)  (n – k)]:

.

Объединяем подматрицы в единую проверочную матрицу кода:

(5.5)

Из условия ортогональности порождающей и проверочной матриц линейного кода (5.3) следует, что каждая разрешенная комбинация линейного кода, сформированная по правилу b = a·G, также удовлетворяет условию ортогональности:

b·H^T = a·G·H^T = 0.(5.6)

При передаче по каналу кодовые символы искажаются. Комбинации на входе декодера имеют вид = b e, где b = (b₀, b₁,..., b_n), а вектор ошибки е = (е₀, е₁, ..., е_n).

При декодировании вычисляют вектор синдрома

S = ·H^T=(s₀, s₁,..., s_n–k–1). (5.7)

Синдром зависит только от вектора ошибок:

S = ·H^T = (b  e) H^T = ·H^T e·H^T.

Поскольку выполняется условие ортогональности ·H^T = 0, синдром равен:

S = e·H^T. (5.8)

Отсюда вытекает простое правило обнаружения ошибок:

Если синдром S = 0 (вектор ошибки е = 0), то комбинация на входе декодера принадлежит к множеству разрешенных кодовых комбинаций. Это может быть, если в канале не было ошибок либо ошибки перевели переданную разрешенную комбинацию в другую разрешенную комбинацию.

При S  0 комбинация содержит ошибки. По значениям символов синдрома судят о конфигурации вектора ошибок.

Этот принцип лежит в основе синдромного декодирования.