Iterative Decoding
`
`Thesis by
`
`Jung-Fu Cheng
`
`In Partial Fulfillment of the Requirements
`
`for the Degree of
`
`Doctor of Philosophy
`
`California Institute of Technology
`
`Pasadena, California
`
`1997
`
`(Submitted March 7, 1997)
`
`Page 1 of 112
`
`SAMSUNG EXHIBIT 1012
`
`

`

`ii
`
`@ 1997
`
`Jung-Fu Cheng
`
`All Rights Reserved
`
`Page 2 of 112
`
`

`

`iii
`
`Abstract
`
`Though coding theory suggests long error correcting codes chosen at random perform
`
`close to the optimum, the problem of designing good codes has traditionally been
`
`attacked by developing codes with a lot of structure, which lends itself to feasible
`
`decoders. The challenge to find practical decoders for long random codes has not
`
`been seriously considered until the recent introduction of turbo codes in 1993. This
`
`methodology of multi-stage iterative decoding with exchange of soft information, ap(cid:173)
`
`plied to codes with pseudo-random structure, has provided a whole new approach to
`
`construct good codes and to decode them with low complexity. This thesis examines
`
`the theoretical ground as well as the design and implementation details of these iter(cid:173)
`
`ative decoding techniques. The methodology is first applied to parallel concatenated
`
`unit-memory convolutional codes and generalized concatenated convolutional codes
`
`to demonstrate its power and the general design principle. We then show that, by
`
`representing these coding systems with appropriate Bayesian belief networks, all the
`
`ad hoc algorithms can be derived from a general statistical inference belief propaga(cid:173)
`
`tion algorithm. A class of new binary codes based on low-density generator matrices
`
`is proposed to eliminate the arbitrariness and unnecessary constraints in turbo cod(cid:173)
`
`ing we have recognized from this Bayesian network viewpoint. Contrary to the turbo
`
`decoding paradigm where sequential processing is accomplished by very powerful cen(cid:173)
`
`tral units, the decoding algorithm for the new code is highly parallel and distributive.
`
`We also apply these codes to M-ary modulations using multilevel coding techniques
`
`to achieve higher spectral efficiency. In all cases, we have constructed systems with
`
`flexible error protection capability and performance within 1 dB of the channel ca(cid:173)
`
`pacity.
`
`Page 3 of 112
`
`

`

`IV
`
`Acknowledgements
`
`It is impossible to express in words of any length my gratefulness and appreciation to
`
`my advisor Professor Robert J. McEliece, who offered me an unparalleled opportunity
`
`to study at Caltech and spent numerous hours with me for my research. Working
`
`with him is a true privilege, and I have benefited tremendously from his knowledge
`
`of science, both in depth and broadness, and his enthusiasm of doing research. While
`
`being a constant source of valuable insights and advice, he has always allowed me
`
`high degree of freedom and independence to pursue my own research and study. It
`
`was, however, his unlimited encouragement, patience, and availability that kept me
`
`focused and made all the accomplishments in this thesis possible.
`
`My special thanks go to Prof. Dariush Divsalar, who has been given me invalu(cid:173)
`
`able suggestions and comments on my research. I am also grateful to Prof. Andrea
`
`Goldsmith, Prof. Aron Kiely, Prof. P. P. Vaidyanathan, Prof. Marvin Simon, and
`
`Prof. Mani Chandy for their interest in my work, their helpful comments, and their
`
`precious time serving on my candidacy/ defense examinations committees. I have also
`
`learned immensely from many state-of-the-art classes given by them.
`
`I would like to thank my friends, especially James Tong and Masayuki Hattori, for
`
`their friendship and encouragement for me. Without them, life at Caltech would have
`
`been very difficult. I am grateful to my colleagues, Zhong Yu, Mohamed-Slim Alouini,
`
`Wei Lin, Gavin Horn, and Srinivas Aji for many fruitful discussions I had with them.
`
`I thank Lilian Porter, our secretary, for her professional help for my administrative
`
`obligations and for her care and kindness toward me. Robert Freeman, our system
`
`administrator, who devoted great amount of time to maintain the computers, has
`
`been an indispensable resource for my work.
`
`Above all, I would like to express my greatest gratitude to my family: my mother
`
`Yumei, my brother Chung-Hong, my cousin Mulan, and my newly-wedded wife Kay.
`
`( I wish I could share this delightful moment with my father, who had passed months
`
`Page 4 of 112
`
`

`

`before I came to Caltech.) They supported me in every aspect of my life and encour(cid:173)
`aged me every step of the way. They enriched both my life and my dreams.
`
`V
`
`Page 5 of 112
`
`

`

`vi
`
`Contents
`
`Abstract
`
`Acknowledgements
`
`List of Figures
`
`1 Introduction
`
`1.1 Error Correcting Codes for Digital Communications
`
`1.2 Thesis Outline. . . . . . . . . . . . . . . . . . . . .
`
`2 Unit Memory Hamming Turbo Codes
`
`2.1 Encoder
`
`. . . . . . .
`
`2.2 Decoding Algorithm
`
`2.2.1 MAP Algorithm for Multi-Input Recursive Trellis Codes
`
`2.2.2 Extrinsic Information .
`
`2.2.3 Turbo Decoding .
`
`2.3 Simulation Results
`
`2.4 Conclusions
`
`. . . .
`
`2.A Symbol MAP Algorithm for Multi-Input Recursive Trellis Codes
`
`3 Generalized Concatenated Convolutional Codes
`
`3.1
`
`Introduction . . . . . . . . . . . . . . . . . . . . .
`
`3.2 Generalized Concatenated Convolutional Codes of the Plotkin Type
`
`3.2.1 Hard-Decision Decoding
`
`3.2.2 Performance Bounds
`
`3.2.3 Numerical Results
`
`.
`
`3.3 Clipped Soft-Decision Decoding Algorithm
`
`iii
`
`iv
`
`ix
`
`1
`
`2
`
`4
`
`8
`
`9
`
`12
`
`12
`
`16
`
`17
`
`18
`
`20
`
`21
`
`23
`
`24
`
`26
`
`27
`
`29
`
`30
`
`31
`
`Page 6 of 112
`
`

`

`vii
`
`3.3.1
`
`Performance Bounds
`
`3.3.2
`
`Numerical Results
`
`3.3.3
`
`Iterative Decoding
`
`3.4 Generalized Concatenated Convolutional Codes of the Convolutional
`Type
`
`3.4.1
`
`General Construction .
`
`3.4.2
`
`Systematic Recursive Construction
`
`3.5 Conclusions
`
`. . . . . . . . . . . . . . . .
`
`4 Turbo Decoding and Belief Propagation
`
`4.1
`
`Introduction to Bayesian Networks and Belief Propagation
`
`4.1.1 Probabilistic Inference and Bayesian Networks
`
`4.1.2 Pearl's Belief Propagation Algorithm
`
`4.2 General Optimal Symbol Decision Rules
`
`4.2.1 Conventional Systematic Codes
`
`4.2.2 General Turbo Codes . . . . . .
`
`4.3 Turbo Decoding Is Belief Propagation .
`
`4.3.1 The Turbo Decoding Algorithm
`
`4.3.2 Turbo Decoding as an Instance of Belief Propagation
`
`4.4 Concluding Remarks
`
`. . . . . . . . . . . . . . . . . . . . . .
`
`5 Low-Density Generator Matrix Codes
`
`5.1
`
`Introduction and Construction .
`
`5.2 Decoding Algorithm
`
`. . . . . .
`
`5.2.1 Fourier Transform Techniques for Belief Propagation
`5.2.2 Further Tricks to Speed Up the Algorithm
`
`5.2.3 Decoding Algorithm for LDGM Codes
`
`5.2.4 Comments about the Algorithm
`
`5.3 Simulation Results
`
`5.4 Conclusions
`
`. . . .
`
`33
`
`36
`
`39
`
`39
`
`39
`
`43
`
`46
`
`48
`
`49
`
`49
`
`52
`
`54
`
`54
`
`58
`
`59
`
`60
`
`61
`
`63
`
`65
`
`66
`
`68
`
`70
`
`71
`
`72
`
`73
`74
`
`79
`
`Page 7 of 112
`
`

`

`6 Efficient Multilevel Coded Modulations
`
`6.1 Multilevel Coding Based on Partitioning
`
`viii
`
`6.1.1 Subset Partitioning
`
`6.1.2 Multilevel Codes
`
`.
`
`6.1.3 Equivalent Channel Capacity
`
`6.2 Multilevel Coding and Multistage Decoding with LDGM Codes
`
`6.2.1 Multistage Decoding
`
`. . . . . . . . . .
`
`6.2.2 Belief Propagation Decoding Revisited
`
`6.3 Partitioning Rules for Multilevel Coding
`
`. . .
`
`6.3.1 Partitioning by Ungerboeck's Criterion
`
`6.3.2 Other Partitioning Criteria . . . . . . .
`
`6.3.3 Application: Unequal Error Protection Using One Code.
`
`6.4 Conclusions
`
`7 Conclusions
`
`Bibliography
`
`80
`
`81
`
`81
`
`82
`
`83
`
`85
`
`85
`
`86
`
`87
`
`88
`
`89
`
`91
`
`92
`
`93
`
`95
`
`Page 8 of 112
`
`

`

`IX
`
`List of Figures
`
`1.1 Digital communication system.
`
`1.2 The structure of the (7,4) Hamming Code.
`
`2.1 Encoder of the recursive partial unit-memory Hamming code (additions
`
`are performed in the vertical direction only.)
`
`2.2 The encoders of rate 1/4 and 1/3 turbo codes.
`
`2.3 Trellis termination circuit.
`
`. . . . . . . . . . .
`
`2.4 The weight distributions of (80, 16) SIT and UMT codes.
`
`2.5 The variables involved in the MAP algorithm.
`2.6 Turbo decoder for (3(K + 4) + 4, K) codes ...
`2. 7 Performance of the (1552, 512) unit-memory turbo code.
`
`2.8 Performance of several turbo codes, code rates ~ 1/3.
`
`3.1 Superimposed code encoder and channel model.
`
`3.2 Block diagram of the generic decoder . . . . . . .
`
`3.3 Bit error performance of ECl with hard decision decoding ( overall code
`
`rate is 0.5).
`. . . . . . . . . . . . . . . . . . . . . .
`3.4 The input-output relationship of ti = COM(xi, ai)- .
`3.5 The integration regions for computing the cumulative conditional prob-
`
`ability density function of ui . ....
`
`3.6 The conditional pdf fu(uiJai = +1).
`
`3.7 The SNR at the output of COM(xi, ai)- .
`3.8 The conditional pdf fv(viJbi = +l). ...
`3.9 Bit error performance of ECl with soft decision decoding ( overall code
`
`2
`
`3
`
`10
`
`10
`
`11
`
`11
`
`13
`
`18
`
`19
`
`20
`
`27
`
`28
`
`30
`
`33
`
`33
`
`34
`
`35
`
`36
`
`rate is 0.5).
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`37
`
`3.10 Bit error performance of EC2 with soft decision decoding ( overall code
`
`rate is 0.567).
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`38
`
`Page 9 of 112
`
`

`

`3.11 Hyperimposed code encoder ..
`
`X
`
`3.12 Bit error rates of hyperimposed codes and a turbo code with SOVA
`
`(overall code rate is 0.5).
`
`3.13 CC-SCT code encoder. .
`
`3.14 Bit error rates of systematic hyperimposed codes and turbo codes with
`
`SOVA . . . . . . . . . . . . . . . . . .
`
`4.1 Example of a directed acyclic graph.
`
`4.2 The local environment of a vertex V.
`
`4.3 The messages in Pearl's belief propagation algorithm.
`
`40
`
`42
`
`43
`
`46
`
`50
`
`51
`
`52
`
`4.4 System model and the corresponding Bayesian network representation
`
`of a systematic code.
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`55
`
`4.5 System model and the corresponding Bayesian network representation
`
`of a general turbo code.
`
`4.6 Turbo decoding modules. .
`
`4. 7 Belief network for a multiple turbo code with M parallel components.
`
`5.1 Expanded belief network representation of a turbo code.
`
`5.2 A random regular bipartite belief network.
`
`. . . .
`
`5.3 Bayesian network for the error-correcting system.
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`5.4 Performances of the (1536, 1024) systematic random linear codes with
`X = 6 and X = 7.
`5.5 Performances of the (1536, 1024) systematic random linear codes with
`x = 3, 4, 5, 6, 7, and 8 after 16 iterations.
`5.6 Performances of (1024/ R, 1024) systematic random linear codes after
`
`. . . . . . . . . . . . . . . .
`
`16 iterations.
`
`. . . . . . . . . . . . . . .
`
`(Marks for specific coding
`5. 7 Spectral efficiency comparison of codes.
`systems are based on the code rates and the required Eb/ N 0 for BER =
`10-5
`
`59
`
`60
`
`64
`
`66
`
`66
`
`68
`
`75
`
`76
`
`77
`
`78
`
`.)
`
`•
`
`.
`
`.
`
`.
`
`.
`
`• •
`
`.
`
`•
`
`.
`
`•
`
`.
`
`• •
`
`.
`
`.
`
`•
`
`.
`
`.
`
`.
`
`.
`
`.
`
`•
`
`.
`
`• •
`
`.
`
`.
`
`.
`
`•
`
`.
`
`. • • •
`
`Page 10 of 112
`
`

`

`xi
`
`81
`
`82
`
`6.1 Partitioning of 8PSK by the maximum intra-set distance (Ungerboeck)
`criterion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`6.2 Encoding structure for multilevel coded modulation. (E1 is the encoder
`for code C1, l = 0, l, ... , L.)
`. . . . . . . . . . . . . . . . . . . . . . .
`6.3 Capacities of 8PSK partitioned by the maximum intra-set distance
`(Ungerboeck) criterion. (A) Capacities of the subsets. (B) Capacities
`of individual partition levels. . . . . . . . . . . . . . . . . . . . . . . .
`6.4 Multistage decoder for multilevel coded modulation. (D1 is the decoder
`for code C1, l = 0, l, ... , L, and B denotes for buffers.)
`. . . . . . . .
`86
`6.5 Performances of coded 8PSKs with frequency efficiencies · 2.5 bits/symbol.
`(Channel capacity is at Eb/No...:.. 4.7 dB.). . . . . . . . .
`
`84
`
`88
`
`6.6 Partitioning of 8AMPM by the most separable criterion.
`
`6.7 Capacities of 8AMPM partitioned by the most separable criterion. (A)
`Capacities of the subsets. (B) Capacities of individual partition levels.
`6.8 Partitioning of 8AMPM by the mixed criterion.
`
`. . . . . . . . . . . .
`6.9 Capacities of 8AMPM partitioned by the mixed criterion. (A) Capac-
`ities of the subsets. (B) Capacities of individual partition levels.
`. . .
`6.10 Performances of the three coding levels in a coded 8AMPM for un(cid:173)
`equal error protection. In each of the plots, the curves correspond
`to the BERs after 1st, 2nd, 4th, 8th, and 16th iterations of decod-
`ing. (Frequency efficiency is 2 bits/symbol and channel capacity is at
`Eb/No . 2.4 dB.)
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`89
`
`90
`
`90
`
`91
`
`92
`
`Page 11 of 112
`
`

`

`1
`
`Chapter 1
`
`Introduction
`
`With the advance of digital logic design, the last decade has observed wide application
`
`and deployment of digital communication and error protection techniques. These sys(cid:173)
`
`tems have enabled, and induced explosive demands for, high-quality and high-speed
`
`voice-band modems, digital subscriber loops, personal wireless communications, mo(cid:173)
`
`bile and direct-broadcast satellite communications. To achieve efficient use of band(cid:173)
`
`width and power and, at the same time, combat against adverse channel conditions,
`
`new engineering challenges have arisen. For example, the systems should have low
`
`physical and computational complexity to increase portability and reachability, allow
`
`seamless data rate changes to cope with time-varying channel conditions and higher
`
`level network protocols, and provide unequal error protection to accommodate differ(cid:173)
`
`ent service rates and to differentiate bits of nonuniform importance from advanced
`
`source encoders. In this thesis, new high-performance error correcting techniques
`
`with low system complexity are developed to address these new challenges.
`
`Page 12 of 112
`
`

`

`2
`1.1 Error Correcting Codes for Digital Communi-
`
`cations
`
`The basic structure of a digital communication system [63, 70] is illustrated in Fig. 1.1.
`
`The function of the modulator is to convert a digital sequence into signals that are
`
`compatible with the characteristics of the channel. The channel, however, is unre(cid:173)
`
`liable and, hence, the demodulator is usually unable to reproduce the input to the
`
`modulator exactly. One way to increase the reliability of the system is to introduce
`
`some structure into the information sequence by adding redundant bits [46, 51, 52].
`
`This process ( encoding) is furnished by the encoder and the new digital sequence
`
`is termed a codeword. The collection of all the digital sequences is called an error
`
`correcting code. Because of the structure introduced, the decoder is able to infer the
`
`original information from the demodulator output with high probability, despite the
`
`corruption from the channel. In fact, it was shown by Shannon that, by operating on
`
`very long sequences of data with rates below the "capacity" of the channel, which is
`
`defined as the theoretical limit performance limit, the encoder and decoder are able
`
`to achieve error-free communication [23, 52, 68, 75].
`
`These ideas are best illustrated by an example: the classic (7,4) Hamming code.
`
`The encoder takes four bits of input, (u 1,u2 ,u3 ,u4 ), and outputs three redundant
`
`parity bits (p 1 ,p2 ,p3 ) according to:
`
`__ u __ / Encoder / c > Modulator
`
`s
`
`-e:~u-~ ____,, Decoder I e: x
`
`/~D-em-o-du-la-ro~
`
`Figure 1.1 Digital communication system.
`
`Page 13 of 112
`
`

`

`3
`
`P2 = U1 EB U3 EB U4,
`
`p3 = Uz EB U3 EB U4.
`
`The structure thus imposed on the codeword can be illustrated as the diagram in
`
`Fig. 1.2: a valid codeword will have even number of ones (even parity) in each circle.
`
`As claimed before, this will enable us to correct some errors that occurred during the
`
`transmission of these bits. For example, suppose there is only one bit whose value
`
`was changed because of the noisy channel. There are three cases to be considered:
`
`1. If only one circle has odd parity, then it is the parity bit of the circle that was
`
`changed. The information bits are intact.
`
`2. If two circles have odd parity, then it is the information bit of the intersection
`
`of the two circles that was damaged. The error can corrected by flipping the
`
`value of that information bit.
`
`3. If none of the circles has even parity, then it is the value of u4 that was changed.
`
`The correct information bits can be obtained by flipping the value of this bit.
`
`Therefore, we can correct transmission errors so long as there is only one error bit
`
`within a block of seven bits ( a codeword). The above procedure ( decoding algorithm),
`
`however, does not produce correct answers if there are more than one error within a
`
`codeword and thus results in decoding errors. The purpose of this thesis is to construct
`
`Figure 1.2 The structure of the (7,4) Hamming Code.
`
`Page 14 of 112
`
`

`

`codes that are able to correct large number of errors with low error probabilities and
`
`require low complexity in the decoding algorithms.
`
`4
`
`1. 2 Thesis Outline
`
`Though coding theory suggests that error correcting codes chosen at random perform
`
`close to the optimum if their block lengths are large enough [52, 68, 75], the problem of
`
`designing good codes has traditionally been attacked by developing codes with a lot of
`
`structure, which lends itself to feasible decoders [51, 52]. The challenge to find prac(cid:173)
`
`tical decoders for long random codes was not seriously considered until the recent
`
`introduction of turbo codes in 1993 [7]. This methodology of multi-stage iterative
`
`decoding with exchange of soft information, applied to codes with pseudo-random
`
`structure, provides a whole new approach to construct good codes and to decode
`
`them with low complexity. The thesis will first apply this decoding method to a wide
`
`range of codes and will clarify some ambiguities and problems in the decoding algo(cid:173)
`
`rithms that have appeared in the literature. The connection between these decoding
`
`algorithms and a statistical inference framework [58] from the artificial intelligence
`
`community will then be made so that, when any of the codes is represented by a "be(cid:173)
`
`lief network," the application of this framework leads directly to the corresponding
`
`decoding algorithm without any ad hoc arguments used in the literature. A class of
`
`generalized turbo codes based on low-density generator matrices are then proposed
`
`and shown to achieve near-capacity performance with this belief propagation algo(cid:173)
`
`rithm. These low-density generator matrix (LDGM) codes can be applied to binary
`
`or M-ary signaling schemes with performance approaching the channel capacity. The
`
`content of subsequent chapters is briefed as follows:
`
`~ Unit Memory Hamming Turbo Codes (Chapter 2)
`
`The coding scheme of parallel concatenation of two simple recursive system(cid:173)
`
`atic convolutional codes ( turbo codes) was recently proposed to achieve near
`
`Shannon-limit error correction performance with reasonable decoding complex-
`
`Page 15 of 112
`
`

`

`5
`
`ity [7]. The underlying component code adopted in these results is a single-input
`
`convolutional code, or, more specifically, a (2, 1, 4, 7) code which is of memory
`v = 4 and free distance di = 7. On the other hand, in many cases of inter(cid:173)
`est, multi-input unit-memory codes have been demonstrated to have larger free
`
`distances than the single-input codes with the same rate and the same num(cid:173)
`
`ber of memory elements [l]. In this chapter, new turbo codes based on the
`
`(8, 4, 3, 8) unit-memory Hamming code are proposed and BCJR's optimal bit
`
`decision algorithm [2] is modified for this multiple input recursive convolutional
`
`code. Our results show that the new codes achieve marginally better perfor(cid:173)
`
`mance than conventional turbo codes. Better performance can be obtained by
`
`using two different component codes in the design of turbo codes.
`
`~
`Generalized Concatenated Convolutional Codes (Chapter 3)
`
`Since the decoders of turbo codes usually require maximum a posteriori (MAP)
`
`algorithm [2], which is of relatively high complexity if implemented straightfor(cid:173)
`
`wardly. Modified MAP algorithms [3, 60, 65] and soft-output Viterbi algorithm
`
`(SOVA) [38, 40] have thus been proposed in place of MAP decoders to reduce
`
`system complexity. Alternative high-performance coding systems of low com(cid:173)
`
`plexity are proposed in this chapter via the generalized concatenation of convo(cid:173)
`
`lutional codes. Two classes of generalized concatenated ( GC) codes with convo(cid:173)
`
`lutional outer codes are studied. The first class is based on the classical Plotkin
`
`/ a EB b/ b/ construction. A new suboptimal multi-stage soft decision algorithm
`
`is proposed and the corresponding performance bounds are obtained. These
`
`codes are shown to achieve better performance than conventional convolutional
`
`codes with equal or less decoding complexity, and are capable of unequal error
`
`protection. The Plotkin construction is then generalized using an inner differen(cid:173)
`
`tial encoding structure to obtain a second class of GC codes. A low-complexity
`
`two-iteration decoding algorithm using traditional hard-output Viterbi decoders
`
`is proposed. Numerical results show that the new coding systems can achieve
`
`comparable and sometimes superior performance to low-complexity turbo codes
`
`Page 16 of 112
`
`

`

`with similar computational complexity.
`
`6
`
`~
`Turbo Decoding and Belief Propagation {Chapter 4)
`
`Though the turbo decoding method has been applied to a wide range of codes
`
`with remarkable success, a satisfactory theoretical explanation as to why the
`
`turbo decoding algorithm performs so well has been lacking. In addition, some
`
`pathological cases where the algorithm never converges or converges to the
`
`wrong answer have been identified [53]. In this chapter, we establish a close
`
`connection between the turbo decoding mechanism and the "belief propagation"
`
`algorithm [58], well-known in the artificial intelligence community. We show
`
`that, by representing a turbo code with a "belief network", the application of
`
`the belief propagation algorithm directly leads to the turbo decoding algorithm.
`
`This framework also prescribes explicitly how the decoders for multiple turbo
`
`codes should proceed without any ad hoc arguments. In fact, it is also argued
`
`that the decoding algorithms for a wide range of turbo code constructions as
`
`well as low-density parity check codes [33] can be explained by this Bayesian
`
`network and belief propagation principle.
`
`· ~ Low-Density Generator Matrix Codes {Chapter 5)
`
`It is the purpose of this chapter to further examine the applicability of the belief
`
`propagation algorithm to coding theory. It is observed that the turbo codes sep(cid:173)
`
`arate parity bits into subsets in their Bayesian network representation, which
`
`is unnecessary for the belief propagation algorithm. A class of codes based on
`
`low-density generator matrix, where the parity bits are not differentiated, are
`
`proposed as a generalization of classical turbo codes. Contrary to the turbo
`
`decoding paradigms where sequential processing is accomplished by very pow(cid:173)
`
`erful central units, the decoding algorithm proposed here is formulated in a
`
`distributed parallel form. The decoders can thus enjoy modular pipeline design
`
`and the systems therefore seem more suitable for practical applications. For
`
`high-rate applications, numerical results show that these codes achieve perfor(cid:173)
`
`mance within 1 dB of the channel capacity.
`
`Page 17 of 112
`
`

`

`~
`Efficient Multilevel Coded Modulations (Chapter 6)
`
`7
`
`In this chapter, the low-density generator matrix codes are applied to M-ary
`signaling schemes by multilevel coding methods [12, 42, 62, 66, 72). The equiva(cid:173)
`lent channel capacities [41] for individual partition levels used in the multilevel
`coding systems are first computed. Partition rules other than Ungerboeck's
`maximum intra-set distance criterion are examined. LDGM codes for individ(cid:173)
`ual levels are then selected according to the corresponding equivalent capacities.
`We show this approach can be used to devise systems that achieve near channel
`capacity performance and are also able to provide unequal error protection.
`
`Page 18 of 112
`
`

`

`8
`
`Chapter 2
`
`Unit Memory Hamming Turbo Codes
`
`The coding scheme of parallel concatenation of two simple recursive systematic convo(cid:173)
`
`lutional codes-the turbo code-was recently proposed to achieve near Shannon-limit
`
`error correction performance with reasonable decoding complexity [7, 24, 25, 64]. The
`
`underlying component code used in these constructions is a single-input (SI) convolu(cid:173)
`tional code or, more specifically, a (2, 1, 4, 7) code, which is of rate 1/2, memory v = 4,
`and free distance di = 7. On the other hand, in many cases of interest, multi-input
`
`unit-memory (UM) codes have been demonstrated to have larger free distances than
`
`SI codes with the same rate and the same number of memory elements [1,45]. In this
`
`chapter, new turbo codes based on the (8, 4, 3, 8) UM Hamming code are developed.
`
`Page 19 of 112
`
`

`

`2.1 Encoder
`
`9
`
`The generator matrix of the (8, 4, 3, 8) unit-memory Hamming code is [1]
`
`G" =
`
`1
`
`1
`
`l+D l+D
`
`1
`
`1
`
`l+D
`
`l+D
`
`0
`
`0
`
`l+D
`
`0
`
`l+D
`
`D
`
`l+D 0
`
`1
`
`D
`
`1
`
`1
`
`l+D
`
`1
`
`0
`
`l+D
`
`D
`
`1
`
`1
`
`0
`
`0
`
`1
`
`0
`
`0
`
`= [AIB].
`
`To convert this into a systematic recursive code with a generator matrix of the form
`G = [IIA-1 Bl, one needs to find a column permutation such that (1) the matrix A
`is nonsingular and (2) the matrix A- 1 B is in its simplest form. There are (~) = 70
`permutations to be considered, since those that group columns into the same sub(cid:173)
`
`matrices are all equivalent for our purpose. The following matrix was found to fulfill
`
`the requirements through computer search:
`
`G'=
`
`1
`
`1
`
`1
`
`0 l+D l+D
`
`0 l+D
`
`0 l+D
`
`0
`
`0
`
`1
`
`0
`
`0
`
`1
`
`1
`
`l+D
`
`1
`
`D
`
`1
`
`1
`
`0
`
`1
`
`l+D
`
`l+D D
`
`l+D
`
`0
`
`l+D D
`
`1
`
`= [A'IB'].
`
`Therefore, the generator matrix of the equivalent systematic recursive code is
`
`G = [IIA'-1B'] =
`
`1 0 0 0
`
`0 1 0 0
`
`0 0 1 0
`
`0 0 0 1
`
`1
`l+D
`1
`
`D
`l+D
`1
`
`1
`
`1
`l+D
`1
`D
`l+D
`
`D
`l+D
`1
`
`1
`
`1
`l+D
`
`1
`
`D
`l+D
`1
`l+D
`1
`
`Because the McMillan degree of the generator is three [55, 73], it can be implemented
`
`with three memory elements as shown in Fig. 2.1. If we use the average edge com(cid:173)
`
`plexity of the trellis per information bit 2k+v / k as the decoding complexity 1) of a
`
`convolutional code [54], both the SI (2, 1, 4, 7) code and the UM (8, 4, 3, 8) code have
`the same complexity, 1) = 32, and hence are fair competitors.
`
`Page 20 of 112
`
`

`

`10
`
`U1 -~ - - - - - - - - - - , - - -~C I = U1
`~=¾
`½
`~=¾
`¾
`~=~
`~
`
`Cg
`Figure 2.1 Encoder of the recursive partial unit-memory Hamming code (additions
`are performed in the vertical direction only.)
`
`The encoders of parallel concatenated codes are illustrated in Fig. 2.2, where P
`represents the shift-register circuits for implementing the parity-check part A'-I B' of
`
`the generator P and I is a pseudo-random bit interleaver. The first encoder operates
`) = u and c~1
`on the input information bits directly and outputs c~1
`). The second
`encoder operates on the interleaved information sequence ii and outputs c~2
`) = ii and
`c~). After encoding a block of K information bits, the trellises of both codes can
`
`terminated by selecting two four-bit sequences for each of the encoders. These bits
`can be generated by the circuit in Fig. 2.3. This results in a (4(K + 4), K) block
`
`u
`
`2
`._.H:--t...-=-=---=-=---=-=---=-=--":j:
`(cid:157) C~
`
`)
`
`U
`
`~ - ,~ c~2)
`
`u ~ - - 1~ c~2)
`
`(B)
`(A)
`Figure 2.2 The encoders of rate 1/4 and 1/3 turbo codes.
`
`Page 21 of 112
`
`

`

`11
`
`Figure 2.3 Trellis termination circuit.
`
`code. The interleaved information sequence ii can be discarded to increase spectral
`
`efficiency. This will give us a (3(K +4)+4, K) block code. Note that the 4 terminating
`
`bits for the second encoder should be kept and transmitted.
`
`Since the minimum distance of the component UM code is larger than that of
`
`the SI code, the new unit-memory turbo (UMT) code is expected to have better
`
`performance than the SI turbo (SIT) codes. The estimate of the performance of
`
`a code requires information about its weight distribution. However, obtaining this
`
`weight distribution is a particularly challenging problem for turbo codes because of the
`
`pseudo-random interleaver. Though some bit error rate (BER) bounding techniques
`
`have been developed [26], they are not useful here. As to be shown later, the operating
`
`"' " 0
`
`~
`8103
`0
`:;;
`.c
`E
`::,
`C
`~ 102
`~
`"5
`E
`::,
`0
`
`10'
`
`100
`
`, , .. , , .. , .. 1· ., ...
`I
`".I," .. ,.
`::;,::::· .
`.....••. UMT/Biti6~i~Il
`I'.·· Co'efficiertt · ·
`25
`30
`
`20
`
`15
`
`weight
`Figure 2.4 The weight distributions of (80, 16) SIT and UMT codes.
`
`...
`
`35
`
`40
`
`Page 22 of 112
`
`

`

`12
`
`Eb/ N 0 range of interest is below 2 dB, but the bounds diverge above that. Before
`plunging into full-scale simulations, short-block (K = 16) cases of both SIT and UMT
`codes are compared. While the best found interleaver for the (80, 16) SIT code gives
`a minimum distance of 15 [24], the new (80, 16) UMT code enjoys a larger minimum
`distance of 18, achieved using the interleaver {13, 5, 10, 1, 11, 14, 0, 12, 6, 4, 15, 7,
`3, 9, 2, 8}. The weight distributions of both codes and a "random code," which is
`computed from the binomial coefficients Aw = 2k-n (:), are plotted in Fig. 2.4.
`
`2.2 Decoding Algorithm
`
`In this section, the classical maximum a posteriori (MAP) algorithm for computing
`the a posteriori probabilities [2] will be modified to deal with multiple input recursive
`trellis codes. Turbo decoding based on this algorithm will then be described.
`
`2.2.1 MAP Algorithm for Multi-Input Recursive Trellis Codes
`
`Let the state of the encoder for the (n, k, v) code at time t be St E {0, 1, ... , 2v - 1}
`for t = 0, ... , K, where the initial and final states, S0 and SK, are known. As
`shown in Fig. 2.5, the input symbol Ut = (ut,l, ... , Ut,k) causes a transition from
`St-l to St, and the corresponding output codeword Ct = (ct,1 , ... , Ct,n) is observed
`over an AWGN channel as Yt = (Yt,1, ... , Yt,n), for t = 1, ... , K. Note that Ct =
`(ut,1, ... , Ut,k, Ct,k+l, ... , Ct,n) since the code is systematic. The log likelihood ratios
`of the a posteriori probabilities, given all the received signals y:f 1::,. (y1 , y 2 , ... , YK),
`are computed as
`
`·) A
`(
`A Ut,J
`-
`
`log
`
`Pr { Ut,j = +1 I yf} _
`I K} -
`_
`{
`Pr Ut,j - -1 y 1
`
`I:s Pr {St= s, Ut,j = +1 I yf}
`_
`{ _
`log I:
`I K} ,
`s, Ut,j - -1 y 1
`s Pr St -
`
`(2.1)
`
`fort= 1, ... , K, and j = 1, ... , k. The summations are over all the possible states at
`time t. In order to compute (2.1) recursively, the following quantities are introduced:
`
`Page 23 of 112
`
`

`

`13
`
`Trellis
`transition
`
`St-1
`•
`•
`s'
`
`•
`
`St
`•
`
`s
`•
`
`St+i
`•
`s"
`•
`ut+if ct+1:
`
`•
`
`Input
`data
`ouiut
`Co ewords
`Received
`Y t+l
`Y t
`signals
`Figure 2.5 The variables involved in the MAP algorithm.
`
`Ut
`
`Ct
`
`Ut+l
`
`Ct+l
`
`• The probability of St = s given the past signals Yi 6 (Yi, Y2, ... , Yt):
`
`• The normalized probability of the future signals yft._1
`given St= s:
`
`6
`
`(Yt+l, Yt+2, ... , YK)
`
`) 6 Pr {yft-1 I St = s, yt}
`r:l (
`I t}
`{ K
`1--'t s
`Pr Yt+1 Y1
`
`Pr { yft__ 1 I St = s}
`Pr {yft._1 I yt}
`'
`
`which follows from the Markov property of the trellis.
`
`• The branch transition probability from St-l = s' to St = s with the present
`
`signal Yt=
`
`I't(s', s) 6 Pr {St= s, Yt I St-1 = s'}.
`
`• The joint probability of the transition from s' to s and a the jth input of i:
`
`,L(s', s) 6 Pr {St= s, Ut,j = i, Yt / St-1 = s'}.
`
`Page 24 of 112
`
`

`

`Consider the terms in the summands of (2.1):
`
`14
`
`Pr { St = s, Ut,j = i I yf}
`Pr {St= s, Ut,j = i,yi, Y~I}
`Pr {YL Y~I}
`Pr {St= s, Ut,j = i, yi} Pr {Y~I I St= s, Ut,j = i, Yi}
`Pr {yt;_I I Yi}
`Pr {yi}
`Es' Pr { St = s, Ut,j = i, Yt I St-I = s', Yi-I} Pr { St-I = s', Yi-I}
`I t-I} p { t-I}
`f3t(s)
`r Yt YI
`r YI
`P {
`Es, 'Yt,j ( s', s) lYt-I ( s') f3t( s)
`Pr {Yt I Yi-I}
`
`where
`
`Pr {YtI I St = s, Ut,j = i, yi} = Pr {YtI I St = s}
`Pr {St= s, Ut,j = i, Yt I St-I= s', YtI} = Pr {St= s, Ut,j = i, Yt I St-I= s'}
`
`because of the Markov property. Therefore,
`
`A(u ·)=lo Es Es' 'Yt/(s', s) lYt-I(s') f3t(s).
`g Es Es' "ft,} ( s', s) at-I ( s') f3t( s)
`t,J
`
`(