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
`
`Allerton Conference
`
`September 22-24 , 1999
`
`0
`
`Apple 1005
`Apple 1005
`
`1
`
`
`Uniform Random lnterleavers
`
`Henry Pfister and Paul H. Siegel
`Signal Transmission and Recording (STAR) Lab
`University of California, San Diego
`
`{hpfister, psiege|}@ucsd.edu
`
`Allerton Conference
`
`September 22-24 , 1999
`
`0
`
`Apple 1005
`Apple 1005
`
`1
`
`
`
`The Sena] Concatcnation of Rate—l Codes Through Uniform Random Interleavers
`
`Outline
`
`o Union Bounds and Code Performance
`
`0 Serial Concatenation and Repeat-Accumulate (RA) Codes
`
`o Serial Concatenation of Rate-1 Codes
`
`o Repeat-Accumulate-Accumulate (RAA) Codes
`
`a Summary
`
`
`
`‘>*\-"_"'
`Unimmmmrma
`SanDiego
`
`«$2513
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Szgnal Transrmsszon and Recordmg Group, Umverslry of Calzfor/ua, San Dzego
`
`1
`
`2
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`Union Bounds on Performance
`
`o Rate 7" = 19/72, linear block code C’
`
`o Input Output Weight Enumerator Function (IOWEF) :
`
`Awah Cg # codewords, input weight 10, output weight h
`
`o Union bound on word error probability PW
`(binary-input, memoryless channel, maximum-likelihood decoding):
`
`PW S 22:1 25:1 Aw,hZh
`
`o z is channel dependent; e.g., for Gaussian channel, 2 : e""(Eb/N0).
`
`o For ensembles, replace AWL by average IOWEF Awfi
`
` :-.....__
`
`T 1%»
`Unimm/dC_]_r "in
`ifizfgg.
`SanDieg'o
`E
`
`Signal Transmission and Recording Group, University of California, San Diego
`
`2
`
`3
`
`
`
`The Sefial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Serial Concatenation through a Uniform lnterleaver
`
`aih
`
`o Let C1, C; be (711, /:1), (n2, kg) linear block codes with n1 : I22,
`and IOWEFS Affh, A,ff>h.
`
`o Let C be the (n2, kl) code obtained by serial concatenation of C1 and 02
`through a uniform interleaver of size 711, with average IOWEF AW1 :
`
`711
`AM : Z An)
`,h
`h1:0
`w 1
`
`°
`
`A§?2)h
`1;
`( Z1 >1
`
`
`
`*§" «aefiig
`Univcmiiy urC-anrun.a..
`SanDieg,'0
`
`Signal Tran.s‘mz'sSi0n and Recording Group, Urziverxity of CaIz_'fornia, San Diego
`
`4
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`
`Repeat-Accumulate (RA) Codes
`(Divsalar, et al., Al|erton’98)
`
`qN
`Repeat
`. —>
`%—> .
`b1t q tunes
`
`P
`
`qN
`
`qN
`——>
`
`1/(1+D)
`Rate-=1
`
`o Repeat input block $15132 ~
`
`-
`
`- a:N a total of q times.
`
`o Permute with random interleaver P of size n = qN.
`
`o Accumulate over block:
`
`vn=u1+---+un
`
` ..—_
`--an
`
`“\
`U“ivmkMC__M_mi__ 5+: 3:;
`SanDiego
`Q
`
`.
`,
`.
`.
`.
`.
`.
`.
`.
`.
`Signal Trcuzsmtsston and Recording Group, Unzversziy of Calzforma, San Dzego
`
`5
`
`
`
`The Serial Concatenation of Rate—l Codes Through Uniform Random Interleavers
`
`A Simple Example
`
`o Rate-1, (n, k) = (3, 3) Accumulate code:
`
`lnputweightw
`
`Output Bits Outputweighth
`
`
`
`U"MnWfl_a“fimifl
`Sarmiego
`
`Szgna] 1 ransmzsszon and Recordmg Group, UmversI.ly 0fCal1f0rma, San Dzego
`
`6
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`RA Weight Enumerator
`(Divsalar, et aI., A|lerton’98)
`
`o (qN, N) Repeat Code
`
`(1)
`AW:
`
`0
`if
`h;éq'w
`(95) if h:q1u
`
`(n, n) Accumulate Code (cf. "Oberg and Siegel, A||erton’98)
`
`< {:75} )( M723 31)
`
`0 (qN, N) RA Code
`
`N
`
`qN—h
`
`hA1
`
`gm : ifw,h > 0
`
`qw
`
`
`
`‘-<,—---
`\ H
`Univcrxizy ufC-alifurni
`San Diego
`
`Signal Transmz'ssz'0n and Recording Grnup, Universily 0_fCalzf0r71ia, San Diego
`
`6
`
`$34
`
`7
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`RA Coding Theorem
`(Divsalar, et al., Allerton’98)
`
`0 Theorem: For q 2 3 , there exists ~yq > 0 such that, for any Eb/No > *yq, as the
`block length N becomes large,
`
`P5?/B = o<N‘*>,
`
`wherefiz — [9-§3].HencePW—>OasN—+oo.
`
`o Example 7,] estimates (from Viterbi—Viterbi Bound):
`
`V3 2,» 1.112 dB
`
`
`
`Xlnimwyul C 1 I ma
`
`Signal Trmzsnzission and Recording Group, University of California, San Diego
`
`7
`
`8
`
`
`
`The Serial Concatenation of Ratc—1 Codes Through Uniform Random lnterleavcrs
`
`Performance of RA Codes
`
`o RA codes, 7“ = % and 7° :
`
`with iterative decoding.
`
`
`
`WER for Rate 1/q HA Codes (20 iterations)
`'
`.‘::'
`:<:*—T‘
`
`WEFI
`
`10”‘.
`..: :2
`—><— K=25aq=2
`:
`::
`ae K=512q:2
`
`
`—><* K:1024 q=2 ..
`'
`—e~ K:25Gq=3
`-—
`-6» K=512q=3
`-0- K=1024 q=3
`
`O
`
`
`
`10-
`—0.5
`
`
`
`
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`fir" <:e£*:£
`Ufiimswurcamrnia
`§41xiV§;2.
`SanDiego
`4%’
`
`.
`.
`..
`.
`.
`_
`.
`.
`.
`,,
`.
`Slgnal 1 ransmtsston and Recording Group, UI1lV€P‘.5‘Ify of Calzfomza, San. Dzega
`
`9
`
`
`
`10
`
`The Sena] Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Serial Concatenation
`
`0 Consider an encoder architecture of the following form:
`
`*+ AnyC°d6
`R316 K1
`
`UIC
`Rate 1
`
`UIC _+
`Rate 1
`
`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 UlC’s.
`
`
`
`"x.-.:'
`Um_mS“ynrC_Mm_
`Sanlliego
`
`‘<kQ§;'F
`,%‘f,;:;.
`
`.
`,
`.
`.
`.
`.
`.
`.
`.
`.
`Signal Trarzsmrsswn and Recording Group, Unrvemziy of Calzfornza, San Dzego
`
`9
`
`10
`
`
`
`11
`
`The Serial Concatenation of Rate—1 Codes Through Unifoim Random interleave/rs
`
`Serial Concatenation with U |C’s
`
`e Let IOWEF for rate-1, (n, 72,) code be A = [A- -],
`1,]
`
`0 < z',j < n.
`_
`_
`
`o Define IOW Transition Probabilities (IOWTP): P : [PM],
`
`0 < z',j 3 n7
`
`o Rate-1, (n, k) : (3, 3) Accumulate code:
`
`.
`.
`[PW] Z [P’"(h : 9'” Z Z” Z
`
`1
`0
`0
`0
`0 03 03’ 03
`0
`0.6 03
`0
`
`0
`
`0
`
`1
`
`0
`
`(3)
`
`0 Oi=—O 0
`
`: O
`3 O
`
`O 1
`2
`3
`
`
`
`Ԥ" flier
`Unimshy
`_Mm_‘_‘
`‘,(<Ii‘,;:;.
`San ‘ego
`‘
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Signal Transmission and Recording Group, University of California, San Diego
`
`10
`
`11
`
`
`
`12
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavcrs
`
`Serial Concatenation with U|C’s
`
`—. Any C0“
`R319 K1
`
`
`
`
`
`UIC H_.
`Rate 1
`
`UIC _%.
`Rate 1
`
`o Outer (n, is) code C’, IOWEF CW1.
`
`o Cascade of m, rate—1 (n, n) U|C’s, each with IOWTP P : [PM].
`
`o Average IOWEF AWL of serial concatenation:
`
`Aw,h : Z Cw,h1 [P7n]h1,h
`/11:0
`
`
`
`-i?‘-“ «ta
`Univcrsily uI‘CaIifi.\vrnia
`rrge
`SanDie go
`
`Signal Transmission and Recording Group, University of Califamia, San Diego
`
`11
`
`12
`
`
`
`13
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random lnterleavers
`
`Perron-Frobenius Theory
`
`0 Theorem: An irreducible stochastic matrix P has a unique stationary distribution
`71'S.t. 7'l'P:’7Tal'ldZ7l'Z' = 1.
`
`o Theorem: An irreducible aperiodic (primitive) stochastic matrix P with unique
`stationary distribution 71' satisfies:
`
`lim Pm :
`7'rL:>OO
`
`o A linear rate-1 code is primitive if P+ : [Pm], 2', j 75 O,
`
`is a primitive matrix.
`
`
`
`;xF;;;+,.
`
`Signal Transmission and Recording Group, I,/niversiry of California, San Diego
`
`12
`
`13
`
`
`
`14
`
`The Sefial Concatenation of Ratc—1 Codes Through Uniform Random Interleavcrs
`
`A Simple Example (cont.)
`
`o Rate-1, (n, k:) : (3, 3) Accumulate Code:
`
`1
`
`0
`
`0
`
`0
`
`< 0
`
`r
`g
`
`%
`
`% )
`
`0 03 03 03
`0
`0:6
`0.§
`0
`
`:( 0
`
`1% 1+?-1
`
`\II+-—‘
`
`0
`
`0
`
`1
`
`0
`
`mm
`m—>oo
`
`1
`0
`0
`0
`
`0
`0
`0
`03 03 03
`0.6 03
`0
`0
`1
`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
`
`1?-F Qflw
`U_fim“Y_“aW"ia
`
`Signal Transmission and Recording Group, University 0fC{1lIf0rn.ia, San Diego
`
`14
`
`
`
`15
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Stationary Distributions and Rate-1 Codes
`
`0 Proposition: Consider the SC 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
`
`7rh=
`
`(Z)
`2n—1’
`
`for h7EO.
`
`o The ensemble averaged OWEF for any rate 7’ < 1 code SC with m —+ 00
`primitive rate-1 codes is
`
`2’I"fL __ 1
`
`“Z3751” (Z)
`
`
`
`Signal Transmission and Recording Group, Un.iver.vity nfCalif0rm'a, San Diego
`
`14
`
`15
`
`
`
`16
`
`The Serial Concatenation of Rate-l Codes Through Uniform Random Interleavers
`
`Iterated Rate-1 Codes Make Good Codes
`
`o Proposition: For a code randomly chosen from an ensemble with average OWE
`A—h,
`
`El. —-1
`
`(of. Gallager, 1963)
`
`Il
`13
`
`o For length n, rate 7" < 1,and e > 0, let d*(n, r, e) be the largest value of d
`satisfying
`
`d— 1
`
`n
`
`2 h
`
`I120
`
`2”
`— TTL _
`
`< —?21 6.
`
`
`
`Uuimmnmlm_"m
`
`Szgnal Trcmsmzsston and Recordmg Group, Umverszty of Calzforma, San Diego
`
`15
`
`16
`
`
`
`17
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`Iterated Rate-1 Codes Make Good Codes
`
`0 Proposition: For the ensemble of length-n codes obtained by serial
`concatenation of a rate-r linear block code with m —> oo primitive rate-1 linear
`codes through uniform random interleavers,
`
`P7‘(dmz-n < d*(n, 1", 6)) 3 e.
`
`0 Corollary: Let e = (2(1"’)” — 1)(2""” — 1)/(2” — 1). Then,
`
`where d*is the largest value of d satisfying
`
`<
`
`S E < 1,
`
`d—1
`n
`2<h)g2
`
`h=0
`
`(1)
`n—r‘_n~
`
`-2
`
`k
`
`(i.e., at least one code satisfies the Gilbert-Varshamov Bound).
`
`
`.—'=-...
`-V ,2 .\
`unimm urcalirwnin
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`,
`.
`Signal Transmission and Recording Group, University of Califorma, San Diego
`
`16
`
`17
`
`
`
`18
`
`The Serial Concatenation of Rate—l Codes Through Uniform Random Interleavers
`
`Bounds for CA” Codes
`
`o Rate r<1, outer code C.
`
`0 Serial concatenation with m uniformly interleaved Accumulate codes.
`
`o Compute largest value d* satisfying
`
`d—1 j 1
`2 Ah < —.
`h=1
`2
`
`o Then, by the bound,
`
`*
`1
`PT(d7rLin < d ) < 57
`(i.e., at least half the codes satisfy dmm > d*).
`
`
`:-_._...1
`
`
`u..:venuyurcawu’umaa
`SanDiego
`
`Signal Transmission and Recording Group, Univer.vz'ty of (.'alI'f0rnia, San. Diego
`
`17
`
`18
`
`
`
`19
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`
`Numerical Results
`
`o CAT” bounds for Repeat-2 and Repeat-4 codes, 1 3 m 3 4.
`
`Minimum distance guaranteed for half of the codes by our bound
`_I
`.
`— >+ - Repeat by 2 m=1
`— ><-
`V Repeat by 2 m=2
`— >+ » Repeat by 2 m=3
`200- ~ * Repeat by 2 m=4
`—><— GV Bound rate 1/2
`4 —- Repeat by 4 m=1
`'
`7 Repeat by 4 m=2
`—: Repeatby4m=3
`~“ ~ Repeat by4 m=4
`GV Bound rate 1/4
`
`;
`E
`
`_.
`
`V
`/’ 3
`
`,.
`
`v
`,,r 3:
`.
`
`"
`
`,
`
`,
`
`......... ..
`
`_
`
`250
`
`150
`
`U
`
`100-
`
`0
`O
`
`
`_ »e—J-—x——--v—|——=;x———|
`
`200
`
`400
`
`1-—~——x—|v~—><———*—Y
`800
`1000
`
`_
`600
`Block Length
`
`1200
`
` :-___.__
`
`Ԥ'f qfiza
`Univcrsky ofc».urumi..
`"qfir-*”"
`San Dte go
`
`Signal Transmission and Recording Group, University of California, San Diego
`
`18
`
`19
`
`
`
`20
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`
`Numerical Results
`
`0 For (8,4) Hamming and rate 7/8 parity-check codes, 1 3 m 3 4.
`
`120
`
`100
`
`80
`
`(
`- Hamming 8,4) m=1
`- Hamming (8,4) m=2
`— Hamming (8,4) m=3
`~ Hamming (8,4) m=4
`GV Bound rate 1/2
`Rate 7/8 Parity m=1
`a Rate 7/8 Parity m=2
`Rate 7/8 Parity m=3
`7 Rate 7/8 Parity m=4
`
`GV Bound rate 7/8
` :5;"’l;7: 1 ~32
`
`Minimum distance guaranteed for half of the codes by our bound
`_
`r"—'
`E
`.
`~
`
`.
`
`V
`
`V
`
`-
`
`-
`
`V
`
`'
`
`'
`
`'
`
`A
`
`'
`
`‘
`
`'
`
`’ ”
`
`'
`
`' "
`
`'
`
`.
`
`‘: _ 48'.
`: F1
`800
`
`1000
`
`*
`
`1200
`
` .__T
`
`
`unawnny prc..i;ruma..
`SanDiego
`
`‘V,
`
`Szgnal Transmzsszon and Recordmg Group, Umverszty 0fCal1fr)rma, San Diego
`
`19
`
`20
`
`
`
`21
`
`The Serial Concatenation of Rate—I Codes Through Uniform Random Interleavcrs
`Rate 1/2, RAA Codes
`
`N
`
`qN
`
`qN
`
`qN
`
`qN
`
`qN
`
`Repeat
`bit q timfis
`
`P
`
`1/(1+D)
`Rate=l
`
`P
`
`1/(1+D)
`Rate=l
`
`o For rate 7" = 1/2 RA code, analysis and simulations suggest that there is no
`word-error-probability interleaving gain.
`
`9 For rate r : 1/2 RAA code, analysis and simulations suggest that there is...
`
` —.—
`
`
`Un.m_mmmm__;d §7@‘i::2..
`SanDiego
`
`Signal Transmission. and Recording Group, University of California, San Diego
`
`20
`
`21
`
`
`
`22
`
`The Serial Concatcnation of Rate—1 Codes Through Uniform Random Interleavcrs
`
`Rate 1/2, RA vs. RAA
`
`o Word-error-probability PW , from computer simulation.
`Comparison of Word Error rate for RA and RAA Codes
`__ z __ ’* _ _x
`,
`
`10 :=
`
`»,;z
`
`=::
`
`—.
`
`7
`
`10*
`
`10-2?
`
`9:
`
`—3
`
`g 10
`
`E
`
`1o“‘|—
`
`
`
`Xjx Acc1 K=256
`><- ~ ><
`Acc1 K=512
`>e ~ —><
`Acc1 K=102
`e—o Acc2 K=256
`O—- — -0
`Acc2 K=512
`0 ~ -0
`Acc2 K=1024
`I
`1
`0
`0.5
`
`10-5;
`
`'
`
`10’5
`—o.5
`
`I
`1
`
`I
`15
`Eb/NO
`
`1
`2
`
`I
`2.5
`
`\
`
`\
`
`’\
`
`-\
`-\
`o
`I
`3
`
`—.
`
`3.5
`
`
`‘fir
`University nfC-.vlifornia
`SanDie gt)
`
`Signal Transmission and Recording Group, University of Callfomia, San Diego
`
`21
`
`22
`
`
`
`23
`
`The Serial Concatcnation of Rate—l Codes Through Uniform Random Interleavcrs
`
`Summary
`
`c 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.
`
`0 We analyzed the output weight enumerator function TL for finite m, as well as
`asymptotically for m —> oo.
`
`o 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 7“ = 1/2, RAA codes, is there a y such that , for Eb/N0 > 7,
`PW —> O as N —> oo ?
`
`
`
`Dummy urC_ammh_
`SanDiego
`
`gmjvggi.
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. .
`bzgnal Trarlsnmszoii and Recordmg Group, University of Call/omza, San Diego
`
`22
`
`23
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
