Decoding Times of Repeat(cid:2)Accumulate 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:9) Draft (cid:5)
`
`Abstract
`
`Repeat(cid:10)Accumulate codes (cid:11)RA codes(cid:12) are turbo(cid:10)like codes with near(cid:10)Shannon
`limit performance(cid:5)
`This paper shows histograms of decoding times of RA codes(cid:5)
`Please forgive the cocky language in which it is written(cid:5)
`
`In the turbo code community the widespread practice when decoding is to run the
`decoder for a (cid:3)xed number of iterations(cid:2) At this point(cid:4) decoding is halted and the bit
`error rate is computed(cid:2)
`I have spent the last couple of years advocating a di(cid:5)erent approach (cid:6)for scienti(cid:3)c
`purposes at least(cid:4) if not in practice(cid:7) (cid:8) namely to detect convergence of the algorithm
`and halt when a valid state is reached(cid:2)
`Using a (cid:3)xed number of decoding iterations is wasteful of computer time because the
`number of iterations required to reach a valid state is a random variable with considerable
`variance(cid:2) To get really good performance(cid:4) the (cid:9)(cid:3)xed number(cid:10) crew have to use a large
`number of iterations(cid:11) most of their computer time is then actually spent chuntering away
`in a steady state(cid:4) in order to eke out a small fraction more decoding successes(cid:2)
`It seems a pity not to detect whether a valid state has been reached because no dis(cid:12)
`tinction is then made between the two possible failure modes of a sum(cid:13)product decoder(cid:14)
`detected block errors and undetected errors(cid:2) A detected error occurs when the decoder
`fails to reach a valid state before a maximum number of iterations is reached(cid:2) An unde(cid:12)
`tected error occurs when the decoder (cid:3)nds a valid state that corresponds to a codeword
`di(cid:5)erent from the one transmitted(cid:2)
`Distinguishing between undetected errors and detected errors is probably a good idea
`in many engineering applications if it is possible to do it(cid:2) (cid:6)For example(cid:4) if retransmission
`is an option(cid:2)(cid:7)
`I have ridden this hobby horse for some time(cid:4) but it seems only Brendan Frey has
`implemented a turbo decoder that detects when it can stop(cid:2) This week(cid:4) I implemented
`RA codes and (cid:8) it goes without saying (cid:8) my decoder halts when a valid state is reached(cid:2)
`This paper shows some results primarily to emphasize that it is possible to decode RA
`codes in this way(cid:2) These results also give an indication of the potential computational
`savings for those who simulate RA codes the old(cid:13)fashioned way(cid:4) if they will but see the
`light(cid:2)
`
`Hughes, Exh. 1054, p. 1
`
`

`
`80
`
`70
`
`60
`
`50
`
`40
`
`30
`
`20
`
`10
`
`0
`
`(cid:6)a(cid:7)
`3000
`
`2500
`
`2000
`
`1500
`
`1000
`
`500
`
`0
`
`20
`
`40
`
`60
`
`80
`
`100 120 140 160 180
`
`2000
`
`1800
`
`1600
`
`1400
`
`1200
`
`1000
`
`800
`
`600
`
`400
`
`200
`
`(cid:6)b(cid:7)
`
`0
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`0
`
`20
`
`40
`
`60
`
`80
`
`100 120 140 160 180
`
`total
`detected
`undetected
`
`0
`
`0
`
`(cid:6)c(cid:7)
`
`20
`
`40
`
`60
`
`80
`
`100 120 140 160 180
`
`1e-05
`(cid:6)d(cid:7)
`0.3
`
`0.4
`
`0.5
`
`0.6
`
`0.7
`
`0.8
`
`0.9
`
`1
`
`Figure (cid:14) Histograms of number of iterations to (cid:3)nd a valid decoding(cid:2) The RA code has
`source block length K (cid:16) and transmitted block length N (cid:16) (cid:2) (cid:6)a(cid:7) Channel
`signal to noise ratio x(cid:2)(cid:3) (cid:16) (cid:4)(cid:4) Eb(cid:2)N (cid:16) (cid:4) dB(cid:2) (cid:6)b(cid:7) x(cid:2)(cid:3) (cid:16) (cid:4) (cid:4) Eb(cid:2)N (cid:16) (cid:4) dB(cid:2)
`(cid:6)c(cid:7) x(cid:2)(cid:3) (cid:16) (cid:4) (cid:4) Eb(cid:2)N (cid:16) (cid:4) dB(cid:2) (cid:6)d(cid:7) Block error probability versus signal to noise ratio
`for the RA code(cid:2) Most errors in this experiment were detected errors(cid:4) but not quite all(cid:2)
`
`Figures (cid:6)a(cid:13)c(cid:7) show histograms of the number of iterations for a valid decoding to
`be found under two di(cid:5)erent signal(cid:13)to(cid:13)noise ratios(cid:2) The RA code has source block
`length K (cid:16) and transmitted block length N (cid:16) (cid:2) I used a maximum of 
`iterations(cid:2) If  iterations elapsed then a detected error was declared(cid:2) Detected errors
`are not included in the histograms(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:26)(cid:27)(cid:2) Figures (cid:6)b(cid:13)c(cid:7) show power laws (cid:3)tted by hand to the histograms
`of (cid:3)gures (cid:6)b(cid:13)c(cid:7)(cid:2) Histogram (cid:6)b(cid:7) is well (cid:3)tted by (cid:2)(cid:5)  and (cid:6)c(cid:7) is well (cid:3)tted by (cid:2)(cid:5) (cid:2)
`Figure (cid:6)d(cid:7) shows the block error probability versus signal to noise ratio for the same
`RA code of source length K (cid:16) and transmitted block length N (cid:16) (cid:2) Most
`errors in this experiment were detected errors(cid:4) but at high signal(cid:13)to(cid:13)noise ratios some
`undetected errors occur (cid:6)one so far(cid:4) corresponding to a codeword of weight (cid:4) found
`after  block transmissions(cid:7)(cid:2)
`In my experience RA codes with smaller block lengths make more undetected errors(cid:2)
`I(cid:10)m going to investigate further these undetected errors (cid:6)which sometimes correspond to
`codewords and sometimes to near codewords(cid:7)(cid:2)
`
`Hughes, Exh. 1054, p. 2
`
`

`
`1/x^6
`
`1/x^9
`
`1000
`
`100
`
`10
`
`1
`
`1000
`
`100
`
`10
`
`1
`
`(cid:6)b(cid:7)
`
`10
`
`20
`
`30
`
`40
`
`50 60 70 80 90100
`
`(cid:6)c(cid:7)
`
`10
`
`20
`
`30
`
`40
`
`50
`
`60
`
`70 80 90 100
`
`Figure (cid:14) Fits of power laws to the histograms of (cid:3)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:6)b(cid:7) x(cid:2)(cid:3) (cid:16) (cid:4) (cid:4)
`Eb(cid:2)N (cid:16) (cid:4) dB(cid:2) (cid:6)c(cid:7) x(cid:2)(cid:3) (cid:16) (cid:4) (cid:4) Eb(cid:2)N (cid:16) (cid:4) dB(cid:2)
`
`Discussion
`
`The Divsalar(cid:4) Jin and McEliece paper (cid:26) (cid:27) contains graphs for up to iterations(cid:2) His(cid:12)
`togram (cid:6)a(cid:7) above shows that roughly (cid:28) of the decodings in my simulation at (cid:2)dB
`took more than iterations(cid:4) with a small but substantial number taking more than 
`iterations(cid:2) So if you ran the old(cid:13)fashioned decoder for a whopping twice as long(cid:4) you
`could cut the block error probability by a factor of ten or so(cid:2) However(cid:4) using the stop(cid:13)
`when(cid:13)it(cid:10)s(cid:13)done decoder(cid:4) you can use roughly the same amount of computer time as the
`original simulation and get the error probability even lower(cid:2)
`Nothing is lost(cid:4) because (cid:6)if you log the stopping time in a (cid:3)le(cid:7) you can always recover
`the old(cid:13)fashioned graphs if anyone still wants them(cid:2)
`
`The stop(cid:2)when(cid:2)it(cid:3)s(cid:2)done method
`
`(cid:9)OK(cid:10)(cid:4) I hear you say(cid:4) (cid:9)but how do you detect a valid decoder state for an RA code(cid:29) (cid:8)
`Surely any hypothesis about the K source bits is a valid hypothesis(cid:29)(cid:10)
`The method I used is as follows(cid:2)
`
` (cid:2) While running the sum(cid:13)product algorithm up and down the accumulator trellis(cid:4)
`note the most probable state at each time(cid:2) (cid:6)You can get this by multiplying the
`forward signals by the backward signals(cid:2)(cid:7) This state sequence (cid:8) if you unaccu(cid:12)
`mulate it (cid:8) de(cid:3)nes a sequence of guesses for the source bits(cid:4) with each source bit
`being guessed q times(cid:2) (cid:6)q is the number of repetitions in the RA code(cid:2)(cid:7)
`
`(cid:2) When reading out the likelihoods from the trellis(cid:4) and combining the q likelihoods
`for each of the source bits(cid:4) 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:6) (cid:7) agree with the most probable state found in (cid:6)(cid:7) 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)
`
`Hughes, Exh. 1054, p. 3
`
`

`
`RA code construction method
`
`In case you want to know how I made the RA code(cid:4) I simply permuted the source block
`of length K twice using two randomly chosen K (cid:0) K permutations in order to create the
`scrambled repeated signal(cid:2) This isn(cid:10)t the same as repeating three times and scrambling
`the whole block of size N(cid:4) but I expect it makes little di(cid:5)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:16) to assess the variability from code to code in a single
`ensemble(cid:2)
`
`References
`
`(cid:13) (cid:14) 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:15)turbo(cid:10)like(cid:16) codes(cid:5) (cid:5)
`
`(cid:13)(cid:14) 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. 1054, p. 4
`
`

`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`(cid:6)a(cid:7)
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`total
`detected
`undetected
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`total
`detected
`undetected
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`(cid:6)b(cid:7)
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`3
`
`3.5
`
`4
`
`4.5
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`1e-05
`(cid:6)d (cid:7)
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`(cid:6)d (cid:7)
`
`total
`detected
`undetected
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`(cid:6)c(cid:7)
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`(cid:6)d(cid:7)
`
`1
`
`0.1
`
`0.01
`
`0.001
`
`0.0001
`
`1e-05
`
`(cid:6)e(cid:7)
`
`total
`detected
`undetected
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`total
`detected
`undetected
`
`0.5
`
`1
`
`1.5
`
`2
`
`2.5
`
`3
`
`3.5
`
`4
`
`4.5
`
`Figure (cid:14) Block error probability versus signal to noise ratio for RA codes with rate (cid:2) (cid:2)
`(cid:6)a(cid:7) Source block length K (cid:16) (cid:4) transmitted block length N (cid:16) (cid:2) (cid:6)b(cid:7) K (cid:16) (cid:4)
`transmitted block length N (cid:16) (cid:2) (cid:6)c(cid:7) K (cid:16) (cid:4) transmitted block length N (cid:16) (cid:2)
`(cid:6)d (cid:13) (cid:7) K (cid:16) (cid:4) transmitted block length N (cid:16) (cid:2) (cid:6)Three codes shown to illustrate
`the variability from code to code sharing identical parameters(cid:2)(cid:7) (cid:6)e(cid:7) K (cid:16) (cid:4) N (cid:16)
` (cid:6)already shown in (cid:3)gure (cid:6)d(cid:7)(cid:7)(cid:2)
`
`Hughes, Exh. 1054, p. 5