Глава 7. МЕТОДЫ ПОСТРОЕНИЯ И ТЕХНИЧЕСКОЙ РЕАЛИЗАЦИИ КОРРЕКТИРУЮЩИХ КОДОВ

7.1. ЛИНЕЙНЫЕ КОДЫ

Построение линейных кодов. В гл 2 простой трехэлементный код был задан перечислением всех кодовых комбинаций (см. табл. 2 1) Данное множество можно рассматривать как некоторую алгебраическую систему, которая называется группой с заданной на ней операцией сложения по модулю два [7 1]. Рассмотрим в общем виде основные свойства такого множества Обычно группа обозначается буквой G, а элементы множества g, На этом множестве задана некоторая групповая операция, которую обозначим символом «0» Эта операция однозначно сопоставляет двум элементам и g, множества G, третий элемент того же множества где . Обычно говорят, что группа является замкнутой относительно операции

Множество G с определенной на нем групповой операцией называется группой, если выполняются следующие условия,

1. Ассоциативность (сочетательность) - для любых трех элементов группы, например .

2. Существование нейтрального элемента: среди элементов множества имеется некоторый элемент , называемый нейтральным, такой, что

для всех i.

3. Существование обратного элемента для каждого данного элемента; к каждому элементу можно подобрать такой элемент , что

Группа, в которой выполняется также условие для всех I, j, называется коммутативной, или абелевой, группой. Группа называется конечной, если она состоит из конечного числа элементов. В противном случае она называется бесконечной.

Пример 7.1. Задав в качестве групповой операции операцию сложения по модулю 2, убедимся, что множество 000, 001, 010, 100, 110, 011, 101, 111 является группоп Складывая элементы множества в различном сочетании, видим, что каждый раз получаем элемент, входящий в множество Так, 001 и т. п. Нетрудно заметить, что условие ассоциативности также выполняется Нейтральным является элемент 000 Для каждого элемента, заданного в примере множества, существует обратный Так, для элемента 100 обратным является он сам, т. е.

Таким образом, рассматриваемое множество является группой, порядок которой (число элементов) равен восьми Очевидно также, что данная группа является коммутат ивной

Пример 7.2. Задавшись в качестве групповой операции операцией умножения, рассмотрим множество рациональных чисел

Перемножая элементы множества в различном сочетании, получаем рациональное число Легко убедиться в том, что выполняется условие ассоциативности Нейтральным элементом, очевидно, является единица Для каждого элемента заданного рациональным числом, имеется ему обратный Так, для числа 2 это 1/2, числа 1/4 — это 4 и т. д.

Множество элементов примера не обязательно задавать перечислением всех элементов, входящих в группу

Пользуясь свойством замкнутости относительно операции сложения по модулю 2, такое множество можно задать матрицей

Все остальные элементы группы (кроме 000) могут быть получены путем сложения по модулю 2 различных сочетаний строк матрицы (7.1). Матрица (7.1) называется производящей матрицей рассмотренного в примере 7.1 трехэлементного кода. Кодовые комбинации, составляющие матрицу (7.1), являются линейно-независимыми.

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

Код, заданный матрицей (7.1), является линейным, т. е. имеет структуру, обладающую свойством линейности. Двоичный блочный код является линейным тогда и только тогда, когда сумма по модулю 2 двух кодовых слов является также кодовым словом [7.1]. Двоичные линейные коды называют также групповыми.

Так как в системе ПДС используются, как правило, корректирующие коды, перейдем далее к рассмотрению линейных (групповых) корректирующих кодов и поиску кодов с заданным алфавитом передаваемых сообщений и кодовым расстоянием которые позволят обеспечить требуемую верность.

Пример 7.3. Пусть требуется построить линейный код с для передачи восьми сообщений

Тогда необходимое число информационных элементов Запишем исходный код в виде единичной матрицы (7 1) и дополним информационные элементы элементами, которые в дальнейшем будем называть проверочными, так, чтобы обеспечить Дополним каждую строку матрицы (7.1) двумя элементами

Складывая по модулю 2 строки матрицы (7 2), видим, что хэммиигово расстояние для 1,2, 1,3; 2,3 строк равно 3 Однако при этом кодовое расстояние, равное 3, не обеспечивается, так как в числе разрешенных кодовых комбинации (множества, являющегося группой) имеется нейтральный элемент 00000, относительно которого комбинации 10010 и 01001 имеют хэммингово расстояние, равное только двум.

Таким образом, производящая матрица матрица кода (5 3) с кодовым расстоянием, равным только двум. Для получения необходимо к исходным информационным элементам добавить проверочные элементы, в числе которых было бы не мепее двух единиц, а добавляемые проверочные элементы разных строк отличались бы, по крайней мере, в одном элементе Этому требованию удовлетворяет производящая матрица

Добавляемые проверочные элементы могут быть записаны и в другом порядке. Необходимо лишь обеспечить Матрица (7 3) является производящей, или порождающей, матрицей кода (6 3), содержащею элементов, из которых три информационных. Обычно матрицу обозначают буквой G с индексом, указывающим, к какому коду она относится (в нашем случае ).

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

Обозначим элементы комбинаций кода, задаваемого матрицей (7.3), , где — информационные, а — проверочные элементы. Полученный линейный код является систематическим Проверочные элементы могут быть получены путем суммирования по модулю 2 определенных информационных элементов. Найдем это правило для пользуясь матрицей (7.3). Из первой строки следует, что в суммировании обязательно должен участвовать элемент (только в этом случае ). Из второй строки следует, что элемент в суммировании не должен участвовать. Из третьей строки следует, что элемент должен участвовать в суммировании. Итак,

Уравнения для записываются в виде

Представим правила (7.4) -(7.6) в виде матрицы называемой проверочной. Эта матрица содержит строк и k столбцов:

Каждая из строк матрицы (7.7) определяет правило формирования соответствующего проверочного элемента. Так, единицы, расположенные на местах, соответствующих информационным элементам в первой строке, указывают на то, какие информационные элементы должны участвовать в получении первого проверочного элемента (элемента 04). Единица на месте, соответствующем проверочному элементу (четвертом месте), указывает, какой проверочный элемент получается в результате суммирования информационных элементов. Так, из первой строки следует Матрица состоит из двух матриц: прямоугольной и единичной b, содержащей строк и столбцов:

Легко заметить, что означает транспонирование)

Проверочная матрица задает правила кодирования линейного кода и определяет схему кодирующего устройства. Структурная схема кодирующего устройства, задаваемого проверочной матрицей приведена на рис. 7.1. Запишите