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

Завдання побудови групового коду формулюється так само, як і постановка загальної задачі кодування. Її рішення починається з очевидного етапу: з визначення числа надлишкових елементів по нижній межі Хеммінга (формула 10). Однак побудувати груповий код з надмірністю, яка визначається подібним чином, вдається не завжди. Зазвичай при dmin ≤ 4 можна скористатися нижньою межею Хеммінга. У ряді випадків для досягнення dmin = 5 розрахункову надмірність, збільшують на один елемент, а для досягнення dmin = 7 - на два елементи.

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

(N = m + k), так як в групі повинен бути нульовий елемент. Потім записується певна кількість q ненульових комбінацій. Далі, використовуючи ці q комбінацій, побудуємо додаткові комбінації, застосовуючи операцію G = mod2 до будь-якої парі, трійці і т. Д. З комбінацій a1 - aq. Процедуру отримання додаткових кодових комбінацій можна формально представити так:

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

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

Загальна кількість робочих комбінацій одно

Для побудови групового коду з параметрами MРАБ = 2 m і заданим мінімальним кодовою відстанню dmin досить, крім нульової комбінації, записати q = m ненульових, які будуть базовими. Ці ненульові комбінації a1 - aq. однак, не можна вибирати довільно. Базові комбінації повинні відповідати таким вимогам.

1. Всі базові комбінації повинні бути ненульовими і різними.
2. При реалізації процедури (1) не повинні виходити вихідні комбінації з числа a1 - aq. так як це призведе до отримання a0 ще раз. Тобто

Так як в число робочих комбінацій входить нульова a0. то для отримання коду з заданим значенням dmin необхідно, щоб будь-яка базова комбінація мала вага (вага комбінації - число одиниць в ній).

Число відрізняються розрядів у будь-якої пари базових комбінацій не повинно бути менше dmin.

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

Матрицю V називають породжує (генераторної).

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

У матриці (1) завжди можна переставити стовпчики незалежно один від одного так, що на перших m позиціях виявляться тільки інформаційні елементи. Відстань dmin при цьому не зміниться. В результаті отримаємо так звану канонічну форму породжує матриці:

Визначимо спочатку необхідне число надлишкових елементів.

Код не має однозначної записи кодових комбінацій.

Рядки породжує матриці задовольняють умовам 1-4, і тому можуть бути базисом коду. Додаткові кодові комбінації знайдемо підсумовуванням за модулем два базисних:

Побудуємо породжує матрицю в канонічному вигляді (її можна отримати з V перестановкою стовпців):

Основним завданням, яке вирішується при побудові групового коду, є знаходження породжує матриці шляхом підбору. Однак існують приватні різновиди групових кодів, в яких породжують матриці записуються по формалізованим алгоритмам. До таких кодами відносяться коди Ріда-Мюллера, коди на базі матриць Адамара, коди Макдональда і інші. Деяким недоліком цих кодів є можливість отримання тільки парного мінімального кодового відстані dmin = 2 b. b = 1,2,3, ....