Identification and zero-error codes
Identification and zero-error codes
复制标题
识别码和零错误码
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Bracher
中科院分区：
文献类型：
--
作者：
A. Bracher
本文从信息论的角度研究了两个通信问题：广播信道的身份识别和带反馈链路的Gelfand-Pinsker信道的零错误传输。对于每个问题，都建立了容量；它表征了可以传递的最大消息数量。证明的关键是新的身份识别和零误码。在经由单用户信道的标识中，发送方在该信道上传送来自有限集合的标识消息，并且对于每个可能的消息，存在集中在该消息上的接收方。每个接收方都观察到通道输出，并且必须从中猜测它所关注的消息是否已发送。因此，它面临着带有两个假设的假设检验问题。不严格地说，如果对于每一对可能的发送消息和接收方，接收方以高概率正确地猜测，则标识方案被称为可靠的。也就是说，如果发送的消息等于接收方关注的消息，则接收方大概率地猜测其关注的消息被发送，否则其大概率地猜测其关注的消息未被发送。可识别消息的数目在信道使用的数目中是双指数的，并且识别率因此被定义为由信道使用的数目归一化的识别消息的数目的重对数。识别能力是可达到的识别率的最高值。只有在允许编码处的随机化的情况下才能实现：如果仅允许确定性编码器，即从标识消息集到信道输入集的确定性映射，则可识别消息的数量仅在信道使用的数量中呈指数增长。
This thesis studies two communication problems from an informationtheoretic perspective: identification via the broadcast channel and zeroerror 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.