Bose–Chaudhuri–Hocquenghem (BCH) code: (15, 5, 7) and C Implementation Using the Octave GNU Tool
1. Abbreviation
2. Introduction
This article is a continuation of the article: “Hamming Code and C Implementation Using the Octave GNU Tool” and “Hadamard Codes and C Implementation Using the Octave GNU Tool”. This article will review the BCH (15,5,7) code which can correct up to three errors in a code word.
Now I will repeat the important coding provisions that will be required in the following description.
It is necessary often to ensure reliable data transmission or storage in Digital Signal Processing applications. Data will be understood messages (code words) containing zeros (0) and ones (1), that is binary data. Additional parity bits create differences between the data (code words). To estimate the difference between the codes, Hamming introduced a code distance. For example, there are two messages:
These two code words differ in four positions (see italics). The number of differences between binary messages is called the Hamming code distance. A theorem is known that is used to create self-correcting codes. If there is a set of code words with a Hamming distance: d = 2t +1. Then this code can correct t-errors that occur during data transmission or storage. The proof of this theorem can be seen in [1]. For example, Hamming codes have a code distance of 3, which a single error is corrected, and extended Hamming codes have a code distance of 4, which a single error is corrected and a double error is detected.
Code words can be interpreted as vector coordinates and treated as a vector space.
Next we will use the following notation for the code: (n,k,d), where
BCH code is a linear cyclic code with error control. The cyclic code can be set using the generator polynomial g(x). The BCH (15,5,7) correctes three errors (t = (7 – 1) / 2 = 3 ). The generator polynomial g(x) has coefficients 0 or 1 from the Galois field GF(2) and the roots of the polynomial belong to the Galois field GF(16). The length of the code is determined by the order of the primitive element GF(16) and is equal to n=15.
Notes:
-
The Galois field GF(16) is constructed on the basis of a primitive polynomial:
-
Primitive element α=x=2 of the GF(16) has order 15. See the Table 2-1:
Table 2-1: GF(16): Representation of various degrees of a primitive α element
The roots of the generator polynomial g(x) for BCH code with correction of t errors are selected using the primitive element of the corresponding Galois field:
In our case BCH (15,5,7), to correct three errors t = 3, the roots of the generator polynomial g(x) take values:
To obtain a generator polynomial with coefficients from GF(2), it is necessary to add all conjugate roots of the form:
to each root of (12), taking into account the order of the primitive element from Table 2-1:
Discarding the same polynomials (with the same roots) from (13):
Now let’s make up polynomials with roots (14):
The generator polynomial g(x) for BCH (15,5,7) is defined as the least common multiple for the polynomials (15), (16), (17):
Notes:
-
The degree of the generator polynomial g(x) determines the number of parity (check) bits in the message and from (18): n – k = 10. Given that n = 15, then the number of information bits: k = n – 10 = 15 – 10 = 5. Thus using the generator polynomial (18), it is possible to generate the code BCH (15,5,7)
-
The coefficients of the polynomials take the values 0 or 1 of GF(2)
-
The operations of addition, subtraction, multiplication and division with polynomials use Modular Arithmetic modulo 2
-
The addition and subtraction operations correspond to the XOR operation:
and multiplications and divisions correspond to the AND operation:
For example:
-
See the [1] for more information about Galois fields, cyclic codes, and the choice of generator polynomials
3. BCH Code (15,5,7) Using Polynomials
First the polynomials u(x) are prepared, which use information bits as coefficients. Next the polynomials c(x) = u(x)*g(x) are calculated. The coefficients of the polynomial c(x) will be the desired code words. See table 3-1:
Table 3-1: BCH Code (15,5,7) with Generator Polynomial g(x) = x^10 + x^8 + x^5 + x^4 + x^2 + x + 1
Note:
-
The Table 3-1 contains 32 BCH code words (15,5,7). See the last column of the table. All calculations are given in BCH_Code.m
-
The received code word is correct if the corresponding polynomial is divisible by the generator polynomial g(x) without remainder. For example: position 22 of the code word is 0x4DC2 from Table 3-1 with the corresponding polynomial: x^14 + x^11+ x ^10 + x^8 + x^7 + x^6 + x is divisible by (18) without remainder. See the Figure 3-1:
Figure 3-1: 0x4DC2 is divided by g(x) without remainder
The quotient x^4 + x^2 + x corresponds to the information code:
4. Generator Matrix G and Parity-Check Matrix H of the BCH (15,5,7)
BCH (cyclic) codes are linear codes. Linear codes can be represented in matrix form: the generator matrix G with dimension (k) x (n) and the check matrix H with dimension (n-k) x (n).
The code words are created from information codes using the generator matrix G:
If the generator polynomial is known:
then the generator matrix has the form:
The syndrome is calculated using the check matrix H. If the received code word x contains no errors, then the syndrome must have a null string:
If the check polynomial is known:
Then the check matrix has the form:
Now let’s go back to BCH (15,5,7) and calculate the matrices G and H. Using the generator polynomial (18) the generator matrix G:
Let’s calculate the check polynomial h(x) for BCH (15,5,7) using the formula:
then the verification matrix H:
If G and H are chosen correctly, then the equality is fulfilled:
where the null matrix has dimension (k) x (n-k). You can check the (28) for BCH (15,5,7) code yourself.
Using the generator matrix (25), the code words BCH (15,5,7) are calculated. The results are shown in Table 4-1:
Table 4-1: BCH Code (15,5,7) with Generator Matrix G
Notes:
-
All calculations with the generator matrix G are given in BCH_Code.m
-
Both methods: polynomial and matrix, given in Table 3-1 and Table 4-1, lead to the same result
-
The calculations use Modular Arithmetic modulo 2
-
The matrix (25) has a non standard (non systematic) form and it is difficult to extract the u information bits from the BCH code. It is more convenient in this case to work with the message number
-
The formula is correct for the check polynomial h(x):
For example, let’s take the code word: 0x4DC2 with polynomial: x^14 + x^11 + x^10 + x^8 + x^7 + x^6 + x and the check polynomial (26). Then:
The resulting polynomial must be divisible without remainder by a polynomial (x^15 – 1):
Figure 4-1: c(x)*h(x) is divided by (x^15 – 1) without remainder
The quotient x^4 + x^2 + x corresponds to the information code:
5. Conclusions for BCH Code (15,5,7)
-
BCH Code (15,5,7) with 2^5=32 code words and Hamming Distance 7 is allowed to fix((7-1)/2) = 3 errors in the code word
-
If there are more than 3 errors in the code word of BCH (15,5,7), then the algorithm leads to incorrect corrections
-
It follows from the previous point that the use of BCH codes (15,5,7) is limited to 3 errors. If there is a high probability of more than 3 errors in the code word, then in this case codes with a greater Hamming distance should be used and allowing the necessary number of errors to be corrected
-
Often messages consisting of only zeros or ones are excluded from the list of BCH Code messages. This is due to the fact that in cases of a reception failure, the system mistakenly accepts a message consisting of zeros or ones
-
If the received messages contain errors, then dividing the message polynomial by the generator polynomial g(x) leads to a non-zero remainder or calculating the syndrome using the check matrix H gives a non-zero syndrome. In this case a system of equations is compiled, the solution of which is allowed to determine the numbers of erroneous bits and correct them. The BCH code (15,5,7) has only 2^5 = 32 code words and in the BCH_Code.c/h the minimum Hamming distance of the received message is searched with patterns from the BCH list (15,5,7). The code word from the list with the minimum Hamming distance from the received code is accepted as a valid message
-
See also the BCH_Code.m/c/h and [1]
6. Octave GNU file BCH_Code.m
The script generates and tests the BCH Code: (15,5,7)
% Hamming Distance between two Messages: Input and Pattern
% Input parameters:
% InMessage – input message
% PatternMessage – pattern message list
% MessageLength – message length in bits
% Output parameters:
% DistanceValue – Hamming distance
function DistanceValue = MessageCompare(InMessage, PatternMessage, MessageLength)
% Receiving the message
% Input parameters:
% InMessage – input message
% WordMessageList – message list
% MessageLength – message length in bits
% Output parameters:
% Distance – min Hamming distance
% MessageNmb – number of the message in the WordMessageList
% MessageValue – message value
function [Distance MessageNmb MessageValue] = ReceivingMessage(InMessage, WordMessageList, MessageLength)
% Hamming Distance In Message List
% Input parameters:
% MessageList – message list
% MessageLength – message length in bits
% Output parameters:
% MinHammingDistance – min Hamming distance
% MaxHammingDistance – max Hamming distance
function [MinHammingDistance MaxHammingDistance] = DistanceInMessageList(MessageList, MessageLength)
% Code Generator with Polynomial
% Input parameters:
% Polynomial – vector of the polynomial coefficients
% MessageLength – message length in bits <= 64
% Output parameters:
% BitMessageList – bit message array
% WordMessageList – word message array
function [BitMessageList WordMessageList] = CodeGeneratorPolynomial(Polynomial, MessageLength)
% Code Generator with Matrix
% Input parameters:
% GeneratorMatrix – generator matrix k x n
% MessageLength – message length in bits
% InfoLength – information bit number
% Output parameters:
% BitMessageList – bit message array
% WordMessageList – word message array
function [BitMessageList WordMessageList] = CodeGeneratorMatrix(GeneratorMatrix, MessageLength, InfoLength)
% Hex Integer Table to File
% Support C-Code
% Input parameters:
% ParameterVector – data array
% FileNameString – output file name
function HexIntegerParamVector2file(ParameterVector, FileNameString)
7. C Language BCH_Code.c/h
Supports the BCH Code: (15,5,7)
/*
Hamming Distance between code1 and code2
Input
uint16 code1
uint16 code2
Return
uint8 – Hamming Distance
*/
uint8 HammingDistance(uint16 code1, uint16 code2)
/*
Receiving the BCH message
Input
uint16 code – input message
receiving_message_t* ptr_result – pointer on the receiving result
Return
void
*/
void ReceivingMessage(uint16 code, receiving_message_t* ptr_result)