CECCO: Polynomial and Cyclic Codes
Besides general linear codes as demonstrated in the corresponding demo, CECCO also supports polynomial and cyclic codes. They are treated as linear codes with special polynomial and cyclic properties. Same as general linear codes, polynomial and cyclic codes are supported over finite fields and (partially) over the rationals. For details about finite field construction consult the demo on prime fields, the demo on finite extension fields, or the documentation
The main example here is based on the binary field F4 (as extension of F2 with irreducible polynomial 1 + x + x^2, compiler-generated LUTs). It can easily be modified to any other finite field.
using F = Ext<Fp<2>, {1, 1, 1}, LutMode::CompileTime>;
After selecting some code length n and code dimension k we calculate a random generator polynomial with nonzero constant term and degree n-k:
auto gamma = Polynomial<F>();
do {
gamma.randomize(n - k);
} while (gamma[0].is_zero());
Based on the random polynomial (which might come out as 1 + 2x + 2x^3 + 2x^4 + 2x^5 + 2x^7 + x^8) we can set up a polynomial code C[F_4; n, k] as a linear code with the polynomial property (through a dedicated constructor of the LinearCode class template):
auto C = LinearCode<F>(k, gamma);
We can print all properties of C to the console using the CECCO::showall IO manipulator;
std::cout << showall << C << std::endl;
[F_4; 17, 9], dmin = 7
Linear code with properties: {
G =
⌈1 2 0 2 2 2 0 2 1 0 0 0 0 0 0 0 0⌉
|0 1 2 0 2 2 2 0 2 1 0 0 0 0 0 0 0|
|0 0 1 2 0 2 2 2 0 2 1 0 0 0 0 0 0|
|0 0 0 1 2 0 2 2 2 0 2 1 0 0 0 0 0|
|0 0 0 0 1 2 0 2 2 2 0 2 1 0 0 0 0|
|0 0 0 0 0 1 2 0 2 2 2 0 2 1 0 0 0|
|0 0 0 0 0 0 1 2 0 2 2 2 0 2 1 0 0|
|0 0 0 0 0 0 0 1 2 0 2 2 2 0 2 1 0|
⌊0 0 0 0 0 0 0 0 1 2 0 2 2 2 0 2 1⌋
H =
⌈1 0 0 0 0 0 0 0 1 2 3 3 0 0 3 3 2⌉
|0 1 0 0 0 0 0 0 2 2 3 2 3 0 1 2 0|
|0 0 1 0 0 0 0 0 0 2 2 3 2 3 0 1 2|
|0 0 0 1 0 0 0 0 2 3 3 3 3 2 2 1 2|
|0 0 0 0 1 0 0 0 2 1 2 2 3 3 3 3 2|
|0 0 0 0 0 1 0 0 2 1 0 3 2 3 2 2 0|
|0 0 0 0 0 0 1 0 0 2 1 0 3 2 3 2 2|
⌊0 0 0 0 0 0 0 1 2 3 3 0 0 3 3 2 1⌋
A(x) = 1 + 1224x^7 + 1530x^8 + 10200x^9 + 8160x^10 + 51408x^11 + 25704x^12 + 85680x^13 + 24480x^14 + 45288x^15 + 5661x^16 + 2808x^17 tmax = 3
polynomial(cyclic, gamma = 1 + 2x + 2x^3 + 2x^4 + 2x^5 + 2x^7 + x^8)
}
We see the code parameters, the minimum distance, G and H, the weight enumerator A(x). The number of correctable errors with a BD decoder is shown as tmax=3 and CECCO also found that the random code happens to be not only polynomial with generator polynomial 1 + 2x + 2x^3 + 2x^4 + 2x^5 + 2x^7 + x^8 but also cyclic.
CECCO can deliver the dual code and applies MacWilliams' identity in order to calculate the weight enumerator. Cyclicity is, other than polynomiality in general, preserved by the dual code:
auto Cd = C.get_dual();
std::cout << showall << Cd << std::endl;
[F_4; 17, 8], dmin = 8
Linear code with properties: {
G =
⌈1 0 0 0 0 0 0 0 1 2 3 3 0 0 3 3 2⌉
|0 1 0 0 0 0 0 0 2 2 3 2 3 0 1 2 0|
|0 0 1 0 0 0 0 0 0 2 2 3 2 3 0 1 2|
|0 0 0 1 0 0 0 0 2 3 3 3 3 2 2 1 2|
|0 0 0 0 1 0 0 0 2 1 2 2 3 3 3 3 2|
|0 0 0 0 0 1 0 0 2 1 0 3 2 3 2 2 0|
|0 0 0 0 0 0 1 0 0 2 1 0 3 2 3 2 2|
⌊0 0 0 0 0 0 0 1 2 3 3 0 0 3 3 2 1⌋
H =
⌈1 0 0 0 0 0 0 0 0 1 2 0 2 2 2 0 2⌉
|0 1 0 0 0 0 0 0 0 2 2 2 3 1 1 2 3|
|0 0 1 0 0 0 0 0 0 3 3 2 3 2 0 1 3|
|0 0 0 1 0 0 0 0 0 3 2 3 3 2 3 0 0|
|0 0 0 0 1 0 0 0 0 0 3 2 3 3 2 3 0|
|0 0 0 0 0 1 0 0 0 0 0 3 2 3 3 2 3|
|0 0 0 0 0 0 1 0 0 3 1 0 2 3 2 3 3|
|0 0 0 0 0 0 0 1 0 3 2 1 1 3 2 2 2|
⌊0 0 0 0 0 0 0 0 1 2 0 2 2 2 0 2 1⌋
A(x) = 1 + 1530x^8 + 8160x^10 + 25704x^12 + 24480x^14 + 5661x^16 tmax = 3
polynomial(cyclic, gamma = 1 + 2x + 3x^2 + 3x^3 + 3x^6 + 3x^7 + 2x^8 + x^9)
}
CECCO supports all decoders for general linear codes also for polynomial and cyclic codes (cf. the demo for linear codes and their decoding). For the special case of cyclic codes, it also supports the more efficient Meggitt BD decoder:
First, we generate a random codeword of C:
auto u = Vector<F>(k).randomize();
std::cout << "Random message: " << u << std::endl;
auto c = C.enc(u);
Random message: ( 1, 3, 3, 0, 2, 0, 1, 1, 0 )
Then we transmit over a quaternary symmetric discrete memoryless channel for a hard-input decoding scenario:
const double pe = 0.05;
SDMC<F> channel(pe);
// RX
auto r = channel(c);
BD decoding can fail with a CECCO::decoding_failure so we have to wrap the decoder in a
try/catch block. In case the code is cyclic we verify that the output of the Meggitt BD decoder coincides with the output of the generic standard array-based BD decoder.
try {
auto c_est = C.dec_BD(r);
if (C.is_cyclic()) assert(c_est == C.dec_Meggitt(r));
auto u_est = C.encinv(c_est);
std::cout << "BD decoding message estimate: " << u_est << std::endl;
} catch (const decoding_failure& e) {
std::cout << "BD decoding failure!" << std::endl;
}
The polynomial and cyclic properties are preserved by subfield subcodes (here, the subfield subcode is a binary repetition code C' of length 17):
auto Cp = SubfieldSubcode(C);
std::cout << showall << Cp << std::endl;
assert(Cp.is_polynomial());
if (C.is_cyclic()) assert(Cp.is_cyclic());
F_2; 17, 1], dmin = 17
Linear code with properties: {
G =
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
H =
⌈1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1⌉
|0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1|
|0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1|
⌊0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1⌋
A(x) = 1 + x^17 tmax = 8
polynomial(cyclic, gamma = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12 + x^13 + x^14 + x^15 + x^16) perfect MDS equidistant
}
Subfield-subcode with properties: {
Gamma =
(1 3 0 3 3 3 0 3 1),
Supercode = [F_4; 17, 9] Linear code with properties: { polynomial(cyclic, gamma = 1 + 2x + 2x^3 + 2x^4 + 2x^5 + 2x^7 + x^8) }
}
A complete, compilable demo is shown below:
#include <iostream>
#include "cecco.hpp"
using namespace CECCO;
int main(void) {
using F = Ext<Fp<2>, {1, 1, 1}, LutMode::CompileTime>;
const size_t n = 17;
const size_t k = 9;
auto gamma = Polynomial<F>();
do {
gamma.randomize(n - k);
} while (gamma[0].is_zero());
auto C = LinearCode<F>(k, gamma);
std::cout << showall << C << std::endl;
auto Cd = C.get_dual();
std::cout << showall << Cd << std::endl;
if (C.is_cyclic()) {
assert(Cd.is_polynomial());
assert(Cd.is_cyclic());
}
// TX
auto u = Vector<F>(k).randomize();
std::cout << "Random message: " << u << std::endl;
auto c = C.enc(u);
const double pe = 0.05;
SDMC<F> channel(pe);
// RX
auto r = channel(c);
try {
auto c_est = C.dec_BD(r);
if (C.is_cyclic()) assert(c_est == C.dec_Meggitt(r));
auto u_est = C.encinv(c_est);
std::cout << "BD decoding message estimate: " << u_est << std::endl;
} catch (const decoding_failure& e) {
std::cout << "BD decoding failure!" << std::endl;
}
auto Cp = SubfieldSubcode(C);
std::cout << showall << Cp << std::endl;
assert(Cp.is_polynomial());
if (C.is_cyclic()) assert(Cp.is_cyclic());
return 0;
}