ISIT 2000, Sorrento, Italy, June 25-30,2000
`
`Irregular Turbocodes
`Brendan J. Frey, Computer Science, University of Waterloo, http:l/w.cs.uwaterloo.ca/4rey
`David J. C. MacKay, Physics, Cambridge University, http://wol.ra.phy.cam.ac.uk/mackay
`
`Abstract - We construct irregular turbocodes with systematic
`bits that participate in varying numbers of trellis sections. By
`making the original rate 112 turbocode of Berrou et uL slightly
`irregular, we obtain a coding gain of 0.15 dB at BER =
`
`I. IRREGULAR TURBOCODES
`Recently, significant coding gains have been obtained by
`making the codeword bits of low density parity check codes
`participate in varying numbers of parity checks (c.f. [ 1,2]).
`What we call an irregular turbocode [3] has the form shown
`in Fig. 1, which is a type of “trellis-constrained code” [3]. One
`way to describe the code is by a degreeprofile, f d E [0,1], d E
`{ 1,2, . . . , D}, where f d is the fraction of codeword bits that
`have degree d and D is the maximum degree. Each codeword
`bit with degree d is repeated d times before being permuted
`and connected to the trellis for a convolutional code. If the
`bits in the convolutional code are partitioned into “systematic
`bits” and “parity bits”, then by connecting each parity bit to a
`degree 1 codeword bit, we can encode in linear time by copy-
`ing, permuting and encoding the systematic bits.
`The overall rate R of an irregular turbocode is related to-the
`rate R’ of the convolutional code and the average degree d by
`a( 1 - R’) = 1 - R. So, if the average degree is increased, the
`rate of the convolutional code must also be increased (e.g., by
`puncturing or redesign) to keep the overall rate constant.
`
`11. DECODING IRREGULAR TURBOCODES
`Fig. 1 can be interpreted as the graphical model (factor
`graph, Bayesian network, etc.) [4, 51 for the irregular tur-
`bocode. Decoding consists of applying the sum-product al-
`gorithm (a generalized form of turbodecoding) in this graph.
`The decoder first computes the N channel output log-
`likelihood ratios ,$, . . . , L g , and then repeats each log-
`likelihood ratio appropriately. For bit i with degree di, set
`Li,l t Ly, . . . , &,d e Lf. Next, the log-likelihood ratios
`are permuted and fed into the BCJR algorithm for the convo-
`lutional code, which, for bit i, produces d a posteriori log-
`probability ratios, Li,l, . . . , L:,d. The current estimate of the
`log-probability ratio for bit i is Li t Ly + C i = l ( L i , , -
`Li,k). The inputs to the BCJR algorithm for the next itera-
`tion, are computed by subtracting off the corresponding out-
`puts from the BCJR algorithm produced by the previous itera-
` - L : , ~ .
`tion: ~ i
`
`, k t i i
`111. DISCUSSION
`Fig. 2 shows the simulated BER-Eb /NO curves for the orig-
`inal regular turbocode and an irregular turbocode that we came
`up with by making 5% of the codeword bits in the original tur-
`bocode have degree 10 The irregular turbocode clearly per-
`forms better than the regular turbocode for BER >
`For high &,/NO, most of the errors for the irregular tur-
`bocode were due to low-weight codewords. Our permuter
`was drawn from a uniform distribution over permuters, but
`
`Figure 1: A general irregular “ d e . For d = 1,. . . , D, fraction
`fd of the codeword bits are repeated d times, permuted and connected
`to a convolutional code.
`
`0.1
`
`1
`
`0.01
`
`:
`
`w a 0.001
`m
`
`-
`
`o.ooo1
`
`-
`
`\
`
`‘1
`
`\
`
`REFERENCES
`D. J. C. MacKay, S. T. Wilson, and M. C. Davey, “Comparison of con-
`structions of irregular Gallager codes,” IEEE ~ansactions on Communi-
`cations, vol. 41, October 1999.
`T. Richardson, A. Shokrollahi, and R Urbanke, “Design ofprovably good
`low density parity check codes.” Submitted to IEEE Transactions on In-
`formation Theory, July 1999.
`B. J. Frey and D. J. C. MacKay, “Irregular turbocodes,” m Proceedings of
`the 37th Allerton Conference on Communication. Control and Comput-
`ing 1999.
`B. J. Frey, Graphical Modehfor Machine Learning and Digital Commu-
`nication. Cambridge MA.: MIT Press, 1998.
`E R. Kschischang and B. J. Frey, “Iterative decoding of compound codes
`by probability propagation in graphical models:’ IEEE Journal on Se-
`lected Areas in Communications, vol. 16, pp. 219-230, February 1998.
`
`0-7803-5857-0/00/S10.00 02000 IEEE.
`
`121
`
`Hughes, Exh. 1048, p. 1