OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 18, Iss. 22 — Oct. 25, 2010
  • pp: 23371–23377
« Show journal navigation

On the reduced-complexity of LDPC decoders for ultra-high-speed optical transmission

Ivan B. Djordjevic, Lei Xu, and Ting Wang  »View Author Affiliations


Optics Express, Vol. 18, Issue 22, pp. 23371-23377 (2010)
http://dx.doi.org/10.1364/OE.18.023371


View Full Text Article

Acrobat PDF (1023 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

We propose two reduced-complexity (RC) LDPC decoders, which can be used in combination with large-girth LDPC codes to enable ultra-high-speed serial optical transmission. We show that optimally attenuated RC min-sum sum algorithm performs only 0.46 dB (at BER of 10−9) worse than conventional sum-product algorithm, while having lower storage memory requirements and much lower latency. We further study the use of RC LDPC decoding algorithms in multilevel coded modulation with coherent detection and show that with RC decoding algorithms we can achieve the net coding gain larger than 11 dB at BERs below 10−9.

© 2010 OSA

1. Introduction

In order to reduce the complexity of SPA, a number of different approximate algorithms were proposed [2

2. I. B. Djordjevic, W. Ryan, and B. Vasic, Coding for Optical Channels (Springer, 2010).

,4

4. J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier, and X.-Y. Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun. 53(8), 1288–1299 (2005). [CrossRef]

,5

5. M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced-complexity iterative decoding of low-density parity-check codes based on belief propagation,” IEEE Trans. Commun. 47(5), 673–680 (1999). [CrossRef]

]. The main focus was to reduce the complexity of check-node (c-node) update rule. Because c-node update rule is the key step in SPA, imperfect approximations lead to significant BER performance degradation. In this paper we follow a different strategy. Instead of trying to reduce the complexity of c-node update rule, we try to reduce the complexity of variable-node (v-node) update rule. Two reduced complexity (RC) LDPC decoding algorithms are introduced: (i) RC min-sum algorithm and (ii) RC a posteriori probability (APP) algorithm. We show that even complete elimination of v-node update rule leads to only 0.46 dB degradation when large-girth LDPC codes are used. We further study the use of RC decoding algorithm in polarization multiplexed (PolMUX) 32-IPQ with symbol rate of 50 Giga symbols/s (50 GS/s) and show that that net coding gains (NCGs) beyond 11 dB (at BER ≤10−9) are possible.

The paper is organized as follows. In Section 2, we provide two RC LDPC decoding algorithms and evaluate their BER performance, decoding complexity, and memory requirements. In Section 3, we describe polarization-multiplexed IPQ scheme suitable for ultra-high-speed serial optical transmission and evaluate its performance when the proposed RC LDPC decoding algorithms are used. Concluding remarks are given in Section 4.

2. Reduced-complexity LDPC decoders

Before we fully describe the proposed RC algorithms, we introduce several definitions that will facilitate the description. A regular (n, k) LDPC code is a linear block code whose parity-check matrix H contains exactly Wc 1's per column and exactly Wr = Wc(n/(n-k)) 1’s per row, where Wc << (n-k). Decoding of LDPC codes is based on SPA, which is an iterative decoding algorithm where extrinsic probabilities are iterated forward and back between variable and check nodes of bipartite (Tanner) graph representation of a parity-check matrix H. The Tanner graph of an LDPC code is drawn according to the following rule: check node c is connected to variable node v whenever element hcv in H is a 1. For v-node v (c-node c) we define its neighborhood N(v) (N(c)) as the set of c-nodes (v-nodes) connected to it. For the completeness of presentation we briefly describe the log-domain SPA (for detailed description an interested reader is referred to [2

2. I. B. Djordjevic, W. Ryan, and B. Vasic, Coding for Optical Channels (Springer, 2010).

]).

Gallager SPA

  • 0. Initialization: For v = 0,1,…,n-1; initialize the messages Lv c to be sent from v-node v to c-node c to channel log-likelihood ratios (LLRs) L ch(v)*, namely Lv c = L ch(v).
  • 1. c-node update rule: For c = 0,1,…,n-k-1; compute Lcv=+N(c)\{v}Lvc.   The box-plus operator is defined iteratively by L1+L2=k=12sign(Lk)ϕ(k=12ϕ(|Lk|)),   ϕ(x)=logtanh(x/2). The box operator for |N(c)\{v}| components is obtained by recursively applying 2-component version defined above.
  • 2. v-node update rule: For v = 0,1,…,n-1; set Lvc=Lch(v)+N(v)\{c}Lcv for all c-nodes for which hcv = 1.
  • 3. Bit decisions: Update L(v) (v = 0,…,n-1) by L(v)=Lch(v)+N(v)Lcv and set v^=1 when L(v)<0 (otherwise, v^=0). If v^HT=0 or pre-determined number of iterations has been reached then stop, otherwise go to step 1.
    • *The channel LLR is defined by L ch(v) = log[P(v = 0|y)/P(v = 1|y)], where y is the channel sample. For example, for asymmetric AWGN channel L ch(v) = log(σ10)-(y0)2/2σ0 2 + (y1)2/2σ1 2, while for symmetric AWGN (σ1 = σ0 = σ) channel L ch(v) = 2y2, where μii) denote the mean (standard deviation) corresponding to symbol i (i = 0,1).

Reduced-complexity min-sum algorithm

  • 0. Initialization: For v = 0,1,…,n-1; initialize the v-node reliabilities Lv to channel LLRs, Lv = L ch(v).
  • 1. c-node update rule: For c = 0,1,…,n-k-1; compute Lcv=+N(c)\{v}Lv.    The box-plus operator is defined by L1+L2=αk=12sign(Lk)min(|L1|,|L2|).
  • 2. Bit decisions: Update L(v) (v = 0,…,n-1) by L(v)=Lch(v)+N(v)Lcv and set v^=1 when L(v)<0 (otherwise, v^=0). If v^HT=0 or pre-determined number of iterations has been reached then stop, otherwise go to step 1.

The second RC algorithm to be described here is based on the RC decoding algorithm proposed by Fossorier et al. [5

5. M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced-complexity iterative decoding of low-density parity-check codes based on belief propagation,” IEEE Trans. Commun. 47(5), 673–680 (1999). [CrossRef]

]. The original algorithm was applicable to AWGN channels only. Our proposed algorithm, which will be called here reduced complexity a posteriori probability (RC-APP) algorithm, is independent on channel assumption and can be formulated as follows.

Reduced complexity a posteriori probability algorithm

  • 0. Initialization: For v = 0,1,…,n-1; determine hard decisions zv = {1-sign[L ch(v)]}/2 and magnitudes m v = | L ch(v)| from channel LLRs L ch(v).
  • 1. c-node update rule: For c = 0,1,…,n-k-1; compute the magnitudes mc v to be sent from c-node c to v-node v by mcv=α(minN(c)\{v}mv), where α is the attenuation factor. Compute also zcv=(N(c)\{v}zv)mod2.
  • 2. Bit decisions: Update the v-node magnitudes mv (v = 0,…,n-1) by mv=|Lch(v)|+N(c)(12zcv)mcv and set zv = zv⊕1 for mv<0. If zHT=0 or pre-determined number of iterations has been reached then stop; otherwise go to step 1.

Note that this algorithm requires only the use of summations, comparators and mod 2 adders. The attenuations can be implemented by appropriate register shifts (e.g., 0.5 corresponds to one register shift to the right). The decoding complexity can be estimated in terms of number of required operations per single iteration. For example, the c-node update rule in RC-min-sum algorithm is dominated by number of comparators, which is (d c-2), where d c is the c-node degree. The conventional min-sum algorithm requires dv-additions (where dv is the v-node degree) in v-node update rule, while the bit-decision step requires (dv + 1) additions. Therefore, the RC-min-sum algorithm requires ndv additions less compared to conventional min-sum algorithm. The complexity of Gallager SPA is even higher since the c-node update rule requires 15(d c-2) additions per check node. To study the memory allocation requirements, we assume that partially parallel implementation is used, with bit-processing elements (BPEs) and check processing elements (CPEs) being assigned as shown in Fig. 1
Fig. 1 Assignment of v-nodes and c-nodes to BPEs and CPEs, respectively. I denotes the identity matrix of size pxp (p is a prime), P is the permutation matrix given by P = (pij)p x p, pi , i +1 = pp ,1 = 1 (zero otherwise), and r and c represent the number of block-rows and block-columns in parity-check matrix. The set of integers S are carefully chosen from the set {0,1,…,p-1} so that the cycles of short length (4 and 6) are avoided.
. In Table 1

Table 1. Memory allocation requirements of LDPC(16935, 13550) code of column-weight 3 (for p = 1129 and |S| = 15)

table-icon
View This Table
| View All Tables
, we summarize the memory allocation for quasi-cyclic LDPC(16935, 13550) code, where we use the following notation: MEM B and MEM C denote the memories used to store bit node and check node edge values; MEM E stores the codeword estimate; MEM I stores the initial LLRs, and MEM F stores final LLRs (required in bit decision step). When RC-min-sum algorithm is used, the MEM B block is not needed at all. Finally, since v-node update rule does not exist in RC-min-sum algorithm, the decoding latency will be lower. Although exact latency improvement is dependent on the implementation platform, our study indicates that proposed RC-min-sum algorithm has lower complexity compared to conventional min-sum algorithm and SPA.

3. PolMUX IPQ coded-modulation based on large-girth LDPC codes and RC decoders

The PolMUX IPQ-based coded modulation scheme suitable for beyond 400 Gb/s per wavelength optical transmission is shown in Fig. 4
Fig. 4 PolMUX PEG-LDPC-coded IPQ modulation scheme: (a) transmitter and (b) receiver configurations. MAP: maximum a posteriori probability.
. The m x + m y (index x (y) corresponds to x-(y-) polarization) independent data streams are encoded using different LDPC codes of code rates Ri = Ki/N (i∈{x,y}), where K x (K y) denotes the number of information bits used in the binary LDPC code corresponding to x- (y-) polarization, and N denotes the codeword length. The m x (m y) input bit streams from m x (m y) different information sources, pass through identical encoders that use LDPC codes with code rate R x (R y) designed using a quasi-cyclic code design [2

2. I. B. Djordjevic, W. Ryan, and B. Vasic, Coding for Optical Channels (Springer, 2010).

]. The outputs of the encoders are then bit-interleaved by an m x × N (m y × N) bit-interleaver where the sequences are written row-wise and read column-wise from a block-interleaver. The mapper maps each m x (m y) bits, taken from interleaver, into a 2mx-ary (2my-ary) IPQ signal constellation point based on the LUT, which is for M = 32 given in Table 2

Table 2. Specifications for 32-IPQ-based modulation

table-icon
View This Table
| View All Tables
(mi denotes the ith circle radius, Li denotes the number of constellation points per ith circle, ri denotes the decision regions in amplitude coordinate). The corresponding constellation diagram is shown in Fig. 5
Fig. 5 32-IPQ constellation.
, as we described in [3

3. I. B. Djordjevic, and H. G. Batshon, Lei Xu and T. Wang, “Coded polarization-multiplexed iterative polar modulation (PM-IPM) for beyond 400 Gb/s serial optical transmission,” in Proc. OFC/NFOEC 2010, Paper No. OMK2, San Diego, CA, March 21–25, 2010.

]. The IPQ mapper x (y) assigns m x (m y) bits to a constellation point represented in polar coordinates as s i ,x = |s i ,x|exp(jϕi ,x) [s i ,y = |s i ,y|exp(jϕi ,y)]. One output of IPQ mapper is used as input of amplitude modulator (AM), while the second output is used as input to phase modulator (PM), as shown in Fig. 4(a). Notice that we use (m x + m y) encoders/decoders operating in parallel at data rate of R b instead of only one encoder/decoder operating at date rate of (m x + m y)R b. At the receiver side (see Fig. 4(b)), the outputs at I- and Q-branches in two polarizations, are sampled at the symbol rate, while the symbol LLRs are calculated by λ(s) = log[P(s|r)/P(s 0|r)], where s and r denote the transmitted signal constellation point and received symbol at time instance i (in either x- or y- polarization), respectively, and s 0 represents the reference symbol. The turbo equalization (TE) principle is used to compensate for various channel impairments such as PMD, residual chromatic dispersion, and fiber nonlinearities [2

2. I. B. Djordjevic, W. Ryan, and B. Vasic, Coding for Optical Channels (Springer, 2010).

]. Since the turbo equalization is not the main topic of this paper, we assume that channel impairments are ideally compensated for. The results of simulations of PolMUX based LDPC-coded IPQ scheme with 50 GS/s in symbol rate are shown in Fig. 6
Fig. 6 BER performance of PolMUX LDPC-coded IPQ scheme. CT: correction term.
. Corresponding encoders, decoders, mappers and demappers operate at data rate of 50 Gb/s. Notice that proposed LDPC decoding schemes are independent on data rate. The aggregate data rate of this particular simulation example is obtained as 2 × 5 × 0.8 × 50 Gb/s = 400 Gb/s (the factor 2 originates from two orthogonal polarizations, the factor 5 from 5 bits carried per single 32-IPQ symbol, and the factor 0.8 from code rate). The NCG at BER of 3 × 10−9, when min-sum-with-correction-term algorithm is used, is 11.6 dB. Larger coding gains can be expected at lower BERs. The optimally attenuated min-sum algorithm performs comparable to min-sum-with-correction-term algorithm. The RC-min-sum algorithm provides the NCG of 11 dB. This RC decoding based scheme, therefore, represents an excellent candidate to be used for 400G Ethernet technologies.

4. Conclusions

In this paper, we proposed two RC LDPC decoders, suitable for use in ultra-high-speed serial optical transmission: (i) attenuated RC min-sum algorithm and (ii) RC APP algorithm. We show that optimally attenuated RC min-sum sum algorithm performs only 0.46 dB (at BER = 10−9) worse than the conventional sum-product algorithm, when used in combination with large-girth LDPC codes. The RC APP algorithm performs 0.2 dB worse than RC min-sum algorithm. The proposed algorithms simplify the implementation complexity and have lower storage memory requirements and lower latency, and can be used to support ultra-high-speed implementation. We further evaluate the proposed algorithm for use in PolMUX multilevel coded modulation with coherent detection, in combination with PolMUX 32-IPQ-based signal constellation. We show that low BERs can be achieved for medium optical SNRs, while achieving the NCG above 11 dB.

Acknowledgments

This work was supported in part by the National Science Foundation (NSF) under Grants CCF-0952711 and ECCS-0725405.

References and links

1.

R. Saunders, M. Traverso, T. Schmidt, and C. Malouin, “Economics of 100Gb/s transport,” in Proc. OFC/NFOEC 2010, Paper No. NMB2, San Diego, CA, March 21–25, 2010.

2.

I. B. Djordjevic, W. Ryan, and B. Vasic, Coding for Optical Channels (Springer, 2010).

3.

I. B. Djordjevic, and H. G. Batshon, Lei Xu and T. Wang, “Coded polarization-multiplexed iterative polar modulation (PM-IPM) for beyond 400 Gb/s serial optical transmission,” in Proc. OFC/NFOEC 2010, Paper No. OMK2, San Diego, CA, March 21–25, 2010.

4.

J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier, and X.-Y. Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun. 53(8), 1288–1299 (2005). [CrossRef]

5.

M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced-complexity iterative decoding of low-density parity-check codes based on belief propagation,” IEEE Trans. Commun. 47(5), 673–680 (1999). [CrossRef]

OCIS Codes
(060.0060) Fiber optics and optical communications : Fiber optics and optical communications
(060.1660) Fiber optics and optical communications : Coherent communications
(060.4080) Fiber optics and optical communications : Modulation

ToC Category:
Fiber Optics and Optical Communications

History
Original Manuscript: September 29, 2010
Manuscript Accepted: October 12, 2010
Published: October 20, 2010

Citation
Ivan B. Djordjevic, Lei Xu, and Ting Wang, "On the reduced-complexity of LDPC decoders for ultra-high-speed optical transmission," Opt. Express 18, 23371-23377 (2010)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-18-22-23371


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. R. Saunders, M. Traverso, T. Schmidt, and C. Malouin, “Economics of 100Gb/s transport,” in Proc. OFC/NFOEC 2010, Paper No. NMB2, San Diego, CA, March 21–25, 2010.
  2. I. B. Djordjevic, W. Ryan, and B. Vasic, Coding for Optical Channels (Springer, 2010).
  3. I. B. Djordjevic, and H. G. Batshon, Lei Xu and T. Wang, “Coded polarization-multiplexed iterative polar modulation (PM-IPM) for beyond 400 Gb/s serial optical transmission,” in Proc. OFC/NFOEC 2010, Paper No. OMK2, San Diego, CA, March 21–25, 2010.
  4. J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier, and X.-Y. Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun. 53(8), 1288–1299 (2005). [CrossRef]
  5. M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced-complexity iterative decoding of low-density parity-check codes based on belief propagation,” IEEE Trans. Commun. 47(5), 673–680 (1999). [CrossRef]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited