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

Пусть нечетное простое число. Классы вычетов чисел по модулю называются квадратичными вычетами по модулю Для того чтобы найти полное множество квадратичных вычетов по модулю достаточно рассмотреть квадраты чисел от 1 до На самом деле, поскольку полное множество порождается квадратами Остальные классы по модулю называются невычетами.

Например, при квадратичными вычетами по модулю 17 будут Остальные числа 3, 5, 6, 7, 10, 11, 12 и 14 будут невычетами. Квадратично-вычетные коды определяются требованием, согласно которому корнями порождающего многочлена должны быть в точности все квадратичные вычеты.

Определение. Пусть множество квадратичных вычетов по модулю числа множество невычетов. Зададим порождающие многочлены

где элемент порядка в расширении поля GF (2). Коды, порожденные многочленами называются квадратично-вычетными.

Коды, порожденные эквивалентны в том смысле, что они имеют одинаковый спектр. [Аналогичное утверждение справедливо для Заметим, что при выполнено равенство где содержит вычеты, а —невычеты. Продолжая рассмотрение предыдущего примера для обозначаем через примитивный элемент поля Поскольку то имеет порядок 17. В качестве корней можно взять

Это множество степеней а является полным множеством квадратичных вычетов по модулю 17. Таким образом, это множество совпадает с множеством корней Строя с помощью неприводимого многочлена получаем, что является минимальной функцией для т. е.

Аналогично является минимальной функцией для т. е.

Кодовое расстояние обоих квадратично-вычетных -кодов

Можно показать, что кодовое расстояние квадратично-вычетных кодов удовлетворяет неравенству Это неравенство можно улучшить и получить

при К сожалению, эти границы плохи при больших значениях и не помогают при определении кодового расстояния большинства кодов. Однако кодовое расстояние некоторых квадратично-вычетных кодов для небольших длин больше кодового расстояния кодов БЧХ со сравнимыми длинами. Это привело к большому числу исследований, посвященных поиску длинных квадратично-вычетчых кодов и определению их свойств. Некоторые наиболее важные теоретические результаты, а также полный список литературы можно найти в книгах Мак-Вильямс и Слоэна [8], Берлекэмпа [2] и Питерсона и Уэлдона [1].

Некоторые из этих кодов являются также примерами непримитивных кодов БЧХ [например, -код Голея)]; они приведены в табл. А. 2. Во многих случаях декодирование таких кодов оказывается сложнее декодирования кодов БЧХ. Однако в следующих двух главах будут приведены алгоритмы декодирования, пригодные для декодирования этих кодов.