IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 35, NO. 6, NOVEMBER 1989 Capacity and Coding for the Gilbert-Elliott Channels MORDECHAI MUSHKIN AND ISRAEL BAR-DAVID, FELLOW, IEEE Ahstrrrrt -The Gilbert-Elliott channel is a varying binary symmetric channel with crossover probabilities determined by a binary-state Markov process. In general, such a channel has a memory that depends on the transition probabilities between the states. First, a method of calculating the capacity of this channel is introduced and applied to several examples: then the question of coding is addressed. In the conventional usage of varying channels, a code suitable for memoryless channels is used in conjunction with an interleaver, with the decoder considering the deinter- leaved symbol stream as the output of a derived memoryless channel. The transmission rate in such uses is limited by the capacity of this memoryless channel, which is, however, often considerably less than the capacity of the original channel. In this work a decision-feedback decoding algorithm, that completely recovers this capacity loss, is introduced. It is shown that the performance of a system incorporating such an algorithm is determined by an equivalent genie-aided channel, the capacity of which equals that of the original channel. Also, the calculated random coding exponent of the genie-aided channel indicates a considerable increase in the cutoff rate over the conventionally derived memoryless channel. I. INTRODUCTION AND REVIEW OF MAIN RESULTS T HE GILBERT-ELLIOTT channel [l] is a varying binary symmetric channel, the crossover probabilities of which are determined by the current state of a discrete- time stationary binary Markov process (see Fig. 1). The states are appropriately designated G for good and B for bad. Due to the underlying Markov nature of the channel, it has memory that depends on the transition probabilities between the states. Section II of this paper is devoted to the calculation of the capacity C, of the channel where p is a measure of memory. It is shown that, when the one- dimensional statistics of the channel are fixed, C, increases monotonically with p and converges asymptotically to a value Cs’ which is the capacity of the same channel when side information about its instantaneous state is available to the receiver. Section III is devoted to the efficient use of codes, originally designed for memoryless channels, over this channel with memory. Manuscript received June 10, 1988; revised April 19, 1989. An early version of this work was presented at the 1986 Symposium on Informa- tion Theory, Ann Arbor, MI, under the title, “Benefiting from Hidden Memory in Interleaved Codes.” This work was supported in part by a grant from the Israeli Ministry of Communication, in part by Elisra Electronic Systems Ltd., in part by Mr. and Mrs. I. E. Berezin, and in part by the Fund for Promotion of Research at the Technion. M. Mushkin is with Elisra, Electronic SyStems, Ltd., 48 Mivtza Kadesh Street, Bene-Beraq 51203, Israel. I. Bar-David is with the Department of Electrical Engineering, Tech- nion-Israel Institute of Technology, Haifa 32000, Israel. IEEE Log Number 8931526. b l-b 9 r-PB OT--TO PG A P8 A 4-1 i-1 i-PG I-PB Fig. 1. Gilbert-Elliott channel model. pG and pB are channel error probabilities in “good” and “bad” states, respectively, and g and h are transition probabilities between states. It is known that reliable communication over a finite- state channel is theoretically possible at any rate below capacity’ [2, pp. 176-1821. In practical uses, however, two major difficulties arise. First, much less is known about good codes for such channels than for memoryless ones; second, the length (and therefore the decoding complexity) of such codes would per force depend on the length of the channel memory. This is apparent from the fact that the error exponent for channels with memory [2, p. 1781 de- pends on the block length N whereas for memoryless channels it is independent of N. The conventional solution to these two problems is to fragment and disperse the channel memory by interleaving the encoded stream of symbols prior to transmission and to deinterleave the corresponding stream of received sym- bols [3, pp. 364-3661. If the interleaving span is long then the interleaved channel (the cascade of interleaver, channel, and deinterleaver) may be considered memoryless, and therefore efficient coding techniques for memoryless chan- nels may be used. We denote the capacity of the inter- leaved channel, under the assumption of no memory, by CNM. The disadvantage of such a solution is that the capacity C NM of the memoryless interleaved channel is lower than the capacity CP of the original channel. This fact is demonstrated in Section II and illustrated in Fig. 2, where a typical curve of C, is drawn as a function of 1-1 between its limits CNM and C”. The other curves in this figure will be explained further, In reality, however, the interleaving process, being invertible, does not remove the channel memory but only transfers it into a latent frag- ‘Strictly speaking, at any rate below _C [2, pp. 180z181]. The Gilbert-Elliott channel is indecomposable and therefore _C = C = C [2, p. 1091. OOlS-9448/89/1100-1277$01.00 01989 IEEE1278 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 35, NO, 6, NOVEMBER 1989 is composed of a novel metric calculator and a soft-deci- sion decoder, such as is used with memoryless channels. The metric calculator operates on the received channel symbols y and and on feedback decoded data 2 to esti- mate the probability q that the next channel symbol is in error, conditioned on the previous channel errors. The estimate 4 of this probability is used to