On Fast Decoding of (41, 21, 9) Quadratic Residue Code

二次剩余码是由域GF(2) 上的生成多项式g(x)=g₀+g₁x+…+g_n-kx^n-k生成的一类线性循环码，用(n，k，d)来表示，其中n=8l±1(l为正整数)为码长，k为信息长度，d为码的最小汉明距离. (41，21，9) QR码就是其中一种. m是能满足n整除2m-1的最小正整数.设Q_n={j|j≡x²mod n，1≤x≤(n-1)/2}.当n=41时，m=20，且Q₄₁={1，2，4，5，8，9，10，16，18，20，21，23，25，31，32，33，36，37，39，40}. α是本原多项式p(x)=x²⁰+x³+1的一个根.因此，β=α^u，u=(2^m-1) /n=(2²⁰-1)/41=25 575，是域GF(2²⁰)上一个41阶本原根.生成多项式g(x)通过

可以得到.

由(41，21，9) QR码的最小汉明距离d=9，可知它的纠错能力 $t=\left\lfloor \frac{d-1}{2} \right\rfloor =4$ (41，21，9) QR码的码字可用多项式c(x)=c₀+c₁x+…+c₄₀x⁴⁰来表示，其中c(x)是g(x)的倍式，即c(x)=m(x)g(x)，这里m(x)=m₀+m₁x+…+m₂₀x²⁰为码的信息多项式.当码字通过一个有噪音的信道，接收到的多项式r(x)=r₀+r₁x+…+r₄₀x⁴⁰是c(x)与错误多项式e(x)=e₀+e₁x+…+e₄₀x⁴⁰的和.为简单起见，信息、码字、错误模式、接收量和校验子分别用向量m=[m₀，m₁，…，m_k-1]，c=[c₀，c₁，…，c_n-1]，e=[e₀，e₁，…，e_n-1]，r=[r₀，r₁，…，r_n-1]和s=[s₀，s₁，…，s_n-k-1]来表示.

QR码作为循环码，按下列方法可得它的一个生成多项式G₁^[3]：

对G₁进行行初等变换，可以得到形式为G=[I_k，A]的生成矩阵，其中I_k是一个k×k单位矩阵，A是一个k×(n-k)矩阵.由G可得形如H=[-A^T，I_n-k]的一个校验矩阵.用H_i表示H^T的第i行向量，即

对于(41，21，9) QR码，矩阵A为

当给定信息向量m=[m₀，m₁，…，m_k-1]，码字c通过

进行编码得到.向量[m₀，m₁，…，m_k-1]和[p₀，p₁，…，p_n-k-1]分别为码字c的信息部分和校验部分.另外，对于接收向量r，它的校验子s=rH^T.

为了更好了解FSWDA算法，我们先给出相关的定义和结论.需要注意的是这些结论都是针对(n，k，d)二进制循环码，所有计算都在域GF(2) 上进行，而H=[A^T，I]是它的一个校验矩阵.

定义1 一个向量z的非零分量的个数称为向量z的汉明重量，记为w(z).向量a-b的汉明重量w(a-b)表示向量a和向量b的不同分量的个数，又称为向量a和向量b的汉明距离.

设e是错误向量e=[e_M，e_P]=[e₀，e₁，…，e_n-1]，其中e_M=[e₀，e₁，…，e_k-1]是信息部分，e_P=[e_k，e_k+1，…，e_n-1]是校验部分，w(e)≤t，s=eH^T.

下面这个结论在后面的证明中多次用到：

定理1 若H=[A^T，I]，e=[e_M，0_1×(n-k)]≠0_n，则w(eH^T)≥d-w(e_M).

证 因为码字的重量至少是d，e_M[I，A]=[e_M，e_MA]是码字，所以w(e_M)+w(e_MA)≥d.而

故w(eH^T)=w(e_MA)≥d-w(e_M).

在纠错范围内，定理2和定理3确定何时错误只出现在校验部分.

定理2 若e=[0_1×k，e_P]，其中w(e_P)≤t，则w(s)=w(eH^T)≤t.

证 由H=[A^T，I]的结构可得

故w(s) =w(e_P)≤t.

定理3 若e=[e_M，e_P]，其中w(e_M)≥1，w(e_M)+w(e_P)≤t，则w(s)=w(eH^T)≥t+1.

证 此时

故结论成立.

推论1 若w(e)≤t，则w(eH^T)≤t当且仅当e=[0_1×k，eH^T].

当e=[e_M，e_P]时，下面的定理给出了e_P与e的伴随式和e_M的伴随式之间的一个关系.

定理4 设e=[e_M，e_P].若[e_M，0_1×(n-k)]H^T=s_M，则e_P=eH^T-s_M.

证 因为w(e_P)≤w(e)≤t，所以

结论得证.

下面的定理是我们的查表译码算法正确性的理论基础.

定理5 设w(e)≤t，e=[e_M，e_P]，w(e_M)≥1.若eH^T=s，则存在唯一一个 $\mathit{\boldsymbol{\hat e}}{\rm{ = }}\left[ {{{\mathit{\boldsymbol{\hat e}}}_{M,}}{\bf{0}}} \right]$ 及相应的校验子 ${\mathit{\boldsymbol{\hat s}}}$ ，使得 $w\left( {\mathit{\boldsymbol{s}} - \mathit{\boldsymbol{\hat s}}} \right) = w\left( {{{{\bf{\hat e}}}_M}} \right) \le t$ .此时一定有 $\mathit{\boldsymbol{e = }}\left[ {\mathit{\boldsymbol{\hat e}},\mathit{\boldsymbol{s - \hat s}}} \right].$ .

证 当 ${{\mathit{\boldsymbol{\hat e}}}_M} = {\mathit{\boldsymbol{e}}_M}$ 时，由定理4知e_P=s- ${\mathit{\boldsymbol{\hat s}}}$ ，故w(s- ${\mathit{\boldsymbol{\hat s}}}$ )+w( ${\mathit{\boldsymbol{\hat e}}}$ _M)=w(e_p)+w(e_M)≤t，说明存在性成立.下面只需证当 ${\mathit{\boldsymbol{\hat e}}}$ _M≠e_M时必有w([s-s_i，e_Mⁱ])≥t+1，可证明唯一性也成立.实际上

当得到接收向量r时，向右循环i个比特可以得到r⁽ⁱ⁾=[r_n-i，…，r_n-1，r₀，…，r_n-i-1].通过s⁽ⁱ⁾=r⁽ⁱ⁾H可以得到r⁽ⁱ⁾的校验子.由r=c+e易得r⁽ⁱ⁾=c⁽ⁱ⁾+e⁽ⁱ⁾.换句话说，如果r的错误模式是e，那么e⁽ⁱ⁾是r⁽ⁱ⁾相应的错误模式.根据推论1，若1≤w(s)≤4，则错误仅出现在r的校验部分；若1≤w(s^(n-k))≤4，则错误仅出现在r的信息部分.设e₀=[1，0，…，0]是n维向量，e_j为仅在下标为j的位置有错误的n维向量(除第j位为1外，其它位均为0)，相应的校验子s_j= e_jH^T=H_j，0≤j≤k-1.显然，在第i位和第j位比特发生错误可用e_i+e_j来表示，H_i+H_j是e_i+e_j的校验子，其中0≤i≠j≤k-1.在这里可以看出，校验子、校验矩阵和错误模式的紧密联系，这就是不需要存储校验子和错误模式构成的表却仍可查表译码的原因.设sd_w为第w步校验子s与h_i的差值，即s-h_i，FSWDA算法通过sd_w的汉明重量，能很快地确定错误模式.

用大写字母F，M和P分别表示r的第一个信息比特、其余信息比特和校验比特.对于(41，21，9) QR码，共有24种错误情况(P，PP，PPP，PPPP，M，MM，MMM，MMMM，F，FP，MP，FPP，MPP，FPPP，MPPP，FM，FMM，MMP，FMMM，MMMP，FMP，FMPP，MMPP，FMMP)，覆盖了所有 $\sum \begin{array}{l} 4\\ i = 1 \end{array} \left( \begin{array}{l} 41\\ i \end{array} \right) = 112791$ 个错误模式.如果w(s)=0，那么接收向量r没有错误.如果1≤w(s)≤4或者1≤w(s⁽²⁰⁾)≤4，那么可以解决8种错误情况(P，PP，PPP，PPPP，M，MM，MMM，MMMM).计算sd₃=(s-h_i)，0≤i≤20.如果1≤w(sd₃)≤3，那么又可解决7种错误情况(F，FP，MP，FPP，MPP，FPPP，MPPP).若还没解决，则继续计算sd₄=(s⁽²⁰⁾-h_i)，0≤i≤20.如果1≤w(sd₄)≤3，那么又有5种错误情况(FM，FMM，MMP，FMMM，MMMP)被检测解决.若仍未解决，则再计算sd₅=(s-h_i-h_j)，0≤i≤19，i+1≤j≤20.如果1≤w(sd₅)≤2，那么3种错误情况(FMP，FMPP，MMPP)能被检测解决.若上述还不能找到错误，则需要计算sd₆=(s⁽²⁰⁾-h₂₀-h_i)，0≤i≤19.如果w(sd₆)=2，那么一定属于(FMMP)这种错误情况. 表 1列出了FSWDA算法每一步能解决的错误情况及相应的错误模式数量. FSWDA算法具体译码步骤如下：

1) 错误情况为(P，PP，PPP，PPPP).根据推论1，计算s和w(s).如果0≤w(s)≤4，那么错误模式e=[0_1×21，s].跳至7)；

2) 错误情况为(M，MM，MMM，MMMM).根据推论1，计算w(s⁽²⁰⁾).如果1≤w(s⁽²⁰⁾)≤4，那么错误模式e⁽²⁰⁾=[0_1×21，s⁽²⁰⁾]，也就是说，e=[0_1×1，s⁽²⁰⁾，0_1×20]，跳至7)；

3) 错误情况为(F，FP，MP，FPP，MPP，FPPP，MPPP).计算sd₃=(s-h_i)，0≤i≤20.如果0≤w(sd₃)≤3，那么错误向量e=e_i+[0_1×21，sd₃].跳至7)；

4) 错误情况为(FM，FMM，MMP，FMMM，MMMP).计算sd₄=(s⁽²⁰⁾ -h_i)，0≤i≤20.如果1≤w(sd₄)≤3，那么错误向量e⁽²⁰⁾=e_i+[0_1×21，sd₄]，也就是说，e=e_[i-20]+[0_1×1，sd₄，0_1×20]，其中, e的下标[x]表示x模41.跳至7)；

5) 错误情况为(FMP，FMPP，MMPP).计算sd₅=(s-h_i-h_j)，0≤i≤19，i+1≤j≤20.如果1≤w(sd₅)≤2，那么错误向量e=e_i+e_j+[0_1×21，sd₅].跳至7)；

6) 错误情况为(FMMP).计算sd₆=(s⁽²⁰⁾-h₂₀-h_i)，0≤i≤19.如果1≤w(sd₆)≤2，那么错误模式e⁽²⁰⁾=e₂₀+e_i+[0_1×21，sd₆].也就是说，e=e₀+e_[i-20]+ [0_1×1，sd₆，0_1×20]，跳至7)；

7) 计算c=r+e.跳至8)；

8) 结束.

本文利用Matlab对(41，21，9) 码纠错范围内的所有112791种错误进行模拟测试，所需平均译码时间大约为3.062 0×10^-4s，并与文献[5-6]中提出的算法进行对比，运算速度基本相当，但其突出特点是能够节省存储空间，对于存储能力有限的终端，特别是移动终端来说具有一定实际意义.