Коррекция ошибок одного байта

Question

200-байтовое сообщение имеет один случайный байт, поврежденный.

Каков наиболее эффективный способ исправить поврежденный байт?

A Hamming(255,247) код имеет 8 байт служебных данных, но его просто реализовать.

Reed-Solomon error correction имеет 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

Использование Рида Соломона для исправления ошибки одного байта не так уж сложно. С помощью порождающего многочлена вида (с использованием ⊕ означает XOR)

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 == right most byte). Если сокращенный код и местоположение находятся за пределами допустимого диапазона, то обнаруживается некорректируемая ошибка.