bch code generator matrix , Golay Codes , Bose Chaudhuri Hocquenghem (BCH) Codes :-
Golay Codes
The (23, 12) Golay code is a very special type of binary code. This code is capable of correcting any combination of three or less than three random errors in the block of 23 bits. The number of message bits out of 23 is 12. This code has a minimum distance of 7. It satisfies the Hamming bound for t = 3. The (23, 12) Golay code is the only known code which is capable of correcting three errors.
The (23, 12) Golay code is generated by one of the following two polynomials :
g1(p) = 1 + p2 + p4 + p5 + p6 + p10 + p11
or g2(p) = 1 + p + p5 + p6 + p7 + p9 + p11
In fact, both, g1(p) and g2(p) are factors of 1 + p23.
Thus, (1 + p23) = (1 + p) g1 (p) g2(p)
10.15.2. Bose-Chaudhuri-Hocquenqhem (BCH) Codes
BCH codes are one of the most important and powerful linear block codes. The BHC codes are cyclic codes with a wide variety of parameters. The most common BCH codes are characterized as under:
For any positive integer m (with m ≥ 3) and t < (2m – 1)/2, there exists a BCH code with the following parameters :
Block length : n = 2m – 1
Number of message bits : h > n – m t
Minimum distance : dmin ≥ 2t + 1
This type of BCH codes is called as primitive BCH codes. Each BCH code can correct t number of errors. This means that it can detect and correct upto t random errors per codeword. The Hamming codes with a single error correcting capability is a BCH code. The block lengths and code rates of BCH codes are variable. In that sense they provide a high flexibility. For block lengths of a few hundred, the BCH codes are among the best known codes of the same block length and code rate.
Generator polynomials of BCH codes
Table 10.17 presents the code parameters and generator polynomials for the binary BCH codes of length upto 25 – 1.
Table 10.17. Binary BCH codes of length upto 25 – 1.
| n | k | t | Generator Polynomial |
| 7 | 4 | 1 | 1 011 |
| 15 | 11 | 1 | 1 10 011 |
| 15 | 7 | 2 | 111 010 001 |
| 31 | 26 | 1 | 100 101 |
| 31 | 21 | 2 | 11 101 101 001 |
| 31 | 16 | 3 | 000 111 110 101 111 |
| 31 | 11 | 5 | 101 100 010 011 011 010 101 |
| 31 | 6 | 7 | 11 001 011 011 110 101 000 100 111 |
where n = block length
k = number of message bits
t = Maximum number of detectable errors
10.15.3. How to use table 10.17
Let us consider that we want to construct the generator polynomial for (15, 7) BCH code, then we refer to the third row of Table 10.17. The generator polynomial from the third row is given by
111 010 001
Hence, the generator polynomial is given by
g(p) = p8 + p7 + p6 + 0p5 + p4 + 0p3 + 0p2 + 0p + 1
or g(p) = p8 + p7 + p6 + p4 + 1 Ans.
10.15.4. Reed-Solomon codes (R-S Codes)
The Reed-Solomon codes are named after their inventors Reed and Solomon. The R-S codes are an important subclass of nonbinary BCH codes. The encoder for an RS code differs from a binary encoder. This encoder operates on multiple bits rather than the individual bits.
For example, the encoder for an RS (n, k) code on m symbols will group the incoming binary data stream into blocks. Each blocks is km bits long. Each block is considered as k number of symbols, with each symbol having m bits. The encoding algorithm then expands a block of k symbols to n symbols by adding
(n – k) redundant symbols. When m is an integer power of two, the m-bit symbols are called bytes.
In practice, the most popular value of m is 8. The RS code with m = 8 is extremely powerful. The parameters of a t – error correcting R-S code may be listed as under :
Block length : n = 2m – 1 symbols
Message size : k symbols
Parity check size : n – k = 2t symbols
Minimum distance : dmin = (2t + 1) symbols
Thus, the block length of the RS code is one less than the size of a code symbol and the minimum distance is always one greater than the number of parity symbols. It can be shown that no (n, k) linear block code can have a minimum distance greater than (n – k + 1). The (n, k) linear block code with a minimum distance equal to (n – k + 1) is called as maximum distance separable code. Hence, every RS code is maximum distance separable code.
Advantages of R-S codes
(i) The RS codes make the highly efficient use of redundancy.
(ii) It is possible to adjust the block lengths and the symbol sizes, to accommodate a wide range of message sizes.
(iii) The R-S codes provide a wide range of code rates. The code rate can be chosen to obtain the optimum performance.
(iv) The efficient decoding techniques are available for decoding the RS codes.
10.16 CONVOLUTIONAL CODES
The main difference between the block codes and the convolutional (or recurrent) codes may be listed as under :
(i) Block codes
In block codes, the block n bits generated by the encoder in a particular time slot depends only on the block of k message bits within that time slot.
(ii) Convolutional code
In the convolutional codes, the block of n bits generated by the encoder in a time slot depends not only on the k message bits within that time slot, but also on the preceding blocks of the message bits (L > 1). Generally, the values of k and n will be small.
Applications of convolutional code
Like block codes, the convolutional codes can be designed to either detect or correct errors. However, because data is usually retransmitted in blocks, the block codes are more suitable for error detection and the convolutional codes are more suitable for error correction.
Encoding and decoding
Encoding of the convolutional codes can be accomplished using simple shift register. Several practical methods have been developed for decoding. The convolutional codes perform as well or better than the block codes in many error control applications.
10.16.1. Encoder for Convolutional Coding
The fundamental hardware unit for the convolutional encoding is a taped shift register with (L + 1) stages, as shown in figure 10.47. Here, g0, g1 …… etc. are the tap gains which are nothing but binary digits 0s or 1s. A tap gain of 0 represents an open circuit whereas a tap gain of 1 represents a short circuit.
diagram
FIGURE 10.47 Block diagram of a general convolutional encoder.
The message bits enter one by one into the tapped shift register, which are then combined by mod-2 addition to form the encoded bit x.
Therefore, we have x = mL gL Å ……….. Å m1 g1 Å m0g0 …(10.49)
or equation
The name convolutional encoding comes from the fact that equation (10.49) has a form of binary convolution which analogous to the convolutional integral. The message bit m0 in figure 10.47 represents the current input whereas the bits m1, to mL represent the past input or state of the shift register. From equation (10.49), it is clear that a message bit x depends on the current message bit m0 and the state of the shift register defined by the previous L message bits.
Important Point
It is important to note that a particular message bit influences a span of L + 1 successive encoded bits as it shift through the register.
16.2. Practical Convolutional Encoder
DIAGRAM
FIGURE 10.48. Convolutional encoder with n = 2, h = 1 and L = 2.
To provide an extra bit needed for error control, a complete convolutional encoder must generate output bits at a rate greater than the message bit rate rb. This is achieved by using two or more mod-2 address to the registers as shown in figure 10.48, and interleaving the encoded bits via the cummulator switch.
The convolutional encoder of figure 10.48 is for n = 2, k = 1 and L = 2. It therefore genera n = 2 encoded bits as under :
x = m0 Å m1 Å m2
and x2 = m0 Å m2 …(10.50)
The commutator switch the selects these encoded bit alternately to produce the stream of encoded bits as under :
X = x1 x2 xl‘ x2‘ x1” x2” …(10.51)
The output bit rate is twice that of the input bit rate i.e., rb.
Important Point
It may be noted that here unlike a block code, the input bits have not been grouped into words. Instead, each message bit influences a span of n (L + 1) = 6 successive output bits.