Построение кодов квадратичных вычетов: алгоритм и пример

Квадратично-вычетные коды существуют для длин п = 4k ± 1, где k - любое число, а n - простое число. Например, если k= 3, то квадратично- вычетный код существует для длины 11 (n =4*3-1) и для длины 13 (n =4*3+1). Если k= 4, то квадратично-вычетный код существует только для длины 17 (n =4*4+1).

Периодическая автокорреляционная функция последовательностей квадратичных вычетов обладает рядом свойств, позволяющих их использо­вать в широкополосных системах связи, и принимает значения:

Пронумеруем в порядке возрастания элементы поля Правило кодирования сформулируем в терминах квадратичных вычетов:

Если сравнение

имеет решение, то а называется квадратичным вычетом поля GF(p), в про­тивном случае - квадратичным невычетом.

Пример. Построить код U для длины 7. Согласно правилу кодирования, не­обходимо определить является или нет индекс i квадратичным вычетом поля

GF{ 7).

1²=1 mod(7) 3²=2 mod(7) 5²=4 mod(7)

2²=4 mod(7) 4²=2 mod(7) 6²=5 mod(7)

Таким образом, квадратичными вычетами являются числа 1, 2,4, т.к.:

1 = 1² mod(7) 2=3² mod(7) 4=2² mod(7)

Кодовое слово имеет вид:

Для перехода в алфавит представления (1,0) необходимо заменить (-1) на (1), а (1) на (0). Для рассмотренного примера получим и = {1001011}.

Квадратичные вычеты являются циклическими кодами, поэтому ос­тальные слова кода формируются путем сдвига опорного кодового слова. Для квадратичных вычетов длиной п=7, ансамбль кодовых слов имеет вид: