错误更正码的解码器及其错误更正值计算装置

摘要

本发明是有关于一种错误更正码的解码器及其错误更正值计算装置。该错误更正码的解码器，用以根据一接收信号产生一错误更正资讯，该错误更正资讯包括分别对应多个错误位置的多个错误更正值。该错误更正码的解码器包含一征状值计算装置及一错误更正值计算装置。该征状值计算装置用以接收该接收信号并据以产生多个征状值。该错误更正值计算装置包括一第一计算模块及一第二计算模块；对于每一错误位置，该第一计算模块根据一生成多项式的一原根的一特定次方求得每一征状值的一征状值有限体除法结果；该第二计算模块根据所述征状值有限体除法结果，求得该错误位置的错误更正值。

说明书

技术领域

本发明涉及一种错误更正码(Error Correction Code，ECC)相关技术，特别是涉及一种应用循环码(cyclic code)的错误更正码的解码器及其错误更正值计算装置。

背景技术

近年来，由于数字储存技术与通讯技术的进步，资料存取与传输的速度越来越快；但，在资料存取与传输的过程中，由于传输媒体或通道极易受到杂讯干扰，因此错误检测及更正机制也日益重要。一般而言，目前的卫星通讯系统、数字电视系统、各式数字影音记录媒体等，是使用错误更正码以提升资料存取与传输的可靠度。而，在各种错误更正码中，循环码是一种相当常见的应用。

一种现有的应用循环码的错误检测更正方法，包含下列步骤：(a)接收一信号；(b)根据已接收的该信号求出多个征状值(syndrome)；(c)根据所述征状值并利用柏力肯-梅西演算法(Berlekamp-MasseyAlgorithm)，以求得一错误位置多项式(error locator polynomial)；以及(d)根据该错误位置多项式进行钱氏寻根(Chien search)，以求出至少一错误位置及对应该错误位置的一错误更正值，并对已接收的该信号进行错误更正。与该现有方法相关的理论基础，在「The Art of ErrorCorrecting Coding，Robert H.Morelos-Zaragoza，Second Edition，JohnWiley & Sons，2006」以及「Fundamentals Of Error-Correcting Codes，W.Cary Huffman and Vera Pless，CAMBRIDGE UNIVIVERSITY PRESS，2003」两本著作中均有详细的解释说明。

然而，上述现有方法，在求得征状值后，是利用柏力肯-梅西演算法或其他等价演算法求出错误位置多项式，再配合钱氏寻根迭代地求出错误位置，所需的时间复杂度较高。这在过去的使用环境下，由于资料存取与传输的速度较慢，通常不会造成严重的问题与迟误；但是由于现在电脑系统效能与传输速率大为提升，为了符合现有的使用环境，往往需要利用大量的电路，或利用提高资料处理的时脉频率的方式，方能满足在所需时间内完成解码动作；而此等方式通常会提高硬件成本，或增加系统功率消耗。

发明内容

本发明的目的在于，提供一种新型的错误更正码的解码器及其错误更正值计算装置，所要解决的技术问题是使其在求得所需征状值后，可以低复杂度的运算及电路直接求得错误更正值及错误位置。

本发明的目的及解决其技术问题是采用以下技术方案来实现的。依据本发明提出的一种错误更正码的解码器，用以根据一接收信号产生一错误更正资讯，以供对该接收信号进行错误检测及更正，该接收信号是一原始讯息于一传送端由一生成多项式编码成一循环码字后，经过一通道传输而于一接收端被接收；该错误更正码的解码器包含：一征状值计算装置，用以接收该接收信号并据以产生多个具有对应索引的征状值；以及一错误更正值计算装置，用以接收所述征状值并据以产生该错误更正资讯，该错误更正资讯包括分别对应多个错误位置的多个错误更正值，该错误更正值计算装置包括一第一计算模块及一第二计算模块，该第一计算模块及该第二计算模块是进行以下计算，以产生对应每一错误位置的该错误更正值：该第一计算模块根据该生成多项式的一原根的一特定次方求得每一征状值的一征状值有限体除法结果，该特定次方与该错误位置及该征状值的对应索引相关；及该第二计算模块根据所述征状值有限体除法结果求得一有限体加法结果作为该错误更正值。

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

较佳地，前述的错误更正码的解码器，其中该征状值计算装置是根据对应该接收信号的一接收信号多项式，求得至少一已知征状值，再根据该已知征状值求得至少一未知征状值，所述征状值包括该已知征状值及该未知征状值。

较佳地，前述的错误更正码的解码器，其中对于每一征状值，该第一计算模块是以该征状值为被除数，并以该原根的该特定次方为除数，求得该征状值有限体除法结果。

较佳地，前述的错误更正码的解码器，其中该征状值计算装置是根据对应该接收信号的一接收信号多项式，求得至少一已知征状值，再根据该已知征状值求得至少一未知征状值，所述征状值包括该已知征状值及该未知征状值。

较佳地，前述的错误更正码的解码器，其中对于每一征状值，该第一计算模块是以该征状值为被除数，并以该原根的该特定次方为除数，求得该征状值有限体除法结果。

较佳地，前述的错误更正码的解码器，其中对于长度为n的该循环码字，将所述错误更正值及其分别对应的所述错误位置以一错误多项式表示，e_j代表第j错误位置的该错误更正值，对于每一错误更正值e_j，该错误更正值计算装置的该第一计算模块所求出的每一征状值的该征状值有限体除法结果为S_i/β^j·i，S_i代表该错误多项式的第i征状值，其对应索引即为i，β为该生成多项式的原根。

较佳地，前述的错误更正码的解码器，其中该错误更正值计算装置的该第一计算模块包括一有限体常数乘法器，该第一计算模块是利用该有限体常数乘法器计算第i征状值S_i与一预设常数1/β^j·i的乘积，以求出S_i/β^j·i。

较佳地，前述的错误更正码的解码器，其中该征状值计算装置是产生该错误多项式的所有征状值，对于每一错误更正值e_j，该错误更正值计算装置的该第二计算模块是加总所述征状值有限体除法结果，以求出该错误更正值

较佳地，前述的错误更正码的解码器，其中该征状值计算装置所产生的每一征状值S_i属于一代表征状值集合，i∈R，R是所有n次分圆陪集的代表元素的集合。

较佳地，前述的错误更正码的解码器，其中对于每一错误更正值e_j，该错误更正值计算装置的该第二计算模块是计算每一征状值的该征状值有限体除法结果的一迹映射值Tr_K/F(S_i/β^j·i)，再加总所述迹映射值以求出该错误更正值F＝GF(2)，K＝GF(2^d)。

较佳地，前述的错误更正码的解码器，其中该生成多项式的原根β∈E＝GF(2^m)，对于每一错误更正值e_j，该错误更正值计算装置的该第一计算模块所求得的每一征状值的该征状值有限体除法结果是以一系数序列表示，该错误更正值计算装置的该第二计算模块是根据所述系数序列及预先建立的一迹系数组，求出该错误更正值为该系数序列的任一系数，c_l为该迹系数组的任一系数，c_l∈F＝GF(2)，且该迹系数组是根据E的一基底组预先建立。

较佳地，前述的错误更正码的解码器，其中该错误更正值计算装置的该第二计算模块包括多个及运算器及多个互斥或运算器，该第二计算模块是利用所述及运算器及所述互斥或运算器计算该错误更正值

$>e_j=S_0+\underset{l=0}{\overset{m-1}{\Sigma }}\underset{i=1}{\overset{\left|R\right|}{\Sigma }}{a}_{\mathrm{jl}}^i{c}_l.$>

本发明的目的及解决其技术问题还采用以下技术方案来实现。依据本发明提出的一种错误更正值计算装置，适用于一错误更正码的解码器，该错误更正码的解码器的一征状值计算装置根据已接收的一接收信号产生多个具有对应索引的征状值，该接收信号是一原始讯息于一传送端由一生成多项式编码成一循环码字后，经过一通道传输而于一接收端被接收者；其中：该错误更正值计算装置用以接收所述征状值并据以产生分别对应多个错误位置的多个错误更正值，该错误更正值计算装置包含一第一计算模块及一第二计算模块，该第一计算模块及该第二计算模块是进行以下计算，以产生对应每一错误位置的该错误更正值：该第一计算模块根据该生成多项式的一原根的一特定次方求得每一征状值的一征状值有限体除法结果，该特定次方与该错误位置及该征状值的对应索引相关；及该第二计算模块根据所述征状值有限体除法结果求得一有限体加法结果作为该错误更正值。

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

较佳地，前述的错误更正值计算装置，其中对于每一征状值，该第一计算模块是以该征状值为被除数，并以该原根的该特定次方为除数，求得该征状值有限体除法结果。

较佳地，前述的错误更正值计算装置，其中对于长度为n的该循环码字，将所述错误更正值及其分别对应的所述错误位置以一错误多项式表示，e_j代表第j错误位置的该错误更正值，对于每一错误更正值e_j，该第一计算模块所求出的每一征状值的该征状值有限体除法结果为S_i/β^j·i，S_i代表该错误多项式的第i征状值，其对应索引即为i，β为该生成多项式的原根。

较佳地，前述的错误更正值计算装置，其中该第一计算模块包括一有限体常数乘法器，该第一计算模块是利用该有限体常数乘法器计算第j征状值S_i与一预设常数1/β^j·i的乘积，以求出S_i/β^j·i。

较佳地，前述的错误更正值计算装置，其中对于每一错误更正值e_j，该第一计算模块是求出该错误多项式的所有征状值中，每一征状值S_i的该征状值有限体除法结果，i＝0，1，...n-1，该第二计算模块是加总所述征状值有限体除法结果，以求出该错误更正值

较佳地，前述的错误更正值计算装置，其中该第一计算模块是求出属于一代表征状值集合的每一征状值S_i的该征状值有限体除法结果，i∈R，R是所有n次分圆陪集的代表元素的集合。

较佳地，前述的错误更正值计算装置，其中对于每一错误更正值e_j，该错误更正值计算装置的该第二计算模块是计算每一征状值的该征状值有限体除法结果的一迹映射值Tr_K/F(S_i/β^j·i)，再加总所述迹映射值以求出该错误更正值F＝GF(2)，K＝GF(2^d)。

较佳地，前述的错误更正值计算装置，其中该生成多项式的原根β∈E＝GF(2^m)，对于每一错误更正值e_j，该错误更正值计算装置的该第一计算模块所求得的每一征状值的该征状值有限体除法结果是以一系数序列表示，该错误更正值计算装置的该第二计算模块是根据所述系数序列及预先建立的一迹系数组，求出该错误更正值为该系数序列的任一系数，c_l为该迹系数组的任一系数，c_l∈F＝GF(2)，且该迹系数组是根据E的一基底组预先建立。

较佳地，前述的错误更正值计算装置，其中该错误更正值计算装置的该第二计算模块包括多个及运算器及多个互斥或运算器，该第二计算模块是利用所述及运算器及所述互斥或运算器计算该错误更正值

$>e_j=S_0+\underset{l=0}{\overset{m-1}{\Sigma }}\underset{i=1}{\overset{\left|R\right|}{\Sigma }}{a}_{\mathrm{jl}}^i{c}_l.$>

本发明与现有技术相比具有明显的优点和有益效果。借由上述技术方案，本发明错误更正码的解码器及其错误更正值计算装置至少具有下列优点及有益效果：

本发明的有益效果在于：借由本发明的该错误更正值计算装置的该第一计算模块及该第二计算模块，在求得所需征状值后，可以低复杂度的运算及电路直接求得错误更正值及错误位置。

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

附图说明

图1是一方块图，说明本发明错误更正码的解码器的一较佳实施例及其应用。

图2A是一示意图，说明在该较佳实施例的一错误更正值计算装置的一第一实施态样中，一第一计算模块所使用的其中一有限体常数乘法器。

图2B是一示意图，说明在该第一实施态样中，一第二计算模块所使用的一有限体加法器。

图3是一示意图，说明在该错误更正值计算装置的一第二实施态样中，一第二计算模块所使用的多个迹映射器及一有限体加法器。

图4是一示意图，说明在该错误更正值计算装置的一第三实施态样中，一第二计算模块所使用的多个及运算器及多个互斥或运算器。

具体实施方式

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

假设一传送端利用一生成多项式G(x)将一原始讯息编码成一(n，k，d)循环码字后，经过通道(channel)传输而于一接收端被接收成为一接收信号，n代表该循环码字的长度，k代表该原始讯息的长度，d代表该循环码字的最小汉明距离(Hamming distance)，该循环码字的最大错误更正容量(errorcorrecting capacity)为。而且，对应该循环码字的该接收信号的长度也是n。

由于该循环码字于通道传递的过程中，有可能受到杂讯(noise)干扰，所以，该接收信号未必等于该循环码字。若将该循环码字以一码字多项式表示，对应该杂讯干扰的错误讯息以一错误多项式表示，则该接收信号可以如式(1)所示的一接收多项式r(x)来表示。

$>r\left(x\right)=\underset{j=0}{\overset{n-1}{\Sigma }}{r}_j{x}^j=c\left(x\right)+e\left(x\right)···\left(1\right)$>

参阅图1，本发明错误更正码的解码器1的较佳实施例，适用于一错误检测更正系统，该错误检测更正系统用以接收该接收信号，并对该接收信号进行错误检测及更正以得到对应的该循环码字。该错误检测更正系统包含该错误更正码的解码器1，及一错误更正装置2。该错误更正码的解码器1包括一征状值计算装置11，及一错误更正值计算装置12。而该错误更正码的解码器1及该错误更正装置2的实施方式及运作关进一步描述如后。

首先，该征状值计算装置11接收该接收信号，并产生多个征状值，该错误多项式e(x)的第i征状值S_i定义为e(βⁱ)，i为征状值的对应索引，β为该生成多项式G(x)的一原根。该征状值计算装置11包括一已知征状值(knownsyndrome)计算模块111，及一未知征状值(unknown syndrome)计算模块112；该已知征状值计算模块111根据该生成多项式G(x)的原根β(primitive root)及该接收多项式r(x)求得至少一已知征状值，然后，该未知征状值计算模块112再根据该已知征状值求得至少一未知征状值；所述征状值包括该已知征状值及该未知征状值。由于所述征状值的求法已揭露于一些现有的文献，例如，「″Algebraic Decoding of(71，36，11)，(79，40，15)，and(97，49，15)Quadratic Residue Codes，″IEEE TRANSACTIONSON COMMUNICATIONS，VOL.51，NO.9，PP.1463-1473，SEPTEMBER 2003」以及「″Algebraic Decoding of(103，52，19)and(113，57，15)QuadraticResidue Codes，″IEEE TRANSACTIONS ON COMMUNICATIONS，VOL.53，NO.5，PP.749-754，MAY 2005」，且非本发明的重点，所以该已知征状值计算模块111及该未知征状值计算模块112的实施细节不在此赘述。

继而，该错误更正值计算装置12接收所述征状值，并产生一错误更正资讯，该错误更正资讯包括分别对应多个错误位置的多个错误更正值，可将所述错误更正值及所述错误位置以该错误多项式表示，e_j代表第j错误位置的该错误更正值。该错误更正值计算装置12包括一第一计算模块121及一第二计算模块122，可以下列三种实施态样来实现。值得一提的是，对应不同的实施态样的需要，该征状值计算装置11所需计算的所述征状值略有不同，但针对每一征状值的计算方式及定义并无不同。

第一实施态样

配合此第一实施态样，该征状值计算装置11需计算该错误多项式e(x)的所有征状值S_i，i＝0，1，...，n-1(即i为0到n-1的整数)。

对于第j错误位置的该错误更正值e_j，该第一计算模块121是根据该生成多项式G(x)的原根β，求出所有征状值中每一者的一有限体(finitefield)除法结果S_i/β^j·i，i＝0，1，...，n-1；然后，该第二计算模块122加总所述有限体除法结果S_i/β^j·i，以求得一有限体加法结果，而该有限体加法结果即为第j错误位置的该错误更正值e_j，整理如以下式(2)。

$>e_j=\underset{i=0}{\overset{n-1}{\Sigma }}(S_i/{\beta }^{j·i})···\left(2\right)$>

参阅图1、图2A与图2B，由于该生成多项式G(x)的原根β为一已知常数，在此第一实施态样中，该第一计算模块121包括多个有限体常数乘法器123，该第二计算模块122包括一有限体加法器124。该第一计算模块121利用与第i征状值S_i对应的有限体常数乘法器123，计算其与一预设常数1/β^j·i的乘积，以求出S_i/β^j·i；然后，该第二计算模块122利用该有限体加法器124加总所述有限体除法结果S_i/β^j·i，以求得第j错误位置的该错误更正值e_j。

第二实施态样

配合此第二实施态样，该征状值计算装置11仅需计算该错误多项式e(x)的所述征状值中，属于一代表征状值集合的征状值S_i，i∈R，R是所有n次分圆陪集(cyclotomic coset of i modulo n)的代表元素(representative)的集合。n次分圆陪集的定义如以下式(3)所示。

C_i＝{i·2^k|k＝0，1，...，d-1}.............................(3)

d为使得i·2^d≡i(modn)的一最小正整数。

为了使后续的描述更为清楚明确，先进行以下式(4)～(7)定义。

F＝GF(2).........................................(4)

E＝GF(2^m)........................................(5)

GF代表加罗瓦体(Galois Field)，E为F的一m阶(degree m)延伸体(extension field)。

若d是m的一约数(divisor)，则E的一子体(subfield)K定义如下。

K＝GF(2^d)........................................(6)

接着，定义由K到F(K onto F)的迹映射(trace mapping)值如下。

$>{\mathrm{Tr}}_{K/F}\left(\gamma \right)=\gamma +{\gamma }^2+...+{\gamma }^{2^{d-1}},\gamma \in K···\left(7\right)$>

基于上述的定义与假设，第j错误位置的该错误更正值e_j的计算可简化为：该第一计算模块121求出该代表征状值集合中每一者的该有限体除法结果S_i/β^j·i，i∈R；然后，该第二计算模块122计算每一有限体除法结果S_i/β^j·i的一迹映射值Tr_K/F(S_i/β^j·i)，再加总所述迹映射值Tr_K/F(S_i/β^j·i)，以求得该有限体加法结果作为第j错误位置的该错误更正值e_j，整理如以下式(8)。

$>e_j=\underset{i\in R}{\Sigma }{\mathrm{Tr}}_{K/F}\left(S_i{\beta }^{j·i}\right)···\left(8\right)$>

参阅图1、图2A与图3，在此第二实施态样中，该第一计算模块121的实施类似于该第一实施态样，是利用与第i征状值S_i对应的有限体常数乘法器123求出其有限体除法结果S_i/β^j·i。该第二计算模块22包括多个迹映射器125及一有限体加法器126；该第二计算模块22是利用与S_i/β^j·i对应的迹映射器125先求出其迹映射值Tr_K/F(S_i/β^j·i)，再利用该有限体加法器126加总所述迹映射值Tr_K/F(S_i/β^j·i)，以求得第j错误位置的该错误更正值e_j，每一迹映射器125的实施类似于有限体加法器。

第三实施态样

配合此第三实施态样，该征状值计算装置11仅需计算与第二实施态样相同的所述征状值S_i，即属于该代表征状值集合的征状值S_i，i∈R。

在此第三实施态样中，该第二计算模块122的实施可基于以下的定义与假设更进一步地简化。

假设α⁰，...，α^m-1为E＝GF(2^m)的一基底组(basis)，则一迹系数组的任一系数c_l定义如式(9)。

c_l＝Tr_E/F(α^l)......................................(9)

由于α⁰，...，α^m-1为一组已知常数，所以该迹系数组可预先建立且c_l∈F。

假设该生成多项式G(x)的原根β∈E，且每一有限体除法结果S_i/β^j·i可以式(10)中的一系数序列表示。

$>S_i/{\beta }^{j·i}=\underset{l=0}{\overset{m-1}{\Sigma }}{a}_{\mathrm{jl}}^i{a}^l,a_{\mathrm{jl}}^i\in F···\left(10\right)$>

基于上述的定义与假设，第j错误位置的该错误更正值e_j的计算可再简化为：该第一计算模块121求出该代表征状值集合中每一者的该有限体除法结果S_i/β^j·i，i∈R，并储存其系数序列然后，该第二计算模块122根据所述系数序列及预先建立的该迹系数组，求得该有限体加法结果作为第j错误位置的该错误更正值e_j，整理如以下式(11)。

$>e_j=S_0+\underset{l=0}{\overset{m-1}{\Sigma }}\underset{i=1}{\overset{\left|R\right|}{\Sigma }}{a}_{\mathrm{jl}}^i{c}_l···\left(11\right)$>

参阅图1、图2A与图4，在此第三实施态样中，该第一计算模块121的实施与该第二实施态样相同。该第二计算模块122包括多个及(AND)运算器127及多个互斥或(XOR)运算器128；该第二计算模块122是利用所述及运算器127进行式(11)中的乘法运算，利用所述互斥或运算器128进行式(11)中的加法运算。

最后，该错误更正装置2根据该错误更正资讯，即，所述错误更正值及其等分别对应的所述错误位置，对该接收信号进行错误检测及更正，以得到对应的该循环码字。当有任一错误位置的错误更正值不为0(即，e(x)≠0)时，表示检测到该接收信号受到杂讯污染，必须进行如式(12)所示的错误更正。

c(x)＝r(x)-e(x)....................................(12)

综上所述，借由本发明的该错误更正值计算装置12的该第一计算模块121及该第二计算模块122，在求得所需征状值后，不需“利用柏力肯-梅西演算法求出错误位置多项式，再配合钱氏寻根叠代地求出错误位置”，而是以低复杂度的运算及电路直接求得错误更正值及错误位置，所以确实能达成本发明的目的。

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