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

2010 届届毕业毕业生生 毕业论毕业论文文 题题 目：目： ldpcldpc 码的编译码算法研究码的编译码算法研究 院系名称：院系名称： 信息工程学院信息工程学院 专业班级：专业班级： 电子信息工程电子信息工程 学生姓名：学生姓名： 学学 号号： 指导教师：指导教师： 教师职称：教师职称： 教授教授 2010 年年 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 : %dn, 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 drjic1(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 prodofrijri(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 : %dn, 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 betaijc1(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 alphaijc1(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 : %dn, 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) + 1)/. (exp(betaij(r(l), c(l) - 1);