3150 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL.
3150IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 7, JULY 2008Capacity of the Trapdoor Channel With FeedbackHaim Permuter, Student Member, IEEE, Paul Cuff, Student Member, IEEE, Benjamin Van Roy, Member, IEEE, andTsachy Weissman, Senior Member, IEEEAbstract—We establish that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio and provide asimple communication scheme that achieves capacity. As part ofthe analysis, we formulate a class of dynamic programs that characterize capacities of unifilar finite-state channels. The trapdoorchannel is an instance that admits a simple closed-form solution.Index Terms—Bellman equation, chemical channel, constrainedcoding, directed information, feedback capacity, golden-ratio, infinite-horizon dynamic program, trapdoor channel, value iteration.I. INTRODUCTIONAVID Blackwell, who has done fundamental work bothin information theory and in stochastic dynamic programming, introduced the trapdoor channel in 1961 [1] as a “simpletwo-state channel.” The channel is depicted in Fig. 1, and adetailed discussion of this channel appears in an informationtheory book by Ash [2], where indeed the channel is shown onthe cover of the book.The channel behaves as follows. Balls labeled “ ” or “ ” areused to communicate through the channel. The channel startswith a ball already in it. To use the channel, a ball is insertedinto the channel by the transmitter, and the receiver receives oneof the two balls in the channel with equal probability. The ballthat does not exit the channel remains inside for the next channeluse.Another appropriate name for this channel is chemicalchannel. This name suggests a physical system in which theconcentrations of chemicals are used to communicate, such asmight be the case in some cellular biological systems as shownby Berger [3]. The transmitter adds molecules to the channel,and the receiver samples molecules randomly from the channel.The trapdoor channel is the most basic realization of this typeof channel; it has only two types of molecules, and there areonly three possible concentrations,, or, equivalently,only one molecule remains in the channel between uses.Although the trapdoor channel is very simple to describe, itscapacity has been an open problem for over 45 years [1]. TheDManuscript received October 8, 2006; revised January 25, 2008. This workwas supported by the National Science Foundation (NSF) under Grants CCR0311633, CCF-0515303, IIS-0428868, and the NSF CAREER Grant. The material in this paper was presented in part at the 44th Annual Allerton Conferenceon Communications, Control, and Computers, Monticello, IL, September 2006,and the IEEE International Symposium on Information Theory, Nice, France,June 2007H. Permuter, P. Cuff, and B. Van Roy are with the Department of Electrical Engineering, Stanford University, Stanford, CA 94305 USA (e-mail:haim1@stanford.edul; pcuff@stanford.edu; bvr@stanford.edu).T. Weissman is with the Department of Electrical Engineering, Technion–Israel Institute of Technology, Technion City, Haifa 3200, Israel He is also withthe Department of Electrical Engineering, Stanford University, Stanford, CA94305 USA. (e-mail: tsachy@stanford.edu).Communicated by Y. Steinberg, Associate Editor for Shannon Theory.Digital Object Identifier 10.1109/TIT.2008.924681Fig. 1. The trapdoor (chemical) channel.zero-error capacity was found by Ahlswede et al. [4], [5] to be0.5 bits per channel use. More recently, Kobayashi and Morita[6] derived a recursion for the conditional probabilities of outputsequences of length given the input sequences and used itto show that the capacity of this channel is strictly larger than0.5 bits. Ahlswede and Kaspi [4] considered two modes of thechannel called the permuting jammer channel and the permutingrelay channel. In the first mode, there is a jammer in the channelthat attempts to frustrate the message sender by selective releaseof balls in the channel. In the second mode, where the sender isin the channel, a helper supplies balls of a fixed sequence at theinput, and the sender is restricted to permuting this sequence.The helper collaborates with the message sender in the channelto increase his ability to transmit distinct messages to the receiver. Ahlswede and Kaspi [4] gave answers for specific casesof both situations, and Kobayashi [7] established the answer tothe general permuting relay channel. Additional results for specific cases of the permuting jammer channel can be found in [8],[9].In this paper, we consider the trapdoor channel with feedback. We derive the feedback capacity of the trapdoor channelby solving an equivalent dynamic programming problem. Ourwork consists of two main steps. The first step is formulating thefeedback capacity of the trapdoor channel as an infinite-horizondynamic program, and the second step is finding explicitly theexact solution of that program.Formulating the feedback capacity problem as a dynamic program appeared in Tatikonda’s thesis [10] and in work by Yang,Kavčić, and Tatikonda [11] [12], Chen and Berger [13], and recently in a work by Tatikonda and Mitter [14]. Yang et al. haveshown in [11] that if a channel has a one-to-one mapping between the input and the state, it is possible to formulate feedback capacity as a dynamic programming problem and to findan approximate solution by using the value iteration algorithm[15]. The authors of [11] have also formulated in [12] the feedback capacity of a stationary additive Gaussian-noise channelwith a rational noise power spectrum of finite order1 as a dynamic program. Chen and Berger [13] showed that if the stateof the channel is a function of the output, then it is possible toformulate the feedback capacity as a dynamic program with afinite number of states.1In subsequent work, Kim [16], [17] showed that the optimal input distribution for this family of channels is stationary, which was a long-standing conjecture.0018-9448/ 25.00 2008 IEEE
PERMUTER et al.: CAPACITY OF THE TRAPDOOR CHANNEL WITH FEEDBACK3151Fig. 2. Unifilar FSC with feedback.TABLE ITHE PROBABILITY OF THE OUTPUT y GIVEN THE INPUT xAND THE STATE sunifilar channels as discussed by Ziv [19]. An FSC is a channelthat, for each time index, has one of a finite number of possible, and has the property thatstates,. A unifilar FSC also has the property that the:state is deterministic givenDefinition 1: An FSC is called a unifilar FSC if there existsa time-invariant functionsuch that the state evolves according to the equationOur work provides the dynamic programming formulation and a computational algorithm for finding the feedbackcapacity of a family of channels called unifilar finite statechannels (FSCs), which include the channels considered in[11], [13]. We use value iteration [15] to find an approximatesolution and to generate a conjecture for the exact solution,and the Bellman equation [18] to verify the optimality of theconjectured solution. As a result, we are able to show that the, wherefeedback capacity of the trapdoor channel isis the golden ratio,. In addition, we present a simpleencoding/decoding scheme that achieves this capacity.The remainder of the paper is organized as follows. Section II defines the channel setting and the notation throughoutthe paper. Section III states the main results of the paper.Section IV presents the capacity of a unifilar FSC in termsof directed information. Section V introduces the dynamicprogramming framework and shows that the feedback capacityof the unifilar FSC can be characterized as the optimal averagereward of a dynamic program. Section VI shows an explicitsolution for the capacity of the trapdoor channel by using thedynamic programming formulation. Section VII discusses asimple communication scheme that achieves the capacity of thetrapdoor channel with feedback, and Section VIII concludesthis work.II. CHANNEL MODELS AND PRELIMINARIESWe use subscripts and superscripts to denote vectors in theandforfollowing ways:. Moreover, we use lower case to denote sample values,upper case to denote random variables, calligraphic letterto denote the alphabet, andto denote the cardinality of thealphabet. The probability distributions are denoted by whenthe arguments specify the distribution, e.g.,. In this paper, we consider only channels for which, and the output, denotedthe input, denoted by, are from finite alphabets,and , respecbytively. In addition, we consider only the family of FSC known as(1)We also define a connected FSC as follows.Definition 2: We say that an FSC is connected if for any statethere exists an integerand an input distribution of thethat may depend on , such that the probformability that the channel reaches from any starting state , intime steps, is positive. That isless than(2)We assume a communication setting that includes feedbackas shown in Fig. 2. At time , the transmitter (encoder) knowsand the feedback samples. The output ofthe messageand is a function of thethe encoder at time is denoted bymessage and the feedback. The channel is a unifilar FSC andthe output of the channel enters the decoder (receiver). Theencoder receives the feedback sample with one unit delay.A. Trapdoor Channel Is a Unifilar FSCThe state of the trapdoor channel, which is described in theIntroduction and shown in Fig. 1, is the ball, or , that is in thechannel before the transmitter transmits a new ball. Letbe the ball that is transmitted at time , andbe the state of the channel when ball is transmitted. The probgiven the inputand the state of theability of the outputis shown in Table I.channelThe trapdoor channel is a unifilar FSC. It has the property that, thethe next state is a deterministic function of the state,input , and the output . For a feasible tuple,the next state is given by the equation(3)wheredenotes the binary XOR operation.
3152IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 7, JULY 2008For any finite-state channel with perfect feedback, as shownin Fig. 2, the capacity was shown in [21], [22] to be bounded asFig. 3. The trapdoor channel as a permuting channel. Going from left to right,there is a probability of one half that two adjacent bits switch places.(6)B. Trapdoor Channel Is a Permuting ChannelIt is interesting to note, although not consequential in thispaper, that the trapdoor channel is a permuting channel [20],where the output is a permutation of the input (Fig. 3). At eachtime , a new bit is added to the sequence and the channelswitches the new bit with the previous one in the sequence with.probabilityThe termis the directed information2 definedoriginally by Massey in [29] as(7)The initial state is denoted as andis the causallyconditional distribution defined in [21], [26] as(8)III. MAIN RESULTS The capacity of the trapdoor channel with feedback is(4)Furthermore, there exists a simple capacity achievingscheme which will be presented in Section VII. The problem of finding the capacity of a connected unifilarchannel (Fig. 2) can be formulated as an average-rewarddynamic program, where the state of the dynamic program is the probability mass function over the states conditioned on prior outputs, and the action is the stochastic. By finding a solution to the average-rematrixward Bellman equation, we find the exact capacity of thechannel. As a byproduct of our analysis, we also derive a closedform solution to an infinite horizon average-reward dynamic program with a continuous state-space.IV. THE CAPACITY FORMULA FOR A UNIFILAR CHANNELWITH FEEDBACKThe main goal of this section is to prove the following theorem, which allows us to formulate the problem as a dynamicprogram.The directed information in (6) is under the distribution ofwhich is uniquely determined by the causal condiand by the channel.tioningIn our communication setting, we are assuming that the initial state is known both to the decoder and to the encoder. Thisassumption allows the encoder to know the state of the channelat any time because is a deterministic function of the previous state, input and output. In order to take into account thisassumption, we use a trick of allowing a fictitious time epochbefore the first actual use of the channel in which the input doesnot influence the output nor the state of channel, and the onlything that happens is that the output equals and is fed back tothe encoder such that at timeboth the encoder and the debe the fictitious time beforecoder know the state . Let,starting the use of the channel. According to the trick,can be chosen arbitrarily because it does notand the inputhave any influence whatsoever. For this scenario, the directedinformation term in (6) becomes(9)The input distribution becomes(10)whereis defined asTheorem 1: The feedback capacity of a connected unifilarFSC when initial state is known at the encoder and decodercan be expressed asTherefore, the capacity of a unifilar channel with feedback forwhich the initial state, , is known both at the encoder and thedecoder is bounded as(5)wheresuch that.denotes the set of all distributionsforTheorem 1 is a direct consequence of Theorem 3 and (26) inLemma 4, which are proved in this section.(11)2In addition to feedback capacity, directed information has recently been usedin rate distortion [23], [24], [25], network capacity [26], [27] and computationalbiology [28].
PERMUTER et al.: CAPACITY OF THE TRAPDOOR CHANNEL WITH FEEDBACKLemma 2: If the finite-state channel is connected, then for anyand any , there exists aninput distributionsuch thatinput distribution(12). Thewhere is a constant that does not depend ontermdenotes the directed information in, whereisduced by the input distributiondethe initial state. Similarly, the termnotes the directed information induced by the input distributionwhere is the initial state.as follows. Use an inputProof: Constructdistribution, which has a positive probability of reaching intime epochs, until the time that the channel first reaches . Suchan input distribution exists because the channel is connected.byDenote the first time that the state of the channel equals. After time , operate exactly aswould (had time startedthen). Namely, for3153follows from the triangle inequality.follows from the fact that in the first absolute value,terms cancel and therefore only terms remain where. In theeach one is bounded byterms, alsosecond absolute value there arebounded by.The proof is completed by noting thatandare upper-bounded, respectively, byand, whereGeometric, and is the minimum probability ofreaching in less than steps from any state. Becausehas a geometric distribution,the random variableandare finite and, consequently, so areand.Theorem 3: The feedback capacity of a connected unifilarFSC, when the initial state is known at the encoder and decoder,is given by(14)Proof: The proof of the theorem contains four main equalities, which are proven separately.Then(15)(16)(17)(18)Proof of Equality (15) and (16): As a result of Lemma 2(19)(20)(13)wherefollows from the triangle inequality and Lemma 3 in[21], which claims that for any arbitrary random variables, the inequalityalways holds.follows from using the special structure of.wherefollows from the definition of conditional entropy.follows from the exchange between the summation andthe maximization. The exchange is possible because maximization is over causally conditional distributions thatdepend on .follows from Lemma 2.follows from the observation that the distributionthat achieves the maximum in(19) and in (20) is the same:. This observation allows us to exchange the order of the minimum andthe maximum.
3154Equations (19) and (20) can be repeated also with, and hence we getstead ofIEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 7, JULY 2008in-(21)The next lemma shows that it is possible to switch betweenthe limit and the maximization in the capacity formula. Thisis necessary for formulating the problem, as we do in the nextsection, as an average-reward dynamic program.Lemma 4: For any FSC, the following equality holds:By using (20) and (21), we get that the upper bound and thelower bound in (11) are equal, and therefore (15) and (16) hold.Proof of Equality (17): Using the property that the nextstate of the channel is a deterministic function of the input,output, and current state, we get(25)And, in particular, for a connected unifilar FSC(26)(22)Equalityis due to the fact thatis a deterministic. Equalityis due to thefunction of the tuple. Byfact thatcombining (16) and (22), we get (17).Proof of Equality (18): It will suffice to proveby induction that if we have two input distributionsandthat induce the same distributions, thenthe distributionsare equal under bothinputs. First, let us verify the equality forbecause, asOn the left-hand side of the equations appearsshown in [22], the limit exists due to the super-additivity property of the sequence.Proof: We prove (25), which holds for any FSC. For thecase of unifilar channel, the left-hand side of (25) is proven tobe equal to the left-hand side of (26) in (15)–(18). By the samearguments as in (15)–(18), the right-hand side of (25) and (26)are also equal.Define(27)In order to prove that the equality holds, we will use two properties ofthat were proved in [22, Theorem 13].is a super additive sequence,The first property is thatnamely, for any two positive integers and that sums to(28)The second property, which is a result of the first, is that(23)Sinceandare not influenced by the inputis equal for both input distribudistribution, and sinceis also equal for both input distributions.tions, thenis equal under both inputNow, we assume thatdistributions, and we need to prove thatis also,equal under both input distributions. The termwhich can be written as(24)First we notice that ifis equal for both cases,thenis necessarily equal for both cases be,cause is a deterministic function of the tuple.and therefore both input distributions induce the sameis the same under both input disThe distributiontributions by assumption, anddoes not dependon the input distribution.(29)Now, consider(30)
PERMUTER et al.: CAPACITY OF THE TRAPDOOR CHANNEL WITH FEEDBACKThe limit of the left-hand side of the equation in the lemmathere existssuch that for allimplies that,Let us choose, and letbe the inputdistribution that attains the maximum. Let us construct3155. Note that given theare generated according toand a policy, one can computehistoryand actions. A policypast statesis referred to as stationary if there is a functionsuch thatfor all and . Withsome abuse of terminology, we will sometimes refer to such afunction itself as a stationary policy.We consider an objective of maximizing average reward,. The averagegiven a bounded reward functionreward for a policy is defined by(31)Then, we get(32)whereis the directed information inducedby the inputand the channel. The left inequalityis only one possible input disholds because. The right inequalitytribution among alltransformsholds because the special structure ofthe whole expression of normalized directed information into anaverage of infinite sums of terms that each term is directed information between blocks of length . Because for each block theinequality holds, then it holds also for the average of the blocks.The inequality may not hold on the last block, but because weaverage over an increasing number of blocks, its influence diminishes.where the subscriptpolicybyindicates that actions are generated by the. The optimal average reward is definedB. The Bellman EquationAn alternative characterization of the optimal average rewardis offered by the Bellman equation. This equation offers a mechanism for verifying that a given level of average reward is optimal. It also leads to a characterization of optimal policies.The following result, which we will later use, encapsulates theBellman equation and its relation to the optimal average rewardand optimal policies.Theorem 5: Ifsatisfyand a bounded functionV. FEEDBACK CAPACITY AND DYNAMIC PRO
3150 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 7, JULY 2008 Capacity of the Trapdoor Channel With Feedback Haim Permuter, Student Member, IEEE, Paul Cuff, Student Member, IEEE, Benjamin Van Roy, Member, IEEE, and Tsachy Weissman, Senior Member, IEEE Abstract—We establish that the feedback capacity of the trap
IEEE 3 Park Avenue New York, NY 10016-5997 USA 28 December 2012 IEEE Power and Energy Society IEEE Std 81 -2012 (Revision of IEEE Std 81-1983) Authorized licensed use limited to: Australian National University. Downloaded on July 27,2018 at 14:57:43 UTC from IEEE Xplore. Restrictions apply.File Size: 2MBPage Count: 86Explore furtherIEEE 81-2012 - IEEE Guide for Measuring Earth Resistivity .standards.ieee.org81-2012 - IEEE Guide for Measuring Earth Resistivity .ieeexplore.ieee.orgAn Overview Of The IEEE Standard 81 Fall-Of-Potential .www.agiusa.com(PDF) IEEE Std 80-2000 IEEE Guide for Safety in AC .www.academia.eduTesting and Evaluation of Grounding . - IEEE Web Hostingwww.ewh.ieee.orgRecommended to you b
Signal Processing, IEEE Transactions on IEEE Trans. Signal Process. IEEE Trans. Acoust., Speech, Signal Process.*(1975-1990) IEEE Trans. Audio Electroacoust.* (until 1974) Smart Grid, IEEE Transactions on IEEE Trans. Smart Grid Software Engineering, IEEE Transactions on IEEE Trans. Softw. Eng.
Einheit aus Armlehne und Sitz, Linde Load Control, innova-tive Abkoppelung der Antriebsachse und die Doppelpedal- Steuerung bieten beste Voraussetzungen für schnelles, ent-spanntes Arbeiten. . 2800 3150 3150 2800 3150 3150 4.5 Höhe Hubgerüst ausgefahren h4 (mm) 3401 3751 3751 3401 3751 3751 4.7 Höhe über Schutzdach (Kabine) h6 (mm) 1970 .
kV 800 A 1600 A 2500 A 3150 A 36 52 300 N 300 N 375 N 375 N 600 N 600 N 945 N 945 N 2.3 Cantilever test load Ur Ir kV 800 A 1600 A 2500 A 3150 A 36 52 1000 N 1000 N 1250 N 1250 N 2000 N 2000 N 3150 N 3150 N . File : ISOLATORI DISTRIBUZIONE UNCONTROLLED COPY Rev. 4
IEEE TRANSACTIONS ON IMAGE PROCESSING, TO APPEAR 1 Quality-Aware Images Zhou Wang, Member, IEEE, Guixing Wu, Student Member, IEEE, Hamid R. Sheikh, Member, IEEE, Eero P. Simoncelli, Senior Member, IEEE, En-Hui Yang, Senior Member, IEEE, and Alan C. Bovik, Fellow, IEEE Abstract— We propose the concept of quality-aware image, in which certain extracted features of the original (high-
IEEE Robotics and Automation Society IEEE Signal Processing Society IEEE Society on Social Implications of Technology IEEE Solid-State Circuits Society IEEE Systems, Man, and Cybernetics Society . IEEE Communications Standards Magazine IEEE Journal of Electromagnetics, RF and Microwaves in Medicine and Biology IEEE Transactions on Emerging .
Standards IEEE 802.1D-2004 for Spanning Tree Protocol IEEE 802.1p for Class of Service IEEE 802.1Q for VLAN Tagging IEEE 802.1s for Multiple Spanning Tree Protocol IEEE 802.1w for Rapid Spanning Tree Protocol IEEE 802.1X for authentication IEEE 802.3 for 10BaseT IEEE 802.3ab for 1000BaseT(X) IEEE 802.3ad for Port Trunk with LACP IEEE 802.3u for .
time test takers of the American Board of Radiology radiation biology (left), physics (center), and clinical (right) qualifying examinations from 2005-2016 [2017 unavailable]. Reported average pass rates from 2018 are plotted as outliers (for radiation biology and physics) and labeled. Two-sided P-values (with distribution of normality confirmed by the Shapiro test) demonstrate that the .
