Single-Byte Error Correction

3
votes

A 200 byte message has one random byte corrupted.

What's the most efficient way to fix the corrupt byte?

A Hamming(255,247) code has 8 bytes of overhead, but is simple to implement.

Reed-Solomon error correction has 2 bytes of overhead, but is complex to implement.

Is there a simpler method that I'm overlooking?

2
error-correctionhamming-codereed-solomon

2 Answers

1
votes

I found a paper of a method that's perfect for this case-- two bytes overhead, simple to implement. Here's the code:

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

Using Reed Solomon to correct a single byte error would not be that complicated. Use a generator polynomial of the form (using ⊕ to mean xor)

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

Encode the message as usual.

For decode, generate the two syndromes S(0) and S(1) in the normal way.

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

Error location would be from right to left (0 == right most byte). If a shortened code and location is out of range, then an uncorrectable error is detected.