`
`Irregular Turbo-Like Codes
`
`Brendan J. Frey
`David J. C. MacKay
`
`Hughes, Exh. 1036, p. 1
`
`
`
`-:.. 1 ~eC\t~, ~o ..
`"\) or k
`, - C C\ rAe Ov 1 o{
`1) · MO\c~j d·,J oA
`l ((.(?~ LJ)P{ .
`Ot hm
`ttJV Its ·,"
`~OL· A\\ e(~" ncrq .
`~ yrv eol"'4. "f
`- - Stevt-t5 h kt ""i~~vV ;Jeaa~
`~~J~ f hv J" h~s
`t t'$ " 4s #.t "-e" ~ Joo. 'l
`/fl c Eh ~u ~· -krt t?t,"-l,~
`0-Jt cv1~+ -foc.v.s : S'ko r+ b/oc(
`
`€1/.8-(
`
`-
`
`-
`
`Hughes, Exh. 1036, p. 2
`
`
`
`Suppose you are told the values of
`some bits" in a transmitted codeword
`(oc- s-b.-he~)
`
`This effectively decreases the rate of
`the remaining code, making decod ing
`eas1er
`
`•
`
`Can we get a free lunch
`out of this?
`
`Hughes, Exh. 1036, p. 3
`
`
`
`Irregular codes:
`A free bite of lunch
`
`Bit or
`State
`Variable
`
`Pinned down SLOWLY
`
`~ Bitor
`
`/
`
`state
`Variable'
`
`Pinned down QUICKLY!
`
`Hughes, Exh. 1036, p. 4
`
`
`
`S' "'~ \
`'(\JO.. t : fA~~ rtt6 re
`O"'e
`.jDt Sc?n-i hi~.
`en.tt)i
`
`~,t IM.O~t ~\t;O\~ ~.
`
`Hughes, Exh. 1036, p. 5
`
`
`
`''Irreg u larizi ng'' a tu rbocode
`
`Regular turbocode R=1 0/20
`Parity bits 7
`
`"lrregularizationn
`
`States. trellis 1
`
`Systematic bits
`
`States, trellis 2
`
`Parity bits 0
`
`Irregular turbocode R=8/18
`
`Hughes, Exh. 1036, p. 6
`
`
`
`--.
`
`\
`
`CP .~ r~
`c~~(\t\e \
`\\ 'v,.e\·, W>oJ s
`
`Hughes, Exh. 1036, p. 7
`
`
`
`. . "' ,. " \ -
`
`'.\ .
`
`-
`
`~ - - -
`
`~-- -~ ~-
`
`Hughes, Exh. 1036, p. 8
`
`
`
`A r~~AlOlr ~f"i~lly cot'\~~. eot~.v. ~ (m)
`\flf1 "~
`
`0~~
`o-~~~~~~~~~~~c~AV~
`
`IW\f'-er
`o-+-.,..-..._.o--t--o-~~~~t--e CoNI eode
`
`,
`Ck~~'\el (' ~~\\ l-.odw
`
`Hughes, Exh. 1036, p. 9
`
`
`
`Af\
`
`l rr eg" 1~r ~CCC.
`l,J. ~...~,
`
`Hughes, Exh. 1036, p. 10
`
`
`
`,~ Jv~ ,Y )\//er~At
`l I rtiLR ( (J)Ja
`
`(V\
`
`\R S~·
`
`Hughes, Exh. 1036, p. 11
`
`
`
`Decodll\~ lrr~u'o..t'" Turbocodes~
`• SuM - :ProJuc+ cx.\5()rl +~Vk
`1. Col"'lfv+e.. C k<A..t'\1'\e \ OIA~ 1).. ~ LL R' s :
`L~) l~_, .. . ) L~
`
`Hughes, Exh. 1036, p. 12
`
`
`
`-
`
`-
`
`L/
`
`t\ ~
`'
`-
`.- ~X lf\S\L U\ o
`'
`
`d
`
`\
`
`, k( e0-ch ·, 6r.
`.
`VJe_ ~ec~ ~ ~
`(A_ J 0\ ( ( \ d . . .
`t )i
`
`Hughes, Exh. 1036, p. 13
`
`
`
`I
`
`...
`
`I
`
`...
`
`Rate-degree relations
`
`Trellis representing constituent convolutional codes, average rateR'
`
`I
`
`...
`
`. ..
`
`I
`
`! ' I
`
`. ..
`
`i
`I
`
`!
`
`. ..
`
`l
`
`~ · ·
`
`~··
`
`I Rep21 r
`
`I
`j
`!
`
`. . .
`l Rep 2j
`6 ... 6
`
`Permuter
`
`[ Rep3
`
`I
`l
`I
`
`I
`
`I ...
`... 6
`
`. ..
`
`...
`
`. ..
`I Rep D
`6
`
`!
`
`'
`
`I ...
`I u .
`I
`I l Rep D
`u~6
`
`In
`
`I
`
`I
`
`I
`
`d = Avg degree of codeword bits
`R = Avg rate of convolutiona l codes
`R = Rate of irregular turbocode
`
`Avg # constraints per bit: d(l- R)
`
`II - R == d( 1 - R) I
`
`Hughes, Exh. 1036, p. 14
`
`
`
`Simplified degree profiles
`
`Degree 1
`
`Degree 2
`
`Degree de: Fraction fe "elite" bits
`have degree de
`
`d = ( 1 - R) + 2 ( R -
`
`f e) + def e
`
`1- R =
`
`1-R
`(1-R)+2(R- fe)+defe
`
`Hughes, Exh. 1036, p. 15
`
`
`
`K=65536, R=l/2:
`Optimizing fe with de= 10
`
`0. 02 r - - - -- - r , --
`
`----r-- - - . -- - . . , . - - - - - - - - j
`
`+
`
`*
`
`a:
`w
`co
`
`0.015 1-
`
`0.01
`
`0.005
`
`+
`+
`
`+
`
`+
`
`-t-
`:f
`+
`
`+
`
`+
`
`+
`+
`
`-
`
`-
`
`-t-
`+
`
`*
`
`0 ..___ _
`0
`
`___.,, __ ____.__ _
`0.08
`0.06
`0.02
`0.04
`Fraction fe of degree 1 0 bits
`
`___.__t __ . . . . . ._ __1 _
`
`__ _ ,
`
`0.1
`
`Hughes, Exh. 1036, p. 16
`
`
`
`K==65536, R==l/2:
`Optimizing de with fe == .05
`
`a:
`w
`co
`
`0.06
`
`0.05
`
`0.04
`
`0.03
`
`0.02 ~
`
`0.01
`
`0
`
`-,
`
`+
`
`+
`
`+
`+
`
`I
`
`... ...
`
`+
`+
`
`I
`
`+
`+
`t
`
`20
`15
`10
`5
`0
`Degree of elite bits making up 5o/o of the codeword bits
`
`0
`
`Hughes, Exh. 1036, p. 17
`
`
`
`K==65536, R==l / 2 :
`Measured bit error rate
`
`\
`\
`
`\ ' \
`' \
`
`\
`
`------------~
`
`\
`\
`\
`
`1 e-1
`
`1e-2
`
`a:
`w 1e-3
`CD
`
`'
`
`'
`'
`
`1e-4
`
`\
`
`\
`
`\ ' \
`
`\
`\
`\
`\
`\
`
`' \
`
`'1
`
`I
`I
`i
`\
`\
`I
`I
`\
`I
`I
`I
`I
`I
`\
`i
`I
`I
`I
`I
`I
`I
`I
`I
`\
`I
`
`\J
`
`1e-5
`0.1
`
`0.2
`
`0.3
`
`0.5
`/No (dB)
`
`0.6
`
`0.7
`
`0.8
`
`n
`
`Hughes, Exh. 1036, p. 18
`
`
`
`R~k '/3 CCS t>S ·hu·boc.ode
`K = il qzo
`N = 2CD~ 7fo0
`El\ c.o Jer ~ bo +k
`toaL~s;
`
`~o ""~-Y. 4-ue.n.t
`
`Hughes, Exh. 1036, p. 19
`
`
`
`K==8920, R==l/3, CCSDS :
`Optimizing de and fe
`
`1e-1
`
`co
`"C
`.,....
`0
`Jl
`0 z
`:0 w
`......
`co
`a: 1e-2
`w
`co
`
`1 e-3 L____.....____.l...---._ l . . - -_ . ! , __ _
`0
`0.01
`0.02
`0.03
`0.04
`
`_.___""--------J
`0.05
`0.06
`0.07
`
`fe
`
`1n
`
`Hughes, Exh. 1036, p. 20
`
`
`
`K=8920, R= l/3, CCSDS :
`Measured bit error rate
`
`1 eOO ,~. - - - r - - - - - - ,- - - , --
`i
`
`- - . - -- - - .
`
`1e-1
`
`1e-2
`
`1e-3
`
`1e-4
`
`a:
`w
`a:l
`
`1e-5 ~
`I
`
`1e-6
`-0.4
`
`Irregular
`
`-0.2
`
`0.2
`0
`Eb/No (dB)
`
`0.4
`
`0.6
`
`., .,
`
`Hughes, Exh. 1036, p. 21
`
`
`
`K==8920, R==l/3, CCSDS :
`Measured word error rate
`
`1e00 ,
`'
`
`1e-1 ~ I
`
`1e-2 1
`
`1e-3
`
`1e-4
`
`a:
`w s
`
`Irregular
`
`I
`
`~
`
`1 e-5 ~,____--~.... __ _...__ __ . . . .L . . -_
`0
`0.2
`-0.2
`-0.4
`Eb/No (dB)
`
`_____. __ __ _ ,
`
`0.4
`
`0.6
`
`Hughes, Exh. 1036, p. 22
`
`
`
`Summary
`
`Irregular turbocodes are a good idea!
`
`Gain of 0.23 dB for irregular K=65536,
`R=l/2 Berrou et al turbocode
`
`. . . But, "i rreg u larization" introduces
`low-weight codewords at rate 1/2
`
`Gain of 0.2 dB for irregular K=8920 ,
`R=l/3 CCSDS turbocode- no weight
`problem
`
`For long block lengths: Use density
`evolution
`
`For short block lengths: Search is
`probably better
`
`Hughes, Exh. 1036, p. 23