BCH Codes

Abstract:

Coding Theory deals with transmission of data over noisy channels. When transmitting digital data, which consists of strings of 0's and 1's, a physical device may for a number of reasons confuse these entries. For example, the Voyager II space probe which explored Jupiter in the late 1960's was transmitting data across many millions of miles with incredibly low power. When the information reached earth its easy to see how there could be errors in the data string received, either from bursts of cosmic energy or by amplification of the weak signal. To make this communication possible there needed to be a method of detecting errors in the transmission and correcting them. The process that made this possible is known as the Reed-Solomon codes. These codes are a specific type of code called a BCH code. These are the structures we wish to explore here.

Background

To understand BCH codes we must understand the basics of cyclic codes, an important class of codes in which the BCH codes dwell. Here are some important definitions about codes in general.

Definition 1   Given a code ,the entire set of codewords is called the codespace.

The strings, or -tuples, of 0's and 1's in the data transmission are called the codewords. Here, we will generally restrict our attention to binary BCH codes. So we can then think of each codeword as an -dimensional vector over the field .

The value of a code depends on the ability to detect and correct errors in a transmission. This process is called decoding. To decode a message we often use a matrix.

Definition 2   The check matrix is the decoding function of a code .

A received message is multiplied by the check matrix. We will see a specific example of a check matrix when we discuss decoding a BCH code. For now, we can define the product of the received message and the check matrix.

Definition 3   The syndrome is the vector obtained after multiplying the received message by the check matrix. The length of the syndrome vector will determine how many errors a given BCH code can correct.

The bounds for error detection and correction depend on the distance between vectors in the codespace of .

Definition 4   Take two codewords in the codespace. The Hamming distance is the number of places where the two vectors differ.

For example, using binary the vectors and , the distance between is . It turns out that we can determine a lower bound on how close two vectors in the codespace can be. This bound will determine exactly how many errors a code can detect and correct. In fact we have the following theorem.

Theorem 1   Let be the minimum distance between two codewords in the codespace. Then a code can detect up to errors if . Further, a code can correct up to errors if .

Definition 5   The Hamming weight of a vector in the codespace is definied to be .

In other words, it is the number of nonzero places in the codeword. With these basic definitions we are ready to define the cyclic class of codes.

Linear and Cyclic Codes

Cyclic codes fall under the category of codes called linear codes.

Definition 6   A linear code of dimension and length over a field is a -dimensional subspace of . Such a code is called an code. If the minumum distance of the code is , then the code is called an code.

The row-space of the following matrix forms a code.

Notice that there are 4 ones in each row.

Any binary n-vector can be thought of as the coeffiecients of an degree polynomial in . Looking at the first row in the matrix we can relate it to the polynomial 需要全部内容的请联系QQ3249114，转发请注明出处www.751com.cn in the polynomial ring .

Given a linear code the following proposition is clear.

Proposition 1   Let be a linear code. Then equals the smallest Hammming weight of all nonzero code vectors.

There are many different varieties of linear codes, such as the well known Hamming codes. We now want to consider a brand of linear codes called cyclic codes. Then we will define BCH codes, which are a specific type of cyclic code

 << 上一页  [11] [12] [13] [14] [15] 下一页