0
`
`LIBRARY OF CONGRESS
`
`•
`
`Office of Business Enterprises
`Duplication Services Section
`
`THIS IS TO CERTIFY that the collections ofthe Library of Congress contain a
`publication entitled IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATION,
`Volume 16, January- June 1998, call number TK510l.A1 I35, and that the attached photocopies
`-the spine, February 1998 issue- Title page/Table of contents page, verso oftitle page/table of
`contents page, Copyright date stamp page 137, back cover containing Table of Contents page,
`and pages 219 through 230,- article entitled, "Iterative Decoding of Compound Codes by
`Probability Propagation in Graphical Models" by Frank R. Kschisfchang, and Brendan J. Frey(cid:173)
`are a true representation from that work.
`
`THIS IS TO CERTIFY FURTHER, that work is marked with a Library of Congress
`Copyright Office stamp that bears the date February 23, 1998.
`
`IN WITNESS WHEREOF, the seal ofthe Library of Congress is affixed hereto on
`September 26, 2014.
`
`Gregory&~
`
`Duplication Service , Section Head
`Office of Business Enterprises
`Library of Congress
`
`101 Independence Avenue, SE Washington, DC 20540-4917 Tel 202.707.5650 www.loc.gov; duplicationservices@loc.gov
`
`Hughes, Exh. 1017, p. 1
`
`

`

`1m
`
`JOURNAL on
`
`SELECIED'
`
`.
`
`AREAS IN 552;“
`ouuumcumijs
`
`1998
`
`16
`
`_
`
`JAN-JUNE '
`
`
`
`'_i-'Iughes, Exh7017, p. 2
`
`Hughes, Exh. 1017, p. 2
`
`

`

`•
`
`~IE 'EE .J 0 U R i'f A l
`
`SELELCTED .:AREAS
`I· ;c· A-·... T··· I··· fo··:
`;·o· ~ 1\iJ l1\i, u;·
`.~c··
`N··..
`·, .. ~. J.YJ. ~YJL ··(
`. · ··~
`'·
`\·.
`...
`·
`.,
`..:
`\ -~
`::..
`
`A PUBUCA nON OF THE IEEE COMMUNICATIONS SOCIETY
`
`FEBRUARY 1998
`
`VOLUME 16
`
`NUMBER 2
`
`ISACEM
`
`(ISSN 0733-8716)
`
`CONCA'fENATED COOJNO' TECHNIQUES AND ITERA'J11VE DECODING:
`. SAILING tOWARD CHANNEL CAPACITY
`Guest Edltors-S. Benedetto, D. Divsulnr, nnd J, Hagennuer
`
`Guest Editorial . ... ................................... . .................... . .. S. ilenedetto. !J. !Ji,•.wlar. and.!. Hagenauer
`
`137
`
`PAPERS
`
`. . . ........... . ... ·.· .. -,. ....... . .... .
`Turbo Decoding as an Instance of Pearl's ''Belief Propagation" Algorithm......
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R. J. McE/iece, D. J. C. MacKay, and I .f'. Cheng
`Early Detection anLI Trellis Splicing: Reduced-Complexity Iterative Decoding .. . ..... IJ. J. Frey and F R. Kschisclwng
`Design anLI Analysis of Turbo Codes on Rayleigh Fading Channels . . .......... . . : .. . . . . .. .. E. K. Hall and S. G. Wil.1·on
`Symbol-by-Symbol MAP Decoding Algorithm for High-Rate Convolutional Codes That Use Reciprocal Dual Codes
`. . ....... . .... . ............. . ................. . ............ . ......... . ....... . ..... . .... . ........ S. Niedel
`Concatenated Decoding with :t Reduced-Search BCJR Algorithm .. .... .. .... .. ........ . ... V. Fmn:. ancl J. /J. tl1lder.wn
`Performance Evaluation of Sttperorthogonal Turbo Codes in AWGN and Flat Rayleigh Fading Channels ..... . ... .. ... .
`.......... . .... . .. . . .... . ... . .... . .. . . . ... . ... . .... . ... . .... . ..... . .. .. . ... P. Komulai11e11 and K. /'ehkonen
`Bandwidth-Efficient Turbo Trcllis-·Coded Modulation Using Punctured Component Codes ... f'. Rohert.I'OII awl r. lViir:.
`Iterative Decoding of Compound Codes hy Probability Propagation in Graphical Models ..... . .... .. ... . . . ... . . . .. ... .. .
`. . . . . . . . . . . . . . . . . . . . .
`, . . . . . . . . . .
`. . . . . . . . . . . . . . .
`. . . . . . . . . . . . .. .. F. /( Ksclrischang und IJ . .1. Frey
`Analysis, Design, and Iterative Decoding of Double Serially Concatenated Codes with lntcrleavcrs .......... . ...... . . .
`.. . ... . .. . ........ . ..... . _ .. . . . . ... .. . . _ . . . . ....... . . . . S. llmedelto, !>. J)h•.l'(l/ar. G. Mrmtorsi, and F. l'o/lam
`A Conceptual Framework for Under.~tanding Turbo Codes .. . . .. . ... . . .. .... . ............. . . . ....... .. ......... G. /Jattail
`Mismatched Decoding of lntersyrnbnl Interference Using a Parallel Concatenated Scheme .. . .. .... . .. .
`. . . . . . . .
`. .
`. . . . . ... . K. llalachtlll(/mn a11d .I /J . Antlcl.l'rJ/1
`An ln.tuitivc Ju stitication and :t Simplifi ed ln1plemcntation t)l' tl:c l'vi;\P llccodcr for C'onvolutioJlal Codes . .. .. .. ... . . .
`
`140
`. 153
`160
`
`175
`IS6
`
`1l)(i
`206
`
`219
`
`211
`245
`
`255
`
`Multiple Differential Detection of Parallel Concatenated ConvolutionnltTu1ho) Codes in C'orrehlled Fa~t R:1ykigh Fading
`I {) Mrtrslr1nt! !11/(l 1'. '/: Morlrio{Jflllfo.l'
`On llt:rativt: Solt -!1cL·ision f1 t:Ct>di11g ol LillCar ll111:11Y Blod: (',lk'.'> a11d Prll(lllcl Cmles
`f.lrr rl\, M /lu,·.,,.,,. untl M_ llu-ifh!l l h
`I<
`
`26.'i
`
`276
`
`1 (
`
`, 1111 /JI//1 ·,I oJ! l~u1 k ( ·, q 1 ' / J
`
`I
`
`r I
`I
`I
`I
`I
`' I
`I ,
`I I
`I
`
`Hughes, Exh. 1017, p. 3
`
`

`

`IEEE COMMUNICATIONS SOCIETY
`
`tilt,. ·11-JJ: ( 'otlllllUtllcalions Sncicty ~..: onsi.-.t~ ol' .111 h.: k,.:nnttnunications including IL'IL·photlt.:. tt:lt•graphy. facsimile. and poinl~lO - poillt tdcvision. hy
`ittll'lt.:'<il ul
`liL·Id cd
`lht•
`ck c ltPIIW ~ tH.:h~ fU 11f '! t C.1J ft~n . tll,,:fuJing racJiH, \\It · . • t~• ial. u t ulc t ~ tuLi nd . lO.I.\Hil . 1t1 tJ suhntarine r..:ahk~: \\avcguidt•s. cnntmunication satl'llilc:-.. <.md lasers: in marine. w.!ronautical.
`ign.tl , hwagl' .uhl
`l''!! ·uaation: tckc:otnmtmit:ation error Jctt'<:liou ;uu.l t:nrrcctinu; multipk xing a11L1 carrier tcrhnilJucs ;
`..;p<KL'. ;tnd li~ ,·d "' lli•m -. .:n k•'; n .. ')le;Hcr-.. t1ultu td.tyiug.
`1111 1 ' 't tllllllllfl t\ ullt r1 lh 11Jry.
`cc~rnttlUtlit·;tri, 111 ,, .. tt• hHI ~· 'Y .., IL'tn': d<~ljl cc u tt i11UIIil. alil)lt':
`In additic'm ln til • ,thu.H•, this JOl R~. nr t1n: U· ll · TKA ~.,,\t 1\t lllNS 0 ,
`( 'u~ I~UJ NIC:\TIIlt'-:S ctH\Iaills paper" pcnaining to analog am.l digital signal pn~.:css ing aru..l nHx.lulatiun.
`audio :111d 'Jtk u l' th'lkfit tg tcl'hniquc..'"i:: tlw t h~·nt ) 111tf dcs ie;.n ,,f H.Hl~rtlhh·"· rc..·..:ncrs. and n:pcatcrs fur communil'alions via opfical anti sunic nll'dia, the design ant..l analysi . ..; of
`nunputct LllllllntpltC<I\ion "Y"Il'lll'. and I he dcrL' InprnL'nt of ccHnlllunitation ~olhs.: arc. Contributions of theory enhancing the un,lerstanJing of <.:omnHmi(.·;.ltiun systems ant.l t.:chni4uc~
`.trc indudcd . a'i arc d i~ l·w. :-. it~th of lhl: stK:ial inlplictttions ol the Ucvclopmcnt of conununil":nion technology . All mcmhcrs uf the IEEE arc cligibk for m"'~ mhcrship in the Stlt.:icty UfHln
`'"""'·" Snc i,· ty nicmfl<:r,hip fee nf ">~.1.<10. Mcmbc" may receive this JOURNAl. upon payment of an adJilional $27.1MJ ($SO.L)(I lola)). the IEEE TR ANS..\ CATIONS
`paylllclll o'r the·
`0.~ C<l~l.\ll );l( MIONS "I~"' paymclll of all addilo11al $2'1 (Kl iS50.(~11otal), or ,both publicatio11s upo11 paymcm of an aJJilinnal S54.flll ($77 .1N) lola!). l'or i11formatio11 on joining.
`"tih: lo I Ill' I EEl·: al riH· addt ~,.·~s h!:IO\'- Mt•mhet <O('it~~ o/ Triiii.\CI<timn'/Jowlwl\' are fm• pt'rJmud UH' oflly.
`
`•
`
`IEEE COMMUNIC,\TIONS SOCIETY
`JOURNAL Editorial lloHrd 199!1
`J-SAC llome Pngc URL: hllp://gump.hellcore.corn:SOOO
`
`W H TR..1 :>: rf·IC /)i~e•uo r of Jmm11ilr
`Virginia 'kch
`-L\2 NL'\\ Engincct ing Rldg
`Bladshurg, VA 1·!061-0J:'i(J
`htrant~r@ vt . ~du
`
`L fl . Mlt.SII'IN. Eclitor·ia-Chief
`Dept. Elect. and Cumput. Eng.
`Mail Code 0407
`Uni y. of California, SD
`La Jolla, CA 9209~
`tnibtcin @cce.ucsJ .cdu
`
`SuE L. M c DosAI o. Erc. ·l/(il•e Editor
`Bellcorc, Rn1. I A10Hf~
`445 South Street
`Morristown, Nl 07%0--1910
`sue@bellcot'e com·
`
`A. M Bt:SII
`NSF
`420 I \Vil.\on Boukvard
`Room 117:'i
`Arliugtoll . VA 222.HI
`
`w B IL\
`IBM Res . I ab. Zut idt
`SalllllL'I ~ Lra ss c ~
`MH01 Ru sc hlikon ZH
`Switzc1laml
`
`J. F HAns
`Dept. Elec. Eng.
`Coneordia Uuiv.
`1455 De Maissunncu'c
`Montreal. Quelxc
`Canada ll .iG I M8
`
`N . M ,\ XFMl Hl:K
`AT&T l.aboratories
`Bldg. 103. Room AI 15
`180 Pat k Ave.
`Florham Pat k. NJ 07932
`
`Senior Editors
`R. RA:Vti\SW/IMI
`rcllabs
`15 Skyline Drive
`Hawthorne, NY 105~ 2
`
`w. H. TRAN!ER
`Dept. Elcc. Eng.
`Uni v. of Missouri-Rolla
`Rolla. MO 6540 I- 0249
`
`T. s. R .. IPPAPORT
`The flradlcy Dept. Elcc Eng.
`615 Whittemore Hall
`Virginia Polylech. lnst. & Stale Univ.
`Blacbhurg, VA 24061 -0 Ill
`
`D. P. TAYLOR
`Dept. E & E Engineering
`Uni v. of Canterbury
`Pri vale Bag 4800
`Chrislchurch, New Zealand
`
`TliE INSTITUTE <W ELECTRICAL ANI> ELECTRONICS ENGINEERS, INC.
`Officers
`
`FRIEDOI F M. SMITS, Vil'c Pre.1idcnt, Puh/ication !lctivitit!l'
`JO'iU'I! LIORIJOt;NA. /'resident
`DANIEL R. BENIGN!, Vice Pre.\'ident. Regional tlctivitit•.\·
`KLNNHII R LIKI·~. /'rr.vit/ent -(0/cc I
`i\ NH JN IO (' n ~ s ros. Seactarv
`L JoliN RANKIN!', Vice President, Stmtdanl1· ' ' u ociation
`BRt'CE A. EISF.:-<SI'I·IN, '(i·ea.\'111'1'1'
`LLOYD A. MORLEY, Vice /'resident, Technical Actil•itie.r
`JuliN R. REIN ER I'. Preside11/, IF:'EE USA
`AKIIII ·I! WI NSI<JN. Vice f'rf'.l'idenl, t.'dunuiona/ ,\r·ti l'itin
`D AV ID D. DMJ r. Oin•ctor. Oil'i.1·io11 'f/1---Commllnicatimt.\' 'f'e<'flllolog \' /Jivisio11
`
`Do:- Ill> C't ~II .> . //Will/It flnourct'.l
`t\.~ I HIJ."') I. h HRAIW, l'lti>li< 'llliOII.I'
`II illllll GOKM ,\N Standarc/.1· Activitie.1·
`Ci·.CFI.I,\ IM<Iu'>IVSKI. Rcxiolla/ ;lctil•irie ,·
`J'f:IEK t\ [,1\WIS, /:dlll'aliollll/ i\clil'ilil'l
`
`Executive Staff
`[),\.'JIEL J. SENESE, /~: 1'1'< '11/il 'l' !Jirector
`RIC'II ARI> D. SCI!Wo\I!TZ . filll'illt'H ;\dministmtioll
`W . THOM,\S St.:rn~. l'rc>(nsimwl Actil'ities
`MARY WARD-CALL\N, Tr·cfllli{'(l/!lctil'itie.\'
`JOHN WJTSKEN, !l~{i>rflla/ir}(t 7i!dtuo("gy
`
`IEEE Periodicals
`Translrctions/Joumals Department
`Sto!l/Jin•ctr!l: fR ,\N Z ·IPPL'I LA
`f.dittjl ia/ !Jirec/01: VALERIE CMviMARAI~I
`Pmd1u lion LJircctor: RtlUER'I SMREK
`[rl/IISII< lioll.l' Afwwger: GAIL S. FERENC'
`1:'1.-t·tmnic Pu/llil'hi11g Ma11ager: To ~ r BoNnttll;t'K
`Mim1iging J:'ditr11: GfR .·IllliN E E. KROIIN
`
`11:1·T I(!~ I~ ~ \1 ll\i\)IIICI~.D . \RE..\.O...:I;...:(rl\1 \ II
`, " l ;m u ~ n ~ h ·hllu••)'
`.'W_ \lJ():":stiSSN07:n X7Hili,publis lwt l mrw l llllt.:>
`~\ •• !!u"'· "''p' c m ~· r. t h. luhct.
`1 u ~ l un~:.
`\r~•tl.
`l1 \l~ l ,,
`;lnd I'Jl'l c·mha h\ lht..' lno:.tllllll' ot' L·.kLll'l l':ll and t·. il'l'\IOIIic..:, Fnginl~CIS Inc..· Re ... pon~ihilit v lor l h·· \.'l'll1 HI ~ ft.:'\1, ''I" '" lh~ ol ll lhun .11'hl
`lt111 ll f'I\UI dl..:
`lhl ·h . Ill • ' Hd..: a ·.I ~ 'II H Ha.:I L 01'
`'cuft!J·: H . II • ., I·'"·. 1'.0
`II• I• ~ t " 'll''r •I•· tun,• ·: II ~ I' o•l 1'1 Sll .. ·l. 'lc<1 Y»JI.. '' '
`I IIIII 1 ! .I'l l. IEEJ•; Opcr.ollmL~
`llo•' I 1.11 . " ' ' '·'' ""' ") · "' I IIXK~~ · I' ~ I
`'" "'' "'"' r
`· ·~ I I ~·! 11rinvl'llhll•.ollll ol Jllrou lllll ll•ooo: lllllivilhl>l l "'" ' \ II.FI ~klllhcJ
`.
`IOJ)(j I 111>1 ~"I'' ' Ill IV I. "''nmcmhcr·. ~21 1 1HI r ll< •IllY r Nnl~ ;\dJ
`I IH I pu~J g~
`'lj h lq l hmor· , '
`\ ).,ulahk· IU t l1 it• t ~rj h lt •
`tl huUI'\! r"h ,j' lltl••utt •t
`I•• ....
`I
`ft•ttJfl••• ttld ltt ll t ll l~ tH I ~ t 'l l h~t.~ l tp ! um jlrl \1'\ tt\'ouLrh k liP"" w 'f11\.~'1 1
`, t 1.~ lt•IIH
`,tth l htnlln1•
`''' ' II
`t, l I'') '•
`•tltlll
`t " I '~ dJtht ~1 iltt U: "'f.H'Ittl 1•.,, ut l•..-.fu u't: •\h .. u '"' II U' j, jt<l!l !I HII"·~I .. -.uh , t\. \ltl lu tit..: :-..tlW u~ . LibtM t ~'lt .ut• jK.•rnlilh.'tl 111 phn•• ·, ~~p~ tor fll'"'''"' uw u l (1 1li •'U1\, r •vvft_l •ll
`Hhl tut• '"" '11•
`tl dt• I"'H h ll tl •II •h·· lu .l P•l l' ~; a.. f'·" d th ii\U!-! h 1 h~· ('up\ HJ.!hl ( l ~utltUt.t: C•: ll l\.' 1 1! 1(, ; C'\\ l~ ld P 11\' \ ' llc ut\'L'I ~. ;\1" UI 'J' l
`Jh•· 1 •t
`'I'" h .. 11 11 h
`Ill 11U11.:r
`,t lnl m th•• • h•
`f ·, u
`tlf 1 ~ (1111•11• ilfo ll r'• 'HH I ''lUll ' ttt ' '" ( \·lt\ll~h1 , •I!Hl f'•' IUU "'"" .., I '4' J'ill lllh' lll , H T J I '•Jh lh .• tti• •l1 ~ ,•\LI111hu •ll .lllnu , l l
`l it h·.., I a rh' P l )
`I 1 \ I, Pt
`-.&l ii\\JI )' , NJ
`• • II' t u o~
`l h• -.:
`It filii If
`t! ~" '""L.
`'l' 1011 .It .llh.lt t H m rl
`q.~;: , t; 1 'f , . ·1•\ tt II!
`l~t't.i h
`,\ lltl)~ltt
`lL""''' ·t•tl l'l! lc ttd n 1l\ 1'•,'-III C'-' l'.~~tl u l
`,
`, uailln~
`'l·h ' ''' t1 ,n, l Ht·· """"' 1-!t ,• u t.,•t · ltn
`ll w ltl •th ·lh'
`'i,·ll ·l nidt l.- ,lt;l!l !.!~o' .. lllllll !t l l
`· \~.'.\ 1
`( 1.'.)11 1 1 111 • \ 1~ 1
`.\.'o
`l >,t '•
`t \ 1\ lt
`l~ ut••
`l' ( l Htn l \l l
`l't ·~
`~~ ~~~l\ t\ I
`II:~Xi l \l l.
`\J fp·, fi J·I
`l f "' fh ,..
`.1(
`l'u•,llfJ ;I .. I•.••:
`11!itL ,·
`ciS I
`~ ~ ' 1!1 :- lt ll'tntl '" 1 ~.:::.(d ~I ~ X p, inh·d 111
`I
`,') -\
`
`Hughes, Exh. 1017, p. 4
`
`

`

`AL oN SELECTED M~Ei\.~ IN CO,\IMUNICtXfiONS, VOL. In, NO. 2, FEBRUARY i'Jl)H
`
`Guest Editorial
`
`() '
`' '
`
`.. ,
`
`r
`
`I
`
`'t I
`
`1
`
`,
`
`•
`
`..
`-.;!rom Shannon theory1 we know that increa~1ng the code· output pi:bvided by an a posteriori probability'illgorithrri) to the
`.I' ' word iengfh n of block cadets (or the constraint H:~g~ of next decoding· stag~, Strictly speaking;· the name- ''turbo~· has
`nothing to do with the encoder: rather', it is justified because
`convolutional codes) leads to better performance. It is also weU
`the decoder uses its processed output values as a priori input
`known that the· comple~ity of maximum likelihood decoding
`algorithl,llS inc~::eases }Yith n, up to a point where decoding
`for the next iteration, similar to a turbo engine-.
`Since 'the first appe'aranc'e of turb'o• codes and a related
`becomes physically· unrealizable.
`struc.ture 'iri t993 [4j; (sU maily ot the snucturat properties of
`~us, r~ ,'e~h .!~ ~.oilln!; t~eo~ has ~een ~il.?Y, ptqpos:us
`tlt.rbo c:odps· hliv~ how beeri put oh ' firm~ theoretical foothi~
`aimed at th~ constructtQn of p~;>werfuJ codes wtth large equtv-
`[ 6J-C81; ~d . of he · .forms· 'of conctiteiul.t!'btls 'witfi . inferfeavet!i
`alent block lengths: s~ctured so ~s to permit breaJting the ML
`decod~ngr iqtq ~lfriP,. e.r par,t,j~ d~~pcJing ~~~ps! thu~. obt,ai~jng have beed studied ?nd sh Wh to ·o~er s!~ilaf. lh s(u;ne caSes
`e~en · better', performance' ~lOJ--[1~]'.. TheY. fonn a class .of
`a subopdi'Il.iun yet gowerful decoding strategy. Iterated codes
`(Jl, product codes and their extension [2]\ co!leatenated codes· ' codes that, under-iterat\ve dec'odirig pemtit' us to apprdadi·
`lhe' Shan'non calmcity· at'a' blt:en'or probaHi1lty cirl fht!' 'ord~k
`[3}, ohd . large ·const!atned·rengtfl corivolutfonnl ' cod~s with
`suboptimaL decoding_ strategies,· lilce sequential deco_din.g, are of , w-'6-10'-T, s'tilf, quite· far ' fr'om-• the ' unhfnitea reliability
`promised by the Shannon' ~ap'&city ' the'dr~rtr, yet more ha.(i
`'
`.
`rlonexhaustlve ·examples :or these 11tteh1pts:
`' ' 'I . r:.
`Furthermore} '· Shanrto~c· theory' h~s proved' that' "ra'ndom"
`enough 'for 1l,~ver~ oppJlp.ati~p~: ;
`'· '..
`'
`:
`Sui::ce~sfvely , appJ ed (;· the ' iterative. d~c. oding of coilc~te"
`co~es arefeC?od; their dec~i,ng, co,mplexity; ~owever, increases
`cxponentia~y wi.tli 1~e blo~k lengt~: On the other hand,
`noted codes [9), w~'at' we would call the "turbb principl~," i.e.,
`rt 'strategyhploiting the l(erated excbartge of soft information
`the structute imposed :on, the codeS in order to· decrease
`their decoding complexity often resuft's in relatively 'poor between differen't'bidcks in ' a "co~muni~atioh receiver, could
`(a .. ~ ih part ·~a8' nlieadr·.~~~gY su~ceisfuli{applied' tti jnli~Y
`performance: As a result approaching the channel capacity or
`even, more modestly, goint 'significantly beyond the channel
`derectioti/de'coding problems such as channei ' equalization,
`codea .¥l;duf~tiO~, I~U~~·user detec~i<?D, JOint source a~a· ch~~
`cutoff rate had .been• an unreachable dreaih Of coding theorists
`nel d~coding, and 'o*ers..
`for many years; .
`.
`.
`.• .
`.
`. . .
`.
`.
`.
`·
`At the tiine t.llis' tssue was completed, there was stili a lack of
`Iri decreasing .the bit~error prbbabilit}' of a sy_stem through
`a sdtisfactpry arlalysts 'of the: iterativ~ proc~s·s\ and pf rl' tfieoret~
`channel cbdlng; w~ ca'r{use ~wo· 'approqci'Jes. The . more tradi·
`icaf explanation of why the turiJ6' decoding algorithm performs
`tional one has attempted to increase· the minimum Hamming
`distance of the code, thus reducing at the same time the word-
`as well as it does. Also, some performance bounds· seem to
`and bit~error probabilities. The goal of the second approach
`point to the fact that, theoretically, the same performance
`is rather to reduce the multiplicity of codewords with low
`should. be obtainable with significantly shorter block lengths.
`Hamming weights. This was the approach applied to the design
`'r1lese seem, at the moment, to be two of the major open
`of "turbon codes [4], ~new cod!ng strate~y that, to quote Dave proble~s· in the field. On o more practical ground, convincing·
`results are still' to 'come in those applications where decoding
`Forney (3J: "Rather than attacking error exponents, they attack
`latency' 18 'hfl issue, like fof voice triinsmjssion' and. others. ·
`multiplicities;. turning conventional· wisdom' on, its head." .: -
`The ' fir~t papbr i'ri thls iss ue, by McEJiece eta/:, describes
`Turbo·codes, in the consid~r?tion. of many..expe~s of the
`rhe' close connections be ~~eh the iterative ''turbo" decoding
`field; are one of the most excttmg and potentially Important
`~leveloprrtents in coding t~eor~ in ~any years. Th~y · cJeverly. · alg~rithrii with P~arl's beiie/propagatfolf algorithi,~~; which. is
`tp.tegrate code concatenallon tn a pseu~orandom a~proach well k~own in the artifiCial lhtelligence scientific conimunity.
`whe.re the randomne~s .and long block stze are · provrded by Once this· connecti6n is established, the belief propagation
`an tn~erleaver, a .butldt~g: block that_doe~ not: add to the
`algorithtb becplhcs tl general framework to devise (terative
`decodmg complexity .. Thts ts du~ to an tterat~ve strategy based decoding algorithms for nther codes: Closely related to trye Orst
`on ~lternately clecodrng ~w~ ~tmple c.onstltuent codes and
`paper is the pnper by Kschischang and Frey, which presents a
`passtng the so-called extmwc tnformatwn (a part of the soft
`unified f.ramework, based on a Bayesian network description of
`codes, for describing compound codes and deriving iterative
`decoding algorithms.
`
`Publisher flcm ldcntilicr s 073.l -87 16(98)00160·7
`
`07 .13 -87 [(ifi}8S 10.00 (f.)
`
`I <J<JH IEEE
`
`Hughes, Exh. 1017, p. 5
`
`

`

`l'i\LLS Hm PAPERS
`
`JIO
`
`April 1997
`May 1997
`May 1997
`June 1997
`August 1997
`September 1997
`January 1998
`Januury 1998
`1998
`
`Multi-Media Network Radios
`Future Vuice _Technologies ,
`Direct-to-User Satellite Systems and Technologies at Ra Band and Beyond
`Wireless Ad Hoc Networks
`Service Enabling Platforms for Networked Multimedia Systems
`Next Generation IP Switches and Routers
` Issue of J-SAC in which the C[dl ror Papers first appears.
`
`1'
`
`Hughes, Exh. 1017, p. 6
`
`

`

`:-rED Ar<EAS IN COMMUNICATIONS. VOL. 16. NO. 2. FEBRUARY I~'IH
`
`Iterative Decoding of Compound Codes by
`Probability Propagation in Graphical Models
`
`Frank R. Kschischang, Member, IEEE, and Brendan J. Frey
`
`219
`
`• (.
`
`Abstract-We present a unified graphical model framework for
`describing compound codes and derJving iterative decoding algo(cid:173)
`rithms. After reviewing a vnriety of graphlcaJ models (Markov
`rnndom fields, Tanner graphs, and Bayesian networks), we derive
`a general distributed marginalization algorithm for functions
`described by factor graphs. From this general algorithm, Pearl's
`belief propagation nlgorlthm is easily derived as a special case.
`We point out that recently developed iterative decoding algo(cid:173)
`rithms for various code.'!, Including "turbo decodlng>t of parallel(cid:173)
`concatenated convolutional codes, may be viewed as probabWty
`propagation In a graphical model of the code. We focus on
`Bayeslan network descriptions of codes, which give a natural
`lnput/stateloutput/channel description of a code and channel, and
`we indicate how iterative decoders can be developed for parallei(cid:173)
`JDd serially concatenated coding systems, product codes, and
`ow-density parity-check codes.
`Index Terms- Concatenated coding, decoding, graph theory,
`terative methods, product codes.
`
`I. INTRODUCTION
`
`C OMPOUND codes are codes composed of a collection
`
`of interacting constituent codes, each of' which can
`>e decoded tractably. rn this paper, we describe various
`traphical models that can be used not only to describe a
`vide variety of compound codes, but also to derive a variety
`,f iterative decoding algorithms for these codes. Prominent
`1mong compound codes are the t11rbo codes introduced by
`Jerrou eta/. [ 1], in which the constituent convolutional codes
`nteract in "parallel concatenation" through an interleaver.
`t is probably fair to say that the near-capacity error-rate
`terfonnance of turbo codes has sparked much of the current
`nterest in iterative decoding techniques, as evidenced by this
`pecial issue. Other examples of compound codes include
`lassical serially concatenated codes [2] (see also [3], [4]),
`}allager's low-density parity-check codes [5], and various
`roduct codes [6], [7].
`In [8] and [9], we observed that iterative decoding algo(cid:173)
`ithms developed for these compound codes are often instances
`f probability propagation algorithms that operate in a graphi(cid:173)
`al model of the code. These algorithms have been developed
`1 the past decade in the expert systems literature, most notably
`y Pearl [!OJ and Lauritzen and Spiegelhalter [II]. (See
`12]-[ 14J for textbook treatments on probability or "belief'
`
`Manuscript received September 27, 1996: revised May 8, 1997 and July
`), 1997.
`F. R. Kschischang is with the Department of Eleclrical and Compuler
`1ginc.:ring, University of Toronto, Toronto, Ont .. Canada, on leave al the
`·assachusctts l11.~titute of Technology, Cambridge, Ml\ 02138 USA.
`ll. J. Frey is with lhc Beckman lmtilutc, Uuivers ity of Illinois al Ur(cid:173)
`IIHI···Charnpaign, Urh:ma, IL 6180 I USA.
`Publisher Item IdentifierS 07 JJ -8 716(98)00225-X.
`
`propagation algorithms and [15] for an extensive treatment of
`graphical models.)
`The first to connect Pearl's "belief propagation" algorithm
`with coding were MacKay and Neal [16]-[18], who showed
`that Gallager's 35-year-old algorithm [5] for decoding low(cid:173)
`density parity-check codes is essentially an instance of Pearl's
`algorithm. Extensive simulation results of MacKay and Neal
`show that Gallager codes can perfonn nearly as well as turbo
`codes, indicating that we probably "sailed" much closer to
`capacity 35 years ago than might have been appreciated in the
`interim. McEiiece eta/. [ 19] have also independently observed
`that turbo decoding is an instance of "belief' propagation.
`They provide a description of Pearl's algorithm, and make
`explicit the connection to the basic turbo decoding algorithm
`described in [1].
`Recently, and independently of developments in the expert
`systems literature, Wiberg et a/. 'in [201 and Wiberg in his
`doctoral dissertation [21] have refocused attention on graphical
`models for codes. They show that a type of graphical model
`called a "Tanner graph" (first introduced by Tanner [22] to
`describe a generalization of Gallager codes) provides a natural
`setting in which to describe and study iterative soft-decision
`decoding techniques, much as the code trellis [23] is an ap(cid:173)
`propriate model in which to describe and study "conventional"
`maximum likelihood soft-decision decoding using the Viterbi
`algorithm. Forney [24] gives a nice description of the history
`of various "two-way" algorithms and their connections with
`coding theory.
`In this paper, we seek to unify this recent work by develop(cid:173)
`ing a graphical model framework that can be used to describe
`a broad class of compound codes and derive correspo~ding
`iterative decoding algorithms. In Section II, we review and
`relate various graphical models, such as Markov random
`fields, Tanner graphs, and Bayesian networks. These graphs
`all support the basic probability propagation algorithm. which
`is developed in Section III in the general setting of a "factor
`graph,". and in Section IV for the specific case of a Bayesian
`network.
`Given a graphical code model, probability propagation can
`be used to compute the conditional probability of a message
`symbol given the observed channel output. For richly con-•
`nected graphs containing cycles, exact probability propagation
`becomes computationally infeasible, in which case iterative
`decoding can still yield excellent results. The basic iterative
`decoding algorithm proceeds as if no cycles were present in
`the graph, with no guarantee that the computed "conditional
`probabilities" are close to the correct values, or that they even
`converge! Nevertheless, the excellent perfonnance of turbo
`codes and Gallager codes is testimony to the efficacy of these
`iterative decoding procedures.
`
`073J. ·ll716/98S I 0.00 ICJ 1998 IEEE
`
`Hughes, Exh. 1017, p. 7
`
`

`

`IEEE JOURNt\L ON SELECTED ARE1\S IN COM~IUNICi\TIONS. VOL. 16. NO. 2. fEil.RY l'i'IH
`
`(),
`
`Fig. 1. Graphical models for the (7, 4) Hamming code. (a) Markov rnnt.lom field with a maximal clique indicated. (b) Tanner gmph. (c) Bayesian network.
`
`(a)
`
`(b)
`
`(c)
`
`In Section V, we describe Bayesian network models for
`a variety of compound codes, and describe how probubility
`propagation can be used to decode these codes. As it is a
`straightforward exercise to develop Bayesian network models
`for many coding schemes such as multilevel codes and coset
`codes, and also for channels more general than the usual mem(cid:173)
`ory less channels, we believe that there are many possibilities
`for application of iterative decoding techniques beyond what
`has been described in the literature to date.
`
`II. GRAPHICAL CODE MODELS
`ln this section, we present several gr1;1ph-based models that
`can be used to describe the conditional dependence structure in
`codes and channels. Given a set U = {vt, ···, 'UN } of random
`variables with joint probability distribution p(vt 1 • • · , 'IJN ), a
`graphical model attempts to cupture the conditional depen(cid:173)
`dency structure inherent in this distribution, essentially by
`expressing how the distribution factors us a product of "local
`functions" (e.g., conditional probabilities) involving various
`subsets of U. Graphical models are useful for describing the
`structure of codes, and are the key to "probability propagation"
`and iterative decoding.
`
`A. Markov Rcmdom Fields
`A Markov random field (see, e.g., [25]) is a graphical model
`based on an undirected graph G = (V1 E) in which each vertex
`corresponds to a random variable, i.e., an element of U. Denote
`by n( v) the neighbors of 11 E V. i.e., the set of vertices of
`V connected to v by a single edge of E. The graph C is a
`Markov random field (MRF) if the distribution p(V1 1 • • • 1 ·u,.)
`satisfies the local Markov property: ('Vv E V)p(U/ V\ { 11 }) =
`1J(v/n(v)). rn other words, G is an MRF if every variable
`v is independent of nonneighboring variables in the graph,
`given the values of its immediate neighbors. MRF' are well
`developed in , tatistics, and have been used in a variety of
`upplicatlons (see, e.g., [25)-[281).
`The joint probability 111uss (or density) function for the
`vertices of a MRF G is often expressed in tenns of u Gibbs
`f G. A
`pmential function defined on the maximul cliques
`·/ique in G i a collection of vertices ~ hic h arc all pairwl. e
`neighbors, and such a clique is maximal if it is not property
`cnntained in any olher clique. orrespon ling 1 ea h clique
`11 ln the set of maximal cliques (j is a collccti n of vertice
`,1 that are contninet..f in q. Denote by S', the sample space f r
`the ran 1om variable 11.
`'iven a nonnegative poteutial fun ction
`r1lr each clique 'I E fj, i.e .. 1.1 fnn ctiun 1/•,1: IT _1• s·, _,
`'''= '#
`
`m.+ U {0}, the joint probability mass (or density) function
`over V = {vt,· .. 1 VN} is given by
`p(Vt 1 ••• 1 VN)=z-t IJ 1/!q({vEVq})
`
`(l)
`
`'I,EQ
`
`where z- 1 is a nonnalizing constant, assuming that the
`product in (I) is not everywhere zero. It is possible to define
`an MRF in tenns of potential functions defined over all cliques
`in G. not just the mnximal cliques, but any potential function
`defined over a nonmaximaJ clique q can be absorbed into the
`potential function defined over the maximal clique containing
`q.
`
`From the structure of the potential functions, it is a straight(cid:173)
`forward exercise (see, e.g., [25]) to show that the resulting
`probability distribution satisfies the local Markov property.
`[ndeed, every strictly positive MRF can be expressed in terms
`of a Gibbs potential. although the proof of this result (given,
`e.g .• in [26, ch. L]) is less straightforward. Lauritzen (15, pp.
`37-38] gives an example due to Moussouris of a nonstrictly
`positive MRP satisfying the local Markov property for which
`it is impossible to express the joint distribution as a product
`of potentials as in ( 1).
`To illustrate how MRF's can be used to describe codes, con(cid:173)
`sider the MRF with seven binary variables shown in Fig. l(a).
`There are four maximal cliques: q1 = { 11 213, 5} (dashed
`loop), q2 = { 1, 2, 41 6}, q:; -r= {1, 3,4 7}. and Q4 = { 1, 2, 3, 4}.
`From (l), the joint probability distribution for v 11 · • · 1 vr, can
`be written as a product of Gibbs potential functions defined
`over the variable subsets indicnted by these four cliques. This
`MRF can be used to describe a Humming code by setting
`t/Jq~ = 1 (which is equivalent to neglecting q,t), and by Jetting
`the first three potentials be even parity indicator functions. That
`is, 1/Jq(·) = 1 if its arguments form a configurution with even
`parity and 0 otherwise. The MRP places a uniform p_robability
`distribution on all configurations that satisfy even parity in
`cliques q11 q2, and q3 , and zero probability on configurations
`not satisfying these parity relations.
`While the potential functions ch~sen in this example define a
`linear code, it is clear that such potential function ' can be used
`f local check condi(cid:173)
`to determine a code satisfying any set
`tions. rn particular, given a set of variables U = f v11 ···, 'UN},
`let Q be a collection of subsets of
`. COITe:;ponding to each
`element E of (J, o local check condition enforces structure on
`the variables cuntuined in F: by restricting the values that these
`variables ctm assume. (For example, the check condition could
`enforce even parity, as i11 rhe example above.) By defining an
`
`Hughes, Exh. 1017, p. 8
`
`

`

`/o FREY: ITERATI VE DECODING OF COMPOUND CODES
`
`alcutor function for each local check condition that assumes
`::~ value unity for valid configurations and zero for invalid
`configurations, and by defining a graph in which each elemept
`of Q fonns a clique, an MRF description that assigns a
`unifonn probability distribution over the valid configurations is
`obtained, provided that at least one valid configuration exists.
`As we shall see, a Tanner graph is another way to represent
`the same local check structure.
`
`B. Tanner Graphs
`Tanner graphs were introduced in [22] for the construction
`of good long error-correcting codes in tenns of shorter codes.
`Our treatment follows the slightly different presentation of
`Wiberg et al. [20].
`A Tanner graph is a bipartite graph representation for a
`check structure, similar to the one described above. In such
`a graph, there are two types of vertices corresponding to
`the variables and the "checks," respectively, with no edges
`connecting vertices of the same type. For example, a Tanner
`graph corresponding to the Hamming code described above is
`shown in Fig. l(b). Each check vertex q in the set of check
`vertices Q is shown as a filled circle. In this case, a check
`vertex ensures that its set of neighbors satisfies even parity in
`a valid configuration.
`We see that the check vertices play precisely the same role
`in a Tanner graph as do the maximal cliques in an MRF.
`In general.- for each check vertex q with neighbors n(q),
`we can assqciate a nonnegative real-valued potential function
`1/lq ( { v E n('q)}) that assigns positive potent(al only to valid
`configuration$ of its arguments. We then write a probability
`distribution over the variables as
`
`p(vt, .. ·,vN)=z-t IJ 1/lq({vEn(q)})
`
`(2)
`
`qEQ
`
`where z-t is a nonnalizing constant. Of course, (2) is
`analogous to (1).
`An MRF can be ·converted to a Tanner graph by introducing
`a check vertex for each maximal clique, with edges connecting
`that check vertex to each variable in the clique. The potential
`function assigned to the check vertex would be the same as
`that assigned to the clique.
`A Tanner graph can be converted