error-correction - 单字节纠错

Question

200 字节的消息有一个随机字节损坏。

修复损坏字节的最有效方法是什么？

Hamming(255,247)码有 8 个字节的开销，但实现起来很简单。

Reed-Solomon 纠错有 2 个字节的开销，但实现起来很复杂。

有没有我忽略的更简单的方法？

Answer 1

我找到了一篇关于这种情况的完美方法的论文——两个字节的开销，易于实现。这是代码：

// Single-byte error correction for messages <255 bytes long
//  using two check bytes. Based on "CA-based byte error-correcting code"
//  by Chowdhury et al.
//
// rmmh 2013

uint8_t lfsr(uint8_t x) {
    return (x >> 1) ^ (-(x&1) & 0x8E);
}

void eccComputeChecks(uint8_t *data, int data_len, uint8_t *out_c0, uint8_t *out_c1) {
    uint8_t c0 = 0; // parity: m_0 ^ m_1 ^ ... ^ m_n-1
    uint8_t c1 = 0; // lfsr: f^n-1(m_0) ^ f^n(m_1) ^ ... ^ f^0(m_n-1)
    for (int i = 0; i < data_len; ++i) {
        c0 ^= data[i];
        c1 = lfsr(c1 ^ data[i]);
    }
    *out_c0 = c0;
    *out_c1 = c1;
}

void eccEncode(uint8_t *data, int data_len, uint8_t check[2]) {;
    eccComputeChecks(data, data_len, &check[0], &check[1]);
}

bool eccDecode(uint8_t *data, int data_len, uint8_t check[2]) {
    uint8_t s0, s1;
    eccComputeChecks(data, data_len, &s0, &s1);
    s0 ^= check[0];
    s1 ^= check[1];
    if (s0 && s1) {
        int error_index = data_len - 255;
        while (s1 != s0) {  // find i st s1 = lfsr^i(s0) 
            s1 = lfsr(s1);
            error_index++;
        }
        if (error_index < 0 || error_index >= data_len) {
            // multi-byte error?
            return false;
        }
        data[error_index] ^= s0;
    } else if (s0 || s1) {
        // parity error
    }
    return true;
}

Answer 2

使用 Reed Solomon 来纠正单个字节错误不会那么复杂。使用形式的生成多项式（使用⊕表示异或）

g(x) = (x ⊕ 1)(x ⊕ 2) = x^2 + 3x + 2.

像往常一样对消息进行编码。

对于解码，以正常方式生成两个校正子 S(0) 和 S(1)。

if(S(0) != 0){
    error value = S(0)
    error location = log2(S(1)/S(0))
}

错误位置从右到左（0 == 最右边的字节）。如果缩短的代码和位置超出范围，则检测到不可纠正的错误。