Код квадратичного остатка

Не путать с QR-кодом .

Код квадратичного остатка — это разновидность циклического кода .

Примеры

Примеры квадратичныхКоды остатков включают $(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$ или $3$модуль $4$. Затем $g(x)$ также генерируеткод квадратичного остатка; точнее идеал $F_{l}[X]/\langle X^{p}-1\rangle$ созданный $g(x)$соответствует коду квадратичного остатка.

Вес

Минимальный вес квадратичного кода-вычета длины $p$больше, чем ${\sqrt {p}}$; это граница квадратного корня .

Расширенный код

Добавление общей цифры проверки четности к коду квадратичного остаткадает расширенный квадратичный код остатка . Когда $p\equiv 3$ (против $4$) расширенное квадратичное уравнениекод остатка самодвойственный; в противном случае это эквивалентно, но неравен своему двойнику. По теореме Глисона-Пранжа (названной в честь Эндрю Глисона и Юджина Прейнджа ) группа автоморфизмов расширенного квадратичного вычетакод имеет подгруппу, изоморфнуюили $PSL_{2}(p)$ или $SL_{2}(p)$.

Метод декодирования

С конца 1980 года было разработано множество алгоритмов алгебраического декодирования для исправления ошибок в кодах с квадратичным вычетом. Эти алгоритмы могут достичь (истинной) способности исправления ошибок. $\lfloor (d-1)/2\rfloor$ кодов с квадратичным вычетом с длиной кода до 113. Однако декодирование длинных двоичных кодов с квадратичным вычетом и недвоичных кодов с квадратичным вычетом продолжает оставаться сложной задачей. В настоящее время декодирование кодов с квадратичным вычетом по-прежнему остается активной областью исследований в теории кодов, исправляющих ошибки.

Ссылки

• Ф. Дж. МакВильямс и Н. Дж. А. Слоан, Теория кодов, исправляющих ошибки , издательство North-Holland Publishing Co., Амстердам-Нью-Йорк-Оксфорд, 1977.
• Блахут, Р.Э. (сентябрь 2006 г.), «Теорема Глисона-Пранджа», IEEE Trans. Инф. Theory , 37 (5), Пискатауэй, Нью-Джерси, США: IEEE Press: 1269–1273, doi : 10.1109/18.133245 .
• М. Элиа, Алгебраическое декодирование (23,12,7) кода Голея, Транзакции IEEE по теории информации, Том: 33, Выпуск: 1, стр. 150-151, январь 1987 г.
• Рид И.С., Инь Х., Труонг Т.К. Алгебраическое декодирование кода квадратичного вычета (32, 16, 8). IEEE Транс. Инф. Теория 36 (4), 876–880 (1990).
• Рид И.С., Труонг Т.К., Чен X., Инь X. Алгебраическое декодирование кода квадратичных вычетов (41, 21, 9). IEEE Транс. Инф. Теория 38 (3), 974–986 (1992).
• Хамфрис, Дж. Ф. Алгебраическое декодирование троичного (13, 7, 5) кода с квадратичным вычетом. IEEE Транс. Инф. Теория 38 (3), 1122–1125 (май 1992 г.)
• Чен X., Рид И.С., Труонг Т.К. Декодирование кода с квадратичным вычетом (73, 37, 13). IEE Proc., Comput. Цифра. Тех. 141(5), 253–258 (1994)
• Хиггс, Р.Дж., Хамфрис, Дж.Ф.: Декодирование троичного (23, 12, 8) кода с квадратичным вычетом. IEE Proc., Comm. 142 (3), 129–134 (июнь 1995 г.)
• Хе, Р., Рид, И.С., Труонг, Т.К., Чен, X., Декодирование кода квадратичного остатка (47, 24, 11). IEEE Транс. Инф. Теория 47 (3), 1181–1186 (2001).
• ….
• Ю. Ли, Ю. Дуань, Х. К. Чанг, Х. Лю, Т. К. Труонг, Использование разницы синдромов для декодирования кодов квадратичных остатков, IEEE Trans. Инф. Теория 64(7), 5179-5190 (2018)