ISSN 
-
QR码是一类循环码。著名的(23,12,7)Golay码就是一个QR码，它的扩展码是(24,12,8)扩展Golay码，二十世纪80年代在NASA的Voyager spacecraft program中被用于传输木星(Jupiter)和土星(Saturn)的彩色照片。在美国政府的两个标准中也指定使用(24,12,8)扩展Golay码[1-2]。
QR码是在1958年被提出的[3]。从那时起，人们对QR码的研究就一直没有停止过[4-8]。
QR码是一类译码比较困难的“好”码[9]；而对于Q译R码的码，文献[10]认为QR码类的译码算法通常不具有规范的结构，针对不同的QR码，采用不同的译码算法[10]。因此对QR码的译码算法研究具有一定的理论意义和实际意义。
本文针对所有二进制QR码给出一个通用的简化查表译码算法。目前已有的二进制QR码的查表译码算法一般都是针对特定的QR码，本文给出的算法不仅具有适用性广的特点，而且译码表的行数也是最小的。
HTML
-
本文采用文献[11]中的术语和符号。域$F$上的一个$(n,k)$线性码$C$是$F$上的长为$n$的向量作成的一个$k$维向量空间。$C$中的向量称为码字。设$\mathbf{c}\in C$，c的非零分量的个数称为c的(Hamming)重量，记为w(c)。$C$中两个码字差的重量称为这两个码字的(Hamming)距离。$C$中任意两个码字的距离构成的集合中的最小值称为$C$的最小距离，用d表示。此时称$C$是一个$(n,k,d)$码。$C$的纠错能力$t=\left\lfloor (d-1)/2 \right\rfloor $。以C中k个线性无关的码字作成的$k\times n$矩阵称为C的一个生成矩阵。C的对偶码${{C}^{\bot }}$的生成矩阵称为C的一致校验矩阵。设H是C的一个一致校验矩阵，r是一n维向量，rHT称为r的伴随式。r是码字当且仅当rHT=0。
设p是一个奇素数，GF(q)是一个有限域，其中q是另一素数，且是modp的二次剩余。令：
Qp={所有modp的二次剩余},Np={所有modp的二次非剩余}。
设a是包含GF(q)的某个域中的一个p次本原单位根，则多项式：
都属于$GF(q)[x]$[12]。分别以多项式$q(x)$，$(x-1)q(x)$，$n(x)$和$(x-1)n(x)$作为生成多项式的循环码称为二次剩余码(quadratic residue codes，QR码)。设C是一个二进制$(n,k)$线性码。下面的集合作成一个二进制$(n+1,k)$码：
称为C的扩展码。
QR码的译码分为两类：代数译码[13-14]和查表译码。查表译码的大致过程如下：
事先构造一个译码表，该表中一个错误模式与一个伴随式对应。对接收到的向量r，按下面的步骤进行译码：
1) 计算r的伴随式s=rHT；
2) 通过译码表找到s对应的错误模式；
3) 通过错误模式进行纠错，然后将纠错后的向量输出。
查表译码最直接的做法是在译码表中将纠错能力范围内的所有错误模式和其对应的伴随式一一全部列出，这时译码表的行数为$\sum\limits_{i=1}^{t}{\left( \begin{matrix} n \\ i \\ \end{matrix} \right)}$。由于译码表的大小直接影响查表译码算法的效率和实用性，所以长期以来有很多学者都致力于减少译码表的行数的研究。
文献[15]利用循环码的循环特性，将译码表的行数减少为${\sum\limits_{i=1}^{t}{\left( \begin{matrix} n \\ i \\ \end{matrix} \right)}}/{n}\;$。由二项式系数的单峰性可知，当t<n/2时，$\left( \begin{matrix} n \\ 1 \\ \end{matrix} \right)＜\left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)＜\cdots ＜\left( \begin{matrix} n \\ t \\ \end{matrix} \right)$。因此减少$\sum\limits_{i=1}^{t}{\left( \begin{matrix} n \\ i \\ \end{matrix} \right)}$中求和的项数t，对和的减小影响是非常大的。正因为如此，文献[16]为了将$(47,24,11)$QR码的译码表的行数从$\sum\limits_{i=1}^{5}{\left( \begin{matrix} 47 \\ i \\ \end{matrix} \right)}$减少为$\sum\limits_{i=1}^{4}{\left( \begin{matrix} 47 \\ i \\ \end{matrix} \right)}$，不得不单独处理错误个数为5的情形：逐个反转接收码字r的每个分量，然后计算其伴随式，该伴随式与译码表中的伴随式相比。如果与译码表中的某个伴随式相同，那将该伴随式对应的错误模式在反转位置的比特反转后得到的向量就是错误向量。即从47个位置中逐个去搜索。这种搜索最多有可能要进行43次才能找到一个错误位置。文献[17]也采取了同样的方法来减少(41,21,9)QR码的译码表的行数。文献[18]给出了(41,21,11)QR码的一个查表译码算法，译码表的行数从文献[16]的$\sum\limits_{i=1}^{t-1}{\left( \begin{align} & n \\ & k \\ \end{align} \right)}$减少为${}^{\sum\limits_{i=1}^{t-1}{\left( \begin{align} & n \\ & k \\ \end{align} \right)}}\!\!\diagup\!\!{}_{n}\;$。文献[19]给出了(23,12,7)Golay码的一个查表译码算法，其译码表的简化是通过将和中项$\left( \begin{matrix} n \\ i \\ \end{matrix} \right)$的n换成k：在译码表中只列出错误个数不超过t=3，且错误只出现在信息部分的错误模式及其对应的伴随式。因此译码表的行数为$\sum\limits_{i=1}^{t}{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}=298$，错误只出现在校验部分时的情况单独处理。沿用此思路，文献[4]给出了(73,37,13)QR码的一个查表译码算法，在译码表中只列出信息部分出现1～3个错误的错误模式及其对应的伴随式。其译码表的行数为$\sum\limits_{i=1}^{\left\lceil t/2 \right\rceil }{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}=$=8473。当接收向量r的伴随式在表中查不到时，表明r信息部分的错误超过3。当信息部分出现至少4个错误时，校验部分就最多出现2个错误，故循环移位36位后，信息部分最多只有3个错误。继续文献[4]的这种思路，文献[5]给出了(41,21,9)QR码的一个查表译码算法，译码表的行数为$\sum\limits_{i=1}^{\left\lceil t/2 \right\rceil }{\left( \begin{align} & k \\ & i \\ \end{align} \right)}=231$；而文献[6]则给出了(47,24,11)QR码的一个查表译码算法，其译码表的行数为$\sum\limits_{i=1}^{\left\lceil t/2 \right\rceil }{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}=2\text{ }324$。文献[7]给出了(23,12,7)Golay码的一个查表译码方法，将求和的项数从$\left\lceil t/2 \right\rceil $减少为$\left\lfloor t/2 \right\rfloor $，故其译码表的行数为$\sum\limits_{i=1}^{\left\lfloor t/2 \right\rfloor }{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}=12$。
以上这些算法大多数都是针对单个具体的QR码来给出的，且译码表的行数都大于$\sum\limits_{i=1}^{\left\lfloor t/2 \right\rfloor }{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}$。
通过研究，本文发现了QR码的一些性质，利用这些性质，给出一个针对所有二进制$(n,k,d)$QR码的通用的查表译码算法，译码表的行数都为${{N}_{h}}=\sum\limits_{i=1}^{\left\lfloor t/2 \right\rfloor }{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}$。该算法不仅能纠正小于或等于t个的错误，而且还可以检测出部分多于t个的错误。
-
设C是一个(n,k)循环码。多项式：
称为码字$\mathbf{c}=[{{c}_{0}},{{c}_{1}},\cdots ,{{c}_{n-1}}]\in C$的多项式。C中非零码字的多项式中次数最小的首一多项式称为C的生成多项式。设C的生成多项式为：
则矩阵：
是C的一个生成矩阵。对G1进行行初等变换，可以得到C的生成矩阵：
式中，Ik是k阶单位阵；Ak×(n-k)是一个k×(n-k)矩阵。由G可得C的一个一致校验矩阵：
分别简记为G=[I,A]和H=[AT,I]。
容易看出，信息向量$\mathbf{m}=[{{m}_{1}},{{m}_{2}},\cdots ,{{m}_{k}}]$经过G编码得到码字c，其前k个分量恰为m：
具有这种结构的码称为系统码。在系统码的情况下，将一个二进制n维向量的前k个分量称为信息部分，后n-k个分量称为校验部分。
-
假设C是二进制$(n,k,d)$循环码，H=[AT,I]是C的一个一致校验矩阵。
设$\mathbf{e}=\left[ {{\mathbf{e}}_{M}},{{\mathbf{e}}_{P}} \right]$，其中${{\mathbf{e}}_{M}}=[{{e}_{1}},\cdots ,{{e}_{k}}]$是信息部分，${{\mathbf{e}}_{P}}=[{{e}_{k+1}},\cdots ,{{e}_{n}}]$是校验部分，$\mathbf{s}=\mathbf{e}{{\mathbf{H}}^{\text{T}}}$。
为了得到一个适用于所有QR码的通用算法，本文对QR进行研究，发现QR码都具有一些性质，利用这些性质可以得到一个通用的简化查表译码算法。将结果用6个定理的形式给出。
定理1 若$\mathbf{e}=\left[ {{\mathbf{e}}_{M}},{{\mathbf{e}}_{P}} \right],w({{\mathbf{e}}_{M}})\ge 1$，则$w(\mathbf{e}{{\mathbf{H}}^{\text{T}}})\ge d-w(\mathbf{e})$。
证明：因为码字的重量至少是d，而${{\mathbf{e}}_{M}}\left[ \mathbf{I},\mathbf{A} \right]=\left[ {{\mathbf{e}}_{M}},{{\mathbf{e}}_{M}}\mathbf{A} \right]$是非零码字，所以$w({{\mathbf{e}}_{M}})+w({{\mathbf{e}}_{M}}\mathbf{A})\ge d$。由于$\mathbf{e}{{\mathbf{H}}^{\text{T}}}={{\mathbf{e}}_{M}}\mathbf{A}+{{\mathbf{e}}_{P}}$，而$w(\mathbf{e}{{\mathbf{H}}^{\text{T}}})\text{=}w({{\mathbf{e}}_{M}}\mathbf{A}+{{\mathbf{e}}_{P}})\ge w({{\mathbf{e}}_{M}}\mathbf{A})-w({{\mathbf{e}}_{P}})$，故$w(\mathbf{e}{{\mathbf{H}}^{\text{T}}})\ge d-w({{\mathbf{e}}_{M}})-w({{\mathbf{e}}_{P}})=d-w(\mathbf{e})$。
因为$d\ge 2t+1$，所以由定理1可得：
定理 2 若$\mathbf{e}=\left[ {{\mathbf{e}}_{M}},{{\mathbf{e}}_{P}} \right]$，其中$w({{\mathbf{e}}_{M}})\ge 1,w(\mathbf{e})\le t$，则$w(\mathbf{e}{{\mathbf{H}}^{\text{T}}})\ge t+1$。
由H=[AT,I]的结构及矩阵的乘法容易看出：
定理 3 若$\mathbf{e}=\left[ {{\mathbf{0}}_{1\times k}},{{\mathbf{e}}_{P}} \right]$，则$\mathbf{e}{{\mathbf{H}}^{\text{T}}}={{\mathbf{e}}_{P}}$。
由定理2和定理3可得：
定理 4 若$w(\mathbf{e})\le t$，则$w(\mathbf{e}{{\mathbf{H}}^{\text{T}}})\le t$当且仅当$\mathbf{e}=\left[ {{\mathbf{0}}_{1\times k}},\mathbf{e}{{\mathbf{H}}^{\text{T}}} \right]$。
定理4给出了一个如何判别错误只出现在校验部分的方法及如何确定错误模式的方法。因此当错误只出现在校验部分时就可统一处理，而不必将每个错误模式和其对应的伴随式一一列出。下面只须考虑信息部分一定有错误出现的情形。
当$\mathbf{e}=\left[ {{\mathbf{e}}_{M}},{{\mathbf{e}}_{P}} \right]$时，定理5给出了${{\mathbf{e}}_{P}}$与e的伴随式和$[{{\mathbf{e}}_{M}},{{\mathbf{0}}_{1\times (n-k)}}]$的伴随式之间的关系。
定理 5 设$\mathbf{e}=\left[ {{\mathbf{e}}_{M}},{{\mathbf{e}}_{P}} \right]$。若$[{{\mathbf{e}}_{M}},{{\mathbf{0}}_{1\times (n-k)}}]{{\mathbf{H}}^{\text{T}}}={{\mathbf{s}}_{M}}$，则${{\mathbf{e}}_{P}}=\mathbf{e}{{\mathbf{H}}^{\text{T}}}-{{\mathbf{s}}_{M}}$。
证明：${{\mathbf{e}}_{P}}=(\mathbf{e}-[{{\mathbf{e}}_{M}},{{\mathbf{0}}_{1\times (n-k)}}]){{\mathbf{H}}^{\text{T}}}=\mathbf{e}{{\mathbf{H}}^{\text{T}}}-{{\mathbf{s}}_{M}}$。
由定理5可知，在错误向量的伴随式及其信息部分对应的伴随式已知的情况下可以得到错误向量的校验部分。
当错误仅出现在信息部分，且错误个数不超过t时，错误向量的总数为${{N}_{f}}=\sum\limits_{i=1}^{t}{\left( \begin{align} & k \\ & i \\ \end{align} \right)}$。设${{N}_{f}}$个信息部分出错的错误向量为：
其对应的伴随式分别为：
表 1将向量${{\mathbf{s}}_{\mathbf{i}}}$及$\mathbf{e}_{M}^{i}$并置在一行，得到一个${{N}_{f}}$行、n列的表，这个表称为信息部分伴随式与错误模式的对应表MPSET(message part syndrome error table)：
伴随式 错误模式 ${{\mathbf{s}}_{1}}$ $\mathbf{e}_{M}^{1}$ ${{\mathbf{s}}_{2}}$ $\mathbf{e}_{M}^{2}$ $\vdots $ $\vdots $ ${{\mathbf{s}}_{{{N}_{f}}}}$ $\mathbf{e}_{M}^{{{N}_{f}}}$ 在实际译码时并不知道错误向量的信息部分，所以定理5的结果不具可操作性。定理6则从理论上保证由错误向量的伴随式和表MPSET，通过比较向量的汉明重量就可确定错误向量。因为错误向量的伴随式可通过接收到的向量得到，而表MPSET可事先做好，所以定理6的结果可实际操作。
定理 6 设$\mathbf{e}=\left[ {{\mathbf{e}}_{M}},{{\mathbf{e}}_{P}} \right],w(\mathbf{e})\le t$。若$w({{\mathbf{e}}_{M}})\ge 1$，$\mathbf{s}=\mathbf{e}{{\mathbf{H}}^{\text{T}}}$，则存在唯一一个$i\text{ (}1\le i\le {{N}_{f}})$，使得$w([\mathbf{s}-{{\mathbf{s}}_{i}},\mathbf{e}_{M}^{i}])\le t$ 。此时一定有$\mathbf{e}=[\mathbf{e}_{M}^{i},\mathbf{s}-{{\mathbf{s}}_{i}}]$。
证明：由MPSET的构造可知，存在$1\le i\le {{N}_{f}}$使得${{\mathbf{e}}_{M}}=\mathbf{e}_{M}^{i}$。再由定理5知$\mathbf{e}=[\mathbf{e}_{M}^{i},\mathbf{s}-{{\mathbf{s}}_{i}}]$，故$w([\mathbf{s}-{{\mathbf{s}}_{i}},\mathbf{e}_{M}^{i}])=w(\mathbf{e})$。
下面只需证当$j\ne i$时必有：
实际上由定理1可得：
-
保留MPSET中重量$\le \left\lfloor t/2 \right\rfloor $的错误模式和其对应的伴随式，得到的表记作SMPSET(simplified MPSET)，其行数为${{N}_{h}}=\sum\limits_{i=1}^{\left\lfloor t/2 \right\rfloor }{\left( \begin{align} & k \\ & i \\ \end{align} \right)}$。
译码时，当用r的伴随式在SMPSET中找不到错误向量时，则r信息部分的错误个数$\ge \left\lfloor t/2 \right\rfloor +1$，因此校验部分的错误个数$\le \left\lfloor t/2 \right\rfloor $。将r右循环移位$n-k$位，得到${{\mathbf{r}}^{{{R}^{(n-k)}}}}$，再用${{\mathbf{r}}^{{{R}^{(n-k)}}}}$的伴随式在SMPSET中查找错误向量。若用${{\mathbf{r}}^{{{R}^{(n-k)}}}}$的伴随式在SMPSET中仍找不到错误向量时，则r的第一个比特是错的。将其反转，然后再用得到的向量的伴随式查找错误向量。
设C是纠错能力为t的$(n,k)$QR码，$g(x)=\sum\limits_{i=0}^{n-k}{{{g}_{i}}{{x}^{i}}}$是它的一个生成多项式。由定理4和定理6，本文给出一个C的查表译码方法。
预处理：由$g(x)$导出C的一个生成矩阵和一个一致校验矩阵：
然后计算SMPSET。
对于接收到的向量r，本文的译码算法如下：
Algorithm：SimplifiedTLD
{
$\text{input SMPSET, }\mathbf{H},\mathbf{r},t$;
${{N}_{h}}\leftarrow \text{number of rows in SMPSET}$;
$n\leftarrow \text{number of columns in }\mathbf{H}$;
$k\leftarrow n-\text{number of rows in }\mathbf{H}$;
$\text{testVec}\leftarrow \left[ \begin{matrix} \mathbf{r}=[{{r}_{1}},{{r}_{2}},\cdots ,{{r}_{n}}] \\ (\mathbf{r}＜＜k)\vee (\mathbf{r}>>n-k) \\ [({{r}_{1}}+1)\bmod 2,{{r}_{2}},\cdots ,{{r}_{n}}] \\ \end{matrix} \right]$;
$\text{testedNo}\leftarrow 1$;
$\mathbf{e}\leftarrow \overbrace{[1,1,\cdots ,1]}^{n}$;
while ($w(\mathbf{e})>t$ and $\text{testedNo}\le 3$){
$\mathbf{s}\leftarrow \text{testVec}(\text{testedNo}){{\mathbf{H}}^{\text{T}}}$；
if ($w(\mathbf{s})\le t$)
$\mathbf{e}\leftarrow [{{\mathbf{0}}_{1\times k}},\mathbf{s}]$;
else {
$i\leftarrow 1$;
while ($w(\mathbf{e})>t$ and $i\le {{N}_{h}}$){
$\mathbf{e}\leftarrow [\text{SMPSET}(i,2),\mathbf{s}-\text{SMPSET}(i,1)]$;
$i\leftarrow i+1$;
}
}
if testedNo = 2
$\mathbf{e}\leftarrow (\mathbf{e}＜＜n-k)\vee (\mathbf{e}>>k)$;
if testedNo = 3
$\mathbf{e}\leftarrow [({{e}_{1}}+1)\bmod 2,{{e}_{2}},\cdots ,{{e}_{n}}]$;
$\text{testedNo}\leftarrow \text{testedNo}+1$;
}
if $w(\mathbf{e})>t$
output (“failure”);
else
output$(\mathbf{r}+\mathbf{e})\bmod 2$;
}
当算法输出“failure”时，表明在SMPSET中没有找到对应的错误模式，即错误个数超出了纠错能力，因此算法此时实际上相当于检测到纠错能力范围之外的一个错误模式。
利用SimplifiedTLD，可以得到QR码$C$的扩展码${{C}^{*}}$的一个译码算法如下：
设$\mathbf{r}*=[{{r}_{1}},\cdots ,{{r}_{n}},{{r}_{n+1}}]$是接收到的向量。
1) 用算法SimplifiedTLD对$\mathbf{r}=[{{r}_{1}},{{r}_{2}},\cdots ,{{r}_{n}}]$进行译码，设其输出为$\mathbf{y}=[{{y}_{1}},{{y}_{2}},\cdots ,{{y}_{n}}]$。
2) 计算校验和${{y}_{n+1}}=\sum\limits_{i=1}^{n}{{{y}_{i}}\bmod 2}$，然后输出$\mathbf{y}*=[{{y}_{1}},{{y}_{2}},\cdots ,{{y}_{n+1}}]$。
按照这个算法译码，不仅可以纠正码${{C}^{*}}$纠错能力范围内(即错误个数$\le t$)的所有错误模式，而且还能纠正最后一位出错、错误个数为$t+1$的错误模式。
-
本文利用QR码的特点及伴随式的重量，给出了QR码的一个简化译码算法。该译码算法简单明了，容易理解和实现。其译码表的行数为$\sum\limits_{i=1}^{\left\lfloor t/2 \right\rfloor }{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}$，是目前QR码的查表译码算法中最少的。
从本文的讨论可以看出，这个数目还可进一步减少。在SMPSET中，错误模式经过循环移位可以得到的所有错误模式中只需保留一个，其他的均可删去。比如对(23,12,8)Golay码，SMPSET的12行可以只保留第一行${{\mathbf{s}}_{1}},\mathbf{e}_{M}^{1}$，这个行数是最小的。
DownLoad: