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

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

Примеры [ править ]

Примеры квадратичных вычетов кодов включают в себя код Хэмминга над , в двоичный код Голея над и трехкомпонентную Голея код над .${\ 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 е (х) = \ prod _ {j \ in Q} (x- \ zeta ^ {j})}$

где - множество квадратичных вычетов в наборе и - примитивный корень -й степени из единицы в некотором конечном поле расширения . Условие квадратичного вычета гарантирует, что коэффициенты при лежат в . Размер кода . Замена другим примитивным корнем -й степени из единицы приводит либо к тому же коду, либо к эквивалентному коду, в зависимости от того, является ли квадратичным остатком .${\ displaystyle Q}$${\ displaystyle p}$${\ Displaystyle \ {1,2, \ ldots, п-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}$${\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}(p)}$

Метод декодирования [ править ]

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

Ссылки [ править ]

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