用基本CRC C++子程序实现CCSDS (64，56)FEC码

Question

我已经使用C++中的一个非常基本的CRC子例程创建了一个CCSDS BCH(64,56)编码器。我打算在GNU无线电应用程序中使用它。BCH(64,56)码块的格式如下所示。

。可以组合一组码块以形成被称为通信链路传输单元(CLTU)的数据单元，如下所示。

​

据我所知，BCH和CRC都会在数据的末尾添加一个“余数/奇偶校验”，使用相同的计算形式，如this线程中所述。

我所要做的就是修改一个标准的CRC C++ crcFast() subroutine 。该子例程通过迭代通过给定多项式(crcInit())预初始化的数组(表)来计算CRC。下面的代码显示了两个子例程crcInit()和crcFast()。

typedef unsigned char uint8_t;
typedef unsigned short crc;
#define WIDTH (8 * sizeof(crc))
#define TOPBIT (1 << (WIDTH - 1))
crc crcTable[256];
#define POLYNOMIAL 0xD8  /* 11011 followed by 0's */
void
crcInit(void)
{
    crc remainder;


    /*
* Compute the remainder of each possible dividend.
*/
    for (int dividend = 0; dividend < 256; ++dividend)
    {
        /*
* Start with the dividend followed by zeros.
*/
        remainder = dividend << (WIDTH - 8);

        /*
* Perform modulo-2 division, a bit at a time.
*/
        for (uint8_t bit = 8; bit > 0; --bit)
        {
            /*
* Try to divide the current data bit.
*/
            if (remainder & TOPBIT)
            {
                remainder = (remainder << 1) ^ POLYNOMIAL;
            }
            else
            {
                remainder = (remainder << 1);
            }
        }

        /*
* Store the result into the table.
*/
        crcTable[dividend] = remainder;
    }

} /* crcInit() */


crc
crcFast(uint8_t const message[], int nBytes)
{
    uint8_t data;
    crc remainder = 0;


    /*
     * Divide the message by the polynomial, a byte at a time.
     */
    for (int byte = 0; byte < nBytes; ++byte)
    {
        data = message[byte] ^ (remainder >> (WIDTH - 8));
        remainder = crcTable[data] ^ (remainder << 8);
    }

    /*
     * The final remainder is the CRC.
     */
    return (remainder);

}   /* crcFast() */

修改后的代码如下所示。表生成函数crcInit()保持不变。crcFast算法已稍作修改，以纳入格式指定的奇偶校验字节(补码和填充位)上的更改。CRC类型已从短字符更改为无符号字符(1字节)。由g(x) = x^7 +x^6 + x^2 + 1给出的删除型汉明码中的BCH(64,56)，对我来说相当于0xC5。

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <vector>
#include <iostream>
#include "debug.h"
typedef unsigned char uint8_t;
typedef unsigned char crc;
#define WIDTH  (8 * sizeof(crc))
#define TOPBIT (1 << (WIDTH - 1))
crc  crcTable[256];
#define POLYNOMIAL 0xC5  // x^7 + x^6 + x^2 + 1
#define INITIAL_REMAINDER 0x00
#define BCH_INFORMATION_BLOCK 7
void
crcInit(void)
{
    crc  remainder;


    /*
     * Compute the remainder of each possible dividend.
     */
    for (int dividend = 0; dividend < 256; ++dividend)
    {
        /*
         * Start with the dividend followed by zeros.
         */
        remainder = dividend << (WIDTH - 8);

        /*
         * Perform modulo-2 division, a bit at a time.
         */
        for (uint8_t bit = 8; bit > 0; --bit)
        {
            /*
             * Try to divide the current data bit.
             */         
            if (remainder & TOPBIT)
            {
                remainder = (remainder << 1) ^ POLYNOMIAL;
            }
            else
            {
                remainder = (remainder << 1);
            }
        }

        /*
         * Store the result into the table.
         */
        crcTable[dividend] = remainder;
    //std::cout << "Remainder from table : " << int (remainder&0xffff) << std::endl;
    }

}   /* crcInit() */

void
crcEncoder(std::vector<unsigned char> &message, const crc initial_remainder)
{
    uint8_t data;
    crc remainder = initial_remainder;

    /*
     * Divide the message by the polynomial, a byte at a time.
     */
    for (int byte = 0; byte < message.size(); ++byte)
    {
        data = message.at(byte) ^ (remainder >> (WIDTH - 8));
        remainder = crcTable[data] ^ (remainder << 8);
    }

    //Flip the remainder and move by 1 bit
    remainder ^= 0xFF;
    remainder <<= 1;

    //Set filler bit to 0 (anding with 1111 1110)
    remainder &= 0xFE;

    /*
     * The final remainder is the CRC.
     */
    message.push_back(remainder);
    //return message;
}


void bchEncoder(std::vector<unsigned char> &message)
{
    std::vector<unsigned char> information; // 7 bytes
    std::vector<unsigned char> codewords; // Encoded message

    //Ensure integral information symbols
    while(!(message.size() % BCH_INFORMATION_BLOCK) == 0)
      {
        message.push_back(0x55);
      }

    for(int i = 0; i < message.size(); i += BCH_INFORMATION_BLOCK)
    {
        //Copy 7 information bytes
        std::copy(message.begin() + i, message.begin() + i + BCH_INFORMATION_BLOCK,
                      std::back_inserter(information));
        //BCH encoding
        crcEncoder(information,INITIAL_REMAINDER);

        //Copy encoded information bits
        codewords.insert(codewords.end(), information.begin(), information.end());

        //Clear information bytes
        information.clear();
    }
    message = codewords;
}


int main()
{
  crcInit();
  //hexdump(crcTable,256);
  unsigned char message[] = {0xaa, 0xbb, 0xcd, 0xdd, 0xee, 0xff, 0x11,0x00};
  //unsigned char tail[] = {0xC5,0xC5,0xC5,0xC5,0xC5,0xC5,0xC5,0x79};
  std::vector<unsigned char> info(message, message + sizeof(message)/sizeof(unsigned char));

  bchEncoder(info);
  hexdump(info.data(),info.size());

  //Vector hex dump

  return 0;
}

不知何故，我觉得我的方法太天真了。我想知道它是否准确。

致以敬意，

Answer 1

如果BCH码具有距离3，仅意味着纠正单个比特错误或检测(但不纠正)所有两个比特错误，则BCH多项式将与域多项式相同。如果需要更高级别的校正或检测，那么BCH多项式就会变得复杂。这在维基文章中有解释：

https://en.wikipedia.org/wiki/BCH_code

由于消息长度(包括填充比特)是64比特，所以使用了7比特字段(最多127比特是好的)，但是所示的表格生成是针对多项式0x1C5的。要解决此问题，请将多项式更改为0x8A，即((0xC5 << 1) &0xFE)。这应该导致最终在字节的高7位中的7位奇偶校验。

编码循环的内部部分应该是：

    remainder = crcTable[message.at(byte) ^ remainder];