مجموعه هاي تله اي ظرفيت تضمين شده تصحيح خطاي كدهاي LDPC و GLDPC

چكيده انگليسي :

On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes Mahboobe Rostami m rostami@math iut ac ir January 16 2012 Master of Science Thesis Department of Mathematical Science Isfahan University of Technology Isfahan 84156 83111 IranSupervisors Dr Morteza Esmaili emorteza AT cc iut ac ir 2000 MSC 68P30Key word LDPC codes GLDPC codes trapping sets bit flipping algorithm fixed sets error correctioncapability AbstractIn this thesis some lower and upper bounds on the guaranteed error correction capability of bit flippingalgorithms for decoding low density parity check LDPC codes and generalized low density parity check GLDPC codes are studied Two classes of codes are considered first left regular LDPC codesand second left regular and right uniform GLDPC codes also known as regular GLDPC codes The sizeof variable nodes in a left regular Tanner graph which are guaranteed to expand by a factor of at least3 4 based on the Moore bound is determined By using the known relations between the expansion of aTanner graph and the error correction capability some lower bounds on the guaranteed error correctioncapability are established To find an upper bound on the number of correctable errors the size of sets ofvariable nodes which lead to decoding failures is studied A decoding failure is said to have occurred ifthe output of the decoder is not the transmitted codeword One of the factors that lead to decoding failuresfor iterative decoding on the BSC and the additive white Gaussian noise channel AWGNC is known astrapping sets So to find this upper bound we consider trapping sets and fixed sets that are a particularcase of trapping sets A class of interesting graphs known as cage graphs is defined and a relation betweencage graphs and fixed sets is established Then an upper bound on the error correction capability is givenbased on the orders of cage graphs The bounds are functions of the column weight and girth of theunderlying Tanner graph For regular GLDPC codes the parallel bit flipping decoding algorithm isstudied and the expansion factor sufficient to guarantee the correction of a linear number of errors isderived Using the same approach as in LDPC codes some lower bounds on the number of variable nodesthat are guaranteed to achieve the required expansion are derived for the case of GLDPC codes In theregular GLDPC codes some graphs similar to the cage graphs are defined An upper bound on the errorcorrection capability is given based on the orders of these graphs The bounds in the regular GLDPCcodes are functions of the column weight and girth of the underlying Tanner graph and the errorcorrection capability of the component codes Product coding technique is a method for constructing longpowerful codes from shorter ones In this thesis we show that product codes can be expressed as GLDPCcodes Because of the importance of trapping sets we determine the relation between a b trapping setsin a given product code and the a b trapping sets of its components

رستمي، محبوبه

مجموعه هاي تله اي ظرفيت تضمين شده تصحيح خطاي كدهاي LDPC و GLDPC

مجموعه هاي ثابت