Introduction to Algebraic Coding Theory

The following sections are included:

• Dedication
• Preface
• About the Author
• Contents
• Introduction

The following sections are included:

• Real Curve Codes
• Preliminaries
• Vector Space Codes
• Distances
• Maximum Likelihood Decoding
• Dual Codes
• Hamming Code
• Shannon’s Theorem
• Gilbert–Varshamov’s Bound

If we treat letters as unrelated symbols, then we have information theory which cannot correct any error. If we treat sequences of letters as vectors in a vector space, then we have Hamming codes which can correct one error. Naturally, we are interesting in codes which may correct multiple errors. Therefore, we are very likely to involve more algebraic relations. Furthermore, it follows from Shannon’s Theorem that we may have to work with long codes to make better codes. However, a long code will introduce complexity for decoding. To overcome this complexity, we have to assume more algebraic structures to help us…

From now on, we shall fix the ground field F_q. A linear code is defined by a subspace C of an n-dimensional vector space $F_q^n$. Note that for the purpose of decoding, we shall have more (algebraic) relations between the vectors in the words space. Naturally, there shall be multiplicative relations between the vectors in the words space. It means that we shall consider ring structures. A simple ring is F_q[x]/(f (x)). It is easy to see that $F_q^n$ can be represented by F_q[x]/(f (x)) for any polynomial f (x) of degree n. In this representation, we have the multiplicative structure of a ring other than the additive structure of a vector space. We shall study the concepts of coding theory in the context of the ring F_q[x]/(f (x)). To make our work easier, we shall later select a good f (x) for coding purposes. We have the following definition to begin with…

In the last chapter, we discussed the Reed–Solomon codes, which are used to evaluate a polynomial of degree at most k − 1 at n(≥ k) points in the ring of polynomials F_q[x], where F_q is a field with q elements. We see that it is equivalent to evaluate L(D) on $P_{F_q}^1$ (see Example 1 of Section 5.1) with D = nP_∞ (see Section 4.3). Similarly, classical Goppa code can be considered as a code over $P_{F_q}^1$. We may extend the concept of Reed– Solomon codes and classical Goppa codes to codes over any projective smooth curve (instead of lines only). The Riemann–Roch theorem induces a richer algebraic structure, and the corresponding codes will be more useful…

The following sections are included:

• Geometric Goppa Codes
• Comparisons with Reed–Solomon Code
• Improvement of Gilbert–Varshamov’s Bound

The following sections are included:

• Introduction
• Error Locator
• SV Algorithm
• DU Algorithm
• Feng–Rao’s Majority Voting

The following sections are included:

• Appendix A Convolution Codes
  • Representation
  • Combining and Splitting
  • Smith Normal Form
  • Viterbi Algorithm
• Appendix B Sphere-Packing Problem and Weight Enumerators
  • Golay Code
  • Uniformly Packed Code
  • Weight Enumerators
• Appendix C Other Important Coding and Decoding Methods
  • Hadamard Codes
  • Reed–Muller Code
  • Constructing New Code from Old Codes
  • Threshold Decoding
  • Soft-Decision Decoding
  • Turbo Decoder
  • Low-Density Parity Check (LDPC) Codes
• Appendix D Berlekamp’s Decoding Algorithm
  • Berlekamp’s Algorithm

The following sections are included:

• References
• Index