Construction of LDPC codes over GF(q) with modified progressive edge growth

  • 格式:pdf
  • 大小:226.09 KB
  • 文档页数:5

October 2009, 16(5): 103–106 www.sciencedirect.com/science/journal/10058885 www.buptjournal.cn/xben

The Journal of China Universities of Posts and Telecommunications

Construction of LDPC codes over GF(q) with modified progressive edge growth

CHEN Xin (󰀍), MEN Ai-dong, YANG Bo, QUAN Zi-yi School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China Abstract A parity check matrix construction method for constructing a low-density parity-check (LDPC) codes over GF(q) (q>2) based on the modified progressive edge growth (PEG) algorithm is introduced. First, the nonzero locations of the parity check matrix are selected using the PEG algorithm. Then the nonzero elements are defined by avoiding the definition of subcode. A proof is given to show the good minimum distance property of constructed GF(q)-LDPC codes. Simulations are also presented to illustrate the good error performance of the designed codes.

Keywords LDPC codes over GF(q), progressive edge growth, large minimum distance

1 Introduction󰀃Binary LDPC [1] codes have displayed near Shannon limit performance when decoded using the belief propagation algorithm [2]. Davey and MacKay have investigated LDPC codes on finite fields GF(q) when 2q! in Ref. [3]. The

results indicate that system performance is improved with the increase of q when the proper design of parity check matrix on GF(q)-LDPC codes is conducted. It has been shown in Ref. [3] that as q becomes large the best performances at finite length are obtained for ‘ultra-sparse’ LDPC codes, that is, with the minimum connectivity on the symbol nodes 2vd . For GF(q)-LDPC codes, the optimization problem is

generally solved in a disjoint manner. First, the positions of the nonzero entries of the parity check matrix H associated with the nonbinary code are optimized to achieve good girth properties and minimize the impact of cycles on the belief propagation (BP) decoding algorithm. Then the nonzero entries can be selected either randomly from a uniform distribution among nonzero elements of GF(q) [4] or carefully to meet design criteria as done in Refs. [5–6]. In Ref. [7], the author proposed a method to select nonzero elements so that the determinants of the partial matrices corresponding to the

Received date: 09-12-2008 Corresponding author: CHEN Xin, E-mail: c-xin@163.com DOI: 10.1016/S1005-8885(08)60275-7

cycles in the parity check matrix did not become zero. The author declared that the nonbinary parity check matrixes constructed in that way were able to give large-weight codewords, whereas no proof was given to show the good property of the codes. In this article, a proof is presented on why the design criteria presented in Ref. [7] can construct a nonbinary LDPC codes with good distance property. A proposition is presented to show the good minimum distance property of the constructed codes. Also, a combined method is proposed to construct GF(q)-LDPC codes using the design criteria introduced in Ref. [7] and the PEG algorithm described in Ref. [4]. The remainder of this article is organized as follows. Sect. 2 provides a proof of good minimum distance property of GF(q)-LDPC codes constructed using the design criteria proposed in Ref. [7]. Sect. 3 gives a combined algorithm for constructing GF(q)-LDPC codes with the modified PEG algorithm. Sect. 4 presents the performance comparison of the codes by different construction methods. Finally, concluding remarks are given in Sect. 5.

2 Minimum distance problem of (2, dc) GF(q)-LDPC codes

An LDPC code of code rate R and code length N is defined 104 The Journal of China Universities of Posts and Telecommunications 2009 by an M row and N column parity check matrix H. This LDPC code is called a GF(q)-LDPC code when each element

,ijh of H is selected from Galois field GF(q), with

2pq

andq as the order of the field. A row vector c of length N is a codeword if 0Hc. A regular (,)vcdd

LDPC codes have

constant column weight vd and row weight cd.

2.1 Cycles and subcode LetLH be the block matrix representation of a cycle of length2L extracted from parity check matrix H through

row and column transformation. Then, the parity check H

can be represented as:

12340LXXXXªº «»¬¼HH

The sub-matrix LH is given by the following

LLu

block square matrix: 1,11,22,22,3

1,11,,1,

000000LLLLLLLLaaaa

aaaa󰀐󰀐󰀐

ªº«»«»«» «»«»«»¬¼

H"##"A vector >@sub 00cc satisfying Eq. (1) is a codeword