6.441-22 Finite state Markov channels

LECTURE 22 Last time: • Broadcast channel • Gaussian degraded broadcast channelLecture outline • Finite-state channels • Lower capacity and upper capacities• Indecomposable channels • Markov channels � � � � � � � � � Finite-state channelsThe state of the channel at time i is Si The state determines the transition probabillit in the following way: PY n,Sn|Xn,S0 yn,sn|xn,s0 we assume that the channel is stationary There is memory that is different than in the case of ISI channel -memory in state rather than in input The transition probabilities are determined recursively from the one-step transition probabiliities PY n,Sn|Xn,S0 yn,sn|xn,s0 = sn−1 PYn,Sn|Xn,Sn−1 yn,sn|xn,sn−1 PY n−1,Sn−1|Xn−1,S0 yn−1,sn−1|xn−1,s0 � � � � � Upper and lower capacitiesPYn|Xn,S0 yn,sn|xn,s0 = sn PYn,Sn|Xn,S0 yn,sn|xn,s0 Upper capacity: C = limn→∞ Cn where Cn = 1 maxPXn(xn) maxs0 I(Xn; Yn|s0)n Lower capacity:C = limn→∞ CnwhereCn = 1 maxPXn(xn) mins0 I(Xn; Yn|s0)n Neither is the ”capacity” Indecomposable channelsSuppose that we have finite input alphabet X and a finite set of states S Indecomposable means that the initial state does not matter ∀> 0, ∃n0s.t.∀n>n0 |PSn|Xn,S0(sn|xn,s0) − PSn|Xn,S0(sn|xn,s0)|≤ For such channels: C = C Proof: pick some integer number μ let s0 be an initial state such that the maximmu average mutual information over n samples starting from s0 yields Cn let s0 be an initial state such that the maximmu average mutual information over n samples starting from s0 yields Cn � � � � � � �� � � Indecomposable channelsApplying twice the chain rule on mutual informaation we obtain (with the input distributtio that yields Cn) Cn =1 I Xμ; Yn|S0= s 0 n +I Xμn +1; Yμ|S0= s0,Xμ +I Xμn +1; Ynμ+1|S0= s0,Xμ,Yμ let us bound each element in the sum: the first term is upper bounded by μlog(|X |)the second term is 0 the third term, using the chain rule on mutuua information and the cardinality bound on the information about Sn, can be upper bounded by: log(|S|)+I Xμn +1; Ynμ+1|S0= s0,Xμ,Yμ,Sn � � � �� � � � �� Indecomposable channelsSimilarly, we obtain the bound: 1 Cn ≥ n [− log(|S|) � �� +I Xn μ+1; Yn μ+1|S0 = s 0,Xμ,Yμ,Sn then Cn − Cn 1 =[μlog(|X |) + 2 log(|S|)n+I Xnμ+1; Ynμ+1|S0= s0,Xμ,Yμ,Sn −I Xnμ+1; Ynμ+1|S0= s0,Xμ,Yμ,Sn 1=[μlog(|X |) + 2 log(|S|)n+I Xnμ+1; Ynμ+1|S0= s0,Xμ,Sn −I Xnμ+1; Ynμ+1|S0= s0,Xμ,Sn 1 ≤ [μlog(|X |) + 2 log(|S|) n+(n− μ) log(|X |)]where can be made arbitrarily small by approprriatel large choice of μ (which entails sufficiently large n) Markov channelsA special case of indecomposable channels arise when we have a Markov description for the channel states, the states are indepennden of the inputs conditioned on other states Assume the states form a single class of recurrent states, aperiodic Then we have indecomposable channel (see lecture 4) How might we establish a coding theorem for such channels with finite input alphabet and no other constraint on input? � Markov channelsSuppose the current state is known at the sender and the receiver For each state, establish capacity as though that were the only state, let Cs be the capaccit if we were to remain in state s always Average over all the states, the capacity is:s∈S πsCs The coding theorem relies on interleaving codewords over the different states Pick one codebook per state, send portions of the codeword in a codebook only when that state occurs Because of recurrence, each state is always guaranteed to reappear eventually The average transmission rate is the averaag of the transmissions over all the code-books � Markov channelsIf receiver and sender both have Markovian channel side information (CSI) and sender is a function of receiver CSI, then this conceep extends Example: delayed knowledge at the sender of state of channel (because of delays in feedback, for example) Let Ui be the sender CSI (SCSI), which is a deterministic function g of the perfect receiver CSI (RCSI) Vi (thus, the receiver knows the channel exactly Vi = Si) such that Ui remains Markovian Then the capacity is given by (using stationnarit to eliminate time subscripts): C = u∈U PU (u) maxPX|UI(X; Y |S, U = =u u) Markov channels Other cases: • Known at the receiver but not the sender: then the computation is more involved, but the theorem for indecomposable channeel still holds. Sender does not change strategy. • Known at the sender but not the receiiver strategies for the receiver to estimmat the channel are important. • Channel statistics known but channel not known: sender does not change strategy. Hypothesis testing at receiver. Recall Gilbert-Eliot channel. More states: different approach is required. Markov channels What happens when we have for instance different types of AWGN channels? The theorems need to be revisited. The finiteness of states is still an important aspeect Suppose we have two channels, one (channne 1) with noise psd N0 and the other(channel 2) with noise psd N0 >N0 Perfect CSI at the sender and the receiver Does water-filling work? With a modification: make several channeel with noise energy WN0 and several channels with noise energy WN0 in proportiio π1: π2 Then do water-filling on these channels This is power control � � �� Markov channelsWhat happens when we do not have perfect CSI at sender and receiver? Consider the case of AWGN channels with different states where the channel state repressent an amplification factor (this view is clearly equivalent to changing the psd of the AWGN) We have that: √ Y = SX + N when channel S is in force The receiver has perfect CSI The sender has some function of S We then have that: C = maxγE 21ln 1+ Sγσ(2 U) N γ is a mapping from U to R+ such that E [γ(U)] ≤P Markov channelsHow can we take ISI into account? Block fading model: within each block we have a particular ISI profile Transmit optimal scheme for that ISI profiil Problem: what happens at junction of channeels For underspread channels, coherence time is much longer than delay spread Time in a channel state is of the order of a coherence time Time during which ”echo” from previous state persists is small with respect to coherrenc time Markov channelsHow can we take ISI into account? Perform waterfilling in the following way: • decompose along a basis for all channeel in the set of possible channels • replicate channels to have channels repeaate in proportion to their frequency of occurrence • perform water-filling What if the block approach does not work? Use partial codebook approach. � � � � � � Markov channelsHow about multiple access? When the CSI is perfect at the senders and the receiver, simply consider that the channne state is the cartesian product of the channel states for all the users (note: the users must know each other’s channel) The capacity region for multiple-access channeel and the coding theorem arguments show that the arguments for the single user case extend well Take expectation over all states of all usersR1+ R2 ≤ E maxPX1|S1,S2,PX2|S1,S2((X1,X2); Y|S1,S2) R2 ≤ maxPX2|S2(X2; Y|X1,S1,S2) R1 ≤ maxPX1|S1(X1; Y|X2,S1,S2) MIT OpenCourseWarehttp://ocw.mit.edu 6.441 Information Theory Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.