Sparse Graph Codes
`
`David .J. C. 1\IacKay (mackay@mrao. cam. ac. uk)
`Cavendish Laboratory, Cambridge, CB3 OHE, United Kingdom.
`
`Abstract
`In the last decade remarkable progress has been made tm-vards the Shannon limit, using codes
`that are defined in terms of sparse random graphs, and \vhich are decoded by message passing.
`Designing a good error correcting code is difficult because (a) it. is hard t.o find an explicit. set. of
`\vell spaced code\vords; and (b) for a generic code, decoding, i.e., finding the clm;est code\vonl to a
`received f:>ignal, if:> intractable.
`However, a f:>imple method for designing codes~ first pioneered by Gallager (1962), has recently
`been rediscovered and generalized. The practical performance of Gallager's codes and their modern
`cousins is ·vast.ly bett.er than t.he performance of the codes "\vith which textbooks have been filled in
`the intervening years.
`In a. sparse graph code~ the nodes in the graph represent the transmitted bits and the con(cid:173)
`straints they satisfy. For a linear code with a codeword length Nand rateR= K/N, the number
`of constraints is of order AJ = 1V- K (there could be more constraints, if they happen to be redun(cid:173)
`dant). Any linear code can be described by a graph, but \vhat. makes a sparse graph code special is
`that each constraint. only involves a small nurnber of variables in the graph: t.he number of edges in
`the graph scales roughly linearly \Vith l\1•
`The graph defining a low density parity check code (Gallager code) contains two types of
`node: codeword bits~ and parity constraints. In a regular (j, k) Gallager code~ each codc,vord bit is
`connected t.o j parity constraints and each constraint is connected to k bits. The connections in the
`graph are made at random.
`Repeat-accumulate codes (Divsa.la.r et al. 1998) can be represented by a. graph \Vith four types
`of node: equality constraints c=:::J, intermediate binary variables (black circles), parity constraints
`GJ, and t.he transmitted bit.s (whit.e circles). The encoder sets each group of intermediate bits t.o
`values read from the source. These bits arc put through a fixed random permutation. The GJ
`constraints cause the transmitted stream~ working from left to right, to be the accumulated sum
`(modulo 2) of t.he permuted intermediate bit.s.
`In a. turbo code (Berrou and Glavieux 1996), the J( source bits drive hvo linear feedback shift
`registers, 1vhich emit parity bits.
`All these codes can be decoded by a local message-passing algorithm on the graph, the sum(cid:173)
`product algorithm (MacKac· and Neal 1996; :V!cEliece et u.l. 1998; JV!ar:Kay 1999), and, while this
`algorithm is not. t.he opt.imal decoder, t.he empirical result.s are record-breaking.
`\llhich of the three types of sparse graph code is "best' depends on the chosen rate and blocklength,
`the permitted encoding and decoding complexity~ and the question of whether occasional undetected
`errors arc acceptable (turbo codes and repeat-accumulate codes both typically make occasional
`undetected errors because they have a small nurnber of lmv \veight codev·.ronls; Gallager codes do
`not. typically show such an error floor). Gallager codes are t.he most. versatile; it/s easy to make a
`competitive Gallager code with almost any rate and blocklength.
`The best known binary Gallager codes arc irregular codes whose parity check matrices have
`non-uniform weight per column (Lub)• et al. 1998; Crbanke et al. 1999). The careful!)• constructed
`codes of Urbanke, Richardson and Shokrollahi outperform t.urbo codes at long blocklengt.hs. Turbo
`codes can also be beat.en by irregular Gallager codes defined over finit.e fields GF(q) (Davey and
`MacKay 1998). While there is a good theory for Gallager code design (Crbanke et al. 1999), there
`is no comparable theory for the construction of irregular graphs with state variables. Given the case
`\vith which simple repeat-accumulate codes achieve good results, it seems plausible that the best
`codes should make use of state variables.
`
`1
`
`Hughes, Exh. 1042, p. 1
`
`

`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`Reg
`GF(16)
`
`Irreg
`GF(2)
`
`Reg
`GF(2)
`
`Turbo
`
`Irreg GF(8)
`
`-0.2
`
`0
`
`0.4
`0.2
`Eb/No (dB)
`
`0.6
`
`0.8
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`total
`undetected
`
`N=204
`
`N=408
`
`N=816
`
`1
`
`N=30000
`
`2
`
`N=9999
`
`3
`
`N=3000
`
`4
`
`5
`
`

`
`DIFFERENCE SET CYCLIC CODES
`7
`21
`73
`273
`1057 4161
`4 10
`28
`82
`244
`730
`45
`191
`813
`3431
`11
`3
`4
`10
`18
`34
`6
`66
`3
`5
`9
`17
`33
`65
`
`N
`M
`J{
`d
`k
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`Gallager(273,82)
`DSC(273,82)
`
`----tli---
`
`0.0001
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`Figure 3: Lmv density parity check codes satisfying many redundant constraints outperform equiv(cid:173)
`alent Gallager codei:>. Data on DSC code performance courtesy of R. Lucas and l\1. Foi:>f:>orier. The
`table i:>hows the 1V, Af ~ K, distance d, and nJ\V 1veight k of some difference set cyclic codei:>, high(cid:173)
`lighting the codes that have large d/N, small k, and large N/M. In the comparison the Gallager
`code had (j, k) = (4, 13), and rate identical to the DSC code.
`
`The performance of Gallager codes can be enhanced by designing the code to have redundant
`sparse constraints (Tanner 1981) (R. Lucas and I\:J. Fossoricr~ personal communication). There
`is a difference-set cyclic code, for example, that has J\1 = 273, and J( = 191, but the code satisfies
`not Af = 82 but J.V, i.e., 273 lmv-1veight constraints (figure 3). It is impossible to make random
`Gallager codes that have an:pvhere near this much redundancy among their checks.
`An open problem is to discover codes sharing the remarkable properties of the difference-set
`cyclic codes but with different blocklcngths and rates. I call this task the Tanner challenge.
`
`References
`
`Berrou, C., and Glavieux, A. (1996) I\ ear optimum error correcting coding and decoding: Turbo(cid:173)
`codes. IEEE Transactions on Communications 44: 1261-1271.
`
`Davey, M. C., and :V!acKay, D . .J. C.
`(1998) Low density paritc· check codes over GF(q). In
`Proceedings of the 1998 IEEE Infonrwtion Theory Wor·kshop. IEEE.
`
`Divsalar, D., .Jin, H., and McEliece, R . .J., (1998) Coding theorems for 'turbo like' codes.
`
`Gallager, Il. G. (1962) Low densit)• parit)• check codes. IRE Tmns. Info. Theor·y IT-8: 21-28.
`
`Luby, 1\I. G., 1\Iitzenmacher, 1\I., Shokrollahi, 1\I. A., and Spielman, D. A. (1998) Improved low(cid:173)
`density parity-check codes using irregular graphs and belief propagation. In Prnceedings of the
`IEEE International Syrnposinrn on Informati on Theory (!SIT), p. 117.
`
`)..facKay, D. J. C.
`(1999) Good error correcting codei:> bai:>ed on very sparse matrices.
`Tr-ansactions on Information Theor·y 45 (2): 399-431.
`
`IEEE
`
`:V!acKa)•, D . .J. C., and "'eal, R. 1\1. (1996) I\' car Shannon limit performance of low densit)· parit)·
`check codes. Electnm:ics Letters 32 (18): 1645-1646. Reprinted Electronics Letters, 33(6):457-458,
`~larch 1997.
`
`~!cEliece, R . .J., MacKay, D . .J. C., and Cheng, .J.-F. (1998) Turbo decoding as an instance of
`Pearl's 'belief propagation~ algorithm. IEEE Jo-urnal on Selected Areas in Comm-unications 16
`(2): 140-152.
`
`(1981) A recursive approach to lmv complexity codes. IEEE Trnnsaction.<J on
`Tanner, R. I\.-'1.
`Information Theory 27 (5): 533 547.
`
`Urbanke, Il., Richardson, T., and Shokrollahi, A., (1999) Design of provabl)• good low density
`parity check codes.
`
`3
`
`Hughes, Exh. 1042, p.3