对具有高弹性的小消息（8 位）进行纠错，最好的方法是什么？

Question

我需要在一个 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) 比率的情况下能够承受更多的错误。

Answer 1

您可以使用随机化非常轻松地获得距离为 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;
    }
  }
}

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

exit0:
    return 0;
}

对具有高弹性的小消息（8 位）进行纠错，最好的方法是什么？

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

algorithm

error-correction

reed-solomon

hamming-code