3GPP 5G New Radio (NR) wireless access technology will support communication at bands ranging from sub GHz to millimeter wave. For communication at millimeter wave, e.g., at 60 GHz, the transmitted signal experiences severe attenuation, due to outdoor-to-indoor penetration, oxygen absorption, etc., significantly degrading the link budget performance of the NR system. In order to achieve good coverage for NR systems, operating at all bands, it is important to ensure the support of power efficient waveforms for physical channels carrying data and reference signals. Demodulation reference signals (DM-RS) are used in 5G NR systems to assist receivers in estimation of the wireless channel for subsequent coherent processing of the corresponding received data on the physical channel. In this paper, we propose a novel design of DM-RS that achieves channel estimation performance similar to NR Release 15 DM-RS, while providing higher power efficiency. The proposed DM-RS design in conjunction with power efficient waveforms for physical channel can thus be used to enhance coverage of NR systems operating at higher carrier frequency ranges of millimeter wave bands, e.g. 60 GHz. We corroborate our claims via computer simulations.

We study the support recovery problem for compressed sensing, where the goal is to reconstruct the sparsity pattern of a high-dimensional K-sparse signal x ∈ ℝN, as well as the corresponding sparse coefficients, from low-dimensional linear measurements with and without noise. Our key contribution is a new compressed sensing framework through a new family of carefully designed sparse measurement matrices associated with minimal measurement costs and a low-complexity recovery algorithm. Specifically, the measurement matrix in our framework is designed based on the well-crafted sparsification through capacity-approaching sparse-graph codes, where the sparse coefficients can be recovered efficiently in a few iterations by performing simple error decoding over the observations. We formally connect this general recovery problem with sparsegraph decoding in packet communication systems and analyze our framework in terms of the measurement cost, computational complexity, and recovery performance. Specifically, we show that in the noiseless setting, our framework can recover any arbitrary K-sparse signal in O(K) time using 2K measurements asymptotically with a vanishing error probability. In the noisy setting, when the sparse coefficients take values in a finite and quantized alphabet, our framework can achieve the same goal in time O(K log(N/K)) using O(K log(N/K)) measurements obtained from measurement matrix with elements {-1, 0, 1}. When the sparsity K is sub-linear in the signal dimension K = O(Nδ) for some 0δ) and the magnitudes of all thesparse coefficients are bounded below by a positive constant, our algorithm can recover an arbitrarily large (1- p)-fraction of the support of the sparse signal using O(K log(N/K) log log(N/K)) measurements, and O(K log3(N/K)) run-time, where r is an arbitrarily small constant. For each recovered sparse coefficient, we can achieve O(∈) error for an arbitrarily small constant E. In addition, if the magnitudes of all the sparse coefficients are upper bounded by O(Kc) for some constant c1recovery guarantee for the estimated signal x̂: ∥x̂ - x∥1≤ κ∥x∥1, where the constant κ can be arbitrarily small. This offers the desired scalability of our framework that can potentially enable real-time or near-realtime processing for massive datasets featuring sparsity, which are relevant to a multitude of practical applications.

It is a well-known fact that the Discrete Fourier Transform (DFT) X̅ of an arbitrary n-length input signal x̅, can be computed from all the n time-domain samples in O(n log n) operations via a Fast Fourier Transform (FFT) algorithm. If the spectrum X̅ is k-sparse (where k ≪ n), can we do better? We show that asymptotically in k and n, when k is sub-linear in n (precisely, k = O(nδ), where 0 ≤ δ <; 1), and the support of the non-zero DFT coefficients is uniformly random, the fast fourier aliasing-based sparse transform (FFAST) algorithm, proposed in this paper, computes, with asymptotically high probability, the k non-zero DFT coefficients of X̅ from O(k) samples of x̅ in O(k log k) arithmetic operations. Further, the constants in the big Oh notation for both sample and computational cost are small, e.g., when δ <; 0.99, which essentially covers a wide range of sublinear sparsity cases, the sample cost is less than 4k. Although, in this paper we assume that the samples of the signal x̅ observed by the FFAST are noise-free, a noise-robust extension of the FFAST is provided in a companion (Part II) paper [1]. Our approach is based on filter-less sub-sampling of the input signal using a set of carefully chosen uniform sub-sampling patterns guided by the Chinese Remainder Theorem (CRT). The idea is to cleverly exploit, rather than avoid, the resulting aliasing artifacts induced by sub-sampling. Specifically, the sub-sampling operation on the time-domain signal x̅ is designed to create aliasing patterns of the non-zero coefficients of the spectrum X̅ to “look like” paritycheck constraints of a good erasure-correcting sparse-graph code. Next, we show that computing the sparse DFT X̅ is equivalent to decoding of an appropriate sparse-graph code. The sparse-graph codes further permit a fast peeling-style decoding. Consequently, the resulting DFT computation is low in both the sample and the decoding complexity. We analytically connect our proposed CRTbased aliasing framework to random sparse-graph codes, and analyze the performance of our algorithm using density evolution techniques from coding theory. We provide extensive simulation results, that are in tight agreement with our theoretical findings.

The fast Fourier transform is the most efficiently known way to compute the discrete Fourier transform (DFT) of an arbitrary n-length signal, and has a computational complexity of O(n log n). If the DFT X⃗ of the signal x⃗ has only k non-zero coefficients (where k3n) noise-corrupted time-domain samples in O(k log4n) complexity, i.e., sub-linear sample and time complexity. In Section IX, we provide extensive simulation results validating the empirical performance of the R-FFAST algorithm, e.g., we show that the R-FFAST algorithm computes a 50-sparse DFT of an ≈10 million length signal using only 4800 noisy samples with an effective signal-to-noise ratio of 5 dB. We also provide comparison of the run-time performance of several existing sparse Fourier transform implementations with that of the R-FFAST and show that it is almost 20 times faster, for comparable settings, than the state-of-the-art algorithm, while simultaneously providing better support recovery guarantees. While our theoretical results are for signals with a uniformly random support of the non-zero DFT coefficients and additive white Gaussian noise, we provide simulation results, which demonstrate that the R-FFAST algorithm performs well even for signals like magnetic resonance images, that have an approximately sparse Fourier spectrum with a non-uniform support for the dominant DFT coefficients.

We present a novel algorithm, named the 2D-FFAST (Two-dimensional Fast Fourier Aliasing-based Sparse Transform), to compute a sparse 2D-Discrete Fourier Transform (2D-DFT) featuring both low sample and computational complexity. The proposed algorithm is based on diverse concepts from signal processing (sub-sampling and aliasing), coding theory (sparse-graph codes) and number theory (Chinese-remainder-theorem) and generalizes the 1D-FFAST algorithm recently proposed by Pawar and Ramchandran to the 2D setting. Concretely, our proposed 2D-FFAST algorithm computes a k-sparse 2D-DFT, with a uniformly random support, of size N = Nx× Nyusing O(k) noiseless spatial-domain measurements in O(k log k) computational time. Our results are attractive when the sparsity is sub-linear with respect to the signal dimension, that is, when k → ∞ and k/N → 0. For the case when the spatial-domain measurements are corrupted by additive noise, our 2D-FFAST framework extends to a noise-robust version of computing a 2D-DFT using O(k log3N) measurements in sub-linear time of O(k log4N). Empirically, we show that the 2D-FFAST can compute a k = 3509 sparse 2D-DFT of a 508 × 508-size phantom image using only 4.75k measurements. We also empirically evaluate the 2D-FFAST algorithm on a real-world magnetic resonance brain image using a total of 60.18% of Fourier measurements to provide an almost instant reconstruction with SNR=4.5 dB. This provides empirical evidence that the 2D-FFAST architecture is applicable to a wider class of input signals than analyzed theoretically in the paper.

In this paper, we study the data exchange problem, where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is for each user to gain access to the file, while minimizing some communication cost. We assume that the users can communicate over a noiseless broadcast channel, and that the communication cost is a sum of each user's cost function over the number of bits it transmits. For instance, the communication cost could simply be the total number of bits that needs to be transmitted. In the most general case studied in this paper, each user can have any arbitrary convex cost function. We provide deterministic, polynomial-time algorithms (in the number of users and packets), which find an optimal communication scheme that minimizes the communication cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic algorithm, which is based on a random linear network-coding scheme.

Cloud Radio Access Network (C-RAN) is a novel mobile network architecture that allows for efficient and economic building, upgrading and maintenance of RAN networks to cope with increasing mobile traffic data. The main idea behind C-RAN is to maintain distributed remote radio head (RRH) units for transmission and reception of radio signals, while pool the Baseband Units (BBUs) from multiple base stations into a centralized location for statistical multiplexing gain. The BBUs are connected to RRH via front-haul links. Although the C-RAN architecture enjoys significant advantages in terms of both the capital expenditure (CAPEX) and the operational expenditure (OPEX) over traditional networks, it also exerts considerable burden on the capacity-constrained front-haul links of transporting the high bandwidth complex baseband data between RRH and BBUs. Fortunately, the LTE signal is inherently redundant and compressible. In this paper, we propose a low-complexity, frequency domain, front-haul compression algorithm, that leverages the user scheduling side-information available at the BBU pool, in addition to the LTE signal redundancy, to achieve a compression ratio of 10X for a full-buffer traffic model. We also provide extensive link-level and system-level simulations to validate the performance of our proposed front-haul compression algorithm on simulated LTE signal.

We consider the problem of recovering the support of an arbitrary K-sparse N-length vector in the presence of noise, where the sparsity K = O(Nδ) is sub-linear in N for some 01.3̇N) and sub-linear computational complexity O(K log1.3̇N). Our measurement system is designed to capture observations of the signal through the parity constraints of sparse-graph codes, and to recover the signal by using a simple peeling decoder. We formally connect general sparse recovery problems with sparse-graph decoding, and showcase our design in terms of the measurement cost, computational complexity and recovery performance.

In this paper, we consider the problem of computing a K-sparse N-point Hadamard Transforms (HT) from noisy time domain samples, where K = O(Nα) scales sub-linearly in N for some α ∈ (0; 1). The SParse Robust Iterative Graph-based Hadamard Transform (SPRIGHT) algorithm is proposed to recover the sparse HT coefficients in a stable manner that is robust to additive Gaussian noise. In particular, it is shown that the K-sparse HT of the signal can be reconstructed from noisy time domain samples with a vanishing error probability using the same sample complexity O(K logN) as in the noiseless case of [1] and computational complexity1O(N logN). Last but not least, given the complexity orders of the SPRIGHT algorithm, our numerical experiments further validate that the big-Oh constants in the complexity are small.

The Fast Fourier Transform (FFT) is the most efficiently known way to compute the Discrete Fourier Transform (DFT) of an arbitrary n-length signal, and has a computational complexity of O(n log n). If the DFT X⃗ of the signal x⃗ has only k non-zero coefficients (where k1noise-corrupted time-domain samples, in O(n log n) computations2. While our theoretical results are for signals with a uniformly random support of the non-zero DFT coefficients and additive white Gaussian noise, we provide simulation results which demonstrates that the R-FFAST algorithm performs well even for signals like MR images, that have an approximately sparse Fourier spectrum with a non-uniform support for the dominant DFT coefficients.

Given an n-length input signal x, it is well known that its Discrete Fourier Transform (DFT), X, can be computed in O(nlogn) complexity using a Fast Fourier Transform. If the spectrum X is exactly k-sparse (where kδwhere 0 <; δ <; 1), and the support of the non-zero DFT coefficients is uniformly random, we can exploit this sparsity in two fundamental ways (i) sample complexity: we need only M = rk deterministically chosen samples of the input signal x (where r <; 4 when 0 <; δ <; 0.99); and (ii) computational complexity: we can reliably compute the DFT X using O(k log k) operations, where the constants in the big Oh are small. Our algorithm succeeds with high probability, with the probability of failure vanishing to zero asymptotically in the number of samples acquired, M. Our approach is based on filterless subsampling of the input signal x using a small set of carefully chosen uniform subsampling patterns guided by the Chinese Remainder Theorem (CRT). Specifically, our subsampling operation on x is designed to create aliasing patterns on the spectrum X that "look like" parity-check constraints of good erasure-correcting sparse-graph codes. We show how computing the sparse DFT X is equivalent to decoding of these sparse-graph codes and is low in both sample complexity and decoding complexity. We accordingly dub our algorithm the FFAST (Fast Fourier Aliasing-based Sparse Transform) algorithm. In our analysis, we rigorously connect our CRT based graph constructions to random sparse-graph codes based on a balls-and-bins model and analyze the convergence behavior of the latter using well-studied density evolution techniques from coding theory. We provide simulation results in Section IV that corroborate our theoretical findings, and validate the empirical performance of the FFAST algorithm.

In this paper, we quantify how much codes can reduce the data retrieval latency in storage systems. By combining a simple linear code with a novel request scheduling algorithm, which we call Blocking-one Scheduling (BoS), we show analytically that it is possible to use codes to reduce data retrieval delay by up to 17% over currently popular replication-based strategies. Although in this work we focus on a simplified setting where the storage system stores a single content, the methodology developed can be applied to more general settings with multiple contents. The results also offer insightful guidance to the design of storage systems in data centers and content distribution networks.

In this paper we construct a deterministic polynomial time algorithm for the problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge of the file. We further assume the existence of another set of terminals in the system, called helpers, who are not interested in the common file, but who are willing to help the users. Given that the collective information of all the terminals is sufficient to allow recovery of the entire file, the goal is to minimize the (weighted) sum of bits that these terminals need to exchange over a noiseless public channel in order achieve this goal. Based on established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing the largest shared secret key in the presence of an eavesdropper. We consider the following side-information settings: (i) side-information in the form of uncoded packets of the file, where the terminals' side-information consists of subsets of the file packets; (ii) side-information in the form of linearly correlated packets, where the terminals have access to linear combinations of the file packets; and (iii) the general setting where the the terminals' side-information has an arbitrary (i.i.d.) correlation structure. We provide a polynomial-time algorithm (in the number of terminals) that finds the optimal rate allocations for these terminals, and then determines an explicit optimal transmission scheme for cases (i) and (ii).

In this paper we study the problem of data exchange, where each node in the system has a number of linear combinations of the data packets. Communicating over a public channel, the goal is for all nodes to reconstruct the entire set of the data packets in minimal total number of bits exchanged over the channel. We present a novel divide and conquer based architecture that determines the number of bits each node should transmit. This along with the well known fact, that it is sufficient for the nodes to broadcast linear combinations of their local information, provides a polynomial time deterministic algorithm for reconstructing the entire set of the data packets at all nodes in minimal amount of total communication.

We introduce an efficient family of exact regenerating codes for data storage in large-scale distributed systems. We refer to these new codes as Distributed Replication-based Exact Simple Storage (DRESS) codes. A key property of DRESS codes is their very efficient distributed and uncoded repair and growth processes that have minimum bandwidth, reads and computational overheads. This property is essential for large-scale systems with high reliability and availability requirements. DRESS codes will first encode the file using a Maximum Distance Separable (MDS) code, then place multiple replicas of the coded packets on different nodes in the system. We propose a simple and flexible randomized scheme for placing those replicas based on the balls-and-bins model. Our construction showcases the power of the probabilistic approach in constructing regenerating codes that can be efficiently repaired and grown.

We address the problem of securing distributed storage systems against adversarial node attacks. An important aspect of these systems is node failures over time, necessitating, thus, a repair mechanism in order to maintain a desired high system reliability. In such dynamic settings, an important security problem is to safeguard the system from a malicious adversary who may come at different time instances during the lifetime of the storage system to corrupt the data stored on some nodes. We provide upper bounds on the maximum amount of information that can be stored safely on the system in the presence of the adversary. For an important operating regime, which we call the bandwidth-limited regime, we show that our upper bounds are tight and provide explicit linear code constructions. Moreover, we provide a way to shortlist the malicious nodes and expurgate the system.

We address the problem of securing distributed storage systems against eavesdropping and adversarial attacks. An important aspect of these systems is node failures over time, necessitating, thus, a repair mechanism in order to maintain a desired high system reliability. In such dynamic settings, an important security problem is to safeguard the system from an intruder who may come at different time instances during the lifetime of the storage system to observe and possibly alter the data stored on some nodes. In this scenario, we give upper bounds on the maximum amount of information that can be stored safely on the system. For an important operating regime of the distributed storage system, which we call the bandwidth-limited regime, we show that our upper bounds are tight and provide explicit code constructions. Moreover, we provide a way to short list the malicious nodes and expurgate the system.

We address the problem of securing distributed storage systems against passive eavesdroppers that can observe a limited number of storage nodes. An important aspect of these systems is node failures over time, which demand a repair mechanism aimed at maintaining a targeted high level of system reliability. If an eavesdropper observes a node that is added to the system to replace a failed node, it will have access to all the data downloaded during repair, which can potentially compromise the entire information in the system.We are interested in determining the secrecy capacity of distributed storage systems under repair dynamics, i.e., the maximum amount of data that can be securely stored and made available to a legitimate user without revealing any information to any eavesdropper. We derive a general upper bound on the secrecy capacity and show that this bound is tight for the bandwidth-limited regime which is of importance in scenarios such as peer-to-peer distributed storage systems. We also provide a simple explicit code construction that achieves the capacity for this regime.

Cooperation between terminals has been proposed to improve the reliability and throughput of wireless communication. While recent work has shown that relay cooperation provides increased diversity, increased multiplexing gain over that offered by direct link has largely been unexplored. In this work we show that cooperative multiplexing gain can be achieved by using a half duplex relay. We capture relative distances between terminals in the high SNR diversity multiplexing tradeoff (DMT) framework. The DMT performance is then characterized for a network having a single antenna half-duplex relay between a single-antenna source and two-antenna destination. Our results show that the achievable multiplexing gain using cooperation can be greater than that of the direct link and is a function of the relative distance between source and relay compared to the destination. Moreover, for multiplexing gains less than 1, a simple scheme of the relay listening 1/3 of the time and transmitting 2/3 of the time can achieve the 2 by 2 MIMO DMT.

For the quasi-static, Rayleigh-fading multiple-input multiple-output (MIMO) channel with$n_{t}$transmit and$n_{r}$receive antennas, Zheng and Tse showed that there exists a fundamental tradeoff between diversity and spatial-multiplexing gains, referred to as the diversity–multiplexing gain (D-MG) tradeoff. Subsequently, El Gamal, Caire, and Damen considered signaling across the same channel using an$L$-round automatic retransmission request (ARQ) protocol that assumes the presence of a noiseless feedback channel capable of conveying one bit of information per use of the feedback channel. They showed that given a fixed number$L$of ARQ rounds and no power control, there is a tradeoff between diversity and multiplexing gains, termed the diversity–multiplexing–delay (DMD) tradeoff. This tradeoff indicates that the diversity gain under the ARQ scheme for a particular information rate is considerably larger than that obtainable in the absence of feedback.

A recent result of Zheng and Tse states that over a quasi-static channel, there exists a fundamental tradeoff, referred to as the diversity–multiplexing gain (D-MG) tradeoff, between the spatial multiplexing gain and the diversity gain that can be simultaneously achieved by a space–time (ST) code. This tradeoff is precisely known in the case of independent and identically distributed (i.i.d.) Rayleigh fading, for$T geq n_t+n_r-1$where$T$is the number of time slots over which coding takes place and$n_t,n_r$are the number of transmit and receive antennas, respectively. For$T ≪ n_t+n_r-1$, only upper and lower bounds on the D-MG tradeoff are available. In this paper, we present a complete solution to the problem of explicitly constructing D-MG optimal ST codes, i.e., codes that achieve the D-MG tradeoff for any number of receive antennas. We do this by showing that for the square minimum-delay case when$T=n_t=n$, cyclic-division-algebra (CDA)-based ST codes having the nonvanishing determinant property are D-MG optimal. While constructions of such codes were previously known for restricted values of$n$, we provide here a construction for such codes that is valid for all$n$. For the rectangular,$T ≫ n_t$case, we present two general techniques for building D-MG-optimal rectangular ST codes from their square counterparts. A byproduct of our results establishes that the D-MG tradeoff for all$Tgeq n_t$is the same as that previously known to hold for$T geq n_t + n_r -1$.

In the recent landmark paper of Zheng and Tse it is shown for the quasi-static, Rayleigh-fading MIMO channel with n/sub t/ transmit and n/sub r/ receive antennas, that there exists a fundamental tradeoff between diversity gain and multiplexing gain, referred to as the diversity-multiplexing gain (D-MG) tradeoff. This paper presents the first explicit construction of space-time (ST) codes for an arbitrary number of transmit and/or receive antennas that achieve the D-MG tradeoff. It is shown here that ST codes constructed from cyclic-division-algebras (CDA) and satisfying a certain non-vanishing determinant (NVD) property, are optimal under the D-MG tradeoff for any n/sub t/,n/sub r/. Furthermore, this optimality is achieved with minimum possible value of the delay or block-length parameter T = n/sub t/. CDA-based ST codes with NVD have previously been constructed for restricted values of n/sub t/. A unified construction of D-MG optimal CDA-based ST codes with NVD is given here, for any number n/sub t/ of transmit antennas. The CDA-based constructions are also extended to provide D-MG optimal codes for all T /spl ges/ n/sub t/, again for any number nt of transmit antennas. This extension thus presents rectangular D-MG optimal space-time codes that achieve the D-MG tradeoff. Taken together, the above constructions also extend the region of T for which the D-MG tradeoff is precisely known from T /spl ges/ n/sub t/ + n/sub r/ - 1 to T /spl ges/ n/sub t/.

For the quasi-static, Rayleigh-fading MIMO channel with nttransmit and nrreceive antennas, Zheng and Tse showed that there exists a fundamental tradeoff between diversity and multiplexing gains, referred to as the diversity-multiplexing gain (D-MG) tradeoff. Explicit constructions for D-MG optimal ST codes are now available. In a subsequent paper, El Gamal, Caire and Damen considered signaling across the quasi-static ST channel using an L-round ARQ protocol that assumes the presence of a noiseless feedback channel capable of conveying one bit of information (ACK or NACK) per use of the feedback channel. They showed that given a fixed number of ARQ rounds L, there is a tradeoff between diversity and multiplexing gains under which the optimum diversity gain of the ARQ channel transmitting R = r log(SNR) bits per channel use, is that of the quasi-static channel without feedback investigated by Zheng and Tse, transmitting at (1/L)th the information rate. This tradeoff, which now is a function of the number L of ARQ rounds, is termed the diversity-multiplexing gain-delay (DMD) tradeoff. In the current paper, a sufficient condition under which a ST code will achieve the DMD tradeoff is presented for the case nrges nt. The cyclic-division-algebra-based constructions of DMG optimal ST codes by Elia et. al. are then modified to yield codes which meet this sufficient criterion and are thereby DMD-optimal. This modification requires that either nt|L or L|nt

Bounds on the diversity-multiplexing gain tradeoff of a recent space-time block code construction are provided. This construction makes use of binary codes which is optimum in terms of the rate-diversity tradeoff. The code can be decoded using sphere decoding techniques.