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

3.1. Можно ли использовать для построения кодов, позволяющих обнаруживать ошибки, иной метод, нежели рассмотренный в разделе метод отбора разрешенных комбинаций по признаку четности числа единиц?

3.2. Каковы возможности кода с проверкой на четность единиц?

3.3. Каковы возможности кода с d_min = 5 при обнаружении ошибок?

3.4. Каковы возможности кода с d_min = 7 при исправлении ошибок?

3.5. Чем определяется корректирующая способность кода?

Задания

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

3.2. Предложите простой способ декодирования комбинаций кода с четным числом единиц.

4. Алгебраическое описание блоковых кодов

Для описания линейных блоковых кодов используют математический аппарат общей алгебры. При блоковом кодировании наборы кодовых символов образуют кодовые комбинации b = (b₁, b₂, ..., b_n).

Символы комбинаций b двоичных кодов выбирают из поля Галуа GF(2). Множество комбинаций длины n образует n-мерное векторное пространство над полем GF(2). Для элементов этого пространства (векторов) определены операции сложения и умножения, операция умножения вектора на элемент поля, а также скалярное произведение векторов. Совокупность линейно независимых векторов образует базис, который порождает n-мерное векторное пространство B_n, причем каждый из векторов этого пространства может быть получен, как линейная комбинация базисных векторов. Некоторое подмножество векторов пространства B_n, удовлетворяющее аксиомам векторного пространства, образует подпространство A_k.

Двоичный блоковый код значности n с 2^k разрешенными кодовыми комбинациями называется линейным (n, k) кодом, если его кодовые слова образуют k-мерное подпространство A_k векторного n-мерного пространства B_n.

Подпространство A_k порождается базисом из k линейно независимых векторов, которые образуют строки порождающей матрицы (n, k) кода:

. (4.1)

Кодовые комбинации можно представить в систематической форме, образуя отдельно информационную часть из k символов и проверочную часть из r = (n – k) дополнительных символов.

Порождающая матрица систематического кода имеет вид:

.(4.2)

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

Пример 4.1. преобразование матрицы несистематического кода.

Несистематический блоковый код (7, 4) задан порождающей матрицей:

.(4.3)

Используя метод линейной комбинации строк матрицы (4.3) преобразуем ее к систематической форме вида (4.2). Для формирования порождающей матрицы систематического кода строки исходной матрицы (4.3) удобно представить в виде табл. 4.1, в которой показаны строки g1_н, g2_н, g3_н и g4_н.

Таблица 4.1 – Строки порождающей матрицы несистематического кода

g1н	1	0	1	1	0	1	0
g2н	0	1	0	0	1	0	1
g3н	0	0	1	0	0	1	1
g4н	0	0	0	1	1	1	1

Используя правила сложения по модулю 2 элементов этих строк перебором строк в различных комбинациях, устанавливаем, что наиболее подходящими вариантами для формирования строк матрицы систематического кода g1_с, g2_с, g3_с и g4_с являются следующие:

g1_с = (g1_нg3_нg4_н), g2_с = g2_н, g3_с = g3_н, g4_с = g4_н.

Результат вычисления строк матрицы систематического кода приведен в табл. 4.2.

Таблица 4.2 – Строки порождающей матрицы систематического кода

g1с	1	0	0	0	1	1	0
g2с	0	1	0	0	1	0	1
g3с	0	0	1	0	0	1	1
g4с	0	0	0	1	1	1	1

Ниже дана матрица систематического кода в стандартной форме записи:

. (4.4)

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

Вес Хемминга w_H кодовой комбинации двоичного кода равен количеству единиц в кодовой комбинации.

Пример 4.2. вычисление весов Хемминга кодовых комбинаций.

Определим значения весов Хемминга для комбинаций, задаваемых табл. 4.3:

Таблица 4.3 – вычисление весов Хемминга кодовых комбинаций

кодовые комбинации двоичного кода							Вес wH(bi)
b1	1	0	1	1	0	1	4
b2	0	1	0	0	0	1	2

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

Упражнение 4.1. Определение кодового расстояния блокового кода по его порождающей матрице.

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

Указание. Для разработки метода определения кодового расстояния блокового кода по его порождающей матрице необходимо учесть, что полностью нулевая комбинация b₀ = (00…0) также является разрешенной.

Решение. Выше отмечено, что разрешенные комбинации блокового кода определяются как линейные комбинации строк порождающей матрицы. Поскольку полностью нулевая комбинация b₀ = (00…0) является разрешенной, а строки порождающей матрицы g1, g2, g3, g4 также являются разрешенными комбинациями, то расстояния Хемминга этих комбинаций до нулевой комбинации b₀ определяется их весами d_H (gi,b₀) = w_H(gi), i = (1,…,k). Остается выяснить минимальный вес, т.е. минимальное расстояние. Отсюда следует такое заключение:

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

Пример 4.3. Определение весов Хемминга строк порождающей матрицы систематического кода.

Для иллюстрации этого утверждения определим значения весов строк порождающей матрицы систематического кода из примера 4.1 (табл. 4.2). Результаты вычислений приведены в табл. 4.4.

Таблица 4.4 – Распределение весов Хемминга строк порождающей матрицы систематического кода

Строки порождающей матрицы								Вес wH(gi)
g1с	1	0	0	0	1	1	0	3
g2с	0	1	0	0	1	0	1	3
g3с	0	0	1	0	0	1	1	3
g4с	0	0	0	1	1	1	1	4

Анализ данных дает определение минимального расстояния систематического кода из табл. 4.4 d_{min(сист)} = min{w_H(gi)} = 3.

Упражнение 4.2. Определите таким же способом кодовое расстояние несистематического кода из примера 4.1 (табл. 4.1).

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

Решение. Применим методику из примера 4.3. Результаты вычислений весов строк приведены в табл. 4.5.

Таблица 4.5 – Распределение весов Хемминга строк порождающей матрицы несистематического кода

строки порождающей матрицы								Вес wH(gi)
g1н	1	0	1	1	0	1	0	4
g2н	0	1	0	0	1	0	1	4
g3н	0	0	1	0	0	1	1	3
g4н	0	0	0	1	1	1	1	4

Анализ этих данных дает определение минимального расстояния несистематического кода из табл. 4.5 d_{Hmin(несист)} = min{w_H(gi)} = 3. полученные результаты позволяют утверждать, что систематический и несистематический коды из примера 4.1 по величине кодового расстояния эквивалентны.

Таким образом:

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

Отмеченная выше связь между минимальным расстоянием блоковых кодов и весами строк порождающих матриц может быть использована для формирования порождающей матрицы блокового кода с заданным кодовым расстоянием. Это положение иллюстрируется результатами решения задач в примерах 4.4 и 4.5.

Пример 4.4. Порождающая матрица кода с четным числом единиц.

Сформируем порождающую матрицу систематического (n, k) кода, обнаруживающего однократные ошибки. Код, обнаруживающий ошибки кратностиq = 1,должен иметь кодовое расстояниеd_min= q + 1 = 2. Следовательно, ненулевые строки порождающей матрицы этого кода должны иметь минимальный весw_H = 2. Поскольку формированию подлежит матрица систематического (n, k) кода то, в соответствии со стандартной формой записи (4.4) каждая строка такой матрицы уже содержит символ 1 (определяемый видом единичной подматрицыI_k), вес каждой строки следует увеличить до 2, добавив в последних символах каждой строки (в составе подматрицыP) символ 1.Для примера, порождающая матрица такого (7, 4) кода с k = 4 будет иметь вид:

, (4.5)

причем, единица в подматрице P может располагаться в любом месте строки.

Упражнение 4.3. Порождающие матрицы кодов, обнаруживающих двухкратные ошибки.

Сформируйте порождающую матрицу систематического кода, обнаруживающего двухкратные ошибки.

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

Решение.Код, обнаруживающий ошибки кратностиq = 2, должен иметь кодовое расстояниеd_min=q + 1 = 3. Следовательно, строки порождающей матрицы такого кода должны иметь минимальный весw_H = 3. Из общего вида порождающей матрицы систематического кода (4.2) следует, что получить такой вес можно выбором строк подматрицы дополнительных символовP, причем одна из строк этой подматрицы должна иметь вес, равный 2. Возможны следующие варианты подматрицыP:

; , , (4.6)

которые отличаются перестановкой строк. Поскольку минимальный вес строк каждой из этих матриц равен 2, их можно использовать для формирования систематических кодов с кодовым расстоянием d_min = 3. В частности, порождающая матрица одного из таких кодов имеет вид:

. (4.7)