⊕國立中山大學資訊工程學系碩士論文適用於IEEE802.16e標準之多碼率LDPC解碼器設計DesignofMulti-CodeRateLDPCDecoderforIEEE802.16eStandard研究生:蕭志豪撰指導教授:張雲南博士中華民國九十六年七月摘要摘要摘要摘要本篇論文提出了一個適用於多碼率並且符合IEEE802.16e標準的低密度同位檢查碼(Low-DensityParity-Checkcode,LDPC)解碼器。為了支援此標準不同碼率的檢查矩陣,本篇論文提出了一個以邊序列化(edge-serial)執行的可程式化LDPC解碼器。此架構能夠根據內部一連串的更新指令執行序列化的檢查節點運算。當每個檢查節點相連的位元節點數在一定的範圍之內時,任何複雜或是非正規檢查矩陣都能適用於此架構。除了具有高度的使用彈性外,本篇論文也提出了幾個適用於LDPC解碼器的最佳化技巧。首先,在過去LDPC解碼器的相關研究都著重在檢查節點的運算。本篇論文則提出了另外一種以位元節點運算為主的執行方式,此種執行方式可以使得設計更精簡化。第二,使用一種更好、更快速的訊號更新方式,此種方式可以讓訊號收斂所需的時間縮短。除此之外,更能夠節省大約一半的訊號儲存硬體。更進一步的,當使用位元節點為主的執行方式時,可以利用提早停止機制(earlytermination)達到停止部分位元節點的運算進而減少解碼的時間。其他設計的特色還包括重新排程訊號執行的順序,使得相鄰的遞迴運算週期(iteration)可以重疊執行,避免因為內部管線化(pipeline)後的訊號延遲(latency)所可能造成的訊號更新問題。透過這些提出的最佳化方法,我們的實驗結果為硬體成本可以節省大約23.1%,解碼時間可以節省約27.4%。使用0.18µm製程合成後的邏輯閘數(gatecount)為316k。實驗的數據顯示本篇論文提出的LDPC解碼器可以達到235MHz的工作頻率,並且提供平均約116Mbps的吞吐量(Throughput)效能。AbstractThisthesispresentsanovelVLSIdesignofmulti-coderateLow-DensityParity-Checkcode(LDPC)decoderforIEEE802.16estandard.Inordertosupportthedifferentcoderatesadoptedbythestandard,thisthesisproposesaprogrammableLDPCdecoderarchitecturebasedontheedge-serialapproach.Thisedge-serialarchitecturecanperformthesequentialcheck-nodecomputationaccordingtotheinternalsequenceupdatecommands.Anycomplexandirregularparity-checkmatrixcanallberealizedintheproposedarchitectureifthenumberofbit-nodeseachchecknodeconnectsdoesnotexceedacertainbound.Inadditiontothehighflexibility,thisthesisalsoproposesseveraldesignoptimizationtechniquessuitablefortheLDPCdecoder.First,thedesignsoftheLDPCdecodersinthepastallputmoreemphasisontherealizationofchecknodefunction.Thisthesisinsteadappliesanovelbit-nodemajorapproachwhichcanleadtomorecompactdesign.Secondly,afine-grainmessageupdatemethodisusedwhichallowsmorerapidmessagepassingsuchthatthedecodercanconvergeinlesscycles.Inaddition,almosthalfofthemessagememorycanbereduced.Furthermore,basedonthebit-nodemajordecoderdesign,theearlyterminationschemecanbeutilizedtopartiallyterminatethefunctionofsomebitnodestoreducethedecodingcycles.Theothersalientfeaturesalsoincludethereschedulingofthemessageupdateordertoallowtheoverlapofdifferentdecodingiterationsinordertoreduceeffectofthepossiblemessageupdatehazardduetothelonginternalpipelinelatency.Basedontheproposedoptimizationmethods,ourexperimentalresultsshowthatthehardwarecostcanbereducedby23.1%whilethedecodingcyclescanbereducedby27.4%.TheproposedLDPCdecoderarchitecturehasbeenrealizedbyusing0.18µmtechnologywiththetotalgatecountof316k.OurexperimentalshowsthattheproposedLDPCdecodercanrunupto235MHzanddelivertheaverageof116Mbpsthroughput.目錄目錄目錄目錄第第第第1章章章章導論導論導論導論...........................................................................................................13第第第第1.1節節節節研究背景與動機研究背景與動機研究背景與動機研究背景與動機............................................................................13第第第第1.2節節節節論文組織論文組織論文組織論文組織........................................................................................14第第第第2章章章章低密度同位檢查碼低密度同位檢查碼低密度同位檢查碼低密度同位檢查碼...................................................................................16第第第第2.1節節節節低密度同位檢查碼簡介低密度同位檢查碼簡介低密度同位檢查碼簡介低密度同位檢查碼簡介................................................................16第第第第2.2節節節節低密度同位檢查碼在低密度同位檢查碼在低密度同位檢查碼在低密度同位檢查碼在IEEE802.16e標準之資訊標準之資訊標準之資訊標準之資訊.......................19第第第第3章章章章編碼方法與解碼演算法編碼方法與解碼演算法編碼方法與解碼演算法編碼方法與解碼演算法...........................................................................22第第第第3.1節節節節編碼方法簡介編碼方法簡介編碼方法簡介編碼方法簡介................................................................................22第第第第3.2節節節節常用解碼演算法簡介常用解碼演算法簡介常用解碼演算法簡介常用解碼演算法簡介....................................................................26第第第第3.2-1節節節節Sum-of-ProductAlgorithm((((SPA))))................................27第第第第3.2-2節節節節Minimum-SumAlgorithm((((MSA))))...............................27第第第第3.2-3節節節節Forward-BackwardAlgorithm((((FBA)))).........................28第第第第3.3節節節節解碼演算法錯誤率與檢查節點硬體比較解碼演算法錯誤率與檢查節點硬體比較解碼演算法錯誤率與檢查節點硬體比較解碼演算法錯誤率與檢查節點硬體比較....................................29第第第第4章章章章解碼器架構解碼器架構解碼器架構解碼器架構...............................................................................................33第第第第4.1節節節節平行化架構平行化架構平行化架構平行化架構((((ParallelArchitecture)))).........................................33第第第第4.2節節節節序列化架構序列化架構序列化架構序列化架構((((SerialArchitecture))))............................................33第第第第4.3節節節節本設計之架構本設計之架構本設計之架構本設計之架構................................................................................34第第第第4.3-1節節節節整體基本架構整體基本架構整體基本架構整體基本架構.....................................................................34第第第第4.3-2節節節節檢查矩陣相關資訊編碼檢查矩陣相關資訊編碼檢查矩陣相關資訊編碼檢查矩陣相關資訊編碼.....................................................36第第第第4.3-3節節節節移位運算架構移位運算架構移位運算架構移位運算架構.....................................................................37第第第第4.3-4節節節節檢查節點架構檢查節點架構檢查節點架構檢查節點架構.....................................................................38第第第第4.3-5節節節節位元節點架構位元節點架構位元節點架構位元節點架構......