Код квадратичного остатка - 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)