Citation
Abstract
We note that, for fixed e, The idea is simply to interleave b copies of the original code. The rate of the interleaved code is the same as the original code, viz., R. The decoding of the interleaved code is actually 00 nats per symbol easier (as measured in computations per decoded bit) than for lim c= b-t- the original code. This is because the locations of the erasures (1 - e) log 2 nats per bit will be the same for each of the b codewords making up one interleaved block, and so the first step of the decoding, viz., log e-l nats per symbol the row-reduction of H, need only be done once. Thus decodlim ing one interleaved block required at most r2 row operations b-+m R, = 0 nats per bit to row-reduce H followed by at most b r further row operal tions to compute the erased components. Since each interleaved block contains bk information bits, the total decoding Thus, by taking the alphabet size (burst length) sufficiently effort as measured in row operations per decoded bit will be large, we can make the ratio C/R,, as large as desired. at most A (r/b t l), where A = (1 - R)/R. Thus as the interleaving depth b increases the needed computation per decoded bit slowly decreases to a fixed limit A. We conclude that if the Ill. Coding for the q-ary Erasure Channel original decoding algorithm was judged to be practical, then We consider first the case 4 = 2, i.e., the binary erasure the interleaved decoder must also be judged practical. Finally channel. Linear block codes are especially well suited for this we note that the probability of decoder error is the same for channel (Ref. l), as we shall now briefly explain. If y is a the interleaved and non-interleaved systems, since the interpartially erased codeword from an (n,k) binary block code leaved decoder will either decode all b codewords successfully, with parity-check matrix H, to decode y one attempts to or none of them. express the erased coordinates of y in terms of the unerased coordinates, using elementary row operations on H. The decod- In summary, given a practical system with R and error ing will be successful (i.e., a unique codeword x agreeing with probability p for the binary erasure channel, we can construct y on its unerased coordinates will be found) if and only if the an equally practical system with the same rate and same error columns of H corresponding to the erased coordinates of y probability for the 2b-ary erasure channel, for any b > 1. are linearly independent; but whether successful or not the However, as noted in Section II, the Ro-parameter for these decoding will require at most r2 row operations (r = n - k is channels approach 0 (nats per bit) as b increases. We thus can the code’s redundancy) to row-reduce H followed by at most design a practical system for which R/R0 is as large as desired. r further row operations to actually compute the values of the erased positions. For example, take 4 = 21°0, e = 0.01. Then C = 99 bits/ symbol, R, = 6.64 bits/symbol. The (8,4) Hamming code, Now imagine that we have “built” a “practical” decoder interleaved to depth 100, will have a decoded bit error probfor such a code on a binary erasure channel. We assume the ability 6.8 X 10m4, will require at most 1.04 row operations code has rate k/n = R, the channel’s raw erasure probability (8.32 bit operations) per decoded bit, and has R/R0 = 50/6.64 is e, and the bit error probability of the decoder is p. We shall = 7.5. If we took 4 = 2.1000 instead, we would have R/R0 = 75, now show how to use this code to build an equally practical everything else being the same. code for the 2b-ary erasure channel described in the last section, with the same rate (measured in nats per bit), and with We conclude that there can be no theorem which relates the same decoder bit error probability. R/R, to decoder complexity.
Details
- Volume
- 42-60
- Published
- December 15, 1980
- Pages
- 1–2
- File Size
- 69.6 KB