Квадратний код лишку

Квадратичний код лишку є видом циклічного коду.

Приклади

Приклади квадратичного коду лишків включають в себе:

• $(7,4)$ Код Гемінга над $GF(2)$;
• $(23,12)$ двійковий код Голея над $GF(2)$;
• $(11,6)$  трійковий код Голея над $GF(3)$.

Конструкції

Це код квадратичного лишку довжини $p$ над скінченим полем $GF(l)$, коли $p$ та $l$ є простими, $p$ непарне і $l$ є квадратичним лишком за модулем $p$. Його твірний поліном, як циклічний код задається формулою

$f(x)=\prod _{j\in Q}(x-{\zeta }^j),$

де $Q$ є набором квадратичних лишків $p$ у множині $\{1,2,\dots ,p-1\}$, і $\zeta$ — первісний корінь порядку $p$ із одиниці в деякому скінченному полі $GF(l)$. Умова, що $l$ є квадратичним лишком $p$ забезпечує те, що коефіцієнти $f$ належать полю $GF(l)$.

Розмірність коду — $(p+1)/2$.

Заміна $\zeta$ на інший первісний корінь порядку $p$ із одиниці ${\zeta }^r$ призводить до отримання або того ж самого коду, або еквівалентного, залежно від того чи є $r$ квадратичним лишком $p$.

Альтернативна конструкція дозволяє уникнути коренів із одиниці. Задається функція

$g(x)=c+\sum _{j\in Q}{x}^j$

для відповідного $c\in GF(l)$. Коли $l=2$ необхідно підібрати $c$, при якому $g(1)=1$. Якщо $l$ — непарне, то $c=(1+\sqrt{p^{*}})/2$, де $p^{*}=p$ або $-p$ відповідно до того, чи $p$ ≡ $1$ (mod $4$) або $p$ ≡ $3$ (mod $4$). Тоді $g(x)$ також генерує код квадратичного лишку; точніше ідеал множини $F_l[X]/⟨X^p-1⟩$згенерованої функцією $g(x)$ відповідає коду квадратичного лишку.

Вага

Мінімальна вага квадратичного коду лишку довжини $p$ більша, ніж $\sqrt{p}$; це границя квадратного кореня.

Розширений код

Додавання перевірочної цифри на загальну парність до коду квадратичного лишку дає розширений код квадратичного лишку. Коли $p\equiv 3$ (mod $4$), розширений код квадратичного лишку є самодвоїстим; інакше він еквівалентний, проте не дорівнює собі подвійному. За теоремою Глісона-Пранжа (названою на честь Ендрю Глісона та Шаблон:Нп), група автоморфізму коду розширеного квадратичного лишку має підгрупу, що ізоморфна до $PS{L}_2(p)$ або $S{L}_2(p)$.

Список літератури

• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
• Шаблон:Citation.