Comparison of Constructions
`of Irregular Gallager Codes
`
`David J. C. MacKay, Simon T. Wilson and Matthew C. Davey
`Department of Physics, University of Cambridge
`Cavendish Laboratory, Madingley Road,
`Cambridge, CB3 OHE, United Kingdom.
`
`mackaylstw11lmcdavey@mrao.cam.ac.uk
`
`To appear in IEEE Transactions on Communications. Submitted 30 July 1998.
`
`Abstract
`
`The low density parity check codes whose performance is closest to the Shan(cid:173)
`non limit are 'Gallager codes' based on irregular graphs. We compare alternative
`methods for constructing these graphs and present two results.
`First, we find a 'super-Poisson' construction which gives a small improvement
`in empirical performance over a random construction.
`Second, whereas Gallager codes normally take N 2 time to encode, we investi(cid:173)
`gate constructions of regular and irregular Gallager codes which allow more rapid
`encoding and have smaller memory requirements in the encoder. We find that these
`'fast-encoding' Gallager codes have equally good performance.
`
`1
`
`Introduction
`
`Gallager codes [3, 4] are low density parity check codes constructed at random subject to
`constraints on the weight of each row and of each column. The original regular Gallager
`codes have very sparse random parity check matrices with uniform weight t per column
`and tr per row. [We will also use the term 'regular' for codes which have nearly uniform
`weight columns and rows- for example, codes which have some weight 2 columns and
`some weight 3 columns.] These codes are asymptotically good, and can be practically
`decoded with Gallager's sum-product algorithm giving near Shannon limit performance
`when large block lengths are used [7, 8, 6]. Regular Gallager codes have also been found
`to be competitive codes for short block-length CDMA applications [10].
`Recent advances in the performance of Gallager codes are summarised in figure 1. The
`rightmost curve shows the performance of a regular binary Gallager code with rate 1/4.
`The best known binary Gallager codes are irregular codes whose parity check matrices
`have nonuniform weight per column [5]; the performance of one such code is shown by
`the second curve from the right. The best known Gallager codes of all are Gallager
`codes defined over finite fields GF(q) [2, 1]. The remaining two solid curves in figure 1
`show the performance of a regular Gallager code over GF(16) [2] and an irregular code
`over GF(8) with bit error probability of 10-4 at Eb/ N 0 = -0.05dB [1]. In comparing
`this code with the rate 1/4 Turbo code shown by the dotted line, the following points
`
`Hughes, Exh. 1039, 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
`
`

`

`This paper has two parts. In the first part (section 3) we compare alternative con(cid:173)
`struction methods for a fixed profile in order to find out whether the construction method
`matters. In the second part (section 4) we examine regular and irregular constructions
`which lend themsdves to rapid encoding. One motivation for this second study is that.
`the only drawlmck of regular Gallager codes compared t.o Turbo codes for CDMA appli(cid:173)
`cations appears to be their greater encoding complexity [10].
`In the experiments presented here, we study binary codes with rate 1/2 and block(cid:173)
`length about N = 10, 000. \Ve simulate an additive white Gaussian noise channel in the
`usual way [2] and examine the block error probability as a function of the signal to noise
`ratio. The error bars we show are one standard deviation error bars on the estimate of
`the lofiarithm of the block error probability p, defined thus: when we observe r failures
`out ofn trials, P± = pexp(±crtogp) where CTtogp = ,j(n- r)/(rn).
`
`2 Constructions
`
`We compare the following methods.
`
`Poisson: The edges are placed 'completely at random' subject to the profile constraints,
`and the rule that you can't put two edges between one pair of vertices, which would
`correspond to a double entry in the parity check matrix. One way to implement a
`Poisson construction is to make a list of all the columns in the matrix, with each
`column appearing in the list. a number of times equal t.o its weight., then make
`a similar list. of all the rows in the matrix, each row appearing with multiplicity
`equal t.o its weight. and then map one list. onto the other by a random permutation,
`taking care not to create duplicate entries [5].
`
`A variation of this construction is to require that no two columns in the parity
`check matrix have an overlap greater than one, i.e., forbid cyc:les of length 4 in the
`graph. [Similar to construction 1A in [8].] A second variation requires that the
`graph to have no cycles of length less than some l. [Similar to construction 1I3 in
`[8].] This constraint can be quite hard to enforce if the profile includes high weight
`rows or columns.
`
`Permutations. \Ve can build parity check matrices by superposing random permutation
`matrices [4]. The convenience of this method depends on the profile. There are
`many ways of laying out these permutation matrices t.o satisfy a given profile. \Ve
`will distinguish '.supe1' rois.son' and 'snb rois.son' const.mctions.
`
`• In a super-Poisson construction, the distribution of high weight columns per
`row has greater variance than a Poisson distribution;
`
`• In a sub Poisson const.mction, the distribution of high weight columns per
`row has smaller variance than a Poisson distribution.
`
`Hughes, Exh. 1039, p.3
`
`

`

`Profile 3
`
`Profile 93
`
`Column weight Fraction of columns Row weight Fraction
`1
`1
`3
`6
`Column weight Fraction of columns Row weight Fraction
`3
`1
`7
`11/12
`9
`1/12
`
`Table 1: The two profiles studied in this paper
`
`3 Comparing Poisson, 'super-Poisson' and 'sub-Poisson'
`constructions
`
`3.1 Profiles and constructions studied m this paper
`
`3.1.1 Regular codes: 3 and 33
`As our baseline we study regular Gallager codes with weight per column exactly t = 3 and
`weight per row exactly t,. = 6. \Ve construct parity check matrices satisfying this profile
`from permutation matrices in two ways, labelled '3' and '33', shown diagrammatically in
`the upper panels of figure 2. In the figures, a square containing an integer (for example,
`'3') denotes the superposition inside that square of that muuber of random permutation
`matrices. The matrices are generated at random subject to the constraint that no two
`non-zero entries coincide.
`
`3.1.2
`
`Irregular codes: 93p, 93a, 93x and 93y
`
`We chose the profile '93' shown in table 1. It has columns of weight 9 and of weight 3: all
`rows have weight 7. 1\ote that this profile only differs from the regular profile '3' in that
`some extra 1s arc added to /2 of the columns. \Ve emphasize that this profile has not
`been carefully optimized, so the results of this paper should not he taken as describing
`the best that can he done with irregular binary Gallager codes. \Ve chose this profile
`because it lends itself to interesting experiments.
`\Ve will refer to the bits that connect to 9 checks as 'elite' bits. \Ve use four different
`constructions that match this profile, named as follows. These constructions are depicted
`diagrammatically in the upper panels of figure 2.
`
`Poisson: 93p. In this construction, while most checks will connect to one or two elite
`bits, a fraction of them will connect to more than two elite bits, and some will
`connect to none.
`
`Sub-Poisson: 93a. This construction allocates exactly one or two elite bits to each
`check.
`
`Super-Poisson: 93x and 93y are respectively moderately and very super-Poisson. In
`93y, one third of the checks are connected to four elite bits, one third are connected
`to one, and one third are connected to none.
`
`Hughes, Exh. 1039, p.4
`
`

`

`
`
`
`®®®®®®
`oooooo
`oooooo
`
`1
`1
`
`1 1 1
`
`1 1 1
`
`
`
`1 1 1
`
`
`
`1 1 1
`
`
`
`1 1 1
`
`
`
`1 1 1
`
`
`
`
`
`1
`1
`
`
`
`
`
`
`
`0.1 _—
`0.1
`
`z:
`
`0.01 _—
`0.01
`
`0.001 _—
`
`0.001
`
`0.0001 _—
`0.0001
`
`
`
` 1
`
`—_
`
`—_
`
`"—
`
`—_
`
`0.1
`0.1
`
`0.01
`0.01
`
`0.001
`
`0.001
`
`0.0001
`0.0001
`
`0.1 _—
`0.1
`
`0.01 _—
`0.01
`
`0.001 _—
`
`0.001
`
`—_
`
`—_
`
`—_
`
`l
`
`4 4
`
`1 1
`
`2 1
`
`1 2
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`3 4
`
`2 1
`
`1 2
`
`1
`
`
`3
`3
`3
`3
`.
`9
`<..... 7"",
`<- - - - - 7 - - - - ->
`1
`1
`
`
`
`—_
`
`
`G)6)®@'
`
` ®gC900 r@@@@@@ @
` @®@®@®
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`,ooo
`,ooo
`
`
`
`
`
`
`
`
`
`-
`
`1 2 1 2 1 2
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`1
`
`0.1
`0.1
`
`0.01
`0.01
`
`0.001
`0.001
`
`0.0001 -
`0.0001
`
`1
`0.0001 _—
`0.0001
`
`1.5
`1.4
`1.3
`1.2
`1.1
`1
`1.5
`1.4
`1.3
`1.2
`1.1
`1
`1.5
`1.4
`1.3
`1.2
`1.1
`1.5
`1.4
`1.3
`1.2
`1.1
`1
`1.5
`1.4
`1.3
`1.2
`1.1
`1
`1.5
`1.4
`1.3
`1.2
`1.1
`1
`
`93a
`93x
`93y
`
`
`
`Q
`
`6}
`®
`®
`®
`1
`1
`
`
`
`®®®®©
`®®®
`CK?
`1
`1
`
`1
`®
`®
`®®@
`CKKW
`1
`1
`
`
`1
`
`1
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`1
`
`0.1
`0.1
`
`0.01
`0.01
`
`0.001
`0.001
`
`0.0001
`0.0001
`
`0.1
`0.1
`
`0.01
`0.01
`
`0.001
`0.001
`
`0.0001
`0.0001
`
`1
`1
`
`1.1
`1.1
`
`1.2
`1.2
`
`1.3
`1.3
`
`1.4
`1.4
`
`1.5
`1.5
`
`1
`1
`
`1.1
`1.1
`
`1.2
`1.2
`
`1.3
`1.3
`
`1.4
`1.4
`
`1.5
`1.5
`
`1
`1
`
`1.1
`1.1
`
`1.2
`1.2
`
`1.3
`1.3
`
`1.4
`1.4
`
`1.5
`1.5
`
`Figure 2: Upper panels: constructions of regular and irregular codes. Lower panels:
`performance of these codes. The construction types shown are regular, (3, 33), Poisson
`(93p), subiPoisson (93a), superiPoisson (93X), and superiPoisson (93y).
`Notation for upper panels for all constructions except 93p: an integer represents a number
`of permutation matrices superposed on the surrounding square. Horizontal and vertical
`
`lines indicate the boundaries of the permutation blocks. Notation for the Poisson con—
`
`struction 93p:
`
`integers ‘37 and ‘97 represent column weights. The integer ‘7’ represents
`
`the row weight.
`
`Lower panels show the performance of several random codes of each construction. Vertical
`axis: block error probability. Horizontal axis: Eb/NO in dB. All codes have N : 9972,
`and K = M : 4986.
`
`All errors were detected errors, as is usual with Gallager codes.
`
`Hughes, Exh. 1039, p. 5
`
`

`

`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`3
`93p
`93y
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`3
`33
`93a
`93p
`93x
`93y
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`checks
`
`bits
`
`checks
`
`bits
`
`

`

`33
`93y
`
`25000
`25000
`
`20000
`20000
`
`15000
`15000
`
`10000
`10000
`
`5000
`
`10000
`10000
`
`1000
`1000
`
`100
`100
`
`1°
`10
`
`1
`
`0.1
`
`5000
`
`50
`
`40
`
`30
`
`20
`
`10
`
`0
`
`(a)
`
`1
`1
`
`11
`12 13 1A 15
`1.1 1.2 1.3 1.4 1.5
`'
`
`0
`
`0
`
`(b)
`
`10
`
`20
`
`30
`
`40
`
`50
`
`10
`
`(c)
`
`100
`
`(a) Comparison of irregular 93y with regular 33 code. Vertical axis: median
`Figure 4:
`number of iterations. Horizontal: Eb/NO in dB. (b) Histogram of number of iterations
`for 93y code at Eb/NO : 1.4.
`(c) Log/log plot of iterations histogram showing that the
`tail of the distribution is well approximated by a power law. The straight line has slope
`—8.5. Above 50, iterations were binned into intervals of 5.
`
`constructed codes the minimum distance increases linearly with the blocklength, for
`almost all codes [4]
`We discard the two codes with error floors in the subsequent comparisons.
`
`3.2.3 Comparison of constructions
`
`The six families are compared with each other in figure 3. There are no detectable
`
`differences between the regular codes 3 and 33. There is a clear ranking of the other
`
`constructions, as follows:
`
`3 < 93a < 93p < 93x < 93y
`
`Thus we find that, at least for the 93 profile, subiPoisson constructions are inferior to
`
`Poisson constructions, and superiPoisson constructions are significantly superior. In the
`
`case of 93y we see an improvement of about 0.05dB.
`
`3.2.4 Decoding times
`
`Not only do these irregular codes outperform the regular codes, they require fewer it—
`erations as illustrate in figure 4(a) which compares the median number of iterations of
`the irregular code 93y and the regular code 33. Note that 93y requires 7/6 times more
`operations per iteration due to the increased weight of the matrix, so the total decoding
`times are similar.
`
`Figures 4(b) and (c) show that the distribution of decoding times is heavy tailed. At
`Eb/NO : 1.4 the tail is well approximated by the power law: P(T) N T_8'5, where T is
`the number of iterations. At Eb/NO = 1.2 the distribution is heavier tailed, and we have
`13(7) N 7’5.
`
`Hughes, Exh. 1039, p. 7
`
`

`

`~-----N----~
`J(
`
`H
`
`M
`
`B
`
`-c-
`
`Encoding procedure:
`
`Bits t 1 ••• tg are defined to be source bits.
`
`Bits tK+l ... i.t-.i-i\1< are Het in Hequence, using
`the mth parity check to determine tr<+m·
`
`Bits fcv-JVI<+l ... (v are set equal to:
`c- 1Bt*mod2
`(tl ... fN-IVI<J" and c-l is
`where t* =
`the inverse of C in rnodulo 2 aritlnnetie.
`
`This costs (N- M<)t, computational
`operations, where tr
`is the typical
`weight per row.
`
`c- 1 can be stored in M~ bits of mem(cid:173)
`ory. The product Bt' can be com(cid:173)
`puted in M<tr computational opera(cid:173)
`tions, and the multiplication by c-l
`takes M~ operations.
`
`Figmc 5: Cppcr pand: General form of a fast encoding Gallager code. Horiwnt.al stripes
`indicate low weight rows. The diagonal line is a line of ls. The matrices B and C arc of
`dimension 1'vi< x (N- AI<) and JI< x 1'vi< respectively. Lower panel: The fast encoding
`method to generate a codeword, and its computational cost, assuming an appropriate
`representation of the sparse matrix.
`
`3.2.5 Unequal error protection
`
`\Vc can compare the bit error rate of elite bits with that of standard bits. \Vc find that
`when decoding fails. elite bits arc more likely than standard bits to be correctly decoded.
`In the case of construction 93x we found that at Eb/ N0 = 1.3dB the probability of an
`elite bit being in error, given that the block was incorrectly decoded, was 0.012 whereas
`standard bits had an error rate of 0.065. Differences remain at small Eb/ N 0 • For example,
`at Eb/ N 0 = 0. 7dl3 the error rates are 0.035 and 0.097.
`
`4 Fast-encoding Gallager codes
`
`One of the possible drawbacks of Gallager codes is that their encoding time generally
`scales as N 2
`• Inspired by Spielman's [11] work, we have investigated constructions of Gal(cid:173)
`lager codes whose profiles arc similar to or identical to the 3 and 93 profiles above, but
`which arc fast. encoding. The general form of parity check matrix for a fast encoding Gal(cid:173)
`lager code is shown in figure 5. The parity check matrix has an almost lower triangular
`structure which allows all but a small number !VI< of the parity bits to be computed using
`sparse operations. The final AI< parity bits can be computed in AI~ binary operations.
`
`Hughes, Exh. 1039, p.8
`
`

`

`OJ
`
`
`1
`1
`1
`1
`1
`1
`
`
`1
`1
`2
`2
`
`
`
`G}
`2
`2
`1
`2
`1
`1
`1
`
`2
`2
`
`
`
`
`1
`1
`2
`1
`1
`2
`1
`
`2
`
`3
`
`4 4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` -®®® G} G} @69
`
`
`1 1
`
`©®
`2
`3
`
`1 1 1
`
`1
`
`1
`
`0.1
`0.1
`
`0.01
`0.01
`
`0.001
`0.001
`
`0.0001
`0.0001
`
`-
`
`-
`
`-
`
`0.1
`0.1
`
`0.01
`0.01
`
`0.001
`0.001
`
`0.0001
`0.0001
`
`1
`1
`
`1.1
`1.1
`
`1.2
`1.2
`
`1.3
`1.3
`
`1.4
`1.4
`
`1.5
`1.5
`
`1
`1
`
`1.1
`1.1
`
`1.2
`1.2
`
`1.3
`1.3
`
`1.4
`1.4
`
`1.5
`1.5
`
`(a) Upper panels: construction methods 13 and 193y. As in figure 2, an
`Figure 6:
`integer represents a number of permutation matrices superposed on the surrounding
`square. A diagonal line represents an line of 1s. Horizontal and vertical lines indicate
`the boundaries of the permutation blocks. Lower pictures: Variability of performance
`among 13 and 193y codes. Vertical axis: block error probability. Horizontal axis: Eb/NO
`in dB. All codes have N : 9972, and K : M : 4986.
`(b) Example of a parity check matrix with N = 144 made using construction 193y.
`
`Hughes, Exh. 1039, p. 9
`
`

`

`1
`
`0.1
`0.1
`
`0.01
`0.01
`
`0.001
`0.001
`
`0.0001
`0.0001
`
`-
`
`13 — _
`l3
`3
`
`—_
`
`
`
`
`1
`
`0.1
`
`0.01
`0.01
`
`0.001 _
`0.001
`
`0.0001 _
`0.0001
`
`l93y
`93y
`
`(a)
`
`1
`1
`
`1.1
`1.1
`
`1.2
`1.2
`
`1.3
`1.3
`
`1.4
`1.4
`
`1.5
`1.5
`
`(b)
`
`1
`1
`
`1.1
`1.1
`
`1.2
`1.2
`
`1.3
`1.3
`
`1.4
`1.4
`
`1.5
`1.5
`
`(b) Comparison of 19337 with
`(a) Comparison of 13 with an ordinary 3 code.
`Figure 7:
`the best superiPoisson 93y code. Vertical axis: block error probability. Horizontal:
`Eb/NO/dB.
`
`If M< were as small as x/M then the codes would be linearitime encodeable.
`We introduce two constructions, 13 and 19337 (‘1’ for linear), shown diagrammatically
`in figure 6(a). Construction 13 has profile identical to construction 3. Construction 19337
`has a profile identical to the 93 codes, and is most similar to 93y. figure 6(b) shows an
`example of a matrix made using construction 193y and Figure 6(a) shows the variability
`of performance of these codes.
`
`Figure 7 shows that the fastiencoding codes have almost the same performance as
`
`the ordinaryiencoding codes.
`
`5 Discussion
`
`The detection of error floors in some Gallager codes reminds us that it is a good idea,
`though not essential,
`to avoid cycles of length 4 when building these codes, as was
`standard practice in [3, 8, 6]. This is not so easy to enforce in irregular Gallager codes
`with high weight columns, but the present results indicate that what is really important
`is to ensure that no pairs of low weight columns (with weights less than 4) have overlaps
`greater than one.
`
`The improvement of 0.05dB of the superiPoisson construction compared with a Pois—
`
`son construction of irregular codes may not be viewed as practically useful, but we think
`
`it is important to be aware of all the methods available for enhancing code performance,
`
`especially when these methods involve no added cost at the encoder or decoder. It will be
`
`interesting to see how beneficial the superiPoisson concept is for other irregular profiles.
`We are currently investigating the creation of irregular Turbo codes which make use of
`superiPoisson constructions (work in progress with B. J. Frey).
`The discovery that we can make fastiencoding Gallager codes whose performance is
`
`just as good as ordinary Gallager codes may have immediate practical importance for
`
`mobile communications where computer power consumption must be minimized. Both
`
`the memory requirements and the CPU requirements at the encoder of our fastiencoding
`codes are substantially smaller. The static memory required for encoding is proportional
`to ME +MtT, where 25,. is the typical weight per row in the parity check matrix. This com—
`
`Hughes, Exh. 1039, p. 10
`
`

`

`pares to M ( N - i\!1) for storing the generator matrix. The particular constructions used
`in this paper would allow encoding using roughly thirty-six times fewer computational
`operations, since we chose AI< = AI /6. This reduction would be more than sufficient
`to cancel out the factor of fourteen encoding complexity disadvantage with respect to
`Turbo codes of the example mentioned in [10]. The smaller the ratio M<f1'vi. the greater
`the reduction in encoding cost. It will be interesting to investigate how small AI< can be
`made without deterioration in performance.
`
`References
`
`[1] M. C. Davey and D. J. C. MacKay. Low density parity check codes over GF(q).
`Proceedings of the 1998 IEEE Infonn.a.t·ion Theory Wmkshop. IEEE, June 1998.
`
`In
`
`[2] M. C. Davey and D . .J. C. MacKay. Low density parity check codes over GF(q). IEEE
`Communications Letters, 2(6):165-167, June 1998.
`
`[3] R. G. Gallager. Low density parity check codes. IRE Tm.ns. Info. Theory, IT-8:21 28, Jan
`1962.
`
`[4] R. G. Gallager. Low Density Parity Check Codes. Number 21 in Research monograph
`series. MIT Press, Cambridge, Mass., 1963.
`
`[5] M. G. Luby, M. Mit7.emnacher, M. A. Shokrollahi, and D. A. Spielman. Improved low(cid:173)
`denHity parity check codes nHing irregular graphs and belief propagation. In Proceeding,<;
`of the IEEE International Symposium on Informati on Theory (!SIT), page 117, 1998.
`
`[6] D. J. C. MacKay. Good error correcting codes based on very sparse matrices.
`Transactions on Infonnation Theory, 45(2):399-431, 1999.
`
`IEEE
`
`[7] D. J. C. MacKay and Il. M. Neal. Good codes based on very sparse matrices. In Colin
`Boyd, editor, Oryptogra.phy and Coding. 5th IMA Confe·rence, nmnber 1025 in Lecture
`Notes in Computer Science, pages 100-111. Springer, Berlin, 1995.
`
`[8] D. J. C. MacKay and R. M. Neal. Near Sharmon limit performance of low density parity
`check codes. Electmnics Letters, 32(18):1645-1646, August 1996. Reprinted Electmnics
`Letters, 33(6):457-458, March 1997.
`
`[9] R. J. McEliece, D. J. C. MacKay, and J.-F. Cheng.
`'I\nhl decoding as an instance of
`Pearl's 'belief propagation' algorithm. IEEE Journal on Selected Areas in Communications,
`16(2):140 152, 1998.
`
`[10] V. Sorokine, F. R. Kschischang, and S. Pasupathy. Gallager codes for CDMA applications
`II: Implementations, complexity and system capacity. IEEE Trans. Communications, 1998.
`submitted.
`
`[11] D. A. Spielman. Linear-time encodablc and decodable error-correcting codes. IEEE Trans(cid:173)
`actions on Infonn.a.t·ion Theory, 42(6.1):1723 1731, 1996.
`
`Hughes, Exh. 1039, p. 11
`
`