Constacyclic codes

CONSTACYCLIC CODES

SAROJ RANI

DEPARTMENT OF MATHEMATICS

INDIAN INSTITUTE OF TECHNOLOGY DELHI

DECEMBER 2016

©Indian Institute of Technology Delhi (IITD), New Delhi, 2016

CONSTACYCLIC CODES

by

SAROJ RANI

DEPARTMENT OF MATHEMATICS

Submitted

in fulfillment of the requirements of the degree of Doctor of Philosophy

to the

INDIAN INSTITUTE OF TECHNOLOGY DELHI DECEMBER 2016

Dedicated to

My Family and Supervisor

Certificate

This is to certify that the thesis entitled “Constacyclic Codes” submitted by “Ms. Saroj Rani” to the Indian Institute of Technology Delhi, for the award of the Degree of Doctor of Philosophy, is a record of the original bona fide research work carried out by her under my supervision and guidance. The thesis has reached the standards fulfilling the requirements of the regulations relating to the degree.

The results contained in this thesis have not been submitted in part or full to any other university or institute for the award of any degree or diploma.

Dr. Anuradha Sharma Assistant Professor Department of Mathematics Indian Institute of Technology Delhi

i

Acknowledgements

There are many ways of expressing one’s gratitude towards someone. Language is one such way by means of which one can express one’s gratefulness and indebtedness to one’s guide and benefactors. Reaching foremost milestones in one’s life does not occur without the assistance of many great people and for each one of them, I am truly blessed and obliged.

I would like to express my heartfelt gratitude to my supervisor, Dr. Anuradha Sharma, for her proficient supervision and research acumen. Above all and the most needed, she provided me unflinching encouragement and support in various ways.

I am privileged to have the opportunity to work under her supervision. With her valuable suggestions, understanding, patience, enthusiasm, vivid discussions and above all with her friendly nature, she helped me in successfully completing my Ph.D. work. I am always being honored to have a teacher like her.

I am thankful to IIT Delhi authorities for providing me the necessary facilities and teaching assistantship for smooth completion of my research work. I express my regards to Prof. S. Dharmaraja, DRC Chairperson, for his love and support. Special thanks to my SRC (Student Research Committee) Members: Dr. Rupam Barman (Department of Mathematics), Dr. Ritumoni Sarma (Department of Mathematics) and Prof. S.D.Joshi (Department of Electrical Engineering) for generously sharing their time and knowledge. I’m also grateful to all faculty members of Department

iii

iv Acknowledgements

of Mathematics, IIT Delhi, for their cooperation and support.

Words cannot completely express my love and gratitude to my family who have supported and encouraged me during this journey. I would like to thank my parents for their life-long support and sacrifices, which sustained my interest in research and motivated me towards the successful completion of this study. My sincerest thanks to my brother Rajdeep and sister Santosh who have supported me through my difficult times with their inspiration and continous encouragement.

I will always remember the true friends who have walked with me on my path.

There are too many to mention by name, yet too few to ever lose room for in my heart. Many thanks to my dear friends, especially of Neelam, Abhishek, Madhu, Shaily, Anju, Seema, Swati and Alka for times of laughter when I needed a reprieve from the intensity of research.

Finally, I thank the almighty God for the passion, strength, perseverance, and the resources to complete this study.

Saroj Rani

Abstract

Coding theory originated with the paper entitled ‘A mathematical theory of communication’ by Claude Shannon [66]. One of the objectives of coding theory is to design and study encoding and decoding schemes for reliable and faster transmission of messages across noisy communication channels. While passing through a noisy channel, some of the bits of the message may get distorted by noise and the receiver may receive a message different from the message that was sent. In order to detect or correct such errors, many families of error-correcting codes have been introduced and studied. The most-studied family of error-correcting codes is that of cyclic codes, which was first introduced and studied by Prange [63]. In a related direction, Berlekamp [15] introduced and studied negacyclic codes over the finite field F^p, where p ≥ 5 is a prime. In a subsequent work, Berlekamp [14] introduced and studied constacyclic codes over finite fields, which are generalizations of cyclic and negacyclic codes. These codes form an important family of error-correcting codes due to the following reasons: (i) many examples of good codes can be found within this family of codes, and (ii) these codes can be easily encoded and decoded (in principle) using shift registers due to their inherent algebraic structure. Recently, the problem of determination of (i) the algebraic structure of constacyclic codes over finite fields and their dual codes in terms of generator polynomials and (ii) all self-dual, self-orthogonal and complementary-dual constacyclic codes, has attracted

v

vi Abstract

a lot of attention. However, the algebraic structure of constacyclic codes over finite fields is known only in certain special cases.

In this thesis, we determine generator polynomials of all constacyclic codes of length 4`<sup>m</sup>p<sup>n</sup> over the finite field Fq with q elements, where p, ` are distinct odd primes, q is a power of the prime p and m, n are positive integers. We also deter- mine their dual codes, and list all self-dual, self-orthogonal and complementary-dual constacyclic codes of length 4`<sup>m</sup>p<sup>n</sup> overF<sup>q</sup>.Besides this, we provide a method to list all constacyclic codes of length`p^w (w≥0 is an integer) over the finite fieldFq with q elements, whereq is a power of the prime p and ` is a positive integer coprime to q.

Recently, many important non-linear codes (e.g. Kerdock and Preparata codes) are related to linear codes over the ring of integers modulo 4 via the Gray map. This motivated many researchers to study constacyclic codes over finite rings. However, the algebraic structure of constacyclic codes is known only for some special lengths and over certain special classes of finite rings.

In this thesis, we determine all cyclic and negacyclic codes of length 4p^s over the finite commutative chain ring Fp^m+uFp^m, wherepis an odd prime, u² = 0 and s, mare positive integers. We also determine their dual codes and list some self-dual cyclic and negacyclic codes of length 4p^s overFp^m+uFp^m. Extending this work, we also determine all constacyclic codes of length 4p^sover the finite commutative chain ring Fp^m+uFp^m,wherepis an odd prime, u² = 0 ands, mare positive integers. We also determine their dual codes and list some isodual constacyclic codes of length 4p^s over Fp^m +uFp^m.

An important parameter of a constacyclic code is its (Hamming) weight distribu- tion, which is a measure of its error performance relative to various communication channels. Therefore the problem of determination of weight distributions of con- stacyclic codes is of great interest. However, weight distributions of constacyclic codes are known only in a few cases. In this thesis, we explore this problem for an

vii

important class of constacyclic codes over fields, viz. irreducible constacyclic codes, which are building blocks of all the constacyclic codes over finite fields and have applications in deep space communications. More precisely, we provide a trace de- scription for all the irreducible constacyclic codes of lengthn over the finite fieldF^q, wheren is a positive integer andqis a prime power coprime ton.As an application, we determine Hamming weight distributions of some irreducible constacyclic codes of length n overFq.We also derive a weight-divisibility theorem for irreducible con- stacyclic codes, and obtain both lower and upper bounds on the non-zero Hamming weights in irreducible constacyclic codes.

Contents

Certificate i

Acknowledgements iii

Abstract v

List of Tables xiii

List of Symbols xv

1 Introduction 1

1.1 Constacyclic codes over finite fields . . . 2 1.2 Constacyclic codes over finite commutative rings with unity . . . 4 1.3 Trace description and Hamming weights in irreducible constacyclic

codes . . . 6

2 Some preliminaries 9

2.1 Constacyclic codes over a finite commutative ring with unity . . . 9 2.1.1 Constacyclic codes over a finite field . . . 13 2.1.2 Constacyclic codes over the ring Fp^m+uFp^m, u² = 0 . . . 17

ix

x Contents

2.2 Cyclotomic numbers, Gaussian periods, period polynomials and Gaus-

sian sums . . . 18

3 Repeated-root constacyclic codes of length 4`^mpⁿ 29 3.1 Introduction . . . 29

3.2 Some preliminaries . . . 30

3.3 A classification of constacyclic codes of length 4`^mpⁿ over Fq . . . 35

3.4 Determination of constacyclic codes of length 4`^mpⁿoverFqand their dual codes . . . 37

3.4.1 gcd(`, q−1) = 1 . . . 37

3.4.2 gcd(`, q−1) =` . . . 54

3.5 Complementary-dual, self-orthogonal and self-dual cyclic and nega- cyclic codes of length 4`^mpⁿ overFq . . . 71

3.5.1 Cyclic codes . . . 71

3.5.2 Negacyclic codes . . . 80

4 Constacyclic codes over finite fields 101 4.1 Introduction . . . 101

4.2 Determination of q-cyclotomic cosets modulo k . . . 102

4.3 Determination of constacyclic codes over finite fields . . . 107

4.3.1 µ is an odd prime power . . . 109

4.3.2 µ is an even prime power . . . 113

4.3.3 µ is divisible by at least two distinct primes . . . 119

5 Cyclic and negacyclic codes of length 4p^s over Fp^m+uFp^m 133 5.1 Introduction . . . 133

5.2 Structure of cyclic codes of length 4p^s over F^pm +uF^pm . . . 134

5.2.1 p^m ≡1(mod 4) . . . 134

5.2.2 p^m ≡3(mod 4) . . . 136

Contents xi

5.3 Structure of negacyclic codes of length 4p^s overFp^m+uFp^m . . . 138

5.3.1 p^m ≡1(mod 8) . . . 138

5.3.2 p^m ≡5(mod 8) . . . 140

5.3.3 p^m ≡3(mod 4) . . . 141

6 Constacyclic codes of length 4p^s over F^pm +uF^pm 157 6.1 Introduction . . . 157

6.2 Determination of constacyclic codes of length 4p^s over F^pm +uF^pm . . 158

6.2.1 p^m ≡1(mod 4) and β 6= 0 . . . 159

6.2.2 p^m ≡1(mod 4) and β = 0 . . . 163

6.2.3 p^m ≡3(mod 4) and β 6= 0 . . . 174

6.2.4 p^m ≡3(mod 4) and β = 0 . . . 189

7 Trace description and Hamming weights in irreducible constacyclic codes over finite fields 205 7.1 Introduction . . . 205

7.2 Irreducible constacyclic codes and their Hamming weight distributions 206 7.2.1 Trace representation of irreducible constacyclic codes . . . 208

7.2.2 Weight distributions of irreducible constacyclic codes . . . 210

7.3 Weight distribution of M^(m,i)₁ . . . 213

7.4 Some more results on Hamming weights of irreducible constacyclic codes . . . 228

7.5 Examples . . . 232

Bio-Data 247

List of Tables

4.1 Determination of S₈₁⁽ⁱ⁾, 0≤i≤2 . . . 113 4.2 Determination of S₆₄⁽ⁱ⁾, 0≤i≤3 . . . 119 4.3 Determination of S₄₅⁽ⁱ⁾, 0≤i≤2 . . . 130 7.1 Some examples of optimal irreducible ξⁱ-constacyclic codes M^(m,i)₁

over Fq . . . 236 7.2 Weight distribution of code M^(m,i)₁ over Fq . . . 237

xiii

List of Symbols

Symbol Meaning

d·e The Ceiling function b·c The Floor function

∼= is isomorphic to

≡ is congruent to

< a > The principal ideal of a ringR generated by the elementa∈R gcd(a, b) The greatest common divisor of integers a and b

max{a, b} The maximum of real numbers a and b min{a, b} The minimum of real numbers a and b

lcm [a, b] The least common multiple of integers a and b a|b a divides b

a-b a does not divide b

`<sup>r</sup>||(q−1) r is the highest power of ` dividing q−1

R[x] The ring of all polynomials in xover the ring R

xv

xvi List of Symbols

deg f(x) The degree of the non-zero polynomial f(x) w_H The Hamming weight

Z<sup>`</sup> The residue class ring of integers modulo ` Fq The finite field of order q

F^∗q The multiplicative group of Fq

ξ A primitive element of Fq

C^⊥ The dual code of a linear code C ann(I) The annihilator of an ideal I

|A| Cardinality of the setA

O_n(q) The multiplicative order ofq modulo n φ The Euler’s phi function

Cs^(q,k) The q-cyclotomic coset modulo k containing the integer s