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

Квадратичный вычетный код — это тип циклического кода .

Примерами квадратичных кодов вычетов являются код Хэмминга над , двоичный код Голея над и троичный код Голея над .${\displaystyle (7,4)}$ ${\displaystyle ГФ(2)}$${\displaystyle (23,12)}$ ${\displaystyle ГФ(2)}$${\displaystyle (11,6)}$ ${\displaystyle ГФ(3)}$

Существует квадратичный код вычета длины над конечным полем, когда и являются простыми числами, нечетны и являются квадратичным вычетом по модулю . Его порождающий полином как циклический код задается выражением${\displaystyle p}$${\displaystyle GF(l)}$${\displaystyle p}$${\displaystyle л}$${\displaystyle p}$${\displaystyle л}$${\displaystyle p}$

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

где — набор квадратичных вычетов в наборе и — примитивный корень -й степени из единицы в некотором конечном поле расширения . Условие, что является квадратичным вычетом, гарантирует, что коэффициенты лежат в . Размерность кода равна . Замена другим примитивным корнем -й степени из единицы приводит либо к тому же коду, либо к эквивалентному коду в зависимости от того, является ли квадратичным вычетом .${\displaystyle Q}$${\displaystyle p}$${\displaystyle \{1,2,\ldots ,p-1\}}$${\displaystyle \дзета}$${\displaystyle p}$${\displaystyle GF(l)}$${\displaystyle л}$${\displaystyle p}$${\displaystyle f}$${\displaystyle GF(l)}$${\displaystyle (p+1)/2}$${\displaystyle \дзета}$${\displaystyle p}$${\displaystyle \дзета^{r}}$${\displaystyle r}$${\displaystyle p}$

Альтернативная конструкция избегает корней из единицы. Определить

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

для подходящего . При выборе , чтобы убедиться, что . Если нечетно, выберите , где или в соответствии с тем, сравнимо ли с или по модулю . Тогда также генерирует квадратичный код вычета; точнее, идеал , сгенерированный с помощью , соответствует квадратичному коду вычета.${\displaystyle c\in GF(l)}$${\displaystyle l=2}$${\displaystyle с}$${\displaystyle г(1)=1}$${\displaystyle л}$${\displaystyle c=(1+{\sqrt {p^{*}}})/2}$${\displaystyle p^{*}=p}$${\displaystyle -p}$${\displaystyle p}$${\displaystyle 1}$${\displaystyle 3}$${\displaystyle 4}$${\displaystyle g(x)}$${\displaystyle F_{l}[X]/\langle X^{p}-1\rangle }$${\displaystyle g(x)}$

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

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

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

• FJ MacWilliams и NJA Sloane, Теория кодов, исправляющих ошибки , North-Holland Publishing Co., Амстердам-Нью-Йорк-Оксфорд, 1977.
• Blahut, RE (сентябрь 2006 г.), «Теорема Глисона-Пранжа», IEEE Trans. Inf. Theory , 37 (5), Piscataway, NJ, USA: IEEE Press: 1269–1273, doi :10.1109/18.133245.
• М. Элиа, Алгебраическое декодирование кода Голея (23,12,7), Труды IEEE по теории информации, том: 33, выпуск: 1, стр. 150-151, январь 1987 г.
• Рид, И.С., Инь, Х., Труонг, ТК, Алгебраическое декодирование квадратичного кода вычета (32, 16, 8). IEEE Trans. Inf. Theory 36(4), 876–880 (1990)
• Рид, И.С., Труонг, ТК, Чен, Х., Инь, Х., Алгебраическое декодирование квадратичного кода вычета (41, 21, 9). IEEE Trans. Inf. Theory 38(3), 974–986 (1992)
• Хамфрис, Дж. Ф. Алгебраическое декодирование троичного (13, 7, 5) квадратично-вычетного кода. IEEE Trans. Inf. Theory 38(3), 1122–1125 (май 1992 г.)
• Чен, X., Рид, И.С., Труонг, ТК, Декодирование кода квадратичного остатка (73, 37, 13). IEE Proc., Comput. Digit. Tech. 141(5), 253–258 (1994)
• Хиггс, Р. Дж., Хамфрис, Дж. Ф.: Декодирование троичного (23, 12, 8) квадратично-вычетного кода. IEE Proc., Comm. 142(3), 129–134 (июнь 1995 г.)
• He, R., Reed, IS, Truong, TK, Chen, X., Декодирование квадратичного кода вычета (47, 24, 11). IEEE Trans. Inf. Theory 47(3), 1181–1186 (2001)
• ….
• Y. Li, Y. Duan, HC Chang, H. Liu, TK Truong, Использование разности синдромов для декодирования квадратичных вычетных кодов, IEEE Trans. Inf. Theory 64(7), 5179-5190 (2018)