`
`|‘|<.-\NS.A("l'lf).’\lS UN ('()Ml\'ll.'.\'|C.i\Tl(')N.‘a‘. VOL. 47. N0.
`
`Ill. ()(“l'(lllli.R IUW
`
`I-1-19
`
`Transactions Letters
`
`Comparison of Constructions of Irregular Gallager Codes
`
`David J. C. MacKay. Simon T. Wilson. As.»-or-i'tiit= M'cnn'rcr. IELE. and Matthew C. Davey
`
`
`
`:3‘
`5CUJD
`2CL
`
`§
`139'
`
`5 E
`
`jg
`3
`UJ
`
`.
`Turbo
`‘l lrreg GF(B)
`0.2
`0.4
`
`-0.2
`
`0
`
`0.6
`
`0.8
`
`Abstrar-i'—'l‘he low-density parity check codes whose perfor-
`mance is closest
`to the Shannon 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 (lallager codes normally take .\" time to encode. we
`imestigate constructions of regular and irregular Gallager codes
`that allow more rapid encoding and have smaller memory re-
`quirements in the encoder. We find that
`these “fast encoding”
`(lallager codes have equally good performance.
`
`Index Term.r—('hanneI coding. error correction coding, Gauss-
`ian channels. graph theory. iterative probabilistic decoding. ran-
`dom codes.
`
`I.
`
`lNTRODLI(_"I‘lC)N
`
`ALLAGER codes [3]. M] are low-density parity check
`
`GCU[lCS constructed at random subject to constraints on the
`
`weight of each row and of each column. The original i'egiii'ai'
`Gallager codes have very sparse random parity check matrices
`with uniform weight
`f per column and I,. per row. (We will
`also use the term “regular“ for codes that have nearly uniform
`weight columns and rows-l'or example. codes which have
`some weight 2 coltimiis and some weight 3 columns.) These
`codes are asymptotically good and can be practically decoded
`with Gallager's suin—producl algorithm giving near Shannon
`limit performance when large block lengths are used |6]»[8].
`Regular Gallager codes have also been found to be competitive
`codes
`for short blocl-;—length code-division multiple-access
`(CDMA) applications [ill].
`Recent advances in the perforiiiance of Gallager codes
`are summarized in Fig.
`l. The rightmost curve shows the
`performance of a regular binary Gallager code with rate U4.
`The best known binary Ciallagcr codes are i'i'i'e_eiii'ui' codes
`whose parity check matrices have imiiiriii_'f'rJriii weight per
`column IS]:
`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 tields (J Hg)
`[1]. [3]. The remaining two solid curves in Fig.
`l show the
`performance of a regular Gallager code over ("fl-‘t lti) |2| and
`
`for Codiiig Theory and
`the Etlitor
`S. B. Wicltcr.
`Paper approved by
`Technique». of
`the
`IEEE Coniiiiunications Society. Maiiiiscript
`received
`.r'\ll_t._1ll~I
`ll. 1998:
`revised January 27. 1909. This paper was presented in
`part
`at
`the l‘l‘)l< Allerton Conference on (‘oniiiiiinicaiions, ('ontroi. and
`Coiiiputiiig. Allcrton House. IL. September l‘)'~JR.
`The authors are uith the Department of Physics. University of (‘ain-
`hridgc. Canibridgc ("B3 0HF.. UK.
`t_e—iiiail:
`iiiacl-;iiy({i.=itirao.caiii.eic.ul\:
`stu-l l(@‘iiiriio.cam.ac.ult; mcdave_v@n1rao.cam.ac.ul< ).
`Publisher Item Identifier S 0090-6778t99]O7784-3.
`
`Ebi'No{dB)
`
`irregular
`l. Empirical results for (iiitissiiin chzinncl. rate I/-1 |el't—right:
`Fig.
`LDPC. GF{8) blockleiigtli 3-1000 bits; JPL Turbo. bliickleiigtb its 536 hits:
`regular LDPC. GF(t(.1i. blocklcngth 24443 hits;
`irregular 1.l)P(‘. (.'I"t'.’).
`blockleiigth 64000 bits:
`regular LDPC. Cz'Fl.3). blockleiigtli -llltltlll bits.
`(Reproduced from [l|.)
`
`an irregular code over (.'F(.‘-€) with bit-error probability of
`10"; at F.},/N” : —ll.(l7i dB [l]. In comparing this code with
`the rate 1/4 turbo—code shown by the dotted line. the following
`points should be noted. 1) The transmitted hlocklengih of the
`irregular Gallager code is only 24 Otltl bits. whereas that of the
`turbo—code is 65 536 bits. 2) The errors made by the Gallager
`codes were all detected errors. whereas turbo-codes make
`
`least 3. undete
`
`undetected errors at high signal-to—noise ratio. This difference
`is not caused by a difference in the decoding algorithm: both
`codes are decoded by the sum—prodt.ict algorithm [9]. Turbo-
`codes make undetected errors because tft(’_\' have i'riii'-iiicriglii
`t‘odeii'oro's. For Gallager codes.
`the rate of occurrence of
`
`'
`=cause they have good
`
`distance properties
`luinimum distane cales linearly with
`
`the blocklength)
`'
`with Gallager
`codes of block
`
`n h greater tha
`00 and c umn weight at
`gators have Ifefioer occurred.
`
`
`The excelle tzerforinance olE'.i.i3’egular Galgg r codes is the
`
`motivation for
`paper. in wfich we explo 3‘
`ays of further
`
`ciihuiicing thcs
`_
`
`The irregular codes of @iy. Mitzeni
`r. Shokrollahi.
`and Spielinan [5]
`' ve parity check matricix,
`ith both nonuni-
`
`
`form weight per row . d nonuniform we'
`1 per column. It has
`
`not yet been established
`of these nonunifonnities
`are desirable. In our experience with codes for noisy channels.
`performance is more sensitive to the distribution of column
`weiglits. ln this paper. we concentrate on irregular codes with
`the weight per row as uniform as possible.
`We can define an irregular Gallager code in two steps.
`First. we select a profile’ that describes the desired number
`of columns of each weight and the desired number of rows of
`
`(llll)tl—()7'I"l-4lfU'~).‘l4|ll.lllJ tCJ
`
`I‘-J9‘)
`
`llililf
`
`(cid:36)(cid:83)(cid:83)(cid:79)(cid:72)(cid:3)(cid:20)(cid:19)(cid:19)(cid:21)
`Apple 1002
`
`
`
`IEEE TRANSACTIONS ON COMMUNICATIONS. VOL. 47. NO. 10. OCTOBER I999
`
`33
`
`93p
`
`
`
`
`0.0001 1.2
`
`0.1
`
`0.01
`
`0.001
`
`1
`
`1.1
`
`1.3
`
`1.4
`
`1.5
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`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 (9313), sub-Poisson (93a). super-Poisson (93):). and super-Poisson (9337). Notation for upper panels for all constructions except 93p: an integer
`represents a number of pEIT1'1uIt.lll.Dl‘l matrices superposed on the surrounding square. Horizontal and vertical lines indicate the boundaries of the pennutation
`blocks. Notation for the Poisson construction 93p: integers
`and "9“ represent column weights. The integer “7" represents the row weight. Lower panels
`show the performance of several random codes of each construction. Venical axis: block error probability. Horizontal axis: E,,/.\‘';;
`in dB. All codes have
`N = 9972 and K = .1! = -1980. 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 vettices in this graph.
`Second. we choose a consrrur'rr'rm method, that is. 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 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
`
`
`
`
`
`IEEE TRANSACTIONS ON CUMMUNICATIONS. VOL. 47. ND.
`
`ll). ()(."l‘()HF.R I9‘-N
`
`1451
`
` 0.1
`
`0.l
`
`0.01
`
`0001
`
`00001
`
`001
`
`0.001
`
`00001
`
`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 U2 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 fr defined. Thus, when we
`observe r failures out of 1: trials. pi : 1) e=:~;plirri.,,H ,,l where
`“lug ,.
`:
`(ri—:')/(rii).
`
`II. C()N.'~2TRt,'CTION‘S
`
`We compare the following methods.
`Prim-.uri.' The edges are placed "completely at random."
`subject to the prolilc 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 pertnutation.
`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 IS].) 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.
`Pern1tttart'ori.r: 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 “5tt,rm‘-Pol.r.rm1" and "su!J—Pot's.s‘ori"
`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.
`
`11]. COMPARING PotssoN. SllPl€R-POISSON.
`AND SUB-P()]SS()N CoNs'i'RtIcT1oNs
`
`A. Pr0_file.s‘ and C0n.s'ti'm'ti()n.t‘ Smdfed in this Paper
`
`1) Regular‘ Co:ies% and 33: As our baseline. we study
`regular Gallager codes with weight per column exactly f. : it
`and weight per row exactly r,. : ti. 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.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`on
`
`tb)
`
`(at Comparison of one representative of each of the constructions: 3
`Fig. 3.
`(regular). 93p (Poisson) and 93y [super-Poissoii}. (b) Representatives of all
`six constructions in Fig. 2. Vertical axis: block error probability. Horizontal
`axis: E;,/_-\’.,
`in dB.
`
`TABLE 1
`THE Two Pittit-‘iI.t-js S'rtioit-:t) IN '1 His PAPER
`
`
`Profile 3
`
`Profile 93
`
` _weiglit;£ra(‘Li<)n of co|umt_is_ _li:_(.l_\Jl’_l'l'i"£‘_:l_g'l'l.l __£t"d.C_l.l.(iIL
`3
`1
`6
`1
`Column weight Fraction of rolutnns
`Row weigltt
`Fraction
`3
`11/12
`T
`l
`9
`l
`l 2
`
`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 C0de5—93p. 93a. 93):. cmc193y: 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.
`P()I'.\‘.S‘()l'2—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.
`
`Sllfl-P(JfSSOi'?-—93a.' This construction allocates exactly one
`or two elite bits to each check.
`
`.S'tipei'-Poiswn: 93:; 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 Ii'0l'I€.
`
`B. Rt'.\'tt'.l!.\'
`
`con-
`each
`H l/ar‘i(1bilt’rv Within Each Consrrtt('tt'oii.' For
`struction. we created several codes in order to assess the
`
`variability of perfonnance within each ensemble. All codes
`
`
`
`
`
` 1452’.
`
`IEEE TRANSACTIONS ON COMMUNICATIONS. VOL. 47. NO. 10. OCTOBER I999
`
`25000
`
`
`
`20000
`
`15000
`
`10000
`
`5000
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`10000
`
`1000
`
`100
`
`10
`
`I.
`
`_
`
`0
`10
`20
`30
`40
`50
`
`0.1
`
`(a)
`
`lb]
`
`[C]
`
`llurtzontnl: Eh/.\'n in dB. (b) Histogram of
`la) Comparison of irregular 93y with regular 33 code. Vertical axis: median number of iterations.
`Fig. 4.
`number of iterations for 93y code at Er,/.\}, : 1.4. (cl 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 J E.rplcmatt'0n 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 hits
`
`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
`
`checks
`
`(1)
`
`If the three hits 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 _g .'. .' ._'u.__'
`
`.,
`M’
`bits EL"; oioifu §'_:= --
`
`(2)
`
`in construction IA of [8]). This modification is sufficient to
`
`prevent the topology shown in ( i) 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 0fC0ns.rrucrfons: 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 11 ...t;t- are Iltl=.fi]'|(‘I.l to he source hits.
`
`130-5 3K+t - --tN—M¢ 3'9 St’-C lit Hfitltlflflfifit using
`the mth paricyrzlicck to determine tK..,,,.
`
`Bi“ 3-N’M<.‘l*l
`
`'--‘N are Set equal W5
`C'lBt.' r:toti2
`
`where t‘ = (t1...t;..r_M<)’ and C’l is
`the inverse of C in modulo '2 arithttietic.
`
`This costs {N—M<)t,. computational
`opemt'.0ug_ where gr
`13
`the typical
`weight per row.
`
`bits of mem-
`C‘ ' can be stored in
`ory. The product Bt' can be corn-
`puted in llr2l(t,- computational opera-
`tions, and the multiplication hy C 3
`takes Mg operations.
`
`Fig. 5. Upper panel: general form of 2t fasl-encoding Ctallagcr 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 _-it’.-_ x (N — _\t'.__ t and _ll’,_- x _‘t[._:.
`respectively. Lower panel: the fast encoding method to generate Ll codeword
`and its computational cost. assuming an appropriate representation of the
`sparse matrix.
`
`clear ranking of the other constructions. as follows:
`
`3 < 93a < 93p < 93x < 93y.
`
`least for the 93 profile. sub—Poisson
`Thus, we find that at
`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 716 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/NU = 1.4,
`the tail
`is well
`approximated by the power law: P(r) ~ r‘3'5, where -r
`is
`D
`the number of iterations. At Er,/N0 : 1.2, the distribution is
`heavier tailed, and we have P(r) ~ 7-‘ .
`
`
`
`
`
`IEEE TRANSACTIONS ON COMMUNICATIONS. VOL. 47. NO. 10. OCTOBER 1999
`
`1453
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`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 1's. Horizontal and vertical lines indicate the boundaries of the permutation blocks. Lower picture:
`variability of perfonnance among 13 and 1933; codes. Vertical axis: block error probability. Horizontal axis: Eb/Nn in dB. All codes have N = 0072 and
`It" : .11 = 4936. (b) Example of a parity check matrix with X : 14-1 made using construction l93y.
`
`(bl
`
`5) Unequal’ Error Proret"tr'0n: 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 E5,/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 Eh / 1V0. For example. at
`Ei,/Nn = 0.7’ dB. the error rates are 0.035 and 0.097.
`
`IV. FAST-ENCODING GALLAGER CODES
`
`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—e-needing. 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
`lowemriangular structure which allows all but a small number
`M< of the parity bits to be computed using sparse operations.
`The final M< parity bits can be computed in M2 binary
`operations. If M< were as small as \m 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
`
`
`
`
`
`
`
`.._.;_..-._.4.,44_.._—.,_-...;:4;:__c_.4;.‘L2a--.-...a.w-._-L—...+-vq.4.-.—._=-»_..s__.—u.—_....f,—,;..-f—_.r=g..,=..—.=,;L_.-»L:~.u'-—aut_....._..._,._._..,
`
`
`
`
`
`
`
`
`
` 0.1
`0 0001
`
`001
`
`0.001
`
`0.01
`
`0.001
`
`0.0001
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`12
`
`1.3
`
`1.4
`
`1.5
`
`(3)
`
`lb)
`
`ta} Comparison of 13 with an ordinary 3 code. (ht Comparison
`Fig. 7.
`of 193y with the best super—Poisson 93y code. Vertical axis: block error
`probability. Horizontal: Eb/3'0/dB.
`
`construction 1933;. 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 ordinaty—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.
`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 imponant 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.
`11 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'. N0.
`
`l(l. O(T()HF.R [999
`
`
`
`The discovery that we can make fast—encoding Gallager
`codes whose perfonnance 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 .‘l1_§\+.-‘lIl,.. where i‘,. 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 .=lI< =
`M/G. 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 [I0]. The
`smaller the ratio .-"lI< /ill. the greater the reduction in encoding
`cost. It will be interesting to investigate how small
`.‘lI< can
`be made without deterioration in performance.
`
`REFERENCES
`
`[l] M. C. Davey and D. J. C. MacKay. “Low density parity check codes
`over GFlql." in Prat‘. IEEE .7998 Infrarntutiwt Theory Workshop. June
`1998. pp. 7(L7'l.
`. "Low density parity check codes over GF(q]." IEEE Commun
`Le.'!.. vol. 2, pp.
`lh5—|(17. June I9‘-J8.
`[Fri R. G. Gallager. "Low density parity check codes." IRE Tmnr. Infhrnt.
`Theory‘, vol. lT-8. pp. 2I»2li, Jan. 1062.
`. Low Dem't'r_r Pctriry Cltprk (‘mic-.1 (Research Monograph Series
`no. 21). Cambridge. MA: MIT Press. I963.
`[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 .Pl"(?t'. !E}:'E hit. Syntp. l'nfitrmutt'on Theory.‘ HSITH.
`1998. p. 117.
`|e| D. J. C‘. MacKay. “Good error correcting codes based on very sparse
`matrices." IEEE Trtttrts. ill'lfr')l"m. Tftemfv. 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 ar:t1'Cr):!tn2.' 5th [MA Clmf. (Lecture Notes
`in Computer Science. no. I025). Colin Boyd. Ed. Berlin. Germany:
`Springer. 1995. pp.
`l00—ill.
`. “Near Shannon limit performance of low density parity check
`Codes." Et'et'rr'mt. Left. vol. 32. no.
`I8. pp.
`It‘-45—l646. Aug. 1996.
`Reprinted Electron. Lent. vol. 33. no. 6. pp. 457-458. Mar.
`l99'1'.
`|9| R. J. McEliece. D. J. C. MacKay. and J.—F. Cheng. "Turbo decoding as
`an instance of Pearls ‘belief ptopagation' aigotithnt." IEEE J. 5c't'€ct'.
`Areas ('tm1mtut.. vol. 16. pp.
`l40—I52. Feb. I998.
`|lU] V. Sorokine. F. R. Kschischang. and S. Pasupathy. "Gall-ager codes
`for CDMA applications—lI: lmplementations. complexity and system
`capacity." IEEE Trans. Commtm.. submitted for publication.
`I I] D. A. Spielman. “Linear-time encodablc and deeodablc error—corrccting
`codes." IEEE Trans. Inform. Tfrmr).‘. vol. 42. Nov. I996.
`
`l3l
`
`|