throbber
I|:|-l-‘
`
`|‘|<.-\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)1(cid:19)(cid:21)
`Apple 1 102
`
`

`
`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
`
`|

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket