伽罗华域傅里叶变换(GFFT)是识别RS码编码参数的一种非常有效的方法。与传统的欧几里得分析法^[1-2]和矩阵分析法^[3-6]相比，GFFT分析法在抗误码方面具有明显的优势，已成为目前RS码的主流分析方法^[7-13]，并且已形成完善的理论体系^[10-11]。但是，现有文献中所涉及的研究对象都是非缩短的RS码，而缩短RS的应用更为广泛，因此非常有必要讨论缩短RS的识别问题。本文把有限长度GFFT拓展到任意长度，使其能够适用于缩短RS码，并利用文献[10]中的类似方法，定义缩短RS码谱累积量，根据其概率分布确定判决门限，从而得到缩短RS码的GFFT识别方法，解决了缩短RS码的识别问题。

1 缩短RS码的谱累积量 1.1 任意长度GFFT

经典GFFT(限定长度GFFT)要求序列长度必须为${2^m} - 1$($m \geqslant 3$)，非缩短RS码的码长恰好满足这个条件；但是缩短RS码的码长不满足这个条件，不能直接应用经典GFFT，所以需要讨论如何对任意长度序列进行GFFT。限于篇幅，这里直接给出任意长序列GFFT的定义。

令$v(x) = {v_0} + {v_1}x + \cdots + {v_{l - 1}}{x^{l - 1}}$为$GF({2^m})$($m \geqslant 3$)上的多项式，其中$l$为大于0的整数。若$\alpha $为$GF({2^m})$中的本原元，则$v(x)$的GFFT谱为$GF({2^m})$上的多项式$V(x)$：

$ V(x) = {V_0} + {V_1}x + \cdots + {V_{n - 1}}{x^{n - 1}} $

(1)

式中$n = {2^m} - 1$，且

$ {V_j} = v({\alpha ^j}) = \sum\limits_{i = 0}^{l - 1} {{v_i}{\alpha ^{ij}}} ,\;\;\;j = 0,1, \cdots ,n - 1 $

(2)

为$V(x)$的第$j$个谱分量，取值范围为$0 \sim n$。当$l = n$时，式(1)即退化为经典GFFT。

由任意长GFFT的定义可知：a)多项式$v(x)$的谱长度及谱分量取值范围是由定义该多项式的域$GF({2^m})$确定的，而与$l$无关，其中谱长度为$n = {2^m} - 1$，谱分量取值范围为$0 \sim n$；b)如果$GF({2^m})$中某个元素${\alpha ^j}$为多项式$v(x)$的根，则对应的谱分量${V_j} = 0$。

1.2 缩短RS码及其谱累计量

假设$\left( {n, k} \right)$RS码是定义在$GF({2^m})$($m \geqslant 3$)上的，则有$n = {2^m} - 1$，$n - k = 2t$，并且生成多项式具有如下形式：

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

(3)

式中$t \geqslant 1$为该码所能纠正的最大误码数。

如果从$(n, k)$RS码的码字集合中，选取消息字前$l$个符号为0的子集，并去掉这$l$个0符号，则该子集就构成一个$(n - l, k - l)$缩短RS码，通常简称为$(n - l, k - l)$RS码。$(n, k)$RS码称为$(n - l, k - l)$RS码的母码。

令${n_1} = n - l$和${k_1} = k - l$，根据编码原理可知，$({n_1}, {k_1})$RS码与其母码$(n, k)$RS码之间存在如下关系：a) ${n_1}$取值范围为$2t + 1 \sim n$，当${n_1} = n$时退化为非缩短RS码；b) ${n_1} - {k_1} = n - k = 2t$，即缩短RS码与母码具有相同纠错能力；c)缩短RS与母码具有相同的本原多项式及生成多项式。由上述a)可知缩短RS码的码长的取值范围与母码码长有关，所以在识别缩短RS时，需要首先选定母码长度(或阶数)；由上述b)和c)可知，缩短RS码码多项式与母码码多项式具有相同的根，即为生成多项式的根。

参考文献[10]定义$({n_1}, {k_1})$RS码的谱累计量。假设接收端接收到M个$({n_1}, {k_1})$RS码的码字，每个码字构成一个码多项式，对每个码多项式进行GFFT得到该码多项式的谱。假设第k个码字的GFFT谱为：

$ {V_k} = ({V_{k, 0}}, {V_{k, 1}}, \cdots , {V_{k, n - 1}}) $

(4)

则可得到$({n_1}, {k_1})$RS码的谱累积量：

$ W = ({W_0}, {W_1}, \cdots , {W_{n - 1}}) $

(5)

式中

$ {W_j} = \sum\limits_{k = 1}^M {{V_{k, j}}} , \;j = 0, 1, \cdots , n - 1 $

(6)

1.3 缩短RS码谱累计量的概率分布

根据$({n_1}, {k_1})$RS码与其母码之间关系可知：不考虑误码的情况下，$W$中必有$2t$个连续0值。如果存在误码或者用于GFFT的参数与生成RS码的参数不同(包括阶数$m$、本原多项式$p(x)$、码长${n_1}$等)，则$W$的每个分量${W_j}$都是一个随机变量，利用与文献[10]类似的分析方法，可以得到不同情况下谱累积量的概率分布。

1) 码长为真实码长，并且GFFT参数与RS码编码参数相同。假设接收误码率为$\varepsilon $。设谱累积量中与生成多项式根对应的分量为${W_r}$，其他分量为${W_{nr}}$，则${W_r}$与${W_{nr}}$均服从二项分布，当$M$足够大时趋近于高斯分布，其均值及方差分别为：

$ \left\{ \begin{array}{l} {E_1} = E\{ {W_r}\} = \frac{{Mn}}{2}\left[ {1 - {{(1 - \varepsilon )}^{{n_1}}}} \right] \\ {D_1} = D\{ {W_r}\} = \frac{{Mn(2n + 1)}}{6}\left[ {1 - {{(1 - \varepsilon )}^{{n_1}}}} \right] - \frac{{M{n^2}}}{4}{\left[ {1 - {{(1 - \varepsilon )}^{{n_1}}}} \right]^2} \\ \end{array} \right. $

(7)

$ \left\{ \begin{array}{l} {E_0} = E\{ {W_{nr}}\} = \frac{{Mn}}{2} \\ {D_0} = D\{ {W_{nr}}\} = \frac{{Mn(n + 2)}}{{12}} \\ \end{array} \right. $

(8)

另外，在接收端通常给出的误比特率而不是误码率，需要进行转换。假设接收误比特率为$\tau $，RS码定义在$GF({2^m})$上，即$m$比特构成一个码(符号)，假设传输的符号是随机的，则误码率$\varepsilon $可表示为：

$ \varepsilon = 1 - {\left( {1 - \tau } \right)^m} $

(9)

重写${E_1}$和${D_1}$如下：

$ \left\{ \begin{array}{l} {E_1} = \frac{{Mn}}{2}\left[ {1 - {{(1 - \tau )}^{m{n_1}}}} \right] \\ {D_1} = \frac{{Mn(2n + 1)}}{6}\left[ {1 - {{(1 - \tau )}^{m{n_1}}}} \right] - \frac{{M{n^2}}}{4}{\left[ {1 - {{(1 - \tau )}^{m{n_1}}}} \right]^2} \\ \end{array} \right. $

(10)

2) 其他情况。若码字为随机码字，则其根在有限域上也是随机分布的，即此时累积量中每个分量的分布都与情况1)中谱分量${W_{nr}}$的分布相同。

由上述可知，缩短RS码谱累积量的分量近似服从2个不同均值和方差的高斯分布，其概率密度分布分别为：

$ {p_0}(x) = \frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}{D_0}} }}\exp \left[ {\frac{{ - {{(x - {E_0})}^2}}}{{2{D_0}}}} \right] $

(11)

$ {p_1}(x) = \frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}{D_1}} }}\exp \left[ {\frac{{ - {{(x - {E_1})}^2}}}{{2{D_1}}}} \right] $

(12)

式中：${p_1}(x)$表示与生成多项式根对应的分量的概率分布；${p_0}(x)$表示其他分量的概率分布。

2 识别方法 2.1 识别原理

缩短RS码的识别包括域的识别、码长的识别以及生成多项式的识别，域的识别又包括阶数$m$的识别和本原多项式$p(x)$的识别，而生成多项式$g(x)$是在确定域及码长后，根据满足条件的连续码根数来确定的，因此分析过程中需要遍历阶数、码长及本原多项式3个参数。

由1.3中讨论可知，当阶数、本原多项式、码长都与实际参数相同时，谱累积量中存在分量服从概率分布${p_1}(x)$，其他情况下所有分量都服从概率分布${p_0}(x)$。因此，阶数、本原多项式及码长识别问题就转换为如下二元假设检验问题：

$ H = \left\{ \begin{gathered} {H_1}\begin{array}{*{20}{c}} {}&{\exists j, }&{1 \leqslant j \leqslant n, }&{{W_j} \leqslant T} \end{array} \\ {H_0}\begin{array}{*{20}{c}} {}&{\forall j, }&{1 \leqslant j \leqslant n, }&{{W_j} > T} \end{array} \\ \end{gathered} \right. $

(13)

式中：$T$为设定的阈值；${W_j}$为在某阶数m、本元多项式$p(x)$、码长${n_1}$下计算的谱累计量的一个分量；$n = {2^m} - 1$。如果假设${H_1}$成立，则阶数、本原多项式及码长的识别结果即为m, $p(x)$和${n_1}$。

在成功完成阶数、本原多项式及码长的识别后，统计谱累积量中小于等于阈值的连续分量的个数${n_t}$，则可得到$t$的估计值$\hat t = \left\lceil {{n_t}/2} \right\rceil $，进而得到生成多项式的识别结果：

$ \hat g(x) = (x - \alpha )(x - {\alpha ^2}) \cdots (x - {\alpha ^{2\hat t}}) $

(14)

2.2 阈值的选取

在2.1识别方法中，阈值的选取是影响识别性能的关键。由于已经获取$({n_1}, {k_1})$缩短RS码谱累积量的概率分布，因此可据此确定阈值。

如果选定的阈值为T，则虚警概率和漏警概率分别为：

$ {P_{\rm{f}}} = \int_{ - \infty }^T {{p_0}(t){\rm{d}}t} = \frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}{D_0}} }}\int_{ - \infty }^T {\exp \left[ {\frac{{ - {{(t - {E_0})}^2}}}{{2{D_0}}}} \right]{\rm{d}}t} $

(15)

$ {P_{\rm{n}}} = \int_T^\infty {{p_1}(t){\rm{d}}t} = \frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}{D_1}} }}\int_T^\infty {\exp \left[ {\frac{{ - {{(t - {E_1})}^2}}}{{2{D_1}}}} \right]{\rm{d}}t} $

(16)

以${P_{\rm{f}}} = {P_{\rm{n}}}$为目标选取门限值，则可得

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

(17)

可见，$T$为${E_0}$和${E_1}$分别以$1/\sqrt {{D_0}} $和$1/\sqrt {{D_1}} $为权值的加权平均值。

2.3 误码适应性、数据量需求及算法有效性评估

令

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

(18)

此时，

$ {P_{\rm{f}}} = {P_{\rm{n}}} = \int_\alpha ^\infty {\frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}} }}\exp \left( {\frac{{ - {t^2}}}{2}} \right){\rm{d}}t} = Q(\alpha ) $

(19)

显然$\alpha $越大，${P_{\rm{f}}}$和${P_{\rm{n}}}$越小。根据$3\sigma $准则，当$\alpha \geqslant 3$时，则可认为${P_{\rm{f}}}$及${P_{\rm{n}}}$已经足够小，发生虚警、漏警都是小概率事件，此时要求

$ \frac{{{E_0} - {E_1}}}{{\sqrt {{D_0}} + \sqrt {{D_1}} }} \geqslant 3 $

(20)

代入${E_0}$, ${E_1}$, ${D_0}$, ${D_1}$的表达式，可得

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

(21)

式中：${e_0} = \frac{n}{2}$；${d_0} = \frac{{n(n + 2)}}{{12}}$；${e_1} = \frac{n}{2}\left[ {1 - {{(1 - \tau )}^{m{n_1}}}} \right]$；${d_1} = \frac{{n(2n + 1)}}{6}\left[ {1 - {{(1 - \tau )}^{m{n_1}}}} \right] - \frac{{{n^2}}}{4}{\left[ {1 - {{(1 - \tau )}^{m{n_1}}}} \right]^2}$。

如果取定$M$，并且要求$\alpha \geqslant 3$，则可由$\alpha $的表达式得到算法所能适应的误比特率范围：

$ \tau \leqslant 1 - {\left( {\frac{{2\sqrt {3Mn(n + 2)} + 6(n - 1)}}{{9n + Mn}}} \right)^{1/m{n_1}}} $

(22)

此外，当$\alpha \geqslant 3$时，可以保证算法是有效的。

综上所述：a)误码适应能力评估：码字数、编码参数确定条件下，根据式(22)，估计所能适应的误比特率；b)数据量需求评估：误比特率、编码参数确定条件下，可根据式(21)估计所需要的数据量；c)算法有效性评估：如果$\alpha \geqslant 3$则算法有效，并且α取值越大，算法性能越好。

3 仿真验证 3.1 误码适应能力评估

本试验验证2.3中数据量误码适应能力评估方法的正确性。以$(31, 29)$RS码生成的缩短RS码为例进行仿真分析，其中$m = 5$, $n = 31$, $t = 1$, ${n_1} = 3, 4, \cdots , 31$。给定$M = 50$，则根据式(22)，可得到α=3时不同码长对应的最大误比特率，见表 1。

根据表 1数据可以预期，当误比特率分别取0.004, 0.006, 0.008和0.010时，如果对应码长不大于31, 21, 16和12，则可获得较好识别性能。为此，误比特率分别取0.004, 0.006, 0.008和0.010，进行仿真试验，在每种码长下，试验1 000次，统计正确识别率。

图 1给出了误比特率为0.01时的仿真结果。从结果中可以看出：阶数的正确识别率明显优于其他参数；码长、本原多项式、生成多项式的正确识别率随码长增加而降低，这是由于当码字数和误比特率固定时，α随码长的增加而减小从而导致正确识别率降低。其他误码率条件下的仿真结果类似。阶数的识别性能之所以远优于其他参数，是由于不论本原多项式是否正确，只要满足判决条件，则可正确识别，显然不适合以阶数作为对比参数。这里以码长作为待识别参数进行对比。

图 2给出了不同误码率条件下码长的正确识别率曲线。从图 2(a)中可以看出，识别性能随误比特率增加而恶化。图 2(b)对图 2(a)进行了局部放大。由图 2(b)可知，当误比特率0.004，码长31时，正确识别率为0.976；以0.976为阈值，可以得到误比特率为0.006, 0.008和0.001时，正确识别率大于0.976所对应的码长分别为21, 16和13，与理论分析基本一致，所以验证了2.3中误码适应能力评估方法的正确性。

3.2 数据量需求评估

本次仿真试验验证2.3中数据量需求评估方法的正确性。仍以(31, 29)RS码生成的缩短RS码为例进行仿真分析，其他参数同3.1。给定误比特率为0.01，则根据式(21)可得到，α时对应的最小M值见表 2。

根据表 2可以预期，当码字数分别取50, 100, 200, 325时，如果对应码长不大于12, 19, 26, 31，则可获得较好识别性能。为此，码字数分别取50, 100, 200和325，进行仿真试验，在每种码长下，试验1 000次，统计正确识别率，仿真结果见图 3。从图 3(a)中可以看出，识别性能随码字数增加而提高。图 3(b)对图 3(a)进行了局部放大。由图 3(b)可知，当码字数取325时，码长31时的正确识别率为0.971；以0.971为阈值，可以得到码字数为50, 100, 200时，正确识别率大于0.971所对应的码长分别为13, 20和26，与理论分析基本一致，从而验证了2.3中数据量估计方法的正确性。

3.3 算法有效性评估

实际应用中，RS码的阶数一般不会超过8，可选定阶数为3~8。此外，实际的处理平台的处理能力及硬件资源总是有限，所以$M$不可能无限大，假定$M$最大可取800。

首先根据$M$的最大取值，评估算法的误码适应能力。在阶数3~8范围内的所有RS码中，当${n_1} = 255$时的抗误码能力最弱，此时为非缩短RS码。根据式(19)可以得到，τ≤0.001。可知，误比特率不大于0.001时，利用800个码字，可对所有阶数在3~8内的RS码(非缩短的和缩短的)进行识别。

随机选取阶数、码长、最大纠错数、本原多项式进行仿真试验，$M$取100~1 000，步进间隔为100，在每个$M$取值下试验1 000次，统计正确识别率。仿真结果如图 4(a)所示。从仿真结果来看，当码字数不小于800时即可获得不小于99%的正确识别率，这与理论分析一致。为了进一步验证理论分析的正确性，取误比特率0.000 2~ 0.002，步进间隔为0.000 2，在每个误比特率取值下试验1 000次，统计正确识别率，仿真结果如图 4(b)所示。图 4证明了2.3中算法有效性评估方法的正确性。

值得说明的是，按照2.3中评估方法，当$\alpha \geqslant 3$时算法一定有效，但这并不能说明，$\alpha < 3$时算法一定无效，此时算法是否有效与$\alpha $取值、待识别RS码的参数有关，非常复杂，有待深入研究

4 结论

本文把用于非缩短RS码GFFT识别方法经过拓展后应用于缩短RS码的识别，并给出了缩短RS码GFFT谱累积量的概率分布及阈值确定方法。在此基础上，从理论上分析了误码适应性、数据量需求以及算法有效性的评估方法，从而建立了完整的理论体系，为识别算法的实际应用提供了理论依据。仿真试验在验证算法性能的同时，也证明了理论分析的正确性。尽管如此，从理论分析和仿真可以看出，当RS码的阶数较大(例如阶数大于8)或误码率更高(例如误比特率为0.01)时，很难获得较好的识别性能，或者所付出的代价是难以承受的，因此如何提高算法在高阶、高误码条件下的性能是当前亟需解决的问题。