1

我不确定我是否为我编写的校验奇偶校验位函数正确计算奇偶校验位。代码字长 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';
}
4

3 回答 3

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

我将您的整个代码字视为一个整数，而不是一系列数字字符，这样效率更高。

查看Wikipedia 上的表格，我看到该表格的列形成序列 1 ... 11 的二进制表示。每个码字位都会影响该列中提到的奇偶校验位，因此我采用码字位（为零或一），将其乘以该列的位模式以获得该模式或零，然后将其与当前奇偶校验位模式进行异或。这样做的效果是零码字位不会改变任何东西，而非零码字位会翻转所有相关的奇偶校验位。

必须小心，因为位模式是从一​​开始的，而使用右移技巧的位位置是从零开始的。所以我必须减去一个，然后向右移动那个数量，然后提取最低有效位以获得codeWordBit.

使用我的实现作为参考，我能够（通过完整的枚举）验证您的代码是否相同。

于 2013-08-02T13:30:15.463 回答
0

您的代码运行良好 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 发布了测试模式，那将会很有用。

于 2013-08-02T13:48:25.783 回答
-1

这是我的实现。有用。公众可以免费使用它。

我使用了首字母缩略词“secded”，如“单纠错，双错误检测”。如果需要，您可以将其重新连接为“三重错误检测器”。真的，其中一小部分是 secded，其余的是 Hamming 7,4——但我将这些方法命名为我所做的，当我做的时候。

这里的“字符串”不是以 NUL 结尾的，而是计数的。此代码摘自用 C 编写的 Python 模块。这是您看到的字符串类型的出处。

这里的一个关键点是意识到只有 16 个汉明 7,4 码。我用一些 Python 代码计算了 secded_of_nibble()，不幸的是我不再拥有这些代码。

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;
}
于 2013-08-02T14:17:41.483 回答