On the Solution of Algebraic Equations

《On the Solution of Algebraic Equations 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、INFORMATIONANnCONTROL1O,553-564(1967)OntheSolutionofAlgebraicEquationsoverFiniteFieldsE.R.BERLEKA~P,*H.RUMSEY,ANDG.SOLOMON~JetPropulsionLaboralory,Pasadena,California91103Thisarticlegivesnewfastmethodsfordecodingcertainerror-correctingcodesbysolvingcertainalgebraicequations

2、.AsdescribedbyPeterson(1961),thelocationsofaBose-ChaudhuriHocquenghemcodeoverafieldofcharacteristicpareassociatedwiththeelementsofanextensionfield,GF(pk).Thecodeisdesignedinsuchawaythattheweightedpower-sumsymmetricfunctionsoftheerrorlocationscanbeobtaineddirectlybycomputing

3、appropriatelychosenparitychecksonthereceivedword.Goodmethodsforcomputingtheele-mentarysymmetricfunctionsfromtheweightedpower-sumsym-metricfunctionshavebeenpresentedbyBerlekamp(1967).Theelementarysymmetricfunctions,al,a2,.-.,atarethecoefficientsofanalgebraicequationwhoseroot

4、saretheerrorlocationsxt-t-alx~-x-{-~2x~2-{-'"+qt=0.PreviousmethodsforfindingtherootsofthisequationhavesearchedalloftheelementsinGF(pk)(Chien,1964)orlookeduptheanswerinalargetable(Polkinghorn,1966).Wepresenthereimprovedproceduresforextractingtherootsofalgebraicequationsofsma

5、lldegrees.QUADRATICEQUATIONSINFIELDSOFCHARACTERISTICTWOCASE1:WITHREPEATEDROOTSInordertosolveaquadraticequationofthetypex2+c=0,wherecandxCGF(2k),wemustextractthesquarerootofc.Sinceinanyfieldofcharacteristictwowehavetheidentity(x+y)2=x2-t-y2andsimilarly,(x~-y)l~2_-x11~+ylI2th

6、esquarerootisalinearoperation.IntermsofafixedbasisofGF(2k),namelyUl,u~,,u~,wemaywritec=~--~=1c~,wherec~~GF(2).Becauseofthelinearityofthesquareroot,wethenhavec112=~-~1ci(u~)11~.Ofcourse,(u~)lj2canalsobePresentaddress:BellTelephoneLaboratories,MurrayHill,NewJersey07971.Presen

7、taddress:TRWSystems,RedondoBeach,California90278.553Copyright(~)byAcademicPressInc.55AxBERLEKAMP,RUMSEY,ANDSOLOMONrepresentedintermsofthissame:basis,withLu~)~i~1~2~~iR~,ju~withR~,j~GF(2).Wethenhavekkc112=EEc~R,.~.usi=15=1Forexample,inGF(25),letustakethebasisconsistingofu~=a

8、5-~fori=1,2,3,4,5~whereasatisfiestheequationa5+a2+1=0.Therepresentationofallofthee