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

Quadratic residue code

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

Примеры

Примеры кодов квадратичного остатка включают ${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 f (x) = prod _ {jin Q} (x-zeta ^ {j})}

куда ${displaystyle Q}$ - множество квадратичных вычетов ${displaystyle p}$ в наборе ${displaystyle {1,2, ldots, p-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 _ {jin Q} x ^ {j}}

для подходящего ${displaystyle cin 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} -1angle}$ создано ${displaystyle g (x)}$ соответствует квадратичному коду остатка.

Масса

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

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

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

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

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

Navigation