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
`
`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
`
`1
`
`
`
`The Serial Conoatenation of Rate—l Codes Through Uniform Random Interleavers
`
`Outline
`
`o Union Bounds and Code Performance
`
`0 Serial Conoatenation and Repeat-Accumulate (RA) Codes
`
`a Serial Conoatenation of Rate-1 Codes
`
`o Repeat-Acoumulate-Accumulate (RAA) Codes
`
`o Summary
`
`2
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Union Bounds on Performance
`
`o Rate 7' = k/n, linear block code C
`
`0 Input Output Weight Enumerator Function (IOWEF) :
`
`AWL Cg # codewords, input weight 10, output weight h
`
`a Union bound on word error probability PW
`(binary-input, memoryless channel, maximum-likelihood decoding):
`
`PW § 22:1 23: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 AW,
`
`3
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Serial Concatenation through a Uniform lnterleaver
`
`-+E~
`
`0 Let C1, C2 be (711, k1), (n2, kg) linear block codes with n1 : kg,
`and |OWEFs Affh, A,ff>h.
`
`0 Let C be the (TL2, k1) code obtained by serial concatenation of C1 and 02
`through a uniform interleaver of size 721, with average IOWEF AWL :
`
`77,1
`Awah __: E
`h1:0
`
`’LU,h1.
`
`A§L2)h
`__:__1__>___
`In/1
`< h
`)1
`
`4
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`
`Repeat-Accumulate (RA) Codes
`(Divsalar, et al., Allerton’98)
`
`N
`———>
`
`.
`.
`b1t q t1mes
`
`qN
`
`qN
`
`qN
`
`Rate=1
`
`0 Repeat input block $1332 ~
`
`-
`
`- :z;N a total of q times.
`
`a Permute with random interleaver P of size n :: qN.
`
`o Accumulate over block:
`
`rull/u,2...ru’n Z)
`
`rU1rU2...rUn
`
`’U1=’LL1
`
`’U2=U1-I-U2
`
`5
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`A Simple Example
`
`o Rate-1, (n, k) : (3, 3) Accumulate code:
`
`lnputWeightw
`
`Outputweighth
`
`
`
`6
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`RA Weight Enumerator
`(Divsalar, et al., Allerton’98)
`
`o (qN, N) Repeat Code
`
`(1)
`AW:
`
`0
`(qty)
`
`if
`h7éq'w
`if h:qw
`
`(n, n) Accumulate Code (of. "Oberg and Siegel, A||erton’98)
`
`=< M H fwf;i1—1>
`
`0 (qN, N) RA Code
`
`ZUJJL
`
`2 (ii) (@1375) ($5.1)
`qNqw)
`
`h’ > 0
`
`7
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`RA Coding Theorem
`(Divsalar, et al., Allerton’98)
`
`o Theorem: For q 3 3 , there exists yq > 0 such that, for any Eb/N0 > 'yq, as the
`block length N becomes large,
`
`P5? = 0W),
`
`where,8= —
`
`HencePW —+0asN——> oo.
`
`0 Example yq estimates (from Viterbi—Viterbi Bound):
`
`73 m 1.112 dB
`
`74 2:: 0.313 dB
`
`8
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Performance of RA Codes
`
`j 1
`j. 1
`.
`.
`.
`.
`o RA codes, 7“ _ 5 and 7’ _ 5, Wlth Iterative decoding.
`
`0
`
`10
`
`WER for Rate 1/q RA Codes (20 iterations)
`.
`.
`.
`.
`.
`. ..
`5;
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. .. 4-
`
`
`
`10"
`
`10'?
`
`II
`UJ
`E
`
`_ .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.-
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.-
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. ..
`
`10-355
`
`................................ HQ................ ..®.;...iiIZi_
`.....................................................................
`
`
`
`_
`
`104
`
`"'3:
`--x- K=512q=2
`
`...::_
`: —x— K=1024q=2
`.9. K=256q=3
`.
`.
`.
`.
`_
`_
`._
`t-e»K=512q=3
`.
`.
`.
`.
`.
`.
`_
`.
`.
`.
`.
`..........
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`T
`.
`_
`.
`.
`.
`.
`.
`.
`.
`..........
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`-0- K=1024q=3
`‘
`'
`'
`'
`I
`'
`
`10*‘
`_1_
`.1.
`n
`1
`_1.
`1
`___l
`-0.5
`o
`0.5
`1
`1.5
`2
`2.5
`3
`3.5
`Eb/N0
`
`9
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Serial Concatenation
`
`0 Consider an encoder architecture of the following form:
`
`“r
`
`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.
`
`10
`
`
`
`11
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Serial Concatenation with UlC’s
`
`e Let IOWEF for rate-1, (n, 72) code be A : [AM],
`
`0 < i,j < n.
`
`0 Define IOW Transition Probabilities (IOWTP): P : [PM],
`
`0 g 7L,j g n
`
`7
`
`Am-
`(C?)
`
`'
`
`o Rate-1, (n, is) : (3, 3) Accumulate code:
`
`_
`
`_. _. _
`
`1
`0
`
`0
`
`0
`0.33
`
`0
`0
`03‘ 03
`
`0
`
`1
`
`0
`
`0 O;——O
`
`keg‘)
`O
`
`11
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Serial Concatenation with U|C’s
`
`~*
`
`o Outer (n, k) code C’, IOWEF OWL.
`
`o Cascade of m, rate—1 (n, n) U|C’s, each with IOWTP P : [Pm-].
`
`0 Average IOWEF AWL of serial concatenation:
`
`Awah : Z Owahl [Pm]h1,h
`
`h1:O
`
`12
`
`
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Perron-Frobenius Theory
`
`o Theorem: An irreducible stochastic matrix P has a unique stationary distribution
`7rS.’[. 7rP : vrandzm; = 1.
`
`0 Theorem: An irreducible aperiodic (primitive) stochastic matrix P with unique
`stationary distribution 7r satisfies:
`
`lim Pm :
`’l?’L—*OO
`
`o A linear rate-1 code is primitive if P+ : [Pm-], i, j 75 0,
`
`is a primitive matrix.
`
`13
`
`
`
`The Serial Concatenation of Rate—l Codes Through Uniform Random Interleavers
`
`
`A Simple Example (cont.)
`
`14
`
`o Rate-1, (n, It) : (3, 3) Accumulate Code:
`
`(0
`
`‘QIOD
`
`‘QI00
`
`A )
`
`7
`
`1
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0.3
`
`0.6
`
`0.3
`
`0.3
`
`0
`
`1
`
`0.3
`
`0
`
`0
`
`:( 0 1i
`
`7
`
`1—|—l+1
`
`4|?-‘
`
`lim
`772,->00
`
`1
`0
`0
`0
`
`0
`0.3
`0.6
`0
`
`0
`0.3
`0.3
`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
`
`1/7
`1/7
`1/7
`
`14
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Stationary Distributions and Rate-1 Codes
`
`o 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
`
`for h#O.
`
`o The ensemble averaged OWEF for any rate r < 1 code SC with m —+ 00
`primitive rate-1 codes is
`
`15
`
`
`
`The Serial Concatenation of Rate—l Codes Through Uniform Random Interleavers
`
`Iterated Rate-1 Codes Make Good Codes
`
`0 Proposition: For a code randomly chosen from an ensemble with average OWE
`'27,
`
`(of. Gallager, 1963)
`
`R. —1
`
`ll
`13
`
`0 For length n, rate r < Land 6 > 0, let d*(n, 7“, e) be the largest value of d
`satisfying
`
`d—- 1
`
`I120
`
`n
`h
`
`2”
`
`< 2
`
`“ rn _
`
`1 6.
`
`16
`
`
`
`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-fr linear block code with m —> oo primitive rate-1 linear
`codes through uniform random interleavers,
`
`P7“(dm7;n < d*(n, 7', 6)) g E.
`
`o Corollary: Let 5 = (2(1"’)” — 1)(2””" — 1)/(2” — 1). Then,
`
`P7“(dmZ-n < d*) f 6 < 1,
`
`where d*is the largest value of d satisfying
`
`d—1
`n
`Z(h)£2
`
`h=O
`
`(
`
`n1—r_ n——k
`
`)
`
`~
`
`(i.e., at least one code satisfies the Gilbert-Varshamov Bound).
`
`17
`
`
`
`The Serial Concatenation of Rate—1 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
`
`o Then, by the bound,
`
`*
`1
`PT(dmin<d ) <57
`(i.e., at least half the codes satisfy dmm > d*).
`
`18
`
`
`
`19
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Numerlcal Results
`
`a CA” bounds for Repeat—2 and Repeat-4 codes, 1 3 m 3 4.
`
`250
`
`150
`
`100
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`,
`
`.
`
`.
`
`.
`
`.
`
`5
`§
`Q
`
`Minimum distance guaranteed for half of the codes by our bound
`1—
`-1
`I
`
`~ Repeat by 2 m=1
`§
`5
`5
`— >+ - Repeat by 2 m=2
`§
`'
`g E
`— »~ ~ Repeat by 2 m=3
`g
`//f
`200 —>+> Repeat by2m=4
`..... ..f../....._;.Cy .......... .._
`—><— GV Bound rate 1/2
`/4 ,
`:
`~:>—— Repeat by4 m=1
`/’ C ’
`«:«- Repeat by 4 m=2
`:
`,/ ’
`Ix Repeat by4 m=3
`............. _
`~f « Repeat by 4 m=4
`GV Bound rate 1/4
`
`/'¥’’'
`../.<’.....v,
`3,2’
`/
`’
`3. /
`
`y
`
`3
`
`.............. ._
`
`’
`
`
`
`50 t
`
`0
`0
`
`x— — 4- —-x—
`200
`
`)r—| —
`400
`
`_x
`
`>e~_._
`
`I
`600
`Block Length
`
`x
`
`I
`x
`800
`
`hr.
`1000
`
`1200
`
`19
`
`
`
`20
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`:__
`Numerical Results
`
`o For (8,4) Hamming and rate 7/8 parity-check codes, 1 3 m 3 4.
`
`Minimum distance guaranteed for half of the codes by our bound
`
`120 _j !
`I
`I
`3
`—>+- Hamming (8,4) m=1
`1
`—>« - Hamming (
`—
`—>+ - Hamming (8,4) m=3
`—>+ ~ Hamming (8,4) m=4
`—*— GV Bound rate 1/2
`;
`4» A Rate 7/8 Parity m=1
`«CA Rate
`m=2 .
`3
`~:> ~ Rate 7/8 Parity m=3
`.
`a<>— Rate 7/8 Parity m=4
`60 + GV Bound rate 7/8 . .......
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`,
`
`.
`
`.
`
`._
`
`I
`‘
`:
`
`
`
`.
`
`.............
`
`............... ._
`
`.
`
`. ._
`
`
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`g
`
`.
`
`.
`
`,
`
`7 .
`
`_
`
`.
`
`.
`
`.
`
`.
`
`,
`
`.
`
`100
`
`L
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`r
`
`.
`
`. . .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. ..
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`,
`
`,
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`,
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .. / .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. _
`
` .
`
`20. .
`
`.
`
`.
`
`.
`
`_
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`,
`
`.
`
`.
`
`.
`
`.
`
`_
`
`.
`
`_
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`0
`
`200
`
`400
`
`600
`
`800
`
`1000
`
`1200
`
`20
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`
`Rate 1/2, RAA Codes
`
`N
`———>
`
`.
`.
`b1t q txmes
`
`qN
`
`qN
`
`qN
`
`qN
`
`qN
`
`Rate=1
`
`Rate=1
`
`o For rate 7“ = 1/2 RA code, analysis and simulations suggest that there is no
`word-error-probability interleaving gain.
`
`a For rate 7“ :- 1/2 RAA code, analysis and simulations suggest that there is...
`
`21
`
`
`
`22
`
`The Serial Concatenation of Rate—1 Codes Through Uniform Random Interleavers
`
`Rate 1/2, RA vs. RAA
`
`o Word-error-probability PW , from computer simulation.
`
`0
`
`10
`
`Comparison of Word Error rate for RA and RAA Codes
`2':
`—
`-1-
`-
`At
`
`10“
`
`1o‘2
`
`-3
`
`I
`U;-I 10
`
`
`
`10“
`
`1o‘5
`
`Acc1 K=256
`
`><—~—-><
`Acc1 K=512
`\
`Acc1 K=102
`>e — —x
`‘\
`3
`
`e—e Acc2 K=256
`;
`
`
`0- A — -O
`Acc2 K=512
`;
`
`Acc2 K=102
`
`1045
`
`-0 5
`O
`O 5
`
`I
`1
`
`I
`1 5
`
`l
`2
`
`:_J
`2.5
`
`-\
`
`‘\
`o
`l
`3
`
`i
`3 5
`
`22
`
`
`
`23
`
`The Serial Concatcnation of Rate—1 Codes Through Uniform Random Interleavers
`
`Summary
`
`c We investigated a new class of codes based upon serial concatenation of a rate-fr
`code with m 2 1, uniformly interleaved rate-1 codes.
`
`a We analyzed the output weight enumerator function E 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 7 such that , for Eb/N0 > 7,
`PW -—> 0 as N -—> OO
`
`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
