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

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

Приклади

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

$(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$ ), розширений код квадратичного лишку є самодвоїстим; інакше він еквівалентний, проте не дорівнює собі подвійному. За теоремою Глісона-Пранжа (названою на честь Ендрю Глісона та Євгена Пранжа^[en]), група автоморфізму коду розширеного квадратичного лишку має підгрупу, що ізоморфна до $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.