HartungGorre Verlag
Inh.: Dr.
Renate Gorre D78465
Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartunggorre.de

S

ETH Series in Information Theory and its Applications,
Vol. 8
edited by Amos Lapidoth
Annina Bracher
Identification and
ZeroError Codes
1st edition
2016. XXII, 242 pages, € 64,00.
ISBN
9783866285743
Abstract
This
thesis studies two communication problems from an informationtheoretic perspective:
identification via the broadcast channel and zeroerror transmission over the
GelfandPinsker 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 zeroerror codes.
In
identification via the singleuser 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 hypothesistesting 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 singleuser
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 ratepairs 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 averageerror 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 todate unknown. Key to the proof is a new code construction for
identification via the singleuser channel. Extensions to the broadcast channel
with onesided feedback and the threereceiver 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
GelfandPinsker channel is a statedependent singleuser 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 errorfree a message from a finite set is considered. The number of
messages that can be conveyed errorfree is exponential in the number of
channel uses, and the rate of a zeroerror code is thus defined as the
logarithm of the number of messages normalized by the number of channel uses.
The zeroerror capacity is the supremum of achievable rates. The present thesis
fully characterizes the GelfandPinsker channels whose zeroerror feedback
capacity is positive and establishes a formula for the capacity when it is
positive. Together, these results provide a singleletter characterization of
the GelfandPinsker channel’s zeroerror feedback capacity. The capacity is
shown to exhibit phenomena that are not present on the stateless channel: it
can be positive even if the zeroerror capacity is zero in the absence of
feedback; the errorfree 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 GelfandPinsker channel’s zeroerror feedback capacity, new zeroerror
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; averageerror
criterion; zeroerror capacity; feedback; state information; GelfandPinsker
channel; Shannon strategies; zeroerror 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
corporateresearch 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 HartungGorre
Verlag
Direkt bestellen bei / to order directly from:
HartungGorre Verlag / D78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227 Telefax: +49 (0) 7533
97228
http://www.hartunggorre.de eMail: verlag@hartunggorre.de