Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAnalog Coding Frame-work
56
0
0.0
(
0
)
Added by
Marina Haikin
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Marina Haikin
Ask ChatGPT about the research
No Arabic abstract
Analog coding is a low-complexity method to combat erasures, based on linear redundancy in the signal space domain. Previous work examined band-limited discrete Fourier transform (DFT) codes for Gaussian channels with erasures or impulses. We extend this concept to source coding with erasure side-information at the encoder and show that the performance of band-limited DFT can be significantly improved using irregular spectrum, and more generally, using equiangular tight frames (ETF). Frames are overcomplete bases and are widely used in mathematics, computer science, engineering, and statistics since they provide a stable and robust decomposition. Design of frames with favorable properties of random subframes is motivated in variety of applications, including code-devision multiple access (CDMA), compressed sensing and analog coding. We present a novel relation between deterministic frames and random matrix theory. We show empirically that the MANOVA ensemble offers a universal description of the spectra of randomly selected subframes with constant aspect ratios, taken from deterministic near-ETFs. Moreover, we derive an analytic framework and bring a formal validation for some of the empirical results, specifically that the asymptotic form for the moments of high orders of subsets of ETF agree with that of MANOVA. Finally, when exploring over-complete bases, the Welch bound is a lower bound on the root mean square cross correlation between vectors. We extend the Welch bound to an erasure setting, in which a reduced frame, composed of a random subset of Bernoulli selected vectors, is of interest. The lower bound involves moment of the reduced frame, and it is tight for ETFs and asymptotically coincides with the MANOVA moments. This result offers a novel perspective on the superiority of ETFs over other frames.
rate research
Read More
Over-complete systems of vectors, or in short, frames, play the role of analog codes in many areas of communication and signal processing. To name a few, spreading sequences for code-division multiple access (CDMA), over-complete representations for multiple-description (MD) source coding, space-time codes, sensing matrices for compressed sensing (CS), and more recently, codes for unreliable distributed computation. In this survey paper we observe an information-theoretic random-like behavior of frame subsets. Such sub-frames arise in setups involving erasures (communication), random user activity (multiple access), or sparsity (signal processing), in addition to channel or quantization noise. The goodness of a frame as an analog code is a function of the eigenvalues of a sub-frame, averaged over all sub-frames. For the highly symmetric class of Equiangular Tight Frames (ETF), as well as for other near ETF frames, we show that the empirical eigenvalue distribution of a randomly-selected sub-frame (i) is asymptotically indistinguishable from Wachters MANOVA distribution; and (ii) exhibits a universal convergence rate to this limit that is empirically indistinguishable from that of a matrix sequence drawn from MANOVA (Jacobi) ensembles of corresponding dimensions. Some of these results are shown via careful statistical analysis of empirical evidence, and some are proved analytically using random matrix theory arguments of independent interest. The goodness measures of the MANOVA limit distribution are better, in a concrete formal sense, than those of the Marchenko-Pastur distribution at the same aspect ratio, implying that deterministic analog codes are better than random (i.i.d.) analog codes. We further give evidence that the ETF (and near ETF) family is in fact superior to any other frame family in terms of its typical sub-frame goodness.
Analog coding decouples the tasks of protecting against erasures and noise. For erasure correction, it creates an analog redundancy by means of band-limited discrete Fourier transform (DFT) interpolation, or more generally, by an over-complete expansion based on a frame. We examine the analog coding paradigm for the dual setup of a source with erasure side-information (SI) at the encoder. The excess rate of analog coding above the rate-distortion function (RDF) is associated with the energy of the inverse of submatrices of the frame, where each submatrix corresponds to a possible erasure pattern. We give a partial theoretical as well as numerical evidence that a variety of structured frames, in particular DFT frames with difference-set spectrum and more general equiangular tight frames (ETFs), with a common MANOVA limiting spectrum, minimize the excess rate over all possible frames. However, they do not achieve the RDF even in the limit as the dimension goes to infinity.
The exponential growth in data generation and large-scale data analysis creates an unprecedented need for inexpensive, low-latency, and high-density information storage. This need has motivated significant research into multi-level memory systems that can store multiple bits of information per device. Although both the memory state of these devices and much of the data they store are intrinsically analog-valued, both are quantized for use with digital systems and discrete error correcting codes. Using phase change memory as a prototypical multi-level storage technology, we herein demonstrate that analog-valued devices can achieve higher capacities when paired with analog codes. Further, we find that storing analog signals directly through joint-coding can achieve low distortion with reduced coding complexity. By jointly optimizing for signal statistics, device statistics, and a distortion metric, finite-length analog encodings can perform comparable to digital systems with asymptotically infinite large encodings. These results show that end-to-end analog memory systems have not only the potential to reach higher storage capacities than discrete systems, but also to significantly lower coding complexity, leading to faster and more energy efficient storage.
We reduce the problem of optimal beamforming for two-way relay (TWR) systems with perfect channel state infomation (CSI) that use analog network coding (ANC) to a pair of algebraic equations in two variables that can be solved inexpensively using numerical methods. The solution has greatly reduced complexity compared to previous exact solutions via semidefinite programming (SDP). Together with the linearized robust solution described in (Aziz and Thron, 2014), it provides a high-performance, low-complexity robust beamforming solution for 2-way relays.
We study the fundamental problem of index coding under an additional privacy constraint that requires each receiver to learn nothing more about the collection of messages beyond its demanded messages from the server and what is available to it as side information. To enable such private communication, we allow the use of a collection of independent secret keys, each of which is shared amongst a subset of users and is known to the server. The goal is to study properties of the key access structures which make the problem feasible and then design encoding and decoding schemes efficient in the size of the server transmission as well as the sizes of the secret keys. We call this the private index coding problem. We begin by characterizing the key access structures that make private index coding feasible. We also give conditions to check if a given linear scheme is a valid private index code. For up to three users, we characterize the rate region of feasible server transmission and key rates, and show that all feasible rates can be achieved using scalar linear coding and time sharing; we also show that scalar linear codes are sub-optimal for four receivers. The outer bounds used in the case of three users are extended to arbitrary number of users and seen as a generalized version of the well-known polymatroidal bounds for the standard non-private index coding. We also show that the presence of common randomness and private randomness does not change the rate region. Furthermore, we study the case where no keys are shared among the users and provide some necessary and sufficient conditions for feasibility in this setting under a weaker notion of privacy. If the server has the ability to multicast to any subset of users, we demonstrate how this flexibility can be used to provide privacy and characterize the minimum number of server multicasts required.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
