M. L. Bergman and P. G. Farrell
`
`1.
`Introduction
`The res ts reported in this contribution form part of a study of burst error
`channels? The study was based on error records derived from a hardware
`RayleigP fading simulator designed to model the 900 MHZ mobile radio
`channel . Digital transmission over fading communication media like the mobile
`radio channel is particularly prone to disruption by bursty (non-random or
`clustered) error patterns. The study1 was concerned with the characterisation of
`burst-error channels and an assessment of
`the performance of various block
`error-control coding techniques designed to combat error bursts. Since the
`study covered a wide range of concepts and techniques, and produced a large
`results, this contribution concentrates on the concept of burst
`number of
`interleaving and its performance compared to that of bit interleaving.
`2. Bit and Burst Interleaving
`In the past, there have been two main techniques €or dealing with bursty
`channels.
`first is that of designing a burst-correcting code, and many such
`codes exist , although they usually are single-burst-correcting, and need to
`have very
`long block
`lengths
`to correct
`long bursts
`(particularly
`if
`multiple-burst correcting). The second is that of interleaving (or interlacing) a
`random-error -correcting code. Using the second technique, the transmission
`order of the bits of a message is chauged, but at the receiver the origrnal order
`of the bits is reconstructed; this latter process being termed de-interleaving.
`If
`a burst occurs on the channel, causing several consecutively-transmitted bits to
`be in error, the de-interleaving process causes these errors to be widely
`separated so that they can be corrected by a random-error-correcting code. In
`technique of Burst Interleaving will be described and
`t h chapter
`the
`investigated. This techque attempts to extend the traditional interleaving
`technique (here termed bit interleaving) with the intention of splitting long
`that they can be more easily corrected by
`bursts into shorter bursts so
`burst-correcting codes. Burst interleaving could also be called byte, character
`or symbol interleaving (see below), but the term burst interleaving is felt to be
`more directly descriptive.
`Bit interleaving assumes that a block code of length n will be interleaved to a
`depth D; e.g., values of n=7 and D=3 might be used. The order of the bits in
`the message is 1 2 3 4 ... ID, and the interleaver is filled in this order.
`.However, the bits are actually transmitted by reading out 1 8 15 2 9 16 3 ... 7
`14 2l for this example.
`length L D occurs, then when the
`If a burst of
`received bits are fed into the de-interleaver the burst will have affected no
`If, for example, a burst has corrupted bits
`more than one bit per code block.
`9, 16 and 3, it can be seen that only one bit per block has been affected. The
`message can be read out of the de-interleaver, and the blocks of n bits fed
`into an error corrector which need only correct one bit per block of n bits in
`order that the whole coding scheme corrects one burst of D bits per n D bits.
`Obviously, if the error corrector used can correct more than one bit per block,
`then more than one burst (or a single but longer burst) will be correctable.
`
`M. L. Bergman is with Ferranti International plc, Wythenshaw, Manchester.
`P. G. Famll is at the University of Manchester, Department of Electrical Engineering.
`
`Ericsson Ex. 1007.001
`
`

`
`there is a delay WK occurs at both the transmitting and at the receiving end
`ible problems with the technique of interleaving. Firstly,
`There are several
`the transmrssion channel. This delay is dependent on the size of
`the
`of
`interleaver, and may or may not be undesirable depending on the application.
`In addition, extra synchronisation may be needed
`to ensure
`that
`the
`de-interleaver is being filled correctly. Another possible problem. is that if too
`many bursts occur, the use of interleaving may make the situation worse, so
`that careful design is required.
`The technique of bit interleaving can be extended to burst interleaving, in
`wech a number of bits
`A
`are kept together in the interleaving process.
`typical burst interleaver mght have b d = 4 and D=3. The burst interleaver is
`filled with every four bits being kept together on reading out. Consecutive
`"clumps" of four bits are thus separated on the channel by at least two (D-1)
`other clumps.
`5 6 7 8 9 10 11 12 U 14 15 16 17 ....
`1 2 3 4
`Read-in:
`29 30 31 32 57 58 59 60 56 78 33 ....
`1 2 3 4
`Rout-out:
`A burst in the first 12 bits will be split into three bursts of four bits, separated
`by a burst gap of 28 bits, corresponding to 24 error-free bits between bursts.
`Thus a burst-correcting code capable of correcting one burst of length b=4 bits
`in a block of n=28 bits would be able to correct a U-bit burst. Note that the
`technique of burst-interleaving is equivalent to interleaving multi-level (i.e.,
`non-binary) symbols; in the example a 16-level symbol can be represented by
`4 bits. This will be illustrated in the next section.
`3 4
`well with burst-interleaving are the Reed-Solomon (RS) codes 5 . RS codes are
`One example of a set of burst-correcting codes t h have bee found to work
`hear, cyclic, multi-level block codes. Since they are multi-level codes, the
`code symbols can be transmitted as M-bit binary characters, or mapped on to
`an m-ary multi-level modulation scheme.
`Corresponding to the (n,k,t)
`parameters of binary codes, a set of parameters (N,K,ts) can be defined for
`multi-level codes. Here, N is the number of symbols per block, K is the
`number of those symbols which convey information and t is the number of
`symbols per block correctable (h = d-1), where d is the &"g
`distance of
`the code in symbols. RS codes have d = N-K+1, which is the maximum
`possible for a given N and K, i.e. they are maximum distance separable.
`When the RS code symbols are transmitted in binary form, burst-interleaving
`to a depth (width) D can be used so that bursts of length up to D.M might be
`corrected. Thus in the example above, an RS code having M=bint = 4 might
`.be used; in this case N would be 15 symbols and the interleaver would be of
`size Bx(4x3). Note, however, that such a scheme can in fact only correct
`in order for h bursts of length M bits to be corrected per
`phased bursts, i.e.,
`block, they must start at the boundary between symbols. The maximum size
`of burst correctable, whatever its phase, is given by:
`b= hDM - (M-1)
`= hDM - M+l bits
`For the above example, a scheme with tS = 3, N = 15, D = 3 and M = 4 can
`correct a burst of length up to 33 bits (or several shorter bursts).
`In the case of a binary (n,k) block code, capable of correcting tb bursts Of
`length b, a burst interleaving scheme with b d = b is required. The
`interleaver size will be nD, and the rnaximum correctable burst length is b-
`
`Ericsson Ex. 1007.002
`
`

`
`= t@b. Alternatively, tb bursts of length bD can be corrected. For example,
`the van Overveld4 (23,ll) code has b = 2, tb = 2; used with D = 2, hint = 2
`= 8, or two
`interleaving, the scheme can correct simple bursts of length b
`bursts of
`The effective block
`(super-b1ock)Yength of
`the
`length 4.
`code-interleaver combination is the same as the interleaver size : ni = nD =
`46 bits.
`4.
`Effects of Varvine Burst-Interleaver Parameters
`It has been assumed thus far that any burst interleaver used would have hint =
`b and size ni = (n/b*nt)b.D = nD. However, a designer may wish to use an
`interleaver having difterent parameters; only a certain size interleaver may be
`available, it may have to operate with several codes, and n may not be
`divisible by b or bint.
`4.1 Varvinn the Interleaver Size. ni
`It would seem intuitive that any burst interleaver should be large enough to
`ensure n L ni/D, for which any burst would be split into smaller bursts, one
`per code block. However, this is only feasible if the code used can correct
`end-round (cyclic) bursts.
`In general, this is not the case, and n has to be
`restricted to
`n < (ni/D) - (bint-1)
`(n + hint - l)D.
`ni
`i.e.
`Increasing ni above this limit has little sigmficant effect on the performance of
`the interleaver (provided bursts longer than those designed for do not occur),
`and only increases the de-interleaving and decoding delay.
`4.2 Varvine b b
`In order to illustrate how performance varies with bint, the graph in figure 1 is
`presented, which shows the Block Error Rate achieved by simulating a burst
`mterleaver in conjunction with a burst-correcting code.
`In the figure, four
`curves are shown, for bi = 5, 10, U) and 30, and a burst-correcting code
`(derived from a code of length 63) having a value of b = 20 has been used.
`A burst-interleaving depth of D = 4 and a code-block size of n = 630 is
`assumed. The values of ni used were chosen to be greater than the limit of
`rformance improves as
`It is to be noted that the
`the equation quoted above.
`mcrease. Thus hint = 20 IS best, and it is counter-productive to use too large
`a value of hint, particularly as it requires a code wth a larger value of tb in
`order to take advantage of the full benefit of the interleaving process.
`A further point to note is that burst interleaving where bbt = 1 is exactly the
`same as bit interleaving; thus the advantage of burst interleaving over bit
`interleaving, when burst-correcting codes are used, is clear. Note however that
`all the curves on the graph have the same value of b. The possible advantage
`of bit-interleaving
`in conjunction with random-error codes
`(this being
`equivalent to a burst-correcting code having b = 1) for burst-error-control
`is
`examined in section 5.
`4.3 Varvine D
`Performance improves as D is increased, particularly if hint = b, and if tb is
`large enough (see also figure 3).
`
`pint is increased, until biQt reaches b; then it degra r es as hint continues to
`
`Ericsson Ex. 1007.003
`
`

`
`5. Co mbarison of Code -Interleavim Sche mes
`compared, together with the Golay (23, 12, 5 code, in conjunction with
`In figure 2, the bit error rates of several ap roximately prate codes are
`interleaving depths of D = 1 (no interleaving), 5, 10 and 20. Results for
`A, the general trend is that increasing code
`several approximately +rate RS codes are shown in figure 3, where D now
`refers to symbol-interleaving de th (i.e., hint = b).
`In all cases, increasing D
`improves the
`ormauce.
`block length E i m p r o v e s the performance. However, to achieve the same
`interleaver size, doubling the block length is less effective than doubling the
`interleaving depth, in the case of the BCH and Golay codes; the opposite is
`true for the RS codes, provided D > 1. Comparisons of schemes with about
`the same interleaver size (effective, or super, block length) show a clear
`As an
`superiority for the RS-based burst (symbol) interleaved schemes.
`example,-the RS (16, 8, 4) code with D = 20, ni = 1280 bits and BER C 10-5
`is better than either the BCH (U7, 7l, 9) code wth D = 10, ni = 1270 bits and
`BER LJ 8x10-4 or the BCH (63, 30, 6 ) code with D = 20, ni = 1260 bits and
`BER = lJX1O-4. The superiority of the RS-based scheme becomes smaller as
`d8 bits or \ ess), bit-interleaved binary random-error-correcting codes, and
`n decreases e.g., to IJ 640 and = 320 bits). For quite small values of ni (e.g.,
`burst-interleaved binary single and multiple burst-correct?
`codes, often have
`performances comparable to those of the RS-based schemes. A shorter code
`with burst interleaving is almost always better than a longer code with no
`lower rates (e.g., R = 113)). bit-interleaved binary
`interleaving.
`At
`random-error -correcting codes often have superior performance, particularly
`the (3,l) repetition code. There is some evidence that codes with good
`Hamming distance as well as good burst-error-control power offer better
`performance.
`6. Co nclusion
`,
`If there is no constraint on interleaver size, then burst interleaving combined
`with burst-error-control codes offers a clear advantage over bit-interleaving
`with random-error-control codes. The advantage is not so obvious if
`the
`interleaver must be relatively small. The use of short RS codes with symbol
`interleaving offers a flexible compromise with relatively good performance.
`References
`
`Mm =- B"p;""
`: Burst Error Channels; PhD Thesis, Communications
`roup, University of Manchester, 1990.
`Research
`S. H. Razavi : Data Transmission Over TACS Cellular Radio; PhD
`Thesis, Communications Research Group, University of Manchester; 1988.
`W. W. Peterson and E. J. Weldon : Error-Correcting Codes, MIT Press,
`2nd Edition, 1972.
`W. M. C. J. van Overveld : Some Constructions of New Burst-Correcting
`Codes, IEEE Trans, Voi IT-33, No 1, p 153, Jan 1987.
`
`2.
`
`3.
`
`4.
`
`a14
`
`Ericsson Ex. 1007.004
`
`

`
`2
`
`4
`
`0
`
`----
`FlG
`
`--
`1 : Effect of Varying
`
`.
`
`8
`No. of b&
`
`10
`correctable
`
`lo-’
`
`io4
`
`1 04
`
`1 04
`
`IO - 1
`
`-
`U
`m
`m
`E L
`-
`k 10-2
`.-
`
`I I
`
`IO -3
`
`IO -4
`
`Ericsson Ex. 1007.005
`
`

`
`10 -2
`
`BilErrorRnle
`
`91-’
`
`(16.8.4)
`05
`
`(31,117)
`0.55
`
`(31,153)
`0.48
`
`(5335.14)
`0.56
`
`(6133.15)
`0.52
`
`Bit Error Rates for R
`
`01
`
`v
`
`Ericsson Ex. 1007.006