Advanced
A NEW CLASS OF CYCLIC CODES USING ORDERED POWER PRODUCT OF POLYNOMIALS
A NEW CLASS OF CYCLIC CODES USING ORDERED POWER PRODUCT OF POLYNOMIALS
Journal of Applied Mathematics & Informatics. 2014. Sep, 32(3_4): 529-537
Copyright © 2014, Korean Society of Computational and Applied Mathematics
  • Received : August 20, 2013
  • Accepted : November 30, 2013
  • Published : September 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
ANKITA GAUR
BHUDEV SHARMA

Abstract
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 Rm [ x ] = F [ x ] modulo xm - 1 and Rn [ x ] = F [ x ]modulo xn - 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.
Keywords
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.
Definition 2.1. Ring of polynomials: Given a field F , we can consider a polynomial as,
PPT Slide
Lager Image
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 ( xn − 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
PPT Slide
Lager Image
= ( c n−1 , c 1 , c 2 , ..., c n−2 ) ∈
PPT Slide
Lager Image
. An cyclic code is generated by a polynomial g ( x ) of degree n k that is a factor of ( xn − 1).
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 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
  • λ(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
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.,
PPT Slide
Lager Image
Proof: Choosing λ ( x ) and V ( x ) as above, we have
PPT Slide
Lager Image
Also,
PPT Slide
Lager Image
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.,
PPT Slide
Lager Image
Proof: Associativity: in the above notation associativity is easy to prove by calculations like
PPT Slide
Lager Image
(iii) Distributive over addition: The * product of two polynomials is such that:
(a) The outer polynomial distributes over the sum of inner polynomials,
PPT Slide
Lager Image
(b) The inner polynomial distributing over the sum of outer polynomials,
PPT Slide
Lager Image
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
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, Rm [ x ] modulo ( xm − 1) and Rn [ x ] modulo ( xn − 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 Rm ( x ) for different values of j be polynomials of degree m − 1 or less and Vi ( x ) = a 0i + a 1i x + a 2i x 2 +...+ a (n−1) i x n−1 Rn ( x ) for different values of i , be polynomials of degree n − 1 or less. We define the set of ordered power product of Rm [ x ] and Rn [ x ] as
PPT Slide
Lager Image
Theorem 4.2. If Rm [ x ] F ( x ) modulo ( xm - 1), Rn [ x ] = F ( x ) modulo ( xn - 1), m and n being any positive integers, are two rings of polynomial over a field F, then
PPT Slide
Lager Image
is a ring of polynomials of degree mn - 1, under ordinary addition and ordered product of elements of Γ (x) modulo ( xm − 1, xn − 1) over F.
Proof . Proof is simply followed by the definition.
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, ( xn − 1) may be taken as ( xn + 1) , and that 1+1 = 0. Since cyclic codes of length n are generated by factors of ( xn − 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
PPT Slide
Lager Image
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 xn − 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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.
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 λ ( 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 xk 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.
BIO
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
References
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