在智能通信系统中，编码识别是解码的前提，编码参数的盲识别问题一直是盲信号处理领域研究的重点课题之一。RS码是一类纠错能力很强的前向纠错编码，广泛应用于各种无线通信系统中，因而成为编码识别领域的重要研究对象之一。目前RS码的主要识别方法有欧几里得分析法^[1]、矩阵分析法^[2-5]、码根统计分析法^[6-8]、有限域傅里叶变换(Galois Field Fourier Transform，GFFT)分析法^[9-12]等。GFFT分析法亦称为谱累积量(Spectrum Cumulant)分析法，由于完善的理论体系及较为理想的识别性能，已成为RS码的主流分析方法；但是，该方法需要遍历所有可能的有限域及有限域中的所有元素，导致计算量较大，识别速度慢。为此，文献[13]利用编码域本原元是RS码码根这一特性提出一种快速识别方法，把编码域的识别与生成多项式的识别分离，在一定程度上提高了识别速度，但该方法依然涉及大量高阶有限域运算，速度提高有限。为了进一步提高识别速度，本文提出一种基于校验和的识别方法，把谱累积量运算转换为校验矩阵的校验和运算，主要运算在$GF(2)$内进行，识别速度显著提高，并且在一定程度上改善了识别性能。此外，本文还采取序列相关的方法识别生成多项式，解决了生成多项式识别性能随着RS码纠错能力增强而降低的问题。

1 RS码基础

定义在$GF({2^m})$($m \geqslant 3$)上，能够纠正$t$个错误的RS码具有如下特征：a) 码长$n = {2^m} - 1$；b) 校验符号数$k = n - 2t$；c) 生成多项式可表示为：

$ g(x) = (x - {\alpha ^{{t_0}}})(x - {\alpha ^{{t_0} + 1}}) \cdots (x - {\alpha ^{{t_0} + 2t - 1}}) $

(1)

式中：m为该RS码的阶数；$\alpha $为$GF({2^m})$的本原元；${t_0} = 0$或1，$1 \leqslant t \leqslant \frac{{(n - 1)}}{2}$。因为编码域$GF({2^m})$取决于阶数m及m阶本原多项式$p(x)$，所以一个RS码由阶数m、本原多项式$p(x)$及生成多项式$g(x)$唯一确定。

假设${c_1}, {c_2}, \cdots , {c_N}$为发送端发送的已转换为二进制的RS码比特数据，${r_1}, {r_2}, \cdots , {r_N}$为接收端解调输出的含有误码的比特数据，并且假定已通过帧同步等方法实现了码同步，那么RS码识别问题，就是利用${r_1}, {r_2}, \cdots , {r_N}$识别出目标RS码的编码域$GF({2^m})$和生成多项式$g(x)$。

2 识别算法 2.1 识别原理

定义：记$c(x)$为该RS码的任一码多项式，$\beta $是$GF({2^m})$上的一个元素，如果$c(\beta ) = 0$则称$\beta $为该RS码的一个码根。

命题1：定义在$GF({2^m})$上以$g(x) = (x - {\alpha ^{{t_0}}})(x - {\alpha ^{{t_0} + 1}}) \cdots (x - {\alpha ^{{t_0} + 2t - 1}})$为生成多项式的RS码，一定存在且只存在2t个连续码根，并且这2t个连续码根为${\alpha ^{{t_0}}}, {\alpha ^{{t_0} + 1}}, \cdots , {\alpha ^{{t_0} + 2t - 1}}$。

证明：由码根的定义及RS码的生成多项式表示形式可知，${\alpha ^{{t_0}}}, {\alpha ^{{t_0} + 1}}, \cdots , {\alpha ^{{t_0} + 2t - 1}}$为该RS码的2t个连续码根。如果假设还存在另一个公共码根${\alpha ^l}$，则由于RS码为循环码，其生成多项式为所有码多项式的最大公因式，则生成多项式为$g(x) = (x - {\alpha ^{{t_0}}})(x - {\alpha ^{{t_0} + 1}}) \cdots (x - {\alpha ^{{t_0} + 2t - 1}})(x - {\alpha ^l})$，这与该RS码的定义不一致，从而证明了2t个连续公共码根的唯一性。

命题2：对于定义在$GF({2^m})$上的RS码，$GF({2^m})$的本原元$\alpha $一定是该RS码的一个码根。

证明：由于${t_0} = 0$或1，根据命题1可知2t个连续码根为$1, \alpha , \cdots , {\alpha ^{2t - 1}}$或$\alpha , {\alpha ^2}, \cdots , {\alpha ^{2t}}$；且$1 \leqslant t \leqslant \frac{{(n - 1)}}{2}$，则该RS码至少存在2个码根为1, $\alpha $或$\alpha $, ${\alpha ^2}$，因此$\alpha $一定是该RS码的一个码根。

根据命题1和命题2可知，可以把RS码的识别分为2步：a)编码域的识别，即阶数m及本原多项式$p(x)$的识别；b)生成多项式$g(x)$的识别。

2.1.1 编码域识别

根据命题2，对于定义在$GF({2^m})$上的(n, k)RS码，本原元$\alpha $一定为其一个码根。令C为该RS码的一个码字，对应的码多项式为$c(x)$，则必有$c(\alpha ) = 0$，亦即$x - \alpha $必然整除$c(x)$。因此如果以$x - \alpha $为生成多项式定义一个m进制(n, n-1)循环码，H为该循环码的校验矩阵，则必有

$ {\mathit{\boldsymbol{C}}} \cdot {{\mathit{\boldsymbol{H}}}^T} = 0 $

(2)

对于任一m阶(n, k)RS码，都存在一个等价的(mn, mk)二进制线性分组码，设与RS码字C对应的二进制线性分组码的码字为C_b；同理，以$x - \alpha $为生成多项式的$m$进制(n, n-1)循环码也对应一个(nm, nm-m)二进制线性分组码，设其校验矩阵为H_b，则有

$ {{\mathit{\boldsymbol{C}}}_b} \cdot {\mathit{\boldsymbol{H}}}_b^T = 0 $

(3)

式中H_b为$nm \times m$维二进制矩阵。实际识别过程中，能够获取的是接收到的二进制码字R_b，在含噪的情况下一般其校验和满足一定的分布，可根据该分布确定阈值T，如果校验和小于T，则认为由当前阶数m及本原多项式$p(x)$确定的有限域即为RS码的编码域。由此得到编码域的识别过程为：a) 遍历所有可能的阶数m及本原多项式$p(x)$；b) 在每个m及$p(x)$下构造有限域$GF({2^m})$；c) 求出以$x - \alpha $为生成多项式的m进制(n, n-m)循环码对应的(nm, nm-m)二进制线性分组码的校验矩阵H_b；d) 把接收到比特数据${r_1}, {r_2}, \cdots , {r_N}$分割为M个长度为nm的二进制向量，$n = {2^m} - 1$；计算校验和$CH(m, p) = \frac{1}{{Mm}}\sum\limits_{i = 1}^M {\sum\limits_{j = 1}^m {{{\mathit{\boldsymbol{R}}}_{b, i}}{\mathit{\boldsymbol{h}}}_{b, j}^T} } $，其中：p为$p(x)$，${{\mathit{\boldsymbol{R}}}_{b, i}}$为第$i$个二进制向量，${{\mathit{\boldsymbol{h}}}_{b, i}}$为H_b中的第$j$个行向量；e) 把校验和$CH(m, p)$与设定的阈值$T$进行比较，如果$CH(m, p) < T$，则认为当前$GF({2^m})$即为目标RS码的编码域，识别结束，否则继续。

2.1.2 生成多项式识别

由定义可知，$GF({2^m})$上的RS码，其生成多项式$g(x)$是由t₀及t唯一确定的，所以识别$g(x)$就等价于识别${t_0}$及t；根据命题1，RS码存在2t个连续码根，所以可据此识别t₀及t。

识别出编码域$GF({2^m})$后，设其中的第l个元素为${\alpha ^l}$($0 \leqslant l \leqslant (n - 1)$)，求出以$x - {\alpha ^l}$为生成多项式的m进制(n, n-1)循环码对应的(nm, nm-m)二进制线性分组码的校验矩阵H_{b, l}(显然，H_b=H_{b, 1})，并计算校验和

$ CH(l) = \frac{1}{{Mm}}\sum\limits_{i = 1}^M {\sum\limits_{j = 1}^m {{{\mathit{\boldsymbol{R}}}_{b, i}}{\mathit{\boldsymbol{h}}}_{b, l, j}^T} } ，0 \leqslant l \leqslant (n - 1) $

(4)

式中h_{b, l, j}为H_{b, l}中的第j个行向量。如果$CH(l) < T$，则${\alpha ^l}$为RS码的码根，所以可采用直接法识别t₀及t，步骤如下：a) 初始化l=1；b) 计算$CH(l)$；c) 如果$CH(l) < T$，取l=l+1，转到b)，否则转到d)；d) 如果l为偶数，则${\hat t_0} = 1$，$\hat t = \frac{l}{2}$；否则，${\hat t_0} = 0$，$\hat t = \frac{{(l + 1)}}{2}$。

直接法直接利用BCH码的连续码根特性识别t₀和t，需要进行多个二元假设检验，随着t的增大必然会降低正确识别率，为此需要对识别算法进行改进。

首先，计算除l=0外的所有校验和$CH(l)$($0 \leqslant l \leqslant (n - 1)$)，并把每个校验和与阈值$T$进行对比，得到校验和序列${B_{{\rm{ch}}}} = \{ {b_1}, {b_2}, \cdots , {b_{n - 1}}\} $，其中

$ {b_l} = \left\{ \begin{gathered} - 1, \quad CH(l) < T \\ 1, \quad \;\;CH(l) \geqslant T \\ \end{gathered} \right. , \;0 \leqslant l \leqslant (n - 1) $

(5)

然后，构造如下序列

$ w(d) = 1 - 2pulse(1, d, n - 1), \;1 \leqslant d \leqslant (n - 2) $

(6)

式中$pulse(1, d, n - 1)$表示一个长度为$n - 1$的序列，其中1~d项为1，其余为0。令$w(t, l)$为$w(d)$中第l项，则$w(t, 1) = w(t, 2) = \cdots = w(t, d) = - 1$，其他为1；计算下式，

$ prod(d) = \prod\limits_{l = 1}^{n - 1} {w(d, l) \cdot {b_l}} $

(7)

显然，当$prod(t)$取最大时所取的d与t₀和t相关，

$ \hat d = \mathop {\arg \max }\limits_d prod(d) $

(8)

$ \left\{ \begin{array}{l} {{\hat t}_0} = 1, \hat t = \frac{{\hat d}}{2}\begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}rem(\hat d, 2) = 0 \\ {{\hat t}_0} = 0, \hat t = \frac{{(\hat d + 1)}}{2}\begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}rem(\hat d, 2) = 1 \\ \end{array} \right. $

(9)

式(8)实际上是2个序列的相关，所以称此方法为相关法。得到${\hat t_0}$及$\hat t$之后，则可进一步得到生成多项式g(x)。

2.1.3 校验矩阵的求取方法

由2.1.1和2.1.2可知，上述算法的关键是求取H_{b, l}，而分析等价二进制线性分组码与m进制原循环码之间的关系是比较复杂的。为此，本文采用高斯约旦消元法直接利用二进制线性分组码数据求取对应的校验矩阵^[14]。

对于阶数m、本原多项式$p(x)$构造的有限域$GF({2^m})$，生成P组长度为$n - 1$($n = {2^m} - 1$, $P \geqslant 2mn$)的m进制随机消息分组U_i($1 \leqslant i \leqslant (n - P)$)，${u_i}(x)$为$GF({2^m})$上对应的消息多项式，则以$x - {\alpha ^l}$为生成多项式的m进制$(n, n - 1)$循环码的编码过程可表示为：

$ {v_i}(x) = {u_i}(x)(x - {\alpha ^l}) $

(10)

式中${v_i}(x)$为码多项式，对应的码字为V_i，由$n$个m进制整数构成。将V_i中的每个元素用二进制表示，则可得到长度为$mn$二进制码字V_{b, i}。以V_{b, i}为行向量构成$P \times mn$维数组A。然后，利用高斯消元法，将码矩阵A转换为一个下三角矩阵B，即

$ {\mathit{\boldsymbol{B}}} = {\mathit{\boldsymbol{A\Phi}}} $

(11)

式中：B是$P \times mn$维二进制矩阵；$\mathit{\pmb{\Phi}} $是$mn \times mn$维二进制矩阵，且$\mathit{\pmb{\Phi}} = {[\begin{array}{*{20}{c}} {{{\mathit{\boldsymbol{\phi}}} _1}}&{{{\mathit{\boldsymbol{\phi}}} _2}}& \cdots &{{{\mathit{\boldsymbol{\phi}}} _{mn}}} \end{array}]^T}$，${{\mathit{\boldsymbol{\phi}}} _j}$($1 \leqslant j \leqslant mn$)为矩阵$\mathit{\pmb{\Phi}} $的列向量。统计矩阵B中的列重${w_{B, j}}$($1 \leqslant j \leqslant mn$)，如果当$j = {\lambda _1}, {\lambda _2}, \cdots , {\lambda _m}$时${w_{B, {\lambda _1}}} = {w_{B, {\lambda _2}}} = \cdots = {w_{B, {\lambda _m}}} = 0$，则${{\mathit{\boldsymbol{H}}}_{b, l}}$由$\mathit{\pmb{\Phi}} $中对应的列向量构成：

$ {{\mathit{\boldsymbol{H}}}_{b, l}} = {[\begin{array}{*{20}{c}} {{{\mathit{\boldsymbol{\phi}}} _{{\lambda _1}}}}&{{{\mathit{\boldsymbol{\phi}}} _{{\lambda _2}}}}& \cdots &{{{\mathit{\boldsymbol{\phi}}} _{{\lambda _m}}}} \end{array}]^T} $

(12)

上述求取方法随着阶数的增大，计算量会显著增加，所以在识别前需要离线求出待识别阶数范围内所有的校验矩阵，并保存起来，识别时直接读取，即以存储空间换取识别速度；不过，由于存储的都是二进制数据，所需要的存储空间不大；以8阶RS码为例，所需的存储空间为2 040×2 040×16≈6.5 MB。

2.2 阈值的选取

由文献[15]可知，假设${R_i}$($1 \leqslant i \leqslant M$)是M个二进制线性分组码码字，${\mathit{\boldsymbol{h}}}$为该码的一个校验向量，则当M足够大时，校验和$CH = \frac{1}{M}\sum\limits_{i = 1}^M {{{\mathit{\boldsymbol{R}}}_i}{{\mathit{\boldsymbol{h}}}^T}} $近似服从均值为${e_1} = \frac{1}{2} - \frac{{{{(1 - 2\tau )}^w}}}{{2GF(2)}}$，方差为${d_1} = \frac{1}{{4M}} - \frac{{{{(1 - 2\tau )}^{2w}}}}{{4M}}$的高斯分布，其中$\tau $为误比特率，$w$为h的汉明重量，即其中1的个数；当${{\mathit{\boldsymbol{R}}}_i}$不是与h对应的码字或h不是与${{\mathit{\boldsymbol{R}}}_i}$对应的校验向量时，当M足够大时，校验和近似服从均值为${e_0} = 1/2$，方差为${d_0} = 1/4M$的高斯分布。

由此可以得到，当M足够大时校验和$CH(l)$的分布满足：

1) 当${{\mathit{\boldsymbol{R}}}_{b, i}}$($1 \leqslant i \leqslant M$)与${{\mathit{\boldsymbol{H}}}_{b, l}}$是对应的码字的校验矩阵时$CH(l)$近似服从高斯分布，

$ CH(l) \sim N({E_1}, {D_1}) $

(13)

式中：${E_1} = \frac{1}{2} - \frac{1}{{2m}}\sum\limits_{j = 1}^m {{{(1 - 2\tau )}^{{w_j}}}} $；${D_1} = \frac{1}{{4Mm}} - \frac{1}{{4M{m^2}}}\sum\limits_{j = 1}^m {{{(1 - 2\tau )}^{2{w_j}}}} $；${w_j}$为${\mathit{\boldsymbol{h}}}_{b, l, j}^{}$的汉明重量。为了简化，一般可取${w_j} = \frac{{nm}}{2}$，则${E_1} \approx \frac{1}{2} - \frac{1}{2}{(1 - 2\tau )^{mn/2}}$，${D_1} \approx \frac{1}{{4Mm}} - \frac{1}{{4Mm}}{(1 - 2\tau )^{mn}}$，下面讨论中${E_1}$和${D_1}$取近似值。

2) 其他情况下，$CH(l)$也近似服从高斯分布

$ CH(l) \sim N({E_0}, {D_0}) $

(14)

式中：${E_0} = \frac{1}{2}$；${D_0} = \frac{1}{{4Mm}}$。

因为${E_1} < {E_0}$，所以判断$GF({2^m})$中某一元素${\alpha ^l}$($0 \leqslant l \leqslant (n - 1)$)是否为码根的问题就转换为一个二元假设检验问题：

$ H = \left\{ \begin{gathered} {H_1}\begin{array}{*{20}{c}} {}&{CH(l) < T} \end{array} \\ {H_0}\begin{array}{*{20}{c}} {}&{CH(l) \geqslant T} \end{array} \\ \end{gathered} \right.\quad\quad{E_1} < T < {E_0} $

(15)

式中：H₀表示${\alpha ^l}$不是码根的假设；H₁表示${\alpha ^l}$是码根的假设。另外由于$CH(m, p) = CH(1)$，因此也符合同样的概率分布。

得到$CH(l)$所符合的概率分布后，即可据此选取最优判决阈值。为了兼顾检测概率和虚警概率，本文根据最大后验概率准则确定阈值。由最大后验概率准则可知，当$\frac{{CH(l) - {E_1}}}{{\sqrt {{D_1}} }} > \frac{{CH(l) - {E_0}}}{{\sqrt {{D_0}} }}$时应取${H_1}$假设，否则取${H_0}$假设，取两边相等时的$CH(l)$为阈值$T$，则可得到：

$ T = \frac{{{E_1}\sqrt {{D_0}} + {E_0}\sqrt {{D_1}} }}{{\sqrt {{D_0}} + \sqrt {{D_1}} }} $

(16)

分析可知，按式(17)确定的阈值与$M$无关。

2.3 数据量需求分析

令

$ \alpha = \frac{{{E_0} - T}}{{\sqrt {{D_0}} }} = \frac{{T - {E_1}}}{{\sqrt {{D_1}} }} = \frac{{{E_0} - {E_1}}}{{\sqrt {{D_0}} + \sqrt {{D_1}} }} $

(17)

为了保证足够高的正确识别率和足够低的虚警概率，根据3σ准则，$\alpha $应满足$\alpha \geqslant 3$，由此得到：

$ M \geqslant 9{\left( {\frac{{\sqrt {{d_1}} + \sqrt {{d_0}} }}{{{E_0} - {E_1}}}} \right)^2} $

(18)

式中：${d_0} = \frac{1}{{4m}}$；${d_1} = \frac{1}{{4m}} - \frac{1}{{4m}}{(1 - 2\tau )^{mn}}$。因此，在3σ准则下，所需的最少码字数${M_{\min }}$为：

${M_{\min }} = \left\lceil {9{{\left( {\frac{{\sqrt {{d_1}} + \sqrt {{d_0}} }}{{{E_0} - {E_1}}}} \right)}^2}} \right\rceil $

(19)

谱累计量具有类似的性质，可以得到类似的结论，

$ {M'_{\min }} = \left\lceil {9{{\left( {\frac{{\sqrt {{{d'}_1}} + \sqrt {{{d'}_0}} }}{{{{e'}_0} - {{e'}_1}}}} \right)}^2}} \right\rceil $

(20)

式中：${e'_0} = \frac{1}{2}$；${d'_0} = \frac{1}{{12}}$；${e'_1} = \frac{1}{2} - \frac{1}{2}{(1 - \tau )^{mn}}$；${d'_1} = \frac{1}{3}\left[ {1 - {{(1 - \tau )}^{mn}}} \right] - \frac{1}{4}{\left[ {1 - {{(1 - \tau )}^{mn}}} \right]^2}$。图 1给出了m=8时，${M_{\min }}$和${M'_{\min }}$随误比特率的变化。可以看出${M'_{\min }} > {M_{\min }}$，并且随着误比特率的增加，二者的差值越大。这表明，在同等识别性能下，本文识别方法要比累计量识别方法所需的码字数要少得多；换言之，利用等量数据，本文方法可以获得更优的识别性能。后面的仿真试验也验证了这一点。

3 仿真试验

实际应用中8阶RS码应用最广，所以这里以8阶RS码为例进行仿真。待识别RS码的本原多项式在所有8阶本原多项式集合中随机选取；识别时，阶数搜索范围为3~8，采用BPSK调制方式，噪声为高斯白噪声，每次试验重复测试1 000次，统计正确识别率。

3.1 编码域的识别

${t_0}$在0和1之间随机选取，$t = 1$，在误比特率0.000 1~0.002(步进0.000 1)条件下，分别取$M = 300$和$M = 500$，本文方法及谱累积量识别方法识别性能对比见图 2，为了便于对比，绘图时横轴为BPSK调制模式下误比特对应的信噪比。由图 2可知，在相同数据量条件下，本文方法优于谱累积量方法，性能改进约0.1dB，但在同一平台上的运行速度相对于谱累积量法提高了1个数量级(运行用时比约为20)。

图 3给出了误比特率0.001，码字数取50~1 000(步进50)时，正确识别率随码字数的变化，由图可知，当$t > 250$，本文方法的正确识别率接近于1，而当$t > 750$，谱累积量方法的正确识别率才接近于1，与理论分析一致。

3.2 生成多项式的识别

由2.1.2可知，生成多项式$g(x)$的识别可转换为t₀和$t$的识别，但这是以正确识别编码域$GF({2^m})$为前提的，所以$g(x)$的正确识别等价于同时正确识别编码域$GF({2^m})$、t₀及$t$。在与3.1相同的条件下进行仿真，识别t₀和$t$时采用直接法，图 4给出了仿真结果。由图 4可得到与3.1类似的结论，即在同等条件下，本文方法优于谱累积量方法，性能改进约0.1dB。由于皆采用直接法估计${t_0}$和$t$，所以性能改善主要是由编码域识别性能的改善带来的。

为了对比直接法和相关法识别t₀和$t$的性能，取$t = 1, 2, 4, 8, 16$，$M = 500$，其他条件与3.1同，采用本文方法进行识别，仿真结果见图 5和图 6。由图可知，直接法的识别性能随$t$取值增大而恶化，而相关法中，当$t \geqslant 2$时，识别性能已基本保持不变。限于篇幅没有给出$t$取相同值时，两种方法的性能曲线，但对比图 4和图 5，大致可以看出，相关法的性能优于直接法，并且随着$t$取值增大，其性能改善程度越大，体现了相关法的优越性。

4 结论

本文从RS码的码根特性出发，提出一种基于校验和的识别方法。仿真试验结果表明，无论是在识别速度方面还是在数据量需求方面，本文所提方法都远优于谱累积量方法。而且，由于校验和计算仅涉及二进制运算和十进制运算，容易用硬件描述语言实现，所以更有利于应用于实时系统中。

此外，由于需要利用二进制校验矩阵，所以本文方法可以很方便地转换为基于软信息的识别方法。软信息中包含了每个比特的可靠性信息，因此利用软信息进行识别有望进一步提高识别性能，值得深入研究。