BCH 21,31

• 下载源文件 - 3.12 Kb

引言

BCH 纠错码是基于块的纠错码，在数字通信和存储中具有广泛的应用。BCH 码用于纠正许多系统中的错误，包括

• 存储设备（包括磁带、光盘、DVD、条形码等）
• 无线或移动通信（包括蜂窝电话、微波链路、寻呼机等）
• 卫星通信
• 数字电视 / DVB
• 高速调制解调器，如 ADSL、xDSL 等。

BCH 编码器接收一块数字数据并添加额外的“冗余”位。由于多种原因（例如，噪声或干扰、光盘上的划痕等），传输或存储过程中会发生错误。BCH 解码器处理每个数据块并尝试纠正错误并恢复原始数据。可以纠正的错误数量和类型取决于 BCH 码的特性。

BCH 编码和解码可以在软件或专用硬件中进行。

有限（伽罗瓦）域算术

BCH 码基于一个称为伽罗瓦域或有限域的特殊数学领域。有限域具有的特性是，对域元素执行的算术运算（+、-、x、/ 等）的结果始终在该域中。BCH 编码器或解码器需要执行这些算术运算。这些运算需要特殊的硬件或软件函数来实现。

生成多项式

BCH 码字是使用一个特殊的多项式生成的。所有有效的码字都可以被生成多项式整除。生成多项式的通用形式是

g(x) = (x - ai) (x - ai+1) .... (x - ai+2t)

码字使用以下公式构造：

c(x) = g(x) . i(x)

其中 g(x) 是生成多项式，i(x) 是信息块，c(x) 是有效的码字，a 是域的本原元素。

BCH 21,31

我的一个项目是实现 POCSAG 协议，该协议用于寻呼机进行简单的通信。该协议需要一些纠错码，可以很容易地从冗余数据中恢复丢失的数据。为此，创建者决定使用 BCH ECC。该协议由码字组成。每个码字包含 21 位数据（原始数据）、10 位冗余数据（用于纠错）和 1 位奇偶校验位。在这种情况下，我们使用 BCH 21,31 来实现 POCSAG 的码字。

我试图对 BCH 进行简要介绍，您可以从有关纠错码、概念和所需数学知识的文章和书籍中找到更多有用的信息。此外，《Dr. Dobbs 杂志》发表了一系列关于 Reed-Solomon 和 BCH 的非常有用的文章。我在此领域找到了一些文章，例如在“纠错码 (ECC) 页面”中介绍的文章，但不幸的是，它们都不起作用。代码中存在一些错误，它们返回错误的结果。然后，我决定编写自己的代码。

请注意，我们为 POCSAG 使用了二进制 BCH。

CBCHEncoder

CBCHEncoder 是一个简单的类，用于计算一组数据的 BCH ECC。您可以为该类提供一个 32 位整数或一个整数数组进行编码。该类将前 21 位视为原始数据，并将编码后的 10 位添加到整数的末尾。以下是类接口

class CBCHEncoder  
{
public:
    int GetEncodedData();
    int* GetEncodedDataPtr();
    void SetData(int* pData);
    void SetData(int iData);
    void Encode();
    
    CBCHEncoder();
    virtual ~CBCHEncoder();

private:
    void InitializeEncoder();
    void ComputeGeneratorPolynomial();
    void GenerateGf();
    
    /*
    * m = order of the field GF(2**5) = 5
    * n = 2**5 - 1 = 31 = length 
    * t = 2 = error correcting capability 
    * d = 2*t + 1 = 5 = designed minimum distance 
    * k = n - deg(g(x)) = 21 = dimension 
    * p[] = coefficients of primitive polynomial 
    *       used to generate GF(2**5)
    * g[] = coefficients of generator polynomial, g(x)
    * alpha_to [] = log table of GF(2**5) 
    * index_of[] = antilog table of GF(2**5)
    * data[] = coefficients of data polynomial, i(x)
    * bb[] = coefficients of redundancy polynomial 
    *        ( x**(10) i(x) ) modulo g(x)
    * numerr = number of errors 
    * errpos[] = error positions 
    * recd[] = coefficients of received polynomial 
    * decerror = number of decoding errors 
    *            (in MESSAGE positions) 
    */
    
    int m, n, k, t, d;
    int    length;
    int p[6];        // irreducible polynomial 

    int alpha_to[32], index_of[32], g[11];
    int recd[32], data[21], bb[11];
    int Mr[31];
};

使用该类非常简单。只需创建一个类的实例，例如 m_bch，如下所示

CBCHEncoder  m_bch;
m_bch.SetData(0x23c5FFFF);
m_bch.Encode();
int iEncodedData=m_bch.GetEncodedData();

请注意，该类本身会生成伽罗瓦域 GF(2**m)，然后计算 BCH 码的生成多项式（请参见该类的 InitializeEncoder(), private 成员函数）。

Encode() 是该类的核心。这是它的主体

void CBCHEncoder::Encode()
{
    int    h, i, j=0, start=0, end=(n-k);
    
    // reset the M(x)+r array elements

    for (i = 0; i < n; i++)
        Mr[i] = 0;
    
    // copy the contents of data into Mr and add the zeros

    // use the copy method of arrays, its better :-)

    for (h=0; h < k; ++h)
        Mr[h] = data[h];
    
    
    while (end < n)
    {
        for (i=end; i>start-2; --i)
        {
            if (Mr[start] != 0)
            {
                Mr[i]^=g[j];
                ++j;
            }
            else
            {
                ++start;
                j = 0;
                end = start+(n-k);
                break;
            }
        }
    }
    
    
    j = 0;
    for (i = start; i < end; ++i)
    {
        bb[j]=Mr[i];
        ++j;
    }
}

致谢

我应该感谢我的表弟 Mohammad 以及我的好朋友 Mohammad Shahmohammadi，他们帮助我编写/调试代码。大部分代码取自 ECC Homepage 中的 Reed-Solomon 实现。

尽情享用！