CECCO: Soft Decoding
CECCO supports several soft-input decoders for linear codes over finite fields. The common input format is a matrix of symbol-level log-likelihood ratios (LLRs). For a code over a finite field with q elements, the matrix has q−1 rows and one column per code symbol. Entry (a−1, i) is log(P(yi | 0) / P(yi | a)) for the nonzero field symbol a. This is the format consumed by soft-input exhaustive-search ML decoding, soft-input Viterbi decoding, BCJR decoding, and belief propagation.
The example uses F4 as an extension of F2. Transmission is done over the binary image of
the F4-valued codeword: the DEMUX block expands every F4 symbol into two
binary coordinates, the BI-AWGN channel acts on these binary coordinates, and the field-aware
LLRCalculator<F4> assembles the resulting observations into F4-symbol LLRs.
The LLR calculator is constructed from the channel object because the channel state is needed for
the LLR magnitudes.
What we see here are only the instantiations of the aforementioned blocks, we will make use of their overloaded operator() later.
using F2 = Fp<2>;
using F4 = Ext<F2, MOD{1, 1, 1}>;
DEMUX<F4, F2> demux;
BI_AWGN bi_awgn(2.0);
LLRCalculator<F4> llrcalculator(bi_awgn); // field aware LLR calculator
We use an extended Hamming code over F4 and convert it to an equivalent code in (systematic) standard form. This is important for the final message comparison: BCJR and BP both make symbol-wise hard decisions from posterior probabilities, so their output is not guaranteed to be a codeword in every situation. Standard-form encoding makes information-symbol extraction independent of the redundancy symbols.
auto Cpp = HammingCode<F4>(3);
auto Cp = extend(Cpp);
auto C = Cp.get_equivalent_code_in_standard_form();
std::cout << showall << C << std::endl;
A random F4-message is generated. We also store its binary image, which will be used later to determine message bit errors. The F4-message is encoded into a codeword of C.
const size_t k = C.get_k();
auto u = Vector<F4>(k).randomize();
Matrix<F2> u_binary = demux(u); // only needed for counting bit errors
std::cout << "Random message over F4: " << u << std::endl;
auto c = C.enc(u);
std::cout << "Codeword over F4: " << c << std::endl;
The following line performs the complete soft channel front end:
demux(c) expands the F4-codeword to a binary matrix, bi_awgn(...) transmits these
binary coordinates and returns soft channel outputs, and llrcalculator(...) converts those
observations into the symbol-level LLR matrix expected by the decoders. The explicit template argument in
LLRCalculator<F4> is essential: without it, class template argument deduction would create a
binary LLR calculator, resulting in binary-image LLRs instead of the required F4-symbol LLRs.
auto llrs = llrcalculator(bi_awgn(demux(c)));
The same LLR matrix can be passed to any of the soft decoders. Viterbi performs per-codeword ML decoding on the minimal trellis. The commented exhaustive-search ML decoder gives the same result, but it compares against all codewords and is therefore not feasible already for this small example (the code has 418 codewords).
auto c_hat_Viterbi = C.dec_Viterbi_soft(llrs);
auto u_hat_Viterbi = C.encinv(c_hat_Viterbi);
std::cout << "Viterbi message estimate: " << u_hat_Viterbi << std::endl;
std::cout << "Viterbi message bit errors: " << dH(u_binary, demux(u_hat_Viterbi)) << std::endl;
/*
auto c_hat_ML = C.dec_ML_soft(llrs); // highly inefficient, not for larger codes!
auto u_hat_ML = C.encinv(c_hat_ML);
std::cout << "ML message estimate: " << u_hat_ML << std::endl;
std::cout << "ML message bit errors: " << dH(u_binary, demux(u_hat_ML)) << std::endl;
assert(c_hat_ML == c_hat_Viterbi); // Viterbi _is_ ML
*/
BCJR performs exact marginalization on the trellis (s/s MAP decoding) and BP runs sum-product message passing on the Tanner graph. Both return symbol-wise hard decisions based on posterior information. These decisions need not coincide with the ML codeword decision and they are not guaranteed to be codewords.
auto c_hat_BCJR = C.dec_BCJR(llrs);
auto u_hat_BCJR = C.encinv(c_hat_BCJR);
std::cout << "BCJR message estimate: " << u_hat_BCJR << std::endl;
std::cout << "BCJR message bit errors: " << dH(u_binary, demux(u_hat_BCJR)) << std::endl;
auto c_hat_BP = C.dec_BP(llrs, 20); // max. 20 iterations of BP decoding
auto u_hat_BP = C.encinv(c_hat_BP);
std::cout << "BP message estimate: " << u_hat_BP << std::endl;
std::cout << "BP message bit errors: " << dH(u_binary, demux(u_hat_BP)) << std::endl;
The message estimates are converted to their binary images. The number of message bit errors is the Hamming distance between the two binary matrices, where the two entries in the i-th column represent the i-th F4 symbol.
The same simulation can alternatively be written as a simulation chain. The decoder block can be switched between
method_t::Viterbi_soft, method_t::ML_soft, method_t::BCJR, and method_t::BP without
changing the preceding channel and LLR calculation.
{
/* alternative realization: simulation chain (BCJR example) */
Enc enc(C); // encoder block
Dec dec(C, method_t::BCJR); // (BCJR) decoder block
Encinv encinv(C); // (systematic, standard form) encoder inverse block
Vector<F4> u_hat;
u >> enc >> demux >> bi_awgn >> llrcalculator >> dec >> encinv >> u_hat;
std::cout << "Sim. chain message estimate: " << u_hat << std::endl;
std::cout << "Sim. chain message bit errors: " << dH(u_binary, demux(u_hat)) << std::endl;
The chain output is handled in the same way as before: recover the F4-message, demultiplex it to its binary image for bit error calculation. Intermediate values of the simulation chain can be extracted as needed (by inserting appropriate buffer variables).
Random message over F4: ( 3, 1, 2, 0, 3, 2, 2, 3, 3, 3, 3, 0, 3, 1, 3, 2, 0, 1 )
Codeword over F4: ( 3, 1, 2, 0, 3, 2, 2, 3, 3, 3, 3, 0, 3, 1, 3, 2, 0, 1, 3, 3, 3, 2 )
Viterbi message estimate: ( 3, 1, 2, 0, 3, 2, 2, 3, 3, 3, 3, 0, 3, 1, 3, 2, 0, 1 )
Viterbi message bit errors: 0
BCJR message estimate: ( 3, 1, 2, 0, 3, 2, 2, 1, 3, 3, 1, 0, 3, 1, 3, 2, 0, 1 )
BCJR message bit errors: 2
BP message estimate: ( 3, 1, 2, 0, 3, 2, 2, 1, 3, 1, 1, 0, 3, 0, 3, 2, 0, 1 )
BP message bit errors: 4
Sim. chain message estimate: ( 3, 1, 2, 0, 3, 2, 2, 3, 3, 3, 3, 0, 3, 1, 3, 2, 0, 1 )
Sim. chain message bit errors: 0
The exact output changes from run to run because the message and channel are random. Also, the alternative simulation chain realization includes an actual channel use, resulting in a chain estimate that is much different from the other estimates. The relevant point is the interface: finite-field code symbols are transmitted through their binary images, the field-aware LLR calculator produces the common symbol-level LLR matrix format, and all soft decoders consume this same matrix.
A complete, compilable demo is shown below:
#include <iostream>
#include "cecco.hpp"
using namespace CECCO;
int main(void) {
using F2 = Fp<2>;
using F4 = Ext<F2, MOD{1, 1, 1}>;
DEMUX<F4, F2> demux;
BI_AWGN bi_awgn(2.0);
LLRCalculator<F4> llrcalculator(bi_awgn); // field aware LLR calculator
std::cout << F4::get_info() << std::endl;
auto Cpp = HammingCode<F4>(3);
auto Cp = extend(Cpp);
auto C = Cp.get_equivalent_code_in_standard_form();
std::cout << showall << C << std::endl;
const size_t k = C.get_k();
auto u = Vector<F4>(k).randomize();
Matrix<F2> u_binary = demux(u); // only needed for counting bit errors
std::cout << "Random message over F4: " << u << std::endl;
auto c = C.enc(u);
std::cout << "Codeword over F4: " << c << std::endl;
auto llrs = llrcalculator(bi_awgn(demux(c)));
auto c_hat_Viterbi = C.dec_Viterbi_soft(llrs);
auto u_hat_Viterbi = C.encinv(c_hat_Viterbi);
std::cout << "Viterbi message estimate: " << u_hat_Viterbi << std::endl;
std::cout << "Viterbi message bit errors: " << dH(u_binary, demux(u_hat_Viterbi)) << std::endl;
/*
auto c_hat_ML = C.dec_ML_soft(llrs); // highly inefficient, not for larger codes!
auto u_hat_ML = C.encinv(c_hat_ML);
std::cout << "ML message estimate: " << u_hat_ML << std::endl;
std::cout << "ML message bit errors: " << dH(u_binary, demux(u_hat_ML)) << std::endl;
assert(c_hat_ML == c_hat_Viterbi); // Viterbi _is_ ML
*/
auto c_hat_BCJR = C.dec_BCJR(llrs);
auto u_hat_BCJR = C.encinv(c_hat_BCJR);
std::cout << "BCJR message estimate: " << u_hat_BCJR << std::endl;
std::cout << "BCJR message bit errors: " << dH(u_binary, demux(u_hat_BCJR)) << std::endl;
auto c_hat_BP = C.dec_BP(llrs, 20); // max. 20 iterations of BP decoding
auto u_hat_BP = C.encinv(c_hat_BP);
std::cout << "BP message estimate: " << u_hat_BP << std::endl;
std::cout << "BP message bit errors: " << dH(u_binary, demux(u_hat_BP)) << std::endl;
{
/* alternative realization: simulation chain (BCJR example) */
Enc enc(C); // encoder block
Dec dec(C, method_t::BCJR); // (BCJR) decoder block
Encinv encinv(C); // (systematic, standard form) encoder inverse block
Vector<F4> u_hat;
u >> enc >> demux >> bi_awgn >> llrcalculator >> dec >> encinv >> u_hat;
std::cout << "Sim. chain message estimate: " << u_hat << std::endl;
std::cout << "Sim. chain message bit errors: " << dH(u_binary, demux(u_hat)) << std::endl;
}
return 0;
}