error-correction - シングルバイトエラー訂正

Question

200 バイトのメッセージには、ランダムな 1 バイトが破損しています。

破損したバイトを修正する最も効率的な方法は何ですか?

Hamming(255,247)コードには 8 バイトのオーバーヘッドがありますが、実装は簡単です。

リードソロモン エラー訂正には 2 バイトのオーバーヘッドがありますが、実装が複雑です。

私が見落としている簡単な方法はありますか？

Answer 1

この場合に最適なメソッドの論文を見つけました.2バイトのオーバーヘッドで、実装が簡単です。コードは次のとおりです。

// 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;
}