




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
BCHCodesOUTLINE[1]Finitefields[2]Minimalpolynomials[3]CyclicHammingcodes[4]BCHcodes[5]Decoding2error-correctingBCHcodesBCHCodes[1]Finitefields1.Irreduciblepolynomialf(x)K[x],f(x)hasnoproperdivisorsinK[x] Eg. f(x)=1+x+x2isirreducible f(x)=1+x+x2+x3=(1+x)(1+x2)isnotirreducible
f(x)=1+x+x4isirreducibleBCHCodes2.Primitivepolynomialf(x)isirreducibleofdegreen>1f(x)isnotadivisorof1+xmforanym<2n-1 Eg.f(x)=1+x+x2isnotafactorof1+xmform<3sof(x)isaprimitivepolynomialf(x)=1+x+x2+x3+x4isirreduciblebut1+x5=(1+x)(1+x+x2+x3+x4)andm=5<24-1=15sof(x)isnotaprimitivepolynomialBCHCodes3.DefinitionofKn[x]
ThesetofallpolynomialsinK[x]havingdegreelessthannEachwordinKncorrespondstoapolynomialinKn[x]MultiplicationinKnmoduloh(x),withirreducibleh(x)ofdegreenIfweusemultiplicationmoduloareducibleh(x),say,1+x4todefinemultiplicationofwordsinK4,however:
(0101)(0101)(x+x3)(x+x3) =x2+x6 =x2+x2(mod1+x4) =0
0000(K4-{0000}isnotclosedundermultiplication.)
BCHCodes4.DefinitionofField(Kn,+,x)(Kn,+)isanabeliangroupwithidentitydenoted0Theoperationxisassociativeax(bxc)=(axb)xcThereisamultiplicativeidentitydenoted1,with101xa=ax1=a,aKnTheoperationxisdistributiveover+ax(b+c)=(axb)+(axc)Itiscommunicativeaxb=bxa,a,bKnAllnon-zeroelementshavemultiplicativeinversesGaloisFields:GF(2r)Foreveryprimepowerorderpm,thereisauniquefinitefieldoforderpmDenotedbyGF(pm)BCHCodesExampleLetusconsidertheconstructionofGF(23)usingtheprimitivepolynomialh(x)=1+x+x3todefinemultiplication.Wedothisbycomputingximodh(x): word ximodh(x) 100 1 010 x 001 x2 110 x31+x 011 x4x+x2 111 x51+x+x2 101 x61+x2BCHCodes5.UseaprimitivepolynomialtoconstructGF(2n)LetKnrepresentthewordcorrespondingtoxmodh(x)i
ximodh(x)m1form<2n-1sinceh(x)dosenotdivide1+xmform<2n-1Sincej=iforjiiffi=j-iij-i=1Kn\{0}={i|i=0,1,…,2n-2}BCHCodes6.
GF(2r)isprimitiveisprimitiveifm1for1m<2r-1Inotherwords,everynon-zerowordinGF(2r)canbeexpressedasapowerofExample
ConstructGF(24)usingtheprimitivepolynomialh(x)=1+x+x4.Writeeveryvectorasapowerof
xmodh(x)(seeTable5.1below) Notethat15=1. (0110)(1101)=5.7=12=1111BCHCodesTable1ConstructionofGF(24)usingh(x)=1+x+x4wordpolynomialinxmodh(x)powerof00000-100010=10100x0010x220001x3311001+x=x440110x+x2=x550011x2+x3=x66BCHCodesTable1(continue)ConstructionofGF(24)usingh(x)=1+x+x4wordpolynomialinxmodh(x)powerof11011+x+x3=x7710101+x2=x880101x+x3=x9911101+x+x2=x10100111x+x2+x3=x111111111+x+x2+x3=x121210111+x2+x3=x131310011+x3=x1414BCHCodes[2]Minimalpolynomials
1.Rootofapolynomial:anelementofF=GF(2r),p(x)F[x]isarootofapolynomialp(x)iffp()=02.OrderofThesmallestpositiveintegermsuchthatm=1inGF(2r)isaprimitiveelementifithasorder2r-1BCHCodes3.MinimalpolynomialofThepolynomialinK[x]ofsmallestdegreehavingasrootDenotedbym(x)m(x)isirreducibleoverKIff(x)isanypolynomialoverKsuchthatf()=0,thenm(x)isafactoroff(x)m(x)isuniquem(x)isafactorofBCHCodesExampleLetp(x)=1+x3+x4,andletbetheprimitiveelementinGF(24)constructedusingh(x)=1+x+x4(seeTable5.1): p()=1+3+4=1000+0001+1100=0101=9isnotarootofp(x).However p(7)=1+(7)3+(7)4=1+21+28=1+6+13=1000+0011+1011=0000=07isarootofp(x).BCHCodes4.FindingtheminimalpolynomialofReducetofindalinearcombinationofthevectors{1,,2,…,r},whichsumsto0Anysetofr+1vectorsinKrisdependent,suchasolutionexistsRepresentm(x)bymi(x)where=Ieg.
Findthem(x),=3,GF(24)constructedusingh(x)=1+x+x4BCHCodesUsefulfacts:f(x)2=f(x2)
Iff()=0,thenf(2)=(f())2=0Ifisarootoff(x),soare,2,4,…,Thedegreeofm(x)is|{,2,4,…,}|BCHCodesExampleFindthem(x),=3,GF(24)constructedusingh(x)=1+x+x4Letm(x)=m3(x)=a0+a1x+a2x2+a3x3+a4x4thenwemustfindthevaluefora0,a1,…,a4{0,1}
m()=0=a01+a1+a22+a33+a44 =a00+a13+a26+a39+a412 0000=a0(1000)+a1(0001)+a2(0011)+a3(0101)+a4(1111)
a0=a1=a2=a3=a4=1and
m(x)=1+x+x2+x3+x4BCHCodesExampleLet
m5(x)betheminimalpolynomialsof=5,5GF(24) Since{,2,4,8}={5,10},therootsofm5(x)are5and10whichmeansthatdegree(m5(x))=2.Thusm5(x)=a0+a1x+a2x2: 0=a0+a15+a210
=a0(1000)+a1(0110)+a2(1110) Thusa0=a1=a2=1andm5(x)=1+x+x2BCHCodesTable2:MinimalpolynomialsinGF(24)constructedusing1+x+x4ElementofGF(24)Minimalpolynomial01,2,4,83,6,9,125,107,11,13,14x1+x1+x+x41+x+x2+x3+x41+x+x21+x3+x4BCHCodes[3]CyclicHammingcodes1.ParitycheckmatrixTheparitycheckmatrixofaHammingcodeoflengthn=2r-1hasitsrowsall2r-1nonzerowordsoflengthrisaprimitiveelementof GF(2r)Histheparitycheckma- trixofaHammingcodeof lengthn=2r-1BCHCodes2.GeneratorpolynomialForanyreceivedwordw=w0w1…wn-1 wH=w0+w1+…+wn-1n-1w()wisacodewordiffisarootofw(x)m(x)isitsgeneratorpolynomialTheorem5.3.1
AprimitivepolynomialofdegreeristhegeneratorpolynomialofacyclicHammingcodeoflength2r-1BCHCodesExample: Letr=3,son=23-1=7.Usep(x)=1+x+x3toconstruct
GF(23),and010astheprimitiveelement.Recallthati
ximodp(x).ThereforeaparitycheckmatrixforaHammingcodeoflength7isBCHCodes3.DecodingthecyclicHammingcodew(x)=c(x)+e(x),wherec(x)isacodeword,e(x)istheerrorw()=e()ehasweight1,e()=j,jisthepositionofthe1inec(x)=w(x)+xjBCHCodesExample: SupposeGF(23)wasconstructedusing1+x+x3.m1(x)=1+x+x3isthegeneratorforacyclicHammingcodeoflength7.Suppose w(x)=1+x+x3+x6isreceived.Then w()=1+2+3+6 =100+001+110+101 =110 =3
e(x)=x3andc(x)=w(x)+x3=1+x2+x6
BCHCodes[4]BCHcodes1.BCH:Bose-Chaudhuri-HocquenghamAdmitarelativelyeasydecodingschemeTheclassofBCHcodesisquiteextensiveForanypositiveintegersrandtwitht2r-1-1,thereisaBCHcodesoflengthn=2r-1whichist-errorcorrectingandhasdimensionkn-rtBCHCodes2.
Paritycheckmatrixforthe2error-correctingBCHThe2error-correctingBCHcodesoflength2r-1isthecycliclinearcodes,generatedbyg(x)=,r4Thegeneratorpolynomial:g(x)=m1(x)m3(x)Degree(g(x))=2r,thecodehasdimensionn-2r=2r-1-2rBCHCodesExample:
isaprimitiveelementinGF(24)constructedwithp(x)=1+x+x4.Wehavethatm1(x)=1+x+x4andm3(x)=1+x+x2+x3+x4.Therefore g(x)=m1(x)m3(x)=1+x4+x6+x7+x8 isthegeneratorfora2error-correctingBCHcodeoflength15BCHCodes3.TheparitycheckmatrixofC15(distanced=5)
(Table3)BCHCodes[5]Decoding2error-correctingBCHcodes1.Errorlocatorpolynomial
w(x):receivedword
syndromewH=[w(),w(3)]=[s1,s3]Histheparitycheckmatrixforthe(2r-1,2r-2r-1,5)2error-correctingBCHcodewithgeneratorg(x)=m1(x)m3(x)wH=0ifnoerrorsoccurredIfoneerroroccurred,theerrorpolynomiale(x)=xi wH=eH=[e(),e(3)]=[i,3i]=[s1,s3],BCHCodesIftwoerrorsoccurred,sayinpositionsiandj,ij,e(x)=xi+xj,wH=eH=[e(),e(3)]=[i+j,3i+3j]=[s1,s3]Theerrorlocatorpolynomial:BCHCodesExample: Letww(x)beareceivedwordwithsyndromess1=0111=w()ands3=1010=w(3),wherewwasencodedusingC15.FromTable5.1wehavethats111ands38.Then Weformthepolynomialx2+11x+2andfindthatithasroots4and13.Thereforewecandecidethatthemostlikelyerrorsoccurredinpositions4and13,e(x)=x4+x13,themostlikelyerrorpatternis 0000100000000010BCHCodes2.DecodingalgorithmofBCHcodesCalculatethesyndromewH=[s1,s3]=[w(),w(3)]Ifs1=s3=0,noerrorsoccurredIfs1=0ands30,askforretransmissionIf(s1)3=s3,asingleerroratpositioni,wheres1=iFromthequadraticequation: (*)Ifequation(*)hastwodistinctrootsiandj,correcterrorsatpositionsiandjIfequation(*)doesnothavetwodistinctrootsinGF(2r),concludethatatleastthreeerrorsoccurredBCHCodesExample:
AssumewisreceivedandthesyndromeiswH=01111010[11,8].Now Inthiscaseequation(*)isx2+11x+2=0whichhasroots4and13.Correcterrorinpositionsi=4andj=13.Example:
AssumethesyndromeiswH=[w(),w(3)]=[3,9].Then(s1)3=(
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 山東省師范大學附屬中學2024-2025學年高三下學期第二期聯考物理試題含解析
- 上海政法學院《數據預處理技術及應用》2023-2024學年第二學期期末試卷
- 江蘇省鎮江市重點達標名校2025年中考猜題卷(一)化學試題含解析
- 沈陽工學院《水利水電工程造價》2023-2024學年第一學期期末試卷
- 瀘溪一中2025年上學期高一第四次階段檢測數學試卷參考答案
- 2025年中考英語三輪復習之寫作-時代變遷
- 神經內科生命體征護理
- 高一英語同步訓練:訓練二LearningaboutLanguage
- 壓瘡護理教學查房
- 中昇山東省2024-2025學年高三4月大聯考政治試題
- 高空清洗施工安全的協議書6篇
- 食品安全自查制度、從業人員健康管理、進貨查驗記錄
- 南寧2025年3月高三二模英語試卷
- 產教融合校企合作框架協議書8篇
- 2025年駕駛三力測試題及答案
- 2025-2030年中國加濕器數據監測研究報告
- 兒童生長發育遲緩
- 班組級安全教育培訓內容
- 2025年河南工業職業技術學院單招職業技能測試題庫及參考答案
- 《無人機操控培訓材料》課件
- 電氣控制技術基礎應用知到智慧樹章節測試課后答案2024年秋蘭州石化職業技術大學
評論
0/150
提交評論