Decoding Times of Irregular Gallager 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
`
`October (cid:2)  (cid:10) Draft (cid:5)
`
`Abstract
`
`This paper is an appendix to (cid:0)Comparison of Constructions of Irregular Gallager
`Codes(cid:2) by David J(cid:5) C(cid:5) MacKay(cid:2) Simon T(cid:5) Wilson and Matthew C(cid:5) Davey(cid:2) which was
`published in the proceedings of the  Allerton Conference on Communication(cid:2)
`Control(cid:2) and Computing and submitted to IEEE Transactions on Communications
` July (cid:5) That paper compares alternative methods for constructing irregular
`Gallager codes(cid:5)
`This paper reports the decoding times of the codes studied in that paper(cid:5) The
`decoding time di(cid:11)ers very little between irregular codes and regular codes(cid:5)
`I prepared this draft for Dan Spielman(cid:5) Dan(cid:2) should I write this up for pub(cid:12)
`lication somewhere(cid:13) Perhaps in the IEEE Transactions on Sparse Graph Codes(cid:13)
`Oh(cid:2) that doesn(cid:14)t exist yet does it(cid:5)
`
` Introduction
`
`It is natural to speculate that irregular Gallager codes might take longer to decode than
`regular Gallager codes(cid:2) This paper presents the facts(cid:3) for the case of a small collection
`of well(cid:4)studied codes(cid:2)
`The decoding time can be described by the number of iterations of the sum(cid:4)product
`algorithm required(cid:2) One iteration is a horizontal step followed by a vertical step(cid:2) Given
`one code and a set of channel conditions the decoding time varies randomly from trial
`to trial(cid:2) Figure shows two histograms of the number of iterations to get a valid de(cid:6)
`coding under two channel conditions(cid:2) (cid:7)Cases where no valid decoding was found are not
`included in the histograms(cid:2)(cid:8) When the signal to noise ratio is higher(cid:3) fewer iterations are
`required(cid:2) In the remaining (cid:9)gures in this paper histograms like these are summarised by
`(cid:9)ve percentiles(cid:10) the th(cid:3) th(cid:3) th (cid:7)also known as the median(cid:8)(cid:3) th(cid:3) and th(cid:2)
`
` Decoding times
`
`In each panel(cid:3) the bottom graph shows for one code of each construction the median
`number of iterations to get a successful decoding as a function of Eb(cid:2)N(cid:16) upper and lower
`bars show the th(cid:3) th(cid:3) th and th percentiles of the number of iterations(cid:2)
`
`Hughes, Exh. 1052, p. 1
`
`

`
`0
`
`20
`
`40
`
`60
`
`80
`
`100 120 140 160 180
`
`1600
`
`1400
`
`1200
`
`1000
`
`800
`
`600
`
`400
`
`200
`
`0
`
`0
`
`10
`
`20
`
`30
`
`40
`
`50
`
`60
`
`55
`
`50
`
`45
`
`40
`
`35
`
`30
`
`25
`
`20
`
`15
`
`10
`
`05
`
`1600
`
`1400
`
`1200
`
`1000
`
`800
`
`600
`
`400
`
`200
`
`(cid:7)a(cid:8)
`
`(cid:7)b(cid:8)
`
`0
`
`0
`
`20
`
`40
`
`60
`
`80
`
`100 120 140 160 180
`
`Figure (cid:10) Histogram of number of iterations for a regular Gallager code with transmitted
`block length N (cid:17)  and rate R (cid:17) (cid:2)(cid:2) (cid:7)a(cid:8) Channel signal to noise ratio x(cid:2)(cid:3) (cid:17) (cid:4) (cid:2)
`(cid:7)b(cid:8) x(cid:2)(cid:3) (cid:17) (cid:4) (cid:2)
`
`Hughes, Exh. 1052, p. 2
`
`

`
` y
`
`4 4
`
`1
`
`1 1
`
`2 1
`
`1 2
`
`1 1 1
`
`1 1 1
`
`1 1 1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`
`
`3
`
`3
`
` p
`
`3
`
`9
`
`<- - - - - 7 - - - - ->
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`120
`
`100
`
`80
`
`60
`
`40
`
`20
`
`120
`
`100
`
`80
`
`60
`
`40
`
`20
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`120
`
`100
`
`80
`
`60
`
`40
`
`20
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`Figure (cid:10) Upper panels(cid:10) constructions of regular and irregular codes(cid:2) Lower panels(cid:10)
`performance of these codes(cid:2) The construction types shown are regular(cid:3) (cid:7) (cid:8)(cid:3) Poisson
`(cid:7) p(cid:8)(cid:3) and super(cid:4)Poisson (cid:7) y(cid:8)(cid:2)
`Notation for upper panels for all constructions except p(cid:10) an integer represents a number
`of permutation matrices superposed on the surrounding square(cid:2) Horizontal and vertical
`lines indicate the boundaries of the permutation blocks(cid:2) Notation for the Poisson con(cid:6)
`struction p(cid:10) integers (cid:19) (cid:21) and (cid:19) (cid:21) represent column weights(cid:2) The integer (cid:19)(cid:21) represents
`the row weight(cid:2)
`Lower panels show the performance of several random codes of each construction(cid:2) Vertical
`axis(cid:10) block error probability(cid:2) Horizontal axis(cid:10) Eb(cid:2)N in dB(cid:2) All codes have N (cid:17) (cid:3)
`and K (cid:17) M (cid:17)  (cid:2)
`All errors were detected errors(cid:3) as is usual with Gallager codes(cid:2)
`
`Hughes, Exh. 1052, p. 3
`
`

`
`l y
`1
`
`4 4
`
`1
`
`1
`
`2
`
`1
`
`2
`
`2
`
`2
`
`2
`
`2
`
`3
`
`1 1
`
`1
`
`1
`
`1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`l
`1
`
`1
`
`2
`
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`
`2
`
`2
`
`2
`
`2
`
`3
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`120
`
`100
`
`80
`
`60
`
`40
`
`20
`
`1 1 1
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`120
`
`100
`
`80
`
`60
`
`40
`
`20
`
`(cid:7)a(cid:8)
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`Figure (cid:10) (cid:7)a(cid:8) Upper panels(cid:10) construction methods l and l y(cid:2) As in (cid:9)gure (cid:3) an
`integer represents a number of permutation matrices superposed on the surrounding
`square(cid:2) A diagonal line represents an line of s(cid:2) Horizontal and vertical lines indicate the
`boundaries of the permutation blocks(cid:2) Lower pictures(cid:10) Variability of performance among
`l and l y codes(cid:2) Vertical axis(cid:10) block error probability(cid:2) Horizontal axis(cid:10) Eb(cid:2)N in dB(cid:2)
`
`Hughes, Exh. 1052, p. 4
`
`

`
`33
`l3
`l93
`93p
`93y
`
`120
`
`100
`
`80
`
`60
`
`40
`
`20
`
`95th
`
`median
`
`(cid:7)a(cid:8)
`
`1
`
`1.1
`
`1.2 1.3 1.4 1.5
`
`1
`
`0.1
`
`5th
`
`median
`
`0.01
`
`0.001
`
`0.0001
`
`l3
`33
`93p
`93y
`l93y
`
`95th
`
`(cid:7)b(cid:8)
`
`10
`
`20
`
`30
`
`40
`
`50 60 70 80 90
`
`Figure (cid:10) (cid:7)a(cid:8) Number of iterations versus Eb(cid:2)N(cid:2) (cid:7)b(cid:8) Error probability versus number of
`iterations (cid:7)on log scale(cid:8)(cid:2) Curves show th(cid:3) th and th percentiles for codes with (cid:9)ve
`di(cid:24)erent constructions(cid:2)
`
`Hughes, Exh. 1052, p. 5
`
`

`
`Figure  shows (cid:7)a(cid:8) the decoding times of all codes plotted against Eb(cid:2)N(cid:3) and (cid:7)b(cid:8) the
`error probability plotted against the decoding time(cid:2) There are di(cid:24)erences between codes
`because the codes have di(cid:24)erent absolute performances(cid:2)
`
` Discussion
`
`The di(cid:24)erences between constructions are much smaller than the range of decoding times
`within one construction(cid:2)
`
`Hughes, Exh. 1052, p. 6