Mathematics of Coding Theory : Information, Compression, Error Correction, and Finite Fields

by Garrett, Paul

• ISBN13: 9780131019676
• ISBN10: 0131019678
• Edition: 1st
• Format: Paperback
• Copyright: 2003-11-19
• Publisher: Pearson
• More Book Details
• Purchase Benefits

Summary

This book makes a very accessible introduction to a very important contemporary application of number theory, abstract algebra, and probability. It contains numerous computational examples throughout, giving learners the opportunity to apply, practice, and check their understanding of key concepts.KEY TOPICSCoverage starts from scratch in treating probability, entropy, compression, Shannon¿s theorems, cyclic redundancy checks, and error-correction.For enthusiasts of abstract algebra and number theory.

Table of Contents

Probability

Counting

Preliminary Ideas of Probability

More Formal View of Probability

Random Variables, Expected Values, Variance

Markov Inequality, Chebycheff Inequality

Law of Large Numbers

Information and Entropy

Uncertainty, Acquisition of Information

Entropy

Uniquely-Decipherable and Prefix Codes

Kraft and Macmillan Inequalities

Noiseless Coding

Noiseless Coding Theorem

Huffman Coding

Noisy Coding

Noisy channels

Example: Parity Checks

Decoding from a Noisy Channel

Channel Capacity

Noisy Coding Theorem

Cyclic Redundancy Checks

The Finite Field GF(2) with 2 Elements

Polynomials over GF(2)

Cyclic Redundancy Checks (CRC's)

What Errors Does a CRC Catch?

6

Reduction Algorithm

Divisibility

Factorization into Primes

Euclidean Algorithm

Integers Modulo M

The Finite Field Z/P for P Prime

Fermat's Little Theorem

Primitive Roots

Euler's Criterion

Fast Modular Exponentiation

Finite Fields

Making Fields

Examples of Field Extensions

Addition Modulo P

Multiplication Modulo P

Multiplicative Inverses Modulo P

Primitive Roots

Polynomials

Polynomials with Coefficients in a Field

Divisibility

Factoring and Irreducibility

Euclidean Algorithm

Unique Factorization

Introduction to Linear Codes

An Ugly Example

The Hamming Binary [7,4] Code

Some Linear Algebra

A Review of Row Reduction

Definition: Linear Codes

Syndrome Decoding

Berlekamp's Algorithm

Bounds for Codes

Hamming (Sphere-Packing) Bound

Gilbert-Varshamov Bound

Singleton Bound

Cyclic Codes

Minimum Distance in Linear Codes

Cyclic Codes

Primitive Roots

Characteristics of Fields

Multiple Factors in Polynomials

Cyclotomic Polynomials

Primitive Roots in Finite Fields

Primitive Roots Modulo Prime Powers

Counting Primitive Roots

Non-Existence

An Algorithm to Find Primitive Roots

Primitive Polynomials

Definitions

Examples Modulo 2

Testing for Primitivity

Example: Periods of LFSR's

Example: Two-Bit Errors Detected by CRC's

Basic Linear Codes

Vandermonde Determinants

More Check Matrices for Cyclic Codes

RS Codes

Hamming Codes (Again)

BCH Codes

Decoding BCH Codes

Concatenated Codes

Mirage Codes

Concatenated Codes

Justesen Codes

Some Explicit Irreducible Polynomials

Curves and Codes

Plane Curves

Singularities of Curves

Projective Plane Curves

Curves in Higher Dimensions

Genus, Divisors, Linear Systems

Geometric Goppa Codes

Tsfasman-Vladut-Zink Bound

Appendices

Sets and functions

Equivalence Relations

Stirling's Formula

Bibliography

Index

Table of Contents provided by Publisher. All Rights Reserved.

Excerpts

This book is intended to be accessible to undergraduate students with two years of typical mathematics experience, most likely meaning calculus with a little linear algebra and differential equations. Thus, specifically, there is no assumption of a background in abstract algebra or number theory, nor of probability, nor of linear algebra. All these things are introduced and developed to a degree sufficient to address the issues at hand.We will address the fundamental problem oftransmitting information effectively and accurately.The specific mode of transmission does not really play a role in our discussion. On the other hand, we should mention that the importance of the issues of efficiency and accuracy has increased largely due to the advent of the internet and, even more so, due to the rapid development of wireless communications. For this reason it makes sense to think of networked computers or wireless devices as archetypical fundamental practical examples.The underlying concepts ofinformationandinformation contentof data make sense independently of computers, and are relevant in looking at the operation ofnatural languagessuch as English, and of other modes of operation by which people acquire and process data.The issue ofefficiencyis the obvious one: transmitting information costs time, money, and bandwidth. It is important to use as little as possible of each of these resources.Data compressionis one way to pursue this efficiency. Some well known examples of compression schemes are commonly used for graphics: GIFs, JPEGs, and more recently PNGs. These clever file format schemes are enormously more efficient in terms of filesize than straightforward bitmap descriptions of graphics files. There are also general-purpose compression schemes, such asgzip, bzip2, ZIP,etc.The issue ofaccuracyis addressed bydetectionandcorrectionof errors that occur during transmission or storage of data. The single most important practical example is the TCP/IP protocol, widely used on the internet: one basic aspect of this is that if any of thepacketscomposing a message is discovered to be mangled or lost, the packet is simplyretransmitted.The detection oflostpackets is based on numbering the collection making up a given message. The detection of mangled packets is by use of 16-bitchecksumsin theheadersof IP and TCP packets. We will not worry about the technical details of TCP/IP here, but only note thatemailand many other types of internet traffic depend upon this protocol, which makes essential use of rudimentary error-detection devices.And it is a fact of life that dust settles on CD-ROMs, static permeates network lines, etc. That is, there isnoisein all communication systems. Human natural languages have evolved to include sufficientredundancyso that usually much less than 100% of a message need be received to be properly understood. Such redundancy must bedesignedinto CD-ROM and other data storage protocols to achieve similar robustness.There are other uses for detection ofchanges in data:if the data in question is the operating system of your computer, a change not initiated by you is probably a sign of something bad, either failure in hardware or software, or intrusion by hostile agents (whether software or wetware). Therefore, an important component ofsystems securityis implementation of a suitable procedure to detect alterations in critical files.In pre-internet times, various schemes were used to reduce the bulk of communication without losing the content: this influenced the design of the telegraphic alphabet, traffic lights, shorthand, etc. With the advent of the telephone and radio, these matters became even more significant. Communication with exploratory spacecraft having very limited resources available in deep space is a dramatic