The Serial Concatenation of Rate-1 Codes Through
`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 1122
`Apple 1122
`
`Allerton Conference
`
`September 22-24 , 1999
`
`T4
`
`Uliivrr-aily (IF Ci-11ifi1I'ni5)
`San Diego
`
`
`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 1122
`Apple 1122
`
`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
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
