Codes on Euclidean Spheres (eBook)

T. Ericson, V. Zinoviev (Herausgeber)

eBook Download: PDF

2001 | 1. Auflage
564 Seiten
Elsevier Science (Verlag)
978-0-08-050216-8 (ISBN)

Infos

Codes on Euclidean spheres are often referred to as spherical codes. They are of interest from mathematical, physical and engineering points of view. Mathematically the topic belongs to the realm of algebraic combinatorics, with close connections to number theory, geometry, combinatorial theory, and - of course - to algebraic coding theory. The connections to physics occur within areas like crystallography and nuclear physics. In engineering spherical codes are of central importance in connection with error-control in communication systems. In that context the use of spherical codes is often referred to as coded modulation.

The book offers a first complete treatment of the mathematical theory of codes on Euclidean spheres. Many new results are published here for the first time. Engineering applications are emphasized throughout the text. The theory is illustrated by many examples. The book also contains an extensive table of best known spherical codes in dimensions 3-24, including exact constructions.

---

Codes on Euclidean spheres are often referred to as spherical codes. They are of interest from mathematical, physical and engineering points of view. Mathematically the topic belongs to the realm of algebraic combinatorics, with close connections to number theory, geometry, combinatorial theory, and - of course - to algebraic coding theory. The connections to physics occur within areas like crystallography and nuclear physics. In engineering spherical codes are of central importance in connection with error-control in communication systems. In that context the use of spherical codes is often referred to as "e;coded modulation."e;The book offers a first complete treatment of the mathematical theory of codes on Euclidean spheres. Many new results are published here for the first time. Engineering applications are emphasized throughout the text. The theory is illustrated by many examples. The book also contains an extensive table of best known spherical codes in dimensions 3-24, including exact constructions.

Inhalt

Cover 1
Contents 10
Chapter 1. Introduction 16
1.1 Definitions and basic properties 16
1.2 Examples of spherical codes 20
1.3 Two basic functions 27
1.4 The Rankin bounds 29
1.5 The Simplex and the Biorthogonal codes 32
1.6 The Chabauty–Shannon–Wyner bound 34
1.7 The direct sum 39
Chapter 2. The linear programming bound 42
2.1 Introduction 42
2.2 Spherical polynomials 43
2.3 The linear programming bound 54
2.4 Orthogonal polynomials 57
2.5 The Levenshtein bound 62
2.6 The Boyvalenkov–Danev–Bumova criterion 73
2.7 Properties of the Levenshtein bound 77
Chapter 3. Codes in dimension n=3 82
3.1 Introduction 82
3.2 The optimal codes 83
3.3 Additional comments 94
3.4 The Fejes Tóth bound 96
3.5 Optimality in the case M=7 101
3.6 The Coxeter–Böröczky extension 112
3.7 Thirteen spheres 113
Chapter 4. Permutation codes 122
4.1 Introduction 122
4.2 Variant 1 123
4.3 Best variant 1 codes 128
4.4 Variant 2a 131
4.5 Variant 2b 134
4.6 Dimensionality 136
4.7 Decoding 138
4.8 General comments 141
Chapter 5. Symmetric alphabets 144
5.1 Introduction 144
5.2 An introductory example 145
5.3 Binary labeling 149
5.4 The construction. 2 & #8805
5.5 The construction: general case 157
5.6 A simple example 164
5.7 Analysis 166
5.8 Explicit constructions 171
5.9 Unions 176
5.10 Extensions 184
5.11 Concluding remarks 190
Chapter 6. Non-symmetric alphabets 194
6.1 Introduction 194
6.2 The binary balanced mapping 194
6.3 Comments 197
6.4 Unions from the CW2-construction 198
6.5 Non-symmetric ternary alphabet 200
6.6 The general balanced construction 203
Chapter 7. Polyphase codes 210
7.1 Introduction 210
7.2 General properties 210
7.3 The case q = 3 212
7.4 The case q = 4 214
7.5 The case q = 6 215
7.6 The case q = 8 215
7.7 Two special constructions 216
7. 8 A general comment 217
Chapter 8. Group codes 220
8.1 Introduction 220
8.2 Basic properties 221
8.3 Groups represented by matrices 225
8.4 Group codes in binary Hamming spaces 228
8.5 Group codes from binary codes 233
8.6 Dual codes and MacWilliams' identity 238
8.7 Finite reflection groups 245
8.8 Codes from finite reflection groups 257
8.9 Examples 262
8.10 Remarks on some specific codes 267
Chapter 9. Distance regular spherical codes 272
9.1 Introduction 272
9.2 Association schemes 278
9.3 Metric schemes 290
9.4 Strongly regular graphs 300
9.5 The absolute bound 326
9.6 Spherical designs 329
9.7 Regular polytopes 339
Chapter 10. Lattices 352
10.1 Introduction 352
10.2 Lattices 352
10.3 The root lattices 359
10.4 Sphere packings and packing bounds 363
10.5 Sphere packings and codes 368
10.6 Lattices and codes 373
10.7 Expurgated constructions 377
10.8 The Leech lattice 380
10.9 Theta functions 382
10.10 Spherical codes from lattices 386
10.11 Theta functions for expurgated constructions 393
10.12 Unions of shells 397
Chapter 11. Decoding 404
11.1 Introduction 404
11.2 The problem 405
11.3 Preliminaries 406
11.4 Generalized minimum distance decoding 410
11.5 The Chase decoder 415
11.6 Parallel decoding 419
11.7 Decoding Y3 424
Appendix A. Algebraic codes and designs 432
Appendix B. Spheres in R n 454
Appendix C. Spherical geometry 458
Appendix D. Tables 466
D.1 Introduction 466
D.2 Notation 467
D.3 Spherical codes of dimension n = 3 470
D.4 Spherical codes of dimension n = 4 471
D.5 Spherical codes of dimension n = 5 471
D.6 Spherical codes of dimension n = 6 472
D.7 Spherical codes of dimension n = 7 475
D.8 Spherical codes of dimension n = 8 478
D.9 Spherical codes of dimension n = 9 480
D.10 Spherical codes of dimension n = 10 483
D.11 Spherical codes of dimension n = 11 487
D.12 Spherical codes of dimension n = 12 490
D.13 Spherical codes of dimension n = 13 492
D.14 Spherical codes of dimension n = 14 495
D.15 Spherical codes of dimension n = 15 498
D.16 Spherical codes of dimension n = 16 500
D.17 Spherical codes of dimension n = 17 503
D.18 Spherical codes of dimension n = 18 507
D.19 Spherical codes of dimension n = 19 512
D.20 Spherical codes of dimension n = 20 516
D.21 Spherical codes of dimension n = 21 521
D.22 Spherical codes of dimension n = 22 523
D.23 Spherical codes of dimension n = 23 527
D.24 Spherical codes of dimension n = 24 532
Bibliography 534
Index 556

Textauszug

Chapter 2

The linear programming bound

Thomas Ericson; Victor Zinoviev    North-Holland

2.1 Introduction

The best upper bounds for codes are usually those obtained from linear programming techniques. The basic idea belongs to Delsarte [79]. The particular case of spherical codes was developed in successive steps by Delsarte–Goethals–Seidel [81], [82], Kabatianskii–Levenshtein [140], Levenshtein [155], [156], [157], Boyvalenkov [42], [43] and Boyvalenkov–Danev–Bumova [45]. The most explicit result, which we shall refer to as the Levenshtein bound, was obtained by Levenshtein [155], [156], [157].

The linear programming bound is largely based on the theory of orthogonal polynomials. The bound is expressed in terms of so called Gegenbauer polynomials. These polynomials are orthogonal with respect to a certain inner product, which is defined in terms of a weighted integral over the interval [− 1, 1]. They are also related to so called spherical polynomials, which are multi-variate polynomials defined on the unit sphere Ωn. The key feature for our purposes is the fact that the Gegenbauer polynomials are positive definite. This property is a simple consequence of the addition formula, which is the bridge between Gegenbauer polynomials and spherical polynomials.

In order to derive the linear programming bound we need first to offer precise definitions to the above concepts and to establish a few facts about the polynomials occurring in the theory. All these results are classical, [1], [7], [17], [37], [195], [191].

2.2 Spherical polynomials

Let f(x) be a polynomial of the real variables x1, x2, …, xn. We usually collect the variables xi in a vector x = (x1, x2, …, xn) · We will be interested in polynomials evaluated on the unit sphere Ωn. This means that two polynomials f(x) and g(x) such that f(x) = g(x) for all x ∈ Ωn will be regarded as identical elements. The equivalence class of all polynomials taking the same value for all x ∈ Ωn will be referred to as a spherical polynomial. The set of all spherical polynomials over Ωn will be denoted Pol(n).

For any integer vector u = (u1, u2, …, un) with nonnegative components ui the special polynomial xu is defined as

u≜∏i=1nxiui.

A polynomial of this form is called a monomial. The sum deg(xu) u1 + u2 + · · · + un is called the degree of the monomial xu.

A polynomial f(x) is a linear combination of monomials:

x=∑ufuxu.

  (2.2.1)

An expression of the form (2.2.1) will also be referred to as a monomial expansion. If f(x) is interpreted as a polynomial over n its monomial expansion is unique. In that case the degree of f(x) is defined as the largest of the degrees of the monomials in its monomial expansion. For spherical polynomials, however, the monomial expansion is not unique. For a spherical polynomial we define the degree as the smallest of the degrees in sense of polynomials over n of any of the polynomials in the corresponding equivalence class.

We denote by Pol(n, k) the set of all spherical polynomials f(x) of degree k or less. It is clear that Pol(n, k) is a linear space. Our first concern will be to determine the dimension of this space.

A spherical polynomial f(x) ∈ Pol(n, k) is said to be homogeneous if it can be expressed as a sum of monomials, all of the same degree. We denote by Hom(n, i) the set of all spherical polynomials which can be represented as homogeneous polynomials of degree i.

We notice that Hom(n, i − 2) is a subspace in Hom(n, i). Moreover, Hom(n, i) is a subspace in Pol(n, k) for any i ≤ k. The following lemma holds.

Lemma 2.2.1

Pol(n, k) = Hom(n, k) ⊕ Hom(n, k − 1).

Proof: Consider the general expansion (2.2.1). Any monomial xu is an element in Hom(n, i), where i = deg (xu). If i < k − 1, let us replace xu with xu‖x‖2s, where the nonnegative integer s is selected such that k − 1 ≤ 2 s + i ≤ k. Regarded as functions over Ωn the polynomials xu and xu‖x‖2s are the same. It follows that it is always possible to express f(x) as a linear combination of elements in Hom(n, k) and Hom(n, k − 1). Conversely, any such linear combination is obviously an element in Pol(n, k). Moreover, it is also easy to see that any polynomial f(x) ∈ Pol(n, k) has a unique representation in the form f(x) = g(x) + h(x), where g(x) ∈ Hom(n, k) and h(x) ∈ Hom(n, k − 1). This completes the proof.

It is now easy to determine the dimension of the space Pol(n, k). We first observe that the monomials xu of degree k are linearly independent and span Hom(n, k). Thus, the dimension of the linear space Hom(n, k) equals the number of vectors u = (u1, u2, …, un) with nonnegative integer components adding to k. This number is well known and is given by -1+kk. Combining this observation with Lemma 2.2.1 we obtain

Lemma 2.2.2

dim⁡Polnk=n−1+kk+n−2+kk−1.

  (2.2.2)

For k > 2 let φ : Hom(n, k) → Hom(n, k − 2) be a surjective homomorphism with kernel ker(φ). Notice that the image Im (φ) = Hom(n, k − 2) is also a subspace in Hom(n, k). It follows that the kernel is independent of φ and that we always have Hom(n, k) ≅ ker(φ) ⊕ Hom(n, k – 2). It can be shown that the laplacian operator is a surjective homomorphism of this kind. Therefore the elements in the kernel are usually referred to as harmonic polynomials, and therefore the kernel is usually denoted Harm(n, k). Although the laplacian operator itself plays no role in our theory we will follow the conventional terminology. For k = 0 we define Harm(n, 0) = < 1 > and for k = 1 we define Harm(n, 1) = < x1, …, xn >. We have

omnk=Harmnk⊕Homn,k−2,k≥2.

  (2.2.3)

It follows that any spherical polynomial f(x) ∈ Pol(n, k) has a unique representation as a sum of harmonic polynomials. We state this important result as a theorem.

Theorem 2.2.1

The polynomial space Pol(n, k) is a direct sum of the polynomial spaces Harm(n, i), i = 0,1, …, k:

olnk=⊕i=0kHarmni.

  (2.2.4)

Let rk denote the dimension of...

Produkt-Details

• Erscheint lt. Verlag: 27.4.2001
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Arithmetik / Zahlentheorie
• Themenwelt: Mathematik / Informatik ► Mathematik ► Geometrie / Topologie
• Themenwelt: Technik
• ISBN-10: 0-08-050216-4 / 0080502164
• ISBN-13: 978-0-08-050216-8 / 9780080502168