解码错误订正码时用以解答键方程式多项式之方法及其装置

摘要

在解码时，通常为了错误订正目的而将接收字码经编码处理。据此，一种在键方程式解答步骤中，用以计算错误定位器多项式和错误求值器多项式之一种方法，在本发明加以揭露。藉由本发明，多项式可经由多个中间步骤而产生，而上述步骤可由最少量之硬体线路来加以实施。中间步骤之数目需要一相对应之运算时间周期(cycle)数目，以完成多项式之计算。依所选择之(N,K)码而定，计算多项式所须之运算时间周期数目将是介于上游资料计算所须时间之内。特别的是，只须小数量之暂存器及有限场乘法器(FFM)，且不须有限场反转器(FFI)之有效安排配置也加以揭露。使用这些新方法，仅使用4t+2ρ+4个暂存器，3个FFM且不须FFI之有效节省面积的架构也已揭示，用以实施由无反转Euclidean演算法推导而得之方法。此外，所提出之架构也可用来求出Forney徵兆多项式。本发明之方法及其装置可广泛应用于各种具有适当编码长度之RS码和BCH码，包括错误更正以及抹除更正之情况。

主权项

1.一种在解码错误订正码时用以解答键方程式多项式之装置,尤其是一种可以应用在BCH以及Reed-Solomon(RS)解码器的所谓无反转打散架构装置,其主要之组成架构系包括下列几个部分:(a)徵兆计算器,接收字元码并输出徵兆多项式到键方程式解答器;(b)键方程式解答器,接收徵兆多项式以产生错误定位多项式及错误计算多项式;(c)Chein Search,接收错误定位多项式,并将结果输入到错误値计算器并输出错误区域;(d)错误値计算器,接收由键方程式解答器及CheinSearch的讯号并输出错误値。2.如申请专利范围第1项所述之装置,其中所述之架构是使用在BCH和Reed-Solomon(RS)解码器。3.如申请专利范围第1项所述之装置,其中所述之架构是以无反转打散架构之方法应用于BCH和Reed-Solomon解码器。4.如申请专利范围第1项所述之装置,其中所述之架构除了可以除去错误的讯号之外也可用于抹除符号。5.如申请专利范围第1项所述之装置,其中所述之架构是用于无反转Euclidean演算法。6.如申请专利范围第1项所述之装置,其中所述之架构是以移除会拖累整体有限场反转器来完成。7.如申请专利范围第1项所述之装置,其中所述之架构可将原来2t个步骤更改为只需t个步骤就能完成。8.如申请专利范围第1项所述之装置,其中所述之架构可使用打散的技巧大幅的将有限场乘法器由4t-6t个减少为仅仅3个。9.如申请专利范围第1项所述之装置,其中所述之架构可使用打散的技巧,其中仅仅使用4t+2+4个暂存器。10.如申请专利范围第1项所述之装置,其中所述之架构可使用打散的技巧,无须使用FFI。11.如申请专利范围第1项所述之装置,其中所述之架构可使用以求Forney徵兆多项式。12.如申请专利范围第1项所述之装置,其中所述之架构是使用于通讯及储存系统上。13.一种在解码错误订正码时用以解答键方程式多项式之方法,尤其是一种可以应用在BCH以及Reed-Solomon(RS)解码器的所谓无反转打散架构之方法,其主要包括下列几个步骤:(a)接收字元码并计算徵兆;(b)产生错误定位多项式及错误计算多项式;(c)寻找错误区域;(d)计算错误値。14.如申请专利范围第13项所述之方法,其中所述之架构是使用在BCH和Reed-Solomon解码器。15.如申请专利范围第13项所述之方法,其中所述之架构是以无反转打散架构之方法使用于BCH和Reed-Solomon解码器。16.如申请专利范围第13项所述之方法,其中所述之架构除了可以除去错误的讯号之外也可用于抹除符号。17.如申请专利范围第13项所述之方法,其中所述之架构适用于无反转Euclidean演算法。18.如申请专利范围第13项所述之方法,其中所述之架构是以移除会拖累整体有限场反转器来完成。19.如申请专利范围第13项所述之方法,其中所述之架构可将原来2t个步骤更改为只需t个步骤就能完成。20.如申请专利范围第13项所述之方法,其中所述之架构可使用打散的技巧大幅的将有限场乘法器由4t-6t个减少为仅仅3个。21.如申请专利范围第13项所述之方法,其中所述之架构可使用打散的技巧,其中仅仅使用4t+2+4个暂存器。22.如申请专利范围第13项所述之方法,其中所述之架构可使用打散的技巧,无须使用FFI。23.如申请专利范围第13项所述之方法,其中所述之架构可使用以求Forney徵兆多项式。24.如申请专利范围第13项所述之方法,其中所述之架构是使用于通讯及储存系统上。25.一种在解码错误订正码时用以解答键方程式多项式之方法,尤其是一种可以应用在BCH以及Reed-Solomon(RS)解码器的所谓无反转打散架构之方法,其过程包括下列几个改善之步骤:(a)改善Educlidean演算法的速度;(b)修饰解码步骤以减少半数之解码结果;(c)将错误定位多项式和错误评价多项式之计算结合。26.如申请专利范围第25项所述之方法,其中所述之Educlidean演算法是和时间共享一个有限场乘法器(FFMs)。27.如申请专利范围第25项所述之方法,其中所述之方法可降低硬体使用面积。28.如申请专利范围第25项所述之方法,其中所述之改善Educlidean演算法的速度是以移去有限场反转器之限制的无反转之Educlidean演算法来完成。29.如申请专利范围第25项所述之方法,其中所述之无反转Educlidean演算法是使角度重叠的数目降低到t来完成。30.如申请专利范围第28项所述之方法,其中所述之无反转Educlidean演算法是使错误定位多项式角度由+1增加为+t及错误计算多项式。31.如申请专利范围第28项所述之方法,其中所述之无反转Educlidean演算法其每次之重复小于t。32.一种在解码错误订正码时用以解答键方程式多项式之方法,尤其是一种可以应用在BCH以及Reed-Solomon(RS)解码器的所谓无反转打散架构之方法,其方法包含下列:(a)每一个分割是被限制到至少一度;(b)将错误定位多项式和错误评价多项式计算使用之硬体结合;(c)将FFMs之数目降低为3个。33.如申请专利范围第32项所述之方法,将使Euclidean Algorithm变慢,但是不会冲击整体之解码速度。34.如申请专利范围第32项所述之方法,其中所述BCH以及Reed-Solomon(RS)解码器,其合成码在影音光碟中(DVD)使用RS合成码在行方向(182,172)及列方向(208,192)。35.如申请专利范围第32项所述之方法,其中所述BCH以及Reed-Solomon(RS)解码器,其合成码在数位电视广播系统使用(204,188)RS码。36.如申请专利范围第32项所述之方法,其中所述BCH以及Reed-Solomon(RS)解码器,其合成码在一般CD-ROM使用小数目的RS码包括(32,28)(28,24)。37.如申请专利范围第32项所述之方法,其中所述BCH以及Reed-Solomon(RS)解码器,其合成码在无线通讯方面,尤其AMPS电话系统使用(40,28)和(48,36)双位元的BCH码,其为(63,51)的短码。图式简单说明:第1A图 显示解码具错误订正功能字码时之处理方块图。第1B图 显示解码具错误及抹除订正功能字码时之处理方块图第2A图 显示解码程序中第i个步骤中起始运算之状态第2B图 显示解码程序中第i个步骤中运算时间周期j=0之状态第2C图 显示用以求出解码程序中第i个步骤之第j个错误及抹除求値器多项式系数之状态第2D图 显示用以求出解码程序中第i个步骤之第个错误定位器多项式系数之状态第2E图 显示相同的方法及装置,用以求出Forney徵兆多项式时第i个步骤之第个系数之状态。