Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

Identification without randomization

Rudolf Ahlswede, Ning Cai

Published Jan 1, 1999• 36 citations
Publisher

Abstract

In the theory of identification via noisy channels randomization in the encoding has a dramatic effect on the optimal code size, namely, it grows double-exponentially in the blocklength, whereas in the theory of transmission it has the familiar exponential growth. We consider now instead of the discrete memoryless channel (DMC) more robust channels such as the familiar compound (CC) and arbitrarily varying channels (AVC). They can be viewed as models for jamming situations. We make the pessimistic assumption that the jammer knows the input sequence before he acts. This forces communicators to use the maximal error concept and also makes randomization in the encoding superfluous. Now, for a DMC W by a simple observation, made by Ahlswede and Dueck (1989), in the absence of randomization the identification capacity, say C/sub NRI/(W), equals the logarithm of the number of different row-vectors in W. We generalize this to compound channels. A formidable problem arises if the DMC W is replaced by the AVC W. In fact, for 0-1-matrices only in W we are-exactly as for transmission-led to the equivalent zero-error-capacity of Shannon. But for general W the identification capacity C/sub NRI/(W) is quite different from the transmission capacity C(W). An observation is that the separation codes of Ahlswede (1989) are also relevant here. We present a lower bound on C/sub NRI/(W). It implies for instance for W={(/sub 0 1//sup 1 0/), (/sub /spl delta/ (1-/spl delta/)(1 0)/)}, /spl delta//spl isin/(0, 1/2 ) that C/sub NRI/(W)=1, which is obviously tight. It exceeds C(W), which is known to exceed 1-h(/spl delta/), where h is the binary entropy function. We observe that a separation code, with worst case average list size L~ (which we call an NRA code) can be partitioned into L~2/sup ne/ transmission codes. This gives a nonsingle-letter characterization of the capacity of AVC with maximal probability of error in terms of the capacity of codes with list decoding. We also prove that randomization in the decoding does not increase C/sub I/(W) and C/sub NRI/(W). Finally, we draw attention to related work on source coding.

DOI
10.1109/18.796419

Related papers

The AVC with noiseless feedback and maximal error probability: a capacity formula with a trichotomy

Rudolf Ahlswede, Ning Cai

Summary form only given. To use common randomness in coding is a key idea from the theory of identification. Methods and ideas of this theory are shown here to have also an impact on Shannon's theory of transmission. We determine the capacity for a classical arbitrarily varying channel (AVC) (Ahlswede, 1973) with a novel structure of the capacity formula. This channel models a robust search problem in the presence of noise (Ahlswede and Wegner 1987).

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 1997•2 citations

Deterministic Identification Over Channels With Power Constraints

Mohammad J. Salariseddigh, Uzi Pereg, Holger Boche +1 more

Identification capacity is developed without randomization at neither the encoder nor the decoder. In particular, full characterization is established for the deterministic identification (DI) capacity for the Gaussian channel and for the general discrete memoryless channel (DMC) with and without constraints. Originally, Ahlswede and Dueck established the identification capacity with local randomness given at the encoder, resulting in a double exponential number of messages. In the deterministic setup, the number of messages scales exponentially, as in Shannon’s transmission paradigm, but the achievable identification rates can be significantly higher than those of transmission. Ahlswede and Dueck further stated a capacity result for the deterministic setting of a DMC, but did not provide an explicit proof. In this paper, a detailed proof is given for both the Gaussian channel and the general DMC. The DI capacity of a Gaussian channel is infinite regardless of the noise.

arXiv:2010.04239•International Conference on Communications•Jun 1, 2021•18 citations

New directions in the theory of identification via channels

Rudolf Ahlswede, Z. Zhang

Studies two problems in the theory of identification via channels. The first problem concerns the identification via channels with noisy feedback. Whereas for Shannon's transmission problem the capacity of a discrete memoryless channel does not change with feedback, it is known that the identification capacity is affected by feedback. The authors study its dependence on the feedback channel. They prove both, a direct and a converse coding theorem. Although a gap exists between the upper and lower bounds provided by these two theorems, the known result for channels without feedback and the known result for channels with complete feedback, are both special cases of these two new theorems, because in these cases the bounds coincide. The second problem is the identification via wiretap channels. A secrecy identification capacity is defined for the wiretap channel. A "dichotomy theorem" is proved which says that the second-order secrecy identification capacity is the same as Shannon's capacity for the main channel as long as the secrecy transmission capacity of the wiretap channel is not zero, and zero otherwise. Equivalently, one can say that the identification capacity is not lowered by the presence of a wiretapper as long as 1 bit can be transmitted (or identified) correctly with arbitrarily small error probability. This is in strong contrast to the case of transmission.>

IEEE Transactions on Information Theory•Jul 1, 1995•70 citations

Identification in the presence of feedback-a discovery of new capacity formulas

Rudolf Ahlswede, G. Dueck

A study is made of the identification problem in the presence of a noiseless feedback channel, and the second-order capacity C/sub f/ (resp. C/sub F/) for deterministic (resp. randomized) encoding strategies is determined. Several important phenomena are encountered. (1) Although feedback does not increase the transmission capacity of a discrete memoryless channel (DMC), it does increase the (second-order) identification capacity; (2) noise increases C/sub f/; (3) the structure of the new capacity formulas is simpler than C.E. Shannon's (1948) familiar formula. This has the effect that proofs of converses become easier than in the authors' previous work.>

IEEE Transactions on Information Theory•Jan 1, 1989•132 citations

The arbitrarily varying channel when the jammer knows the channel input

Ning Cai, Terence Chan, Alex J. Grant

The arbitrarily varying channel can be modeled as communication in the presence of a jammer. In this paper we propose a new model: a jammer who knows the channel input, and where the transmitter and receiver share a secret random key. Shared randomness differentiates this scenario from the case where the jammer knows the message. For sufficiently large key rate, we determine the capacity of this channel (which may be strictly smaller than the case where the jammer knows only the message). We also provide an upper bound on the minimum key rate required to achieve capacity. We prove that additionally revealing the message to the jammer does not change the capacity, provided the key rate is sufficiently large. This new capacity result differs from existing results for the AVC, and in fact coincides with a well-known upper bound on the deterministic coding capacity of the AVC with maximum error. Without secret keys, our problem degenerates to deterministic coding for the AVC with maximum probability of error, a well-known hard problem. Our results demonstrate that knowledge of the channel input is better than knowledge of the message for the jammer.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•6 citations

Secure Identification Under Jamming Attacks

Holger Boche, Christian Deppe

In this survey we contrast the classical transmission theory of Shannon and the identification theory of Ahlswede and Dueck. We show that it may be useful to take a closer look at the recipient's goals. In identification theory, the recipient's goal is changed, thereby significantly increasing the channel capacity. Furthermore, there are further gains in the secure transmission of data. In this work we review the results for robust and secure discrete memoryless channels and jamming attacks. We analyze the capacity functions for various channels. It turns out that there may be discontiuity points of these functions. It is very important to use this result in practical implementations.

IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)•Jun 1, 2018•4 citations
In the theory of identification via noisy channels randomization in the encoding has a dramatic effect on the optimal code size, namely, it grows double-exponentially in the blocklength, whereas in the theory of transmission it has the familiar exponential growth. We consider now instead of the discrete memoryless channel (DMC) more robust channels such as the familiar compound (CC) and arbitrarily varying channels (AVC). They can be viewed as models for jamming situations. We make the pessimistic assumption that the jammer knows the input sequence before he acts. This forces communicators to use the maximal error concept and also makes randomization in the encoding superfluous. Now, for a DMC W by a simple observation, made by Ahlswede and Dueck (1989), in the absence of randomization the identification capacity, say C/sub NRI/(W), equals the logarithm of the number of different row-vectors in W. We generalize this to compound channels. A formidable problem arises if the DMC W is replaced by the AVC W. In fact, for 0-1-matrices only in W we are-exactly as for transmission-led to the equivalent zero-error-capacity of Shannon. But for general W the identification capacity C/sub NRI/(W) is quite different from the transmission capacity C(W). An observation is that the separation codes of Ahlswede (1989) are also relevant here. We present a lower bound on C/sub NRI/(W). It implies for instance for W={(/sub 0 1//sup 1 0/), (/sub /spl delta/ (1-/spl delta/)(1 0)/)}, /spl delta//spl isin/(0, 1/2 ) that C/sub NRI/(W)=1, which is obviously tight. It exceeds C(W), which is known to exceed 1-h(/spl delta/), where h is the binary entropy function. We observe that a separation code, with worst case average list size L~ (which we call an NRA code) can be partitioned into L~2/sup ne/ transmission codes. This gives a nonsingle-letter characterization of the capacity of AVC with maximal probability of error in terms of the capacity of codes with list decoding. We also prove that randomization in the decoding does not increase C/sub I/(W) and C/sub NRI/(W). Finally, we draw attention to related work on source coding.
Identification capacity is developed without randomization at neither the encoder nor the decoder. In particular, full characterization is established for the deterministic identification (DI) capacity for the Gaussian channel and for the general discrete memoryless channel (DMC) with and without constraints. Originally, Ahlswede and Dueck established the identification capacity with local randomness given at the encoder, resulting in a double exponential number of messages. In the deterministic setup, the number of messages scales exponentially, as in Shannon’s transmission paradigm, but the achievable identification rates can be significantly higher than those of transmission. Ahlswede and Dueck further stated a capacity result for the deterministic setting of a DMC, but did not provide an explicit proof. In this paper, a detailed proof is given for both the Gaussian channel and the general DMC. The DI capacity of a Gaussian channel is infinite regardless of the noise.
Studies two problems in the theory of identification via channels. The first problem concerns the identification via channels with noisy feedback. Whereas for Shannon's transmission problem the capacity of a discrete memoryless channel does not change with feedback, it is known that the identification capacity is affected by feedback. The authors study its dependence on the feedback channel. They prove both, a direct and a converse coding theorem. Although a gap exists between the upper and lower bounds provided by these two theorems, the known result for channels without feedback and the known result for channels with complete feedback, are both special cases of these two new theorems, because in these cases the bounds coincide. The second problem is the identification via wiretap channels. A secrecy identification capacity is defined for the wiretap channel. A "dichotomy theorem" is proved which says that the second-order secrecy identification capacity is the same as Shannon's capacity for the main channel as long as the secrecy transmission capacity of the wiretap channel is not zero, and zero otherwise. Equivalently, one can say that the identification capacity is not lowered by the presence of a wiretapper as long as 1 bit can be transmitted (or identified) correctly with arbitrarily small error probability. This is in strong contrast to the case of transmission.>
A study is made of the identification problem in the presence of a noiseless feedback channel, and the second-order capacity C/sub f/ (resp. C/sub F/) for deterministic (resp. randomized) encoding strategies is determined. Several important phenomena are encountered. (1) Although feedback does not increase the transmission capacity of a discrete memoryless channel (DMC), it does increase the (second-order) identification capacity; (2) noise increases C/sub f/; (3) the structure of the new capacity formulas is simpler than C.E. Shannon's (1948) familiar formula. This has the effect that proofs of converses become easier than in the authors' previous work.>
The arbitrarily varying channel can be modeled as communication in the presence of a jammer. In this paper we propose a new model: a jammer who knows the channel input, and where the transmitter and receiver share a secret random key. Shared randomness differentiates this scenario from the case where the jammer knows the message. For sufficiently large key rate, we determine the capacity of this channel (which may be strictly smaller than the case where the jammer knows only the message). We also provide an upper bound on the minimum key rate required to achieve capacity. We prove that additionally revealing the message to the jammer does not change the capacity, provided the key rate is sufficiently large. This new capacity result differs from existing results for the AVC, and in fact coincides with a well-known upper bound on the deterministic coding capacity of the AVC with maximum error. Without secret keys, our problem degenerates to deterministic coding for the AVC with maximum probability of error, a well-known hard problem. Our results demonstrate that knowledge of the channel input is better than knowledge of the message for the jammer.
In this survey we contrast the classical transmission theory of Shannon and the identification theory of Ahlswede and Dueck. We show that it may be useful to take a closer look at the recipient's goals. In identification theory, the recipient's goal is changed, thereby significantly increasing the channel capacity. Furthermore, there are further gains in the secure transmission of data. In this work we review the results for robust and secure discrete memoryless channels and jamming attacks. We analyze the capacity functions for various channels. It turns out that there may be discontiuity points of these functions. It is very important to use this result in practical implementations.