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

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

Приклади

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

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

Конструкції

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

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

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

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

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

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

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

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

Вага

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

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

Додавання перевірочної цифри на загальну парність до коду квадратичного лишку дає розширений код квадратичного лишку. Коли ${\displaystyle p\equiv 3}$ (mod ${\displaystyle 4}$), розширений код квадратичного лишку є самодвоїстим; інакше він еквівалентний, проте не дорівнює собі подвійному. За теоремою Глісона-Пранжа (названою на честь Ендрю Глісона та ^[en]), група автоморфізму коду розширеного квадратичного лишку має підгрупу, що ізоморфна до ${\displaystyle PSL_{2}(p)}$ або ${\displaystyle 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.