`
`1449
`
`
`
`Transactions Letters
`
`----------------------------
`
`Comparison of Constructions of Irregular Gallager Codes
`
`
`
`
`
`David J. C. MacKay, Simon T. Wilson. Member. IEEE. and Matthew C. Davey
`
`Associate
`
`UJ
`
`0.1 .-�-�-�-�----�
`
`low-density parity check codes whose perfor
`Abstract-The
`u Reg
`
`
`mance is closest to the Shannon limit are ·'Gallager codes"
`"' .0 0.01
`Reg
`c GF(16) \
`
`
`
`based on irregular graphs. We compare alternative methods for
`GF(2)
`
`
`
`constructing these graphs and present two results. First, ,,-e find
`0.001
`lrreg\
`GF(2)
`
`a ·'super-Poisson" construction which gives a small improvement
`e
`w ii§ 0.0001
`
`
`
`in empirical performance over a random construction. Second,
`
`
`whereas Gallager codes normally take _yl time to encode,
`we
`<ii .g·c.E
`18·05
`
`
`
`
`
`inve ligate constructions of regular and irregular Gallager codes
`T
`lrreg GF(8)
`
`
`
`that allow more rapid encoding and have smaller memory re
`18·06
`
`
`quirements in the encoder. We find that these "fast encoding"
`-0.2 0 0.2 0.4 0.6 0.8
`
`
`Gallager codes have equally good performance.
`Eb/No (dB)
`Index Terms--Channel coding, error correction coding, Gauss
`
`
`
`
`
`ra1e 1/4 left-right: irregular Fig. I. Empirical results for Gaussian channel.
`
`
`
`
`
`
`
`ian channels, graph theory, iterative probabilistic decoding, ran
`
`
`LDPC. G F( 8) blocklenglh 24 000 bits: JPL Turbo. blocklength 65 536 bi1,:
`dom codes.
`
`
`
`regular LDPC. GF(lG). blockleng1h 24448 bi1s: irregular LDPC. GF(2).
`
`
`
`block.Jenglh 6 4000 bil,: regular LDPC. GF(2). blocklc!nglh 40000 biis.
`
`(Reproduced from [I].)
`I.INTRODUCTION
`
`
`LLAGER codes 131, 141 are low-density parity check
`probability ofan irregular code over C F(8) with bit-error
`
`
`
`
`
`
`codes cons1ruc1ed at random subject to constraints on the
`10-� at Eb/ No
`
`-0.05 dB [II. In comparing this code with
`
`weight of each row and of each column. The original
`
`
`the rate 1/4 turbo-code shown by the dotted line. the following
`
`
`
`Gallager codes have very sparse random parity check matrices
`
`
`
`
`points should be noted. I) The transmitted blocklength of the
`
`with uniform weigh1 t per column and t,. per row. (We will
`
`
`
`
`irregular Gallager code is only 24 000 bits, whereas that of the
`
`
`also use the term "regular" for codes 1hat have nearly uniform
`
`
`
`turbo-code is 65 536 bits. 2) The errors made by the Gallager
`
`
`
`weight columns and rows-for example. codes which have
`
`
`
`
`codes were all detected errors, whereas turbo-codes make
`
`
`some weight 2 columns and some weight 3 columns.) These
`
`
`
`
`undetected errors at high signal-to-noise ratio. This difference
`
`
`codes are asymptotically good and can be practically decoded
`
`
`
`is not caused by a difference in the decoding algorithm: both
`
`
`
`
`with Gallager·s sum-product algorithm giving near Shannon
`
`
`
`codes are decoded by the sum-product algorithm [9]. Turbo
`
`
`limit performance when large block lengths are used [6)-[8].
`
`
`codes make undetected errors because
`
`
`Regular Gallager codes have also been found to be competitive
`
`
`For Gallager codes, the rate of occurrence of
`
`
`
`codes for short block-length code-division multiple-access
`
`
`
`undetected errors is ext y s cause they have good
`
`(CDMA) applications I 101.
`
`
`withdistance propertiesl\).inimum distanc cales linearly
`
`
`
`Recent advances in the performance of Gallager codes
`
`the blocklength) � all our experime with Gallager
`
`
`are summarized in Fig. I. The rightmo t curve hows the
`tha� OO and c umn weight at
`code of block n'ifti greater
`
`
`performance of a regular binary Gallager code with rate 1/4.
`
`� errors have �r occurred.
`least 3. undete
`
`
`The best known binary Gallager codescodes are irregular
`T�e �xcelle
`� rforma�ce o� egular
`Gal� r codes is the
`
`
`weight perwhose parity check matrice · have 110111111ifor111
`
`
`for � paper, 111 wltich we explo ays of further
`mouvauon
`
`column [5]; the performance of one such code is shown by
`
`enhancing the codes. �
`
`
`the second curve from the right. The best known Gallager
`�
`codes of � y. Mitzen Shokrollahi,
`The irregular
`
`
`
`codes of all are Gallager codes defined over finite fields (,' F( q)
`and Spie_lman 15 J ve parity
`ch_eck mat� ith both nonuni
`
`
`[ l J. [2]. The remaining two solid curves in Fig. I show the
`
`
`
`form weight per row d nonuniform we t per column. lt has
`
`
`
`perfom1ance of a regular Gallager code over G'F(rn) 121 and
`not yet been established of these nonuniformities
`
`
`are desirable. Jn our experience with codes for noisy channels,
`
`
`Paper approved by S. B. Wicker, !he Editor for Coding Theory amJ
`
`
`
`performance is more sensitive to the distribution of column
`
`
`
`
`Technique, of 1he IEEE Communication, S0cic1y. Manw,cripl received
`
`
`
`Augu5t 11. 1998: revised January 27. 1999. Thi, paper wa, presented in
`
`
`
`
`weights. In this paper, we concentrate on irregular codes with
`
`
`
`
`pan al the t 998 Allenon Conference on Communica1iorn,, Control. and
`
`the weight per row as uniform as possible.
`
`
`
`Computing. Allenon Hou,e. IL. September 1998.
`
`We can define an irregular Gallager code in two steps.
`
`
`
`
`The au1hor, are wi1h 1he Depanment of Physics. University of Cam
`
`
`
`
`
`the desired numberthat describes First, we select a profile
`
`
`
`bridge, Cambridge CB3 OHE. U.K. (e-mail: mackay@mrao.cam.ac.uk;
`
`,1w I t@mrao.cam.ac.uk; mcdavey@mrao.cam.ac.uk).
`
`
`of columns of each weight and the desired number of rows of
`
`
`
`Publisher hem Identifier S 0090-6778(99)07784-3.
`
`regular
`
`=
`
`GA
`
`codewords.
`
`they ha,•e low-weight
`
`
`
`0090--0778/99$10.00 © 1999 IEEE
`
`Apple 1002
`
`
`
`
`
`
`
`
`
`
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL, 47, NO. 10, OCTOBER 1999
`
`93p
`
`0.001
`
`0.0001
`
`0.01
`
`0.001
`
`0.0001
`
`1
`
`130642
`
`td:
`
`14 15
`
`1
`
`Lt 2 GS: he OS
`
` 1450
`
`0.1
`
`0.1 0.01
`
`
`
`
`
`
`93a
`93%
`
`
`AST ASAI
`WICVIC
`te
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`[Zz
`(1
`
`(1)
`
`(1):
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`UA WS ta hs
`
`i |
`
`No
`
`133- 14
`
`15
`
`1
`
`vA
`
`1.2
`
`13
`
`ta NS
`
`Fig. 2. Upper panels: constructions of regular and irregular codes. Lower panels: performance of these codes. The construction types shownare regular,
`(3, 33), Poisson (93p), sub-Poisson (93a), super-Poisson (93x), and super-Poisson (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 construction 93p: integers “3” and “9” 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: E),/.Vo in dB. All codes have
`N = 9972 and AK = M = 4986. All errors were detected errors, as is usual with Gallager codes.
`
`each weight. The parity check matrix of a code can be viewed
`as defining a bipartite graph with “bit” vertices corresponding
`to the columns and “check” vertices corresponding to the
`rows. Each nonzero entry in the matrix corresponds to an edge
`connecting a bit to a check. The profile specifies the degrees
`of the vertices in this graph.
`Second, we choose a construction method, thatis, a pseudo-
`random algorithm for putting edges between the vertices in a
`
`way that satisfies the constraints. (In the case of nonbinary
`Gallager codes, we also need to choose an algorithm for
`assigning values to the nonzero entries in the matrix.)
`This paper has two parts. In the first part (Section III), we
`compare alternative construction methodsfor a fixed profile in
`order to find out whether the construction method matters. In
`the second part (Section IV), we examine regular and irregular
`constructions which lend themselves to rapid encoding. One
`
`
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL, 47, NO. 10,OCTOBER 1999
`
`motivation for this second study is that the only drawback of
`regular Gallager codes compared to turbo-codes for CDMA
`applications appears to be their greater encoding complexity
`[10].
`In the experiments presented here, we study binary codes
`with rate 1/2 and blocklength aboutNV = 10000. We 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 logarithm
`of the block error probability p defined. Thus, when we
`observe r failures out of 7 trials, px = p exp(+ojog p) where
`=
`J/(n—1r)/(rn).
`Nog p
`
`II]. CONSTRUCTIONS
`
`We compare the following methods.
`Poisson: The edges are placed “completely at random,”
`subject to the profile constraints and the rule that you cannot
`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 to its weight, then make a
`similar list of all the rows in the matrix, each row appearing
`with multiplicity equal to 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 cycles of length 4 in the graph. (Similar
`to construction 1A in [8].) A second variation requires that the
`graph have no cycles of length less than some |. (Similar to
`construction 1B in [8].) This constraint can be quite hard to
`enforce if the profile includes high weight rows or columns,
`Permutations: We can build parity check matrices by su-
`perposing random permutation matrices [4]. The convenience
`of this method dependsonthe profile. There are many ways of
`laying out these permutation matrices to satisfy a given pro-
`file. We will distinguish “super-Poisson” and “sub-Poisson™
`constructions.
`
`*
`
`*
`
`In a super-Poisson construction, the distribution of high
`weight columns per
`row has greater variance than a
`Poisson distribution.
`
`the distribution of high
`In a sub-Poisson construction,
`weight columns per row has smaller variance than a
`Poisson distribution.
`
`III. COMPARING POISSON, SUPER-POISSON,
`AND SUB-POISSON CONSTRUCTIONS
`
`A. Profiles and Constructions Studted in this Paper
`
`!) Regular Codes—3 and 33: As our baseline, we study
`regular Gallager codes with weight per column exactly ¢ = 3
`and weight per row exactly ¢, = 6. We construct parity check
`matrices satisfying this profile from permutation matrices in
`two ways, labeled “3” and “33,” shown diagrammatically in
`the upper panels of Fig. 2. In the figure, a square containing
`
`1451
`
`0.01
`
`0.001
`
`0.0001
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`variability of performance within each ensemble. All codes
`
` 0.1
`
`1
`
`LY Me
`
`1a
`
`14 Ss
`
`1 42°48)
`
`he
`
`he
`
`(a)
`
`(b)
`
`(a) Comparison of one representative of each of the constructions: 3
`Fig. 3.
`(regular), 93p (Poisson) and 93y (super-Poisson). (b) Representatives of all
`six constructions in Fig. 2. Vertical axis: block error probability. Horizontal
`axis: E;,/No in dB.
`
`TABLE |
`THE TWO PROFILES STUDIED IN THIS PAPER
`
`Column weight Fraction of columns Row weight Fraction
`
`Profile 3
`7 SS 6
`1
`
`Profile 93
`Column weight Fraction of columns
`Row weight
`Fraction
`3
`11/12
`7
`1
`9
`1/12
`
`an integer (for example, 3”) denotes the superposition inside
`that square of that number of random permutation matrices.
`The matrices are generated at random subject to the constraint
`that no two nonzero entries coincide.
`chose
`2) Irregular Codes—93p,. 93a, 93x, and 93y: We
`the profile “93” shown in Table I. It has columns of weight
`9 and of weight 3; all rows have weight 7. Note that
`this
`profile only differs from the regular profile “3” in that some
`extra 1’s are added to 1/12 of the columns. We emphasize that
`this profile has not been carefully optimized, so the results of
`this paper should not be taken as describing the best that can
`be done with irregular binary Gallager codes. We chose this
`profile because it lends itself to interesting experiments.
`We will refer to the bits that connect to nine checks as
`“elite” bits. We use four different constructions that match this
`profile, named as follows. These constructions are depicted
`diagrammatically in the upper panels of Fig. 2.
`Poisson—93p:
`In this construction, while most checks will
`connect to one or twoelite 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.
`
`B. Results
`
`con-
`each
`1) Variability Within Each Construction: For
`struction, we created several codes in order to assess the
`
`
`
`25000
`
`20000
`
`15000
`
`10000
`
`5000 Tt
`
`jal
`
`12 18 14 1.5
`
`(a)
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL, 47, NO. 10, OCTOBER 1999
`
` (b)
`
`
`Fig. 4,
`(a) Comparison of irregular 93y with regular 33 code. Vertical axis: median number ofiterations. Horizontal: E,/No in dB. (b) Histogram of
`numberof iterations for 93y code at E,/No = 1.4. (c) Log/log plot ofiterations histogram showing thatthe 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.
`
`
`
`Encoding procedure:
`Bits ¢;...t, are defined to be source bits.
`
`Bits te4i...tn-m. are set in sequence, using
`the mth parity check to determine ty 4n-
`
`Bits tv-me41...tw are set equal to:
`C™'Bt* mod 2
`
`where t” = (t1...t~-me)' and Co! is
`the inverse of C in modulo 2 arithmetic.
`
`This costs (V—M-.)t, computational
`operations, where t,
`is
`the typical
`weight per row.
`
`C™! can be stored in M2 bits of mem-
`ory. The product Bt" can be com-
`puted in Met, computational opera-
`tions, and the multiplication by C~!
`takes M2? operations.
`
`
`
`studied were of rate 1/2, with blocklength N = 4986. The
`results are shown in Fig. 2. We see no significant variability
`among the 3,33,93i (Poisson) or 93a (sub-Poisson) codes.
`But among the super-Poisson codes, 93x and 93y, there is
`some variability with some codes showing an error floor.
`2) Explanation of Error Floors:
`\n both cases,
`the error
`floor has a simple cause. The most frequent error under these
`conditions is a reconstructed transmission which differs from
`the correct codewordin exactly three bits—the samethreebits
`every time. These bits, which have weight 3 columns in the
`parity check matrix, are connected to just five checks with the
`topology shown below
`sbke
`a
`a
`a
`a
`a
`checks _ApSNM
`Ml ae. | f
`
`bits O@@O0eOO
`
`peoltoe (1)
`
`If the three bits shaded grey are flipped into the wrong
`state, then the syndrome vector changes sign in the fifth check
`only. The sum—product algorithm is unable to extricate itself
`from this state. As the block length of the code is increased,
`the probability of this topology’s occurrence falls. It
`is also
`possible to modify the construction algorithm for Gallager
`codes such that cycles of length 4, like this are forbidden (as
`
`checks 4.3.9%.
`
`i WA ak
`bits O@@O0O
`
`(2)
`
`in construction 1A of [8]). This modification is sufficient to
`prevent the topology shownin (1) from occurring. In principle,
`it is possible for a code to have a minimumdistance of 4 even
`when the minimum cycle length is 6. However, for randomly
`constructed codes,
`the minimum distance increases linearly
`with the blocklength, for almost all codes [4].
`Wediscard the two codes with error floors in the subsequent
`comparisons.
`are
`families
`six
`3) Comparison of Constructions: The
`compared with each other in Fig. 3. There are no detectable
`differences between the regular codes 3 and 33. There is a
`
`Fig. 5. Upper panel: general form ofa fast-encoding Gallager code. Hon-
`zontal stripes indicate low-weight rows. The diagonalline is a line of 1's.
`The matrices B and C are of dimension Af- x (N — \f~) and Me x Me,
`respectively. Lower panel: the fast encoding method to generate a codeword
`and its computational cost, assuming an appropriate representation ofthe
`sparse matrix.
`
`clear ranking of the other constructions, as follows:
`
`3.< 98a < 93p < 93x < 93y.
`
`Thus, we find that at least for the 93 profile, sub-Poisson
`constructions are inferior to Poisson constructions, and super-
`Poisson constructions are significantly superior. In the case of
`93y, we see an improvement of about 0.05 dB.
`4) Decoding Times: Not only do these irregular codes out-
`perform the regular codes,
`they require fewer iterations as
`illustrated in Fig. 4(a), which compares the median numberof
`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.
`Fig. 4(b) and (c) showsthat the distribution of decoding
`times is heavy tailed. At £,/No = 1.4,
`the tail
`is well
`approximated by the power law: P(r) ~ 7~*°, where 7 is
`the numberofiterations. At E;,/No = 1.2, the distribution is
`heavier tailed, and we have P(r) ~ 77°.
`
`
`
`0.1
`
`0.01
`
`0.001
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47, NO. 10, OCTOBER 1999
`
`
`
`12
`
`(b)
`
`0.0001
` 1A
`
`
`1453
`
`12°13 14
`
`1.5
`
`93y. Fig. 6(b) shows an example of a matrix made using
`
`(a) Upper panels: construction methods 13 and 193y. As in Fig. 2, an integer represents a number of permutation matrices superposed on the
`Fig. 6.
`surrounding square. A diagonal line represents a line of 1's. Horizontal and vertical lines indicate the boundaries of the permutation blocks. Lower picture:
`variability of performance among 13 and 193y codes, Vertical axis: block error probability. Horizontal axis: E,,/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.
`
`5) Unequal Error Protection: We can compare the bit-
`error rate of elite bits with that of standard bits. We find that
`when decoding fails, elite bits are more likely than standard
`bits to be correctly decoded. In the case of construction 93x,
`we found that at £,/No = 1.3 dB,
`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 £,/No. For example,at
`E,,/No = 0.7 dB, the error rates are 0.035 and 0,097.
`
`TV. FAST-ENCODING GALLAGER CODES
`
`Oneof the possible drawbacks of Gallager codesis that their
`encoding time generally scales as N*. Inspired by Spielman’s
`work [11], we have investigated constructions of Gallager
`
`codes whose profiles are similar to or identical to the 3 and
`93 profiles above, but which are fast-encoding. The general
`form of parity check matrix for a fast-encoding Gallager code
`is shown in Fig. 5. The parity check matrix has an almost
`lower-triangular structure which allows all but a small number
`M_- ofthe parity bits to be computed using sparse operations.
`The final Me parity bits can be computed in M2 binary
`operations. If M~ were as small as VM,then the codes would
`be linear-time encodable.
`We introduce two constructions, 13 and 193y (“1” for
`linear), shown diagrammatically in Fig. 6(a). Construction 13
`has profile identical to construction 3. Construction 193y has
`a profile identical
`to the 93 codes and is most similar to
`
`
`
`1454
`
`1
`
`o4
`
`0.01
`
`0.001
`
`0.0001
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`
`
`1.
`
`We
`
`ie eee ee
`
`1
`
`VW
`
`ae ns ud ts
`
`(a)
`
`(b)
`
`(a) Comparison of 13 with an ordinary 3 code. (b) Comparison
`Fig. 7.
`of 193y with the best super-Poisson 93y code. Vertical axis: block error
`probability. Horizontal: FE), /No/dB.
`
`construction 193y, and Fig. 6(a) shows the variability of
`performance of these codes.
`Fig. 7 shows that the fast-encoding codes have almost the
`same performance as the ordinary-encoding codes.
`
`V. 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], [6], and [8]. 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.05 dB of the super-Poisson con-
`struction compared with a Poisson 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 super-Poisson concept is
`for other irregular profiles. We are currently investigating the
`creation of irregular turbo-codes, which make use of super-
`Poisson constructions (work in progress with B. J. Frey).
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47, NO. 10, OCTOBER 1999
`
`The discovery that we can make fast-encoding Gallager
`codes whose performanceis 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 fast-encoding codes are
`substantially smaller. The static memory required for encoding
`is proportional to AJ? +Mt,., wheret, is the typical weight per
`row in the parity check matrix. This compares to M(.N — AM)
`for storing the generator matrix. The particular constructions
`used in this paper would allow encoding using roughly 36
`times fewer computational operations, since we chose M2 =
`M/6. This reduction would be more than sufficient to cancel
`out the factor of 14 encoding complexity disadvantage with
`respect to turbo-codes of the example mentioned in [10]. The
`smaller the ratio M/-/M, the greater the reduction in encoding
`cost.
`It will be interesting to investigate how small MM. can
`be made without deterioration in performance.
`
`REFERENCES
`
`[1] M. C. Davey and D. J. C. MacKay, “Lowdensity parity check codes
`over GF(q),” in Proc. IEEE 1998 Information Theory Workshap, June
`1998, pp. 70-71.
`
`. “Low density parity check codes over GF(q).” JEEE Commun.
`Lert., vol. 2, pp. 165-167, June 1998,
`[3] R. G. Gallager, “Low density parity check codes,” JRE Trans. Inform.
`
`Theory, vol. IT-8, pp. 21-28, Jan. 1962.
`, Low Density Parity Check Codes (Research Monograph Series
`no. 21). Cambridge, MA: MIT Press, 1963.
`[5] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman,
`“Improved low-density parity-check codes using irregular graphs and
`belief propagation,” in Proc. IEEE Int. Symp. Information Theory (1SIT),
`1998, p. 117.
`[6] D. J. C. MacKay, “Good error correcting codes based on very sparse
`matrices,” [EEE Trans. Inform. Theory. vol. 45, pp. 399-431, Feb. 1999.
`[7] D. J. C. MacKay and R. M. Neal, “Good codes based on very sparse
`matrices,” in Cryptography and Coding: 5th IMA Conf. (Lecture Notes
`in Computer Science, no. 1025), Colin Boyd, Ed. Berlin, Germany:
`Springer, 1995, pp. 100-111.
`
`. “Near Shannon limit performance of low density parity check
`codes,” Electron. Lett., vol. 32, no. 18, pp. 1645-1646, Aug. 1996.
`Reprinted Electron. Lett., vol. 33, no. 6, pp. 457-458, Mar. 1997.
`[9] R. J. McEliece, D. J. C. MacKay, and J.-F. Cheng, “Turbo decoding as
`an instance of Pearl’s “belief propagation’ algorithm,” /EEE J. Select.
`Areas Commun., vol. 16, pp. 140-152, Feb. 1998,
`V. Sorokine, F. R. Kschischang, and S, Pasupathy, “Gallager codes
`for CDMA applications—I]: Implementations, complexity and system
`capacity,” JEEE Trans. Commun., submitted for publication.
`D, A. Spielman, “Linear-time encodable and decodable error-correcting
`codes,” /EEETrans. Inform. Theory, vol. 42, Nov. 1996.
`
`[8]
`
`[10]
`
`[1]
`
`