对具有高弹性的小消息(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;
}
我需要在一个 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;
}