I need to implement an ECC algorithm on an 8-bit message with 32 bits to work with (32, 8), being new to ECC I started to google and learn a bit about it and ended up coming across two ECC methods, Hamming codes and Reed Solomon. Given that I needed my message to be resilient to 4-8 random bit flips on average I disregarded Hammings and looked into Reed, however, after applying it to my problem I realized it is also not suitable for my use case because while a whole symbol (8 bits) could be flipped, because my errors tend to spread out (on average), it can usually only fix a single error...
Therefore in the end I just settled for my first instinct which is to just copy the data over like so:
00111010 --> 0000 0000 1111 1111 1111 0000 1111 0000
This way every bit is resilient up to 1 error (8 across all bits) by taking the most prominent bits on each actual bit from the encoded message, and every bit can be subject to two bitflips while still detecting there was an error (which is also usable for my use case, eg: input 45: return [45, 173] is still useful).
My question then is if there is any better method, while I am pretty sure there is, I am not sure where to go from here.
By "better method" I mean resilient to even more errors given the (32, 8) ratio.
I made a test program for David Eisenstat's example, to show it works for 1 to 5 bits in error. Code is for Visual Studio.
#include <intrin.h>
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int uint32_t;
/*----------------------------------------------------------------------*/
/* InitCombination - init combination */
/*----------------------------------------------------------------------*/
void InitCombination(int a[], int k, int n) {
for(int i = 0; i < k; i++)
a[i] = i;
--a[k-1];
}
/*----------------------------------------------------------------------*/
/* NextCombination - generate next combination */
/*----------------------------------------------------------------------*/
int NextCombination(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;
}
/*----------------------------------------------------------------------*/
/* Rnd32 - return pseudo random 32 bit number */
/*----------------------------------------------------------------------*/
uint32_t Rnd32()
{
static uint32_t r = 0;
r = r*1664525+1013904223;
return r;
}
static uint32_t codes[256];
/*----------------------------------------------------------------------*/
/* main - test random hamming distance 11 code */
/*----------------------------------------------------------------------*/
int main() {
int ptn[5]; /* error bit indexes */
int i, j, n;
uint32_t m;
int o, p;
for (i = 0; i < 256; i++) { /* generate table */
retry:
codes[i] = Rnd32();
for (j = 0; j < i; j++) {
if (__popcnt(codes[i] ^ codes[j]) < 11) goto retry;
}
}
for(n = 1; n <= 5; n++){ /* test 1 to 5 bit error patterns */
InitCombination(ptn, n, 32);
while(NextCombination(ptn, n, 32)){
for(i = 0; i < 256; i++){
o = m = codes[i]; /* o = m = coded msg */
for(j = 0; j < n; j++){ /* add errors to m */
m ^= 1<<ptn[j];
}
for(j = 0; j < 256; j++){ /* search for code */
if((p =__popcnt(m ^ codes[j])) <= 5)
break;
}
if(i != j){ /* check for match */
printf("fail %u %u\n", i, j);
goto exit0;
}
}
}
}
exit0:
return 0;
}