IEEE TRANSACTIONS ON COMMU, !CATIONS. VOL. 47. NO. 10. OCTOBER 1999
`
`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 1102
`
`

`
`IEEE TRANSACTIONS ON COMMUNICATIONS. VOL. 47. NO. 10. OCTOBER I999
`
`93p
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`.
`
`1.2
`
`1.3
`
`1.4
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`Fig. 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), sub-Poisson (933). super-Poisson (5333:). 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. bower panels
`show the performance of several random codes of each construction. Venical axis: block error probability. Horizontal axis: E1. /.\1i
`in dB. All codes have
`.-‘V = 9972 and K = .-U = -41986. 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 at 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 constrttctirm method, that is. a pseudo-
`random algorithm for putting edges between the vertices in a
`
`way that satisfies the Constraints. (In the case of rtonbinary
`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 methods for 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
`
`

`
`IEEF. TRANSACTIONS ON (UMMUNICATIONS. VOL. 4?. NO.
`
`ll). f)C'I"()BER I999
`
`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 about N : 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 ft defined. Thus, when we
`observe r failures out of II‘ trials. pi = 1) r-xp{:I:rIt.,g ,,l where
`altlg ,.
`:
`lit -1‘)/(rri).
`
`ll. C()NSTRl}CTl0NS
`
`We compare the following methods.
`Pui.i'.mn: The edges are placed “completely at random."
`subject to the prolile 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 IA in I81.) A second variation requires that the
`graph have no cycles of length less than some I. (Similar to
`construction 1B in [8].) This constraint can be quite hard to
`enforce if the profile includes high weight rows or columns.
`Perniutart'0ns: We can build parity check matrices by su-
`perposing random permutation matrices £4]. The convenience
`of this method depends on the profile. There are many ways of
`laying out these permutation matrices to satisfy a given pro-
`file. We will distinguish “srtpr’t'-Poi's.rwi" and "sut'J-Pm'.rson"
`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. Pi'0_file.r and Cwtstt'trr‘ti0rI.r Srttrlferl in this‘ Paper’
`
`I) Rcgrtlai' Cort‘es%’: and 33: As our baseline. we study
`regular Gallager codes with weight per column exactly 1 = It
`and weight per row exactly t‘,. : b‘. We construct parity check
`matrices satisfying this profile from pennutation matrices in
`two ways. labeled "3" and “33," shown diagrammatically in
`the upper panels of Fig. 2. In the figure, a square containing
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`.
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`(:1)
`
`(b)
`
`(at Comparison of one representative of each of the constructions: 3
`Fig. 3.
`(regular). 93p (Poisson) and 93y [super-Poisson). lb) Representatives of all
`six constructions in Fig. 2. Vertical axis: block error probability. Horizontal
`axis: Er,/Ni,
`in dB.
`
`TABLE l
`THE Two PRt_iFt|.I~IS Srtinttsii IN rttts PAPI-iR
`
`Profile 3
`Profile 93
`
`Fraction
`ltow weight
`Column weight Fraction of columns
`’r'j3_'“_—j1j'_‘ " " "6‘m-T_‘-t
`Column weight Fractlortof t‘0ltJIIII1S
`Row weight
`Fraction
`3
`11/12
`7
`1
`9
`lg]!
`
`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 Code.r—93p. 93a. 931:. 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.
`Put'.rsmi—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-Pot'sson—93a.' This construction allocates exactly one
`or two elite bits to each check.
`
`Super-Pm'.rson.' 933; 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. Rc.\'ttlr.t'
`
`con-
`each
`II Vat‘t'abit't‘r}.' Wt‘rh.t'ri Each Construc'ti'art.' For
`struction. we created several codes in order to assess the
`
`variability of performance within each ensemble. All codes
`
`

`
`IEEE TRANSACTIONS ON COMMUNICATIONS. VOL. 47. NO. 10. OCTOBER 1999
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`(:1)
`
`(hi
`
`lci
`
`in dB. (b) Histogram of
`1a) Comparison of irregular 93y with regular 33 code. Vertical axis: median number of iterations. Horizontal: E,,/.\},
`Fig. 4.
`number of iterations for 93y code at Ei,/N0 : 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.
`
`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.931 (Poisson) or 93a (sub-Poisson) codes.
`But among the super-Poisson codes, 93:: and 93y. there is
`some variability with some codes showing an error floor.
`2) E.rplcman'on of Error Floors:
`In 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 codeword in exactly three bits—the same three bits
`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
`I
`I
`I
`-
`-
`checks /, 3.. ./..§(__
`.
`..i£<€!»;”. ' t
`bits i”; Q;
`
`in
`
`.
`
`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
`I
`I
`'§/\-
`
`checks 1,7‘. .''..t,
`
`<2)
`
`V
`
`"\
`
`i./
`
`=1‘; . . "_‘I 1"’:
`
`I
`
`in construction IA of [8]). This modification is sufficient to
`
`prevent the topology shown in (1) from occurring. In principle.
`it is possible for a code to have a minimum distance 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].
`We discard 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
`
`Encoding procedure;
`Bits 1; .
`.
`. tx are ricfint-d to he source hits.
`
`Bits tK+1...tN_M< are set in sequence. using
`the mth parity check to determine ix“...
`
`Bi” 3N— M<+|
`
`‘N 5-"9 39‘ ‘-'‘l“3-l
`C_lBt’ t:1od2
`
`‘-95
`
`where t‘ = (t1...tN_M<)‘ and C” is
`the inverse of C in module 2 arithmetic.
`
`This costs {N —M<)t, computational
`operations. where t,
`is
`the typical
`weight per row.
`
`bits of mem-
`C’ ' can be stored in
`t:.'t.n he com-
`ory. The product Bl.’
`puted in !lrf<t',- computational opera-
`tions,
`tutti the multiplication by C”
`takes M3 operations.
`
`Fig. 5. Upper panel: general fomi of a fast-encoding Crallagcr code. Hori-
`zontal stripes indicate low-weight rows. The diagonal line is a line of 1's.
`The matrices B and C are of dimension .l[( X (N — .11.‘ l and 1!.‘ x .\I.;.
`respectively. Lower panel: the fast encoding method to generate a codeword
`and its computational cost, assuming an appropriate representation of the
`sparse matr'tx.
`
`clear ranking of the other constructions, as follows:
`
`3 < 93a < 93p < 93:: < 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 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.
`
`Fig. 4(b) and (C) shows that the distribution of decoding
`times is heavy tailed. At Eb/N0 = 1.4,
`the tail
`is well
`approximated by the power law: P( ) ~ 7"3'5, where 1'
`is
`the number of iterations. At Eb/N0 = 1.2, the distribution is
`heavier tailed, and we have P(r) ~ “F5.
`
`

`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47'. NO. I0. OCTOBER I999
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`(a) Upper panels: construction methods 13 and 1933;. 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 F5. Horizontal and vertical lines indicate the boundaries of the permutation blocks. Lower picture:
`variability of performance among 13 and 1933; codes. Vertical axis: block error probability. Horizontal axis: Eb/N9 in dB. All codes have N = 9972 and
`It' : AI = 4086. (b) Example of a parity check matrix with .\' = 1-14 made using construction 1933*.
`
`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 93):.
`we found that at E1,/N0
`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 El,/Nu. For example. at
`Eh/Na = 0.7 dB. the error rates are 0.035 and 0.097.
`
`IV. FAST~ENCODlNG GALLAGER Cones
`
`One of the possible drawbacks of Gallager codes is that their
`encoding time generally scales as N2. 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—tt-iangular structure which allows all but a small number
`114.: of the parity bits to be computed using sparse operations.
`The final M< parity bits can be computed in ME binary
`operations. If M< were as small as \/TE, then the codes would
`be linear—time encodable.
`
`We introduce two constructions, 13 and l93y (“l" 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
`93y. Fig. 6(b) shows an example of a matrix made using
`
`

`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47. N0.
`
`l(l. OCTOBER NW
`
`
`
`The discovery that we can make fast-encoding 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 fast-encoding codes are
`substantially smaller. The static memory required for encoding
`is proportional to .-iii + Ml.,.. where 1%,. is the typical weight per
`row in the parity check matrix. This compares to M (N — M)
`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 M< :
`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 [IO]. The
`smaller the ratio !lf< /M. the greater the reduction in encoding
`cost.
`It will be interesting to investigate how small
`."lI< can
`be made without deterioration in perfonnance.
`
`REFERENCES
`
`
`
`[l] M. C. Davey and D. J. C. MacKay. “Low density parity check codes
`over GF|ql." in Print‘. IEEE I998 Irifnrntutirm Theory Workshop. June
`1998. pp. 7(L':‘l.
`. “Low density parity check codes over GF(q).“ IEEE Crmimim.
`Lett.. vol. 2. pp. 165467. June I998.
`[3} R. G. Gallager. “Low density parity check codes." IRE Trans. Inform.
`Theory, vol. IT-8. pp. 2|~28. Jan. 1062.
`, Law .DE’!l.\'.l!_\' Pm'i'ry Check ('m1tar (Research Monograph Series
`no. 21). Cambridge. MA: MIT Press. I963.
`[5] M. G. Luby, M. Mitzenntacher. M. A. Shokrollahi. and D. A. Spielman.
`"Improved low-density parity-check codes using irregular graphs and
`belief propagation." in Prm: IEEE Int. S_vmp. hrfurntuti'cm Theory IISITI.
`1998. p. 117.
`[6] D. J. C. MacKay. “Good error correcting codes based on very sparse
`matrices." IEEE Trans. Inform. Tfimrjv, vol. -15. pp. 399-431. Feb. 1999.
`[7] D. J. C. MacKay and R. M. Neal. "Good codes based on very sparse
`matrices." in C!"_t‘pl'0gF'L1ph_‘l’ and Coding: 5:}: {MA Con]. (Lecture Notes
`in Computer Science. no. I025). Colin Boyd. Ed. Berlin. Germany:
`Springer. 1995. pp.
`l00—il].
`. “Near Shannon limit performance of low density parity check
`codes." Et'ect'ran. Leta. vol. 32. no. 18. pp.
`I645~l6-46. Aug. 1996.
`Reprinted Electron. Lem. vol. 33. no. 6. pp. 457-458. Mar. 1997.
`|'-3| R. J. McEliece. D. J. C. Macliay. and .l.—F. Cheng. "Turbo decoding as
`an instance of Pearls ‘belief propagation‘ algorithm." IEEE J. Sc-let-r.
`.4rc'a.3‘ Commun.. vol. 16. pp.
`l40—I52. Feb. I998.
`V. Sorokine. F. R. Kschischang. and S. Pitsupathy. "Gall-age: codes
`for CDMA applications—lI: implementations. complexity and system
`capacity." IEEE Trans. Commtrrt. submitted for publication.
`D. A. Spiel:-nan. “Linear—time encodablc and dceodnblc error-correcting
`codes." IEEE Tram. Inform. Th:'rJr).‘. vol. 42. Nov.
`i996.
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`0.1
`
`0.01
`
`0 0001
`
`0.00 1
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`(a)
`
`(b)
`
`(a) Comparison of 13 with an ordinary 3 code. {bl Comparison
`Fig. 7.
`of 1933: with the best super—Poisson 93y code. Vertical axis: block error
`probability. Horizontal: Eb/N3/dB.
`
`Construction 193)], 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
`
`[2]
`
`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 irnponant to be aware of all the methods available for
`enhancing code perfonnance, 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).
`
`[4]
`
`l8l
`
`llUl
`
`Illl