Hartung-Gorre Verlag Inh.: Dr. Renate Gorre D-78465 Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de

S

ETH Series in Information Theory and its Applications, Vol. 8
edited by Amos Lapidoth

Annina Bracher

Identification and Zero-Error Codes

1st edition 2016. XXII, 242 pages, € 64,00.

ISBN 978-3-86628-574-3

Abstract

This thesis studies two communication problems from an information-theoretic perspective: identification via the broadcast channel and zero-error transmission over the Gelfand-Pinsker channel with a feedback link. For each problem the capacity is established; it characterizes the maximum number of messages that can be conveyed. Key to the proofs are new identification and zero-error codes.

In identification via the single-user channel the sender conveys an identification message from a finite set over the channel, and for every possible message there is a receiving party focused on that message. Each receiving party observes the channel output and must guess from it whether or not the message it is focused on was sent. It thus faces a hypothesis-testing problem with two hypotheses. Loosely speaking, an identification scheme is said to be reliable if, for every possible pair of transmitted message and receiving party, the receiving party guesses correctly with high probability. That is, if the transmitted message equals the message that the receiving party is focused on, then the receiving party guesses with high probability that the message it is focused on was sent, and otherwise it guesses with high probability that the message it is focused on was not sent. The number of identifiable messages is double exponential in the number of channel uses, and the identification rate is thus defined as the iterated logarithm of the number of identification messages normalized by the number of channel uses. The identification capacity is the supremum of achievable identification rates. It is achievable only if randomization at the encoder is allowed: if only deterministic encoders, i.e., deterministic mappings from the set of identification messages to the set of channel inputs, are allowed, then the number of identifiable messages grows only exponentially in the number of channel uses.

This thesis studies identification via the broadcast channel. Unlike the single-user channel, the broadcast channel has two receiving terminals; and the sender conveys two identification messages, one to each receiving terminal. The channel output at each receiving terminal is observed by different parties, each of which is focused — among all the possible identification messages intended for that terminal — on a different message. Each receiving party must guess from its observation whether or not the message it is focused on was sent. The identification capacity region of the broadcast channel is shown to be the set of rate-pairs for which, for some distribution on the channel input, each receiver’s identification rate does not exceed the mutual information between the channel input and the channel output that it observes. Moreover, the capacity region’s interior is achieved by codes with deterministic encoders. The results are obtained under the average-error criterion, which requires that the message intended for each receiving terminal be identified reliably whenever the message intended for the other receiving terminal is drawn at random. They hold also for channels whose transmission capacity region is to-date unknown. Key to the proof is a new code construction for identification via the single-user channel. Extensions to the broadcast channel with one-sided feedback and the three-receiver broadcast channel are also discussed: inner bounds on their identification capacity regions are obtained, and those are shown to be in some cases tight.

The Gelfand-Pinsker channel is a state-dependent single-user channel whose state is revealed acausally to the sender. On this channel the problem where the sender observes the channel output via a feedback link and wishes to convey to the receiver error-free a message from a finite set is considered. The number of messages that can be conveyed error-free is exponential in the number of channel uses, and the rate of a zero-error code is thus defined as the logarithm of the number of messages normalized by the number of channel uses. The zero-error capacity is the supremum of achievable rates. The present thesis fully characterizes the Gelfand-Pinsker channels whose zero-error feedback capacity is positive and establishes a formula for the capacity when it is positive. Together, these results provide a single-letter characterization of the Gelfand-Pinsker channel’s zero-error feedback capacity. The capacity is shown to exhibit phenomena that are not present on the state-less channel: it can be positive even if the zero-error capacity is zero in the absence of feedback; the error-free transmission of a single bit may require more than one channel use; and Shannons´s sequential coding technique cannot be applied naively. These phenomena do not occur when the state is revealed to the transmitter causally, a case that is solved here using Shannon strategies. To derive the Gelfand-Pinsker channel’s zero-error feedback capacity, new zero-error coding schemes are introduced, which — unlike Shannon’s sequential coding technique — allow the encoder to take advantage of the acausal state information. Cost constraints on the channel inputs or channel states are also discussed, as is the scenario where — in addition to the message — also the state sequence must be recovered.

Keywords: identification via channels; identification code; broadcast channel; capacity region; average-error criterion; zero-error capacity; feedback; state information; Gelfand-Pinsker channel; Shannon strategies; zero-error code; conveying the state; cost constraint.

About the Author

Annina Bracher was born in Bern, Switzerland, on March 30, 1989. She attended Kantonsschule Rychenberg in Winterthur, from which she graduated in 2007 (as the best student of the year) with a bilingual Matura (German and English) in classical languages (Latin and English). Annina received the BSc and MSc degrees in electrical engineering and information technology (both with distinction) from ETH Zurich in 2010 and 2012. During her master’s studies, she worked from September to December 2011 in Bangalore as a corporate-research intern at ABB. In the academic year 2012/2013 she pursued graduate studies at Princeton University, from which she received the MSc degree in electrical engineering in 2014. In 2013 she joined the Signal and Information Processing Laboratory at ETH Zurich as a PhD student and teaching assistant.

Annina was awarded an Excellence Scholarship and Opportunity Award for her master’s studies at ETH Zurich, an ETH Medal “for an excellent master’s thesis,” the Willi Studer Prize for the “best student of the year 2012/2013 in electrical engineering and information technology,” and a Francis Robbins Upton Fellowship in Engineering for her graduate studies at Princeton University. She is a member of the Swiss Study Foundation.

Reihe "ETH Series in Information Theory and its Applications" im Hartung-Gorre Verlag

Direkt bestellen bei / to order directly from:

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de