Теория групповых кодов

Задача построения группового кода формулируется так же, как и постановка общей задачи кодирования. Ее решение начинается с очевидного этапа: с определения числа избыточных элементов по нижней границе Хемминга (формула 10). Однако построить групповой код с избыточностью, определяемой подобным образом, удается не всегда. Обычно при d_min ≤ 4 можно воспользоваться нижней границей Хемминга. В ряде случаев для достижения d_min = 5 расчетную избыточность, увеличивают на один элемент, а для достижения d_min = 7 – на два элемента.

На втором этапе решается задача записи всех требуемых M = 2^m кодовых комбинаций. Можно сразу же записать нулевую кодовую комбинацию

(n = m + k), так как в группе должен быть нулевой элемент. Затем записывается некоторое число q ненулевых комбинаций. Далее, используя эти q комбинаций, построим дополнительные комбинации, применяя операцию G = mod2 к любой паре, тройке и т. д. из комбинаций a₁– a_q. Процедуру получения дополнительных кодовых комбинаций можно формально представить так:

C₁a₁ ⊕ C₂a₂ ⊕ C₃a₃ ⊕ …⊕ C_ia_i ⊕ … ⊕ C_qa_q, (1)

где C_i = 0 или C_i= 1.

В результате все дополнительные комбинации можно считать рабочими, так как они будут новыми равноправными элементами группы.

Количество дополнительных комбинаций M_ДОП может быть получено в результате выполнения процедуры (1):

Общее количество рабочих комбинаций равно

Так как по условию надо иметь в коде M_РАБ = 2^m рабочих комбинаций, то q = m.

Для построения группового кода с параметрами M_РАБ = 2^m и заданным минимальным кодовым расстоянием d_min достаточно, кроме нулевой комбинации, записать q = m ненулевых, которые будут являться базовыми. Эти ненулевые комбинации a₁ – a_q, однако, нельзя выбирать произвольно. Базовые комбинации должны удовлетворять следующим условиям.

1. Все базовые комбинации должны быть ненулевыми и различными.
2. При реализации процедуры (1) не должны получаться исходные комбинации из числа a₁– a_q, так как это приведет к получению a₀ еще раз. То есть

C₁a₁ ⊕ C₂a₂ ⊕ C₃a₃ ⊕ …⊕ C_ia_i ⊕ … ⊕ C_qa_q ≠ 0 (2)

при любых значениях коэффициентов, кроме C₁ = C₂ =C₃ =…= C_i =…= C_q = 0. Все базовые комбинации, удовлетворяющие условию (2), называются линейно независимыми.

3. Так как в число рабочих комбинаций входит нулевая a₀, то для получения кода с заданным значением d_min необходимо, чтобы любая базовая комбинация имела вес (вес комбинации – число единиц в ней).
4. Число отличающихся разрядов у любой пары базовых комбинаций не должно быть меньше d_min.

Базовые кодовые комбинации, удовлетворяющие условиям 1-4, принято называть базисом группового кода и записывать в виде матрицы, строки которой являются базовыми кодовыми комбинациями:

(1)

Матрицу V называют порождающей (генераторной).

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

В матрице (1) всегда можно переставить столбцы независимо друг от друга так, что на первых m позициях окажутся только информационные элементы. Расстояние d_min при этом не изменится. В итоге получим так называемую каноническую форму порождающей матрицы:

(2)

Пример

Построить групповой код с параметрами M = 8 и d_min = 3.

Определим сначала необходимое число избыточных элементов.

Код не имеет однозначной записи кодовых комбинаций.

Строки порождающей матрицы удовлетворяют условиям 1-4, и поэтому могут быть базисом кода. Дополнительные кодовые комбинации найдем суммированием по модулю два базисных:

a₄ = a₁ ⊕ a₂ = 010011,

a₅ = a₁ ⊕ a₃ = 011110,

a₆ = a₂ ⊕ a₃ = 001101,

a₇ = a₁ ⊕ a₂ ⊕ a₃ = 101011.

Построим порождающую матрицу в каноническом виде (ее можно получить из V перестановкой столбцов):

Основной задачей, которая решается при построении группового кода, является нахождение порождающей матрицы путем подбора. Однако существуют частные разновидности групповых кодов, в которых порождающие матрицы записываются по формализованным алгоритмам. К таким кодам относятся коды Рида-Мюллера, коды на базе матриц Адамара, коды Макдональда и другие. Некоторым недостатком этих кодов является возможность получения только четного минимального кодового расстояния d_min = 2^b, b = 1,2,3,….

---