Encoder/decoder for a primitive narrow-sense BCH codes over Galois field GF(2) written in standard C++20.
Instant encoding and decoding with no runtime initialization.
All lookup values including the generator polynomial deduced at compilation time from the known user-provided primitive polynomial and BCH code parameters.
Berlekamp-Massey algorithm used in decoder for finding the error locator polynomial.
Chien's search used for finding roots of error locator polynomial. For reference, the alternative brute force algorithm can be selected with a compiler option.
Single threaded.
Not optimized.
Header-only implementation.
No 3rd party dependencies.
This is an experimental demo project exploring the potential of template metaprogramming and compilation time code execution in the context of error correcting codes.
Operator overloading for polynomial and modulo arithmetic delivers inuitive and self-explanatory code in an otherwise non-trivial cases.
Templated and constexpr polynomial and Galois field implementations allow representing constructs like polynomials with other kinds of polynomials as coefficients in a compact way. A practical example is the error locator polynomial used in decoding.
The resulting top-level encode and decode routines are simple and easy to read.
Depending on the author, the types of binary BCH codes are usually described as BCH(n, k), BCH(n, k, t), BCH(m, k, t) or similar and generally can be characterised by the following parameters:
- m is the power of prime q used to build the GF(q^m) field, q=2 in case of binary BCH
- n = 2^m - 1, determines the codeword length (number of usable elements in GF(2^m))
- t or ECC (error correction-capability) bits can be corrected in a single codeword in case of a detected errors, affects relation between number of usable data and parity bits present within a single codeword size
- primitive polynomial example: 1 + x^3 + x^7, determines the pattern of an emergent Galois field (2^m), may non-trivially affect the effective number of required parity bits because of some obscure effects
- k number of usable data bits within a single BCH codeword, directly results from m (or n), t and primitive polynomial
- generator polynomial is used to encode codewords, deduced from the above parameters and is often provided for reference together with the BCH code type
Some parameters are often omitted in such a description and must be determined from the provided ones by the following inequality conditions:
t <= n
n-k <= m*t
with
m >= 3 and t < 2^(m-1)
The mr::bch codec uses the following representation based on m, t and primitive polynomial only:
mr::bch<m, t, poly...>
where poly... term expands to the nonzero coefficient powers of the used primitive polynomial.
With
- m = 7
- t = 13
- primitive polynomial = 1 + x^6 + x^7 (non-zero polynomial coefficient powers: 0, 6, 7)
the resulting codec type is:
#include "bch.h"
using bch_type = mr::bch<7, 13, 0, 6, 7>;
Now it's simple to encode and decode consecutive codewords.
auto encoded = bch_type::encode_codeword(message_bytes);
//
// transmission errors may appear here in encoded bits...
//
const auto result = bch_type::decode_codeword(*encoded, decoded_bytes);
For more usage details, please refer to the code in tests.h, tests.cpp and main.cpp.
The only requirement is a working C++20 compiler.
The range of implemented C++20 features varies among the compilers. If the code doesn't compile, try a different or newer compiler.
Because of my preference this project uses Qt for configuration and building, but no actual Qt references are used in code.
Here's list of configurations it builds for me so far:
- Qt 6.7.2 for GCC 11 on Ubuntu 22.04 Linux 64-bit
- Qt 6.8 beta4 for MinGW 13.1 on Windows 10 64-bit
Implements an executable running a single test procedure for m=7, t=13 and the primitive polynomial 1 + x^6 + x^7.
This BCH code configuration results in a codeword of 127 bits with 50 (usable) data bits and 77 (error correcting) parity bits.
The test message is a zero terminated "Hello" text. Using 48 data bits out of 50 available wastes 2 bits in each codeword, but still works good enough for a demo.
The test procedure is running 100 iterations, corrupting the encoded codeword with t random errors in each.
The number of iterations can be controlled by passing a single number as command line argument to the compiled executable.
./bch 1000
or
bch.exe 1000
will execute 1000 iterations instead of 100.
BCH from the ATSC A/336 specification for audio watermarking in essence boils down to the codec introduced in the Usage section:
mr::bch<7, 13, 0, 6, 7>
With no DEBUG_* compiler flags defined, code in main.cpp prints only one line:
mr::bch<7, 13, 0, 6, 7> 100 test iterations (encode -> add errors -> decode) took 1.760389 [s] (avg: 17.603889 [ms])
Adding the DEBUG_VERBOSE_ENC_DEC to the compiler defines makes one line appear for each encode/decode routine execution:
mr::bch<7, 13, 0, 6, 7>::encode_codeword... execution took 198.639 us (0.000198639 s)
mr::bch<7, 13, 0, 6, 7>::decode_codeword... execution took 17318.9 us (0.0173189 s)
The output after adding also the DEBUG_VERBOSE to the compiler defines prints the full debug output for every test iteration, including the full Galois field summary:
BCH (m=7, n=127, t=ECC=13, k=data_bits=50, parity_bits=77, primitive_polynomial=11000001):
Galois field (2^m), m=7, n=2^m-1=127:
[a^ 0]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 % 11000001 = 0000001
[a^ 1]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010 % 11000001 = 0000010
[a^ 2]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100 % 11000001 = 0000100
[a^ 3]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000 % 11000001 = 0001000
[a^ 4]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000 % 11000001 = 0010000
[a^ 5]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000 % 11000001 = 0100000
[a^ 6]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000 % 11000001 = 1000000
[a^ 7]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000 % 11000001 = 1000001
[a^ 8]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000 % 11000001 = 1000011
[a^ 9]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000 % 11000001 = 1000111
[a^ 10]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000 % 11000001 = 1001111
[a^ 11]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000 % 11000001 = 1011111
[a^ 12]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000 % 11000001 = 1111111
[a^ 13]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000 % 11000001 = 0111111
[a^ 14]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000 % 11000001 = 1111110
[a^ 15]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000 % 11000001 = 0111101
[a^ 16]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000 % 11000001 = 1111010
[a^ 17]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000 % 11000001 = 0110101
[a^ 18]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000 % 11000001 = 1101010
[a^ 19]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000 % 11000001 = 0010101
[a^ 20]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000 % 11000001 = 0101010
[a^ 21]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000 % 11000001 = 1010100
[a^ 22]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000 % 11000001 = 1101001
[a^ 23]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000 % 11000001 = 0010011
[a^ 24]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000 % 11000001 = 0100110
[a^ 25]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000 % 11000001 = 1001100
[a^ 26]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000 % 11000001 = 1011001
[a^ 27]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000 % 11000001 = 1110011
[a^ 28]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000 % 11000001 = 0100111
[a^ 29]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000 % 11000001 = 1001110
[a^ 30]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000 % 11000001 = 1011101
[a^ 31]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000 % 11000001 = 1111011
[a^ 32]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000 % 11000001 = 0110111
[a^ 33]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000 % 11000001 = 1101110
[a^ 34]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000 % 11000001 = 0011101
[a^ 35]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000 % 11000001 = 0111010
[a^ 36]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000 % 11000001 = 1110100
[a^ 37]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000 % 11000001 = 0101001
[a^ 38]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000 % 11000001 = 1010010
[a^ 39]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000 % 11000001 = 1100101
[a^ 40]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000 % 11000001 = 0001011
[a^ 41]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000 % 11000001 = 0010110
[a^ 42]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000 % 11000001 = 0101100
[a^ 43]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000 % 11000001 = 1011000
[a^ 44]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000 % 11000001 = 1110001
[a^ 45]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000 % 11000001 = 0100011
[a^ 46]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000 % 11000001 = 1000110
[a^ 47]: 00000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000 % 11000001 = 1001101
[a^ 48]: 00000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000 % 11000001 = 1011011
[a^ 49]: 00000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000 % 11000001 = 1110111
[a^ 50]: 00000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000 % 11000001 = 0101111
[a^ 51]: 00000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000 % 11000001 = 1011110
[a^ 52]: 00000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000 % 11000001 = 1111101
[a^ 53]: 00000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000 % 11000001 = 0111011
[a^ 54]: 00000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000 % 11000001 = 1110110
[a^ 55]: 00000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000 % 11000001 = 0101101
[a^ 56]: 00000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000 % 11000001 = 1011010
[a^ 57]: 00000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000 % 11000001 = 1110101
[a^ 58]: 00000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000 % 11000001 = 0101011
[a^ 59]: 00000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000 % 11000001 = 1010110
[a^ 60]: 00000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1101101
[a^ 61]: 00000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0011011
[a^ 62]: 00000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0110110
[a^ 63]: 00000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1101100
[a^ 64]: 00000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0011001
[a^ 65]: 00000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0110010
[a^ 66]: 00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1100100
[a^ 67]: 00000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0001001
[a^ 68]: 00000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0010010
[a^ 69]: 00000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0100100
[a^ 70]: 00000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1001000
[a^ 71]: 00000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1010001
[a^ 72]: 00000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1100011
[a^ 73]: 00000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0000111
[a^ 74]: 00000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0001110
[a^ 75]: 00000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0011100
[a^ 76]: 00000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0111000
[a^ 77]: 00000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1110000
[a^ 78]: 00000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0100001
[a^ 79]: 00000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1000010
[a^ 80]: 00000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1000101
[a^ 81]: 00000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1001011
[a^ 82]: 00000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1010111
[a^ 83]: 00000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1101111
[a^ 84]: 00000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0011111
[a^ 85]: 00000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0111110
[a^ 86]: 00000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1111100
[a^ 87]: 00000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0111001
[a^ 88]: 00000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1110010
[a^ 89]: 00000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0100101
[a^ 90]: 00000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1001010
[a^ 91]: 00000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1010101
[a^ 92]: 00000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1101011
[a^ 93]: 00000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0010111
[a^ 94]: 00000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0101110
[a^ 95]: 00000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1011100
[a^ 96]: 00000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1111001
[a^ 97]: 00000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0110011
[a^ 98]: 00000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1100110
[a^ 99]: 00000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0001101
[a^100]: 00000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0011010
[a^101]: 00000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0110100
[a^102]: 00000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1101000
[a^103]: 00000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0010001
[a^104]: 00000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0100010
[a^105]: 00000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1000100
[a^106]: 00000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1001001
[a^107]: 00000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1010011
[a^108]: 00000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1100111
[a^109]: 00000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0001111
[a^110]: 00000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0011110
[a^111]: 00000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0111100
[a^112]: 00000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1111000
[a^113]: 00000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0110001
[a^114]: 00000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1100010
[a^115]: 00000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0000101
[a^116]: 00000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0001010
[a^117]: 00000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0010100
[a^118]: 00000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0101000
[a^119]: 00000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1010000
[a^120]: 00000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1100001
[a^121]: 00000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0000011
[a^122]: 00000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0000110
[a^123]: 00001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0001100
[a^124]: 00010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0011000
[a^125]: 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0110000
[a^126]: 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 1100000
[a^127]: 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 % 11000001 = 0000001 (shown for clarity)
primitive polynomial {msb...lsb}: 11000001
cyclotomic cosets [a^ 1]: 1, 2, 4, 8, 16, 32, 64,
cyclotomic cosets [a^ 3]: 3, 6, 12, 24, 48, 96, 65,
cyclotomic cosets [a^ 5]: 5, 10, 20, 40, 80, 33, 66,
cyclotomic cosets [a^ 7]: 7, 14, 28, 56, 112, 97, 67,
cyclotomic cosets [a^ 9]: 9, 18, 36, 72, 17, 34, 68,
cyclotomic cosets [a^ 11]: 11, 22, 44, 88, 49, 98, 69,
cyclotomic cosets [a^ 13]: 13, 26, 52, 104, 81, 35, 70,
cyclotomic cosets [a^ 15]: 15, 30, 60, 120, 113, 99, 71,
cyclotomic cosets [a^ 19]: 19, 38, 76, 25, 50, 100, 73,
cyclotomic cosets [a^ 21]: 21, 42, 84, 41, 82, 37, 74,
cyclotomic cosets [a^ 23]: 23, 46, 92, 57, 114, 101, 75,
minimal polynomial a^[ 1] {msb...lsb}: 11000001
minimal polynomial a^[ 3] {msb...lsb}: 11010101
minimal polynomial a^[ 5] {msb...lsb}: 11110001
minimal polynomial a^[ 7] {msb...lsb}: 10111111
minimal polynomial a^[ 9] {msb...lsb}: 10011101
minimal polynomial a^[ 11] {msb...lsb}: 10010001
minimal polynomial a^[ 13] {msb...lsb}: 10100111
minimal polynomial a^[ 15] {msb...lsb}: 11111101
minimal polynomial a^[ 19] {msb...lsb}: 11110111
minimal polynomial a^[ 21] {msb...lsb}: 11010011
minimal polynomial a^[ 23] {msb...lsb}: 11100101
generator polynomial (77th order) {msb...lsb}: 111101100111011101100000001110000101111000110101100100001111100011001000100101
mr::bch<7, 13, 0, 6, 7>::encode_codeword... execution took 204.534 us (0.000204534 s)
test poly: 0000000000011011110110110001101100011001010100100000100101110111010111100010100010110110001110001101101010001111111111111111111
testing by corrupting message bit 44 @ byte 5
testing by corrupting message bit 13 @ byte 1
testing by corrupting message bit 116 @ byte 14
testing by corrupting message bit 112 @ byte 14
testing by corrupting message bit 90 @ byte 11
testing by corrupting message bit 110 @ byte 13
testing by corrupting message bit 72 @ byte 9
testing by corrupting message bit 3 @ byte 0
testing by corrupting message bit 30 @ byte 3
testing by corrupting message bit 103 @ byte 12
testing by corrupting message bit 113 @ byte 14
testing by corrupting message bit 2 @ byte 0
testing by corrupting message bit 26 @ byte 3
decoding poly: 0000000000111101010110100001101100010001010100100000101101110111010111100010100010010110001110000101001010001111101111111110011
decoding bit errors...
syndrome[0]: 0100011 --> a^ 45
syndrome[1]: 0100011 --> a^ 90
syndrome[2]: 1001011 --> a^ 69
syndrome[3]: 0100011 --> a^ 53
syndrome[4]: 1111011 --> a^ 28
syndrome[5]: 1001011 --> a^ 11
syndrome[6]: 0111110 --> a^ 54
syndrome[7]: 0100011 --> a^106
syndrome[8]: 1001101 --> a^ 33
syndrome[9]: 1111011 --> a^ 56
syndrome[10]: 0000101 --> a^102
syndrome[11]: 1001011 --> a^ 22
syndrome[12]: 1100010 --> a^ 42
syndrome[13]: 0111110 --> a^108
syndrome[14]: 0010101 --> a^113
syndrome[15]: 0100011 --> a^ 85
syndrome[16]: 1001101 --> a^ 20
syndrome[17]: 1001101 --> a^ 66
syndrome[18]: 1000011 --> a^ 54
syndrome[19]: 1111011 --> a^112
syndrome[20]: 1011101 --> a^ 85
syndrome[21]: 0000101 --> a^ 77
syndrome[22]: 1011010 --> a^121
syndrome[23]: 1001011 --> a^ 44
syndrome[24]: 1000011 --> a^ 51
syndrome[25]: 1100010 --> a^ 84
found error locator polynomial root @ a^ 11 --> error location: a^116
found error locator polynomial root @ a^ 14 --> error location: a^113
found error locator polynomial root @ a^ 15 --> error location: a^112
found error locator polynomial root @ a^ 17 --> error location: a^110
found error locator polynomial root @ a^ 24 --> error location: a^103
found error locator polynomial root @ a^ 37 --> error location: a^ 90
found error locator polynomial root @ a^ 55 --> error location: a^ 72
found error locator polynomial root @ a^ 83 --> error location: a^ 44
found error locator polynomial root @ a^ 97 --> error location: a^ 30
found error locator polynomial root @ a^101 --> error location: a^ 26
found error locator polynomial root @ a^114 --> error location: a^ 13
found error locator polynomial root @ a^124 --> error location: a^ 3
found error locator polynomial root @ a^125 --> error location: a^ 2
corrupted (13 errs): 0000000000111101010110100001101100010001010100100000101101110111010111100010100010010110001110000101001010001111101111111110011
error mask: 0000000000100110100000010000000000001000000000000000001000000000000000000000000000100000000000001000100000000000010000000001100
corrected: 0000000000011011110110110001101100011001010100100000100101110111010111100010100010110110001110001101101010001111111111111111111
mr::bch<7, 13, 0, 6, 7>::decode_codeword... execution took 18635.9 us (0.0186359 s)
mr::bch<7, 13, 0, 6, 7> test result:
input: (hex: 48 65 6c 6c 6f 00 00) "Hello"
encoded: (hex: ff ff 47 6d 1c 5b 14 af bb 04 a9 8c 8d ed 0d 00)
corrupted: (hex: f3 df 47 29 1c 4b 14 af bb 05 a9 88 0d ad 1e 00)
decoded: (hex: 48 65 6c 6c 6f 00 00) "Hello"
As described in this paper, the Phobos Lander telemetry system used a BCH(128, 113) with 2 error-correcting capability, which is a BCH(127, 113) with an additional parity bit.
The paper also describes the polynomials used, theese are:
primitive = 1 + x^3 + x7
and
generator = 1 + x + x^2 + x^4 + x^5 + x^6 + x^8 + x^9 + x^14
Interpreting for the mr::bch codec and knowing the BCH inequality condition
n = 2^m - 1
n - k <= m * t
then (2^m-1) - m*t = 113 = k and works for m=7, t=2 and BCH(127, 113) together with given primitive polynomial translates to the following codec type:
mr::bch<7, 2, 0, 3, 7>
The debug output correctly prints the matching generator polynomial (msb...lsb: 100001101110111).
For reference, below is the output of all three verbosity schemes:
mr::bch<7, 2, 0, 3, 7> 100 test iterations (encode -> add errors -> decode) took 0.242246 [s] (avg: 2.422458 [ms])
With DEBUG_VERBOSE_ENC_DEC:
mr::bch<7, 2, 0, 3, 7>::encode_codeword... execution took 245.113 us (0.000245113 s)
mr::bch<7, 2, 0, 3, 7>::decode_codeword... execution took 2386.37 us (0.00238637 s)
With DEBUG_VERBOSE and DEBUG_VERBOSE_ENC_DEC:
BCH (m=7, n=127, t=ECC=2, k=data_bits=113, parity_bits=14, primitive_polynomial=10001001):
...
cyclotomic cosets [a^ 1]: 1, 2, 4, 8, 16, 32, 64,
cyclotomic cosets [a^ 3]: 3, 6, 12, 24, 48, 96, 65,
minimal polynomial a^[ 1] {msb...lsb}: 10001001
minimal polynomial a^[ 3] {msb...lsb}: 10001111
generator polynomial (14th order) {msb...lsb}: 100001101110111
mr::bch<7, 2, 0, 3, 7>::encode_codeword... execution took 664.433 us (0.000664433 s)
test poly: 0000000000000000000000000000000000000000000000000000000000000000000000000011011110110110001101100011001010100100010110000001111
testing by corrupting message bit 1 @ byte 0
testing by corrupting message bit 13 @ byte 1
decoding poly: 0000000000000000000000000000000000000000000000000000000000000000000000000011011110110110001101100011001010100100000110000001101
decoding bit errors...
syndrome[0]: 1100110 --> a^ 29
syndrome[1]: 1100110 --> a^ 58
syndrome[2]: 1101111 --> a^ 52
syndrome[3]: 1100110 --> a^116
found error locator polynomial root @ a^114 --> error location: a^ 13
found error locator polynomial root @ a^126 --> error location: a^ 1
corrupted (2 errs): 0000000000000000000000000000000000000000000000000000000000000000000000000011011110110110001101100011001010100100000110000001101
error mask: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000010
corrected: 0000000000000000000000000000000000000000000000000000000000000000000000000011011110110110001101100011001010100100010110000001111
mr::bch<7, 2, 0, 3, 7>::decode_codeword... execution took 4912.92 us (0.00491292 s)
mr::bch<7, 2, 0, 3, 7> test result:
input: (hex: 48 65 6c 6c 6f 00 00 00 00 00 00 00 00 00 00) "Hello"
encoded: (hex: 0f 2c 52 19 1b db 1b 00 00 00 00 00 00 00 00 00)
corrupted: (hex: 0d 0c 52 19 1b db 1b 00 00 00 00 00 00 00 00 00)
decoded: (hex: 48 65 6c 6c 6f 00 00 00 00 00 00 00 00 00 00) "Hello"
- more code refactoring
- better error reporting
- check compilation on Mac
- add more rigorous tests
- buffered codec input/output
- move codeword layout options from compiler flags to the user code
- automatic primitive polynomial deduction
- even more rigorous automatic tests after primitive polynomial deduction is implemented
- try alternative polynomial implementation
- check the dissassembly
This software may be freely distributed under the MIT License