`3%
`5.:
`
`23 H’) egrmz iii
`
`:2 gig:
`
`7. ”‘%.§.,
`5-a‘:l_,§,l§%:i:;’e§‘%:>f*§ {T ,"§%lf%§§5§€LL.§%§i..“»s¥§_f§I
`
`
`
`
`
`’
`‘
`§7§%§}§;
`;‘?=s.§“‘%§._}
`€[f‘{,7?'
`33% §§‘§l%%‘§..s‘
`
`
`
`..;3&}§er?»:a:x
`
`
`I
`
`*§I<.>s22i§<;§s§E»:>,,
`
`§l§§i:a<.';é::;
`
`
`
`€32;
`f%§;mns:m'«s:d 3.23;
`7
`saw? Has:
`:§..J'<g%}{§‘2§i()¥‘:¥.
`§%$4:§e:m:
`€fm"2r.r.ii%z:2zziei'i
`lingézxeering oi’ '£§§&:
`:1?‘ §!11s;s~1;:-éxzai éiiiii {T<3mp':aim‘
`§3egmr€mmi
`Ejim/e§*s§§}= of Eliiazsjés
`:2: 33:*%};m:;a.»€l22m2pzségiz
`
`
`
`i
`
`Replacement - Apple 1003
`
`Apple V. Caltech
`IPR2017—00210
`
`
`
`PR()('EED!N(£$
`
`l'llIRTY-SIXTH ~\:'\'Nl9Al, Al.l.l-‘.RT('):\’ (’();\"l'"PIRF.;‘i("E",
`UN COM.\'H’VlC‘\TI():V. C()NTR()I.. n\;\‘D C0.VlPl’Tl\'(;
`
`T amcr Bzgmr
`Bruce Hujck
`(Tor)fo;'rcnce ('0«( "hairs
`
`held
`('unfcr€n£'€
`St*ptt’IIIhc:r 23 — 35. 1‘W.?i
`Aucrmn Houst-
`Mmuticcfln. Illinois
`
`Spnnwred by
`l'hc ( xmrdinaned Scictusc l,,emnrzu(>r_V
`mad
`Ths: Uepnrtnicnt of Electrical and Computer Engineering
`of Ihc
`l“s’I\’ERSX'l"Y OF H,.Ll;\(H5
`at
`l,‘rhana-('hamp3i;_I,n
`
`ii
`
`
`
`Coding Theorems for “'1‘ux'b0-Like” Codes’
`
`Uaritxslx l?)ivs21l:\,1'. llui Jin, and Robert. J. N'l('l.§Iliot:(t
`.l«;rt Pmpulsirm l,:1l><>ml.<‘>ry and C21lil'<m1i:1 In.sl:itutr= nf‘"I‘<2<rl1x1(>lngy
`§:);“A"52‘(.i("I‘E)<\ C:1lif(>rniz1 USA
`
`E-mail: dariuslmshannon.jp1.nasa.gov,
`
`(hui. rjm)@systems.caltech.edu
`
`Abstract.
`
`In .".l}iS‘ pzxpor xw.‘ (liS(‘i1;<s l»H'V(.}':\’ Crjuiling clu-m‘m2.§ Fm” <=:nsmrxb!<rs <;n"'rmj1ir1g qvstlrrrxgw whicrh
`nrw lmilt. fmzn fi,\'0<‘1 mzm)Iur:i<)r1zzI (r<>(lrr.< itll(?(‘(i()IlIl(‘(‘l(?(1 with mrznlcim ir1te>r1<..=:zs'<*r5. Vl/9
`cm’! £11059 syatexzxs “tm‘b<2~lik<,=‘" C'£)(1(fS and tlzqv mcrludtr as .~;p<—:<r1'.=z1 <.‘a.~;¢,-s both the <:1;Ls‘sir21I
`riirbo m<’I«;>.'~' {/1,2.-3,5 sum’ r}zers(¢1'i;1l <'<:>:zr:;zI.c>1zL2xcinI2 ()fx'r1tc>1'!c>;a1x's><I mI1w.>Iuti<mal (‘<:.2<1e:~'
`..
`XV?» e:»ffeé;‘ el gr?r1z‘I‘u1 C‘-"tII‘_l'l"(,‘EllI'(’ zzbullt the l,u:lz2.u-iuz of Hm <?r1.\‘¢~,‘II1l)](~’ »"‘1ma.\:i:znxrn-Ulu,
`.» mm}
`
`<lc.=m<'1m',l w:_:r."<.'l (-rmr ;2:'ol,>z»Ll,2i1i!_)‘
`11.5 the Wr.)I’(i1 1r_*n;;t.l1 s.1;>pr'<.v<_‘IM:< iru‘ir1it§‘.
`l«V.»'» prove’ tllis
`rrurzjc~('£z1r*<‘* for ;2 .‘«‘iII![)1c" c'I;t.s':s cu” mic‘ .l_/q s:'=1‘iexl1y Ct")!I('€l(f‘l'lZl.C(‘(I
`rrIf.>(lr3.‘i wl1m‘(* film mzter
`r.:od<* is a <g~f<:2Id 1'r.apz~:f.i(.ic)1; <:'u(l<.~' sum’ the inner wcle is,» a r2'1tL.* 1 <.'<>I2mIL1ti()n:.2I code uxith
`£mz:.~‘F<*r’
`fz1I.=<'rimI l/{l ~i~ D}. W?‘ Z,wl§r.w'(‘ this 1‘rrpi‘r:w;‘I1r.~a
`t.l2<“> first r1gorm1.~i
`;2z‘m‘>f of a
`mdmg tl1<*<,7rmr1 fin‘ mrbo-like‘ mrIc?.<',
`
`1. Introduction.
`
`lxas
`'l"l‘zit_'mmjsl1ima
`(:m'l(*:-5 by I3m‘mu. Cilzwimzx. zmzl
`tAm‘l.z<,;
`The 1993 «;lis<.:<,wL-x'_y v:1»f
`x'm=<>lt,xti<>Ia‘z7.v<l Llur
`fivlnl nf m'1'm‘-<:(>rr<e<1rixlg c<)clv.sy
`In hr'xe~.l".
`turbo <':<')<"los
`llm-'0 mxmlgh
`X‘:;1Il4.lr,>t3\I'kt>,>'_\I an ac-lxiew I‘E*l§9.l)l6* <‘mmn\,1z‘1i<":stion at c;l:_«xl.z1 I‘Zi«’.¢:‘.‘>'
`I1€:3éiI'
`a:ap:;xc.“n.y. yet v3x1<mgl1
`STl'i1\‘t$11X'e‘:‘ I10 zxllmv p1‘m>ti<:2»Ll sm.<r<,)clix1g and clmioclizxg al}:,<>rit:l1ms. Tlxis pz,\por is an zu,tcmpt
`In illmzxirmte? llw fir.~:.* of tlwsv two z~U.tri‘:>u{e.::s. l.f'.. tlw “n«:‘2x.r Slmnn<m limit“ <*:.1;.>;.‘.l,>iliti{::s
`of H1E’l)¢»—lll{(T ("ml(‘..'-»' ma flu? .»\‘»—V'(f_J:\' rrl12mm*.l.
`
`.
`
`llw<,n‘<_',II1:~‘ fur 2: <rl:15&~: of gs—>.1zr,—rz'2l.li'/»':r<.l wh-
`is in pram: .~\'»\'(,,2.‘~i <'u<lling,
`(_}!U’ .~‘;>v<‘.il"i<~ g<>2_'.l
`:.,‘;_:\*.r'szx;~.wal r.tx;;z1mlul.imml
`(:{)t'liIR‘;'§ i3§":$l.£.'Il1§ with i11§2:'1’l<_e::n'§el":u wlxiclx u—'<> call
`"tt1:’l>u>»»like"
`
`m<:lc:>;~';. This 4212155
`‘mr‘,l1,u:l
`both {)Zll‘2'1lI€‘fl
`(.‘0{1(’z1‘{€T’Il21t<‘Cl mlmulmémml
`4'_‘t.n”l€‘S
`l?.*l21.'x*r,~.Ical
`
` *
`mrl:n:‘> <?«‘><:l«;‘e?l
`"
`l as S[')f!(‘,l?Ll C.2xsrs:~‘.
`e'm«‘,l $€‘l’lE'1l
`c<:mcm,c1mt.r~cl
`(‘Cm\-’<“)l1lll<"!l'1:-Ll Cmlc.
`_
`'2.
`
`
`a.rxr'l
`int:o,r—
`zx ¢;mu‘ic s3x'I,34,,'t1.1n- of ilxits i:.g,»';_>o_. with fi:<e:<_l c:r_>r11pm1m1£ (‘Ur
`ll
`l,’mgiz:rxing_, mt.
`‘t«;,>;)<>l<‘w'\'. WE" ».tTvx'npf
`tn :.<l‘s<'_'7\&’ that as r,l14_~°.
`li>lm‘l< lerrzgjlx 2,:;2p1‘«.>2z,<:l1<rs ixlllrxity,
`kiln‘-E1tf(‘l'l<T>l'l
`
`flu: m":s<?z12l)l<2 §<.>V<.
`all p<,‘»>:sil:>l<é ir1ter1<?7w<rr'5) mzL.\'im2.nn lllurlilxuml m‘mz‘ prc>l1;xl>i.lity exp»
`
`prn.:~U~l;-as 7,m~u if 53,,
`?x<~<w:l:s sonw r,ln':-:alml<l. Ozxr pmof r_.¢;',<‘lmi(_111C 15 km <,ls.~.;’iw em
`::‘.\:pliz*if.
`i‘I\'[')I'(“SSl<f)!l for f.l1(*£7z1s<‘ml‘>l1": .inpuf,~<’>utput xw-viglxt, mxz1ix1<~>mt<wr {'IO\‘v' Y1.) zmcl fiver:
`M USE‘ this ¢'x}.>rl'xx$i<‘>rx.
`in <‘<>xnl‘riuz1l,i(_m with e:it'hm' flu‘ <"la.<.siml urmm l><mn(l. or the
`. to show tlm. Slur xxmxlznum
`
`z‘<*<‘s'~.x11.
`“':1r1g‘>:'¢_>w.x'l“ Imlrm hmxml nf\/'m*1'h§ zmcl Virswlai
`[,7nformxxamzly the <l‘n‘fi-
`ix;
`lglgciimmli wrgml <:z‘1'<:r pz'l3l)é1l)illt.)= ;Lppx‘c>eLr.‘l1r.~.~: zen» an N
`z-u|r.§,= nf ’t.iu.:~ first
`.~_,:t«.>;,>.
`i.s;-..
`the: <'c.>rnputa,tlrm of tllo ms:t;2rx1bl€:
`IOWPI, lms keg): us {rams
`full $>1<:m.~:;x.
`:*.\:I.i'<-
`pt‘ far s<m':«:
`\’£?I’}‘
`:'~‘iI'nplI.‘1 «f:<><‘liz1g ~‘V'$.f.i‘!21s. wlnvlx xw call 'z‘.»':;.v2mf and mi-
`r_’1¢rmLirLt€:: <:ml<>s. Still. we %U‘(’ mprirzxlstirfi tlmr, Lhlss HT(_7l1Xllql1¢.? will _'5/lé',_l(l mzling ¥.h£*or<*n1s
`11>: 2: .uiu<:l: wi<,,lm* kil2l.‘5f~% of iz1t.erlt>2we3:l mm::1l:<1r1aL.<-ml
`(:<wrl¢.=.s.
`In azxy <7a:~;%.!. it is sm,.i:.<f_\.’ix1g to
`llama ri;;c:)1'm1sl}; pzwvarxl c:o<‘lizl;;; tlu.-uwxus fur azvexx ti x'4.>stm:L2.>d clams of lllflI>(‘)-llkt: (zuclcs.
`
`
`l‘ler+;*
`an r,,»utl'me.> of the ;):.»1p(.>r.
`In Sé:<':t.l(:»zx '2 we quiai
`V, rcvimv the (713 .5i<:2;s.l union
`l':»mxn«”l on maximalm~likr:lil1«:)o<'l W<T>I‘(l crmr p1'ol>ab'1lit_y for l;>lm'-k ('C)I'l€‘.3 on the :\VV’Cl?\'
`7?‘
`
`:\vlc"l:“,li<r<'<~:’s wmk. w;\:.~‘ ps::*1‘f<')1'xxx(—7(l
`l)ariusl\ Uzvs, iar'>‘. worlq. and :1 [)(3l‘l,l(.lH (if Rol_><>.rt
`
`
`at JPI. uzlcim c:ont1':»u-i v.‘i'._,l1 ;
`.\SA The: rrsmzxinclegzr of M
`w<'<¢'s \‘.‘(‘1I‘l~(, and Hill J'm":1
`wurk.
`\‘,’2,‘i£~’
`p<..*.r'f<_»x't1'w<l at. C32tlt.e:r:lx zmcl 3\zpp(>x’t;c:<l hy NSF’ grzxxaf.
`rm. NCIR-S)5()5€)75.
`.~‘xFOS,R glam nu. 5F:ilE.lf}2()~97-l--U313.
`:«m<.l grant from Quztl<:(.>mrn.
`
`20 l
`
`
`
`3 we
`In S€:?(Zl2iC)n
`channel, which is seen to clepencl on the (:ode"'s weight eriurrierzitor.
`define the class of “turbo-like” cnclcx. nncl give zx f<arrnula for the average input;~<:mt,put
`weight enurnerator for such a code. In Sectixian 4 we state a (tonjecture (the intei‘l¢.~2wer‘
`gain exponent conjmttiirc) about the ML decoder performzince of turbo-like codes.
`ln
`Section 5, we defiiie a special Class of turbo-lilccz cocles, the rep:::at.~:'ui<l~accrumnlate ccxles.
`and prove the ICE Cc>rijeCl;ure for them. Fnally, in Section 6 we present p€1‘i()1'I1l'dI1(‘(~?
`curves for sorne RA cocles, using an iterative,
`t1,l1‘l)(>«lli\'€,
`clvcorliiig algorithm. This
`performance is seen to be renizirlcably good. clospite the simplicity of Elli-3 cmltzs and the
`sul)0pt;irnality of the (lecoding zilgurithxri.
`
`2. Union Bounds on the Performance of Block Codes.
`
`In this section we will review £119 rrlzissical union bonml on the 1Il2L‘(i1'IluIi1-ili((}lili()0Cl
`worcl error probability for bl()('.k codes.
`Consider 23. biriary linear (rr kl block code C with code rate 7' = I:/72.. The (butpulj
`weight en.-umemtair (WE) for C-' is the sequence of numbers 214),.
`.
`.
`, A”. where .~'l;‘ dc}.
`notes the number Of Cocgleworcls in C with (output) weight h. The mput-outpw. 'wez'gh£
`r:n.m'n,eratm' (lC)WE) for C is the array of numbers .»~’iw,2., 2.0 :: 0, 1. .
`.
`.
`, k, /2 2 O, 1,. .
`. .gn:
`.»l,,_.,h (.lCIl()l.£i3S the n11ITllf)(_‘.X‘ of <tm'l¢_-worth; in C with input weight 21; and output weight. /i.
`The union bound on the wcml error pr<.)l>abllil,y PW of Cliff cgncle C‘ over 21 tl1eXI1()l'}’l(?25S
`binar3/«input channel, using masdmum likelihood <ile.<toding, has the wcll~l<n0wn farm
`H
`
`,
`
`.
`(2 2;
`
`-»
`, Z r
`PW "3
`.*i),£.'
`h=x
`n
`k
`
`z
`
`13
`
`I
`
`Ii:
`
`“
`uxrzl
`
`l‘[‘ A
`
`..
`
`h
`
`[,)2Lii"w'lSl.! crmrWk?
`the fiin(7t,i<>n 2" l’(2f)l'CS€2Il[S an l.lpp€;‘l” bound on l1i'i(;‘f
`in (2.1) and (2.2),
`probability for two C0(i(:?WOl‘dS sepai'atecl ivy Harmning; (output) Lli:st.2nic:<;: Ii. Fur AW(.m
`channels‘ 3 : .»;“”’'‘*~’''“''‘> where Eg,/N0 is tlie sig_,nal—m-n-'.)i5€~ ratio per bit.
`
`3. The Class of “Turbo-Like” Codes.
`
`In this sec:‘t.i<)n, we (I(,IU25l(flE:I’ 21 goricml (‘.l£l5S (‘if <;ori(:2il.r;2ri2it.<::rl mrlirig Sy$l(,‘Il1S of the l,}’p(‘.
`depictecl
`in Figiuxa l, with q (?!1(.‘.()(l€3FS
`(<:ircles) Ztllli q — I
`iriterlcavers (l:>m;z>s). The
`ith code C;
`is an (In, N.) lir\.(‘,m‘
`i>lo(:l< (rode. and the ith encoder is preceded by an
`iriterleaver (p€:rnii,1t.m’) P; of Si’l.€t
`;\fi, <7:~:('ept C7; whicih
`not pre<:e<:led by an iritearlsrztwr,
`but rather is COI1I]C‘(.?C€2Cl
`to time: input. The 0VCI°2lll structure: must lmve no loops. i.e.. it
`i'I1\l:~,'i. be 21 grapht,licort:rl;ic: trcrz. V\'o. call It
`(:0<'l+:~2 (if this type 51 “Liir‘l)<.+lil<n" Cr)('l€;E.
`[)<:l‘irm .51, 5’ {l.2, .
`.
`. .q} '<UX(i5l.li)$€El»S of 5,, by 5, 2 {i 6 sq : CI‘; comwcttcrl to input},
`.90 2 {i 6 Sq : C, ctorinecrterl to output‘. }, and its c<)riiple1nerit.S‘¢j;, The <wcr'all ..s'yst.mri
`....4:E_v(_-,i
`~
`clepiczted in Figure 1
`is then an eii<:<:>(ler for arr {n, N) block i;:s>dr.: with H r: '5‘
`n..
`If we know the IOWEI :‘i::,_)_,h‘s for the CCJIiSCil;Ll{2I1[ mclcs C’, we can calculate
`the average IOWE /iw_f; for the overall systmn (aivzzraged oven‘ the set. of all pnssiiyle
`int.erlea\=ers), using the uniform in.t.erlecwer techniqiie
`(A uniform iI1C€Il£i‘.7J.‘»’(3I‘
`is
`dezfirisxi
`probabilistic clevicrc-2 t.har, maps a giveri
`input. word of weight.
`‘U1
`into all
`distinct (‘:2’) pnririiil.at.imis of it with eqiizil pmbzlliility p -:=
`The result is
`
`<3»)
`
`,
`*5
`.2 2.
`>\,v&9(;)h‘,{5T1'0
`E'.h‘s::h
`
`4
`
`1”
`
`1:22
`
`(am)
`
`202
`
`
`
`In (3.1) we liave w,- = in if i 6 5;, and w, =: h] if C; is preceeclecl by C} (see Figure 2.).
`We Clo not give 2). proof of fomiula (3.1). but it is intuitively plausible if we note: that
`‘)
`the term
`is tlie pr0ba,bilit_v that. a random input worcl to C; of weight my
`will pmcluce an output worcl of weight h.,.
`For exaiiiple. fm‘ the (n; 4-n3 +714, N) oricroclcr Of Figure 1 the formiila (3.1) l')ecoxm~3s
`
`“
`. U,’ 11
`
`W
`~—
`
`“
`(I12 ,~n3+A,,—.,n;
`
`. ('2)
`(3)
`, (4)
`Ar.vg.:t_1 '4w3.h3 “ w.;.h¢
`AU)
`. an ‘hi ~—--N2~
`r~——~—«myV1M.
`(mg)
`(;,i,)
`(mg)
`=13:
`(3)
`’4l
`~___ 2 A(1)h Ami, :‘1.n._h,, ‘4l1;,h4
`‘
`(N)
`(22)
`71;)
`A; iA3,h3,h,;
`.w
`(Ii,
`(ri2,ih3 9-rum»;
`
`
`
`P2
`.
`
`W2
`
`N2
`
`C2
`
`h2
`
`n2
`
`> outzpixi
`
`Figure 1. A “t.Lirb<>—lil<<2" code with
`.5] 2 {l.2}..$'()
`I;
`{2.3.~'-1}.§(_)
`
`
`
`<ne.—Ni>
`
`<*“~3~N:‘-‘
`
`(,7, (an (fl./. :\/'1) encodtsl‘) is coiinected ti; C’,
`Figure 2.
`(an (72), ;'\"j,i cIi«::ml<2i‘) by an ii‘ite:i‘le;.iw.>,r ml" size ;'\/'1, We
`liave the "bi>mi(lzi.i'_y i:oi‘i<:lit.i.r,ms” .-‘'V}
`r: n, and IUJ 2 ii,
`
`4. The Interleaving Gain Exponent Conjecture.
`in which
`In this section we will consider systciiis of the form <l<epicLed in Figure l,
`aim mcliviclual <-.iic<':>r:im‘s are l.1‘1.lYI(‘.Z‘xl1(;‘:Cl coiwolutional encoders, and study the behavior
`of the ewmage ML decoder error pr<>h21l)ilit,_v as t.l'ic_—z input block lmigtli N zipprczaclies
`
`203
`
`
`
`
`
`’/?'A7‘?‘Nf¢"'!&v\>I.*A’Vr/»»\1¢'/KvrL('I>/N’/\)g~fl/'
`
`
`
`infinity. If /i;::'Vh <.1«:_m<>‘t<-5 the [()\.VE- wlwn the: input blcmk has 1::-,x1g,t,h N, we ixitmducrc
`the f<)ii0‘WiI'1g x1o‘t,2xt.i<m for the union bound (2.2) for S_‘/St€I'l1S of this type:
`:2
`
`\
`-V‘
`(4.1;
`
`I'[3,i:;_f
`
`Pf‘? <— 2hr‘:
`
`Next we Lit‘.‘fi[l€.
`
`for <.>..:zc'h fi:<c(l an 5‘;
`
`1 zmd I1 .3 1.
`
`Bo V
`
`.\.
`‘ _
`)5?‘
`n(u-, /1,) = iiII1S\l{)i()g,_.\.- .4ij:‘_i,3.
`
`It
`
`f0Hows& fmm this <:i<:fir1it_i(.>ri that if u: 21ml
`
`/1. are fixed.
`
`Mix
`‘.,‘.\-
`‘ u,.w,)x"
`
`:7 ()(";\_-xflizzr .‘1')+~z)
`,
`
`35 N, "“
`
`fur 21:1)‘
`
`:
`
`:> 0. Thus if \\‘t‘ r1r~fin(>
`
`{<13}
`
`:33;
`
`:: max znzuq m’ er. 21).
`A231 us};
`
`it foiimvss that far all u’ and )2.
`
` i 1:“ 2. (‘})(s\’”** 3“)
`
`as .\’ -~
`
`fix,“ xx-'hic'i1 we-> 5112111 mii f,.h¢i* mi6r!{>(u."mg 3/m.7z z?‘:tp07z,<~r'rzi
`[.>éH‘«’HIi€‘T£‘I‘
`for :—my F iv 0. Tim.
`:3} fwr pwzxlitéi «;tun::::sxtesnatiwii and Iziter in
`fur
`{ICl1§): w21.»:. first iI‘1fX‘U(fi!.i€‘(f."\i
`‘an
`
`
`
`serial <:r>xiCaten:xt.i0n.
`I5. Y~€_:x1.,~:i'»—’e mime. . 111 sirx’1niz'1r,i<;nis. and Y..i1C,‘(')I't"’fiCZii <‘<f>I‘1si<:ic=mtim1s
`r..hz,it are nuz fuliy r‘ig<')z'<.>u:~:
`iczxd to 1.31:,’ follnwitig ('CiXlj€’('I.i1§’{?
`a1I><.>m. the be>h2sn.‘ir>x' nf mes.
`un'z<.m bo1_u'1«;i for syuttexxxs of the t.jy‘;)e siwxm in F.7i;;ux'r3 1.
`
`(1<i'_r)c3I1cf;= on rim r;
`sx.'}.~;‘r-ix
`"1“h<*-rrr exists 2: [)L)Siti‘.'(‘ mum’):-r 1,9,
`The IGE Conjecture.
`
`
`('<'>r1r*s am] (120 .’."(‘€'? St!'(I('f{2I'(‘ of Kim r>wm.!1 .5;
`en), but 1101.
`z.:mnp(>1'1("12t <;‘r)In'<)Iz2{.i<)r1:i!
`in 2» "f0.&iS the b1z;2r_:k 1e.'I2;,rr..2s
`;\"'
`fwrgorriczs 1zi1'_{;c:-.
`on
`such tliaxft far 3113;‘
`fix«;.=c! En/.
`
`(44:
`
`Iyfi/£5 L; (N-fl\;r2'i,\/I)
`
`
`‘> 70 the urmiri.’ e?rx'm' 513mb-
`‘v}-,
`<3.‘ 0, tizmi for A givem /‘T
`Eq. {-*—3.4'} implies i,lxzu. if n'_\.,
`airilitv of the:-, c<_>z1c2*mrx‘mIed c:<><‘i9 <ic:<_'c'::;u‘w.~’: m ze-~n> as the input birwk 337:: is i:zc'x'(2asm‘i.
`
`This
`_ stxmniari’/,€e<'1 by sayixig that I1h(~‘.I‘(? is zun7'(X P7“/m"1)I‘()b(1?)':l2£y :‘I:ta7‘lm:.'z:2'Tz_r; gzmz.‘
`the a:al<.:t1l>xt.i<:_>rz of u(u', M amcl £7}; for 21 c(>11::2:1te112:m:d
`In
`we dist,
`the typv <i<*.pic-.t.o<:i
`in Figure 1, using; 2'ziml_yt'i<~a} r.;u~,3,~,
`im’r<“)(]m‘(--(I an
`e32x:1.x'xiple. for Lhv [)éi.I’fl,H("i ccm<'atm1zui<m uf :1 (mks, with q M»
`1
`iH[€‘}‘i.P'.‘<).‘.’i'_
`u
`;T3~,v
`
`[31 am;
`
`, we hz’-we
`
`~_g mt} + 2.
`
`
`I'é?('1lX‘;<i‘»’(’t. Fm‘ 21 “ 'i'~,z:~Lsi<tal"
`«'1-‘{ the} <:uIup\,>m:xif (‘f_)(i(’.S
`with e*<.‘;‘x:2~1li.lj_y' if mid Uni}; if (f«'_3.(?il
`;'‘f,«,;
`:2" 0. so thr:rr~ is no word (‘I“I'(1)I‘ probability ixi‘£e:1‘~
`t.m‘bo (7c’>d«> with q :2 ‘2. we hzu-'4:
`Imvirig gain. This .<1.2;:,’;:<’*;~r€.s rim: the? ward f_‘I"r(>I' ;>ro?>;\hiiity for <tI2:s'si<*. turbo (T<’>L'i<.‘.‘\‘ will
`not ixxipmw: w';'t,h input blewk aim. whicrh is in iL§{,I'C£?1I|€?l1i with 5iiH\.li€_Li'.i()I1'i.
`
`3 Tiliém is R. siixiiim" <'<mj<3(:t.iir:2 far 1' he: bit error pr<)b2ibili{._‘v' which we do not (ii:~2(‘.\lS.‘-S in
`this paper. Suffice it to many that the im.::r‘xe:5xvii1g gain expomzni fair bit error DI‘(l.>b21biiit}‘
`(i M - i.
`
`20-'1
`
`
`
`As aumtherx‘ <:x;1xupI<:. <r<»n.~ti<lvr
`
`If the mum‘ cu<.1:;-
`n~.>4.:m.'.. w then.
`
`t.h<—r 5(,’I’i£,l1 <:<..>xx<_'zn,c!:atimam (:5 (wt; <~c_.>xm)iuti<)naI c.:(.>:le,,».~:.
`
`Ix
`
`
`
`
`‘zuu-v nf tin‘? (HEf€.‘I‘
`is Vtw miuinuxm (E?
`c_(,‘,.\
`‘.\‘h€‘L‘t’
`zxaitcd r;r.>«..ie>s. if «ii! 52 .3 th<*:‘:\ is z1‘.:*:<.*L‘ica\'i:1g gain but wc:»rd £:r'x'0v.' p1'<)bzLbilitj;. {If the inrxer
`<'<>Li<~=
`11<.>x‘x1‘w::1;'xi\'e‘ M,
`5? (T7 and there is no i:1tv:'1<>z_n'1;xg gaéta.)
`
`<.:n<'1c‘. Thv:‘vf}::x'<.':
`
`1%!‘ stxrizti <'<’>xutm.,c'»
`
`A Class of Simple Turb0—Like Codes.
`
`in this smttiuzx *.\-'9 wiil nm'mi=,z<'s;: 21 (‘Ems of mz'bt>-like <:c,.>d<’.~: whicl: are Silllblt” m<:>u;’?;h
`.s‘r;2
`tizzzt we um pz'<,,:v<* thv {GE <:v:mj<—r<:turz°. We call t.hc?:~'e mgvciess
`rzepctut and »;z«.:c;urrz.ulatr~:
`{R.~\} (mic:-5.
`'l."l1£:~ g<*1'u.‘:r.»1l
`iaica is .‘\’}'m\\.‘X1 in Fig»_;ur::
`15, An §nfs_mx1ati«>:1 Mock <31" lesngth
`.\’ §.~'
`:‘<7_r,><*.:\tr:-cf q tizncs.
`sr‘razui:»}£~<_§ by an iz:r<;\r!m\\~e‘r of size q.«'\’, and than e=>z1«:o<§e:><‘I by
`a ':2x¥;c
`1
`a.rz-:u"rrmla.£c'»r. The a.<~mztz'u1l;m>z‘ mm he vimved as n t,m1n<721t.e7<l mm»! r<:<-uz‘siw._,>
`
`:.'<>m‘«.71:mx,>x1;11 t3?;'l(.‘(’)(i(."I warh tmx:sf::x' ft1z2<tt.i0n 1/(‘L 4,» D}. but we: p?:<*f<‘3x' tn think mf it
`a ?:>l<_><:k C<)~:}e wh<.>.~5(i- inpm M<,'><:k
`,
`..L',1§ and m.:z_out biock {gm ;
`.
`.
`.
`.;;,,_j
`rc.:1;m'—(i
`'!:s_x' {he f<)rn11:la
`
`I/2
`
`J‘;
`
`1/»_» == I; + £2
`
`
`
`
`
`"s,7;_>t*a" aim} v.,<'<:1xz1u,:l;m,=
`?:l:1<,‘<,u!M‘ for .2. {::1;\'. ;\ ';
`P'igur(-1*, 3.
`izzgmt.-t:)u4:;>ua‘. Btu»:
`’I‘E;r;- x1uxnE':tr:‘s ;:ab«:2w ‘r.'m-
`<;0d<*.
`im1i<:‘>_1?,e‘ Hat’ §<‘x1§z,H: «>5 rhv <"<)z':‘<‘.s‘g,2c>::r_img ?>1r,><,"K, zaxxzi
`th<>;~:<» E>e__*§<m'
`the» xinrxs ix:<l':rz,u<—> \‘.'m—* xvvight of the b‘.r.>c.?k,
`
`tin" mximz bmmd from S<:<‘ti<m '2 to the <:la.\:s of RA (:()(l£3s. we nzxtcl the
`To A;‘>p}j,-'
`in;.>~zr--«>1:t{‘n,zt we-isght <‘mam<=1‘:;1tr.xrs for hrnth the '1’!/r:,.n‘} :'<>pL-tkrimz mr,1<=. mu} tixv (217).)
`
`{1i‘(‘i.1Il1{11i'L7()I’ <:m.iL:. The uH!(‘{‘ rvpct§tioz1 mdc Es rrivialr if 511:: mp: 7..
`'r..»lw.:k has Ecxzgth re,
`xwr Exzvwe
`
`
`
`4{£,_~,
`
`‘
`
`:,f qw
`11,
`if A : qw.
`
`I 0
`1(3)
`205
`
`
`
`
`
`The inner aczcmnulator code is
`the input block has lc:ngt.h 11);
`
`trivial, but it is possible to show that (again assi.xii1§rig
`
`_ ,
`
`M
`
`_ U)
`
`'
`
`12 «~ h.
`
`I‘:
`
`-~» 1
`
`1
`
`'
`
`It follows then from the generzxl formula (3.1). that for the {q;V, N) RA code: 1‘e:p1'es<::r‘ired
`by Figure 3. the enaseiiibk: {OWE is
`
`4}
`
`€:‘.*
`_L1m‘f:—_~_
`
`A
`
`41 :)
`‘
`/’
`
`.1
`
`.3: N 4((';‘y
`" ufs
`§
`hi;-:{)
`
`qu:
`
`q:'V‘
`(mu)
`
`it is craze);
`From
`The rcrsult. is
`
`ta» ('m1'ipuf.<' the ;'>zii‘z1xiiot(rx‘$ a_1{'zLr,l2,) am‘! ,;'3‘,\_;
`
`in (412) mid {:1..’S}.
`
`_. ")
`
`e
`
`(‘
`
`‘
`
`'3'‘:
`
` F
`
`rv(w. h) 2: —~
`an ‘" *
`
`{5 3)
`(5 6}
`
`It f0H0w.s' f‘m1n (:3.0) that an R:\ ctocie vzm hEW'f_;‘ worn"! ernwir ;i>r<:>habiIif,_y iI1T(:“l'i€?3\‘iIIg sgaéia
`oniy if q >_‘ 3.
`\V«_* are? now pr:-"p21r(ecl to use the zmiim bounri tn pI‘0Vf§ H19 IC3F r<)i:jmttI.1z'n for R.:\
`<“c‘)dP.s'.
`in m‘<ls=.r m sizxmIif_y the expcisitinii as much as p<‘2ssii»I<'~., we will _zi5.s'izrii<~ fur the
`z*<~rsr, of this se<:t_imi that q
`41, the (:,~ct.<2nsimi 1.0 arbitr'ary q
`3 i)e3i:'ig straigi1tii.>rwa.i"cI
`but rather l<:ugf.hy.
`Fm‘ Q
`~l.
`(S.6‘)
`b€~Y(.?(§In(!S
`{SM rr -1. so aim [GEL <tmr1jc=<:t1,1m
`11$,“ 2 (’")(N“‘} for 113,’,/:\»’0 1> 1/0 in this instamxz-.
`Tile union bmxiid (2.2) for the cixsseiiible of q
`
`:1 RA <:<..;(ies is. be<'z.uz5e of f,_I'>.=1}.
`
`«L-N‘
`1:/Y2
`IOUB W. Z §“"‘
`
`112V «Ir ‘ix--E‘
`(w!"{ 211-
`)(j.22u~- 1} ‘A’
`
`De11<‘>('s: 1.1112 (11: lama hrmz in the ;‘5U1'!1 {:17} by T,\:(u:. fz):
`
` T:\'{€,1.¥.
`
`.r‘i;,,Vh Zh ::
`
`Using sta.n<i2Lrd t,e<'}1r1iqi4w:»' («Lg
`(at. h}.
`
`E8, A;,ip<>nr:ii,\'
`
`ii,
`
`is ;;>()s.s4ii)l<‘ to siiow that for all
`
`(5. O1:
`
`V)
`
`"1:~:(~u:. n; < 1;>2"%"’"<*~fl"‘*%2
`
`wiitma D :: <1 V517 is 3 (1(){1.N‘(E,lI1f..
`
`:1: xr; u,,'_,-’»'-L‘\*'. y = ii./=i;"V'.
`
`1'"(:r.'y) 2
`
`—;-’H»m:r> + (1; y>H2<%§) + zgI12f;)
`H
`
`,
`
`206
`
`
`
`is the binary cntrc>py functicm. Thet-
`(l ~ :1:/1 log.3(l ~ 1:)
`~—.1:l(>g.2{,_.*‘_l
`:2:
`and Hg(.rl
`2.1: 3 3/ 3 ,1
`~
`'21:
`r>(_‘<'ur>: at: (gay) :2:
`m2x:\'inmm of the fuz1cri<'>n F{:1._z/) in the range 0
`((H0(l.(’l.3T1) zmcl is
`so that if log.) : < ~——O.5fi2'2Sl)
`t.lw mcpmmrxt. in (5.8) will
`be xwg’2tl.ive.>.
`is eqtxivnlem to E
`<1 «~(.').:”.v(.i" ‘€81. wlxicb.
`Let us tl1ewl'0x'c ns;<umn that logy,
`
`
`<1
`~ in? » 0..3()22Sl 2 1.r'>:">9 ==
`l.9‘2S <lB.
`If H is clcefincl
`' -,.l. it follows from (5.8) for all w and /1,
`
`lV
`
`——.
`t.<::» be
`
`(5.29;
`
`'1‘,,»(u:, n; g.
`
`;:)-;>*’*”.
`
`What (5.9) tells us is that if E», "‘/0 :> l.9‘2«§ (113. most of flu? terms in the union l>m,1m'l
`(-3,?) will te.,~n<__l {.0 zem rapi<.ll}y‘. as N M
`Tlw n<_:.\t amp in rlw proof is to brmk (luv
`Sum in (5.7) im.r:> twv» parts. nt0x'1‘<~:~;;‘>«)n:lm5_{ to t.lm.~;(~r
`lm'm:~: fur wvlmrlx (5.9) is lwlpful.
`and l'.ll()M','f for wlxiclx it
`is not. Tn sllis assnl. dof‘im-
`
`5 E
`
`
`
`; 10%:
`
`Ijmzs./2;
`
`J:"<'
`
`}xg"'l
`
`\
`.
`,
`,
`,-
`»
`74\,'1!_1-’. fa) -r 2 § Txgzz: /7;
`- ‘
`
`and write
`
`Pg“
`
`.2 A‘ A
`
`2
`'2 1:”: l
`2: 1‘
`71/ 3
`}>.,~;
`W‘ W‘
`
`hr 2 :4"?!
`
`rs
`
`57 «S;
`
`"7" 53.
`
`
`jg fly mail
`<1‘ 1 for 2:
`.&}’i‘/‘Y’A"i[¢,'}]
`l2»11‘ge:* em.’=u§.;l1. Al” —
`i.Z*1.es‘r, wluen .\"
`Its *;?8.*~'}’ m w';*1‘if}~'
`is :1 <.'l(~<t1‘s::225'uxg f:_Ln«;:£.'zurx of u- fm lar'§._;e=. N. Tlxus
`it’ 5 /2f'2
`/73;,/”‘Z. wlzich slmws .4, 3;
`flu’: xurn 5'1 (‘am lw (V)\‘€‘,l‘l')Ul!I]<l(‘.(l as l}>ll<;~w;s‘ {we mmif.
`.\‘mx‘w <l(“t‘z'1il:§}:
`
`ll
`
`.5’;
`
`)3 A.’*~«
`
`2;:
`
`
`—’i.\;
`
`‘)7 fir { 11.‘, h
`
`/25.
`
`’‘/V3
`
`2: Z T},-'1: l . /2') ~l~- Z:
`F; ;.'2
`h 1 2 Ir .4?
`)1 N 9:. /I '.I
`
`T,v(zr." in}
`
`o;;\=' *; Z Z 7',y{u'. 2:;
`I‘.
`‘L7 u-,:/.2
`,1.
`I: / '3
`
`g ()s;;\* 3. Z Z
`
`Z07
`
`
`
`
`
`For H34." sum 52.
`
`\‘.'r- bmurwl 5‘-M}: tnrm //",\=(z.».-, h‘)
`
`l‘:}»'
`
`€5.93?
`
`
`
` y
`
`()1; .\’
`
`”
`
`\\'é,> h2t\‘f.,’
`3.92.‘: :18.
`
`45> H}:
`
`Ihs:’:'<‘f<‘»x'6* sh<m'n {'!x.'x,t
`
`!'e>r Hw <*1w*;ni:-iv <,Ǥ' 1]
`
`—1 RA c-:><i<‘.\‘.
`
`
`
`v1.'E.“.
`‘H
`
`«;)s,\' H
`
`.»:,\* ‘>
`
`(LHj.\‘
`
`T}
`
`'
`
`IGI‘:(’n11_j:‘(‘iH1‘<* in iixisi «';15v;.
`ix U1!‘
`21>: we ,-A'-.\.' nimxw-,
`
`N
`1’
`1 "her lminn ?>«:n.ua<i xix .
`21
`!‘>Y'‘3’">f 8"?
`{ 3*!‘ “:5 ‘5’””’l.iswt\xx's"- {or R.\ <wl«>.<. thr
`
`
`
`s'<*:~:n"l:':z‘1;; Vexizw {J in is U3‘ rm m<’;:,n.~. nlxn beast
`;>:;,~j,.<il:l¢'r.
`Iw.!w*<§.
`ii’ xw n.x'e> Yin,“
`§'L?(,‘,t‘S'£i
`iw 1’:z1!u'2
`ti’:-~ mu: .,‘.?;>.
`‘M.’ (um 1<>\‘.'£'I‘
` rm ’ms.:mx1<‘i
`V}?t,'I",z§~\"iH’:‘M i:x:;>:*<=«:wi zminn ‘tjnuznri
`.
`.2 I
`‘$3 to {}..'SE.'_’» AB. In ii-;:_uz'z’~-1 ax1:1"l‘z>.§)!<,e I WU
`Hf ‘I4; 2.'nm§:'im‘z11‘>ij;.
`4?
`m: z;
`-§ Ehzxlx 1.9.-.
`<.‘<.:e:.{«:'.\,A
`‘1 h€‘Z’tIf
`'w<~ r::,>n'1;,>;::'I.,> the’ "<'v,1(r>§F t.§::‘I'>,‘h<2l«i"
`« z‘+:.~ui!;~‘ um I\‘.-\
`13. M; R.-\ <‘«’>c"u:~; Wit 3
`I]
`in {Ear
`1‘.=m).;'<J'
`I’:
`jg;
`:1
`‘_’{
`3'4
`11.«t'm}.g hut}: Has:
`t'§;:.~;~:i4.'.-:3 zmiuzs iwmnmi
`and siw \‘it<>M’Ji--\"1t¢~1'3»§ 'u1:;'>x'm:z~<'é mzinn hmxxui nu (hp Hztmfi‘ {'::I‘s\.~:’;:«'»L:‘1 fur zizrn m:~:r.*:x';}‘>'{£‘
`
`.‘
`'
`1
`i
`(,,'mh*_\' «fix-,.
`"m§;r§u:x1 :’url*‘“'"3 uf ax
`iixm rain).
`\\'z; bx-}'1«:\’»" -hut
`?,hx>s:o \.2}.[¥_lij'> <',-if
`1)
`rm: kw mrhm~r.i sztéli fnmht-r.
`fur «‘-:\‘:':z‘nMr~ bfi
`\z:<'m:.’?,
`he» hr-»:.xr2<‘. H3.
`insr<~21-‘E of Mn"
`‘fit«=;'§,:i~‘»'ite~1'i_>i
`l><mn=:?..
`
`
`
` R;\ (.y':)(i{‘.x
`RJLT1<§n{z1 (_‘z)t.'§(“£\' 1,'T‘.§.x_‘»I'1 P>«"»I!I1t3a‘
`
`RA Until,-1» If\'§fe‘z'M I3=u.xz1ri)
`I{a.;'x:.ium (.'u<i«2;~: Wm-ms I'§:>21z~.<‘.,
`I
`Sinzwvf5?x;1n:1cm Liam:
`
`
`
`
`
`6. P<:x‘foI‘x11;1x)(':<.2 of RA Codes with It.eI‘at;i\’e D<w(::<t)<‘iixw.
`
`FE-‘SE_i§f_.~‘ of t.hi:~,:~
`Thz‘
`fl/C(f!2}le’)f')I'i
`«'z':>.r‘r)(.{’zn_r}
`
`.~'»h«:>\-u
`[.>:.'1;..w<:~:’
`\‘<"1'_‘,‘ g(>m‘i‘
`
`r/U.L:ttrII,m'H-
`('il.J(_ii-‘S mile.
`thew p<~’:z‘f<2I'xst‘rJuum <,:»f R:\
`thtxt
`Hf‘>‘.V(‘\'(‘l‘.
`tho m;'>zx'xp1:‘>ciX,}.' of '.\U, cim'm'§iI1p; 05 R.=~'\
`
`208
`
`
`
`
`
`‘
`
`-
`-
`'~
`
`
`
`~
`
`
`
`Ix,
`
`umon bound random goces
`vvterbi bound random codes
`Shannon limb! binary mput
`umon bound RA codes
`vvterbi bound RA codes
`
`i1
`1
`
`
`
`\
`
`2*
`
`
`
`\
`
`
`
`Code Rate R
`
`
`
`
`
`In
`t.'tm_:.»h<.zl:l
`('«.>zxI;_>ux'i1x;; thr RA m<1v.~ “<.:\1t,<)€f
`Figure 4.
`the <_:1n..:.;ff £211.42 uf x‘<uz<,£t;)zn males usixxg h<'>[’n the classirxai
`2_:ni<>n bmnul .::z1<i Hus '\"iU:.x‘1.>i-\"ire.2rbi
`izz2gu‘c.m;2-s.i union buuml.
`
`gylwhibirixr
`irrzpcsrfzm? fe‘;xtx2r"r'
`Izxrgc-*. Pm: 2--U1
`'
` '
`"
`
` ‘.<2,2s»;r> gm.
`'”in§.{ r'i<'~xi'm:ii1'1g
`uf Im'?'m—li'K:*_ <fa'>:§<x<
`the su';1il21bi1izy of :1 .<.iIn;vi<:
`it»f'x'2:tiw~. rm
`:1 {'f,>lIi[)ll?,é‘I' g»1‘ng.§mxrz in imp1<--
`;;i;:nr‘it}\rz1 mm zL;>;_>r:s.\'iIn¢\tv.s' s\EL r,1m‘r><.IiI\;,;.
`VNE3 W!'¢>U‘
`
`n‘1onf
`this “m:‘h:>-lilw" <ir‘-'.r«><!in§;;
`11,35‘ R.’-\ <'m1<‘:< with I’;
`:2 I5 {;‘z.\I,:" 1]."); and (1 L:
`4}
`{_x‘;1.tzn
`
`\\’e? \'e:%4>
`in Fi 1.,m'
`:2. fur <>x::1:x;.,>§r"~,
`that
`L/<1}. 2-ma! Ihu zwrxitzst aw .<,%w.x‘n in
`
`
`for q 2::
`IS ;~1;:>;'>r2:vu'>,:
`to hr“ ‘(~.‘t_~TE",? {hem 1 <18‘
`tiw <,:m_L>i;‘ical «:u£r‘::fY th;‘e*.\:lui,a!«,i for R.»'»\ cm
`
`
`<.‘<)I‘x1p2‘u‘tf‘s:i to thv xzppffx‘ b<;mm.l L,
`1.112 dB z‘<n.1m1 in fl.[::Nr.,= 1.
`'
`
`R.efcx'ez1ces.
`
`E.
`
`2.
`
`I5.
`
`een'«‘,»z‘~
`limit
`".\’e>2u’ Shzmnur:
`’l'}‘.i!.mxzajxilixnz-1,
`1’.
`E’»m‘x'<‘m. A (f,lI21‘.'im1x. anti
`fuxhrf; <‘*m’i€_‘:~."
`P/:r2c:.
`,If}5i';‘
`/1715/? /r2.y'.¢::m(.I,!.m‘r'1.a£‘
`m>x'I‘r.'~:'[iz1j,;
`(‘wi'2x:{,: emd cl(t«‘<)c§ll1_*;’:
`(:.’r22zf},:r‘,nn.r:{5 rm (,7(.>I:zrmmurzzizmas. Ge‘z1x_3\'z1. 2S‘.x'itzm'l;ux<l {f\.I;x}; Wilffifi. pp.
`1W:i—1—- X070.
`S.
`i3<'x:c=:i(:K?.«.2;1I1t,i Ci.
`;\Iuumx‘>i. “[,’m'0ili1‘1§,g tur%>r,> <'<>dv:~::
`,~'t<.»xn<' x‘<.*sult5 on pzuuflr,-X
`z;r:»m:;xH3x'1:_atrgcl <"4,>:!in;,;; g;(-'n¢;;;rx<".
`/I':.'I".'I'f "['ru.'n..s-, nu Inf.
`’1‘iu=:z.rr_';_/. val. ~12. no. ‘2 {f\l:1x‘<:}z
`
`1:)€I)e~;;,« pp. 402) 42 .
`"D<‘:»ii§,;_12 Hf p:'xz‘2xli:'*l <:'r>:1<t21t.mmtmi v<‘>u\ruI11t’imm1
`3.
`.Rvr1(*<§<‘!?,«: Ami C} ,«'.\Ir.‘>mur>:§.
`c:n{1o.\,;<."
`l}'7;"L'Pf '[‘:'czzz,sa;:1,um; rm. (,I'mmr:z_or‘zu:zz!u.>m7. ml. M. no. .3.
`:}\‘I:—1_x-'
`i9¥_lbE pp. .1391
`{5l.)D.
` Y,3s~:'z«:>det:r:»_ D. Uix’:a:31:12". C5.
`“S<~x‘iexl «mu-at;rn;vui<>11
`:'\Immsrsi. and F. Pmilara.
`(hf i1xt.t:x'h°:1\-‘mi
`('c'>('1v>;: pz§t'f<.::'!.:mI*.zt<3 zxxzzxlysira. <i¢‘r»i<,;I1. Ami
`iI_z>l‘z:'t.i\'<_2 <Iv<:<'><i'2zx§,;." U,'.‘['.7I:7
`
`'I'r'm:.s'. on.
`I"2'£f£'}7".'fi.l1_"'i('/’II. T/‘z<-.».-.n"!i.
`1.’:-.,:»i, ~14. rm 3,5.
`i'.\l:1v !‘;!.‘.3-:'?- PI’
`9U‘§3V-»$)'2f,3
`
`30‘)
`
`