高弹性的小报文(8位)纠错，最好的方法是什么?

Question

我需要在8位消息上实现一个ECC算法，其中32位可以使用(32,8)，作为ECC的新手，我开始谷歌并学习一些关于它的知识，并最终遇到两种ECC方法，汉明码和里德所罗门。考虑到我需要我的消息平均能够适应4-8个随机位翻转，我忽略了汉明斯并研究了里德，然而，在将其应用于我的问题之后，我意识到它也不适合我的用例，因为虽然整个符号(8位)可以翻转，但由于我的错误倾向于扩散(平均)，它通常只能修复单个错误…

因此，最后我只是满足于我的第一直觉，即只是复制数据，像这样:

00111010 --> 0000 0000 1111 1111 1111 0000 1111 0000

这样，通过从编码消息中获取每个实际位上最突出的位，每个位都可以恢复到1个错误(8个所有位)，并且每个位可以受到两个位翻转，同时仍然检测到有一个错误(这也可用于我的用例，例如:input 45: return [45, 173]仍然有用)。

我的问题是，如果有更好的方法，虽然我很确定有，我不知道从这里去哪里。

通过"更好的方法";我的意思是，考虑到(32,8)的比率，我的意思是能够承受更多的错误。

Answer 1

使用随机化可以很容易地获得距离-11代码。

#include <stdio.h>
#include <stdlib.h>
int main() {
uint32_t codes[256];
for (int i = 0; i < 256; i++) {
printf("%dn", i);
retry:
codes[i] = arc4random();
for (int j = 0; j < i; j++) {
if (__builtin_popcount(codes[i] ^ codes[j]) < 11) goto retry;
}
}
}

Answer 2

我为David Eisenstat的例子做了一个测试程序，以显示它可以在1到5位错误中工作。代码是为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 %un", i, j);
goto exit0;
}
}
}
}
exit0:
return 0;
}