2

我需要在 32 位的 8 位消息上实现 ECC 算法，以便与 (32, 8) 一起使用，对于 ECC 来说是新手和里德所罗门。鉴于我需要我的消息平均能够适应 4-8 次随机位翻转，因此我忽略了 Hammings 并研究了 Reed，但是，在将其应用于我的问题之后，我意识到它也不适合我的用例，因为虽然整个符号（8位）可以翻转，因为我的错误倾向于分散（平均），它通常只能修复一个错误......

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

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

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

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

通过“更好的方法”，我的意思是在 (32, 8) 比率下对更多错误具有弹性。

4

2 回答 2

2

您可以使用随机化很容易地获得距离为 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;
    }
  }
}
于 2021-09-09T17:21:29.163 回答
1

我为 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;
}
于 2021-09-10T08:38:57.063 回答