close

Вход

Забыли?

вход по аккаунту

?

О числе различных циклических кодов заданной длины.

код для вставкиСкачать
УДК 519.725.2
О ЧИСЛЕ РАЗЛИЧНЫХ ЦИКЛИЧЕСКИХ КОДОВ ЗАДАННОЙ ДЛИНЫ
© 2013
С.Ю. Корабельщикова, кандидат физико-математических наук, доцент,
доцент кафедры математического анализа, алгебры и геометрии
А.И. Чесноков, студент
Северный (Арктический) федеральный университет, Архангельск (Россия)
Ключевые слова: циклический код; порождающий многочлен; конечное поле.
Аннотация: Рассматривается задача нахождения числа циклических кодов над конечным полем с произвольными фиксированными параметрами n – длина кода, и k – количество информационных символов. Приведен алгоритм решения этой задачи в общем виде, его теоретическое обоснование, программный код на языке С++,
а также результаты работы программы при некоторых фиксированных значениях.
ВВЕДЕНИЕ
В практике помехоустойчивого кодирования успешно применяются циклические коды. Они, в дополнение к структуре линейного подпространства, обладают свойством устойчивости относительно циклического сдвига. Это требование приводит к возможности
реализации кодеров и декодеров циклических кодов
на основе регистров сдвига с обратной связью. Принципы построения и современные области применения
двоичных циклических кодов описаны в [1], недвоичных – в [2] и ряде других.
При построении циклического кода чаще всего параметры n – длина кода, q – мощность конечного поля,
над которым строится код, и k – число информационных символов, заранее известны. Поэтому вполне естественно возникает вопрос о числе различных циклических кодов с фиксированными значениями n, q и k.
В учебной литературе по этой теме обычно приводится
ряд частных задач такого вида [2, стр. 298]. Также известна формула для количества неприводимых нормированных многочленов данной степени над конечным
полем [3, стр. 129], однако она не дает решения нашей
задачи, так как порождающий многочлен циклического
кода не обязан быть неприводимым.
ЦИКЛИЧЕСКИЕ КОДЫ ЗАДАННОЙ ДЛИНЫ
Конечное поле из q элементов будем обозначать Fq.
Как известно, q является степенью простого числа.
Циклический (n, k) код над конечным полем Fq, имеющий длину n и k информационных символов, однозначно определяется порождающим многочленом g(x)
над полем Fq, удовлетворяющим трем условиям:
1. g(x) нормированный;
2. степень g(x) равна n-k;
3. многочлен xn–1 делится на g(x) в кольце многочленов Fq[x].
Верно и обратное утверждение [2, стр. 286]: если
взять любой нетривиальный нормированный делитель
g(x) многочлена xn–1 в кольце многочленов Fq[x],
то он будет порождать некоторый циклический код с количеством проверочных символов, равным степени g(x).
Таким образом, число различных циклических кодов длины n над полем Fq равно числу различных нетривиальных нормированных делителей многочлена
xn–1. Значит, если имеется разложение многочлена
xn–1 на неприводимые нормированные множители
над полем Fq:
xn–1=f1(x)f2(x)…fs(x),
Вектор науки ТГУ. 2013. № 4
то количество различных циклических кодов будет
равно 2s-2 (из общего числа делителей вычли 2 тривиальных). Здесь подсчитаны всевозможные коды с произвольным числом информационных символов. Заметим, что среди этих кодов могут быть эквивалентные.
Для нахождения числа различных циклических (n, k)
кодов достаточно знать лишь степени многочленов
из разложения (1).
Следует отметить, что в случае наибольшего общего
делителя (НОД) (n, q)=1 многочлен f(x)=xn–1 взаимно
прост со своей производной, и значит, не имеет кратных делителей. Все корни этого многочлена образуют
циклическую группу <> порядка n в некотором расширении F m поля Fq. Для нахождения степеней многоq
членов из разложения (1), нужно разбить эту группу
на классы сопряженных над полем Fq элементов и подсчитать количество элементов в каждом классе. Как известно, число элементов в классе равно степени соответствующего этому классу минимального многочлена.
В противном случае НОД (n, q)=d1, n=dk, и задача
сводится к разложению многочлена xk–1, так как получим в кольце Fq[x]:
x n  1  x kd  1  ( x k  1) d ,
где НОД (k, q)=1.
Таким образом, каждый многочлен из разложения
xk–1 будет входить в разложение исходного многочлена
xn–1 ровно d раз.
Рассмотрим, каким образом производится разбиение
циклической группы <>={1, , 2, …, n-1} на классы
сопряженных над полем Fq элементов. Известно,
что возведение каждого элемента в степень q является автоморфизмом поля F m над подполем Fq. Этот автоморq
физм : F m  F m , (a)=aq, называют автоморфизмом
q
q
Фробениуса поля F m над Fq. Он является порождающим
q
циклической группы автоморфизмов поля F m над Fq,
q
и, как любой автоморфизм этой группы, переводит корень
многочлена из Fq[x] в корень этого же многочлена. Поэтому если i – корень неприводимого над полем Fq многочлена f(x), то и (i)q – корень многочлена f(x), и класс
элементов, сопряженных с i, состоит из элементов:
2
m1
{ i ,  iq ,  iq , ... ,  iq } . Построение класса заканчивается,
когда для некоторого m получаем:  iq   i .
m
(1)
25
С.Ю. Корабельщикова, А.И. Чесноков «О числе различных циклических кодов заданной длины»
Заметим, что разбиение циклической группы
<>={1, , 2, …, n-1} на классы сопряженных элементов можно заменить разбиением на классы чисел от 0
до n−1, соответствующих степеням .
Теперь дадим оценку количества циклических (n, k)
кодов над полем Fq. Пусть нам известны степени многочленов f1(x), f2(x), …, fs(x) из разложения (1). Тогда вопрос
сводится к подсчету способов представления числа n-k
в виде суммы этих чисел. Эта задача эквивалентна частному случаю задачи о рюкзаке (knapsack problem, [4]).
Приведем фрагмент программного кода для нахождения этого значения на языке С++ [5]:
#include <iostream>
#include <vector>
using namespace std;
int gcd(int a,int b)
{
if (!a)
return b;
return gcd(b%a,a);
}
int main()
{
int n,k,q;
cin >> n >> k >> q;
if (k <=0 || k >=n || n < 1 || q < 2){
cout << "Input incorrect";
return 0;
}
int step=gcd(n,q);
n /=step;
k=n - k;
if (k <=0){
cout << "Input incorrect";
return 0;
}
vector<bool> used(n);
vector<int> dp(k + 1);
dp[0]=1;
for(int i=0;i < n;i++)
if (!used[i]){
int ord=1;used[i]=true;
int x=(i * q) % n;
while(x !=i)
used[x]=true,ord++,x=(x * q) % n;
for(int j=k; j >=ord;j--)
if (dp[j - ord])
for(int t=j,ost=step;ost && t <=k;ost--){
dp[t] +=dp[j - ord];
t +=ord;
}}
cout << dp[k] << endl;
return 0;
}
В частности, для двоичных циклических кодов примитивной длины n=15 получены следующие значения
P(k) – количества различных циклических кодов данной
длины с k информационными символами: P(1)=1,
P(2)=1, P(3)=1, P(4)=3, P(5)=3, P(6)=3, P(7)=3, P(8)=3,
P(9)=3, P(10)=3, P(11)=3, P(12)=1, P(13)=1, P(14)=1.
Для сравнения, у циклических кодов над полем F4
длины n=15 получены следующие значения P(k):
P(1)=3, P(2)=9, P(3)=19, P(4)=33, P(5)=51, P(6)=65,
P(7)=75, P(8)=75, P(9)=65, P(10)=51, P(11)=33,
P(12)=19, P(13)=9, P(14)=3.
Как легко заметить, P(k)=P(n−k), поэтому для троичных кодов примитивной длины n=26 приведем лишь
половину значений P(k): P(1)=2, P(2)=1, P(3)=8,
P(4)=16, P(5)=8, P(6)=28, P(7)=56, P(8)=28, P(9)=56,
P(10)=112, P(11)=56, P(12)=70, P(13)=140.
ЗАКЛЮЧЕНИЕ
В данной статье были рассмотрены некоторые алгебраические аспекты теории построения циклических кодов,
необходимые для оценки количества различных циклических (n, k) кодов над конечным полем мощности q. Получено решение в общем виде с применением вычислительных
средств. В программной части нами использовались методы динамического программирования, а также метод сведения исходной задачи к задаче о рюкзаке. В будущем для
больших размерностей предполагается применить эвристические алгоритмы, аналогичные рассмотренным в [4, 6].
СПИСОК ЛИТЕРАТУРЫ
1. Лидл Р., Пильц Г. Прикладная абстрактная алгебра. –
Екатеринбург: Уральский университет, 1996 г., С. 226.
2. Вернер М. Основы кодирования. – М.: Техносфера,
2006. – 288 с.
3. Зяблицева Л. В., Колпачникова Т. А. Конечные поля
и многочлены над ними. – Архангельск: Поморский
университет, 2006., С.112.
4. Громкович Ю. Теоретическая информатика. Введение
в теорию автоматов, теорию вычислимости, теорию
сложности, теорию алгоритмов, рандомизацию, теорию
связи и криптографию. –БХВ-Петербург, 2010. – 325 с.
5. Страуструп Б. Язык программирования С++. – Бином, 2011. – 1136 с.
6. Melnikov B. Multiheuristic approach to discrete optimization problems. – Cybernetics and Systems Analysis.
2006. Vol. 42, No 3, P. 335–341.
NUMBER OF DIFFERENT CYCLIC CODES OF SPECIFIED LENGTH
© 2013
S.Y. Korabelshchikova, candidate of physical and mathematical sciences,
associate professor, department of mathematical analysis, algebra and geometry,
A.I. Chesnokov, student
Northern (Arctic) Federal University named after M.V. Lomonosov, Arkhangelsk (Russia)
Keywords: cyclic code; the generator polynomial; finite field.
Annotation: We consider the problem of determining the number of cyclic codes over a finite field with arbitrary fixed parameters n – length of the code, and k – the number of data symbols. An algorithm of solution of this problem is given
for the general case. There are theoretical justification of the algorithm, the program code in C++, as well as results of the program for some fixed values.
26
Вектор науки ТГУ. 2013. № 4
Документ
Категория
Без категории
Просмотров
15
Размер файла
902 Кб
Теги
кодо, длина, циклические, заданной, числа, различных
1/--страниц
Пожаловаться на содержимое документа