I have to implement a BCH error-correcting code. I have found some codes in Python BCH library Python and MATLAB BCH encoder in MATLAB. However, codes have different performance, BCH(127,70) in Python can correct up to 70 bitflips in a block size of 127. However, the MATLAB code can correct up to only 15 bits in 127 bits in BCH(127,15).
Why do these implementation perform differently?
Python Code
import bchlib
import hashlib
import os
import random
# create a bch object
BCH_POLYNOMIAL = 8219
BCH_BITS = 72
bch = bchlib.BCH(BCH_POLYNOMIAL, BCH_BITS)
# random data
data = bytearray(os.urandom(127))
# encode and make a "packet"
ecc = bch.encode(data)
packet = data + ecc
# print length of ecc, data, and packet
print('data size: %d' % (len(data)))
print('ecc size: %d' % (len(ecc)))
print('packet size: %d' % (len(packet)))
# print hash of packet
sha1_initial = hashlib.sha1(packet)
print('sha1: %s' % (sha1_initial.hexdigest(),))
def bitflip(packet):
byte_num = random.randint(0, len(packet) - 1)
bit_num = random.randint(0, 7)
packet[byte_num] ^= (1 << bit_num)
# make BCH_BITS errors
for _ in range(BCH_BITS):
bitflip(packet)
# print hash of packet
sha1_corrupt = hashlib.sha1(packet)
print('sha1: %s' % (sha1_corrupt.hexdigest(),))
# de-packetize
data, ecc = packet[:-bch.ecc_bytes], packet[-bch.ecc_bytes:]
# correct
bitflips = bch.decode_inplace(data, ecc)
print('bitflips: %d' % (bitflips))
# packetize
packet = data + ecc
# print hash of packet
sha1_corrected = hashlib.sha1(packet)
print('sha1: %s' % (sha1_corrected.hexdigest(),))
if sha1_initial.digest() == sha1_corrected.digest():
print('Corrected!')
else:
print('Failed')
This outputs
data size: 127
ecc size: 117
packet size: 244
sha1: 4ee71f947fc5d561b211a551c87fdef18a83404b
sha1: a072664312114fe59f5aa262bed853e35d70d349
bitflips: 72
sha1: 4ee71f947fc5d561b211a551c87fdef18a83404b
Corrected!
MATLAB code
%% bch params
M = 7;
n = 2^M-1; % Codeword length
k = 15; % Message length
nwords = 2; % Number of words to encode
% create a msg
msgTx = gf(randi([0 1],nwords,k));
%disp(msgTx)
%Find the error-correction capability.
t = bchnumerr(n,k)
% Encode the message.
enc = bchenc(msgTx,n,k);
%Corrupt up to t bits in each codeword.
noisycode = enc + randerr(nwords,n,1:t);
%Decode the noisy code.
msgRx = bchdec(noisycode,n,k);
% Validate that the message was properly decoded.
isequal(msgTx,msgRx)
which outputs:
t = 27
ans = logical 1
Increasing k>15 in MATLAB code gives following error:
Error using bchnumerr (line 72)
The values for N and K do not produce a valid narrow-sense BCH code.
Error in bchTest (line 10)
t = bchnumerr(n,k)
I discovered this question today (24 January 2021) as I searched for other information about BCH codes.
See Appendix A: Code Generators for BCH Codes (pdf) of Error-Correction Coding for Digital Communications by George C. Clark and J. Bibb Cain:
Your use of the Python library is confusing. For standard usage of BCH codes, the length of a codeword is equal to 2m - 1 for some positive integer m. The codeword in your example is not of this form.
I have not used that Python library, so I cannot write with certainty. If ecc is of length 127, then I suspect that it is a codeword. Concatenating ecc and data yields a packet that has a copy of the original message data as well as a copy of the codeword. This is not how BCH codes are used. When you have the codeword, you don't need to send it and a separate copy of the original message.
If you do read the reference linked above, be aware of the notation used to describe the polynomials. For the n = 127 table, the polynomial g1(x) is denoted by 211, which is octal notation. The nonzero bits in the binary expressions indicate the nonzero coefficients of the polynomial.
The polynomial g2(x) is equal to g1(x) multiplied by another polynomial:
This means that
g2(x) = (x7 + x3 + 1)(x7 + x3 + x2 + x + 1)
Each gt+1(x) is equal to gt(x) multiplied by another polynomial.