基于改进的GS算法的矩阵式二维码RS译码纠错方法

摘要

本发明提供了一种基于改进的GS算法的矩阵式二维码RS译码纠错方法，改进的GS算法可以降低插值的复杂度，因此可以提高算法的效率，同时译码纠错方法对RS码的两种编码方式及其转化关系进行了研究，因此可以利用两种编码方式的转化过程对RS码进行纠正，使二维码在出现脱落、污点、穿孔以及局部破损等情况时，也能正确地还原原始信息。

主权项

一种基于改进的GS算法的矩阵式二维码RS译码纠错方法，其中改进的GS算法包括改进的Kotter插值算法和Roth‑Ruckenstein因式分解算法，其特征在于：所述纠错方法包括以下步骤：S1.对二维码图像进行去掩膜处理，获得去掩膜后的RS(n,k)码，在RS(n,k)码的末位填充(255‑n)个零，构造RS(255,255+k‑n)码；S2.通过码字RS(255,255+k‑n)结合有限域GF(q^m)中非零元素(x₀,x₁,...,x_{255+k‑n‑1})构成255+k‑n个插值点(x₀,r₀),(x₁,r₁),...,(x_{255+k‑n‑1},r_{255+k‑n‑1})，再基于(1,k‑1)‑加权字典反序表通过在每个插值点至少插值m次来构建一个二元多项式，其中m为内插重度；S3.利用改进的Kotter插值算法求取最小多项式，具体过程如下：S31.首先通过公式初始化一组二元多项式，其中为初始化的第j条二元多项式，l_m为该组二元多项式的数目，为初始化后的二元多项式组成的集合，i_k为迭代次数，此时i_k＝0；S32.通过公式消去集合内首阶大于C的二元多项式，其中$C=n\left(\begin{array}{c}m+1\\ 2\end{array}\right);$S33.通过公式对中的各个二元多项式的Hasse混合偏导数进行计算，然后判断集合中所有二元多项式的Hasse混合偏导数是否都等于0，若都等于0，则进行步骤S36，若不全等于0，进行步骤S34；S34.求取该组二元多项式中的最小多项式，如下式所示：$f=\underset{j\in J_{i_k}}{\min }{g}_{i_k,j}$$j^{*}=\arg \underset{j\in J_{i_k}}{\min }{g}_{i_k,j}$其中f为该组二元多项式中的最小多项式，j^*为最小多项式对应的序号；S35.对该组二元多项式中的最小多项式进行变换修改，公式如下：$g_{i_k+1,j^{*}}={[\mathrm{xf},f]}_{D_{i_k}}={\Delta }_{j^{*}}(x-x_i)\mathrm{fj}=j^{*},$其余的二元多项式也进行变换修改，公式如下：$g_{i_k+1,j}={[g_{i_k,j},f]}_{D_{i_k}}={\Delta }_{j^{*}}{g}_{i_k,j}-{\Delta }_j\mathrm{fj}\ne j^{*};$S36.选取另一组二元多项式重复步骤S31～S35的过程进行该组最小多项式的求取，并令i_k＝i_k+1；S37.若i_k＝C则停止迭代，此时各组二元多项式的最小多项式g_C,j组成集合G_C，通过公式Q(x,y)＝min{g_C,j|g_C,j∈G_C}对C组二元多项式中的最小多项式Q(x,y)进行求解；S4.在求得Q(x,y)之后，利用Roth‑Ruckenstein因式分解算法对Q(x,y)进行分解获得RS码频域编码对应的信息多项式m'(x)；S5.对信息多项式m'(x)采用频域编码方式进行n位编码，获得编码码字之后取编码码字第n‑k+1到n位码字生成时域编码对应的信息多项式m(x)，对m(x)采用时域编码方式进行编码，即可获得纠正的RS(n,k)码。