~/~iEEE TRAN SACTI 0 N S 0 N
`COMMUNICATIONS
`
`f' .. l
`A PUBLICATION OF THE~~EE COMMUNICATIONS SOCIETY
`
`(\
`
`OCTOBER 1999
`
`VOLUME 47
`
`NUMBER10·
`
`IECM T
`/
`
`(ISSN 0090-6778)
`
`TRANSACTIONS LETTERS
`
`Coding
`Comparison of Constructions of Irregular Gallager Codes ............................ D. J. C. MacKay, S. T. Wilson, and M. C. Davey
`Data Compression
`Level-Compressed Huffman Decoding ........................................................................ K.-L. Chung and J.-G. Wu
`Digital Communications
`Maximum Ratio Transmission ................................................................................................. T. K. Y. Lo
`Modulation/Detection
`The Constellation-Shaping Algorithm Using Closed-Form Expressions for the Number of Ring Combinations .......... C. E. D. Sterian
`Optimum Precompensation Filters for IQ Modulation Systems ............................................... J. Tuthill and A. Cantoni
`Personal Communication Systems
`Optimal Adaptive Spectrum Utilization in Cellular Communications Systems ......................................................... .
`.................................................. M. G. Kazantzakis, P. P. Demestichas, E. C. Tzifa, and M. E. Anagnostou
`Synchronization
`About the Asymptotic Performance of MMSE MIMO DFE for Filter-Bank Based Multicarrier Transmission ........................ .
`...................................................... _ .......... L. Vandendorpe, J. Louveaux, B. Maison, and A. Chevreuil
`
`TRANSACTIONS PAPERS
`
`Coding
`Very Low Rate Trellis/Reed-Muller (TRM) Codes ............................................................. J.-P. Chaib and H. Leib
`On Decoding of Both Errors and Erasures of a Reed-Solomon Code Using an Inverse-Free Berlekamp-Massey Algorithm
`........................................................................................... J.-H. Jeng and T.-K. Truong
`The Union Bound for Turbo-Coded Modulation Systems over Fading Channels .......................... T. M. Duman and M. Salehi
`Fading/Equalization
`Performance Analysis of Optimum Combining with Multiple Interferers in Flat Rayleigh Fading ........................... E. Villier
`Reuse Within a Cell-Int~~-.I~_ej_ection or Multiuser Detection? .......................... C. Tidestav, M. Sternad, and A. Ahten
`Multiple Access
`·~--_.
`Time-Varying Narrow-Band Interference Rejection in Asynchronous Multiuser DS/CDMA Systems over Frequency-Selective Fading
`Channels .............................................................................................. S. Buzzi, M. Lops, and A. M. Tutino
`Personal Communication Systems
`Lateness Probability of a Retransmission Scheme for Error Control on a Two-State Markov Channel. ......... M. Zorzi and R. R. Rao
`Spread Spectrum
`Performance Enhancement of DSSS Systems: Two-Dimensional Interference Suppression ............................................ .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . S. G. Glisic, Z. B. Nikolic, D. Pokrajac, and P. A. Leppanen
`Channel Estimation for DS-CDMA Downlink with Aperiodic Spreading Codes ....................... A. J. Weiss and B. Friedlander
`Convolutionally Coded Multi carrier DS-CDMA Systems in a Multi path Fading Channel- Part I: Performance Analysis ............ .
`....................................................................................... D. N. Rowitch and L. B. Milstein
`Optimal Reception, Performance Bound, and Cutoff Rate Analysis of References-Assisted Coherent COMA Communications with
`Applications ........................................................................................................................ F. Ling
`
`1449
`
`1455
`
`1458
`
`1462
`1466
`
`1469
`
`1472
`
`1476
`
`1488
`1495
`
`1503
`1511
`
`1523
`
`1537
`
`1549
`1561
`
`1570
`
`1583
`
`(Contents Continued on Back Cover)
`
`L
`
`I~
`
`~
`
`'. ,
`
`f'
`
`f I
`
`J~
`I
`I
`
`I' II
`:;
`'!!;
`I"
`:I
`1;:
`I 'i}:
`
`:'
`!:
`
`',I
`
`Hughes, Exh. 1023, p. 1
`
`

`

`•'···,.~.· ,,,
`
`:.:.t;!t~·\;~ ~·111\-n•t--..~
`~-~..;."·
`J.l!''<·''
`•. ~
`IEEE COMMUNICATIONS SOCIETY
`,
`1
`~;.
`J
`\ .. ,
`.... ~
`~
`.,f ··Th~ fiel~~ilweresi of the '··t~m~unications :Jiociety consists of all telecom~unicatil~ns including telephone, telegraphy, facsimile, and poinHo-~oint television, by electrornagneti_c propagation including radio~ wire;
`aenal~ unJerground, coaxial, and ~ubrncwfn~.cables; waveguides, communicatiOn satellites. and lasers; in marine, aeronautical, space and fixed station services; repeaters, radio relaymg, signal storage, and regeneration;
`telecommunication error dete~a~~ction: multiplexing and carrier techrtiques; communication switching systems: data communications; and communication theory.
`In a~.dition to ~ .... .abO'Ve;.. ihit>'a.~~c:IONS contai~s pa~rs pertaini~g to analog a~d digital signal processi.ng ~nd modulation. audio and video encoding tec~niq.ues, the theory and .des!gn of transmitters, receivers,
`, .
`'311Q, re~j. f~_L conyrw.~._\ll~~ .. via optical and some med1a, the des1gn and analys1s of computer comm~mcallon systems, and the developmen~ of commumcatlon software. Contnbuuons of theory enhancing the
`undet~t~.~.i[f0Jt"41Wffit.'at1on systems and tec.hniques are in~luded, as are discussions of the social. impli.catJOns of the development of communicatJO·n· technology. All members of the IEEE are eligible for membership
`in~e Soc1ety upon payment of the annual Soc1ety membership fee of $23.00. Members may rece1ve thts TRANSACTIONS upon payment of an addtttonal $27.00 ($50.00 total), or the IEEE JOURNAL ON SELECTED
`A~rAs IN COMMUNICATIONS upon payment of an additional $32.00 ($55.00 total), or both publications upon payment of an additional $59.00 ($82.00 total). For information on joining, write to the IEEE at the address
`below. Member copies of Transactions/Journals are for personal use only.
`
`D. P. TAYLOR, Editor-in-Chief
`Dept. Elec. Electron. Eng.
`Univ. Canterbury
`Christchurch, New Zealand
`
`IEEE COMMUNICATIONS SOCIETY
`TRANSACTIONS Editorial Board
`D. G. DAUT, Publications Editor
`Dept. Elec. & Comput. Eng.
`Rutgers Univ.
`Piscataway, NJ 08855
`
`K. C. CHEN, Wireless Data Commun.
`National Taiwan Univ., Taipei, Taiwan
`
`J. C.· I. CHUANG, Area Editor
`AT&T Labs.-Research, Red Bank, NJ
`
`A. GOLDSMITH, Multiuser and Adaptive S.vstems
`EE Dept., Stanford Univ., Stanford, CA
`
`B. JABBARI, Wireless Multiple Access
`ECE Dept., George Mason Univ., Fairfax, VA
`
`P. Y. KAM, Modulation & Detection
`Electrical Engineering
`National Univ. Singapore, Singapore
`z. KOSTIC, Wireless S\'stems
`AT&T Labs.-Resear~h. Red Bank, NJ
`
`K. B. LETAIEF, Wireless Systems
`EEE Dept., HKUST, Hong Kong
`
`K. K. LEUNG, Wireless Network Access &
`Perfonnance
`AT&T Labs.-Research, Red Bank, NJ
`
`Y. LI, Wireless Communication Theory
`AT&T Labs.-Research, Red Bank, NJ
`
`Editors
`P. PRUCNAL, Area Editor & Light. Networks
`EE Dept., Princeton Univ ., Princeton, NJ
`0. TONGUZ, Optical Transmission S.vstems
`ECE Dept., SUNY, Buffalo, NY
`
`Speech, Image, Video, & Signal Process.
`M. R. CIVANLAR, Image Commun. S.vst.
`AT&T Labs.-Research, Holmdel, NJ
`B. GIROD, Image Processing, Area Editor
`EE Dept., Univ. Erlangen-Nuremberg
`Germany
`K. ILLGNER, Image Processing and Transmission
`Texas Instruments, Inc., Dallas, TX
`K.-K. MA. Video & Signal Processing
`Elect. & Electron. Eng.
`Nanyang Tech. Univ., Singapore
`C. S. RAVISHANKAR, Speech Process.
`Hughes Network Systems
`Germantown, MD
`A. H. WATANABE, Video Image
`NTI Human Interface Labs., Commun.
`Yokosuka, Japan
`
`P. T. MATHIOPOULOS, Wireless Personal Commun.
`EE Dept., Univ. Brit. Columbia
`Vancouver, BC, Canada
`
`E. SOUSA, CDMA Systems
`EE Dept., Univ. Toronto, Toronto, Canada
`
`R. A. VALENZUELA, Wireless S\'stems
`Lucent Technologies, Bell Labs:, Holmdel NJ
`
`Transmission Systems
`S. GELFAND, Equalization
`ECE Dept., Purdue Univ., West Lafayette, IN
`H. LUI, Synchronization & Equalization
`EE Dept.. Univ. Washington, Seattle, WA
`R. RAHELI, Detection, Equalization & Coding
`Infonnation Eng., Univ. Parma, Parma, Italy
`J. K. TOWNSEND, CAD Commun. Syst.
`ECE Dept., NC State Univ., Raleigh, NC
`L. V ANDENDORPE, Synchronization & Equalization
`Univ. Catholique de Louvain,
`Louvain-la-Neuve, Belgium
`C.-L. WANG, Equalization
`EE Dept., National Tsing Hua Univ., Taiwan
`M. Z. WIN, Equalization & Diversity
`AT&T Labs.-Research, Red Bank. NJ
`J. J. O'REILLY, Opt. Commun. Syst.
`J. WINTERS, Area Editor & Equalization
`Dept. Elec. Electron. Eng.
`AT&T Bell Labs., Holmdel, NJ
`Univ. College, London, U.K.
`(Information for Authors, ComSoc Board of Governors, Depanments, and Committees appear on Cover Ill)
`
`J. WANG, Wireless Spread.Spectrum
`EEE Dept., Univ. Hong Kong, Hong Kong
`
`Optical Communication
`D. K. HUNTER, Photonic Networks
`Dept. Electron. Elect. Eng.
`Univ. Strathclyde, Glasgow, U.K.
`
`I. JACOBS, Senior Advisor
`Dept. Elec. Eng.
`Virginia Polytechnic lost.
`Blacksburg, VA 24061
`
`Network Architecture
`G. S. Kuo, Commun. Architect.
`Dept. Inf. Mgt., National Central Univ.
`Chung-Li, Taiwan
`N. MCKEOWN, Switching & Routing
`EECS Dept., Stanford Univ., Stanford, CA
`G. O'REILLY, Commun. s~dtch.
`AT&T Labs., Lincroft, NJ
`A. PATTAVINA, Switching Arch. Perform.
`Dept. Elec. & Inform.
`Politec. di Milano, Italy
`R. RAO, Packet Multiple Access
`Elect. and Computer Eng.
`Univ. California, San Diego
`La Jolla, CA
`P. E. RYNES, Switch. Syst.
`AT&T Bell Labs., Naperville, IL
`E. G. SABLE, Area Editor
`AT&T Bell Labs., Holmdel, NJ
`
`Coding & Common. Theory
`T. AULIN, Coding & Commun. Theory App/.
`Chalmers Univ. Technol., Goteborg, Sweden
`E. AYANDGLU, Commun. Theory & Coding App/.
`Bell Labs., Lucent Tech., Holmdel, NJ
`M. FOSSORIER, Coding & Commun. Theory
`EE Dept., Univ. Hawaii, Honolulu, HI
`P. HOEHER, Coding & Iterative Processing
`Information & Coding Theory Lab.
`Kiel Univ., Kiel, Germany
`R. KOETTER, Coding Theory & Techniques
`CSL, Univ. Illinois, Urbana, IL
`C. SCHLEGEL, Coding Theory & Techniques
`EE Dept., Univ. Utah, Salt Lake City, UT
`R. D. WESEL, Coding & Coded Modulation
`EE Dept., UCLA, Los Angeles, CA
`S. G. WILSON, Area Editor & Coding
`Theory & App/.
`EE Dept., Univ. Virginia, Charlottesville, VA
`
`Senior Technical Consultants
`D. DIVSALAR
`Y. BAR·NESS
`
`W. H. TRANTER, Director of Journals
`Dept. Elec. & Comput. Eng.
`Virginia Polytechnic lost.
`Blacksburg, VA 24061
`
`Modulation & Signal Design
`A. AHLEN, Demodulation & Equalization
`Signals and Systems, Uppsala Univ.
`Uppsala, Sweden
`0. ANDRISANO, Modulation for Fading Channels
`DEIS/CSITE, Bologna, Italy
`S. BENEDETIO, Area Editor
`Dept. Elec., Politec. di Torino, Italy
`M. BRANDT·PEARCE, CDMA Svstems
`EE Dept., Univ. Virginia
`.
`Charlottesville, VA
`G. CAIRE, Multiuser Detection & CDMA
`Inst. Eurocom, Cedex., France
`G. CHERUBINI, CDMA Svstems
`IBM Research Lab., Zurich, Switzerland
`G. CORAZZA, Spread Spectrum
`DEIS, Univ. of Bologna, Bologna, Italy
`B. L. HUGHES, Theory & Systems
`ECE Dept.
`North Carolina State Univ., Raleigh, NC
`R. A. KENNEDY, Data Commun.
`Res. School Info. Sci. Eng.
`Australian Nat' I. Univ .• Canberra, Australia
`R. KOHNO, Spread Spectrum Theory & Appl.
`Div. ECE, Yokohama Univ., Yokohama, Japan
`U. MITRA, Spread Spectrum/Equalization
`EE Dept., Ohio State Univ., Columbus, OH
`C. ROBERTSON, Spread Spectrum Syst.
`ECE Dept.
`Naval Postgraduate School, Monterey, CA
`S. ROY, Theory/Systems & Electronic Processes
`EE Dept., Univ. Washington, Seattle, WA
`W. E. RYAN, Modulation. Coding & Equalization
`ECE Dept., Univ. Arizona, Tucson, AZ
`C. TELLAMBURA, Multicarrier Svstems
`Information Tech., Monash Univ .. ,
`Clayton, Australia
`
`Wireless Communication
`S. ARIYAVISITAKUL, Wireless Techniques & Fading
`Home Wireless Networks, Norcross, GA
`N. C. BEAULIEU, Wireless Commun. Theory
`EE Dept., Queen's Univ., Kingston, Canada
`
`·i i
`
`''
`
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, INC.
`Officers
`
`KENNETH R. LAKER, President
`BRUCE A. EISENSTEIN, President· Elect
`MAURICE PAPO, Secretary
`DAVID A. CONNER, Treasurer
`ARTHUR W. WINSTON, Vice President, Educational Activities
`
`LLOYD A. MORLEY, Vice President, Publication Activities
`DANIEL R. BENIGN!, Vice President, Regional Activities
`DONALD C. LOUGHRY, Vice President, Standards Association
`MICHAEL S. ADLER, Vice President, Technical Activities
`PAUL J. KOSTEK, President, IEEE USA
`DAVID G. DAUT, Director, Division Ill-Communications Technology Division
`
`DONALD CURTIS, Human Resources
`ANTHONY DURNIAK, Publications
`JUDITH GoRMAN, Standards Activities
`CELIA JANKOWSKI, Regional Activities
`PETER A LEWIS, Educational Activities
`
`RICHARD D. SCHWARTZ, Business Administration
`W. THOMAS SUTTLE, Professional Activities
`MARY WARD-CALLAN, Technical Activities
`JOHN WITSKEN, Information Technology
`
`Executive Staff
`DANIEL J. SENESE, Executive Director
`
`IEEE Periodicals
`Transactions/Journals Department
`Staff Director: FRAN ZAPPULLA
`Editorial Director. VALERIE CAMMARATA
`Production Director. ROBERT SMREK
`Transactions Manager. GAIL S. FERENC
`Electronic Publishing Manager. STEPHEN COHEN
`Managing Editor: MONA MITTRA
`Associate Editor: LISA M. PERRY
`
`IEEE TRANSACTIONS ON COMMUNICATIONS (ISSN 0090-6778) is published monthly by The Institute of Electrical and Electronics Engineers, Inc. Responsibility for the contents rests upon the authors and not upon
`the IEEE, the Society, or its members. IEEE Corporate Office: 3 Park Avenue, 17th Floor, NY 10016·5997. IEEE Operations Center: 445 Hoes Lane, P.O. Box 1331, Piscataway, NJ 08855·1331. NJ Telephone:
`732·98).()060. Price/Publication Information: Individual copies: IEEE Members $10.00 (first copy only), nonmembers $20.00 per copy. (Note: Add $4.00 postage and handling charge to any order from $1.00 to $50.00.
`including prepaid orders.) Member and nonmember subscription prices available upon request. Available in microfiche and microfilm. Copyright and Reprint Permissions: Abstracting is pennitted with credit to the
`source. Libraries are pennitted to photocopy for private use of patrons, provided the per-copy fee indicated in the code at the bottom of the first page is paid through the Copyright Clearance Center, 222 Rosewood
`Drive, Danvers, MA 01923. For all other copying, reprint, or republication pennission, write to Copyrights and Pennissions Department, IEEE Publications Administration, 445 Hoes Lane, P.O. Box 1331, Piscataway, NJ
`08855-1331. Copyright © 1999 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Periodicals Postage Paid at New York, NY and at additional mailing offices. Postmaster: Send address r
`changes to IEEE TRANSACTIONS ON COMMUNICATIONS, IEEE, 445 Hoes Lane, P.O. Box 1331, Piscataway, NJ 08855-1331. GST Registration No. 125634188. Printed in U.S.A.
`
`1 __L
`
`Hughes, Exh. 1023, p. 2
`
`

`

`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47, NO. 10, OCTOBER !999
`
`Comparison of Constructions of Irregular Gallager Cod s
`David J. C. MacKay, Simon T. Wilson, Associate Member, IEEE, and Matthew C. Davey
`
`g
`:0
`<1l
`
`(ij
`<.>
`
`0.1
`
`0.01
`
`1e-06
`
`.0 e a. e 0.001
`UJ
`ffi 0.0001
`1e-05
`·;:: ·a.
`E
`UJ
`
`'~
`~F(16) lrre~
`
`GF(2)
`
`Reg
`GF(2)
`
`~ lrreg GF(8)
`
`-0.2
`
`0
`
`0.4
`0.2
`Eb/No (dB)
`
`0.6
`
`0.8
`
`Abstract- The low-density parity check codes whose perfor(cid:173)
`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 Gallager codes normally take N 2 time to encode, we
`investigate constructions of regular and irregular Gallager codes
`that allow more rapid encoding and have smaller memory re(cid:173)
`quirements in the encoder. We find that these "fast encoding"
`Gallager codes have equally good performance.
`
`Index Terms---Channel coding, error correction coding, Gauss(cid:173)
`ian channels, graph theory, iterative probabilistic decoding, ran(cid:173)
`dom codes.
`
`I. INTRODUCTION
`
`~-
`
`G ALLAGER codes [3], [4] are low-density parity check
`
`codes constructed at random subject to constraints on the
`weight of each row and of each column. The original regular
`Gallager codes have very sparse random parity check matrices
`with uniform weight t per column and tr per row. (We will
`also use the term "regular" for codes that have nearly uniform
`weight columns and rows-for example, codes which have
`some weight 2 columns and some weight 3 columns.) These
`codes are asymptotically good and can be practically decoded
`with Gallager's sum-product algorithm giving near Shannon
`limit performance when large block lengths are used [6]-[8].
`Regular Gallager codes have also been found to. be competitive
`codes for short block-length code-division multiple-access
`(CDMA) applications [10].
`Recent advances in the performance of Gallager codes
`are summarized in Fi~ I. The rightmost curve shows the
`performance of a regular'Oinaf)'__Gallager code with rate 1/4.
`The best known binary Gallager-codes are irregular codes
`whose parity check matrices have nonuniform weight per
`column [5]; the performance of one such code is shown by
`· the second curve from the right. The best known Gallager
`codes of all are Gallager codes defined over finite fields GF(q)
`[I], [2]. The remaining two solid curves in Fig. I show the
`performance of a regular Gallager code over GF(l6) [2] and
`
`Paper approved by S. B. Wicker, the Editor for Coding Theory and
`Techniques of the IEEE Communications Society. Manuscript received
`August 11, 1998; revised January 27, 1999. This paper was presented in
`part at the 1998 Allerton Conference on Communications, Control, and
`Computing, Allerton House, IL, September 1998.
`The authors are with the Department of Physics, University of Cam(cid:173)
`bridge, Cambridge CB3 OHE, U.K. (e-mail: mackay@mrao.cam.ac.uk;
`stwll@mrao.cam.ac.uk; mcdavey@mrao.cam.ac.uk).
`Publisher Item IdentifierS 0090-6778(99)07784-3.
`
`Fig. I. Empirical results for Gaussian channel, rate l/4 left-right: irregular
`LDPC, GF(8) blocklength 24000 bits; JPL Turbo, blocklength 65536 bits;
`regular LDPC, GF(16), blocklength 24448 bits; irregular LDPC, GF(2),
`blocklength 64000 bits; regular LDPC, GF(2), blocklength 40000 bits.
`(Reproduced from [!].)
`
`an irregular code over GF(8) with bit-error probability of
`10- 4 at Eb/No = -0.05 dB [1]. In comparing this code with
`the rate 1/4 turbo-code shown by the dotted line, the following
`points should be noted. I) The transmitted blocklength of the
`irregular Gallager code is only 24 000 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
`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-product algorithm [9]. Turbo(cid:173)
`codes make undetected errors because they have low-weight
`codewords. For Gallager codes, the rate of occurrence of
`undetected errors is extremely small because they have good
`distance properties (the minimum distance scales linearly with
`the blocklength) [4]. In all our experiments with Gallager
`codes of block length greater than I 000 and column weight at
`least 3, undetected errors have never occurred.
`The excellent performance of irregular Gallager codes is the
`motivation for this paper, in which we explore ways of further
`enhancing these codes.
`The irregular codes of Luby, Mitzenmacher, Shokrollahi,
`and Spielman [5] have parity check matrices with both nonuni(cid:173)
`form weight per row and nonuniform weight per column. It has
`not yet been established whether both of these non uniformities
`are desirable. In our experience with codes for noisy channels,
`performance is more sensitive to the distribution of column
`weights. In 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
`
`0090-6778/99$10.00 © 1999 IEEE
`
`Hughes, Exh. 1023, p. 3
`
`

`

`[i
`~ I
`I
`
`J
`
`' 'I ;:
`vi
`
`~ '
`j
`,. '!
`I .
`~ -\
`
`j
`
`I'
`
`':
`
`1450
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47, NO. 10, OCTOBER 1999
`
`3
`
`33
`
`®®
`
`93p
`
`3
`
`<--- -- 7 -
`
`9
`
`>
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1.1
`
`1.2 1.3 1.4 1.5
`
`1.1
`
`1.2 1.3 1.4 1.5
`
`1 '1
`
`1.2 1.3 1.4 1.5
`
`93a
`
`93x
`
`93y
`
`0.01
`
`0.001
`
`0.0001
`
`0.01
`
`0.001
`
`0.0001
`
`0.01
`
`0.001
`
`0.0001
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1.1
`
`1.2 1.3 1.4 1.5
`
`1.1
`
`1.2 1.3 1.4 1.5
`
`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 (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: Eb/No in dB. All codes have
`N = 9972 and K = 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, that is, a pseudo(cid:173)
`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 tQ. 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
`
`I
`1
`
`Hughes, Exh. 1023, p. 4
`
`

`

`.,,
`
`1-
`
`i.
`
`!I
`i i
`
`' .
`
`:
`
`~
`
`~
`
`I
`
`i,i
`II'
`"
`
`11·
`·ll
`1!
`I!
`ii
`! ~ t:
`
`i·l
`I!
`1:
`
`I I
`
`f
`
`:,~ .
`
`I •
`\
`
`~
`I
`f'
`
`i
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47, NO. 10, OCTOBER 1999
`
`1451
`
`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 = 10 000. 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
`observer failures out of n trials, P± = p exp(±alog p) where
`ITlog p = J(n- r)j(rn).
`
`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 IA in [8].) A second variation requires that the
`graph have no cycles of length less than some I. (Similar to
`construction IB 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(cid:173)
`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(cid:173)
`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.
`• In a sub-Poisson construction, the distribution of high
`weight columns per row has smaller variance than a
`Poisson distribution.
`
`III. COMPARING POISSON, SUPER-POISSON,
`AND SUB-POISSON CONSTRUCTIONS
`
`. A. Profiles and Constructions Studied in this Paper
`1) Regular Codes-3 and 33: As our baseline, we study
`regular Gallager codes with weight per column exactly t = 3
`and weight per row exactly tr = 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
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`3 -
`93p ..
`93y .....
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`3 -
`33 ····-
`93a --·-
`93p .
`93x -----
`93y ....•
`
`1.1
`
`1.2 1.3 1.4 1.5
`
`1.1
`
`1.2 1.3 1.4 1.5
`
`(a)
`
`(b)
`
`Fig. 3. -(a) Comparison of one representative of each of the constructions: 3
`(regular), 93p (Poisson) and 93y (super-Poisson). (b) Representatives of all
`six constructions in Fig. 2. Vertical axis: block error probability. Horizontal
`axis: Eb/No in dB.
`
`TABLE I
`THE Two PROFILES STUDIED IN THIS PAPER
`
`Profile 3
`
`Profile 93
`
`Column weight Fraction of columns Row weight Fraction
`3
`1
`1
`6
`Column weight Fraction of columns Row weight Fraction
`I
`7
`3
`11/12
`1 12
`9
`
`an integer (for example, "3") denotes the superposition inside
`that square of that number of random permutation matrices.
`The matri~es 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 I' s are added to 1/12 of the columD.s. 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.
`Poisso~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-Poisso~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
`1) Variability Within Each Construction: For each · con(cid:173)
`struction, we created several codes in order to assess the
`variability of performance within each ensemble. All codes
`
`Hughes, Exh. 1023, p. 5
`
`

`

`1452
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47, NO. 10, OCTOBER 1999
`
`10000
`
`1000
`
`100
`
`10
`
`0.1
`
`~\\
`
`+
`
`+
`
`+~\
`+
`\'\
`\'\
`+
`\\,
`\\
`\\
`++\
`"'
`\~\
`
`~ ,
`
`i
`
`I
`I
`H
`
`(a) Comparison of irregular 93y with regular 33 code. Vertical axis: median number of iterations. Horizontal: Eb/No in dB. (b) Histogram of
`Fig. 4.
`number of iterations for 93y code at Eb/ No :::: 1.4. (c) Log/log plot of iterations histogram showing that the tail of the distribution is well approximated
`by a power law. The straight line has slope -8.5. Above 50, iterations were binned into intervals of 5.
`
`10 20 30 40 50
`
`10
`
`100
`
`(b)
`
`(c)
`
`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: 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
`
`checks
`
`• • • • •
`
`. Jf2\li:
`
`b1ts oeeooeoo
`
`(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
`
`• • • •
`
`-~ b1tsoeeooo
`
`(2)
`
`in construction lA 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.
`families are
`3) Comparison of Constructions: The six
`compared with each other in Fig. 3. There are no detectable
`differences between the regular codes 3 and 33. There is a
`
`-----N-----
`
`-K - -
`
`H ·B~C-+i
`
`Encoding procedure:
`
`Bits !1 ... tK are defined to be source bits.
`
`Bits tK+l· •• tN-M< are set in sequence, using
`the mth parity check to determine tK+m·
`
`Bits tN-M<+l· •. tN are set equal to:
`c-1Bt'mod2
`where t' = (It ... tN-M<J' and c-t is
`the inverse of C in modulo 2 arithmetic.
`
`This costs (N -Mdtr computational
`operations, where tr is the typical
`weight per row.
`
`c- 1 can be stored in M~ bits of mem(cid:173)
`ory. The product Bt' can be com(cid:173)
`puted in M<tr computational opera(cid:173)
`tions, and the multiplication by c-1
`takes M~ operations.
`
`Fig. 5. Upper panel: general form of a fast-encoding Gallager code. Hori(cid:173)
`zontal stripes indicate low-weight rows. The diagonal line is a line of l's.
`The matrices B and C are of dimension M < x ( N - AI<) and M < x M <,
`respectively. Lower panel: the fast encoding method to generate a 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.
`Thus, we find that at least for the 93 profile, sub-Poisson
`constructions are inferior to Poisson constructions, and super(cid:173)
`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(cid:173)
`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/No = 1.4, the tail is well
`approximated by the power law: P( T) ""' r- 8 ·5 , where T is
`the number of iterations. At Eb/ N0 = 1.2, the distrib