Turbo Codes are Low Density Parity Check Codes
`
`David J(cid:2) C(cid:2) MacKay
`
`July (cid:4) (cid:7) Draft (cid:2)(cid:4) not for distribution(cid:10) (cid:11)First draft written July (cid:4)
` (cid:13)
`
`Abstract
`
`Turbo codes and Gallager codes (cid:2)also known as low density parity check codes(cid:3) are at
`present neck and neck in the race towards capacity(cid:4)
`In this paper we note that the parity check matrix of a Turbo code can be written as
`low density parity check matrix(cid:4)
`
`Turbo codes and Gallager codes are both greatly superior to error(cid:2)correcting codes found in
`textbooks(cid:3) Some similarities between these codes have been noted(cid:3) For example(cid:4) both families of
`codes can be de(cid:5)ned in terms of sparse graphs which de(cid:5)ne the constraints satis(cid:5)ed by codewords
`(cid:6)cite Tanner(cid:4) Wiberg(cid:4) Loeliger(cid:4) Frey(cid:4) MacKay(cid:7)(cid:3) Both families of codes are decoded using a
`local probability propagation algorithm which is known as the sum(cid:2)product algorithm or belief
`propagation (cid:6)cite Wiberg(cid:4) McEliece and MacKay(cid:4) Frey(cid:7)(cid:3)
`There are also di(cid:8)erences between the two code families(cid:3) In the original form studied by
`Gallager and MacKay and Neal(cid:4) Gallager codes are quick to decode but have an encoding time
`that scales as N (cid:4) whereas Turbo codes are usually de(cid:5)ned in terms of linear time encoders(cid:3)
`(cid:6)Fast(cid:9)encodeable Gallager codes have recently been investigated(cid:4) MacKay(cid:3)(cid:7) In Turbo codes there
`is a sharp distinction between the bits viewed as source bits and the bits viewed as parity check
`bits(cid:10) they play di(cid:8)erent roles in the decoding algorithm(cid:4) and posterior probabilities over the states
`of parity check bits are usually not computed(cid:3) In Gallager codes(cid:4) there is a symmetry between
`all bits(cid:3) Turbo codes as originally de(cid:5)ned tend to su(cid:8)er from low weight codewords which cause
`the asymptotic performance for large Eb(cid:2)N to have an (cid:11)error (cid:12)oor(cid:13)(cid:3) Gallager codes(cid:4) in contrast(cid:4)
`show no such error (cid:12)oor(cid:4) and it has been proved that they have asymptotically good distance
`properties(cid:3) Gallager codes are simple to modify in order to create codes with higher or lower
`rates(cid:3) In contrast(cid:4) increasing the rate of a Turbo code can be tricky because simple puncturing
`of the parity bits might weaken the code by introducing low weight codewords(cid:3)
`Since these two families of codes are both so good in performance(cid:4) it seems a good idea
`to try to relate them so as to enhance technology transfer and hybridisation between the two
`methodologies(cid:3) However(cid:4) to our knowledge(cid:4) only a few researchers have tried to connect these
`(cid:5)elds together and design new codes (cid:6)cite Frey and MacKay(cid:7)(cid:3)
`This paper makes a simple observation about Turbo codes(cid:14) treating a Turbo code as a block
`code(cid:4) the parity check matrix of that code is actually a low density parity check matrix(cid:3) This
`observation is probably extremely obvious to anyone who is familiar with convolutional codes(cid:4)
`but for the bene(cid:5)t of readers like myself who are not(cid:4) I will spell this out in a little more detail(cid:3)
`
`
`
`Hughes, Exh. 1056, p. 1
`
`

`
`Trellis complexity
`
`
`
`t
`
`Turbo
`
`t
`
`Gallager (cid:6)GF (cid:6)q(cid:7)(cid:7)
`
`
`q
`
`
`
`
`o(cid:3) of bits per trellis
`
`
`t
`
`Turbo
`
`NN
`
`
`
`(cid:3)(cid:3)(cid:3)
`
` log q
`
`
`
`t
`
`t
`
`
`
`t
`
`Gallager
`
`(cid:2)
`
`Gallager (cid:6)GF (cid:6)q(cid:7)(cid:7)
`Gallager
`(cid:2)
`M(cid:2)q(cid:3) (cid:3) (cid:3) M No(cid:3) of trellises
`Figure (cid:14) One view of the locations of Gallager codes and Turbo codes in (cid:11)code space(cid:13)(cid:4) using
`rate (cid:19) codes as an example(cid:3) From this perspective(cid:4) Gallager codes and Turbo codes seem quite
`di(cid:8)erent(cid:3)
`
`
`
`(cid:3) (cid:3) (cid:3)
`
`
`
`
`
`
`
`Mean no(cid:3) of trellises p
`
` De(cid:2)nitions
`
`A low density parity check code is a block code which has a parity check matrix(cid:4) H(cid:4) every row
`and column of which is (cid:11)sparse(cid:13)(cid:3)
`A regular Gallager code is a low density parity check code in which every column of H has
`the same weight t and every row has the same weight tr(cid:10) regular Gallager codes are constructed
`at random subject to these constraints(cid:3)
`An (cid:6)N(cid:4) K(cid:7) Turbo code is de(cid:5)ned by a number of constituent encoders (cid:6)often(cid:4) two(cid:7) and an equal
`number of (cid:11)interleavers(cid:13) which are K(cid:0)K permutation matrices(cid:3) Without loss of generality(cid:4) we take
`the (cid:5)rst interleaver to be the identity matrix(cid:3) The constituent encoders are often convolutional
`codes(cid:3) A string of K source bits is encoded by feeding them into each constituent encoder in
`the order de(cid:5)ned by the associated interleaver(cid:4) and transmitting the bits that come out of each
`constituent encoder(cid:3) For simplicity(cid:4) let us concentrate on Turbo codes with two constituent
`codes that are both convolutional codes(cid:3) Often the (cid:5)rst constituent encoder is chosen to be a
`systematic encoder(cid:4) and the second is a non(cid:2)systematic one which emits parity bits only(cid:3) The
`transmitted codeword then consists of K source bits followed by M parity bits generated by the
`(cid:5)rst convolutional code and M parity bits from the second(cid:3)
`For the purposes of this paper we will not need to discuss the decoder for either of these codes(cid:3)
`One unifying viewpoint for these two code families is in terms of trellis constrained codes(cid:3) A
`trellis constrained code is a code whose codewords satisfy a set of constraints(cid:4) each constraint
`being compactly described by a trellis in which two or more of the codeword bits participate(cid:3)
`Viewing these codes as trellis constrained codes(cid:4) they appear rather di(cid:8)erent(cid:3) The M (cid:0) N parity
`check matrix of a regular Gallager code de(cid:5)nes M trellises(cid:3) Each trellis constrains the parity of
`tr of the bits to be even(cid:4) and each of the N bits participates in t trellises(cid:3) We can think of a
`Turbo code as a trellis constrained code in which there are two trellises(cid:10) the K source bits and
`the (cid:5)rst M parity bits participate in the (cid:5)rst trellis and the K source bits and the last M parity
`bits participate in the second trellis(cid:3) Each codeword bit participates in either one or two trellises(cid:4)
`depending on whether it is a parity bit or a source bit(cid:3) See (cid:5)gure (cid:3)
`However(cid:4) we will now see that from the point of view of their parity check matrices(cid:4) Turbo
`
`
`
`Hughes, Exh. 1056, p. 2
`
`

`
`hdz
`
`hdz
`
`hdz
`
`z
`
`hd (cid:3)
`z
`
`(cid:2)
`
`(cid:2)
`
`t(cid:6)a(cid:7)
`s
`
`(cid:2)
`
`(cid:2)
`
`(cid:2)
`
`(cid:2)
`
`t(cid:6)b(cid:7)
`
`t(cid:6)b(cid:7)
`
`s
`
`t(cid:6)a(cid:7)
`
`t(cid:6)b(cid:7)
`
`(cid:2)(cid:4)
`
`(cid:2)
`
`(cid:2)(cid:4)
`
`(cid:2)
`
`(cid:2)(cid:4)
`
`(cid:2)(cid:4)
`
`(cid:2)(cid:2)
`
`(cid:2)
`
`(cid:2)
`
`hdz
`
`hdz
`
`hdz
`
`z
`
`hd (cid:3)
`z
`
`(cid:2)(cid:4)
`
`(cid:2)
`
`(cid:2)(cid:4)
`
`(cid:2)
`
`(cid:2)(cid:4)
`
`(cid:2)(cid:4)
`
`(cid:2)(cid:2)
`
`(cid:2)
`
`(cid:2)
`
`(cid:6) (cid:2) (cid:7)
`
`(cid:2)
`
`t(cid:6)a(cid:7)
`s
`
`hdz
`
`hdz
`
`hdz
`
`z
`
`hd
`
`z
`
`(cid:2)
`
`(cid:2)
`
`(cid:3)
`
`(cid:2)
`
`(cid:2)(cid:4)
`
`(cid:2)
`
`(cid:2)(cid:4)
`
`(cid:2)(cid:4)
`
`(cid:2)(cid:2)
`
`(cid:6)a(cid:7)
`
`(cid:6)b(cid:7)
`
`(cid:6)z(cid:7)
`
`Figure (cid:14) Linear feedback shift registers for generating convolutional codes(cid:3) K (cid:21) (cid:3)
`
`codes are actually very similar to Gallager codes(cid:3)
`
` (cid:2) The parity check matrix of a single convolutional code
`
`Note di(cid:8)erent meaning for parity check matrix from convolutional code literature(cid:3) Here we are
`talking about the literal parity check matrix of the code viewed as a linear block code(cid:3)
`A systematic recursive convolutional code(cid:4) as used in Turbo codes(cid:4) is equivalent (cid:6)in the
`sense that its codewords are the same(cid:7) to a nonsystematic nonrecursive convolutional code (cid:6)(cid:5)g(cid:9)
`ure (cid:2)(cid:2)(cid:6)b(cid:7)(cid:7)(cid:3) Now(cid:4) what parity constraints are satis(cid:5)ed by the latter code(cid:22) Well(cid:4) if we pass stream
`b through the convolutional (cid:5)lter that generated stream a and vice versa(cid:4) then the two resulting
`streams are identical(cid:3) So the parity check matrix of a single convolutional code may be written
`as a low density parity check matrix as shown in (cid:5)gure (cid:2)(cid:2)(cid:6)b(cid:7)(cid:3)
`Issue neglected here(cid:14) termination(cid:3) Termination simply adds an extra k constraints(cid:4) where k
`is the constraint length(cid:3) Not a big deal(cid:3)
`
` (cid:2) The parity check matrix of a Turbo code
`
`Note that for the standard constraint length  convolutional codes(cid:4) the pro(cid:5)le of the turbo code(cid:13)s
`parity check matrix is roughly K columns of weight about (cid:4) and the remaining columns of weight
`about (cid:10) the row weight is about  for all rows(cid:3)
`Here puncturing ignored(cid:3) How to handle it(cid:14) if the bit only participates in one check(cid:4) remove
`that check(cid:3) If it participates in more than one check(cid:4) use row manipulations to create new higher
`weight checks that don(cid:13)t involve that bit(cid:3)
`Note that classic Turbo codes are punctured down to rate (cid:19)(cid:3)
`
`
`
`Hughes, Exh. 1056, p. 3
`
`

`
`3
`
`3
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`3
`
`5
`
`2 2
`
`(cid:6)a(cid:7)
`
`(cid:6)a(cid:13)(cid:7)
`
`(cid:6)b(cid:7)
`
`(cid:6)c(cid:7)
`
`(cid:6)d(cid:7)
`
`Figure (cid:14) Schematic pictures of the parity check matrices of (cid:6)a(cid:7) a regular Gallager code(cid:4) rate (cid:19)(cid:4)
`(cid:6)a(cid:13)(cid:7) an almost regular Gallager code rate (cid:19) (cid:6)b(cid:7) a convolutional code(cid:4) rate (cid:19)(cid:4) and (cid:6)c(cid:7) a Turbo
`code(cid:4) rate (cid:19) (cid:3) Notation(cid:14) A diagonal line represents an identity matrix(cid:3) A band of diagonal lines
`represent a band of diagonal s(cid:3) A circle inside a square represents the random permutation of
`all the columns in that square(cid:3) Horizontal and vertical lines indicate the boundaries of the blocks
`within the matrix(cid:3) (cid:6)d(cid:7) shows another code with roughly the same pro(cid:5)le as a Turbo code(cid:3)
`
`
`
`Hughes, Exh. 1056, p. 4
`
`

`
` Consequences
`
`Some of the theoretical results proved for Gallager codes carry over to Turbo codes(cid:3) The positive
`ones (cid:6)for example(cid:4) that Gallager codes are (cid:11)very good(cid:13)(cid:7) don(cid:13)t carry over since they rely on creating
`the whole matrix at random(cid:3) But the negative ones do(cid:3) One negative result is that Turbo codes
`de(cid:5)nitely can(cid:13)t get to the Shannon limit unless the constraint length of the constituent codes
`grows(cid:3)
`
` Discussion
`
`For those of us who thought that there was a considerable distance in (cid:11)code space(cid:13) between Turbo
`codes and Gallager codes(cid:4) this observation forces a shift in viewpoint(cid:3) It also allows us to roll out
`a few simple theorems about the maximum likelihood performance of Turbo codes(cid:3)
`So(cid:4) given that they are such similar codes(cid:4) what are the di(cid:8)erences(cid:22) Why are regular Gallager
`codes worse than Turbo codes(cid:22) We have caught up with Turbo codes only by (cid:6) (cid:7) making them
`over GF(cid:6) (cid:7)(cid:10) (cid:6)(cid:7) making them irregular(cid:3) But notice these Turbo codes are binary and their parity
`check matrices are pretty near regular(cid:25)
`I have some ideas about why Turbo are better(cid:3)
`Notice that the standard way of decoding a Gallager code is not how Turbo codes are decoded(cid:3)
`Message passing di(cid:8)erent and would be more inaccurate in the Gallager style(cid:3) Turbo sends
`messages all the way along trellises(cid:4) so the within(cid:2)trellis messages are correct(cid:3)
`
` (cid:2) Wasted checks
`
`Consider a Gallager code with tr (cid:21) (cid:3) Imagine that of the four bits that participate in one check(cid:4)
`three of them happen to be well(cid:2)determined given the output of the channel(cid:3) This check allows
`us instantly to correct the fourth bit(cid:4) but then it plays no useful role(cid:3) This is not the way a good
`code works(cid:25)
`In contrast(cid:4) in a Turbo code(cid:4) if some bits are well determined(cid:4) the sole e(cid:8)ect is to prune the
`trellis(cid:3) Whatever bits are well(cid:2)determined(cid:4) the remaining bits participate in a trellis that looks
`(cid:6)locally(cid:7) just the same(cid:3)
`
`
`
`Hughes, Exh. 1056, p. 5