`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
`
`