Код проверки кода Хэмминга

Question

Я не уверен, правильно ли я вычисляю бит четности для функции битов контроля четности, которую я написал. CodeWord имеет длину 11 символов с 4 битами четности и 7 бит данных. Отличается ли реализация?

void parityCheck(char* codeWord) { 
int parity[4] = {0}, i = 0, diffParity[4] = {0}, twoPower = 0, bitSum = 0; 

// Stores # of 1's for each parity bit in array. 
parity[0] = (codeWord[2] - 48) + (codeWord[4] - 48) + (codeWord[6] - 48) + (codeWord[8] - 48) + (codeWord[10] - 48); 
parity[1] = (codeWord[2] - 48) + (codeWord[5] - 48) + (codeWord[6] - 48) + (codeWord[9] - 48) + (codeWord[10] - 48); 
parity[2] = (codeWord[4] - 48) + (codeWord[5] - 48) + (codeWord[6] - 48); 
parity[3] = (codeWord[8] - 48) + (codeWord[9] - 48) + (codeWord[10] - 48); 

// Determines if sum of bits is even or odd, then tests for difference from actual parity bit. 
for (i = 0; i < 4; i++) { 
    twoPower = (int)pow((double)2, i); 

    if (parity[i] % 2 == 0) 
      parity[i] = 0; 
     else 
      parity[i] = 1; 

     if ((codeWord[twoPower-1] - 48) != parity[i]) 
      diffParity[i] = 1; 
} 

// Calculates the location of the error bit. 
for (i = 0; i < 4; i++) { 
    twoPower = (int)pow((double)2, i); 
    bitSum += diffParity[i]*twoPower; 
} 



// Inverts bit at location of error. 
if (bitSum <= 11 && bitSum > 0) { 
    if ((codeWord[bitSum-1] - 48)) 
     codeWord[bitSum-1] = '0'; 
    else 
     codeWord[bitSum-1] = '1'; 
} 

Answer 1

ли реализация хорошо выглядеть?

Это очень зависит от вашей меры для «хорошего». Я могу подтвердить, что он выполняет эту работу, по крайней мере, это правильно. Ваш код очень многословный, и поэтому трудно проверить правильность. Я хотел бы сделать следующее:

int parity_check(int codeWord) { 
    int parity = 0, codeWordBit, bitPos; 
    for (bitPos = 1; bitPos <= 11; ++bitPos) { 
    codeWordBit = ((codeWord >> (bitPos - 1)) & 1); 
    parity ^= bitPos*codeWordBit; 
    } 
    if (parity != 0) { 
    if (parity > 11) 
     return -1; // multi-bit error! 
    codeWord ^= 1 << (parity - 1); 
    } 
    return codeWord; 
} 

Вместо последовательности цифровых символов, я лечу все кодовое слово как единое целое, что является намного более эффективным.

Глядя на the table at Wikipedia, я вижу, что столбцы из этой таблицы образуют двоичные представления последовательности 1 ... 11. Каждое кодовое слово бит влияет именно те биты четности, указанные в этой колонке, поэтому я беру немного кодовое слово (который равен нулю или один), умножьте его на бит-шаблон этого столбца, чтобы получить либо этот шаблон, либо нуль, а затем XOR с текущей битовой диаграммой четности. Эффект от этого заключается в том, что бит нулевого кодового слова ничего не изменит, тогда как бит ненулевого кодового слова переворачивает все связанные биты четности.

Следует проявлять определенную осторожность, поскольку бит-бит является однонаправленным, в то время как позиция бита, использующая трюк правой смены, основана на нулевом значении. Поэтому я должен вычесть его, а затем сдвинуть вправо на эту сумму, а затем извлечь младшую значащую цифру, чтобы получить codeWordBit.

Используя мою реализацию для справки, я смог verify (by complete enumeration), что ваш код работает так же.

Answer 2

Ваш код работает отлично AFAIK, поскольку он прошел тестовые примеры, которые я создал. Были сделаны некоторые упрощения, но функциональность OP не изменилась. Для упрощения просмотра были сделаны некоторые классические упрощения.

void parityCheck(char* cW) { 
    int parity[4] = { 0 }, i = 0, diffParity[4] = { 0 }, twoPower = 0, bitSum = 0; 

    // Stores # of 1's for each parity bit in array. 
    parity[0] = (cW[2] - '0') + (cW[4] - '0') + (cW[6] - '0') + (cW[8] - '0') + (cW[10] - '0'); 
    parity[1] = (cW[2] - '0') + (cW[5] - '0') + (cW[6] - '0') + (cW[9] - '0') + (cW[10] - '0'); 
    parity[2] = (cW[4] - '0') + (cW[5] - '0') + (cW[6] - '0'); 
    parity[3] = (cW[8] - '0') + (cW[9] - '0') + (cW[10] - '0'); 

    // Determines if sum of bits is even or odd, then tests for difference from actual parity bit. 
    for (i = 0; i < 4; i++) { 
    //twoPower = (int) pow((double) 2, i); 
    twoPower = 1 << i; 
    //if (parity[i] % 2 == 0) parity[i] = 0; else parity[i] = 1; 
    parity[i] &= 1; // Make 0 even, 1 odd. 
    if ((cW[twoPower - 1]-'0') != parity[i]) 
     diffParity[i] = 1; 
    } 

    // Calculates the location of the error bit. 
    for (i = 0; i < 4; i++) { 
    // twoPower = (int) pow((double) 2, i); 
    twoPower = 1 << i; 
    bitSum += diffParity[i] * twoPower; 
    } 

    // Inverts bit at location of error. 
    if (bitSum <= 11 && bitSum > 0) { 
    if ((cW[bitSum - 1]-'0')) 
     cW[bitSum - 1] = '0'; 
    else 
     cW[bitSum - 1] = '1'; 
    } 
} 

void TestP(const char * Test) { 
    char buf[100]; 
    strcpy(buf, Test); 
    parityCheck(buf); 
    printf("'%s' '%s'\n", Test, buf); 
} 


int main(void) { 
    TestP("00000000000"); 
    TestP("10011100101"); 
    TestP("10100111001"); 
} 

Было бы полезно использовать тестовые образцы OP.

Answer 3

Вот моя реализация. Оно работает. Публика может свободно пользоваться ею бесплатно.

Я использовал аббревиатуру «secded», как в «исправлении с ошибкой с одной ошибкой, с двойной ошибкой». Вы можете повторно подключить это как «детектор тройных ошибок», если хотите этого. На самом деле, небольшая часть этого времени закрыта, а остальное Хэмминг 7,4 - но я назвал эти методы тем, что я сделал, когда я это сделал.

«Строки» здесь не имеют NUL-терминацию, но считаются. Этот код выписывается из модуля Python, написанного на C. Это доказуемость типа строки, который вы видите.

Ключевым моментом здесь было осознание того, что всего 16 кодов Хэмминга 7,4. Я вычислил secded_of_nibble() с некоторым кодом Python, которого, к сожалению, я больше не имею.

static const unsigned char secded_of_nibble[] = 
{ 0x0, 0xd2, 0x55, 0x87, 0x99, 0x4b, 0xcc, 0x1e, 0xe1, 0x33, 0xb4, 0x66, 0x78, 0 
xaa, 0x2d, 0xff }; 

int fec_secded_encode_cch_bits(const char * strIn, const int cchIn, char * strOu 
t, const int cchOut) 
{ 
    assert(cchIn * 2 == cchOut); 
    if(cchIn * 2 != cchOut) 
     return 0; 

    if (!strIn || !strOut) 
     return 0; 

    int i; 
    for (i = 0; i < cchIn; i ++) 
    { 
     char in_byte = strIn[i]; 
     char hi_byte = secded_of_nibble[(in_byte >> 4) & 0xf]; 
     char lo_byte = secded_of_nibble[in_byte & 0xf]; 

     strOut[i * 2] = hi_byte; 
     strOut[i * 2 + 1] = lo_byte; 
    } 

    return 1; 
} 

char bv_H[] = {0x9, 0xA, 0xB, 0xC, 0xD, 0xE, 0xF, 0x8}; 

char val_nibble(char ch) 
{ 
    return ((ch & 0x20) >> 2) | ((ch & 0xE) >> 1); 
} 

char correct_nibble(char ch) 
{ 
    char nibble = 0; 
    int i = 0; 
    for (i = 0; i < 8; i++) 
    if (ch & (1 << (7-i))) 
     nibble ^= bv_H[i]; 

    return nibble; 
} 

void apply_correct(char nib_correct, char * pbyte, int * pcSec, int *pcDed) 
{ 
    if (0 == nib_correct) 
     return; 

    if (nib_correct & 0x8) 
    { 
     (*pcSec) ++; 

     int bit = (8 - (nib_correct & 0x7)) & 0x7; 
     /* fprintf(stderr, "bit %d, %02X\n", bit, 1 << bit);*/ 
     (*pbyte) ^= (1 << bit); 
    } 
    else 
    { 
     (*pcDed) ++; 
    } 
} 

int fec_secded_decode_cch_bits 
(
    const char * strIn, 
    const int cchIn, 
    char * strOut, 
    const int cchOut, 
    int * pcSec, 
    int * pcDed 
) 
{ 
    assert(cchIn == cchOut *2); 
    if(cchIn != cchOut * 2) 
     return 0; 

    if (!strIn || !strOut) 
     return 0; 

    int i; 
    for (i = 0; i < cchOut; i ++) 
    { 
     char hi_byte = strIn[i * 2]; 
     char lo_byte = strIn[i * 2 + 1]; 


     char hi_correct = correct_nibble(hi_byte); 
     char lo_correct = correct_nibble(lo_byte); 

     if (hi_correct || lo_correct) 
     { 
      apply_correct(hi_correct, &hi_byte, pcSec, pcDed); 
      apply_correct(lo_correct, &lo_byte, pcSec, pcDed); 
/*   fprintf(stderr, "Corrections %x %x.\n", hi_correct, lo_correct);*/ 
     } 

     char hi_nibble = val_nibble(hi_byte); 
     char lo_nibble = val_nibble(lo_byte); 

     strOut[i] = (hi_nibble << 4) | lo_nibble; 
    } 

    return 1; 
}