A NEW CLASS OF CYCLIC CODES USING ORDERED POWER PRODUCT OF POLYNOMIALS

Journal of Applied Mathematics & Informatics.
2014.
Sep,
32(3_4):
529-537

- Received : August 20, 2013
- Accepted : November 30, 2013
- Published : September 28, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

The paper introduces a new product of polynomials defined over a field. It is a generalization of the ordinary product with inner polynomial getting non-overlapping segments obtained by multiplying with coefficients and variable with expanding powers. It has been called ‘Ordered Power Product’ (OPP). Considering two rings of polynomials
R_{m}
[
x
] =
F
[
x
] modulo
x^{m}
- 1 and
R_{n}
[
x
] =
F
[
x
]modulo
x^{n}
- 1 , over a field F, the paper then considers the newly introduced product of the two polynomial rings. Properties and algebraic structure of the product of two rings of polynomials are studied and it is shown to be a ring. Using the new type of product of polynomials, we define a new product of two cyclic codes and devise a method of getting a cyclic code from the ‘ordered power product’ of two cyclic codes. Conditions for the OPP of the generators polynomials of component codes, giving a cyclic code are examined. It is shown that OPP cyclic code so obtained is more efficient than the one that can be obtained by Kronecker type of product of the same component codes.
AMS Mathematics Subject Classification : 94B15, 94B99.
Definition 2.1.
Ring of polynomials: Given a field
F
, we can consider a polynomial as,
where coefficients
a
_{0}
,
a
_{1}
,
a
_{2}
, ...,
a
_{n−1}
∈
F
. The collection of all polynomials over field
F
, denoted by
F
[
x
] under usual addition and product of polynomials, forms a ring, called ‘ring of polynomials over
F
’.
Definition 2.2.
Ring of polynomials : Algebra of Polynomial Residue Classes (Refer Peterson andWeldon (1972) The residue classes of the ring of polynomials
F
[
x
] modulo (
x^{n}
− 1) a polynomial
ƒ
(
x
) of degree n form a commutative linear algebra of dimension n over the coefficient field F.
Definition 2.3.
Cyclic code: An(
n, k
) block code
C
is said to be cyclic if it is linear and if for every code word
C
= (
c
_{0}
,
c
_{1}
,
c
_{2}
, ...,
c
_{n−1}
) ∈
C
, its right cyclic shift
= (
c
_{n−1}
,
c
_{1}
,
c
_{2}
, ...,
c
_{n−2}
) ∈
. An cyclic code is generated by a polynomial
g
(
x
) of degree
n
−
k
that is a factor of (
x^{n}
− 1).
F
, and consider the set of all polynomials
F
[
x
]. We will be considering structure of
F
[
x
] modulo some polynomial, say,
g
(
x
). It is proposed to define a new type of composition on polynomials, in which order of the polynomials multiplied is retained and segments of the product arise in terms of rising powers, we name it as ‘Ordered Power product.’ To motivate the new product, let us look at ordinary product of two polynomials
λ
(
x
) =
c
_{0}
+
c
_{1}
x
+
c
_{2}
x
^{2}
+...+
c
_{m−1}
x
^{m−1}
and
V
(
x
) =
a
_{0}
+
a
_{1}
x
+
a
_{2}
x
^{2}
+...+
a
_{n−1}
x
^{n−1}
, then
Generalizing this by considering suitably indexed powers of x in the segments above, we arrive at the following what we call as the ‘Ordered power Product’ (OPP).
Definition 3.1.
Ordered Power Product of Polynomials in non-overlapping sifting segments: Let
λ
(
x
) =
c
_{0}
+
c
_{1}
x
+
c
_{2}
x
^{2}
+...+
c
_{m−1}
x
^{m−1}
and
V
(
x
) =
a
_{0}
+
a
_{1}
x
+
a
_{2}
x
^{2}
+...+
a
_{n−1}
x
^{n−1}
be two polynomials of degree
m
− 1 and
n
− 1 respectively over a field F. The ordered power product of
λ
(
x
)and
V
(
x
) (in nth power of in different segments), denoted by
λ
(
x
) ∗
V
(
x
), is defined as
In short we shall call it ‘Ordered Power Product’ (OPP) or ∗product of
λ
(
x
) and
V
(
x
).
Remark 3.1.
Clearly, the degree of the product polynomial
λ
(
x
) ∗
V
(
x
) is (
m
− 1)
n
+ (
n
− 1) =
mn
− 1 .
Remark 3.2.
We call it ‘ordered’ because as proved below, unlike ordinary product it is not commutative.
Remark 3.3.
Just for convenience, in the product so defined, we will refer to
λ
(
x
) as outer polynomial and
V
(
x
) as inner polynomial.
Example 1.
Let
λ
(
x
) = 1 + 2
x
+ 4
x
^{3}
+ 5
x
^{4}
be a polynomial (outer) of degree 4, with
m
= 5 and
V
(
x
) = 2+
x
^{2}
+
x
^{6}
be the polynomial of degree 6 with
n
= 7 then
this example also verifies the degree of outer product of two polynomials
λ
(
x
) ∗
V
(
x
) mentioned above.
Definition 3.2.
Vector Equivalence of OPP: Interestingly, if polynomials are replaced by their equivalent vectors
then it can be easily seen that
λ
∗
V
is the Kronecker product of vectors
λ
and
V
.
Properties of Ordered Power of Product of Polynomials
(i) Non Commutativity: The * product of polynomials is in general non commutative, i.e.,
Proof: Choosing
λ
(
x
) and
V
(
x
) as above, we have
Also,
In general (1) and (2) are different and this proves the result.
(ii) Associativity : The * product of two polynomials is in general associative, i.e.,
Proof: Associativity: in the above notation associativity is easy to prove by calculations like
(iii) Distributive over addition: The * product of two polynomials is such that:
(a) The outer polynomial distributes over the sum of inner polynomials,
(b) The inner polynomial distributing over the sum of outer polynomials,
Where
U
(
x
) and
V
(
x
) are of same degree
n
−1 and
C
(
x
) and
D
(
x
) are of same degree
m
− 1 .
Proof: We prove both the forms
R_{m}
[
x
]
modulo
(
x^{m}
− 1) and
R_{n}
[
x
]
modulo
(
x^{n}
− 1), where m and n are any positive integers. Obviously these rings contain respectively all polynomials of degree
m
− 1,
n
− 1 and less.
Definition 4.1.
Let
λ_{j}
(
x
) =
c
_{0j}
+
c
_{1j}
x
+
c
_{2j}
x
^{2}
+...+
c
_{(m−1)j}
x
^{m−1}
∈
R_{m}
(
x
) for different values of
j
be polynomials of degree
m
− 1 or less and
V_{i}
(
x
) =
a
_{0i}
+
a
_{1i}
x
+
a
_{2i}
x
^{2}
+...+
a
_{(n−1) i}
x
^{n−1}
∈
R_{n}
(
x
) for different values of
i
, be polynomials of degree
n
− 1 or less. We define the set of ordered power product of
R_{m}
[
x
] and
R_{n}
[
x
] as
Theorem 4.2.
If R_{m}
[
x
]
F
(
x
)
modulo
(
x^{m}
- 1),
R_{n}
[
x
] =
F
(
x
)
modulo
(
x^{n}
- 1),
m and n being any positive integers, are two rings of polynomial over a field F, then
is a ring of polynomials of degree mn
- 1,
under ordinary addition and ordered product of elements of
Γ (x)
modulo
(
x^{m}
− 1,
x^{n}
− 1)
over F.
Proof
. Proof is simply followed by the definition.
x^{n}
− 1) may be taken as (
x^{n}
+ 1) , and that 1+1 = 0. Since cyclic codes of length n are generated by factors of (
x^{n}
− 1), we next give some useful results for getting its factors.
Lemma 5.1.
For p and q distinct prime numbers and r and s are natural num-bers, we have
Proof
. The results can be easily verified, and extended for , for any n when n is expressed as product of powers of primes.
Theorem 5.2.
If
(
n
_{1}
,
k
_{1}
)
and
((
n
_{2}
,
k
_{2}
)
are two cyclic codes with
g
_{1}
(
x
)
and
g
_{2}
(
x
)
as their generator polynomials then the * product of their generator polynomials given by
g
(
x
) =
g
_{1}
(
x
)∗
g
_{2}
(
x
)
of degree
(
n
_{1}
−
k
_{1}
)
n
_{2}
+(
n
_{2}
−
k
_{2}
)
code, will generate a cyclic
(
n, k
)
code, where n
=
n
_{1}
n
_{2}
and
k
= (
k
_{1}
− 1)
n
_{2}
+
k
_{2}
,
whenever
g
_{2}
(
x
)
divides
x_{n}
− 1.
Proof
. Let
g
(
x
) =
g
_{1}
(
x
) ∗
g
_{2}
(
x
). It can be written as a simple product:
g
(
x
) =
g
_{1}
(
x
^{n2}
)
g
_{2}
(
x
) where
g
_{1}
(
x
) and
g
_{2}
(
x
) are divisors of
x
^{n1}
−1 and
x
^{n2}
−1 respectively. For
g
(
x
)to represent a cyclic code of length
n
_{1}
n
_{2}
−1,
g
(
x
) must a factor of
x
^{n1n2−1}
. So we examine the conditions under which
g
(
x
) =
g
_{1}
(
x
) ∗
g
_{2}
(
x
) is a divisor of
x
^{n1n2}
−1. First we show that
g
_{1}
(
x
^{n2}
) is a divisor of
x
^{n1n2}
−1. This follows from the fact that
g
_{1}
(
x
) is a divisor of
x
^{n1−1}
, and by replacing
x
by
x
^{n2}
. Thus we get that
g
_{1}
(
x
^{n2}
) is a divisor of (
x
^{n2}
)
^{n1−1}
=
x
^{n1n2}
− 1. It remains to investigate the conditions for
g
_{2}
(
x
) is a factor of
x
^{n1n2}
− 1. This will not happen for all choices of
n
_{1}
n
_{2}
, as is evident by the Example 3 below. We therefore can use the result of the Lemma above for determining if
g
_{2}
(
x
) divides
x
^{n1n2}
− 1. In fact any one or products of any numbers of these factors can be taken for
g
_{2}
(
x
) to get the *-product cyclic code from generator polynomials of component codes.
Note: It may have been noted that while choice of , the inner-polynomial, is limited, there is no limitation on choice of outer polynomial in forming OPP codes.
Theorem 5.3.
If
(
n
_{1}
,
k
_{1}
)
and
(
n
_{2}
,
k
_{2}
)
are two cyclic codes with
g
_{1}
(
x
)
and
g
_{2}
(
x
)
as their generator polynomials and
g
_{2}
(
x
)
dividesx
^{n1n2}
− 1
then the * product
g
(
x
) =
g
_{1}
(
x
) *
g
_{2}
(
x
)
generates
(
n
_{1}
n
_{2}
,
k
)
code, where k
= (
k
_{1}
− 1)
n
_{2}
+
k
_{2}
.
Also then k
− 1
code polynomials
g
(
x
),
xg
(
x
),
x
^{2}
g
(
x
), ...,
x
^{k−1}
g
(
x
)
span cyclic code C.
Proof
. The proof follows directly from the definition of cyclic code generated by g(x).
Example 2.
Let us consider two cyclic codes
C
_{1}
and
C
_{2}
where
C
_{1}
is (7, 4) code and
C
_{2}
is (3, 1) cyclic code with generator polynomials
g
_{1}
= (1 +
x
+
x
^{3}
) and
g
_{2}
= (1 +
x
+
x
^{2}
) respectively. Then
Example 3.
Let us consider two cyclic codes
C
_{1}
and
C
_{2}
where
C
_{1}
is (3, 2) code and
C
_{2}
is ( (7, 4) cyclic code with generator polynomials
g
_{1}
= (1 +
x
) and
g
_{2}
= (1 +
x
+
x
^{3}
) respectively. Then
Here
g
_{2}
(
x
) = (1 +
x
+
x
^{3}
) is not a divisor of
x
^{21}
− 1 .
Theorem 5.4.
If two linear binary cyclic codes
(
n
_{1}
,
k
_{1}
)
and
(
n
_{2}
,
k
_{2}
)
have rates
R
_{1}
and
R
_{2}
then the rate R of their cyclic Code is an increasing function of the rate of either component code
.
Proof
. Let R be the rate of the product cyclic code. Then, we have
and trivially, (
R
=
R
_{1}
R
_{2}
), when
k
= 1. In general the difference is directly proportional to
R
_{1}
, and increases with
R
_{2}
. This shows that the newly introduced OPP cyclic codes are a new class of codes that have rates better than those that be obtained by their Kronecker product codes.
λ
(
x
) =
c
_{0}
+
c
_{1}
x
+
c
_{2}
x
^{2}
+...+
c
_{m−1}
x
^{m−1}
and
V
(
x
) =
a
_{0}
+
a
_{1}
x
+
a
_{2}
x
^{2}
+ ... +
a
_{n−1}
a
^{n−1}
; but
λ
(
x
) ∗
V
(
x
) =
c
_{0}
V
(
x
) +
c
_{1}
x^{k}
V
(
x
) +
c
_{2}
x
^{2k}
V
(
x
) + ... +
c
_{m−1}
x
^{(m−1)k}
V
(
x
). where
k
<
n
, or even when
k
>
n
. In such cases we can perhaps use the notation for OPP using an index
like
∗
^{k}
−
opp
. These interesting cases are being studied separately.
Ankita Gaur received M.Sc. from Dr. B.R.A. University and Ph.D Scholar at Jaypee Institute of Information Technology University, Noida , India. Her research interests include information and coding theory.
Department of Mathematics, Jaypee Institute of Information Technology University, Noida, India.
e-mail: ankitagaur50@yahoo.com
BhuDev Sharma received Ph.D. from Delhi University, India. He is currently a professor at Jaypee Institute of Information Technology University, Noida, India. He was a faculty at the University of Delhi (1966-1979) andearlier at other places. He spent about 29 years abroad 20 years (1988-2007) in USA and 9 years (1979-1988) in the West Indies, as Professor of Mathematics and in between as chair of the department. Professor Sharma has published over 120 research papers in the areas covering Coding Theory, Information Theory, Functional Equations and Statistics. He has successfully guided 23 persons for Ph.D. in India and abroad. He has also authored/co-authored 23 published books in Mathematics and some others on Indian studies. He is the Chief Editor of Jr. ofn Combinatorics, Information and System Sciences JCISS (1976-present), and is on the editorial boards of several other journals. He is memberof several professional academic organizations. Past President of Forum for Interdisciplinary Mathematics (FIM), Vice President of Calcutta Mathematical Society, Ramanujan Math Society, Vice President of Academy of Discrete Mathematics and Applications (ADMA). After returning to India, he is working on establishing a Center of Excellence in Interdisciplinary Mathematics (CEIM) in Delhi, India. Professor Sharma has received several awards and recognitions in India and abroad. He is widely traveled that would include Germany and several other countries of Europe, Brazil, Russia, and China. He has organized several International Conferences on Math/Stat in India, USA, Europe, Australia and China. Currently five persons are registered for Ph.D. under his supervision. His research interests are computational mathematics, iterative methodand parallel computation.
Department of Mathematics, Jaypee Institute of Information Technology University, Noida, India.
e-mail: bhudev sharma@yahoo.com

1. Introduction

Linear algebra and in particular vector spaces are important mathematical structures and have numerous applications. There are areas, for example coding theory, finite geometries and statistical theory of designs, where vector spaces provide basic foundations. There it is felt that higher order and more efficient structures can be developed with advantage by suitably composing the lower order structures. There is thus interest in developing new mathematical composition laws on vectors, matrices and polynomials. Elias (1954) used Kronecker product of matrices to develop higher efficiency codes by combination of lower order codes. The method was powerful, but it could develop only a sparse class of product codes and the all important duality property was lost. Sharma (2008), introduced a new concept of matrix-multiplication called the partitioned product of matrices, and obtained a rather large class of rank-partitioned product codes in which the duality property was preserved. Cyclic codes, as is known, are ideally suited for implementation through shift registers. Most important codes like BCH, Goppa codes etc. are cyclic codes, which are best characterized through their generator polynomials. Composing higher order cyclic codes from lower order codes in terms of their generator polynomials has not been explored at any length. The reason for not been able to do that is that there does not exist a method of multiplying two polynomials leading to what may be used to consider product of two cyclic codes. In this paper, we start by introducing a new product of two polynomials defined over a field. It is a generalization of the ordinary product. For convenience we call the two polynomials as outer and inner polynomials. The new defined product then results in non-overlapping segments obtained by multiplying it with coefficients of outer polynomials and expanding powers of the variable. It is called Ordered Power Product and has elegant algebraic properties leading to new algebraic structures. Paper carries a section on applications of the above concepts in developing product of two cyclic codes, in terms of the new product defined by us of two polynomials. Paper is organized as follows: Section 2 gives basic definitions required for later study. In Section 3, the Ordered Power Product of two polynomials in introduced and its algebraic properties are reported. Section 4 carries Applications of Ordered Power Product of polynomials in Coding Theory and an example is given to illustrate the a cyclic code arising from the OPP of two cyclic codes. In Section 5, we refer to further work under study.
2. Main results

For our purpose, we begin with following simple well known algebraic ideas of polynomials over a field F. For details, one may refer to any standard text on Algebra as also Peterson and Weldon 1972 Chapters 2 and 6.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

3. New Product - Ordered Power Product of polynomials

Linear algebraic structures, as is well known, are studied with advantage through polynomials. While direct polynomial addition and multiplications are commonly used as the operations on polynomial, wider algebraic structures and applications are done by considering polynomial algebra over a field. Here we shall consider polynomials over a field
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- λ(x) =c0+c1x+c2x2+ ... +cm−1xm−1≈ (c0,c1,c2, ....,cm−1) =λand
- V(x) =a0+a1x+a2x2+ ... +an−1xn−1≈ (a0,a1,a2, ....,an−1) =V

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

4. Ordered Power Product of Rings of Polynomials

In this section we extend the idea considered above to product of two sets of polynomials defined over the same field F. In particular, let us consider two rings of polynomials namely,
PPT Slide

Lager Image

PPT Slide

Lager Image

5. Applications of OPP of Polynomials in Coding Theory

In this section, we consider cyclic binary codes represented by their generator polynomials and study the codes obtained by their OPP-composition. It may be pointed out that in the binary case, (
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

6. Concluding Remarks

We have considered ordered power product of two polynomials in such powers of x that the various segments of the inner polynomial are laterally advanced without having overlaps amongst them, with coefficients multiplied by those of the outer polynomial. For this choice the motivation was to consider a new composition suitable for developing new product type of codes, which are more efficient. However, an ordered power product may be defined more generally, when this is not the case, that is when
BIO

Berlekamp E. R.
1968
Algebraic Coding Theory
McGraw-Hill
New York

Bose R.C.
,
Ray Chaudhuri D.K.
1960
On a class of error correcting binary group codes
Information and Control
3
68 -
79
** DOI : 10.1016/S0019-9958(60)90287-4**

Burton H.O.
,
Weldon E.J.
1965
Cyclic Product Code
IEEE Trans On Information Theory
IT-11
433 -
439

Elias P.
1954
Error-Free Coding
IRE Transactions
PGIT-4
29 -
37

Peterson W. W.
,
Weldon E. J.
1972
Error-Correcting Codes
2nd ed.
MIT Press
Cambridge, Mass.

Shannon C. E.
1948
The mathematical theory of communication
Bell System Technical Journal
27
379 -
423
** DOI : 10.1002/j.1538-7305.1948.tb01338.x**

Sharma Bhu Dev
2008
Partitioned Product of Matrices and Construction of Efficient Product Codes
Journal of Comb. Information and System Sciences
33
437 -
448

Slepian D.
1960
Some further theory of group codes
Bell System Technical. Journal
39
1219 -
1252
** DOI : 10.1002/j.1538-7305.1960.tb03958.x**

Citing 'A NEW CLASS OF CYCLIC CODES USING ORDERED POWER PRODUCT OF POLYNOMIALS
'

@article{ E1MCA9_2014_v32n3_4_529}
,title={A NEW CLASS OF CYCLIC CODES USING ORDERED POWER PRODUCT OF POLYNOMIALS}
,volume={3_4}
, url={http://dx.doi.org/10.14317/jami.2014.529}, DOI={10.14317/jami.2014.529}
, number= {3_4}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={GAUR, ANKITA
and
SHARMA, BHUDEV}
, year={2014}
, month={Sep}