NGNadim Ghaddar

Nadim Ghaddar

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Nadim Ghaddar has a total of 10 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Low-Complexity Coding Techniques for Cloud Radio Access Networks

    by Nadim Ghaddar, Lele Wang

    The problem of coding for the uplink and downlink of cloud radio access networks (C-RAN’s) with K users and L relays is considered. It is shown that low-complexity coding schemes that achieve any point in the rate-fronthaul region of joint coding and compression can be constructed starting from at most 4(K+L)-2 point-to-point codes designed for symmetric channels. This reduces the seemingly hard task of constructing good codes for C-RAN’s to the much better understood task of finding good codes for single-user channels. To show this result, an equivalence between the achievable rate-fronthaul regions of joint coding and successive coding is established. Then, rate-splitting and quantization-splitting techniques are used to show that the task of achieving a rate-fronthaul point in the joint coding region can be simplified to that of achieving a corner point in a higher-dimensional C-RAN problem. As a by-product, some interesting properties of the rate-fronthaul region of joint decoding for uplink C-RAN’s are also derived.


  • Noisy Sorting Capacity

    by Ziao Wang, Nadim Ghaddar, Banghua Zhu, Lele Wang

    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.


  • Noisy Computing of the OR and MAX Functions

    by Banghua Zhu, Ziao Wang, Nadim Ghaddar, Jiantao Jiao, Lele Wang

    We consider the problem of computing a function of n variables using noisy queries, where each query is incorrect with some fixed and known probability $p \in (0,1/2)$ . Specifically, we consider the computation of the $\textsf {OR}$ function of n bits (where queries correspond to noisy readings of the bits) and the $\textsf {MAX}$ function of n real numbers (where queries correspond to noisy pairwise comparisons). We show that an expected number of queries of $(1 \pm o(1)) {}\frac {n\log {}\frac {1}{\delta }}{D_{\textsf {KL}}(p \| 1-p)}$ is both sufficient and necessary to compute both functions with a vanishing error probability $\delta = o(1)$ , where $D_{\textsf {KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\textsf {Bern}(p)$ and $\textsf {Bern}(1-p)$ distributions. Compared to previous work, our results tighten the dependence on p in both the upper and lower bounds for the two functions.


  • A Lego-Brick Approach to Coding for Network Communication

    by Nadim Ghaddar, Shouvik Ganguly, Lele Wang, Young-Han Kim

    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.


  • Joint Channel Estimation and Coding Over Channels With Memory Using Polar Codes

    by Nadim Ghaddar, Young-Han Kim, Laurence B. Milstein, Liangping Ma, Byung K. Yi

    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.