`Uniform Random lnterleavers
`
`Henry Pfister and Paul H. Siegel
`Signal Transmission and Recording (STAR) Lab
`University of California, San Diego
`
`{hpfister, psiege|}@ucsd.edu
`
`0
`
`Apple 1222
`Apple 1222
`
`Allerton Conference
`
`September 22-24 , 1999
`
`T4
`
`Uliivrr-aily (IF Ci-11ifi1I'ni5)
`San Diego
`
`
`
`The Serial Concatenation ofRa1te-l Codes Through Uniform Random lnlerleawers
`
`Outline
`
`o Union Bounds and Code Performance
`
`a Serial Concatenation and Repeat—Accumu|ate (RA) Codes
`
`a Serial Concatenation of Rate-1 Codes
`
`o Repeat—Accumu|ate—Accumu|ate (RAA) Codes
`
`o Summary
`
`
`
`t
`_-E":
`r
`-—-f--
`\ ‘-3. ‘g
`um \hWm_M_m__
`nniego
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`, .
`.
`Sxgnu.’ 1'ra:r.s'm:.s‘sz0:: nnr!Recam'u1g l'.:1'rmp, £h.=n'er.m_\' of Cm':_fnrnm. Srm D.'e_1;o
`
`1
`
`
`
`The Serial Concalenalion of Ratc—l Codes Through Uniform Random lntcrlcavors
`Union Bounds on Performance
`
`a Rate r = k/n, linear block code C
`
`o Input Output Weight Enumerator Function (IOWEF) :
`
`Aw; déf # codewords, input weight to, output weight it
`
`o Union bound on word error probability PW
`(binary—input, memoryless channel, maximum-likelihood decoding):
`
`PW S 2221 Ef:U=1‘4’1-Uahzh
`
`o 2 is channel dependent; e.g., for Gaussian channel, 2 : e""(Eb/N0).
`
`o For ensembles, replace AW; by average IOWEF AW;
`
`
`
`:1 E
`-—f-
`)'
`WWW ‘K_‘__rm_ia
`;_',"Q\:.
`Sanfllego
`'
`
`Srgrtm’ 1' I‘art.5‘mi.s'.';t0It and Rr3c'rJi'd1.=Ig C.vi'rJtrp. U.'HVc‘J".\'Iu'_\’ qf Caigfrrrtttir. Sim Diego
`
`2
`
`
`
`The Serial Concalenalion of Rutc—l Codes Through Uniform Random Interleavers
`
`Serial concatenation through a Uniform lnterleaver
`
`a3»
`
`a Let C1, 02 be (711, kl), (ng, kg) linear block codes with 711 = kg,
`and IOWEFS ,4§;>h, Affih.
`
`a Let C be the (T12, kl) code obtained by serial concatenation of C1 and 02
`through a uniform interleaver of size n1, with average IOWEF AW; :
`
`A(_2)
`
`
`——r_
`$-Univznsily ul'C‘n|iI'm‘II|:| qt‘
`@‘,,':.
`Sanilliego
`
`,
`.
`.
`.
`.
`,
`.
`.
`.
`,.
`..
`Sigiiai IJ‘a:£.m1.=.s'.\‘mr1 rum’ Rerrardiiig Grrmp, Ur.=n'e.r'.\'ir_T of Cm'.'fi3r."im, San D1.£’grJ
`
`
`
`The Serial Concalenalion of Rate—l Codes Through Uniform Random lnlerlenvers
`Repeat-Accumulate IRA) Codes
`(Divsalar, et aI., Allerton’98)
`
`N
`
`Repeat
`bit q times
`
`qN
`
`qN
`
`qN
`
`li'[ l+D)
`Raic=1
`
`o Repeat input block 3:132; -
`
`-
`
`- my a total of q times.
`
`a Permute with random interleaver P of size are. : qN.
`
`o Accumulate over block:
`
`ulug---urn —>
`
`’U1’U2---‘(In
`
`’U1=U1
`
`’U2=’u1+'U»2
`
`vfl:u1+"'+u7L
`
`
`$-
`"? :9
`Uni W‘_m_hr_m_ia fififix
`:1 Diego
`
`Stgnrtf Tran.wm.\‘.s'ir)n and R(1‘(.’(}!¥z’!I1._Q Grrmp. U.I1:vei'.\‘:r_\' of C(.'.f{,f}Jmm, San Diego
`
`4
`
`
`
`The Serial Concatenalion of RaI<:—l Codes Through Uniform Random Intcrlcavcrs
`
`A Simple Example
`
`o Rate-1, (n, is) = (3, 3) Accumulate code:
`
`lnputweightw
`
`Outputweighth
`
`
`
`Unim_W_m_‘mmfl fiat;
`
`S:'gmd T}nmrs::::'.s‘.\‘i0:r and Remm’a'ng Group. U.m‘-.=r:r:'.w'.'__\= rJ_f‘C7ahj',f}>r:1."n. San Diego
`
`
`
`The Serial Concatenation of Rate-I Codes Through Uniform Random Inlerlcavers
`RA Weight Enumerator
`(Divsalar, et al., Allerton’98)
`
`o (qN, N) Repeat Code
`
`(1)
`Au”:
`
`0
`
`if h#q'w
`if
`h,:q'w
`
`(n, n) Accumulate Code (cf. "Oberg and Siegel, A!lerton’98)
`
`=( [Q5] )( [wigs £1)
`
`0 (qN, N) RA Code
`
`—
`
`’
`
`(N) (“N”) (r “"1
`w
`qw 2
`qw
`(W)qw
`
`)
`
`-1
`
`.
`
`
`
`|___imiw urcmmfl g:'Q‘;>
`SanDiego
`
`SIgnaf FrcI.=:5m:s.-;m:: and Rec.-nm'urg Grrmp. Ur.=rw:'.\‘I1__\‘ rgf (,ah.,for.-m.r. San Diego
`
`5
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`
`RA Coding Theorem
`(Divsalar, et al., AlIerton’98)
`
`o Theorem: Forq 3 3 ,there exists ’-Yq > 0 such that, for any Eb/N0 > ’Yq’ as the
`block length N becomes large,
`
`P5413 = 0W),
`
`wherefi = —
`
`Hence PW —> 0asN —> oo.
`
`o Example ,Yq estimates (from Viterbi-Viterbi Bound):
`
`73 3:: 1.112 dB
`
`74 2: 0.313 dB
`
`
`
`”_I_“::u:;“mh
`SanDle-go
`
`Q‘;-.
`
`Srgna.’ {rm!.\‘n'I:‘.\‘.\;:r)H and Recordmg Grmrp, UJJH-’er.wI_y' ofCm'.If*Jrnm‘, Sm! Duego
`
`7
`
`
`
`The Serial Concatenation of Rule-l Codes Through Uniform Random Interleavers
`
`Performance of RA Codes
`
`o RA codes, 1" : g and r : «TE, with iterative decoding.
`
`10u:...'.:::
`
`WEFI Ior Flats 1.rq HA Codes (E iheratlons]
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. _‘.
`Z
`.
`__
`Z
`
`.
`
`10-‘
`
`'..I
`
`-"J"
`
`WEFI
`
`10-
`
`::
`
`::..:_.
`
`-:55
`
`::
`
`_
`
`
`
`_;
`'2
`I
`
`10‘ + K:256q=2
`il K=512Q=2
`-X- K=1024Q=2
`-e—|(=255q—fi'g
`9- K=512q;'i
`-0- K=I02-1 q=3
`0
`
`II]-
`-0.5
`
`.
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`fittd
`XI
`u”hm,_v_“_._rm_h pan
`Sanmego
`
`.
`,
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Srgnaf Trm'1SJ'I!I.!i.§'tO.|'i a:1dRec-rmimg Group. Umver'.m_v of Cnhfzannrx, Srm Diego
`
`
`
`The Serial Concatenation of Ratc—l Codes Through Uniform Random Interleavcrs
`
`Serial Concatenation
`
`o Consider an encoder architecture of the following form:
`
`it glfiefije
`
`[RJatIe(I-1’ jut
`
`...
`
`[I—<Iet¥cCl
`
`o UIC represents a Uniform Interleaver in cascade with a rate-1 Code (e.g., an
`(n, n) Accumulate Code).
`
`c We want to characterize the average IOWEF when the code is concatenated with
`m U|C’S.
`
`
`
`..,m.v
`IILICIIIJI
`W .[ “W .
`Sat1Diego
`
`E
`
`-
`-
`-
`Sigrmi‘ h'a:z.s‘:ms.s‘:or1zmrfRer.'rJ:'d:.=:g Group. f.J'1.-:1.-'e::v:n_'rJ,f Cm’:for.-m.r, Sm: DIL’,f,’{J
`
`9
`
`
`
`The Serial Concatenation of Rate-l Codes Through Uniform Random Inicrieavers
`
`Serial Concatenation with UlC’s
`
`0 Let lOWEFfor rate—1, (n, 71) code be A = [Am], 0 3 z',j 3 n.
`
`o Define IOW Transition Probabilities (IOWTP): P = [Rd],
`
`0 3 i,j g n,
`
`A1,’
`.
`.
`R!-J : Pr(h = 3|w : 1,) : :3.
`(2-‘)
`
`o Rate-1, (n, k) : (3, 3) Accumulate code:
`
`P---—-P'r'h="w:'i=
`
`1
`
`0
`
`0
`
`0
`
`-
`0.3
`—
`
`0
`
`~—
`0.3
`—
`
`0
`
`—
`0.3
`
`O
`
`1
`
`0
`
`0 Oj—O D
`
`O
`
`..
`
`30
`
`O 1
`
`2
`
`3
`
`
`
`~% tr
`Um,V:;:C*_W_______
`
`SanDiego
`
`.S‘."gnai' Tran.w:is.s'Eor1 (mdRecc:rz!i;1g Gmup, Um'!.'c’r'_~;i.'_\‘ ofCm':fi9rm'c:, San Diego
`
`10
`
`
`
`The Serial Cuncatcnation of Rate-I Codes Through Uniform Random Intcrieavers
`
`Serial concatenation with UlC’s
`
`A“? C-°"*‘=
`Rate K1
`
`UIC
`Rate 1
`
`UIC
`Rate 1
`
`o Outer (n, is) code C, IOWEF OWL.
`
`o Cascade of m, rate-1 (n, n) U|C’s, each with IOWTP P : [ad].
`
`a Average IOWEF Awfi of serial concatenation:
`
`n
`
`Awm = Z C'w,h1 [Pm]!a1,h
`
`471120
`
`
`
`u_im____w I
`
`I'M‘;
`
`,
`
`‘fig.
`
`Sflrgriai Trm1.\'mi.\'.s'ir):1 and Recrm'a'ing Cr'r(mp, Uiifi-'(4r.w'.*_\' 0_f‘Cci.’g‘f}inii(:, San Diego
`
`11
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavcrs
`
`Perron-Frobenius Theory
`
`o Theorem: An irreducible stochastic matrix P has a unique stationary distribution
`'n'S.t. «P = at-andzm = 1.
`
`o Theorem: An irreducible aperiodic (primitive) stochastic matrix P with unique
`stationary distribution 71' satisfies:
`
`lim Pm =
`m.—rC>O
`
`o A linear rate-1 code is primitive if 19* : [PM], '21, j aé O,
`
`is a primitive matrix.
`
`
`
`\i
`.»
`II|’.I'FIfil
`W _l M W _
`nD[ego
`
`3:9",-F~.
`"3
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`—
`V
`-
`S1,:,r:ml' Imi:.m1i.s‘.wrJr: and R8('o1‘dmg Grrmp, Uiriirermtr uf Cul.'ifm-nirr, sat: Diego
`
`12
`
`
`
`The Scriz11Concatenation of Rate-I Codes Through Uniform Random Interleavers
`
`A Simple Example (cont.)
`
`o Rate-1, (n, is) : (3, 3) Accumulate Code:
`
`1
`
`0
`
`0
`
`0
`
`<0 %
`
`% 1)
`
`33:2 3;;
`
`if =<o
`
`1)
`
`0
`
`U
`
`1
`
`0
`
`lim
`m—>c-0
`
`1
`0
`0
`0
`
`0
`0
`0.3
`0.3
`0.6 03
`0
`1
`
`0
`0.3
`0
`0
`
`m
`
`_
`‘
`
`1
`0
`0
`0
`
`0
`3/7
`3/7
`3/7
`
`0
`3/7
`3/7
`3/7
`
`0
`1/7
`1/7
`1/7
`
`;:.
`uniu:_?wm|fi_m
`
`San Die go
`
`Q’
`
`Sigrid.’ Tr(m.mri.s'.s'i()r.= mid RcC0rd:'ng Group, b'r1fI-'£:r'.\'fI)‘ rJfC(!.’{'fw‘rn'(:. Srrn Dfegr;
`
`13
`
`
`
`The Serial Concatenation of Rate-I Codes Through Uniform Random intcrlcavers
`
`Stationary Distributions and Rate-1 codes
`
`a Proposition: Consider the S0 of m primitive rate-1 codes through uniform
`interleavers. For non—zero input weights and as m —> 00, the output weight
`distribution is independent of the input weight distribution and is
`
`G
`_2n—1 ,fo'r F1750.
`
`o The ensemble averaged OWEF for any rate at" < 1 code S0 with m —> oo
`primitive rate-1 codes is
`
`.v
`.....r..u
`l__l_m._ N T,
`_
`Sanllliego
`
`.
`.
`.
`.S':g-:m:'.»i Trun.vrm.s'.s‘w:i and Rec‘oi‘r1ing: Gr(J'I.ip_ i'J'i.=1irer.\'m‘ of Criiifriima. Sm: Diem":
`
`14
`
`
`
`The Serial Concatenation of RaIe—l Codes Through Uniform Random lnlerleavcrs
`
`Iterated Flate-1 Codes Make Good Codes
`
`o Proposition: For a code randomly chosen from an ensemble with average OWE
`7
`
`S1. -1
`
`(cf. Gaiiager, 1963)
`
`P'r(dmm < 03) g
`
`IJ
`
`1
`
`:-
`
`o For length n, rate r < 1,and e > 0, let d*(n, er, 5) be the largest value of d
`satisfying
`
`0’. — 1
`
`n
`h
`
`2”
`Tn __
`
`< 2
`—'
`
`1 6'
`
`h=0
`
`
`
`Uniwniwd,m__rmiu
`San Diego
`
`.SIgiim’ Ir(m.\':rIJ.\‘.s'ir)ri mid R(+(.‘0i'diiIg Grrmp,
`
`(J'i‘!'i1-’€J'.\'i‘.|'_\-' of CrIJ'if¢;r?iJ(:, Sm: D!egrJ
`
`15
`
`
`
`The Serial Conoatenation of Rate-] Codes Through Uniform Random Interleavers
`
`Iterated Rate-1 Codes Make Good Codes
`
`o Proposition: For the ensemble of length-rn, codes obtained by serial
`concatenation of a rate—r linear block code with m —> oo primitive rate-1 linear
`codes through uniform random interleavers,
`
`Pr(dmm < d*('n.,'r',e)) _§ 6.
`
`. Corollary: Let 6 = (2<1—'">“ — 1)(2="” — 1)/(2” — 1). Then,
`
`P'r'(dmm < d*) 3 e < 1,
`
`where d*is the largest value of d satisfying
`
`d—l
`
`C h ) = 2
`Z 77-
`
`<
`
`h=0
`
`n(1—r'} _ n—k'
`— 2
`
`(i.e., at least one code satisfies the Gilbert-Varshamov Bound).
`
`
`
`T I?» _
`\ Q3‘-1-‘&""-F
`M_m_I_ _mM_m_ Q‘-,;,
`Sanfliego
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`..
`Signal TJ"(Jl'!.\'!il'.'.s‘.\‘I(J!I and Recordmg Group, Univerxszry of Calgforiiia, San Diego
`
`15
`
`
`
`The Serial Cnncatcnution of Ralevl Codes Through Uniform Random ]ntcrlca\«'ers
`
`Bounds for CAT” Codes
`
`o Rate r<1, outer code C.
`
`0 Serial concatenation with m uniformly interleaved Accumulate codes.
`
`on Compute largest value d* satisfying
`
`n Then, by the bound,
`
`*
`
`1
`
`(i.e., at least half the codes satisfy dmm 3 d*).
`
`
`=-_
`
`LW_fiiw_“_“rD__fl
`Sanniego
`
`Srgmil Tran.mn.v.t:rm and Recording Group, Ifl‘I!1-'é’i".§‘I.|"\-' of Crilgforniu. Scm D.‘é’g()
`
`‘l7
`
`
`
`The Sefiai Concatenation of Ratc—I Codes Through Uniform Random [nterieayers
`
`Numerical Results
`
`a CA“ bounds for Repeat—2 and Repeat-4 codes, 1 3 m 3 4.
`
`Minimum distance guaranteed for half of the codes by our bound
`
`— 2+ - Repeat by 2 m=1
`— av - Repeat by 2 m=2
`- * - Repeat by 2 m=3
`- * Repeat by 2 m=4
`---— GV Bound rate H2
`Repeat by 4 m=1
`Repeat by 4 m=2
`Repeat by 4 m=3
`Repeat by 4 m=4
`GV Bound rate 1K4
`
`
`
`
`
`
`
`
`
`
`
`250
`
` 200
`
`
`
`
`
`150
`
` 0
`
`200
`
`400
`
`600
`Btock Length
`
`800
`
`1000
`
`1 200
`
`/41»
`Un1'vI.'nu'Iy'1fCuIiI'uruu'uI
`Sanfliego
`
`yak
`
`S:'gmr.’ Trun.s'r:rf.s.s'i(m and Recondfrrg Group. Um'1-'er'sE.'_1-‘0fCaLfifh:1Ifa. San Diego
`
`18
`
`
`
`The Serial Concatenation of R-ate—l Codes Thmugh Uniform Random Intcrleavers
`-
`Numerical Results
`
`o For (8,4) Hamming and rate 7/8 parity-check codes, 1 5 m 5 4.
`
`Minimum distance guaranteed for halt of the codes by our bound
`
`— * - Hamming (8,4) m=1
`— * - Hamming (8,4) m=2
`
`- >~ - Hamming (8,4) m=3
`
`~ >+
`- Hamming (8,4) m=4
`
`
`--- GV Bound rate H2
`
`Flate ‘H8 Parity m=1
`Fiate 7.18 Parity m=2
`
`Hate ‘H8 Parity m=3
`
`
`Hate W8 Parity m=4
`GV Bound rate 718
`
`
`
`120
`
`100
`
` 40
`
`.
`
`0
`0
`
`._'___l
`-
`—
`'1
`-
`,5:
`I,”
`V
`r2r——--—‘=‘4'-1+---"‘f"'*""*’"’“"T?‘
`.
`|:I_J'
`:1 .
`:.:.
`. "
`.
`..
`..
`"_
`-
`.. 4.
`x:
`:-
`200
`400
`800
`800
`1000
`
`—
`
`-
`
`_.
`
`1200
`
` z X
`
`Lmlvvn-i|ynl'Ca|il'm-m'u
`San Diego
`
`.S‘ignm' }'}"cmsmis.9ion mm’ Rec'0r'd:'ng Group. U:n‘1'em‘ry r;;f‘Cc1!{fiJi'nfa. San Diego
`
`19
`
`
`
`The Serial Concatenation of Rate—l Codes Through Uniform Random Intcrleavers
`Rate1/2, RAA Codes
`
`N
`
`Repeat
`hi! (1 times
`
`EIN
`
`(IN
`
`(N
`
`CIN
`
`qN
`
`lf( 1 +13)
`Rate-=1
`
`P
`
`L’( 1 +D)
`Rate=l
`
`o For rate 1" = 1 / 2 RA code, analysis and simulations suggest that there is no
`word-error-probability interleaving gain.
`
`o For rate 7" : 1 / 2 RAA code, analysis and simulations suggest that there is...
`
`
`——I:..
`
`u_I__‘hMmfi_[_i_‘ pg‘;
`San Diego
`
`Srgna.’ Irausmr.s‘.mm and Re(.'m'd:'ng Gmup. U11 :‘ver.\‘i:_v Q)‘ Ccr!.'jrmm.-, Sm: Drego
`
`20
`
`
`
`The Serial Cnncutenation of Rate-1 Codes Through Uniform Random Interlcavers
`Rate 1/2, RA vs. BAA
`
`o Word—error-probability PW , from computer simulation.
`
`3.5
`
`Acc1 K=255
`Aoc1K=512
`><—-—-x
`A0131 K=102
`:- — -x
`e—o Accz K=256
`0--—-0 Acc2K=512
`Acc2 K=1D2
`
`
`
`
`
`E5
`
`WEFI
`
`10'
`
`Mm,“ _fl_Mmi_
`Sanniego
`
`g7.QY:;.
`
`btgnal Fran.s'nn.s‘.s‘:0:1mm’Rec'0m’m_e Group, (J'mver.m‘)= of Ca.’{frm::a, Sam Drego
`
`21
`
`
`
`The Serial Concatcnation of Rate-I Codes Through Uniform Random lntcrleavers
`
`Summary
`
`o We investigated a new class of codes based upon serial concatenation of a rate-r
`code with m 3 1, uniformly interleaved rate-1 codes.
`
`o We analyzed the output weight enumerator function A—h for finite m, as well as
`asymptotically for m —> oo.
`
`a We evaluated the “goodness” of these ensembles in terms of the
`Gilbert-Varshamov Bound.
`
`c We compared 7' : 1 / 2 RAA codes to RA codes.
`
`Question: For r = 1/2, RAA codes, is there a qr such that , for Eb/N9 > 7,
`PW —> 0 as N —> oo ?
`
`
`
`..:E'—_ Q—j
`v.
`lhimm u,mirW_“
`,Q12.
`Sanfliego
`
`Sigrml Trcm.m:r.s'.su'o:': rmd R(.'c0rdmg Group. U:::1=e2'.~':.*_\= 0}’ C(J':"{fi‘H"l‘u'l'rJ', Srm Dl(’g()
`
`22