Encyclopedia of Sparse Graph Codes
`
`David J(cid:2) C(cid:2) MacKay
`
`Department of Physics(cid:2) University of Cambridge
`
`Cavendish Laboratory(cid:2) Madingley Road(cid:2)
`Cambridge(cid:2) CB HE(cid:2) United Kingdom(cid:5)
`
`mackay(cid:2)mrao(cid:3)cam(cid:3)ac(cid:3)uk
`
`November (cid:2)  (cid:10) Draft (cid:5)
`
`Abstract
`
`Evaluation of Gallager codes for low error tolerance(cid:2) short block length and
`high rate applications(cid:5)
`Sparse graph codes include Gallager codes(cid:2) Tanner codes(cid:2) MN codes Repeat(cid:11)
`Accumulate codes (cid:12)RA codes(cid:13)(cid:2) and turbo codes(cid:2) all of which have near(cid:11)Shannon
`limit performance(cid:5)
`This paper (cid:12)which is still in preparation(cid:13) describes empirical properties of a wide
`selection of these codes(cid:2) comparing in particular the codes(cid:14) block error rates with an
`emphasis on undetected versus detected errors(cid:5) We explore the dependence of block
`error rate on block length and other code construction parameters(cid:5) Histograms of
`decoding time are also shown(cid:5)
`Draft concentrates on small block lengths(cid:5)
`
`Summary
` Regular Gallager codes
`
`(cid:0) Rate R (cid:4) (cid:2)(cid:2) Dependence on block
`length N(cid:6) weight per column t(cid:2)
`
`(cid:0) Rate R (cid:4) (cid:2) (cid:2) Dependence on block
`length N(cid:6) weight per column t(cid:2)
`
`(cid:0) Decoding times(cid:2)
`
` Repeat(cid:8)accumulate codes
`
`(cid:0) Rate R (cid:4) (cid:2) (cid:2) Dependence on block
`length N(cid:2)
`
`(cid:0) Decoding times(cid:2)
`
` Regular Gallager codes
`
`For each construction and block length I generated three random codes(cid:2) Their perfor(cid:9)
`mances are shown in (cid:10)gures (cid:8) to give an idea of the variability within one construction(cid:2)
`
`Hughes, Exh. 1050, p. 1
`
`

`
`The program GHG(cid:2)p was used to make these codes(cid:2) This program ensures there are no
`four(cid:8)cycles in the code(cid:12)s graph(cid:2) In subsequent (cid:10)gures(cid:6) one representative (cid:13)the best(cid:14) of
`these three is selected(cid:2)
`
` (cid:2) Dependence on transmitted block length N
`
`Figures  and (cid:2)
`
` (cid:2) Dependence on column weight t
`
`Figures  and (cid:2)
`
` High rate Gallager codes
`
`This section includes a collection of codes with rates (cid:2) (cid:4) (cid:3) and  (cid:2)  (cid:4) (cid:3)(cid:6)
`and a collection of codes with rates greater than (cid:2) and block lengths around  and
`(cid:2)
`
`(cid:2) Rates (cid:2) and (cid:2)
`
`(cid:2) Codes with rates above (cid:2)
`
`More results on these codes can be found in another publication (cid:21) (cid:22)(cid:2)
`
`(cid:2) Discussion
`
`In practical systems such as disc drives(cid:6) people concatenate an outer ECC with an inner
`run(cid:9)length(cid:9)limiting code (cid:13)RLL code(cid:14)(cid:6) the latter being small and non(cid:9)linear(cid:2) This doesn(cid:12)t
`seem ideal(cid:6) since it means that the errors confronting the ECC are rather complex(cid:2) So(cid:6)
`what if we could make an ECC that is an RLL code(cid:23)
`An example of such an ECC is (cid:13)surprise(cid:24)(cid:14) a Gallager code(cid:2) If I make a Gallager code
`whose top rows go like this(cid:25)
`
`
`
`
`
`
`
` (cid:3)(cid:3)(cid:3)(cid:3)
`
`(cid:3) (cid:3) (cid:3)
`
`where the row weight(cid:6) k(cid:6) is  in this example(cid:6) then the maximum possible run length of
` s in a codeword is (cid:13)k(cid:9) (cid:14) (cid:4) (cid:2)
`If the row weight is even instead of odd(cid:6) we can get more bang for our buck(cid:25) if k(cid:4)(cid:6) we
`can modify every codeword in the code by adding the vector (cid:3)
`to it(cid:2) Then all codewords will have a maximum possible run length of s equal to (cid:13)k (cid:2) (cid:14)(cid:6)
`and a maximum possible run length of s equal to (cid:13)k (cid:2) (cid:14)(cid:2)
`With a minor tweak of the Gallager code(cid:6) I can reduce (cid:13)k (cid:2) (cid:14) above to k (cid:2) (cid:2)
`Thus it is easy to make(cid:6) for example(cid:6) a good Gallager code with rate R (cid:4) (cid:2) that
`has a maximum run length of (cid:2)
`
`Hughes, Exh. 1050, p. 2
`
`

`
`N (cid:4) (cid:4) t (cid:4) (cid:13) (cid:14)
`
`N (cid:4) (cid:4) t (cid:4) (cid:13) (cid:14)
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4) 
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4) (cid:13) (cid:14)
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4) 
`
`N (cid:4) (cid:4) t (cid:4) (cid:13) (cid:14)
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4) (cid:13) (cid:14)
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4) (cid:13) (cid:14)
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:2)(cid:2) Variability within one construc(cid:9)
`tion(cid:2) Dependence of block error rate on signal to noise ratio(cid:6) weight per column t and
`transmitted block length N (cid:2) Vertical axis(cid:25) block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N
`(cid:13)decibels(cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 3
`
`

`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`N (cid:4)  (cid:4) t (cid:4) (cid:13) (cid:14)
`
`N (cid:4)  (cid:4) t (cid:4) (cid:13) (cid:14)
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4)  (cid:4) t (cid:4) 
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4)  (cid:4) t (cid:4) 
`
`total
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4)  (cid:4) t (cid:4) 
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:2)(cid:2) (cid:13)continued(cid:14)
`
`Hughes, Exh. 1050, p. 4
`
`

`
`N (cid:4) (cid:4) t (cid:4)  (cid:2) (cid:13)A(cid:14)
`
`N (cid:4) (cid:4) t (cid:4) (cid:13) A(cid:14)
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4) 
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4) 
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4)  (cid:2) (cid:13)A(cid:14)
`
`N (cid:4) (cid:4) t (cid:4) 
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4) (cid:13) A(cid:14)
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) (cid:4) t (cid:4) 
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:2) (cid:2) Variability within one construc(cid:9)
`tion(cid:2) Dependence of block error rate on signal to noise ratio(cid:6) weight per column t and
`transmitted block length N (cid:2) Vertical axis(cid:25) block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N
`(cid:13)decibels(cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 5
`
`

`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`N (cid:4)  (cid:4) t (cid:4)  (cid:2) (cid:13)A(cid:14)
`
`N (cid:4)  (cid:4) t (cid:4) (cid:13) A(cid:14)
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4)  (cid:4) t (cid:4) 
`
`total
`undetected
`undetected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:2) (cid:2) (cid:13)continued(cid:14)
`
`Hughes, Exh. 1050, p. 6
`
`

`
`t (cid:4) (cid:6) construction (cid:26) (cid:12)
`
`t (cid:4) (cid:6) construction (cid:26) (cid:12)
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`N=96
`undetected
`undetected
`N=204
`N=408
`N=816
`
`2
`
`3
`
`4
`
`5
`
`6
`
`t (cid:4) 
`
`N=96
`N=816
`
`2
`
`3
`
`4
`
`5
`
`6
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`N=96
`undetected
`undetected
`N=204
`undetected
`undetected
`N=408
`N=816
`
`2
`
`3
`
`4
`
`5
`
`6
`
`t (cid:4) 
`
`N=204
`N=816
`
`2
`
`3
`
`4
`
`5
`
`6
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:2)(cid:2) Dependence of block error rate on
`signal to noise ratio(cid:6) weight per column t and transmitted block length N(cid:2) Vertical axis(cid:25)
`block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N (cid:13)decibels(cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 7
`
`

`
`t (cid:4) (cid:6) construction (cid:26) A(cid:12)
`
`N=96
`undet
`undet
`N=408
`N=816
`
`2
`
`3
`
`4
`
`5
`
`6
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`t (cid:4)  (cid:2) (cid:6) construction (cid:26)A(cid:12)
`1
`
`N=96
`undet
`undet
`N=408
`N=816
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`t (cid:4) 
`
`N=96
`N=204
`N=408
`N=816
`
`2
`
`3
`
`4
`
`5
`
`6
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:2) (cid:2) Dependence of block error rate on
`signal to noise ratio(cid:6) weight per column t and transmitted block length N(cid:2) Vertical axis(cid:25)
`block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N (cid:13)decibels(cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 8
`
`

`
`N (cid:4) 
`
`N (cid:4) 
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`t=4
`t=3(33)
`t=3(3)
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) 
`
`33
`3
`
`2
`
`3
`
`4
`
`5
`
`6
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`t=5
`t=3(33)
`t=3(3)
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4)  
`
`t=6
`t=5
`t=4
`t=3(33)
`t=3
`
`2
`
`3
`
`4
`
`5
`
`6
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:2)(cid:2) Dependence of block error rate on
`signal to noise ratio(cid:6) weight per column t and transmitted block length N(cid:2) Vertical axis(cid:25)
`block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N (cid:13)decibels(cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 9
`
`

`
`N (cid:4) 
`
`N (cid:4) 
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`t=4
`t=3
`t=2-3
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4) 
`
`t=4
`t=3
`t=2-3
`
`2
`
`3
`
`4
`
`5
`
`6
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`t=6
`t=4
`
`2
`
`3
`
`4
`
`5
`
`6
`
`N (cid:4)  
`
`t=4
`t=3
`t=2-3
`
`2
`
`3
`
`4
`
`5
`
`6
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:2)(cid:2) Dependence of block error rate on
`signal to noise ratio(cid:6) weight per column t and transmitted block length N(cid:2) Vertical axis(cid:25)
`block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N (cid:13)decibels(cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 10
`
`

`
`t (cid:4)
` (cid:2)(cid:2) (cid:2) 
`
`total
`detected
`undetected
`
`t (cid:4) 
` (cid:2)(cid:2)(cid:2) 
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`5
`
` (cid:2)(cid:2) (cid:2) 
`
` (cid:2)(cid:2)(cid:2)
`
`total
`detected
`undetected
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`5
`
` (cid:2)(cid:2) (cid:2) 
`
` (cid:2)(cid:2)(cid:2)
`
`total
`detected
`undetected
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`5
`
`Figure (cid:25) Regular Gallager codes with rates R (cid:4) K(cid:2)N (cid:4) (cid:2) (cid:4) (cid:3)(cid:2) Dependence of
`block error rate on signal to noise ratio(cid:2) Weight per column is t (cid:4) or t (cid:4) (cid:2) Vertical
`axis(cid:25) block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N (cid:13)decibels(cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 11
`
`

`
`t (cid:4)
` (cid:2)(cid:2) (cid:2) 
`
`total
`detected
`undetected
`
`t (cid:4) 
` (cid:2)(cid:2)(cid:2) 
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
` (cid:2)(cid:2) (cid:2) 
`
` (cid:2)(cid:2)(cid:2) 
`
`total
`detected
`undetected
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
` (cid:2)(cid:2) (cid:2)
`
` (cid:2)(cid:2)(cid:2) 
`
`total
`detected
`undetected
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:3)(cid:6) K (cid:4)  (cid:6) N (cid:4) (cid:2) Dependence
`of block error rate on signal to noise ratio(cid:2) Weight per column is t (cid:4) or t (cid:4) (cid:2) Vertical
`axis(cid:25) block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N (cid:13)decibels(cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 12
`
`

`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`block errors
`bit errors
`undetected
`RS
`
`3.5
`
`4
`
`4.5
`
`5
`
`5.5
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1e-06
`
`block errors
`bit errors
`undetected
`RS
`
`3.5
`
`4
`
`4.5
`
`5
`
`5.5
`
`Figure (cid:25) Regular Gallager codes with rate R (cid:4) (cid:2) (cid:2) Dependence of block error rate on
`signal to noise ratio(cid:2) Weight per column t (cid:4)  and transmitted block length N (cid:4) (cid:2)
`Vertical axis(cid:25) block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N (cid:13)decibels(cid:14)(cid:2)
`
` Repeat(cid:4)accumulate codes
`
` (cid:2) Dependence on transmitted block length N
`
` (cid:2) (cid:2) Method
`
`For each block length(cid:6) between one and (cid:10)ve random codes were constructed to assess
`the variability of the performance within the code family for (cid:10)xed block length (cid:13)lower
`panels of (cid:10)gure (cid:14)(cid:2) The best code for each block length is shown in the upper panel of
`(cid:10)gure (cid:2)
`The histogram of decoding times (cid:5) for Gallager codes have been found to follow
`a power law for large (cid:5) (cid:21)(cid:22)(cid:2) Figures (cid:13)b(cid:8)c(cid:14) show power laws (cid:10)tted by hand to the
`histograms of (cid:10)gures (cid:13)b(cid:8)c(cid:14)(cid:2) Histogram (cid:13)b(cid:14) is well (cid:10)tted by (cid:2)(cid:5)  and (cid:13)c(cid:14) is well (cid:10)tted
`by (cid:2)(cid:5) (cid:2)
`Figure (cid:13)d(cid:14) shows the block error probability versus signal to noise ratio for the same
`RA code of source length K (cid:4) and transmitted block length N (cid:4) (cid:2) Most
`errors in this experiment were detected errors(cid:6) but at high signal(cid:8)to(cid:8)noise ratios some
`undetected errors occur (cid:13)one so far(cid:6) corresponding to a codeword of weight (cid:6) found
`after  block transmissions(cid:14)(cid:2)
`In my experience RA codes with smaller block lengths make more undetected errors(cid:2)
`I(cid:12)m going to investigate further these undetected errors (cid:13)which sometimes correspond to
`codewords and sometimes to near codewords(cid:14)(cid:2)
`
`Discussion
`
`The Divsalar(cid:6) Jin and McEliece paper (cid:21) (cid:22) contains graphs for up to iterations(cid:2) His(cid:9)
`togram (cid:13)a(cid:14) above shows that roughly (cid:27) of the decodings in my simulation at (cid:2)dB
`took more than iterations(cid:6) with a small but substantial number taking more than 
`iterations(cid:2) So if you ran the old(cid:8)fashioned decoder for a whopping twice as long(cid:6) you
`could cut the block error probability by a factor of ten or so(cid:2) However(cid:6) using the stop(cid:8)
`when(cid:8)it(cid:12)s(cid:8)done decoder(cid:6) you can use roughly the same amount of computer time as the
`original simulation and get the error probability even lower(cid:2)
`
`Hughes, Exh. 1050, p. 13
`
`

`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`total
`undetected
`
`N=204
`
`N=408
`
`N=816
`
`1
`
`N=30000
`
`2
`
`N=9999
`
`3
`
`N=3000
`
`4
`
`5
`
`N (cid:4) 
`
`N (cid:4) 
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`total
`undetected
`
`1
`
`2
`
`3
`
`4
`
`5
`
`N (cid:4)  
`
`total
`undetected
`
`1
`
`2
`
`3
`
`4
`
`5
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`total
`undetected
`
`1
`
`2
`
`3
`
`4
`
`5
`
`N (cid:4)
`
`total
`undetected
`
`1
`
`2
`
`3
`
`4
`
`5
`
`Figure (cid:25) Repeat(cid:8)accumulate codes with rate R (cid:4) (cid:2) (cid:2) Dependence of block error
`rate on signal to noise ratio and transmitted block length N(cid:2) The source block length
`K is equal to one third of N (cid:2) Vertical axis(cid:25) block error rate(cid:2) Horizontal axis(cid:25) Eb(cid:2)N
`(cid:13)decibels(cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 14
`
`

`
`2000
`
`1800
`
`1600
`
`1400
`
`1200
`
`1000
`
`800
`
`600
`
`400
`
`200
`
`0
`
`20
`
`40
`
`60
`
`80
`
`100 120 140 160 180
`
`(cid:13)b(cid:14)
`
`20
`
`40
`
`60
`
`80
`
`100 120 140 160 180
`
`total
`detected
`undetected
`
`0
`
`0
`
`1
`
`0.1
`
`0.01
`
`80
`
`70
`
`60
`
`50
`
`40
`
`30
`
`20
`
`10
`
`0
`
`(cid:13)a(cid:14)
`3000
`
`2500
`
`2000
`
`1500
`
`1000
`
`500
`
`0
`
`0
`
`(cid:13)c(cid:14)
`
`20
`
`40
`
`60
`
`80
`
`100 120 140 160 180
`
`0.001
`
`0.0001
`
`1e-05
`0.3
`
`(cid:13)d(cid:14)
`
`0.4
`
`0.5
`
`0.6
`
`0.7
`
`0.8
`
`0.9
`
`1
`
`1.1
`
`Figure (cid:25) Histograms of number of iterations to (cid:10)nd a valid decoding(cid:2) The RA code has
`source block length K (cid:4) and transmitted block length N (cid:4) (cid:2) (cid:13)a(cid:14) Channel
`signal to noise ratio x(cid:2)(cid:6) (cid:4) (cid:3)(cid:6) Eb(cid:2)N (cid:4) (cid:3) dB(cid:2) (cid:13)b(cid:14) x(cid:2)(cid:6) (cid:4) (cid:3) (cid:6) Eb(cid:2)N (cid:4) (cid:3) dB(cid:2)
`(cid:13)c(cid:14) x(cid:2)(cid:6) (cid:4) (cid:3) (cid:6) Eb(cid:2)N (cid:4) (cid:3) dB(cid:2) (cid:13)d(cid:14) Block error probability versus signal to noise ratio
`for the RA code(cid:2) Most errors in this experiment were detected errors(cid:6) but not quite all(cid:2)
`
`1/x^6
`
`1/x^9
`
`1000
`
`100
`
`10
`
`1
`
`1000
`
`100
`
`10
`
`1
`
`(cid:13)b(cid:14)
`
`10
`
`20
`
`30
`
`40
`
`50 60 70 80 90100
`
`(cid:13)c(cid:14)
`
`10
`
`20
`
`30
`
`40
`
`50
`
`60
`
`70 80 90 100
`
`Figure (cid:25) Fits of power laws to the histograms of (cid:10)gure (cid:2) Both the axes are shown
`on a log scale so that a power law curve appears as a straight line(cid:2) (cid:13)b(cid:14) x(cid:2)(cid:6) (cid:4) (cid:3) (cid:6)
`Eb(cid:2)N (cid:4) (cid:3) dB(cid:2) (cid:13)c(cid:14) x(cid:2)(cid:6) (cid:4) (cid:3) (cid:6) Eb(cid:2)N (cid:4) (cid:3) dB(cid:2)
`
`Hughes, Exh. 1050, p. 15
`
`

`
`Nothing is lost(cid:6) because (cid:13)if you log the stopping time in a (cid:10)le(cid:14) you can always recover
`the old(cid:8)fashioned graphs if anyone still wants them(cid:2)
`
`The stop(cid:4)when(cid:4)it(cid:5)s(cid:4)done method
`
`(cid:26)OK(cid:12)(cid:6) I hear you say(cid:6) (cid:26)but how do you detect a valid decoder state for an RA code(cid:23) (cid:28)
`Surely any hypothesis about the K source bits is a valid hypothesis(cid:23)(cid:12)
`The method I used is as follows(cid:2)
`
` (cid:2) While running the sum(cid:8)product algorithm up and down the accumulator trellis(cid:6)
`note the most probable state at each time(cid:2) (cid:13)You can get this by multiplying the
`forward signals by the backward signals(cid:2)(cid:14) This state sequence (cid:28) if you unaccu(cid:9)
`mulate it (cid:28) de(cid:10)nes a sequence of guesses for the source bits(cid:6) with each source bit
`being guessed q times(cid:2) (cid:13)q is the number of repetitions in the RA code(cid:2)(cid:14)
`
`(cid:2) When reading out the likelihoods from the trellis(cid:6) and combining the q likelihoods
`for each of the source bits(cid:6) compute the most probable state of each source bit(cid:2)
`This is the state which maximizes the product of the likelihoods(cid:2)
`
` (cid:2) If all the guesses in (cid:13) (cid:14) agree with the most probable state found in (cid:13)(cid:14) then the
`decoder has reached a valid state(cid:2) Halt(cid:2)
`
`The cost of these extra operations is small compared to the cost of decoding(cid:2)
`
`RA code construction method
`
`In case you want to know how I made the RA code(cid:6) I simply permuted the source block
`of length K twice using two randomly chosen K (cid:3) K permutations in order to create the
`scrambled repeated signal(cid:2) This isn(cid:12)t the same as repeating three times and scrambling
`the whole block of size N(cid:6) but I expect it makes little di(cid:29)erence when the block length
`is large(cid:2)
`
`Results for smaller block lengths
`
`Figure  shows results for various block lengths(cid:2) It also shows results for three codes
`all having block length N (cid:4) to assess the variability from code to code in a single
`ensemble(cid:2)
`
` (cid:2) Acknowledgements
`
`This work was supported by the Gatsby Foundation(cid:2) DJCM thanks the researchers at
`the Sloane Center(cid:6) Department of Physiology(cid:6) University of California at San Francisco(cid:6)
`for their generous hospitality(cid:6) and Lucent and Seagate for helpful discussions(cid:2)
`
`References
`
`(cid:15) (cid:16) D(cid:5) Divsalar(cid:2) H(cid:5) Jin(cid:2) and R(cid:5) J(cid:5) McEliece(cid:5) Coding theorems for (cid:17)turbo(cid:11)like(cid:14) codes(cid:5) (cid:5)
`
`(cid:15)(cid:16) D(cid:5) J(cid:5) C(cid:5) MacKay(cid:5) Deccoding times of irregular Gallager codes(cid:5) Unpublished(cid:2) (cid:5)
`
`Hughes, Exh. 1050, p. 16
`
`

`
`total
`detected
`undetected
`
`-1
`
`0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`(cid:13)a(cid:14)
`
`total
`detected
`undetected
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`total
`detected
`undetected
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`1
`
`(cid:13)b(cid:14)
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`0.0001
`-0.5
`
`(cid:13)c(cid:14)
`
`0
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`(cid:13)d (cid:14)
`
`1e-05
`0.3 0.4 0.5 0.6 0.7 0.8 0.9
`
`1
`
`1.1 1.2 1.3 1.4
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`total
`detected
`undetected
`
`1e-05
`0.4 0.5 0.6 0.7 0.8 0.9
`
`1
`
`1.1 1.2 1.3 1.4
`
`(cid:13)d(cid:14)
`
`(cid:13)d (cid:14)
`
`1e-05
`0.4 0.5 0.6 0.7 0.8 0.9
`
`1
`
`1.1 1.2 1.3 1.4
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`(cid:13)e(cid:14)
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`total
`detected
`undetected
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`(cid:13)d(cid:14)
`
`1e-05
`0.3 0.4 0.5 0.6 0.7 0.8 0.9
`
`1
`
`1.1 1.2 1.3 1.4
`
`Figure (cid:25) Block error probability versus signal to noise ratio for RA codes with rate
` (cid:2) (cid:2) (cid:13)a(cid:14) Source block length K (cid:4) (cid:6) transmitted block length N (cid:4) (cid:2) (cid:13)b(cid:14) K (cid:4) (cid:6)
`transmitted block length N (cid:4) (cid:2) (cid:13)c(cid:14) K (cid:4) (cid:6) transmitted block length N (cid:4) (cid:2)
`(cid:13)d (cid:8) (cid:14) K (cid:4) (cid:6) transmitted block length N (cid:4) (cid:2) (cid:13)Three codes shown to illustrate
`the variability from code to code sharing identical parameters(cid:2)(cid:14) (cid:13)e(cid:14) K (cid:4) (cid:6) N (cid:4)
` (cid:13)already shown in (cid:10)gure (cid:13)d(cid:14)(cid:14)(cid:2) (cid:13)d(cid:14) Superposition of (cid:13)d (cid:8) (cid:14)(cid:2)
`
`Hughes, Exh. 1050, p. 17
`
`

`
`(cid:15) (cid:16) D(cid:5) J(cid:5) C(cid:5) MacKay(cid:5) Evaluation of gallager codes for short block length and high rate appli(cid:18)
`cations(cid:5) Available from www(cid:3)keck(cid:3)ucsf(cid:3)edu(cid:4)(cid:5)mackay(cid:4)(cid:2) (cid:5)
`
`Hughes, Exh. 1050, p. 18