6.441-14 Feedback capacity

LECTURE 14Last time:Fano’s Lemma revisited • Fano’s inequality for codewords • Converse to the coding theorem • Lecture outlineFeedback channel: setting up the prob₭ lem Perfect feedback • Feedback capacity • Reading: Sct. 8.12. Feedback channelWhat types of channels do we think if as being feedback channels? Byzantine general problem Error in forward and feedback channel But does that mean that we cannot transmmi without error? Perfect feedbackas good as we are going to get in terms of feedback Feedback code: (2nR, n) is a sequence of mappings xi(M,Y i−1) where each xi is a function of the message M and the previous received signals Question: why only the past received signaals � Feedback capacityThe probability of error is: Pe = P ( �= M)M where g(Yn)= �M CF B is the supremum of all achievable rates Clearly CF B ≥ C How about the reverse direction? Let us reconsider the hapless intra-army messengers. But do we suffer in rate?Feedback capacityLet us try to show that CF B ≤ CTry Fano’s inequality for code wordsHowever, the channel is no longer a DMCFor DMC, we used:Assume that the message M is drawn withuniform PMF from {1, 2,..., 2nR}Then nR = H(M)AlsoH(M)= H(MY )+ I(M; Y )|= H(M|Y )+ H(Y ) − H(Y |M) = H(M|Y )+ H(Y ) − H(Y |X) = H(MY )+ I(X; Y )|≤ 1+ PenR + nC no longer applicable!Feedback capacityWe still have nR = H(M) Need to relate I(M; Y ) to I(X; Y ), which will give then a relation to C as before n� I(M; Yn) Yi−1,M)H(Yn) −H(Y [i]=|=1in�Yi−1, M, X[i])H(Yn) −H(Y [i]=|=1in�n� H(Yn) − H(Y [i]X[i])=|i=1n� i=1 H(Y [i]) −H(Y [i]X[i])|≤==1in�I(X[i]; Y [i])i=1 ≤ nC Feedback capacity Thus, we still have that nR = H(M) ≤ 1+ PenR + nC which as for the DMC implies R ≤ n 1+ PeR + C so R ≤ C Hence C = CF B FEEDBACK DOES NOT HELP!DiscussionDMC does not benefit from feedback What other things might happen: -There is an unknown part of the channel -There is memory in the channel 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.