Many implementations for decoding LDPC codes are based on the (normalized/offset) min-sum algorithm due to its satisfactory performance and simplicity in operations. Usually, each iteration of the min-sum algorithm contains two scans, the horizontal scan a

Single-ScanMin-SumAlgorithmsforFastDecodingofLDPCCodes

XiaofeiHuang

SchoolofInformationScienceandTechnologyTsinghuaUniversity,Beijing,P.R.China,100084

Email:huangxiaofei@ieee.org

(AcceptedbyIEEEInformationTheoryWorkshop,Chengdu,China,2006)

arXiv:cs/0609090v1 [cs.IT] 16 Sep 2006

Abstract—ManyimplementationsfordecodingLDPCcodesarebasedonthe(normalized/offset)min-sumalgorithmduetoitssatisfactoryperformanceandsimplicityinoperations.Usually,eachiterationofthemin-sumalgorithmcontainstwoscans,thehorizontalscanandtheverticalscan.Thispaperpresentsasingle-scanversionofthemin-sumalgorithmtospeedupthedecodingprocess.Itcanalsoreducememoryusageorwiringbecauseitonlyneedstheaddressingfromchecknodestovariablenodeswhiletheoriginalmin-sumalgorithmrequiresthataddressingplustheaddressingfromvariablenodestochecknodes.Tocutdownmemoryusageorwiringfurther,anotherversionofthesingle-scanmin-sumalgorithmispresentedwherethemessagesofthealgorithmarerepresentedbysinglebitvaluesinsteadofusing xedpointones.Thesoftwareimplementationhasshownthatthesingle-scanmin-sumalgorithmismorethantwiceasfastastheoriginalmin-sumalgorithm.

I.INTRODUCTION

Thesum-productalgorithm[1],[2],alsoknownasthebeliefpropagationalgorithm[3],isthemostpowerfuliter-ativesoftdecodingalgorithmforLDPC(lowdensityparitycheck)codes[4],[5],[6].Thenormalized/offsetmin-sumalgorithm[7],[8],[9],[10]hasdemonstratedin[9],[10]asagoodapproximationtothesum-productalgorithm.Itisaparallel,iterativesoftdecodingalgorithmforLDPCcodes.Itissimplerincomputationthanthesum-productalgorithmbecauseitusesonlyminimizationandsummationoperationsinsteadofmultiplicationandsummationoperationsusedbythelatter.Itisalsosimplerincomputationthanthesum-productalgorithminthelogdomainbecausethelatterusesnon-linearfunctions.Forhardware/softwareimplementations,multiplicationoperationsandnon-linearfunctionsare,ingeneral,moreexpensivethanminimizationandsummationoperations.

Despiteofitsreducedcomplexity,wefoundout,inimple-mentingthenormalized/offsetmin-sumalgorithmforChina’sHDTV,thatthemin-sumalgorithmisstillexpensiveforhard-ware/softwareimplementationssincetwoscansarerequiredbythealgorithmateachiteration,anditsconvergencerateisgenerallynotsatisfactory.Themin-sumalgorithmisalsonotmemoryef cient.Thetemporaryresultsofthealgorithmarestoredinmemoryas xedpointvalues.Thenumberofvaluesisproportionaltothenumberofnon-zeroelementsoftheparitycheckmatrixofaLDPCcode.Theyrequirelarge

circuitareasbecausethenumberofnonzeroelementsisnotsmallinpractice.Manipulatingthosevaluesalsotakesalotofsystemtimeandconsumesmuchofsystempoweratrun-time.Weconcludedthatfurthersimpli cationofthemin-sumalgorithmisneededtosuittheeverdemandingrequirementsofthenextgenerationcommunicationsystems.

Thispaperpresentstwosimpli edversionsofthemin-sumalgorithmtoincreaseitsdecodingspeedandreducetherequirementonmemoryusage.Thosesimpli cationsarebasedonseveralobviousobservationswithsomeofthemalreadymentionedbyotherresearcher[12].However,nodetailhasbeenofferedinthepreviousliteratureintheformofalgorithmswhichcanbedirectlyusedbyengineersandpractitionersinthecommunicationarea.Furthermore,theadvantageofthesimpli cationsisnotneglectablebecausethesimpli edmin-sumalgorithmmorethandoublesthedecodingspeedofthestandardmin-sumalgorithminoursoftwareimplementation(inClanguage)fordecodingthequasi-cyclicirregularLDPCcodesusedforChina’sHDTV,theirregularLDPCcodesusedforEuropeandigitalvideobroadcastingusingsatellites(DVB-S2),andtheregular/irregularLDPCcodesfromDr.MacKay’swebsite.Thecomparisonisfairbecausebothalgorithmsaresimpleinoperationsandcanbeimplementedinsoftwareinastraightforwardwaywithoutmuchroomforfurtherimprove-ment.OurHDTVresearchgroupatTsinghuaUniversityhasbene tedfromthesimpli cationsbecausewemostoftenusesoftwaresimulations rsttotesttheperformanceofdifferentLDPCcodesforChina’sHDTVwhichcouldbeverytime-consumingandmaytakehoursorevendaysrunningonfastIntel-baseddesktopcomputers.

II.DEFINITIONS

ANDNOTATIONS

LDPCcodesbelongtoaspecialclassoflinearblockcodeswhoseparitycheckmatrixHhasalowdensityofones.LDPCcodeswereoriginallyintroducedbyGallagerinhisthesis[4].Afterthediscoveryofturbocodesin1993byBerrouetal.[11],LDPCcodeswererediscoveredbyMackayandNeal[5]in1995.BothclasseshaveexcellentperformancesintermsoferrorcorrectionclosetotheShannonlimit.ForabinaryLDPCcode,Hisabinarymatrixwithelements,denotedashmnin{0,1}.LetthecodewordlengthbeN,thenHisaM×Nmatrix,whereMisthenumberofrows.