The Serial Concatenation of Rate-1 Codes Through
`Uniform Random Interleavers
`
`Henry Pfister and Paul H. Siegel
`Signal Transmission and Recording (STAR) Lab
`University of California, San Diego
`
`{hpfister, psiegel} @ ucsd.edu
`
`Allerton Conference
`September 22-24 , 1999
`
`ANUniversity of Californis
`
`San Diego
`
`0
`
`Apple 1022
`Apple 1022
`
`
`Uniform Random Interleavers
`
`Henry Pfister and Paul H. Siegel
`Signal Transmission and Recording (STAR) Lab
`University of California, San Diego
`
`{hpfister, psiegel} @ ucsd.edu
`
`Allerton Conference
`September 22-24 , 1999
`
`ANUniversity of Californis
`
`San Diego
`
`0
`
`Apple 1022
`Apple 1022
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`
`Outline
`
`e Union Bounds and Code Performance
`
`e Serial Concatenation and Repeat-Accumulate (RA) Codes
`
`Serial Concatenation of Rate-1 Codes
`
`Repeat-Accumulate-Accumulate (RAA) Codes
`
`e Summary
`
`a =
`
`= wa
`Senies rye
`San Diego
`
`Signal Transmission and Recording Group, University of California, San Diego
`
`1
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Union Boundson Performance
`
`Rate r = k/n, linear block code C
`Input Output Weight Enumerator Function (IOWEF):
`
`e e
`
`Ay:¥i e # codewords,input weight w, output weight h
`
`e Union bound on word error probability P yw
`(binary-input, memoryless channel, maximum-likelinood decoding):
`
`Pw < Sot Sg Aw,nz"
`
`z is channel dependent; e.g., for Gaussian channel, z = e~"(b/No),
`For ensembles,replace A,;, by average IOWEF Awih
`
`
`
`= abaee Rye
`
`‘San Diego
`
`Signal Transmission and Recording Group, University of California, San Diego
`
`
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Serial Concatenation through a Uniform Interleaver
`
`LaFeLe--
`
`e Let C,, C2 be (ni, k1), (ne, ka) linear block codes with n; = ko,
`and IOWEFs A“), Awh
`
`e Let C bethe (nz, k,) code obtained by serial concatenation of C, and C2
`through a uniform interleaver of size n;, with average IOWEF Ayn:
`
`A (2)
`ny
`hy.h
`Aw.h = y tig rT
`( hy )
`
`hi=0
`
`Thy
`
`(1)
`
`
`
`
`baePian Pa Signal Transmission and Recording Group, UniversityofCalifornia, San Diego=.
`
`SanDiego
`
`a
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`
`Repeat-Accumulate (RA) Codes
`(Divsalar, et al., Allerton’98)
`
`N
`
`qN
`
`qN
`
`qn
`
`Repeat
`bit q times
`
`1/(1+D)
`Rate=1
`
`- xy a total of qg times.
`-
`e Repeatinput block x; x2 -
`e Permute with randominterleaver P of size n = qN.
`e Accumulate over block:
`
`U1U2Q* ++ Un —> V1VZ--+ Un
`
`Ul = Ui
`
`V2 = U1 + U2
`
`Un = Ur++s+ + Un
`
`
`
`SF<i=. ue)
`
`San Diego
`
`Signal Transmission and Recording Group, University ofCalifornia, San Diego
`
`4
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`A Simple Example
`
`e Rate-1, (n,k) = (3,3) Accumulate code:
`
`Input Weight w
`
`Output Weight h
`
`
`
`,
`===
`Wheelieaehinte Py Signal Transmission and Recording Group, Universityof California, San
`SanDiego
`
`Diego
`
`5
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform RandomInterleavers
`RA Weight Enumerator
`(Divsalar, et al., Allerton’98)
`
`e (qN, N) Repeat Code
`
`-
`Ayn =
`
`0
`( iy )
`
`tif
`if
`
`hAquw
`h = qw
`
`(n,n) Accumulate Code(cf. ‘Oberg and Siegel, Allerton’98)
`
`ACh=( Tuyay ) ( puosat a)
`
`e (qN, N) RA Code
`
`=
`
`|
`
`(1) (fhw72y) (tquv/21—1)
`w
`qu /2
`qu 21—l/
`(ja)qu
`
`.
`
`SSSSSS
`= ala
`.
`Soentinateea rae
`Signal Transmission andRecording Group, University ofCalifornia, San Diego
`San Die
`
`6
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`RA Coding Theorem
`(Divsalar, et al., Allerton’98)
`
`e Theorem: For q > 3, there exists y, > 0 such that, for any E,/No > Yq, as the
`block length NV becomeslarge,
`
`Pi? = O(N*),
`
`where 3 = — [*]. Hence Pw — 0as N — oo.
`
`Example +, estimates (from Viterbi-Viterbi Bound):
`
`
`
`UniversityofCeitarnin EAC
`
`Signal Transmission and Recording Group, University of California, San Diego
`
`fb
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Performance of RA Codes
`
`e RAcodes, r = 3 and r = 3, with iterative decoding.
`
`
`
`[:
`107 4 K=256q=2
`F:
`*- K=512q=2
`ci
`|:
`—x- K=1024 q=2
` KeB56 q]a9 feb.
`®- K=512 9-3
`LQ= Ke1024 g=3
`
`WERforRate 1/q RA Codes(20 iterations)
`pslitigaa tee bittes
`trl caer
`bene ce
`
`cate
`
`et
`
`‘
`10 ¢
`
`10" i. 37
`
`10°
`
`10°
`
`oi
`=
`
`fevehae
`
`«|
`
`ss
`
`5
`ENG
`
`2
`
`25
`
`3
`
`3.6
`
`
`
`
`
`
`
`
`
`
`“STS aba i it , + si i B i Z
`
`Seadeeedi ry Signal Transmission and Recording Group, University ofCalifornia, San Diego
`San Diego
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Serial Concatenation
`
`e Consider an encoderarchitecture of the following form:
`
`—[aea}
`
`
`
`-YST-+_-HIast
`
`e UIC represents a Uniform Interleaver in cascade with a rate-1 Code(e.g., an
`(n,n) Accumulate Code).
`
`e Wewantto characterize the average IOWEF whenthe codeis concatenated with
`m UIC’s.
`
`LEE——————
`== sa
`niversityof
`Californian
`27d
`yO
`avaence, LA Signal Transmission and Recording Group, University of California, San Diego
`oT
`San Diego
`
`9
`
`
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Serial Concatenation with UIC’s
`
`e Let IOWEFfor rate-1, (n,n) code be A = [A;j], O< i,j <n.
`
`e Define l|OW Transition Probabilities (IOWTP): P = [P;;], 0<i,7 <n,
`
`R= Prh = je =1yo
`
`Aj;
`
`@)
`
`e Rate-1, (n, k) = (3, 3) Accumulate code:
`
`0 O—O 0
`
`Ey) = (Pr = Fer =—2)| =
`
`1
`
`0
`
`0
`
`0
`
`>
`03
`—
`
`OO
`
`Zs
`O38
`=
`
`Ss
`0.3
`
`0
`
`1
`
`0
`
`0 ee
`
`2
`3 O
`
`2
`3
`
`
`SF x
`es, As
`
`San Diego
`
`Signal Transmission andRecording Group, University ofCalifornia, San Diego
`
`10
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Serial Concatenation with UIC’s
`
`Rate r<1
`
`Rate 1
`
`=
`
`Rate |
`
`e Outer (n, k) code C, IOWEFC,,.p.
`
`e Cascadeof m, rate-1 (n, n) UIC’s, each with IOWTP P = [P,;].
`
`e Average IOWEF A.,,, of serial concatenation:
`
`Aw, = > Cw,hy [Play
`
`hy=0
`
`
`—
`
`Dibesiiartalie: DEAP
`San Diego
`
`Signal Transmission and Recording Group, University of California, San Diego
`
`11
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform RandomInterleavers
`Perron-Frobenius Theory
`
`e Theorem: Anirreducible stochastic matrix P has a unique stationary distribution
`ns.t.27P = 7 and >> 7; = 1.
`
`e Theorem: Anirreducible aperiodic (primitive) stochastic matrix P with unique
`stationary distribution z satisfies:
`
`m
`‘
`lim P=
`moo
`
`e A linear rate-1 code is primitive if P* = [P;,;], i, 7 4 0,
`
`is a primitive matrix.
`
`SS
`
`SH we
`Gata ry Signal Transmission and Recording Group, University of California, San Diego
`San Diego
`
`12
`
`
`
`The Serial Concatenation of Rate-]| Codes Through Uniform Random Interleavers
`A Simple Example (cont.)
`
`e Rate-1, (n,k) = (3,3) Accumulate Code:
`
`( 0
`
`'
`
`:
`
`7 )
`
`1
`0
`0
`
`0
`
`0
`0
`O
`0.3 03 03
`0.6
`0.3
`0
`
`O
`
`1
`
`0
`
`= ( 0 — ae ? )
`
`0
`0
`O
`1
`0O\”™
`OO
`0
`1
`
`
`lim|2 03 0.3 0.3 _| 0 3/7 3/7 1/7
`
`
`
`
`
`mc|0 06 03 £40 — O 3/7 38/7 1/7
`
`
`
`
`
`
`0
`0
`1
`0
`0
`3/7
`3/7
`1/7
`
`SSSSS
`ala
`.
`.
`: ee
`ihaliadiCauiee ry Signal Transmission and Recording Group, Universityof California, San Diego
`San Diego
`
`—=
`
`13
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Stationary Distributions and Rate-1 Codes
`
`e Proposition: Consider the SC of m primitive rate-1 codes through uniform
`interleavers. For non-zero input weights and as m — oo, the output weight
`distribution is independentof the input weightdistribution andis
`
` TK = mY ? for h#0.
`
`e The ensemble averaged OWEF for any rate r < 1 code SC with m — co
`primitive rate-1 codesis
`
`Ay = 24")
`
`Ai
`(<Wearn
`University ofCalifornia ed
`San Diego
`
`Signal Transmission and Recording Group, Universityof California, San Diego
`
`14
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Iterated Rate-1 Codes Make Good Codes
`
`e Proposition: For a code randomly chosen from an ensemble with average OWE
`An,
`
`d—1
`
`Pr(dmin < d) < S~ An.
`
`h=1
`
`(cf. Gallager, 1963)
`
`e Forlength n, rate r < 1,ande > 0, let d*(n, 1, €) be the largest value of d
`satisfying
`
`n
`2"
`h)5om—1°
`= rn.
`
`d—1
`
`h=0
`
`
`SF oles
`SidewlyofCalibecke Vg
`San Diego
`
`Signal Transmission and Recording Group, University ofCalifornia, San Diego
`
`15
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Iterated Rate-1 Codes Make Good Codes
`
`e Proposition: For the ensemble of length-n codes obtainedbyserial
`concatenation of a rate-r linear block code with m — oo primitive rate-1 linear
`codesthrough uniform random interleavers,
`
`Pr(dmin < d"(n,r,€)) < e.
`
`e Corollary: Let « = (24-"" — 1)(2™ — 1)/(2” — 1). Then,
`
`Pr(dosn < da") < € <1,
`
`where d*is the largest value of d satisfying
`
`d—1
`a
`(n(l—-r) __-
`yo (ys =2
`
`h=0
`
`6n-k
`
`(i.e., at least one codesatisfies the Gilbert-Varshamov Bound).
`
`
`aa
`:
`a, Wat
`impos: Ba>
`San Diego
`
`‘
`:
`a
`x
`.
`:
`a
`a
`Signal Transmission and Recording Group, University ofCalifornia, San Diego
`
`16
`
`
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Bounds for CA” Codes
`
`Rate r<1, outer code C.
`
`e Serial concatenation with m uniformly interleaved Accumulate codes.
`
`Computelargest value d* satisfying
`
`ai aa
`
`lI
`
`1
`
`=~
`
`An <
`
`bo]ke
`
`Then, by the bound,
`
`~
`ol
`P¥ (dean A d ) oe Py
`(i.e., at least half the codessatisfy din > d*).
`
`
`——
`
`iilaclobSalim ray
`San Diego
`
`Signal Transmission and Recording Group, University of California, San Diego
`
`17
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Numerical Results
`
`e CA” boundsfor Repeat-2 and Repeat-4 codes, 1 < m < 4.
`
`Minimum distance guaranteedfor half of the codes by our bound
`
`
`GV Bound rate 1/4
`
`250
`
`200
`
`- Repeat by 2 m=1
`» Repeat by 2 m=2
`» Repeat by 2 m=3
`Repeat by 2 m=4
`GV Boundrate 1/2
`Repeat by 4 m=1
`Repeat by 4 m=2
`Repeat by 4 m=3
`Repeat by 4 m=4
`
`.
`
`;
`
`f'
`
`if
`
`|
`
`a
`‘
`
`4
`
`0
`
`200
`
`400
`
`600
`Block Length
`
`800
`
`1000
`
`1200
`
`TT
`a, aba
`1+
`n
`sire
`i
`j
`%
`‘
`a
`‘
`ca,crGatlnde Ry Signal Transmission and Recording Group, University of California, San Diego
`San Diego
`
`18
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Numerical Results
`
`e For (8,4) Hamming and rate 7/8 parity-check codes, 1 < m < 4.
`
`Minimum distance guaranteedfor half 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 Boundrate 1/2
`
`©~
`Rate 7/8 Parity m=1
`Rate 7/8 Parity m=2
`Rate 7/8 Parity m=3
`Rate 7/8 Parity m=4
`GV Boundrate 7/8
`
`1
`
`120
`
`100
`
`40
`
`
`
`
`
`— |
`20}
`:
`sh =a oe —¢ :
`
`eH Spee eSes
`0
`A=
`a)
`— ee = B=
`A= = j=8
`a
`A
`“0
`0
`200
`400
`600
`800
`1000
`
`1200
`
`OY
`
`=.=,
`ala
`5ecelietsedd nye
`San Diego
`
`:
`- wee
`*
`.
`:
`«os
`-
`:
`Signal Transmission and Recording Group, University of California, San Diego
`
`19
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Rate 1/2, RAA Codes
`
`N
`
`Repeat
`bit q times
`
`qN
`
`qN
`
`qN
`
`W/(1+D)
`Rate=1
`
`qN
`
`
`
`1/1+D)
`Rate=1
`
`qN
`
`e For rate r = 1/2 RA code,analysis and simulations suggest that there is no
`word-error-probability interleaving gain.
`
`e For rate r = 1/2 RAA code,analysis and simulations suggestthat thereis...
`
`a=
`
`.=
`
`‘
`‘ mies
`:
`F
`5
`;
`seg
`on
`.
`ala
`
`San Diego
`
`raeee =7| Signal Transmission and Recording Group, University of California, San Diego 20
`
`
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform Random Interleavers
`Rate 1/2, RA vs. RAA
`
`e Word-error-probability Py , from computersimulation.
`
`
`
`
`
`10
`
`Acc K=256
` Acc1 K=512
`x----«
`
`*--x Acct K=102
`
`o—® Acc2 K=256
`o-— 8 Acc2 K=512
`
`Acc2 K=102:
`
`
`:
`Eb/NO
`
`z
`
`orOo
`
`3.5
`
`4 ba=
`University ofCalifornia Fy
`San Diego
`
`Signal Transmission and Recording Group, University of California, San Diego
`
`21
`
`
`
`
`
`The Serial Concatenation of Rate-1 Codes Through Uniform RandomInterleavers
`Summary
`
`e Weinvestigated a new class of codes based uponserial concatenation of a rate-r
`code with m > 1, uniformly interleaved rate-1 codes.
`
`e We analyzed the output weight enumerator function A), for finite m, as well as
`asymptotically for m — oo.
`
`e Weevaluated the “goodness”of these ensemblesin terms of the
`Gilbert-Varshamov Bound.
`
`e We compared r = 1/2 RAA codesto RA codes.
`Question: For r = 1/2, RAA codes,is there a + suchthat, for E,/No> 7,
`Pw —-O0asN—-w?
`
`ES
`>ata,
`_.
`Co
`2ae
`Signal Transmission and Recording Group, University of California, San Diego
`
`A
`iieativatiena
`San Diego
`
`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
