algorithmerror-correctionreed-solomonhamming-code# Error correction on small message (8-Bit) with high resilience, what is the best method?

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.*

Solution

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;
}
```

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array