Skip to content

bchlib sometimes fails to correct errors in parity bits #41

@TuBui

Description

@TuBui

bchlib version 2.1.3

I am working on a problem that requires the whole after-ecc code word to be corrected, not just the original message bits. I notice that bchlib sometimes fails to correct a bit-flip within the parity bits. Here is a MWE to reproduce the problem:

import bchlib
import binascii

def display(byte_data):
    hex_string = binascii.hexlify(byte_data).decode('utf-8')
    bin_string = ' '.join(format(byte, '08b') for byte in byte_data)
    return f"{hex_string} ({bin_string})"

n = 31
t = 3
k = 16
poly = 37
bch = bchlib.BCH(t, poly)
msg = bytes([0xAB, 0xCD])
parity = bch.encode(msg)
cw = msg + parity
print('Original message: ', display(msg))
print('Parity:       ', display(parity))
print('Codeword:     ', display(cw))

# change 3 bits
positions = [0, 10, 24]
rx = bytearray(cw)  # make a copy
for pos in positions:
    rx[pos // 8] ^= (1 << (pos % 8))
print('Corrupted positions:', positions)
print('Corrupted:    ', display(rx))

# decode
data, ecc = rx[:-bch.ecc_bytes], rx[-bch.ecc_bytes:]
nerr = bch.decode(data, ecc)
print('nerr: ', nerr)
bch.correct(data, ecc)
print('Corrected message: ', display(data))
print('Corrected parity:   ', display(ecc))
print('Parity corrected: ', ecc == parity)

Output:

Original message: abcd (10101011 11001101)
Parity: 50e8 (01010000 11101000)
Codeword: abcd50e8 (10101011 11001101 01010000 11101000)
Corrupted positions: [0, 10, 24]
Corrupted: aac950e9 (10101010 11001001 01010000 11101001)
nerr: 2
Corrected message: abcd (10101011 11001101)
Corrected parity: 50e9 (01010000 11101001)
Parity corrected: False

Here, there are 2 bit flips in the message data (position 0 and 10) and 1 bit flip in the parity (position 24 in the codeword, or the 9th parity bit). As shown in the output, bchlib fails to correct the last bit flip and throws number of errors of 2. BCH algorithm should have output 3 errors and be able to correct all of them.

Note that it works with all other error positions, but always fails when the bit at index 24 is flipped.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions