对具有高弹性的小消息(8 位)进行纠错,最好的方法是什么?

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

我需要在一个 8 位消息上实现一个 ECC 算法,32 位可以与 (32, 8) 一起使用,作为 ECC 的新手,我开始 google 并了解了一些,然后结束了遇到两种 ECC 方法,Hamming 码和 Reed Solomon。考虑到我需要我的消息对平均 4-8 次随机位翻转具有弹性,我忽略了 Hammings 并研究了 Reed,但是,在将其应用于我的问题之后,我意识到它也不适合我的用例,因为虽然整个符号(8 bits) could be flipped,因为我的错误倾向于分散(平均),它通常只能修复一个错误...

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

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

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

我的问题是是否有更好的方法,虽然我很确定有,但我不确定从这里去哪里。

我所说的“更好的方法”是指在给定 (32, 8) 比率的情况下能够承受更多的错误。

您可以使用随机化非常轻松地获得距离为 11 的代码。

#include <stdio.h>
#include <stdlib.h>

int main() {
  uint32_t codes[256];
  for (int i = 0; i < 256; i++) {
    printf("%d\n", i);
  retry:
    codes[i] = arc4random();
    for (int j = 0; j < i; j++) {
      if (__builtin_popcount(codes[i] ^ codes[j]) < 11) goto retry;
    }
  }
}

我为 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 %u\n", i, j);
                    goto exit0;
                }
            }
        }
    }

exit0:
    return 0;
}