一种(41, 21, 9)平方剩余码的快速代数译码算法

吴怡; 罗春兰; 张新球; 林潇; 徐哲鑫

doi:10.11999/JEIT170983

一种(41, 21, 9)平方剩余码的快速代数译码算法

doi: 10.11999/JEIT170983

福建师范大学福建省光电传感应用工程技术研究中心福州 350007

基金项目: 国家自然科学基金(61571128, 61701118)

详细信息

作者简介:
吴怡：女，1970 年生，教授、博士生导师，研究方向为无线自组织网、信道编码

罗春兰：女，1994 年生，硕士生，研究方向为信道编码

张新球：男，1954 年生，博士，研究方向为差错控制编码

林潇：男，1981 年生，助理研究员，研究方向为无线网络通信

徐哲鑫：男，1985 年生，副教授，研究方向为无线自组织网络

通讯作者:
吴怡　 wuyi@fjnu.edu.cn

中图分类号: TN911.22
计量
- 文章访问数: 1670
- HTML全文浏览量: 604
- PDF下载量: 49
- 被引次数: 2
出版历程
- 收稿日期: 2017-10-23
- 修回日期: 2018-04-23
- 网络出版日期: 2018-05-30
- 刊出日期: 2018-08-01

A Fast Algebraic Decoding of the (41, 21, 9) Quadratic Residue Code

Fujian Provincial Engineering Technology Research Center of Photoelectric Sensing Application, Fujian Normal University, Fuzhou 350007, China

Funds: The National Natural Science Foundation of China (61571128, 61701118)

摘要

摘要: 为了降低译码时的计算复杂度以及减少译码时间，该文通过对牛顿恒等式进行推导得到了(41, 21, 9) QR码不需要计算未知校验子就可求得错误位置多项式系数的代数译码算法，同时也针对改善部分客观地给出了计算复杂度的理论分析。此外，为了进一步降低译码时间，提出判定接收码字中出现不同错误个数的更简化的判断条件。仿真结果表明该文提出算法在不降低Lin算法所达到的译码性能的前提下，降低了译码时间。
- 平方剩余码 /
- 代数译码 /
- 牛顿恒等式 /
- 未知校验子 /
- 错误位置多项式
Abstract: In order to reduce the computational complexity of computing unknown syndromes for the coefficients of the error-locator polynomial and reduce the decoding time when one is decoding, this paper proposed an algebraic decoding algorithm of (41, 21, 9) QR code without calculating the unknown syndromes by solving the Newtonian identity. Simultaneously, an objective theoretical analysis of the computational complexity is given for the part of improvement. Besides, this paper also puts forward the simplifying conditions to determine the number of errors in the received word, which in order to further reducing the decoding time. Simulation results show that the proposed algorithm reduces the decoding time with maintaining the same decoding performance of Lin’s algorithm.
- Quadratic residue code /
- Algebraic decoding /
- Newtonian identity /
- Unknown syndrome /
- Error-locator polynomial

HTML全文

1. 引言

平方剩余(Quadratic Residue, QR)码的概念是Prang^[1]在1957年发表的一篇报告中首次提出的。QR码是循环(Bose, ray-Chaudhuri and Hocquenghem, BCH)码的一个重要子类，它不仅具有丰富并且严谨的代数结构，还拥有较大的最小汉明距离以及接近于1/2的码率。比如(23, 12, 7) QR码^[2](也称为Golay码)是一个完备码，能够纠正23位分位码组中的最多3个错误。在过去，最为广泛使用的代数译码算法是用Sylvester结子^[3]，Gröbner基^[4]的方法来计算牛顿恒等式确定错误位置多项式。最后再使用Chien^[5]搜索法找出错误位置多项式的根，从而完成译码。此外，也有利用查表法^[6]快速求解QR码，但需要使用额外的内存，最近也有利用QR码的循环特性不用计算错误位置多项式来直接译码^[7]，这两种方法都没有涉及错误位置多项式。由于不同码长QR码的相关未知校验子都不相同，所以到目前为止还没有一个通用的代数译码方法对所有的QR码进行译码。比如(47, 24, 11)QR码^[8]以及(71, 36, 11)QR码^[9–11]，均能纠正5个错，但其未知校验子分别为S₅和S₇。在译码时为了求得错误位置多项式的系数，文献[8]及文献[9]分别提出了当判定接收码字中出现4个错的时候求解错误位置多项式的系数避免了未知校验子的代数译码算法。

在1992年，Reed等人^[3]首次提出了对(41, 21, 9)QR码的一种代数译码方法，即利用Sylvester结子的方法去计算牛顿恒等式从而找到错误位置多项式，再求解错误位置多项式的解，找到错误位置，修正错误达到译码的目的。但是，可以发现文献[3]中当判定接受码字中出现错误的个数为3个或者4个的时候，在译码时需要很高的计算复杂度和较大的存储空间。为了改善这个问题，Lin等人^[12]提出了对(41, 21, 9)QR码的一个有效的代数译码方法，称为Lin算法。该算法是利用Feng等人^[13]提供的方法，即根据(41, 21, 9)QR码的已知校验子去计算未知校验子S₃，从而求得错误位置多项式的系数，然后求解出错误的位置进而完成译码。实验仿真表明Lin算法在计算未知校验子S₃时需要很长的时间。鉴于此，本文提出了(41, 21, 9)QR码一个新的快速代数译码算法。当判定接收码字中出现错误个数分别为2, 3, 4个时，通过对牛顿恒等式进行数学推导，得出了不需要计算未知校验子就能求得相关的错误位置多项式系数的代数译码算法，该算法可以降低译码时的计算复杂度。此外，本文还提出了判定接收码字中出现不同错误个数的更加简单的判断条件，从而能够进一步降低在译码时的仿真时间。将所有的码字经过BPSK调制后传输到加性高斯白噪声(AWGN)信道中，仿真结果表明，本文提出的算法的性能与原有算法的性能一致，然而当判定接收码字中出现的错误个数为1, 2, 3, 4个的时候，译码时间分别减少了83.72%, 62.99%, 15.92%, 14.98%。

2. (41, 21, 9)QR码

在有限域GF(2^m)上，(n, k, d)QR码的码长质数n是由 $n = 8l \pm 1{,}l \in N$ 得到的，其中m是满足 $n|({2^m} - 1)$ 的最小正整数； $k = (n + 1)/{\rm{2}}$ 表示的是该码的信息长度；最大纠错能力 $t = \left\lfloor {(d - 1)/2} \right\rfloor$ 是由最小汉明距离d决定的。令Q_n为QR码的平方剩余集，即 ${Q_n} = \{ j|j \equiv {x^2}{\rm{mod}}n,1 \le x \le (n - 1)\}$ 。因此，(41, 21, 9)QR码是在有限域GF(2²⁰)上构建的，纠错能力为4个错的一种QR码，其平方剩余集为

$\begin{align}{Q_{41}} =& \{ 1,2,4,5,8,9,10,16,18,20,21,23,25,\\&\quad 31,32,33,36,37,39,40\}\end{align}$

(1)

假设 $\alpha$ 为有限域GF(2²⁰)的本原元，则 $\beta = {\alpha ^u}$ ，其中 $u = ({2^m} - 1)/n = ({2^{20}} - 1)/41 = 25575$ ，是GF(2²⁰)上的一个本原41次的单位根。于是(41, 21, 9) QR码的生成多项式可表示为

$\begin{align}g(x) =& \prod\limits_{i \in {Q_{41}}} {(x - {n^i})} = {x^{20}} + {x^{19}} + {x^{17}} + {x^{16}} + {x^{14}} \\& + {x^{11}} + {x^{10}} + {x^9} + {x^6} + {x^4} + {x^3} + x + 1\end{align}$

(2)

假设输入的信息多项式为 $m(x) =$ $\displaystyle\sum\nolimits_{i = 0}^{{\rm{20}}}{{m_i}{x^i}}$ ，其中 ${m_i} \in {\rm{GF(2)}}$ ，接收码字c(x)是生成多项式g(x)与信息多项式m(x)的乘积，即 $c(x) =$ $m(x)g(x) = \displaystyle\sum\nolimits_{i = 0}^{40} {{c_i}{x^i}}$ ，其中 ${c_i} \in {\rm{GF(2)}}$ 。码字c(x)经过AWGN信道，受到噪声e(x)干扰后的接收码字为

$r{\rm{(}}x{\rm{)}} = c{\rm{(}}x{\rm{)}} + e{\rm{(}}x{\rm{)}} = \sum\limits_{i = 0}^{{\rm{40}}} {{c_i}{x^i}} + \sum\limits_{i = 0}^{{\rm{40}}} {{e_i}{x^i}}$

(3)

定义已知校验子：

$\begin{align}{S_i} = & r({\beta ^i}) = e({\beta ^i}) = {e_{{\rm{40}}}}{({\beta ^i})^{{\rm{40}}}} + {e_{{\rm{39}}}}{({\beta ^i})^{{\rm{39}}}} \\& + ·\!·\!·+ {e_1}({\beta ^i}) + {e_0}\end{align}$

(4)

其中， $i \in {Q_{41}}$ 。如果 $i \notin {Q_{41}}$ , S_i则称为未知校验子，例如 $3 \notin {Q_{41}}$ ，所以S₃是(41, 21, 9)QR码的未知校验子。除此之外，如果接收码字中发生的错误个数为奇数， ${S_0} = 1$ ；否则 ${S_0} = 0$ 。

若(41, 21, 9)QR码的码字在传输的过程中受到干扰时发生错误的个数v ≤ 4，则错误多项式e(x)为

$\begin{align}e(x) =& {x^{{l_{\rm{1}}}}} + {x^{{l_{\rm{2}}}}} + ·\!·\!· + {x^{{l_v}}}, \\ & 0 \le {l_1} < {l_2} < ·\!·\!· < {l_v} \le 40\end{align}$

(5)

根据式(4)和式(5)，可以得到校验子： ${S_i} = X_1^i + X_2^i + ·\!·\!· + X_v^i$ ，其中 ${X_j} = {\beta ^{{l_j}}},1 \le j \le v$ ，记做接收码字中发生错误的错误位置。定义错误位置多项式，记为L(z)，表示如式(6)：

$\begin{align}L(z) = & \prod\limits_{j = 1}^v {(z - {X_j})} = (z - {X_1})(z - {X_2}) ·\!·\!· (z - {X_v}) \\ =& {\sigma _0}{{{z}}^v} + ·\!·\!· + {\sigma _{v - 1}}z + {\sigma _v}\end{align}$

(6)

L(z)的系数可以表示为

$\left. \begin{array}{l} {\sigma _0} = {\rm{1}} \\ {\sigma _1} = {X_1} + {X_2} + ·\!·\!· + {X_v} \\ {\sigma _2} = {X_1}{X_2} + {X_1}{X_3} + ·\!·\!·+ {X_{v - 1}}{X_v} \\ \;\, \vdots \\ {\sigma _v} = {X_1}{X_2} ·\!·\!· {X_v} \\ \end{array} \right\}$

(7)

确定了错误位置多项式的系数后，求解出错误位置多项式L(z)，然后利用Chien搜索法找到L(z)的根，即是错误的位置，将此位置的错误改正过来，就完成了译码的目的。

3. (41, 21, 9)QR码的代数译码算法

在文献[12]的Lin算法中，当判定接收码字中的错误个数分别为2, 3, 4的时候，在计算相关的错误位置多项式的系数时需要计算未知校验子S₃，但是计算未知校验子非常复杂，占用内存多。所以，本文提出了一种仅用已知校验子直接求得相关错误位置多项式系数的代数译码算法。

3.1 新的错误位置多项式的推导

为了能够得到(41, 21, 9)QR码的一种不需要计算未知校验子就可以求解出错误位置多项式的系数的算法，需要引进可以表明S_i和 $\sigma$ _j关系的牛顿恒等式即引理1和引理2，详细的证明可以分别参见文献[14]和文献[3]。

引理 1　(牛顿恒等式)　对于二进制QR码，校验子S_i和 $\sigma_j$ 存在对称关系，即

$\!\!\!\! \begin{array}{c}\left. \begin{align}&{S_i} + \sum\limits_{j = 1}^{i - 1} {{\sigma _j}} {S_{i - j}} + {\sigma _j} = 0,1 \le i \le v,\ i{{为奇数}} \\&{S_i} + \sum\limits_{j = 1}^{i - 1} {{\sigma _j}} {S_{i - j}} = 0,1 \le i \le v,\quad\quad \ i {{为偶数}}\\&{S_i} + \sum\limits_{j = 1}^v {{\sigma _j}} {S_{i - j}} = 0,\quad\quad\quad\quad\quad\quad\ \ i \ge v\end{align}\!\!\!\!\!\! \right\}\end{array}$

(8)

引理 2　当(n, k, d)QR码的接收码字中出现错误个数v ≥ 2时，就有 ${S_{n - 1}}{\sigma _v} = {\sigma _{v - 1}}$ 。

当(41, 21, 9)QR码的接收码字中出现的错误个数 $2 \le v \le 4$ 时，其不需要计算未知校验子的错误位置，多项式的系数可以从式(9)–式(23)的牛顿恒等式中获得。

${S_1} + {\sigma _1} = 0\hspace{180pt}$

(9)

${S_3} + {\sigma _1}{S_2} + {\sigma _2}{S_1} + {\sigma _3} = 0\hspace{115pt}$

(10)

${S_5} + {\sigma _1}{S_4} + {\sigma _2}{S_3} + {\sigma _3}{S_2} + {\sigma _4}{S_1} = 0 \hspace{72pt}$

(11)

${S_{20}} + {\sigma _1}{S_{19}} + {\sigma _2}{S_{18}} + {\sigma _3}{S_{17}} + {\sigma _4}{S_{16}} = 0\hspace{53pt}$

(12)

${S_{21}} + {\sigma _1}{S_{20}} + {\sigma _2}{S_{19}} + {\sigma _3}{S_{18}} + {\sigma _4}{S_{17}} = 0\hspace{53pt}$

(13)

${S_{22}} + {\sigma _1}{S_{21}} + {\sigma _2}{S_{20}} + {\sigma _3}{S_{19}} + {\sigma _4}{S_{18}} = 0\hspace{53pt}$

(14)

${S_{23}} + {\sigma _1}{S_{22}} + {\sigma _2}{S_{21}} + {\sigma _3}{S_{20}} + {\sigma _4}{S_{19}} = 0\hspace{53pt}$

(15)

${S_{24}} + {\sigma _1}{S_{23}} + {\sigma _2}{S_{22}} + {\sigma _3}{S_{21}} + {\sigma _4}{S_{20}} = 0\hspace{53pt}$

(16)

${S_{25}} + {\sigma _1}{S_{24}} + {\sigma _2}{S_{23}} + {\sigma _3}{S_{22}} + {\sigma _4}{S_{21}} = 0\hspace{53pt}$

(17)

${S_{34}} + {\sigma _1}{S_{33}} + {\sigma _2}{S_{32}} + {\sigma _3}{S_{31}} + {\sigma _4}{S_{30}} = 0\hspace{53pt}$

(18)

${S_{35}} + {\sigma _1}{S_{34}} + {\sigma _2}{S_{33}} + {\sigma _3}{S_{32}} + {\sigma _4}{S_{31}} = 0 \hspace{53pt}$

(19)

${S_{36}} + {\sigma _1}{S_{35}} + {\sigma _2}{S_{34}} + {\sigma _3}{S_{33}} + {\sigma _4}{S_{32}} = 0\hspace{53pt}$

(20)

${S_{38}} + {\sigma _1}{S_{37}} + {\sigma _2}{S_{36}} + {\sigma _3}{S_{35}} + {\sigma _4}{S_{34}} = 0\hspace{53pt}$

(21)

${S_{39}} + {\sigma _1}{S_{38}} + {\sigma _2}{S_{37}} + {\sigma _3}{S_{36}} + {\sigma _4}{S_{35}} = 0 \hspace{53pt}$

(22)

${S_{40}} + {\sigma _1}{S_{39}} + {\sigma _2}{S_{38}} + {\sigma _3}{S_{37}} + {\sigma _4}{S_{36}} = 0\hspace{53pt}$

(23)

本文提出的避免未知校验子的快速译码算法中求解错误位置多项式的步骤具体如下：

(1) 当接收码字中出现错误个数v=2时，由式(9)–式(11)结合引理2，可以得到 $\sigma_1$ 和 $\sigma_2$ 的表达式为： ${\sigma _{\rm{1}}} = {S_{\rm{1}}},\ {\sigma _{\rm{2}}} = {{{S_{\rm{1}}}} / {{S_{{\rm{40}}}}}}$ ，所以当接到码字中出现错误个数v=2时，其错误位置多项式为

$L{}_2(z) = {z^2} + {\sigma _1}z + {\sigma _2} = {z^2} + {S_1}z + {{{S_1}} / {{S_{40}}}}$

(24)

(2) 当接收码字中出现错误个数v=3时，由式(9)–式(11)，式(18)–式(20)，式(22)和式(23)结合引理2，可以得到

$\begin{align}{\sigma _1} =& {S_1}{,}{\sigma _2} = {\sigma _1}{S_{40}}{,}\\ {\sigma _3} =& {{({B_{36}}{B_0} + {A_5}{B_{31}})} / {{A_{33}}{B_0}}}\end{align}$

(25)

其中， ${A_{\rm{5}}} = S_{\rm{1}}^{\rm{5}} \!+\! {S_{\rm{5}}}$ , ${A_{{\rm{33}}}} = S_{\rm{1}}^{{\rm{33}}} \!+\! {S_{{\rm{33}}}}$ , ${B_{\rm{0}}} = {S_{\rm{1}}}{S_{{\rm{40}}}} \!+\! {\rm{1}}$ , ${B_{{\rm{31}}}} = S_{\rm{1}}^{{\rm{32}}}{S_{{\rm{40}}}} + {S_{{\rm{31}}}}$ , ${B_{{\rm{36}}}} = S_{\rm{1}}^{\rm{3}}{S_{{\rm{33}}}} + {S_{{\rm{31}}}}$ ，所以当接到码字中出现错误个数v=3时，其错误位置多项式为

$\begin{align}L{}_3(z) =& {z^3} + {S_1}{z^2} + ({{({B_{36}}{B_0} + {A_5}{B_{31}})} / {{A_{33}}{B_0}}})\\ & \cdot ({S_{40}}z + 1)\end{align}$

(26)

(3) 当接收码字中出现错误个数v=4时，由式(9)–式(11)可以得到 $\sigma_2$ 与 $\sigma_4$ 的关系式如式(27)：

$\begin{align}\sigma _2^2{S_1} &+ {\sigma _2}\left({\sigma _4}{S_{40}} + S_1^3\right) + {\sigma _4}\left(S_1^2{S_{40}}\right. \\&\left. + {S_1}\right) + S_1^5 + {S_5} = 0\end{align}$

(27)

由式(12)–式(15)可以得到 $\sigma_2$ 与 $\sigma_4$ 的关系式如式(28)：

$\begin{align}& \sigma _2^2({S_{\rm{1}}}{S_{{\rm{20}}}}{S_{{\rm{40}}}} + {S_{21}}{S_{{\rm{40}}}}) + {\sigma _2}\left({\sigma _4} \left({S_{{\rm{18}}}} + {S_{{\rm{20}}}}S_{{\rm{40}}}^2\right)\right. \\&\quad\left. + S_{\rm{1}}^2{S_{{\rm{20}}}} + {S_{\rm{1}}}{S_{{\rm{21}}}} + S_{\rm{1}}^2{S_{{\rm{21}}}}{S_{{\rm{40}}}} + {S_{{\rm{23}}}}{S_{{\rm{40}}}}\right) \\& \quad+\sigma _4^2 \left(S_{\rm{1}}^{16} + S_{\rm{1}}^{17}{S_{{\rm{40}}}} + {S_{{\rm{18}}}}S_{{\rm{40}}}^2 + {S_{\rm{1}}}{S_{{\rm{18}}}}S_{{\rm{40}}}^3\right) \\& \quad+ {\sigma _4}\left(S_{\rm{1}}^2{S_{{\rm{18}}}} + {S_{20}} + {S_1}{S_{20}}{S_{40}} + S_{\rm{1}}^2{S_{20}}S_{40}^2 \right. \\&\quad \left. + {S_{{\rm{21}}}}{S_{{\rm{40}}}}+ {S_{\rm{1}}}{S_{{\rm{21}}}}S_{{\rm{40}}}^2\right) + S_{\rm{1}}^3{S_{21}} + {S_1}{S_{23}} = 0 \end{align}$

(28)

由式(14)–式(17)可以得到 $\sigma_2$ 与 $\sigma_4$ 的关系式如式(29)：

$\begin{align}& \sigma _2^2 \left( {S_{\rm{1}}}{S_{{\rm{20}}}} + {S_{\rm{1}}}{S_{{\rm{21}}}}{S_{{\rm{40}}}}\right) + {\sigma _2}\bigr ( {\sigma _4} \bigr( {S_{\rm{1}}}{S_{{\rm{18}}}} + {S_{{\rm{20}}}}{S_{40}}\\& \quad + {S_1}{S_{20}}S_{40}^2 + {S_{{\rm{21}}}}S_{40}^2\bigr) + S_{\rm{1}}^2{S_{21}} + {S_{23}}\bigr) \\& \quad+\sigma _4^2 \left( {S_{18}}{S_{40}} + {S_{20}}S_{{\rm{40}}}^3\right) + {\sigma _4} \left( {S_{\rm{1}}}{S_{{\rm{20}}}} + S_{\rm{1}}^2{S_{{\rm{20}}}}{S_{{\rm{40}}}} \right. \\ & \quad \left. + {S_{{\rm{21}}}} + {S_{\rm{1}}}{S_{{\rm{21}}}}{S_{{\rm{40}}}} + S_{\rm{1}}^2{S_{{\rm{21}}}}S_{{\rm{40}}}^2 + {S_{{\rm{23}}}}S_{{\rm{40}}}^2\right) \\& \quad+S_{\rm{1}}^2{S_{23}} + S_1^3{S_{23}}{S_{40}} + {S_{25}} + {S_1}{S_{25}}{S_{40}} = 0 \end{align}$

(29)

由式(19)–式(23)可以得到 $\sigma_2$ 与 $\sigma_4$ 的关系式如式(30)：

$\begin{align}& \sigma _2^2\left({\sigma _4}{S_{33}} + {S_1}{S_{36}} + {S_{37}} + {S_1}{S_{37}}{S_{40}}\right) \\& \quad +{\sigma _2}\left(\sigma _4^2\left({S_{31}} + {S_{32}}{S_{40}}\right) + {\sigma _4}\bigr({S_{36}}{S_{40}}\right. \\& \quad \left.\left.+ {S_1}{S_{36}}S_{40}^2\right) + S_1^2{S_{37}} + {S_{39}} + {S_1}{S_{39}}{S_{40}}\right) \\& \quad + {\sigma _4}\left(S_1^2{S_{36}}{S_{40}} + S_1^2{S_{37}}S_{40}^2 \right) + S_1^2S_{40}^2 \\& \quad+ S_1^3{S_{39}}{S_{40}} = 0 \end{align}$

(30)

为了化简式(27)–式(30)中的 $\sigma_2$ 和 $\sigma_4$ ，定义：

${a_{112}} = {S_1}{S_{31}} + {S_1}{S_{32}}{S_{40}} + {S_{33}}{S_{40}}\hspace{67pt}$

(31)

${a_{111}} = S_1^3{S_{33}} + S_1^2{S_{36}}S_{40}^2 + {S_{37}}{S_{40}} + {S_1}{S_{37}}S_{40}^2\hspace{12pt}$

(32)

${a_{110}} = S_1^4{S_{36}} + S_1^4{S_{37}}{S_{40}} + {S_1}{S_{39}} + S_1^2{S_{39}}{S_{40}}\hspace{15pt}$

(33)

${a_{102}} = {S_1}{S_{33}} + S_1^2{S_{33}}{S_{40}}\hspace{125pt}$

(34)

${a_{101}} = S_1^5{S_{33}} + {S_5}{S_{33}} + S_1^2{S_{36}} + {S_1}{S_{37}}\hspace{80pt}$

(35)

$\begin{align}{a_{100}} =& S_1^3S_{40}^2 + S_1^6{S_{36}} + {S_1}{S_5}{S_{36}} + S_1^6{S_{37}}{S_{40}} \\& + S_1^5{S_{37}} + {S_5}{S_{37}} + {S_1}{S_5}{S_{37}}{S_{40}} + S_1^4{S_{39}}{S_{40}}\end{align}$

(36)

${a_{211}} = {S_1}{S_{18}} + {S_1}S_{40}^2\hspace{155pt}$

(37)

${a_{210}} = S_1^3{S_{20}} + S_1^4{S_{20}}{S_{40}} + S_1^2{S_{21}} + {S_1}{S_{23}}{S_{40}}\hspace{17pt}$

(38)

${a_{202}} = S_1^{17} + S_1^{18}{S_{40}} + {S_1}{S_{18}}S_{40}^2 + S_1^2{S_{18}}S_{40}^3\hspace{45pt}$

(39)

${a_{201}} = S_1^3{S_{18}} + {S_1}{S_{20}}\hspace{165pt}$

(40)

$\begin{align}{a_{200}} = & S_1^6{S_{20}}{S_{40}} + {S_1}{S_5}{S_{20}}{S_{40}} + S_1^4{S_{21}} + S_1^5{S_{21}}{S_{40}} \\& + {S_5}{S_{21}}{S_{40}} + S_1^2{S_{23}} \hspace{140pt}\end{align}$

(41)

${a_{311}} = {S_1}{S_{18}} + {S_1}{S_{20}}S{_{40}^2}\hspace{140pt}$

(42)

${a_{310}} = S_1^3{S_{20}} + S_1^2{S_{21}} + S_1^3{S_{21}}{S_{40}} + {S_{23}}\hspace{140pt}$

(43)

${a_{302}} = {S_{20}}S_{40}^3 + S_1^{18}{S_{40}}\hspace{140pt}$

(44)

${a_{301}} = {S_{21}} + {S_{23}}S{_{40}^2}\hspace{150pt}$

(45)

$\begin{align}{a_{300}} =& S_1^5{S_{20}} + {S_5}{S_{20}} + S_1^5{S_{21}}{S_{40}} + {S_5}{S_{21}}{S_{40}} \\&+ S_1^2{S_{23}} + S_1^3{S_{23}}{S_{40}} + {S_{25}} + {S_1}{S_{25}}{S_{40}}\hspace{140pt}\end{align}$

(46)

$\begin{align} {n_3} =& {a_{102}}a_{211}^2{a_{302}} + {a_{111}}a_{202}^2{a_{311}} + {a_{112}}a_{202}^2{a_{310}} \\ & + {a_{102}}{a_{202}}{a_{211}}{a_{311}} + {a_{111}}{a_{202}}{a_{211}}{a_{302}} \\ &+ {a_{112}}{a_{201}}{a_{211}}{a_{302}} + {a_{112}}{a_{202}}{a_{210}}{a_{302}} \\ &+ {a_{112}}{a_{202}}{a_{211}}{a_{301}} \hspace{140pt} \end{align}$

(47)

$\begin{align} {n_2} =& {a_{101}}a_{211}^2{a_{302}} + {a_{110}}a_{202}^2{a_{311}}+ {a_{101}}{a_{202}}{a_{211}}{a_{311}} \\ &+ {a_{102}}{a_{202}}{a_{210}}{a_{311}} + {a_{102}}{a_{210}}{a_{211}}{a_{302}} \\ &+{a_{110}}{a_{202}}{a_{211}}{a_{302}} + {a_{111}}{a_{201}}{a_{202}}{a_{311}} \\ &+ {a_{111}}{a_{201}}{a_{211}}{a_{302}} + {a_{112}}{a_{200}}{a_{211}}{a_{302}} \\ &+ {a_{112}}{a_{201}}{a_{202}}{a_{310}} + {a_{112}}{a_{202}}{a_{210}}{a_{301}} \\ &+ {a_{112}}{a_{200}}{a_{202}}{a_{300}}\hspace{140pt} \end{align}$

(48)

$\begin{align} {n_1} =& {a_{100}}a_{211}^2{a_{302}} + {a_{100}}{a_{202}}{a_{211}}{a_{311}} + {a_{101}}{a_{202}}{a_{210}}{a_{311}} \\ &+ {a_{101}}{a_{210}}{a_{211}}{a_{302}} + {a_{110}}{a_{201}}{a_{202}}{a_{311}} + \\ &{a_{110}}{a_{201}}{a_{211}}{a_{302}} + {a_{111}}{a_{200}}{a_{202}}{a_{311}} \\ &+ {a_{111}}{a_{200}}{a_{211}}{a_{302}} + {a_{112}}{a_{200}}{a_{202}}{a_{310}} \\ &+ {a_{112}}{a_{202}}{a_{210}}{a_{300}} \end{align}$

(49)

$\begin{align}{n_0} =& {a_{100}}{a_{202}}{a_{210}}{a_{311}} + {a_{100}}{a_{210}}{a_{211}}{a_{302}} \\&+ {a_{110}}{a_{200}}{a_{202}}{a_{311}} + {a_{110}}{a_{200}}{a_{211}}{a_{302}}\hspace{140pt}\end{align}$

(50)

${m_3} = {a_{202}}{a_{311}} + {a_{211}}{a_{302}}\hspace{170pt}$

(51)

${m_2} = {a_{201}}{a_{311}} + {a_{202}}{a_{310}} + {a_{210}}{a_{302}} + {a_{211}}{a_{301}}\hspace{140pt}$

(52)

${m_1} = {a_{200}}{a_{311}} + {a_{201}}{a_{310}} + {a_{210}}{a_{301}} + {a_{211}}{a_{300}}\hspace{140pt}$

(53)

${m_0} = {a_{200}}{a_{310}} + {a_{210}}{a_{300}}\hspace{140pt}$

(54)

联合式(27)–式(30)，根据定义式(31)–式(54)，可以得到一个关于 $\sigma_2$ 和 $\sigma_4$ 的表达式如式(55)和式(56)：

${\sigma _2}({\sigma _4}{a_{211}} + {a_{210}}) + {\sigma _4}\!\!^2{a_{202}} + {\sigma _4}{a_{201}} + {a_{200}} = 0\hspace{25pt}$

(55)

${\sigma _4} = A/B\hspace{190pt}$

(56)

其中，

$\begin{aligned}A =& {m_{\rm{0}}}{n_{\rm{1}}}{n_{\rm{2}}}m_3^2 + {n_0}{n_1}m_3^3 + {m_0}n_2^2n_3^2 \\& + {m_0}{n_2}{n_3}{m_2}{m_3} + {n_0}{n_2}{m_2}m_3^2 + {m_0}n_3^2{m_1}{m_3} \\&+ {n_0}{n_3}{m_1}m_3^2 + {n_0}{n_3}m_2^2{m_3}\hspace{140pt}\end{aligned}$

$\begin{align} B =& n_1^2m_3^3 + {n_1}{n_2}m_3^2 + {n_1}{n_3}m_2^2{m_3} + n_2^2{m_1}m_3^2 \\ & + {n_2}{n_3}{m_1}{m_2}{m_3} + {m_0}{n_2}{n_3}m_3^2 + {n_0}{n_2}m_3^3 \\ & + n_3^2m_1^2{m_3} +{m_0}n_3^2{m_2}{m_3} + {n_0}{n_3}{m_2}m_3^2\hspace{140pt} \end{align}$

根据引理2和式(56)可以得到 $\sigma_3$ 为

${\sigma _3} = {\sigma _4}{S_{40}}$

(57)

由式(55)，可以得到 $\sigma_2$ 为

${\sigma _2} =\left ({\sigma _4}\!\!^2{a_{202}} + {\sigma _4}{a_{201}} + {a_{200}})/({\sigma _4}{a_{211}} + {a_{210}}\right)\hspace{30pt}$

(58)

当接到码字中出现错误个数v=4时， ${\sigma _{\rm{1}}} = {S_{\rm{1}}}$ , $\sigma_2$ , $\sigma_3$ , $\sigma_4$ 分别由式(58)，式(57)和式(56)给出，所以其错误位置多项式为

${L_4}(z) = {z^4} + {S_1}{z^3} + {\sigma _2}{z^2} + {\sigma _3}z + {\sigma _4}$

(59)

通过以上对牛顿恒等式结合定理的数学推导，可以清楚地看出本文提出的(41, 21, 9)QR码的代数译码算法中，当接收码字中出现错误个数v=2, 3, 4的时候，其错误位置多项式的系数中均没有出现未知校验子。

3.2 简化v=1, 2, 3时的判断条件进一步优化前述的快速代数译码算法

在译码过程中，不同错误模式情况下的判断条件对译码时间的影响是非常大的，如果能改善出现错误时的判断条件，就能进一步降低译码时间。文献[12]的算法中，判定接收码字中出现错误个数v=1时的判断条件是 $S_{\rm{1}}^{{\rm{41}}} = {\rm{1}}$ ，而本文提出的对应的判断条件为 ${S_1}^5 = {S_5}$ 极大地降低了计算量；当接收码字中出现错误个数v=2或3时，Lin算法中是利用行列式的值是否为0来进行判断的，而本文提出了比Lin算法更加简化的行列式，可以降低译码仿真所需要的时间。本文提出算法的具体步骤如下：

(1)如果 ${S_1} = 0$ ，那么没有错误发生， ${L_{\rm{0}}}(z) = 0$ ；

(2)如果 ${S_1}\!\!^5 = {S_5}$ ，那么就有1个错误发生， ${L_1}(z) =$ $z + {S_1}$ ；

(3)如果 ${\rm{det}}({{{C}}_{\rm{3}}}) = 0$ ，那么就有2个错误发生，错误位置多项式为式(24)，其中，

${{C}}_3 = \left[ {\begin{array}{*{20}{c}} {{S_0}}&{{S_8}}&{{S_{40}}} \\ {{S_1}}&{{S_9}}&{{S_0}} \\ {{S_{32}}}&{{S_{40}}}&{{S_{31}}} \end{array}} \right]$

(60)

(4)如果 ${\rm{det}}({{{C}}_{\rm{4}}}) = 0$ ，那么就有3个错误发生，错误位置多项式为式(26)，其中，

${{C}}_4 = \left[ {\begin{array}{*{20}{c}} {{S_1}}&{{S_{18}}}&{{S_{25}}}&{{S_{33}}} \\ {{S_8}}&{{S_{25}}}&{{S_{32}}}&{{S_{40}}} \\ {{S_{25}}}&{{S_1}}&{{S_8}}&{{S_{16}}} \\ {{S_{37}}}&{{S_4}}&{{S_{23}}}&{{S_{31}}} \end{array}} \right]$

(61)

(5)以上条件都不满足的情况下，则有4个错误发生，错误位置多项式为式(59)。

4. 计算复杂度分析

为了说明本文提出不用计算未知校验子的代数译码算法的复杂度与Lin算法^[12]相比有降低，现就针对 ${L_{\rm{4}}}(z)$ 分别对Lin算法和本文提出的算法的计算复杂度进行客观分析，因为在求解错误位置多项式时，相对于 ${L_{\rm{2}}}(z)$ 及 ${L_{\rm{3}}}(z)$ 的计算量， ${L_{\rm{4}}}(z)$ 最大也最具代表性。

4.1 Lin算法 ${{L}_{{4}}}$ ( ${z}$ )的计算复杂度

当判定接收码字中有4个错时，Lin算法的错误位置多项式如式(62)：

$\begin{align}{L_{\rm{4}}}(z) =& {z^{\rm{4}}} + {\sigma _{\rm{1}}}{z^{\rm{3}}} + {\sigma _{\rm{2}}}{z^{\rm{2}}} + {\sigma _{\rm{3}}}z + {\sigma _{\rm{4}}}{\rm{ = }}{z^{\rm{4}}} + {S_{\rm{1}}}{z^{\rm{3}}} \\&+ \frac{{{S_1}{A_{\rm{7}}} + {S_{\rm{3}}}{A_{\rm{5}}}}}{{{S_{\rm{1}}}{A_{\rm{5}}} + {S_{\rm{3}}}{A_{\rm{3}}}}}{z^{\rm{2}}} + ({A_{\rm{3}}} + {S_{\rm{1}}}{\sigma _{\rm{2}}})z \\&+ \frac{{{B_{\rm{5}}} + {A_{\rm{3}}}{\sigma _{\rm{2}}}}}{{{S_{\rm{1}}}}}\end{align}$

(62)

其中， ${A_{\rm{3}}} = S_{\rm{1}}^{\rm{3}} + {S_3}$ , ${A_{\rm{5}}} = S_{\rm{1}}^{\rm{5}} + {S_{\rm{5}}}$ , ${A_{\rm{7}}} = S_{\rm{1}}^{\rm{7}} + {S_{\rm{7}}}$ , ${B_{\rm{5}}} = S_{\rm{1}}^{\rm{2}}{S_{\rm{3}}} + {S_{\rm{5}}}$ 。

在求解错误位置多项式 ${L_{\rm{4}}}(z)$ 时，首先需要求解相关的未知校验子S₃，由文献[12]可知，S₃表达为

${S_{\rm{3}}} \!=\! \det ({{{C}}_{{\rm{40}}}})\bigr/\det ({{{C}}_{{\rm{41}}}}) \!=\! \det ({{{C}}_{{\rm{40}}}})\cdot{[\det ({{{C}}_{{\rm{41}}}})]^{ - 1}}$

其中，

${{{C}}_{{\rm{40}}}} \!=\! \left[\!\! {\begin{array}{*{20}{c}} {{S_{\rm{0}}}}&{{S_{\rm{2}}}}&{{S_{\rm{8}}}}&{\begin{array}{*{20}{c}} {{S_{\rm{9}}}}\ &\quad {{S_{{\rm{20}}}}} \end{array}} \\ {{S_{\rm{1}}}}&{\rm{0}}&{{S_{\rm{9}}}}&{\begin{array}{*{20}{c}} {{S_{{\rm{10}}}}}\ & \quad {{S_{{\rm{21}}}}} \end{array}} \\ {{S_{{\rm{23}}}}}&{{S_{{\rm{25}}}}}&{{S_{{\rm{31}}}}}&{\begin{array}{*{20}{c}} {{S_{{\rm{32}}}}}\ &\quad {{S_{\rm{2}}}} \end{array}} \\ {\begin{array}{*{20}{c}} {{S_{{\rm{31}}}}} \\ {{S_{{\rm{37}}}}} \end{array}}&{\begin{array}{*{20}{c}} {{S_{{\rm{33}}}}} \\ {{S_{{\rm{39}}}}} \end{array}}&{\begin{array}{*{20}{c}} {{S_{{\rm{39}}}}} \\ {{S_{\rm{4}}}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{S_{{\rm{40}}}}} \\ {{S_{\rm{5}}}} \end{array}}&{\begin{array}{*{20}{c}} {{S_{{\rm{10}}}}} \\ {{S_{{\rm{16}}}}} \end{array}} \end{array}} \end{array}} \!\!\!\!\right]\quad\quad$

(63)

${{{C}}_{{\rm{41}}}} = \left[ {\begin{array}{*{20}{c}} {{S_{\rm{0}}}}&{{S_{\rm{8}}}}&{{S_{\rm{9}}}}&{{S_{{\rm{20}}}}} \\ {{S_{{\rm{23}}}}}&{{S_{{\rm{31}}}}}&{{S_{{\rm{32}}}}}&{{S_{\rm{2}}}} \\ {{S_{{\rm{23}}}}}&{{S_{{\rm{39}}}}}&{{S_{{\rm{40}}}}}&{{S_{{\rm{10}}}}} \\ {{S_{{\rm{37}}}}}&{{S_{\rm{4}}}}&{{S_{\rm{5}}}}&{{S_{{\rm{16}}}}} \end{array}} \right]\hspace{100pt}$

(64)

其中，在v<4时已经计算出的已知校验子就作为已知量，当v=4时，这些已知校验子不再重复计算。并且是采用行(列)展开的方法进行运算的。

对 ${{{C}}_{{\rm{40}}}}$ 的第2行展开，则有

$\begin{gathered} \det ({{{C}}_{{\rm{40}}}}) = {S_{\rm{1}}}{{{C}}_{{\rm{401}}}} + {S_{\rm{9}}}{{{C}}_{{\rm{402}}}} + {S_{{\rm{10}}}}{{{C}}_{{\rm{403}}}} + {S_{{\rm{21}}}}{{{C}}_{{\rm{404}}}} \\ = {S_{\rm{1}}}\left[ {\begin{array}{*{20}{c}} {{S_{\rm{2}}}}&{{S_{\rm{8}}}}&{{S_{\rm{9}}}}&{{S_{{\rm{20}}}}} \\ {{S_{{\rm{25}}}}}&{{S_{{\rm{31}}}}}&{{S_{{\rm{32}}}}}&{{S_{\rm{2}}}} \\ {{S_{{\rm{33}}}}}&{{S_{{\rm{39}}}}}&{{S_{{\rm{40}}}}}&{{S_{{\rm{10}}}}} \\ {{S_{{\rm{39}}}}}&{{S_{\rm{4}}}}&{{S_{\rm{5}}}}&{{S_{{\rm{16}}}}} \end{array}} \right] \\ \quad\quad+ {S_{\rm{9}}}\left[ {\begin{array}{*{20}{c}} {{S_{\rm{0}}}}&{{S_{\rm{2}}}}&{{S_{\rm{9}}}}&{{S_{{\rm{20}}}}} \\ {{S_{{\rm{23}}}}}&{{S_{{\rm{25}}}}}&{{S_{{\rm{32}}}}}&{{S_{\rm{2}}}} \\ {{S_{{\rm{31}}}}}&{{S_{{\rm{33}}}}}&{{S_{{\rm{40}}}}}&{{S_{{\rm{10}}}}} \\ {{S_{{\rm{37}}}}}&{{S_{{\rm{39}}}}}&{{S_{\rm{5}}}}&{{S_{{\rm{16}}}}} \end{array}} \right] \\ \quad\quad+ {S_{{\rm{10}}}}\left[ {\begin{array}{*{20}{c}} {{S_{\rm{0}}}}&{{S_{\rm{2}}}}&{{S_{\rm{8}}}}&{{S_{{\rm{20}}}}} \\ {{S_{{\rm{23}}}}}&{{S_{{\rm{25}}}}}&{{S_{{\rm{31}}}}}&{{S_{\rm{2}}}} \\ {{S_{{\rm{31}}}}}&{{S_{{\rm{33}}}}}&{{S_{{\rm{39}}}}}&{{S_{{\rm{10}}}}} \\ {{S_{{\rm{37}}}}}&{{S_{{\rm{39}}}}}&{{S_{\rm{4}}}}&{{S_{{\rm{16}}}}} \end{array}} \right] \\ \quad\quad+ {S_{{\rm{21}}}}\left[ {\begin{array}{*{20}{c}} {{S_{\rm{0}}}}&{{S_{\rm{2}}}}&{{S_{\rm{8}}}}&{{S_{\rm{9}}}} \\ {{S_{{\rm{23}}}}}&{{S_{{\rm{25}}}}}&{{S_{{\rm{31}}}}}&{{S_{{\rm{32}}}}} \\ {{S_{{\rm{31}}}}}&{{S_{{\rm{33}}}}}&{{S_{{\rm{39}}}}}&{{S_{{\rm{40}}}}} \\ {{S_{{\rm{37}}}}}&{{S_{{\rm{39}}}}}&{{S_{\rm{4}}}}&{{S_{\rm{5}}}} \end{array}} \right] \\ \end{gathered}$

(65)

对式(65)的第1项中的 ${{{C}}_{{\rm{401}}}}$ 按第1行展开，则有

$\begin{aligned}& \det \left({{{C}}_{{\rm{401}}}}\right) \\& = {S_{\rm{2}}}{{{C}}_{{\rm{4011}}}} + {S_{\rm{8}}}{{{C}}_{{\rm{4012}}}} + {S_{\rm{9}}}{{{C}}_{{\rm{4013}}}} + {S_{{\rm{20}}}}{{{C}}_{{\rm{4014}}}} \\ & = {S_{\rm{2}}}\left[ {\begin{array}{*{20}{c}} {{S_{{\rm{31}}}}}&{{S_{{\rm{32}}}}}&{{S_{\rm{2}}}} \\ {{S_{{\rm{39}}}}}&{{S_{{\rm{40}}}}}&{{S_{{\rm{10}}}}} \\ {{S_{\rm{4}}}}&{{S_{\rm{5}}}}&{{S_{{\rm{16}}}}} \end{array}} \right] + {S_{\rm{8}}}\left[ {\begin{array}{*{20}{c}} {{S_{{\rm{25}}}}}&{{S_{{\rm{32}}}}}&{{S_{\rm{2}}}} \\ {{S_{{\rm{33}}}}}&{{S_{{\rm{40}}}}}&{{S_{{\rm{10}}}}} \\ {{S_{{\rm{39}}}}}&{{S_{\rm{5}}}}&{{S_{{\rm{16}}}}} \end{array}} \right] \\ &\quad + {S_{\rm{9}}}\left[ {\begin{array}{*{20}{c}} {{S_{{\rm{25}}}}}&{{S_{{\rm{31}}}}}&{{S_{\rm{2}}}} \\ {{S_{{\rm{33}}}}}&{{S_{{\rm{39}}}}}&{{S_{{\rm{10}}}}} \\ {{S_{{\rm{39}}}}}&{{S_{\rm{4}}}}&{{S_{{\rm{16}}}}} \end{array}} \right] + {S_{{\rm{20}}}}\left[ {\begin{array}{*{20}{c}} {{S_{{\rm{25}}}}}&{{S_{{\rm{31}}}}}&{{S_{{\rm{32}}}}} \\ {{S_{{\rm{33}}}}}&{{S_{{\rm{39}}}}}&{{S_{{\rm{40}}}}} \\ {{S_{{\rm{39}}}}}&{{S_{\rm{4}}}}&{{S_{\rm{5}}}} \end{array}} \right] \\ \end{aligned}$

(66)

对式(66)的第1项中的 ${{{C}}_{{\rm{4011}}}}$ 按第1行展开，则有

$\begin{align}\det ({{{C}}_{{\rm{4011}}}}) =& {S_{{\rm{31}}}}\left[ {\begin{array}{*{20}{c}} {{S_{{\rm{40}}}}}&{{S_{{\rm{10}}}}} \\ {{S_{\rm{5}}}}&{{S_{{\rm{16}}}}} \end{array}} \right] + {S_{{\rm{32}}}}\left[ {\begin{array}{*{20}{c}} {{S_{{\rm{39}}}}}&{{S_{{\rm{10}}}}} \\ {{S_{\rm{4}}}}&{{S_{{\rm{16}}}}} \end{array}} \right] \\ &+ {S_{\rm{2}}}\left[ {\begin{array}{*{20}{c}} {{S_{{\rm{39}}}}}&{{S_{{\rm{40}}}}} \\ {{S_{\rm{4}}}}&{{S_{\rm{5}}}} \end{array}} \right]\end{align}$

(67)

在计算一个2阶行列式的时候，需要进行2次乘法，1次加法。由此，在计算式(67)即3阶行列式的时候，需要进行9次乘法，5次加法；然后，根据式(67)可以得到在计算式(66)即4阶行列式的时候，需要进行40次乘法，23次加法；最后可以得到在计算式(65)即 $\det ({{{C}}_{{\rm{40}}}})$ 时需要的乘法和加法次数分别为：164次和95次。那么以同样的方法求4阶行列式 $\det ({{{C}}_{{\rm{41}}}})$ 时需要的乘法和加法的次数分别为：40次和23次。

在有限域GF(2²⁰)中，利用文献[15]提供的快速求解逆元的方法可知，求一个元素的逆元时，需要的乘法次数为37次。所以在求解未知校验子S₃时，总共需要的乘法次数为：164+40+37+1=242次，加法次数为：95+23=118次。

为了求解错误位置多项式 ${L_{\rm{4}}}(z)$ ，还需先求解未知校验子 ${S_7} = S_3^{16}$ ，计算 ${S_7}$ 的乘法次数为15次。最后计算 ${L_{\rm{4}}}(z)$ 的系数 ${\sigma _{\rm{2}}}$ 时乘法进行了58次，加法进行了6次；计算 ${\sigma _{\rm{3}}}$ 时乘法进行了3次，加法进行了2次；计算 ${\sigma _{\rm{4}}}$ 时乘法进行了43次，加法进行了2次。

综上，该算法求解 ${L_{\rm{4}}}(z)$ 时需要的乘法总次数为：242+15+58+3+43=361次；需要进行的加法总次数为：118+0+6+2+2=128次。

4.2 本文提出算法L₄(z)的计算复杂度

本文提出的快速译码算法直接由已知校验子就可以求出错误位置多项式 ${L_{\rm{4}}}(z)$ 。且在v<4时已经计算出的已知校验子作为已知量，当v=4时，这些已知校验子就不再重复计算。

从式(31)—式(54)可以计算出 ${\sigma _{\rm{4}}}$ 的乘法和加法次数，其中有些变量多次出现，比如 $S_1^2$ 出现了9次， ${a_{211}}{a_{302}}$ 出现了15次， ${a_{202}}{a_{311}}$ 出现了13次，等等。此类变量只需计算一次，在接下来的计算中就当作已知量使用，从而可以减少乘法的运算次数，进而减少译码时间。以上可知只需251次乘法和98次加法就可以计算出 ${\sigma _{\rm{4}}}$ 。由式(57)可知在计算 ${\sigma _{\rm{3}}}$ 时仅需1次乘法。由式(58)可以知道计算 ${\sigma _{\rm{2}}}$ 时有一个逆元的计算，所以需要3+37+1+1=42次乘法和3次加法。

综上，不用计算未知校验子的算法求解 ${L_{\rm{4}}}(z)$ 时需要的乘法总次数为：42+1+251=294次；需要进行的加法总次数为：3+0+98=101次。

4.3 计算L₄(z)的复杂度比较

由上可知，Lin算法和本文提出的算法在计算 ${L_{\rm{4}}}(z)$ 复杂度比较如表1。

表 1 两种译码算法计算L₄(z)复杂度的比较

算法	乘法	加法
Lin算法	361	128
本文算法	294	101
降低百分比(%)	18.56	21.09

下载: 导出CSV

| 显示表格

由表1可知，在求解错误位置多项式 ${L_{\rm{4}}}(z)$ 时，本文提出的算法相对于Lin算法的运算量上，乘法量和加法量分别降低了18.56%和21.09%。

5. 仿真结果

建立仿真的平台为64位的Windows 7操作系统，CPU为英特尔奔腾Pentium(R)Dual-Core，内存为4.00 GB，利用C++语言进行编程实现，采用BPSK调制，对(41, 21, 9)QR码的所有能够求解的错误模式集合进行穷举测试，对比了Lin算法和本文提出的代数译码算法仿真时在不同错误个数时的译码平均时间对比表如表2，所有的错误模式总共有 $\displaystyle\sum\nolimits_{i = 1}^{\rm{4}} \!\! {C_{41}^i = 112791}$ 个。除此之外，令调制后的码字通过加性高斯白噪声(AWGN)信道，求解出(41, 21, 9)QR码的BER (Bit Error Rate)和FER (Frame Error Rate)，再利用MATLAB软件画出了Lin算法和本文提出算法的BER、FER性能曲线图如图1。

表 2 两种译码算法平均译码时间(μs)

错误个数	错误模式总数	Lin算法	本文算法
1	41	24.20	3.94
2	820	142.62	52.79
3	10660	275.60	231.73
4	101270	562.01	477.78

下载: 导出CSV

| 显示表格

图 1 两种译码算法的BER与FER性能曲线图

下载: 全尺寸图片幻灯片

从表2中可以看出当接收码字中出现错误个数v=1的时候，Lin算法平均译码时间需要24.2 μs，而本文提出的算法只需要3.94 μs，本文算法相对于Lin算法，译码时间减少了83.72%；当接收码字中出现错误个数v=2, 3, 4的时候，本文算法相对于Lin算法，译码时间分别减少了62.99%, 15.92%, 14.98%，在v=4时，其时间的降低率与其计算复杂度的降低率相当。并且，从图1中可以看出两种算法的BER和FER的性能曲线完全一致，从而验证了本文提出算法的正确性和可靠性。

6. 结论

本文提出了(41, 21, 9) QR码在判定接收码字中分别出现了2, 3, 4个错的时候，不需要计算未知校验子直接求得对应的错误位置多项式系数的代数译码算法，并简化了文献[12]判定接收码字中发生不同错误时的判断条件，从而降低了译码复杂度。对该码进行穷举仿真，验证了本文提出算法的可行性与正确性及维持原有译码性能不变，降低了译码时间。

图 1 两种译码算法的BER与FER性能曲线图

下载: 全尺寸图片幻灯片

表 1 两种译码算法计算L₄(z)复杂度的比较

算法	乘法	加法
Lin算法	361	128
本文算法	294	101
降低百分比(%)	18.56	21.09

下载: 导出CSV

表 2 两种译码算法平均译码时间(μs)

错误个数	错误模式总数	Lin算法	本文算法
1	41	24.20	3.94
2	820	142.62	52.79
3	10660	275.60	231.73
4	101270	562.01	477.78

下载: 导出CSV

参考文献(15)

PRANGR E. Cyclic error-correcting codes in two symbols, AFCRC-TN-57-103[R]. Cambridge, MA: AirForce Cambridge Research Center, 1957.

LEE Chongdao, CHANG Yaotsu, and CHANG Hohsuan. Unusual general error locator polynomial for the (23, 12, 7) golay code[J]. IEEE Communications Letters, 2010, 14(4): 339–341. DOI: 10.1109/LCOMM.2010.04.091969.

REED I S, TRUONG T K, CHEN Xuemin, et al. The algebraic decoding of the (41, 21, 9) quadratic residue code[J]. IEEE Transactions on Information Theory, 1992, 38(3): 974–986. DOI: 10.1109/18.135639.

CHEN Xuemin, REED I S, HELLESETH T, et al. Use of gröbner bases to decode binary cyclic codes up to the true minimum distance[J]. IEEE Transactions on Communication, 1994, 40(5): 1654–1661. DOI: 10.1109/18.333885.

CHIEN R. Cyclic decoding procedure for Bose-Chaudhuri-Hocquenghem codes[J]. IEEE Transactions on Information Theory, 1964, 10(4): 357–363. DOI: 10.1109/TIT.1964.1053699.

CHEN Yanhaw, HUANG Chingfu, and CHANG J. Decoding of binary quadratic residue codes with hash table[J]. IET Communications, 2016, 10(1): 122–130. DOI: 10.1049/iet-com.2015.0546.

LIN Tsungching, LEE Chongdao, CHEN Yanhaw, et al. Algebraic decoding of cyclic codes without error-locator polynomials[J]. IEEE Transactions on Communications, 2016, 64(7): 2719–2731. DOI: 10.1109/TCOMM.2016.2569078.

ZHANG Pengwei, LI Yong, CHANG Hsinchiu, et al. Fast decoding of the (47, 24, 11) quadratic residue code without determining the unknown syndromes[J]. IEEE Communications Letters, 2015, 19(8): 1279–1282. DOI: 10.1109/LCOMM.2015.2440263.

陈高明, 黎勇, 董灿, 等. 一种(71, 36, 11)QR码的快速代数译码算法[J]. 重庆邮电大学学报(自然科学版), 2015, 27(6): 781–785. DOI: 10.3979 /j.issn.1673-825X.2015.06.013.

CHEN Gaoming, LI Yong, DONG Can, et al. A fast algebraic decoding algorithm of the (71, 36, 11) quadratic residue code[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2015, 27(6): 781–785. DOI: 10.3979/j.issn. 1673-825X. 2015.06.013.

LIN Tsungching, CHANG Hsinchiu, LI Yong, et al. Algebraic decoding of the (71, 36, 11) quadratic residue code[J]. IET Communications, 2016, 10(6): 734–738. DOI: 10.1049/iet-com.2015.0159.

HUANG Chingfu and CHEN Yanhaw. Efficient software method for decoding of the (71, 36, 11) quadratic residue code[C]. Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), Adelaide, Australia, 2015: 45–48.

LIN Tsungching, TRUONG T K, LEE Hungpeng, et al. Algebraic decoding of the (41, 21, 9) quadratic residue code[J]. Information Sciences, 2009, 179(19): 3451–3459. DOI: 10.1016/j.ins.2009.06.002.

FENG G and TZENG K. A new procedure for decoding cyclic and BCH codes up to actual minimum distance[J]. IEEE Transactions on Information Theory, 1994, 40(5): 1364–1374. DOI: 10.1109/18.333854.

MACWILLIMS F J and SLOANE N J A. The Theory of Error Correcting Codes[M]. New York: North Holland, 1977: 244–245.

WANG C C, TRUONG T K, SHAO H M, et al. VLSI architectures for computing multiplications and inverses in GF(2^m)[J]. IEEE Transactions on Computers, 1985, C-34(8):709–717. DOI: 10.1109/TC.1985.1676616.

施引文献

期刊类型引用(1)
1. 罗春兰，林文，祝晓霞. (47, 24, 11)QR码的快速代数译码算法. 三明学院学报. 2022(06): 60-66+78 . 百度学术
其他类型引用(1)

资源附件(0)

访问统计

图(1) / 表(2)

计量

文章访问数: 1670
HTML全文浏览量: 604
PDF下载量: 49
被引次数: 2

1. 引言
2. (41, 21, 9)QR码
3. (41, 21, 9)QR码的代数译码算法
3.1 新的错误位置多项式的推导
3.2 简化v=1, 2, 3时的判断条件进一步优化前述的快速代数译码算法
4. 计算复杂度分析
4.1 Lin算法 ${{L}_{{4}}}$ ( ${z}$ )的计算复杂度
4.2 本文提出算法L4(z)的计算复杂度
4.3 计算L4(z)的复杂度比较
5. 仿真结果
6. 结论

1. 引言
2. (41, 21, 9)QR码
3. (41, 21, 9)QR码的代数译码算法
3.1 新的错误位置多项式的推导
3.2 简化v=1, 2, 3时的判断条件进一步优化前述的快速代数译码算法
4. 计算复杂度分析
4.1 Lin算法 ${{L}_{{4}}}$ ( ${z}$ )的计算复杂度
4.2 本文提出算法L₄(z)的计算复杂度
4.3 计算L₄(z)的复杂度比较
5. 仿真结果
6. 结论

参考文献(15)

施引文献

资源附件(0)

访问统计

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

一种(41, 21, 9)平方剩余码的快速代数译码算法

doi: 10.11999/JEIT170983

通讯作者:
吴怡　 wuyi@fjnu.edu.cn

计量

A Fast Algebraic Decoding of the (41, 21, 9) Quadratic Residue Code

1. 引言

2. (41, 21, 9)QR码

3. (41, 21, 9)QR码的代数译码算法

3.1 新的错误位置多项式的推导

3.2 简化v=1, 2, 3时的判断条件进一步优化前述的快速代数译码算法

4. 计算复杂度分析

4.1 Lin算法 ${{L}_{{4}}}$ ( ${z}$ )的计算复杂度

4.2 本文提出算法L₄(z)的计算复杂度

4.3 计算L₄(z)的复杂度比较

5. 仿真结果

6. 结论

期刊类型引用(1)

其他类型引用(1)

计量

目录

1. 引言

2. (41, 21, 9)QR码

3. (41, 21, 9)QR码的代数译码算法

3.1 新的错误位置多项式的推导

3.2 简化v=1, 2, 3时的判断条件进一步优化前述的快速代数译码算法

4. 计算复杂度分析

4.1 Lin算法 ${{L}_{{4}}}$ ( ${z}$ )的计算复杂度

4.2 本文提出算法L₄(z)的计算复杂度

4.3 计算L₄(z)的复杂度比较

5. 仿真结果

6. 结论

留言板

一种(41, 21, 9)平方剩余码的快速代数译码算法

doi: 10.11999/JEIT170983

通讯作者: 吴怡 wuyi@fjnu.edu.cn

计量

出版历程

A Fast Algebraic Decoding of the (41, 21, 9) Quadratic Residue Code

1. 引言

2. (41, 21, 9)QR码

3. (41, 21, 9)QR码的代数译码算法

3.1 新的错误位置多项式的推导

3.2 简化v=1, 2, 3时的判断条件进一步优化前述的快速代数译码算法

4. 计算复杂度分析

4.1 Lin算法 L4{{L}_{{4}}} ( z{z} )的计算复杂度

4.2 本文提出算法L4(z)的计算复杂度

4.3 计算L4(z)的复杂度比较

5. 仿真结果

6. 结论

期刊类型引用(1)

其他类型引用(1)

计量

出版历程

目录

1. 引言

2. (41, 21, 9)QR码

3. (41, 21, 9)QR码的代数译码算法

3.1 新的错误位置多项式的推导

3.2 简化v=1, 2, 3时的判断条件进一步优化前述的快速代数译码算法

4. 计算复杂度分析

4.1 Lin算法 L4{{L}_{{4}}} ( z{z} )的计算复杂度

4.2 本文提出算法L4(z)的计算复杂度

4.3 计算L4(z)的复杂度比较

5. 仿真结果

6. 结论

通讯作者:
吴怡　 wuyi@fjnu.edu.cn

4.1 Lin算法 ${{L}_{{4}}}$ ( ${z}$ )的计算复杂度

4.2 本文提出算法L₄(z)的计算复杂度

4.3 计算L₄(z)的复杂度比较

4.1 Lin算法 ${{L}_{{4}}}$ ( ${z}$ )的计算复杂度

4.2 本文提出算法L₄(z)的计算复杂度

4.3 计算L₄(z)的复杂度比较