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

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

Приклади

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

• $(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,\ldots ,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]/\langle X^{p}-1\rangle$згенерованої функцією $g(x)$ відповідає коду квадратичного лишку.

Вага

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

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

Додавання перевірочної цифри на загальну парність до коду квадратичного лишку дає розширений код квадратичного лишку. Коли $p\equiv 3$ (mod $4$), розширений код квадратичного лишку є самодвоїстим; інакше він еквівалентний, проте не дорівнює собі подвійному. За теоремою Глісона-Пранжа (названою на честь Ендрю Глісона та Євгена Пранжа), група автоморфізму коду розширеного квадратичного лишку має підгрупу, що ізоморфна до $PSL_{2}(p)$ або $SL_{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.
• Blahut, R. E. (September 2006), The Gleason-Prange theorem, IEEE Trans. Inf. Theory, Piscataway, NJ, USA: IEEE Press, 37 (5): 1269—1273, doi:10.1109/18.133245.