Reputation: 6675
What error correcting code to use for short messages over noisy channel using confidence info for each bit (possible with transmission markers)
I have short (assume 24 to 30 bit long) message to send over a noisy channel. Additionally, the channel allows only sending 0 or 1, without "silence", so start transmission marker is needed. For each bit I receive I have confidence from 0.0 (we don't know which bit was sent at all) to 1.0 (we are certain that given bit was sent) - this can be easily translated to different range like: -127 (ceraint '0') ... 0 (no idea what was sent) ... 127 (certain 1).
For now I used this excelent answer: https://stackoverflow.com/a/79145998/207717 to my previous question, together with some naive start-transmission markers to get fairly good results, but I don't use confidence values for received bits nor anything advanced for start-transmission-markers, so I'm sure that can be improved.
I've read about some advanced error correcting codes, used in wireless communication, 5G and space missions like:
- https://en.wikipedia.org/wiki/Turbo_code
- https://en.wikipedia.org/wiki/Binary_Golay_code
- https://en.wikipedia.org/wiki/Reed%E2%80%93Muller_code
But this quickly turns into a deep rabbit hole with very advanced math. I would expect some libraries implementing these solutions that are not patented, but I cannot find anything above CRC, Reed Solomon and some BCH. Could you recommend best practical approach? Computational performance is not important, simple, reference, implementation in python would be enough.
Upvotes: 0
Views: 209
Answers (1)
Reputation: 28826
Since the 4 bit correction + 7 bit detection method uses 30 bits of data, you could use a (15,11) BCH | CRC code, 11 bits of data, 4 bits of parity, either x^4 + x + 1 (hex 13) or x^4 + x^3 + 1 (hex 19), plus a separate even parity bit to to end up with a (16,11) code. The 11 bits of data would be 0x000 to 0x0FF for data, and 0x555 for marker.
This code can do single bit correction + double bit detection. If there are 3 error bits, then the single bit correction could fail and produce a 4th bad bit. The unknown is the bit error rate. If most of the errors are single bit errors, those get fixed.
You could continue to use the 30 bit data + 33 bits parity correction I posted before, but since the (16,11) code produces 10 bit data values, you could switch to a Reed Solomon code that operates on 10 bit elements, using a (16,12) or (16,10) code.
Example C# code. Since this is single bit correction, a CRC type method can be used for correction for the 15 bit part. A CRC is generated for the received 15 bits, then cycled backwards, setting a bit to xor if or when the backwards cycled CRC == 0x08.
// bchq16.cs 16bit codeword, GF(2^4) + parity
// correct 1 bit, detect 2 bits
// 2024NOV14 15:00
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;
using System.Numerics;
namespace xcs
{
public class Program
{
const byte POLY = 0x13; // GF(2^4) = x^4 + x + 1
const byte ALPHA = 0x02;
static Vector128<ulong> poly; // generator poly
static Vector128<ulong> invpoly; // 2^64 / POLY
static Vector128<ulong> msg; // message
static Vector128<ulong> rem; // remainder
static Vector128<ulong> ren; // reencode
static ulong msgorg; // original message
static ulong msgenc; // encoded message
static ulong msgerr; // received message
static ulong msgfix; // fixed message
static ulong msgpar; // parity
static void GenPoly()
{
ulong M;
ulong N;
ulong Q;
int x;
byte i;
poly = Vector128.Create((ulong)POLY, 0x0000000000000000ul);
// generate 2^64 / poly
x = 63-BitOperations.LeadingZeroCount(poly.GetElement(0));
M = 1ul<<x;
N = M>>1;
Q = 0x0ul;
for(i = 0; i < 65-x; i++){
N <<= 1;
Q <<= 1;
if(0 != (N&M)){
Q |= 1;
N ^= (poly.GetElement(0));
}
}
invpoly = Vector128.Create(Q, 0x0000000000000000ul);
}
static void Encode()
{
Remainder(); // generate remainder
msg ^= rem; // msg[0] = encoded message
}
static void Remainder()
{
rem = Pclmulqdq.CarrylessMultiply(msg, invpoly, 0x00); // rem[1] = quotient
rem = Pclmulqdq.CarrylessMultiply(rem, poly, 0x01); // rem[0] = product
rem ^= msg; // rem[0] = remainder
}
static void FixError()
{
ulong crc;
ulong fix = 0;
byte i;
/* reencode crc */
#if false
crc = msg.GetElement(0);
for (i = 0; i < 15; i++){
crc <<= 1;
if(0x0ul != (crc & 0x8000ul))
crc ^= POLY<<11;
}
crc >>= 11;
#else
ren = Vector128.Create(msg.GetElement(0)<<4, 0x0000000000000000ul);
rem = Pclmulqdq.CarrylessMultiply(ren, invpoly, 0x00); // rem[1] = quotient
rem = Pclmulqdq.CarrylessMultiply(rem, poly, 0x01); // rem[0] = product
rem ^= ren; // rem[0] = reencode
crc = rem.GetElement(0);
#endif
/* reverse cycle crc, fix 0 or 1 error */
for (i = 0; i < 15; i++){
crc = (0x0ul != (crc&1))?(crc^POLY)>>1:(crc)>>1;
if(crc == 0x0008ul)
fix ^= 1ul<<i;
}
fix ^= msg.GetElement(0);
msg = Vector128.Create(fix, 0x0000000000000000ul);
}
static void InitCombination(ref int[] a, int k, int n)
{
for (int i = 0; i < k; i++)
a[i] = i;
--a[k - 1];
}
static int NextCombination(ref int[] a, int k, int n)
{
int pivot = k - 1;
while (pivot >= 0 && a[pivot] == n - k + pivot)
--pivot;
if (pivot == -1)
return 0;
++a[pivot];
for (int i = pivot + 1; i < k; ++i)
a[i] = a[pivot] + i - pivot;
return 1;
}
static int Main(string[] args)
{
int[] ptn = new int[2]; // error bit indexes
int n; // number of errors to test
int i;
GenPoly();
msgorg = 0x0000000000005550ul; // test message
msg = Vector128.Create(msgorg, 0x0000000000000000ul);
Encode();
msgenc = msg.GetElement(0)<<1;
msgenc ^= (ulong)(BitOperations.PopCount(msgenc)&1);
for (n = 1; n <= 2; n++){ // test 1 to 2 bit error patterns
InitCombination(ref ptn, n, 16);
while (0 != NextCombination(ref ptn, n, 16)){
msgerr = msgenc;
for (i = 0; i < n; i++)
msgerr ^= 1ul<<ptn[i];
msgpar = (ulong)(BitOperations.PopCount(msgerr)&1);
msgerr >>= 1;
msg = Vector128.Create(msgerr, 0x0000000000000000ul);
msgfix = msgerr;
Remainder(); // generate remainder
if(0ul == rem.GetElement(0)){ // if rmndr == 0
msgfix <<= 1; // regenerate parity bit
msgfix ^= (ulong)(BitOperations.PopCount(msgfix)&1);
if(msgfix != msgenc){ // check for failure
Console.WriteLine("failed");
return 0;}
continue;
}
if(msgpar == 0ul) // if error but even parity
continue; // detected error
FixError(); // assume 1 bit error
msgfix = msg.GetElement(0);
if(msgfix == msgerr) // if not 1 bit error
continue; // detected error
msgfix <<= 1; // regenerate parity bit
msgfix ^= (ulong)(BitOperations.PopCount(msgfix)&1);
if(msgfix != msgenc){ // check for fixed
Console.WriteLine("failed");
return 0;}
}
}
Console.WriteLine("passed");
return 0;
}
}
}
CRC(24,11), 13 bit CRC, fix 2 bit + detect 5 bit or fix 3 bit + detect 4 bit. Both 12 bit and 13 bit CRC have Hamming distance 8 for 11 data bits, 13 bit CRC used so codeword is 24 bits instead of 23 bits.
// crc24.cs 24 bit codeword, 11 bit data, 13 bit crc
// 2024NOV20 18:00
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;
using System.Numerics;
namespace xcs
{
public class Program
{
#if true
const uint FIX = 2; // fix 2
const uint DET = 5; // detect 5
#else
const uint FIX = 3; // fix 3
const uint DET = 4; // detect 4
#endif
#if true
const ulong POLY = 0x216F; // AE3*3*3
#else
const ulong POLY = 0x3DA1; // C75*3*3
#endif
static uint[] fixtbl = new uint[8192]; // fix table
static Vector128<ulong> poly; // generator poly
static Vector128<ulong> invpoly; // 2^64 / POLY
static Vector128<ulong> msg; // message
static Vector128<ulong> par; // parities
static ulong msgorg; // original message
static ulong msgenc; // encoded message
static ulong msgerr; // received message
static ulong msgfix; // fixed message
static void GenPoly()
{
int[] ptn = new int[8]; // error bit indexes
ulong M;
ulong N;
ulong Q;
int i;
int n;
int x;
poly = Vector128.Create(POLY, 0ul);
// generate 2^64 / poly
x = 63-BitOperations.LeadingZeroCount(poly.GetElement(0));
M = 1ul<<x;
N = M>>1;
Q = 0x0ul;
for(i = 0; i < 65-x; i++){
N <<= 1;
Q <<= 1;
if(0 != (N&M)){
Q |= 1;
N ^= (poly.GetElement(0));
}
}
invpoly = Vector128.Create(Q, 0ul);
// init fix table
fixtbl[0] = 0;
for(i = 1; i < 8192; i++)
fixtbl[i] = 0xffffffffu;
for(n = 1; n <= FIX; n++)
{ // fix 1 to FIX bit error
InitCombination(ref ptn, n, 24);
while(0 != NextCombination(ref ptn, n, 24))
{
msgfix = 0ul;
for(i = 0; i < n; i++)
msgfix ^= 1ul << ptn[i];
msg = Vector128.Create(msgfix, 0ul);
par = Pclmulqdq.CarrylessMultiply(msg, invpoly, 0x00); // par[1] = quotient
par = Pclmulqdq.CarrylessMultiply(par, poly, 0x01); // par[0] = product
par ^= msg; // par[0] = crc
fixtbl[par.GetElement(0)] = (uint)msgfix;
}
}
}
static void Encode()
{
Remainder(); // generate remainder
msg ^= par; // msg[0] = encoded message
}
static void Remainder()
{
par = Pclmulqdq.CarrylessMultiply(msg, invpoly, 0x00); // par[1] = quotient
par = Pclmulqdq.CarrylessMultiply(par, poly, 0x01); // par[0] = product
par ^= msg; // par[0] = crc
}
static bool FixError()
{
par = Pclmulqdq.CarrylessMultiply(msg, invpoly, 0x00); // par[1] = quotient
par = Pclmulqdq.CarrylessMultiply(par, poly, 0x01); // par[0] = product
par ^= msg; // par[0] = crc
par = Vector128.Create(fixtbl[par.GetElement(0)],0ul); // par[0] = fix pattern
if(par.GetElement(0) == 0xfffffffful)
return false;
msg ^= par;
return true;
}
static void InitCombination(ref int[] a, int k, int n)
{
for(int i = 0; i < k; i++)
a[i] = i;
--a[k - 1];
}
static int NextCombination(ref int[] a, int k, int n)
{
int pivot = k - 1;
while(pivot >= 0 && a[pivot] == n - k + pivot)
--pivot;
if(pivot == -1)
return 0;
++a[pivot];
for(int i = pivot + 1; i < k; ++i)
a[i] = a[pivot] + i - pivot;
return 1;
}
static int Main(string[] args)
{
int[] ptn = new int[8]; // error bit indexes
int n; // number of errors to test
int i;
GenPoly();
msgorg = 0x0000000000ffe000ul; // test message
msg = Vector128.Create(msgorg, 0ul);
Encode();
msgenc = msg.GetElement(0);
for(n = 1; n <= DET; n++){ // test 1 to DET bit error patterns
InitCombination(ref ptn, n, 24);
while(0 != NextCombination(ref ptn, n, 24)){
msgerr = msgenc;
for(i = 0; i < n; i++)
msgerr ^= 1ul<<ptn[i];
msg = Vector128.Create(msgerr, 0ul);
msgfix = msgerr;
if(!FixError()) // if not correctable
continue; // continue
msgfix = msg.GetElement(0);
if(msgfix != msgenc){
Console.WriteLine("failed");
return 0;}
}
}
Console.WriteLine("passed");
return 0;
}
}
}
Upvotes: 0