错误检测解码模组及错误检测更正装置

摘要

本发明是有关于一种错误检测解码模组，用于接收一经由一杂信通道传递的接收信号向量，且该接收信号向量中包含一能够以一误差位置多项式表示的误差向量信号，其包含：一已知征状值计算单元，根据该接收信号向量以得到一具有多数个已知征状值的目标信号向量，并根据所述已知征状值以计算出一差错位置多项式，根据该差错位置多项式及所述已知征状值以计算出多数个未知征状值的未知征状值计算单元，及一根据一由所述已知征状值与所述未知征状值形成的征状值集合以输出一检测结果信号的判断单元。

说明书

技术领域

本发明涉及一种错误检测更正装置，特别是涉及一种应用循环码 (cyclic code)的错误检测解码模组及错误检测更正装置。

背景技术

雷德-所罗门码(Reed-Solomon code，RS code)目前已被广泛应用于 如通讯系统、光碟读取系统、高解度电视系统等应用上，使得当一传送单 元传送一编码后的雷德-所罗门码至一接收单元时，若传送过程中发生码错 误或是因为杂信干扰所导致的误差错误时，该接收单元得以修正该码错误 或是误差错误，以得到该传送单元所传送的原始资料。

然而，该接收单元要修正该码错误或是误差错误时，必须先对所接收 的雷德-所罗门码进行解码，而现今已有相当多解雷德-所罗门码的演算法 被提出，如：A.Shiozaki于1988年在IEEE Trans.on Inf.Theory所提 出的「Decoding of redundant residue polynomial codes using Euclid′s algorithm」文献，其利用中国剩余定理(Chinese reminder theorem)与 欧几里得演算法(Euclidean algorithm)发展出一解雷德-所罗门码的演 算法，然而这种演算法的复杂程度非常高，严重导致降低解码速度。

此外，S.V.Fedorenko于2005年在IEEE Trans.on Inf.Theory所 提出的「A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlemamp algorithm」文献借由卫尔须-伯乐肯 演算法(Welch-Berlekamp algorithm)与欧几里得演算法推导出一高尔演 算法(Gao’s algorithm)，也能够用以解雷德-所罗门码，然而，T.C.Lin 等人于2009年在IEEE Trans.on Commun.发表的「Simplified procedure for decoding nonsystematic Reed-Solomon codes over GF(2^m)using Euclid’s algorithm and the fast Fourier transform」文献显示该高 尔演算法适用误差位置多项式(Erasure-locator polynomial)与差错内 插多项式(Errata interpolating polynomial)取代欧几里得演算法的初 始条件以解出码错误或误差错误，所以相似于A.Shiozaki所提出的演算 法，利用大量的内插法会导致演算法的复杂度大幅增加，进而使得解码速 度严重降低。

由此可见，上述现有的快速解出雷德-所罗门码的演算法在方法与使用 上，显然仍存在有不便与缺陷，而亟待加以进一步改进。为了解决上述存 在的问题，相关厂商莫不费尽心思来谋求解决之道，但长久以来一直未见 适用的设计被发展完成，而一般产品及方法又没有适切的结构及方法能够 解决上述问题，此显然是相关业者急要解决的问题。因此如何能创设一种 使用时可具有全方位调整功能的新的错误检测解码模组及错误检测更正装 置，实属当前重要研发课题之一，亦成为当前业界极需改进的目标。

发明内容

本发明的目的在于提供一种错误检测解码模组，使其便于快速解码。

本发明的另一目的在于提供一种错误检测更正装置，使其便于解码速 度快且能够更正错误。

本发明的目的及解决其技术问题是采用以下技术方案来实现的。依据 本发明提出的一种错误检测解码模组，用于接收一个经由一个杂信通道传 递的接收信号向量，且该接收信号向量中包含一个以一个误差位置多项式 表示的误差向量信号，其中错误检测解码模组包含一个已知征状值计算单 元、一个未知征状值计算单元，及一个判断单元，该已知征状值计算单元包 括一个转换器，及一个差错位置多项式计算器，该转换器是用以接收该接收 信号向量并转换得到一个目标信号向量，而该目标信号向量具有多数个已 知征状值，该差错位置多项式计算器是用以接收所述已知征状值，并根据 该误差位置多项式与所述已知征状值以计算出一个差错位置多项式，该未 知征状值计算单元是根据该差错位置多项式及所述已知征状值，以计算出 多数个未知征状值，该判断单元是根据一个由所述已知征状值与所述未知 征状值形成的征状值集合，以输出一个检测结果信号。

本发明的目的及解决其技术问题还可采用以下技术措施进一步实现。

前述的错误检测解码模组，其中所述的转换器根据以下方程式将该接 收信号向量转换出该目标信号向量：

$a_i=\underset{j=0}{\overset{n-1}{\Sigma }}{r}_j·a^{i·j}=\underset{j=0}{\overset{n-1}{\Sigma }}(c_j+{\tilde{\mu }}_j)·a^{i·j}$

其中，0≤i≤n-1。

前述的错误检测解码模组，其中所述的未知征状值计算单元根据以下 方程式以计算出所述未知征状值：

S_i＝τ₁S_i-1+τ₂S_i-2+…+τ_v+sS_i-(v+s)

其中，d≤i≤n的征状值为所述未知征状值，且1≤i≤d-1的征状值就是 所述已知征状值。

本发明的目的及解决其技术问题还采用以下技术方案来实现。依据本 发明提出的一种错误检测更正装置，用于接收一个经由一个杂信通道传递 的接收信号向量，且该接收信号向量中包含一个以一个误差位置多项式表 示的误差向量信号，其中错误检测更正装置包含一个错误检测解码模组，及 一个判断单元，该错误检测解码模组包括一个已知征状值计算单元、一个 未知征状值计算单元，及一个判断单元，该已知征状值计算单元具有一个 转换器，及一个差错位置多项式计算器，该转换器是用以接收该接收信号 向量并转换得到一个目标信号向量，该目标信号向量具有多数个已知征状 值，该差错位置多项式计算器是用以接收该目标信号向量，并根据该误差 位置多项式与该目标信号向量中的所述已知征状值，以计算出一个差错位 置多项式，该未知征状值计算单元是根据该差错位置多项式及所述已知征 状值以计算出多数个未知征状值，该判断单元是根据一个由所述已知征状 值与所述未知征状值形成的征状值集合，以输出一个检测结果信号，该错误 更正模组是接收该检测结果信号、该征状值集合及该目标信号向量，并据 此计算出更正后的该接收信号向量。

本发明的目的及解决其技术问题还可采用以下技术措施进一步实现。

前述的错误检测更正装置，其中所述的转换器根据以下方程式将该接 收信号向量转换出该目标信号向量：

$a_i=\underset{j=0}{\overset{n-1}{\Sigma }}{r}_j·a^{i·j}=\underset{j=0}{\overset{n-1}{\Sigma }}(c_j+{\tilde{\mu }}_j)·a^{i·j}$

其中，0≤i≤n-1。

前述的错误检测更正装置其中所述的未知征状值计算单元根据以下方 程式以计算出所述未知征状值：

S_i＝τ₁S_i-1+τ₂S_i-2+…+τ_v+sS_i-(v+s)

其中，d≤i≤n的征状值为所述未知征状值，且1≤i≤d-1的征状值就是 所述已知征状值。

前述的错误检测更正装置，其中所述的未知征状值计算单元根据以下 方程式以计算出所述未知征状值：

S_i＝τ₁S_i-1+τ₂S_i-2+…+τ_v+sS_i-(v+s)

其中，d≤i≤n的征状值为所述未知征状值，且1≤i≤d-1的征状值就是 所述已知征状值。

前述的错误检测更正装置，其中所述的错误更正模组根据以下方程式 以计算出更正后的该接收信号向量：

m_i＝a_i-S_i

其中，0≤i≤n-1，a_i为该目标信号向量中第i个目标信号，S_i为该征状 值集合中第i个征状值。

本发明与现有技术相比具有明显的优点和有益效果。借由上述技术方 案，本发明提出的错误检测解码模组用于接收一个经由一个杂信通道传递 的接收信号向量，且该接收信号向量中包含一个以一个误差位置多项式表示 的误差向量信号，该错误检测解码模组包含：一个已知征状值计算单元、一 个未知征状值计算单元，及一个判断单元。

该已知征状值计算单元包括一个转换器，及一个差错位置多项式计算 器。该转换器是用以接收该接收信号向量并转换得到一个目标信号向量，其 中，该目标信号向量具有多数个已知征状值。该差错位置多项式计算器是 用以接收所述已知征状值，并根据该误差位置多项式与所述已知征状值以 计算出一个差错位置多项式。

该未知征状值计算单元是根据该差错位置多项式及所述已知征状值，计 算出多数个未知征状值。

该判断单元是根据一个由所述已知征状值与所述未知征状值形成的征 状值集合，以输出一个检测结果信号。

本发明的错误检测更正装置用于接收一个经由一个杂信通道传递的接 收信号向量，且该接收信号向量中包含一个以一个误差位置多项式表示的 误差向量信号，该错误检测更正装置包含：一个错误检测解码模组，及一 个错误更正模组。

该错误检测解码模组包括：一个已知征状值计算单元、一个已知征状 值计算单元，及一个判断单元。该已知征状值计算单元具有一个转换器，及 一个差错位置多项式计算器。

该转换器是用以接收该接收信号向量并转换得到一个目标信号向量，其 中该目标信号向量具有多数个已知征状值。该差错位置多项式计算器是用 以接收所述已知征状值，并根据该误差位置多项式与所述已知征状值以计 算出一个差错位置多项式。

该已知征状值计算单元是用以根据该差错位置多项式及所述已知征状 值，以计算出多数个未知征状值。该判断单元是根据一个由所述已知征状 值与所述未知征状值形成的征状值集合，以输出一个检测结果信号。

该错误更正模组是根据该检测结果信号以接收该征状值集合及该目标 信号向量，并据此计算出更正后的该接收信号向量。

本发明错误检测解码模组及错误检测更正装置的优点及有益效果在于，利 用错误检测解码模组避免采用内插法的方式来进行该接收信号向量的解 码，因此，可以有效降低从该接收信号向量中进行解码时的计算复杂度以 加速计算所有征状值的运算速度，进而可以大幅度提升接收端的错误检测 及修正的速度。

上述说明仅是本发明技术方案的概述，为了能够更清楚了解本发明的 技术手段，而可依照说明书的内容予以实施，并且为了让本发明的上述和 其他目的、特征和优点能够更明显易懂，以下特举较佳实施例，并配合附 图，详细说明如下。

附图说明

图1是本发明的较佳实施例的方框图。

具体实施方式

为更进一步阐述本发明为达成预定发明目的所采取的技术手段及功效，以 下结合附图及较佳实施例，对依据本发明提出的错误检测解码模组及错误 检测更正装置其具体实施方式、方法步骤、特征及其功效，详细说明如后。

在说明本较佳实施例之前，先概略说明一系统利用一生成多项式G(x) 将一要传送的信息编码成一(n，k，d)码字信号向量后传送，其中，n代表该信 息编码后的长度，k代表该原始信息的长度，d代表该编码码字的最小汉明 距离(Hamming distance)。而且，每一编码码字所对应的该接收信号的长 度也是n。其方式如下所述：

举例来说：一具有一发送端及一接收端的通讯系统，其中，该发送端 将要传送的信息与多数个0组成一如下所示的信息信号向量m：

m＝{m₀，m₁，m₂，…，m_k-1，m_k，m_k+1，…，m_n-1}.....(F.1)

其中，m₀，m₁，m₂，…，m_k-1为信息符号，而m_k，m_k+1，m_k+2，…，m_n-1则为征状符 号且m_k＝m_k+1＝…＝m_n-1＝0。

然后，该信息信号向量m经由下列方程式(F.2)转换为一码字信号向量 c：

$c=\frac{1}{n}·\underset{i=0}{\overset{n-1}{\Sigma }}{m}_i·a^{-\mathrm{ij}}=\underset{i=0}{\overset{n-1}{\Sigma }}{m}_i·a^{-\mathrm{ij}}=M\left(a^{-j}\right).....(F.2)$

其中n为一个奇数，且α是一有限场(Finite field)GF(2^m)中的单位 n次根。

然后，该发送端将该码字信号向量c经由一杂信通道传送至该接收端 时，可能因受到杂信干扰导致该接收端所接收到的一接收信号向量r为一错 误信号向量e、一误差信号向量μ与该码字信号向量c混合而成，因此，该 接收信号向量r未必等于该码字信号向量c。

假设该错误信号向量为e＝(e₀，e₁，...，e_n-1)，并定义一错误位置多项式如下 所示：

$W\left(x\right)=\underset{j=1}{\overset{v}{\Pi }}(1-X_{j}x)=\underset{j=0}{\overset{v}{\Sigma }}{W}_j{x}^j.....(F.3)$

该误差信号向量为μ＝(μ₀，μ₁，...，μ_n-1)，并定义一误差位置多项式如下所 示：

$\Lambda \left(x\right)=\underset{j=1}{\overset{s}{\Pi }}(1-Z_{j}x)=\underset{j=0}{\overset{s}{\Sigma }}{\Lambda }_j{x}^j.....(F.4)$

则一差错信号向量可以被定义如下：

$\tilde{\mu }=\mu +e=({\tilde{\mu }}_0,{\tilde{\mu }}_1,...,{\tilde{\mu }}_{n-1}).....(F.5)$

而一差错位置多项式定义如下：

$\tau \left(x\right)=\Lambda \left(x\right)·W\left(x\right)=\underset{j=1}{\overset{v+s}{\Pi }}(1-{\tilde{X}}_{j}x)=\underset{j=0}{\overset{v+s}{\Sigma }}{\tau }_j{x}^j.....(F.6)$

其中，既是第j个误差也是第j个错误位置。

因此，该接收端所接收到的该接收信号向量r定义如下：

$r=c+\tilde{\mu }=(r_0,r_1,...,r_{n-1}).....(F.7)$

参阅图1，本发明的较佳实施例用于接收该接收信号向量r，并对其进 行错误检测以更正该接收信号向量r中的错误，使其回复相等于该码字信号 向量c，该错误检测更正装置包含：一错误检测解码模组1及一错误更正模 组2。

该错误检测解码模组1包括一已知征状值计算单元11、一未知征状值 计算单元12，及一判断单元13。

首先，该已知征状值计算单元11根据所接收的该接收信号向量r，并 产生多数个征状值，其中，该错误信号向量e的第i征状值S_i定义为e(βⁱ)，其 中，i为征状值的对应索引，β为该生成多项式G(x)的一原根。该已知征状 值计算单元11包括一转换器111及一差错位置多项式计算器112。该转换 器111将所接收的该接收信号向量r经由如下的转换，以得到一目标信号向 量a：

$a_i=\underset{j=0}{\overset{n-1}{\Sigma }}{r}_j·{\alpha }^{i·j}=\underset{j=0}{\overset{n-1}{\Sigma }}(c_j+{\tilde{\mu }}_j)·{\alpha }^{i·j}.....(F.8)$

其中，0≤i≤n-1。

借由上述的转换可以得到d-1个连续的已知征状值，所述已知征状值如 下所示：

S_i＝a_i，1≤i≤d-1.....(F.9)

然后，该差错位置多项式计算器112接收所述已知征状值，并根据该误差 位置多项式Λ(x)与所述已知征状值以计算出该差错位置多项式τ(x)。

该差错位置多项式τ(x)的计算方式在现有文献如「“Implementation of Berlekamp Massey algorithm without inversion，”Proc.IEE，vol.138，no. 3，pp.138-140，Jan，1991」以及「“VLSI design of inverse-free Berlekamp-Massey algorithm，”Proc.Inst.Elect.Eng.，vol.138，pt. E，Sept.1991，pp.295-298.」中已揭露一无倒数Berlekamp Massey演 算法，该无倒数Berlekamp Massey演算法可以利用已知征状值产生如下的 一佛倪(Forney)征状多项式：

$T_k=\underset{j=0}{\overset{s}{\Sigma }}{\Lambda }_j{S}_{k+s-j}.....(F.10)$

其中，1≤k≤d-1-s。

然后再根据该误差位置多项式Λ(x)初始化该无倒数Berlekamp Massey 演算法，就能够计算出该差错位置多项式τ(x)。

该差错位置多项式τ(x)的计算方式已清楚揭露于上述文章中，且非本发 明的重点，所以该差错位置多项式计算器112的实施细节不在此叙述。

然后，该未知征状值计算单元12利用如下的公式计算出所述未知征状 值：

S_i＝τ₁S_i-1+τ₂S_i-2+…+τ_v+sS_i-(v+s).....(F.11)

其中，d≤i≤n的征状值为所述未知征状值，且1≤i≤d-1的征状值就是 所述已知征状值。

由该差错位置多项式τ(x)中，可以得知0≤i≤v+s的系数τ_i，所以利用方 程式(F.11)可以递回方式计算出剩下的未知征状值。

因此，该判断单元13接收该已知征状值与该未知征状值并得到一征状 值集合如下所示：

S＝{S₀，S₁，S₂，…，S_n-1}.....(F.12)

当该征状值集合的每一征状值皆为0时，代表该接收信号向量r中并无 包含任何错误信号向量e或误差信号向量μ，因此，该判断单元13输出一表示 该接收信号向量r相等于该码字信号向量c的检测结果信号至该错误更正模 组2中，换句话说，该码字信号向量c传送过程中并没有错误产生。因此，该 目标信号向量不需要进行修正。而当该征状值集合中至少存在一征状值不 为0时，代表该接收信号向量r中有包含至少一错误信号向量e或一误差信 号向量μ，所以，该判断单元13输出一表示该接收信号向量r不相等于该码 字信号向量c的检测结果信号至该错误更正模组2中，并将该征状值集合与 该目标信号向量传送至该错误更正模组2中。

当该检测结果信号表示该接收信号向量r不相等于该码字信号向量c 时，该错误更正模组2根据该征状值集合与该目标信号向量，利用下列的 方程式以更正错误：

m_i＝a_i-S_i.....(F.13)

其中，0≤i≤n-1，a_i为该目标信号向量中第i个目标信号，S_i为该征状 值集合中第i个征状值。

该错误更正模组2计算得到的m_i就是更正后的该接收信号向量r′，且其 相等于该码字信号向量c。

下面将举一范例来说明本实施例的运作方式：

当一(7，4，4)原始信息编码，其中，编码后的信息长度为7，原始信息的长 度为4，且编码码字的最小汉明距离为4，然后，该原始信息多项式为 M(x)＝α⁴x³+αx⁴+α²x⁵+α⁵x⁶且该信息信号向量是m＝(α⁴，0，0，0，α，α²，α⁵)，因 此，该信息信号向量m经由方程式(F.2)能够转换为对应的码字信号向量 c＝(α⁵，α³，α³，α⁶，α²，α⁴，α⁴)，然后将该码字信号向量经由一杂信通道传送。

假设传送过程中发生错误导致本实施例的已知征状值计算单元11所 接收的该接收信号向量为r＝(α⁵，1，α³，α⁶，α²，α⁶，α⁴)时，该转换器111将 该接收信号向量r经由方程式(F.8)的转换，以得到一目标信号向量 a＝(α⁵，α⁴，α⁴，0，1，0，1)，因此，对于1≤i≤d-1的已知征状值S_i＝a_i，换句话 说，S₁＝a₁＝α⁴，S₂＝a₂＝α⁴，S₃＝a₃＝0。

然而，由于1≤i≤3的征状值为已知征状值，因此，该差错位置多项式计 算器112根据该无倒数Berlekamp Massey演算法，并以 μ⁽⁰⁾(x)＝Λ(x)＝(1+α⁵x).为初始值，以计算出对应的差错位置多项式τ(x)。

而该未知征状值计算单元12利用方程式(F.11)及对应的差错位置多项 式τ(x)中的系数以计算出所述未知征状值为S₄＝α³，S₅＝α²，S₆＝α⁴，与 S₀＝S₇＝1。

最后，该错误更正模组2根据所得到的所有征状值S₀～S₆与该目标信 号向量a，利用方程式(F.13)以计算出信息信号向量为 m₀＝α⁴，m₁＝0，m₂＝0，m₃＝0，m₄＝α，m₅＝α²，与m₆＝α⁵。

本发明利用一无倒数Berlekamp Massey演算法为基础的错误检测更正 装置，可以完全避免如前所述技术中采用内插法的方式来进行该接收信号 向量的解码。因此，可以有效降低从该接收信号向量中进行解码时的计算 复杂程度以加速计算所有征状值的运算速度，进而可以大幅度提升接收端 的错误检测及修正的速度，以确实能达到本发明的目的。

以上所述，仅是本发明的较佳实施例而已，并非对本发明作任何形式 上的限制，虽然本发明已以较佳实施例揭露如上，然而并非用以限定本发 明，任何熟悉本专业的技术人员，在不脱离本发明技术方案范围内，当可利 用上述揭示的技术内容作出些许更动或修饰为等同变化的等效实施例，但 凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例 所作的任何简单修改、等同变化与修饰，均仍属于本发明技术方案的范围 内。