В статье рассматривается использование кодов БЧХ для генерации набора кодовых слов заданной длины N, отстоящих друг от друга на расстояние Хэмминга d.

Код БЧХ (n; k, t) задается набором параметров: n — длина кодового слова, k — число информационных бит, причем n=2^m– 1, где m– челое число, t — число исправляемых ошибок кода. Параметр t определяет значение и порядок порождающего полинома кода

g(x) = x^n-k-1 + c_n-k-2x^n-k-2 + … + c₁x +c₀,

с_{i —} коэффициенты, принимают значения 0 или 1.

Параметр t определяет также дистанционные свойства кода, минимальное расстояние Хемминга между кодовыми словами d= 2t+1.

Алгоритм расчета порождающего полинома кода по заданным n, m и t рассмотрен в [1].

Для практических расчетов порождающего полинома можно использовать средства пакета Matlab:

dim=4; % %размерность поля кода

t=1; % %число исправляемых ошибок

m = gfprimdf(dim); cs = gfcosets(dim); pl = gfminpol(cs(2: t+ 1, 1), m);

FACTORS = pl;

GENPOLY = gftrunc(pl(1,:)); % %генераторный (порождающий) полином,

fori = 2: t

GENPOLY = gfconv(GENPOLY, gftrunc(pl(i,:)));

end;

r=size(GENPOLY,2); % %число степеней полинома, включая нулевую.

В таблице 1 приведены генераторные полиномы для кодов БЧХ с длиной кодового слова 15 и 31. Для четных d надо полином с меньшим d умножить на (х+1). В таблице 1 для примера приведен один такой полином (n=15, d=4).

Таблица 1

Параметры кодов БЧХ

Используя свойство кода БЧХ — расстояние Хемминга между двумя кодовыми словами не менее d= 2t+1, можно генерировать слова кодовые слова длиной Nс расстоянием Хемминга d. Для кода (n, k) значение N будет лежать в диапазоне от (k+1) до n. При этом число кодовых слов с расстоянием Хэмминга d равно 2^N-k.

Для генерации кодовых слов необходимо построить порождающую матрицу, первая строка которой формируется по порождающему полиному. Например, для кода БЧХ(15, 10) порождающий полином равен g= х⁴ + х +1 (таблица 1), биты с 0 по 4 соответствуют коэффициентам полинома — 10011, а остальные биты (14–5) заполняются 0.

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

В таблице 2 приведена порождающая матрица кода БЧХ(15, 10), число строк матрицы — 11.

Каждая строка i матрицы соответствует слагаемому xⁱ (S0 — x⁰ (1), S1 — x¹ (x), …, S10 — x¹⁰) полинома данных порядка k. Кодовые слова получаются побитовым XOR строк порождающей матрицы, соответствующих полиному исходных данных.

Таблица 2

Порождающая матрица кода БЧХ(15, 10)

Например, длина кодового слова N=8, для расчета слов используем строки S0 — S7. Слову с номером 11010010 соответствует полином х⁷ +х⁶ + х⁴ +х, оно равно S7 XOR S6 XOR S4 XORS1: 000110001010110.

В таблице 3 приведены 16 кодовых слов для N=8. Для генерации слов с N=7 из таблицы 2 нужно взять только 8 первых строк (без 7 бита).

Число кодовых слов кода БЧХ зависит от параметров кода n, k и t, которые определяют степень порождающего полинома r для заданного расстояния Хемминга d, длины кодового слова L.

На рисунке 1 приведена зависимость числа кодовых слов от расстояния Хемминга для кодов с разной длиной, по оси ординат приведен lgN (для L=511 данные приведены только для d в диапазоне от 3 до 48).

Из графиков рисунка 1 видно, что максимальное расстояние Хемминга кодовых слов, которое может быть получено с использованием кодов БЧХ равно примерно ¼ длины кодового слова, при этом с увеличением d число кодовых слов сильно уменьшается.

Один и тот же код БЧХ можно использовать для генерации кодовых слов разной длины, в таблице 4 показано число кодовых слов для кода БЧХ (31, k).

Таблица 3

Кодовые слова длиной 8, расстояние Хемминга 3

Рис. 1. Зависимость числа кодовых слов от расстояния Хемминга

Выводы: алгоритм с использованием кодов БЧХ позволяет эффективно рассчитывать кодовые слова с заданными значениями длины кодового слова и расстояния Хэмминга, при этом удовлетворение требований по расстоянию Хэмминга обеспечивается свойствами кода и не требует дополнительной проверки, что значительно снижает временные затраты. Число возможных кодовых слов при использовании кода БЧХ заранее известно, это число зависит: от парамертов кода БЧХ и от длины кодового слова. Наибольшее количество слов будет для кодовых слов с длиной (2^m — 1), совпадающих с параметром n кода БЧХ, т. е. для 31, 63, 127, …, для других значений длин число слов с заданным растоянием Хемминга быстро убывает с уменьшением длины кодового слова.

Таблица 4

Число кодовых слов для кода БЧХ (31, k)

Литература:

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки/ Блейхут Р. — М.: Книга по требованию, 2013. — 566 с.