Single-Byte Error Correction

Question

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?

score 1 · Accepted Answer · answered May 02 '13 at 05:57

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

The code above is flawed, it returns `true` on parity errors and uncorrectable errors - at least it should be noted in a comment :) I'd love to read the paper describing the algorithm, but it costs $19 so meh.. — Morten Jensen, Feb 01 '14 at 18:03
Parity errors don't need to be corrected -- the data is fine. Other uncorrectable errors (multibyte, etc) can't reliably be detected by this code, so it returning 'true' in some cases is unsurprising. — rmmh, Feb 02 '14 at 01:31
Thanks for replying :) I've been fiddling with your code and this book: http://bit.ly/LFfpmt trying to figure out some properties about it and CA-based codes in general :) — Morten Jensen, Feb 03 '14 at 01:30
Sketch: xor-sum gives us what the error mask was. We then need a function where f(data+error)=f(data)+f(error) -- f is additive -- and f(x) is different depending on the location. (Note that + in binary Galois fields is XOR). f(x) needs to have 255 different outputs depending on position-- and the easiest way to get every possible output is a Linear Feedback Shift Register, which also has the additive properties we need. — rmmh, Feb 03 '14 at 06:47

rcgldr · Answer 2 · 2017-02-21T06:28:41.393

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.

Single-Byte Error Correction

2 Answers2