本科毕业论文：LDPC码的编译码算法研究.doc

毕业论文毕业论文 题题 目 目 LDPCLDPC 码的编译码算法研究码的编译码算法研究 院系名称 院系名称 信息工程学院信息工程学院 专业班级 专业班级 电子信息工程电子信息工程 学生姓名 学生姓名 学学 号号 指导教师 指导教师 教师职称 教师职称 教授教授 201 年年 6 月月 2 日日 II 摘摘 要要 低密度奇偶校验码 Low Density Parity Check Codes 简称 LDPC 码 本 质上是一种线性分组码 更接近香农限 目前的研究均表明 LDPC 码是信道编 码中纠错能力最强的一种码 其译码器结构简单 在深空探测 卫星通信等领域可 得到广泛的应用 文章介绍了 LDPC 码 综述了其编码方法和译码方法 在编码 方法中分别描述了校验矩阵的构造和基于校验矩阵的编码算法 对 LDPC 码的 快速编码方法进行分析 在译码方法中主要论述了消息传递译码算法 置信传 播译码方法 最小和译码算法 比特翻转译码算法和加权比特翻转译码方法 对部分 LDPC 码的编译码就行了仿真 同时对 LDPC 码的编译码方法的发展及 应用前景作了分析 本文的重点是对 LDPC 码的编译码算法的论述与研究 介绍 LDPC 码的基 本原理和分类 分别从基于生成矩阵和基于校验矩阵详细讨论了 LDPC 码编码 算法 简单介绍了线性分组码编码 LU 分解法 RU 分解法 并用简明例子对 RU 算法做了清晰的解释 对译码大致做了解释 分为软判决译码 MP 算法 和硬判决译码 比特翻转算法和加权比特翻转算法 在本文的最后用 AWGN 信道下 LDPC 码的性能仿真 主要是针对比特翻转算法进行仿真 做出理论比 较 关键词关键词 LDPC 码 编译码 MATLAB III Title Encoding and Decoding Algorithms of LDPC Codes Abstract LDPC code namely Low Density Parity Check Code is a kind of linear block codes in nature and the decoding performance of LDPC is more nearer to the Shannon limit With it s best performance and simple decoder structure LDPC codes will be widely used in deep space exploration satellite communications and other fields While briefly introducing LDPC codes are introduced briefly this paper summarizes the encoding and decoding algorithms The encoding algorithm is described in two steps the const ruction of parity check matrix and the encoding method based on parity check matrix Analyze the rapidly coding method for LDPC code As to decoding algorithm MP decoding method BP decoding method Min Sum decoding method Bit Flipping method and Weighted Bit Flipping method are discussed Emulate for the LDPC codes The development and application of encoding and decoding methods is analyzed as well This article focuses on encoding and decoding algorithms of LDPC codes According to the different methods of decoding algorithm and makes the theoretical MATLAB simulation Key words LDPC codes encoding and decoding MATLAB IV IV 目 录 1引言 1 2 LDPC 码概述 3 2 1 线性分组码 3 2 2 低密度奇偶校验码 LDPC 码 4 2 2 1 LDPC 码定义 4 3 LDPC 码的编码算法 6 3 1 基于生成矩阵的编码算法 线性分组码编码 6 3 2 基于校验矩阵的编码算法 LU 分解法 7 3 3 基于校验矩阵的编码算法 RU 算法 7 4 LDPC 码的译码概述 11 4 1 MP 算法集 11 4 2 硬判决译码算法 13 4 2 1 比特翻转算法 13 4 2 2 加权比特翻转译码算法 14 5 AWGN 信道下 LDPC 码的性能仿真 15 5 1 仿真软件简介 MATLAB end else for cc 1 lc 1 H i c1 cc 0 end end if end if end for j end for i end if fprintf LDPC matrix is created n function c newH makeParityChk dSource H strategy Generate parity check vector bases on LDPC matrix H using sparse LU decomposition dSource Binary source 0 1 H LDPC matrix strategy Strategy for finding the next non zero diagonal elements 0 First First non zero found by column search 27 1 Mincol Minimum number of non zeros in later columns 2 Minprod Minimum product of Number of non zeros its column minus 1 Number of non zeros its row minus 1 c Check bits Copyright Bagawan S Nugroho 2007 Get the matric dimension M N size H Set a new matrix F for LU decomposition F H LU matrices L zeros M N M U zeros M N M Re order the M x N M submatrix for i 1 M strategy 0 First 1 Mincol 2 Minprod switch strategy Create diagonally structured matrix using First strategy case 0 Find non zero elements 1s for the diagonal r c find F i end Find non zero diagonal element candidates rowIndex find r i Find the first non zero column chosenCol c rowIndex 1 i 1 Create diagonally structured matrix using Mincol strategy case 1 Find non zero elements 1s for the diagonal r c find F i end colWeight sum F i end 1 Find non zero diagonal element candidates rowIndex find r i Find the minimum column weight x ix min colWeight c rowIndex Add offset to the chosen row index to match the dimension of the original matrix F chosenCol c rowIndex ix i 1 Create diagonally structured matrix using Minprod strategy case 2 Find non zero elements 1s for the diagonal 28 r c find F i end colWeight sum F i end 1 1 rowWeight sum F i 2 1 Find non zero diagonal element candidates rowIndex find r i Find the minimum product x ix min colWeight c rowIndex rowWeight Add offset to the chosen row index to match the dimension of the original matrix F chosenCol c rowIndex ix i 1 otherwise fprintf Please select columns re ordering strategy n end switch Re ordering columns of both H and F tmp1 F i tmp2 H i F i F chosenCol H i H chosenCol F chosenCol tmp1 H chosenCol tmp2 Fill the LU matrices column by column L i end i F i end i U 1 i i F 1 i i There will be no rows operation at the last row if i length r1 numOfOnes rji r1 k j qij r1 k j 1 else qij r1 k j 0 30 end end for k Bit decoding if numOfOnes ci j length r1 numOfOnes vHat j 1 else vHat j 0 end end for j end for n function vHat decodeProbDomain rx H N0 iteration Probability domain sum product algorithm LDPC decoder rx Received signal vector column vector H LDPC matrix N0 Noise variance iteration Number of iteration vHat Decoded vector 0 1 Copyright Bagawan S Nugroho 2007 M N size H Prior probabilities P1 ones size rx 1 exp 2 rx N0 2 P0 1 P1 Initialization K0 zeros M N K1 zeros M N rji0 zeros M N rji1 zeros M N qij0 H repmat P0 M 1 qij1 H repmat P1 M 1 Iteration for n 1 iteration fprintf Iteration d n n Horizontal step for i 1 M Find non zeros in the column c1 find H i for k 1 length c1 31 Get column products of drji c1 l drji 1 for l 1 length c1 if l k drji drji qij0 i c1 l qij1 i c1 l end end for l rji0 i c1 k 1 drji 2 rji1 i c1 k 1 drji 2 end for k end for i Vertical step for j 1 N Find non zeros in the row r1 find H j for k 1 length r1 Get row products of prodOfrij ri l prodOfrij0 1 prodOfrij1 1 for l 1 length r1 if l k prodOfrij0 prodOfrij0 rji0 r1 l j prodOfrij1 prodOfrij1 rji1 r1 l j end end for l Update constants K0 r1 k j P0 j prodOfrij0 K1 r1 k j P1 j prodOfrij1 Update qij0 and qij1 qij0 r1 k j K0 r1 k j K0 r1 k j K1 r1 k j qij1 r1 k j K1 r1 k j K0 r1 k j K1 r1 k j end for k Update constants Ki0 P0 j prod rji0 r1 j Ki1 P1 j prod rji1 r1 j Get Qj Qi0 Ki0 Ki0 Ki1 Qi1 Ki1 Ki0 Ki1 Decode Qj if Qi1 Qi0 vHat j 1 else vHat j 0 end 32 end for j end for n function vHat decodeLogDomainSimple rx H iteration Simplified log domain sum product algorithm LDPC decoder rx Received signal vector column vector H LDPC matrix iteration Number of iteration vHat Decoded vector 0 1 Copyright Bagawan S Nugroho 2007 M N size H Prior log likelihood simplified Minus sign is used for 0 1 to 1 1 mapping Lci rx Initialization Lrji zeros M N Pibetaij zeros M N Asscociate the L ci matrix with non zero elements of H Lqij H repmat Lci M 1 for n 1 iteration fprintf Iteration d n n Get the sign and magnitude of L qij alphaij sign Lqij betaij abs Lqij Horizontal step for i 1 M Find non zeros in the column c1 find H i Get the minimum of betaij for k 1 length c1 Minimum of betaij c1 k minOfbetaij realmax for l 1 length c1 if l k if betaij i c1 l minOfbetaij minOfbetaij betaij i c1 l end 33 end end for l Multiplication alphaij c1 k use since alphaij are 1 1s prodOfalphaij prod alphaij i c1 alphaij i c1 k Update L rji Lrji i c1 k prodOfalphaij minOfbetaij end for k end for i Vertical step for j 1 N Find non zero in the row r1 find H j for k 1 length r1 Update L qij by summation of L rij r1 k Lqij r1 k j Lci j sum Lrji r1 j Lrji r1 k j end for k Get L Qij LQi Lci j sum Lrji r1 j Decode L Qi if LQi 0 vHat j 1 else vHat j 0 end end for j end for n function vHat decodeLogDomain rx H N0 iteration Log domain sum product algorithm LDPC decoder rx Received signal vector column vector H LDPC matrix N0 Noise variance iteration Number of iteration vHat Decoded vector 0 1 Copyright Bagawan S Nugroho 2007 M N size H 34 Prior log likelihood Minus sign is used for 0 1 to 1 1 mapping Lci 4 rx N0 Initialization Lrji zeros M N Pibetaij zeros M N Asscociate the L ci matrix with non zero elements of H Lqij H repmat Lci M 1 Get non zero elements r c find H Iteration for n 1 iteration fprintf Iteration d n n Get the sign and magnitude of L qij alphaij sign Lqij betaij abs Lqij for l 1 length r Pibetaij r l c l log exp betaij r l c l