Let $\mathsf{TH}_k$ denote the $k$-out-of-$n$ threshold function: given $n$ input Boolean variables, the output is $1$ if and only if at least $k$ of the inputs are $1$. We consider the problem of computing the $\mathsf{TH}_k$ function using noisy readings of the Boolean variables, where each reading is incorrect with some fixed and known probability $p \in (0,1/2)$. As our main result, we show that it is sufficient to use $(1+o(1)) \frac{n\log \frac{m}{\delta}}{D_{\mathsf{KL}}(p \| 1-p)}$ queries in expectation to compute the $\mathsf{TH}_k$ function with a vanishing error probability $\delta = o(1)$, where $m\triangleq \min\{k,n-k+1\}$ and $D_{\mathsf{KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\mathsf{Bern}(p)$ and $\mathsf{Bern}(1-p)$ distributions. Conversely, we show that any algorithm achieving an error probability of $\delta = o(1)$ necessitates at least $(1-o(1))\frac{(n-m)\log\frac{m}{\delta}}{D_{\mathsf{KL}}(p \| 1-p)}$ queries in expectation. The upper and lower bounds are tight when $m=o(n)$, and are within a multiplicative factor of $\frac{n}{n-m}$ when $m=\Theta(n)$. In particular, when $k=n/2$, the $\mathsf{TH}_k$ function corresponds to the $\mathsf{MAJORITY}$ function, in which case the upper and lower bounds are tight up to a multiplicative factor of two. Compared to previous work, our result tightens the dependence on $p$ in both the upper and lower bounds.

This paper presents a novel optimization framework for solving active sensing problems in wireless communications, in which a base station equipped with massive multiple-input multiple-output (MIMO) and a limited number of radio-frequency chains aims to estimate the channel parameters of a sensing target. Specifically, the receive beamforming matrix at the BS is designed sequentially through optimizing the Bayesian Cramér-Rao bound (B-CRB) metric at each sensing stage, while satisfying a rank constraint and that the receive beamformers must be implementable by analog phase shifters. The proposed approach tackles this B-CRB minimization problem in the Lagrangian dual domain. This dual optimization approach has the advantage of reducing the dimension of the search space from the number of antenna elements to the number of channel parameters, which is typically much smaller for sparse mmWave channels. We propose efficient numerical methods for obtaining the primal solution from the dual and subsequentially setting the phase shifts in each active sensing stage based on this approach. Finally, we demonstrate the benefits of the proposed approach as compared to existing beamforming strategies.

This paper presents a novel technique to design receive beamformers for on-grid angle-of-arrival (AoA) estimation in large-scale multiple-input multiple-output systems using channel codes. Specifically, the receive beamformers are designed so that the measurement model is effectively transformed to a Gaussian channel whose inputs are codewords in a channel code, with each codeword corresponding to a different AoA on the grid. Assuming that the number of antennas is larger than the desired angle resolution in the grid, the AoAs can be recovered by leveraging a suitable decoder on the resulting equivalent channel. The performance of the proposed method is derived in terms of the performance of the underlying channel code. Simulations results demonstrate the advantage of the proposed approach compared to existing beamforming strategies.

Coding schemes for several problems in network information theory are constructed starting from point-to-point channel codes that are designed for symmetric channels. Given that the point-to-point codes satisfy certain properties pertaining to the rate, the error probability, and the distribution of decoded sequences, bounds on the performance of the coding schemes are derived and shown to hold irrespective of other properties of the codes. In particular, we consider the problems of lossless and lossy source coding, Slepian–Wolf coding, Wyner–Ziv coding, Berger–Tung coding, multiple description coding, asymmetric channel coding, Gelfand–Pinsker coding, coding for multiple access channels, Marton coding for broadcast channels, and coding for cloud radio access networks (C-RAN’s). We show that the coding schemes can achieve the best known inner bounds for these problems, provided that the constituent point-to-point channel codes are rate-optimal. This would allow one to leverage commercial off-the-shelf codes for point-to-point symmetric channels in the practical implementation of codes over networks. Simulation results demonstrate the gain of the proposed coding schemes compared to existing practical solutions to these problems.

In this work, we study the problem of sorting n elements with pairwise comparisons under the presence of observation noise. We consider variable-length algorithms with a random number of queries M, and attempt to characterize the noisy sorting capacity defined as the maximal ratio $\frac{{n\log n}}{{{\text{E}}[M]}}$ such that the ordering can be correctly estimated with a vanishing error probability. This can be viewed as a generalization of the framework introduced in [1] to allow variable-length algorithms. We provide upper and lower bounds for the noisy sorting capacity. The proposed algorithm attaining the lower bound is based on the insertion sort algorithm for the sorting problem in the noiseless case and the variable-length version of the Burnashev–Zigangirov algorithm for coding over channels with feedback. Moreover, we also derive an upper bound on the maximal ratio that can be achieved by noisy sorting algorithms that are based on insertion sort.

We revisit the problem of computing with noisy information considered in Feige et al. [1], which includes computing the OR function from noisy queries, and computing the MAX, SEARCH, and SORT functions from noisy pairwise comparisons. For K given elements, the goal is to correctly recover the desired function with probability at least 1 – δ when the outcome of each query is flipped with probability p. We consider both the adaptive sampling setting where each query can be adaptively designed based on past outcomes, and the non-adaptive sampling setting where the query cannot depend on past outcomes. The prior work provides tight bounds on the worst-case query complexity in terms of the dependence on K. However, the upper and lower bounds do not match in terms of the dependence on δ and p. We improve the lower bounds for all the four functions under both adaptive and non-adaptive query models. Most of our lower bounds match the upper bounds up to constant factors when either p or δ is bounded away from 0, while the ratio between the best prior upper and lower bounds go to infinity when p → 0 or p → 1/2. On the other hand, we also provide matching upper and lower bounds for the number of queries in expectation, improving both the upper and lower bounds for variable-length query model.

Sorting is the task of ordering n elements using pairwise comparisons. It is well known that$m=\Theta (n\log n)$comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem when each comparison is incorrect with some fixed yet unknown probability p. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons m to achieve a given desired error probability, we consider randomized algorithms with expected number of queries$\textsf {E}[M]$and aim at characterizing the maximal sorting rate$\frac {n\log n}{\mathop {\mathrm {\textsf {E}}}\nolimits [M]}$such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal rate is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. The two lower bounds — one for fixed-length algorithms and one for variable-length algorithms — are established by combining the insertion sort algorithm with the well-known Burnashev-Zigangirov algorithm for channel coding with feedback. Compared with existing methods, the proposed algorithms are universal in the sense that they do not require the knowledge of p, while maintaining a strictly positive sorting rate. Moreover, we derive a general upper bound on the noisy sorting capacity, along with an upper bound on the maximal rate that can be achieved by sorting algorithms that are based on insertion sort.

Coding schemes for asymmetric channels and channels with state are developed starting from a pair of linear codes designed for symmetric channels. Guarantees on the block error rate performance of the coding schemes are derived in terms of the parameters of the constituent codes. Assuming the constituent codes satisfy some properties on the rate, the error probability, and the distribution of the Hamming distance to decoded sequences, the performance guarantees hold irrespective of other properties of the codes. This would allow one to leverage commercial off-the-shelf codes for point-to-point symmetric channels to design codes for asymmetric channels and channels with state known noncausally at the encoder.

A joint channel estimation and channel coding scheme is presented for channels with memory using polar codes. Unlike the conventional approach of first estimating all channel parameters and then performing channel decoding separately, the proposed scheme incorporates a subset of reliable estimates of channel parameters into the decoding procedure and computes decoding metrics averaged over the statistical behavior of the channel. Specifically, decoding algorithms for finite-state Markov channels of any order, for the Gauss-Markov channel and for flat-fading channels are presented. Further, by adapting list decoding to identify reliably-decoded bits within a codeword, channel estimation and decoding steps are performed iteratively to boost the reliability of channel estimation as well as error correction. In order to improve the performance even further, a new pilot arrangement scheme is developed that utilizes the structure of polar codes and sends pilot symbols embedded within the polar codewords. This construction can be viewed as a new family of shortened polar codes that can be of independent interest. Simulation results demonstrate the benefit of the proposed approach compared to existing solutions.

The throughput of successive cancellation decoding of polar codes can be improved through simplified decoders that identify specific constituent codes in the decoding tree. The identified codes include rate-0, rate-1, repetition, and single parity-check codes. In this work, constituent codes that belong to the family of first-order Reed-Muller codes, and their sub-codes, are also identified in the decoding tree. Alternative decoding schemes that utilize the structure of Reed-Muller codes are incorporated into successive cancellation decoding. Simulation results show that such an approach can improve both the block error rate performance as well as the decoding latency of polar codes.

A joint channel estimation and channel coding scheme is presented for finite-state Markov channels using polar codes. Unlike the conventional approach of first estimating all channel parameters and then performing channel decoding separately, the proposed scheme incorporates a subset of reliable estimates of channel parameters into the decoding algorithm and computes decoding metrics averaged over the statistical behavior of the Markov channel. By adapting list decoding (without any inner code), channel estimation and decoding steps can be performed iteratively to boost the reliability of channel estimation as well as error correction. In order to improve the performance even further, a new pilot transmission scheme is developed that utilizes the structure of polar codes and sends pilot symbols along with code symbols. This construction can be viewed as a new family of shortened polar codes that can be of independent interest. Simulation results demonstrate the benefit of the proposed approach compared to existing solutions.