BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Amos Lapidoth contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Two maximization problems of Rényi entropy rate are investigated: the maximization over all stochastic processes whose marginals satisfy a linear constraint, and the Burg-like maximization over all stochastic processes whose autocovariance function begins with some given values. The solutions are related to the solutions to the analogous maximization problems of Shannon entropy rate.
A task is randomly drawn from a finite set of tasks and is described using a fixed number of bits. All the tasks that share its description must be performed. Upper and lower bounds on the minimum $ρ$-th moment of the number of performed tasks are derived. The key is an analog of the Kraft Inequality for partitions of finite sets. When a sequence of tasks is produced by a source of a given Rényi entropy rate of order $1/(1+ρ)$ and $n$ tasks are jointly described using $nR$ bits, it is shown that for $R$ larger than the Rényi entropy rate, the $ρ$-th moment of the ratio of performed tasks to $n$ can be driven to one as $n$ tends to infinity, and that for $R$ less than the Rényi entropy rate it tends to infinity. This generalizes a recent result for IID sources by the same authors. A mismatched version of the direct part is also considered, where the code is designed according to the wrong law. The penalty incurred by the mismatch can be expressed in terms of a divergence measure that was shown by Sundaresan to play a similar role in the Massey-Arikan guessing problem.
We study the secrecy of a distributed storage system for passwords. The encoder, Alice, observes a length-n password and describes it using two hints, which she then stores in different locations. The legitimate receiver, Bob, observes both hints. The eavesdropper, Eve, sees only one of the hints; Alice cannot control which. We characterize the largest normalized (by n) exponent that we can guarantee for the number of guesses it takes Eve to guess the password subject to the constraint that either the number of guesses it takes Bob to guess the password or the size of the list that Bob must form to guarantee that it contain the password approach 1 as n tends to infinity.
A task is randomly drawn from a finite set of tasks and is described using a fixed number of bits. All the tasks that share its description must be performed. Upper and lower bounds on the minimum $ρ$-th moment of the number of performed tasks are derived. The case where a sequence of tasks is produced by a source and $n$ tasks are jointly described using $nR$ bits is considered. If $R$ is larger than the Rényi entropy rate of the source of order $1/(1+ρ)$ (provided it exists), then the $ρ$-th moment of the ratio of performed tasks to $n$ can be driven to one as $n$ tends to infinity. If $R$ is smaller than the Rényi entropy rate, this moment tends to infinity. The results are generalized to account for the presence of side-information. In this more general setting, the key quantity is a conditional version of Rényi entropy that was introduced by Arimoto. For IID sources two additional extensions are solved, one of a rate-distortion flavor and the other where different tasks may have different nonnegative costs. Finally, a divergence that was identified by Sundaresan as a mismatch penalty in the Massey-Arikan guessing problem is shown to play a similar role here.
The listsize capacity of a discrete memoryless channel is the largest transmission rate for which the expectation---or, more generally, the $ρ$-th moment---of the number of messages that could have produced the output of the channel approaches one as the blocklength tends to infinity. We show that for channels with feedback this rate is upper-bounded by the maximum of Gallager's $E_0$ function divided by $ρ$, and that equality holds when the zero-error capacity of the channel is positive. To establish this inequality we prove that feedback does not increase the cutoff rate. Relationships to other notions of channel capacity are explored.
Ahlswede, Cai, and Zhang proved that, in the noise-free limit, the zero-undetected-error capacity is lower bounded by the Sperner capacity of the channel graph, and they conjectured equality. Here we derive an upper bound that proves the conjecture.
We study the capacity of the discrete-time Gaussian channel when its output is quantized with a one-bit quantizer. We focus on the low signal-to-noise ratio (SNR) regime, where communication at very low spectral efficiencies takes place. In this regime a symmetric threshold quantizer is known to reduce channel capacity by a factor of 2/pi, i.e., to cause an asymptotic power loss of approximately two decibels. Here it is shown that this power loss can be avoided by using asymmetric threshold quantizers and asymmetric signaling constellations. To avoid this power loss, flash-signaling input distributions are essential. Consequently, one-bit output quantization of the Gaussian channel reduces spectral efficiency. Threshold quantizers are not only asymptotically optimal: at every fixed SNR a threshold quantizer maximizes capacity among all one-bit output quantizers. The picture changes on the Rayleigh-fading channel. In the noncoherent case a one-bit output quantizer causes an unavoidable low-SNR asymptotic power loss. In the coherent case, however, this power loss is avoidable provided that we allow the quantizer to depend on the fading level.
A coding scheme is proposed for the memoryless Gaussian broadcast channel with correlated noises and feedback. For all noise correlations other than -1, the gap between the sum-rate the scheme achieves and the full-cooperation bound vanishes as the signal-to-noise ratio tends to infinity. When the correlation coefficient is -1, the gains afforded by feedback are unbounded and the prelog is doubled. When the correlation coefficient is +1 we demonstrate a dichotomy: If the noise variances are equal, then feedback is useless, and otherwise, feedback affords unbounded rate gains and doubles the prelog. The unbounded feedback gains, however, require perfect (noiseless) feedback. When the feedback links are noisy the feedback gains are bounded, unless the feedback noise decays to zero sufficiently fast with the signal-to-noise ratio. Extensions to more receivers are also discussed as is the memoryless Gaussian interference channel with feedback.
We derive the capacity region of the state-dependent semideterministic broadcast channel with noncausal state-information at the transmitter. One of the two outputs of this channel is a deterministic function of the channel input and the channel state, and the state is assumed to be known noncausally to the transmitter but not to the receivers. We show that appending the state to the deterministic output does not increase capacity. We also derive an outer bound on the capacity of general (not necessarily semideterministic) state-dependent broadcast channels.
We propose a new inner bound on the capacity region of a memoryless multiple-access channel that is governed by a memoryless state that is known strictly causally to the encoders. The new inner bound contains the previous bounds, and we provide an example demonstrating that the inclusion can be strict. A variation on this example is then applied to the case where the channel is governed by two independent state sequences, where each transmitter knows one of the states strictly causally. The example proves that, as conjectured by Li et al., an inner bound that they derived for this scenario can indeed by strictly better than previous bounds.
We study the behavior of channel capacity when a one-bit quantizer is employed at the output of the discrete-time average-power-limited Gaussian channel. We focus on the low signal-to-noise ratio regime, where communication at very low spectral efficiencies takes place, as in Spread-Spectrum and Ultra-Wideband communications. It is well know that, in this regime, a symmetric one-bit quantizer reduces capacity by 2/pi, which translates to a power loss of approximately two decibels. Here we show that if an asymmetric one-bit quantizer is employed, and if asymmetric signal constellations are used, then these two decibels can be recovered in full.
We study channel capacity when a one-bit quantizer is employed at the output of the discrete-time average-power-limited Rayleigh-fading channel. We focus on the low signal-to-noise ratio regime, where communication at very low spectral efficiencies takes place, as in Spread Spectrum and Ultra-Wideband communications. We demonstrate that, in this regime, the best one-bit quantizer does not reduce the asymptotic capacity of the coherent channel, but it does reduce that of the noncoherent channel.
It is demonstrated that doubling the sampling rate recovers some of the loss in capacity incurred on the bandlimited Gaussian channel with a one-bit output quantizer.
We consider the transmission of a single bit over the continuous-time Poisson channel with noiseless feedback. We show that to send the bit reliably requires, on the average, half the energy of a photon. In the absence of peak-power constraints this holds irrespective of the intensity of the dark current. We also solve for the energy required to send $log_{2} M$ bits.
New achievable rate regions are derived for the two-user additive white Gaussian multiple-access channel with noisy feedback. The regions exhibit the following two properties. Irrespective of the (finite) Gaussian feedback-noise variances, the regions include rate points that lie outside the no-feedback capacity region, and when the feedback-noise variances tend to 0 the regions converge to the perfect-feedback capacity region. The new achievable regions also apply to the partial-feedback setting where one of the transmitters has a noisy feedback link and the other transmitter has no feedback at all. Again, irrespective of the (finite) noise variance on the feedback link, the regions include rate points that lie outside the no-feedback capacity region. Moreover, in the case of perfect partial feedback, i.e., where the only feedback link is noise-free, for certain channel parameters the new regions include rate points that lie outside the Cover-Leung region. This answers in the negative the question posed by van der Meulen as to whether the Cover-Leung region equals the capacity region of the Gaussian multiple-access channel with perfect partial feedback. Finally, we propose new achievable regions also for a setting where the receiver is cognizant of the realizations of the noise sequences on the feedback links.
The two-user discrete memoryless state-dependent multiple-access channel (MAC) models a scenario in which two encoders transmit independent messages to a single receiver via a MAC whose channel law is governed by the pair of encoders' inputs and by an i.i.d. state random variable. In the cooperative state-dependent MAC model it is further assumed that Message 1 is shared by both encoders whereas Message 2 is known only to Encoder 2 - the cognitive transmitter. The capacity of the cooperative state-dependent MAC where the realization of the state sequence is known non-causally to the cognitive encoder has been derived by Somekh-Baruch et. al. In this work we dispense of the assumption that Message 1 is shared a-priori by both encoders. Instead, we study the case in which Encoder 2 cribs causally from Encoder 1. We determine the capacity region for both, the case where Encoder 2 cribs strictly causal and the case where Encoder 2 cribs causally from Encoder 1.