Полная версия

Главная arrow Математика, химия, физика arrow ДИСКРЕТНЫЙ АНАЛИЗ. ОСНОВЫ ВЫСШЕЙ АЛГЕБРЫ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Квадратично-вычетные коды

Квадратично-вычетные коды дают еще один пример хороших циклических кодов.

В этом разделе предполагаем, что длина кода простое число, которое дает остаток ±1 от деления на 8. Длину кода в этом разделе будем обозначать через р = 8т ± 1. Напомним (см. с. 164), что ненулевой вычет а называется квадратичным вычетом по модулю р, если уравнение х2 = а имеет решение в поле Ъ/(р). Множество квадратичных вычетов по модулю п обозначим через Qp, а множество квадратичных невычетов через Np.

Если х2 = а, у2 = b в поле Z/(p), то (ху~1)2 = аЪ~1. Поэтому квадратичные вычеты по модулю р образуют подгруппу мультипликативной группы ноля Z/(p).

Утверждение 4.12. Пусть q — нечетное простое число. Тогда 2 € Qq тогда и только тогда, когда q = ±1 (mod 8).

Доказательство (по [21]). Используем результат задачи 3.8: 2 является квадратичным вычетом но нечетному простому модулю q тогда и только тогда, когда 2^-1^2 = 1 (mod q). Любое поле характеристики q содержит подполе GF(q), поэтому условие можно проверять в любом таком поле.

Рассмотрим расширение F поля GF(q), которое содержит группу корней 8-й степени из единицы (см. раздел 3.9). Обозначим через а примитивный корень 8-й степени из единицы. В поле F у 2 есть квадратный корень. А именно, 2 = 2, где Р = а + а-1. В самом деле,

4 = — 1 так как а — примитивный корень восьмой степени).

Теперь нам нужно вычислить Pq~l = 2^-1^2. Пусть q = = 8m ± 1. Тогда

поэтому f3q~l = 1.

Пусть q = 8m ± 5. Тогда

поэтому fiq~l = — 1. ?

Возьмем поле F характеристики 2, которое содержит группу корней из 1 степени р. Примитивный корень степени р обозначим через и. Рассмотрим многочлены

В силу утверждения 4.12 если р = 8т ±1, то 2 является квадратичным вычетом по модулю р. Умножение на квадратичный вычет переводит множество квадратичных вычетов в себя и множество квадратичных невычетов в себя. Вспоминая структуру разложения хп 1 на неприводимые множители, описанную в разделе 3.9, получаем, что f(x) и q(x) являются многочленами над полем GF(2). Таким образом, над GF(2) имеем разложение

Определение 4.13. Квадратично-вычетными кодами называются идеалы кольца GF(2)/(xn 1), порожденные /(х), д(х), (х - l)f(x), (х - l)ff(x).

Код. порожденный f(x), будем обозначать Q. а код, порожденный д(х), будем обозначать N.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>