Задачи и дополнения

1. Весом вектора u (обозначается ω(u)) называют число его ненулевых координат. Понятно, что расстояние Хемминга между двумя векторами u₁ и u₂ равно весу их разности ω(u₁ - u₂). Это позволяет упростить отыскание кодового расстояния линейного кода. Именно, справедливо следующее утверждение:

Кодовое расстояние линейного кода равно минимальному весу его ненулевых кодовых слов:

d(V) = min ω(υ). 
 υ∈V
 υ≠0

Предоставляем читателю доказать это утверждение.

2. Пусть двоичный линейный код V содержит хотя бы одно слово нечетного веса. Доказать, что число всех таких слов составляет тогда ровно половину от общего числа кодовых слов.

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

3. Рассмотрим матрицу порядка q^k × n, в качестве строк которой взяты все кодовые векторы личного линейного (n, k)-кода. Будем предполагать, что ни один столбец этой матрицы не является нулевым (иначе, вычеркнув нулевой столбец, мы получили бы код с тем же кодовым расстоянием, но меньшей длины). Показать, что в каждом столбце этой матрицы каждый из элементов поля встречается ровно q^k-1 раз. Пользуясь этим, убедиться, что суммарный вес всех кодовых слов равен n(q-1)q^k-1.

Указание. Проверить, что множество всех кодовых слов, содержащих 0 в некоторой фиксированной позиции, есть подпространство, и найти разложение кода в смежные классы по этому подпространству.

4. Предположим, что кодовый вектор υ = (x₁, х₂, ..., х_n) имеет вес, равный ω, x_k1, х_k2, ..., х_kω - его ненулевые координаты. Из проверочных соотношений (1) получаем тогда:

Это означает, что столбцы проверочной матрицы с номерами k₁, k₂, ..., k_ω линейно зависимы. Следовательно, каждому кодовому вектору веса до соответствует до линейно зависимых столбцов проверочной матрицы. Верно и обратное утверждение.

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

5. Доказать, что двоичный линейный код исправляет любые одиночные ошибки тогда и только тогда, когда все столбцы его проверочной матрицы ненулевые и различные. Верно ли это для любого линейного кода?

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

7. Двоичный (8,4)-код задан порождающей матрицей

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

То же задание для троичного (6,3)-кода с порождающей матрицей

8. Два кода V₁ и V₂ называются эквивалентными, если кодовые слова одного кода получаются из кодовых слов другого некоторой перестановкой символов (одной и той же для всех кодовых слов). Поскольку при этом веса кодовых слов остаются без изменений, то кодовые расстояния двух эквивалентных кодов совпадают, поэтому одинаковы также их возможности исправлять или обнаруживать ошибки. Ясно, что если порождающие матрицы кодов получаются одна из другой путем перестановки столбцов, то коды эквивалентны.

Эквивалентными являются, например, коды V₁ и V₂ со следующими порождающими матрицами:

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

9. В предыдущем примере код V₁ эквивалентен систематическому коду V₂. Это не исключение, а правило, поскольку справедливо следующее утверждение:

Всякий линейный код эквивалентен систематическому коду.

Доказательство, которое рекомендуется продумать читателю, основывается, в сущности, на известном современному школьнику методе Гаусса исключения неизвестных.

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

Вычитая из четвертой строки матрицы (11) первую, получим:

далее, вычитая из первой строки вторую, приходим к матрице

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

10. Показать, используя соотношения (7), что для систематического кода с порождающей матрицей (9) в качестве проверочной можно взять следующую матрицу:

11. Пусть V - произвольный линейный (n, k)-код. Рассмотрим множество V' всех векторов пространства L_n, ортогональных каждому из кодовых векторов υ ∈ V. Нетрудно проверить, что V' является под пространством в L_n и, следовательно, может рассматриваться как линейный код. Код V называется дуальным к исходному коду V.

Убедиться, что если G и Н - порождающая и проверочная матрицы кода V, то они служат соответственно проверочной и порождающей матрицей дуального кода V'.

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

12. Одним из способов получения кодов, обладающих большим кодовым расстоянием, а значит, и высокой корректирующей способностью, является комбинирование двух или нескольких кодов. Примером такого комбинирования является рассматриваемая здесь конструкция. Она дает код, который является обобщением матричного кода из § 8 с проверками на четность по строкам и столбцам.

Пусть дано слово, содержащее k = k₁k₂ информационных символов. Разобьем множество этих символов на k₂ блоков по k₁ символов в каждом и запишем результат в виде квадратной матрицы порядка k₂ × k₁:

В первой строке этой матрицы выписаны по порядку символы первого блока, во второй - символы второго и т. д.

Рассмотрим теперь произвольный систематический линейный код V₁ длины n₁ с k₁ информационными символами и с тем же самым кодовым алфавитом. Строки матрицы (12) закодируем указанным кодом. Для этого к каждой строке припишем n₁-k₁ проверочных символов таким образом, чтобы выполнялись проверочные соотношения кода V₁.

Далее каждый столбец получившейся матрицы порядка k₂ × n₁,

закодируем точно таким же способом с помощью линейного (n₂, k₂) кода V₂.

В результате получим матрицу порядка n₂ × n₁:

Выписывая элементы этой матрицы "по строкам", мы и составим кодовое слово, отвечающее исходному слову. Оно, очевидно, однозначно определяется матрицей (12).

Построенный код называется произведением кодов V₁ и V₂ и обозначается V₁ ⊗ V₂.

Пусть теперь k, k₁, k₂ - числа информационных символов кодов V₁ ⊗ V₂, V₁ ⊗ V₂, а n, n₁, n₂ - длины этих кодов. Из построения кода V₁ ⊗ V₂ сразу же вытекает, что

Менее очевидно аналогичное соотношение между кодовыми расстояниями d, d₁, d₂ тех же кодов: d = d₁ · d₂. Доказательство этого факта предоставляем читателю.

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

Проиллюстрируем сказанное примером. Пусть k = 8, k₁ = 4, k₂ = 2. В качестве кода V₁ возьмем (7,4)-код Хемминга, записав предварительно его порождающую матрицу в систематической форме:

в качестве V₂ - (3,2)-код с общей проверкой на четность. Составим кодовое слово кода V₁ ⊗ V₂, соответствующее исходному слову 00101110 с восемью информационными символами. Запишем его в виде матрицы порядка 2 × 4:

В результате кодирования строк (7,4)-кодом Хемминга (см. правило (6)) получим матрицу порядка 2 × 7:

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

соответствует следующее кодовое слово кода V₁ ⊗ V₂: