Код квадратичного остатка - Quadratic residue code

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

Примеры

Примеры кодов квадратичного остатка включают Код Хэмминга над , то двоичный код Голея над и троичный код Голея над .

Конструкции

Имеется код квадратичного остатка длины над конечным полем в любое время и простые числа, странно, и это квадратичный вычет по модулю Его порождающий полином в виде циклического кода имеет вид

куда - множество квадратичных вычетов в наборе и примитивный корень из единства в некотором конечном поле расширения . Условие, что является квадратичным вычетом гарантирует, что коэффициенты при роды . Размер кода.Замена другим примитивом -корень единства либо приводит к тому же коду, либо к эквивалентному коду, в зависимости от того, является квадратичным вычетом .

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

для подходящего . Когда выберите чтобы гарантировать, что .Если странно, выберите ,куда или же согласно ли конгруэнтно или же по модулю . потом также генерирует код квадратичного остатка; точнее идеал создано соответствует квадратичному коду остатка.

Масса

В минимальный вес квадратичного вычетного кода длины больше, чем ; это квадратный корень.

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

Добавление общей контрольной цифры к квадратичному остаточному коду дает расширенный квадратичный код остатка. Когда (мод ) расширенный код квадратичного вычета самодвойственен; в противном случае он эквивалентен, но не равен своему двойственному. Посредством Теорема Глисона – Прейнджа (назван в честь Эндрю Глисон и Юджин Прейндж ) группа автоморфизмов расширенного квадратичного кода вычетов имеет подгруппу, изоморфную либо или же .

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

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

Рекомендации

  • Ф. Дж. Мак-Вильямс и Н. Дж. А. Слоан, Теория кодов, исправляющих ошибки, North-Holland Publishing Co., Амстердам-Нью-Йорк-Оксфорд, 1977.
  • Blahut, R.E. (сентябрь 2006 г.), "Теорема Глисона-Прейнджа", IEEE Trans. Инф. Теория, Пискатауэй, Нью-Джерси, США: IEEE Press, 37 (5): 1269–1273, Дои: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)