We explore applying group theory principles in designing waveforms for a cognitive radar. By leveraging affine groups, we provide a mathematical framework for designing radar waveforms for a wideband multiple-input multiple-output (MIMO) radar. Prior works in this area have considered this approach for the narrowband or single-antenna radar systems. We first derive a general wideband ambiguity function of a MIMO radar by correlating the signal with its time-dilated, Doppler-shifted, and position-delayed replicas. The ambiguity function is essentially a coefficient function of the unitary representation of an affine group. We then construct complementary waveforms that minimize range sidelobes in the cross-ambiguity matrix, depending on the requirements of cognitive radar. Our numerical experiments demonstrate the effectiveness of group-theory-based complementary waveform designs.

We consider the design of a modern uplink for supporting machine-type communication and the confluence of sensing, communication, and distributed learning. We demonstrate that grant-free multiple access is possible even in the presence of highly time-varying channels and high delay spread. Our approach is built on enhancing the 2 -step random access procedure of the 5GNR standard. This 2 -step procedure uses Zadoff-Chu (ZC) sequences as preambles that point to radio resources which are then used to upload data. ZC sequences are processed in the delay-Doppler (DD) domain rather than the time domain. We demonstrate that it is possible to detect multiple preambles in the presence of mobility and delay spread using a receiver with no knowledge of the channel other than the worst case delay and Doppler spreads. Our approach depends on the mathematical properties of ZC sequences in the DD domain. We derive a closed form expression for ZC pilots in the DD domain, we characterize the possible self-ambiguity functions, and we determine the magnitude of the possible cross-ambiguity functions. These mathematical properties combine with Zak-OTFS modulation to enable detection of multiple pilots through solution of a compressed sensing problem. The columns of the compressed sensing matrix are the translates of individual ZC pilots in delay and Doppler. We show that columns in the design matrix satisfy a coherence property that makes it possible to detect multiple preambles in a single Zak-OTFS subframe using One-Step Thresholding, which is an algorithm with low complexity.

Current wireless infrastructure is optimized to support applications such as music/video streaming and internet browsing, where information flows from the base station to the user. This paper anticipates the emergence of applications such as distributed machine learning and automated driving, resulting in a shift of engineering focus from downlink to uplink as users become significant sources of data. The current paradigm of scheduling users on reserved uplink resources (grants) is not able to deal efficiently with unpredictable traffic patterns. As a result, Release 15, 3GPP introduced the 2 -step RACH as a mechanism to enable grant-free (random) initial access. The first of the two steps is preamble detection in a RACH slot, and in this paper we describe a very low-complexity algorithm for simultaneous detection of multiple preambles in the presence of mobility and delay spread. We provide a pathway to standards adoption by choosing Zadoff-Chu (ZC) sequences as preambles, taking advantage of the fact that ZC sequences already appear in 5G standards. We construct preambles by using the discrete Zak transform to pass from a ZC sequence of length$M N$in the time domain (TD) to a quasi-periodic$M \times N$array in the delay-Doppler (DD) domain. There are$M N$quasi-periodic Dirac pulses, each corresponding to a Zak-OTFS carrier waveform, and the ZC preamble is simply the corresponding sum of Zak-OTFS carrier waveforms. We detect multiple preambles in the presence of mobility and delay spread by sampling the received signal on the$M \times N$period grid in the DD domain. We approach detection as a compressed sensing problem. We represent a preamble as a column of length$M N$in the DD domain and apply discrete shifts in delay and Doppler to produce a block with$\mathcal{O}(M N)$columns in the compressed sensing matrix. The superposition of multiple preambles determines a block sparse sum of columns in the sensing matrix. The correlation properties of ZC sequences result in a highly structured compressed sensing matrix, making it possible to identify constituent preambles using One-Step Thresholding (OST), which has complexity$\mathcal{O}\left(M^{3} N^{3}\right)$. In this paper, we describe an algorithm with complexity that is$\mathcal{O}\left(M^{2} N^{2}\right)$in the size of an individual column ($M N$).

Physical layer key generation techniques aim to extract secret keys from the information contained in wireless channels. However, existing key generation schemes often rely on time-frequency domain waveforms for channel estimation, which not only makes secret extraction less reliable but may also compromise the confidentiality of the extracted secret information. This paper presents physical layer key generation methods relying on the Orthogonal Time Frequency and Space (OTFS) waveform. We present analysis showing that the delay-Doppler domain channel estimates obtained using OTFS are conducive to more secure and reliable secret extraction than time-frequency domain channel estimates obtained using the prevalent Orthogonal Frequency Division Multiplexing (OFDM). This analysis provides theoretical guarantees under certain simple assumptions. We then relax those assumptions in extensive time-division duplex (TDD) simulations and show that under realistic settings, OTFS offers the expected benefits to reliability and security. Our simulations show that the introduced OTFS schemes can reliably extract secret keys from channel estimates in scenarios where time-frequency domain methods deteriorate.

Orthogonal Time Frequency Space (OTFS) is a framework for communications and active sensing that processes signals in the delay-Doppler (DD) domain. It is informed by 6G propagation environments, where Doppler spreads measured in$\text{kHz}$make it more and more difficult to estimate channels, and the standard model-dependent approach to wireless communication is starting to break down. We consider Zak-OTFS where inverse Zak transform converts information symbols mounted on DD domain pulses to the time domain for transmission. Zak-OTFS modulation is parameterized by a delay period$\tau_{p}$and a Doppler period$\nu_{p}$, where the product$\nu_{p}\nu_{p}=1$. When the channel spread is less than the delay period, and the Doppler spread is less than the Doppler period, the Zak-OTFS input-output relation can be predicted from the response to a single pilot symbol. The highly reliable channel estimates concentrate around the pilot location, and we configure low-density parity-check (LDPC) codes that take advantage of this prior information about reliability. It is advantageous to allocate information symbols to more reliable bins in the DD domain. We report simulation results for a Veh-A channel model where it is not possible to resolve all the paths, showing that LDPC coding extends the range of Doppler spreads for which reliable model-free communication is possible. We show that LDPC coding reduces sensitivity to the choice of transmit filter, making bandwidth expansion less necessary. Finally, we compare BER performance of Zak-OTFS to that of a multicarrier approximation (MC-OTFS), showing LDPC coding amplifies the gains previously reported for uncoded transmission.

As the development of 6G technologies progresses, there is a focused effort by international bodies and regulatory agencies to enhance worldwide connectivity, paying special attention to the needs of high-mobility users and networks, such as Mobile Ad-Hoc Networks (MANETs) and Vehicular Ad-Hoc Networks(VANETS) . These advanced systems face significant challenges, particularly the increased demand for rapid channel state information (CSI) feedback due to the fast-changing nature of channel conditions. In environments where traditional time-frequency domain approaches struggle, the adoption of delay-Doppler domain representations, like those used in OTFS (Orthogonal Time Frequency Space) modulation, shows promise for improved stability in mobile scenarios. This paper introduces a novel expression for predicting OTFS channel variations over time and proposes an efficient technique for dynamically updating MIMO (Multiple Input Multiple Output) precoders, enhancing the utility of outdated CSI while minimized signaling overhead and computational complexity. Subsequently, we conduct Monte Carlo simulations to evaluate the performance of OFDM and OTFS MIMO systems within high-mobility environments. These simulations aim to rigorously assess the robustness and efficiency of both modulation techniques under scenarios characterized by rapid user movement and fluctuating channel conditions.

Magnetic recording devices are still competitive in the storage density race with solid-state devices thanks to new technologies such as two-dimensional magnetic recording (TDMR). TDMR offers remarkable storage density increase without the need for new magnetic materials; however, advanced data processing schemes are needed to guarantee reliability. Data patterns where a bit is surrounded by complementary bits at the four positions with Manhattan distance 1 on the TDMR grid are called plus isolation (PIS) patterns, and they are error-prone. Recently, we introduced lexicographically-ordered constrained (LOCO) codes, namely optimal plus LOCO (OP-LOCO) codes, with minimal redundancy that prevent these patterns from being written in a TDMR device. However, in the high-density regime or the low-energy regime (as the device ages), additional error-prone patterns emerge, specifically data patterns where a bit is surrounded by complementary bits at only three positions with Manhattan distance 1, and we call them incomplete plus isolation (IPIS) patterns. In this paper, we present capacity-achieving codes that forbid both PIS and IPIS patterns in TDMR systems with wide read heads. Because of their shape, we collectively call the PIS and IPIS patterns rotated T isolation (RTIS) patterns, and we call the new codes optimal T LOCO (OT-LOCO) codes. We analyze OT-LOCO codes and derive their simple encoding-decoding rule that allows reconfigurability. We also present a novel bridging idea for these codes to further increase the rate. Our simulation results demonstrate that OT-LOCO codes not only remarkably outperform OP-LOCO codes, but also entirely eliminate media noise effects, resulting from error-prone data patterns, at practical TD densities in the range [0.6,0.8) with high rates in the range [0.81,0.83]. At the TD density of 0.8, the OT-LOCO code of rate 0.8267 achieves a frame error rate (bit error rate) performance gain of about 1.15 orders (1.23 orders) of magnitude for all TDMR down (horizontal) tracks compared with the uncoded setting. To further preserve the storage capacity, we suggest using OP-LOCO codes, which have higher rates than OT-LOCO codes, early in the device lifetime, then employing the reconfiguration property to switch to OT-LOCO codes later in the device lifetime. While the point of reconfiguration on the density/energy axis is decided manually at the moment, the next step is to use machine learning to make that decision based on the TDMR device status. Moreover, we introduce another coding scheme to remove RTIS patterns in TDMR systems which offers lower complexity, lower error propagation, and track separation, at the expense of a limited rate loss.

Binary chirps (BCs) are exponentiated 2nd-order Reed-Muller codes, which have interesting geometric and algebraic features, one of which is the close connection to the diagonal part of the Clifford group, which is the 2nd level of the Clifford hierarchy. We develop a novel transvection based method to analyze the diagonal Clifford hierarchy. Using this, we identify a connection of recently proposed generalized BCs with the 3rd level of Clifford hierarchy. Then, we propose two systematic extensions of the BC codebook to an arbitrary Clifford hierarchy level and find their minimum distances. In these extensions, the number of codewords grows exponentially with the hierarchy level. For decoding, we design a low-complexity decoding approach for the extended BCs, using the Howard algorithm for BC decoding as a component. Through simulations, we show that the performance of the proposed low-complexity decoder can achieve performance very close to the exhaustive search with significantly reduced complexity.

Binary Chirp (BC) codebooks consist of ${N^{\left( {{{\log }_2}N + 3} \right)/2}}$ lines in ${\mathbb{C}^N}$, equivalent up to overall phase rotations. Exploiting the underlying algebraic structure, the BCs allow suboptimal decoders with complexity N(logN)2, based on autocorrelations between the received signal and its permuted versions. We analyze the performance of these decoders in additive white Gaussian noise channels, providing lower bounds of decoding error probability, which are tight in the limits of low and high signal-to-noise ratio. Due to the autocorrelation nature of the receiver, the error probability becomes a function of order statistics of χ2-distributed random variables. Our results can be used when dimensioning communication systems where BCs are used as component codes.

The pivotal storage density win achieved by solid-state devices over magnetic devices in 2015 is a result of multiple innovations in physics, architecture, and signal processing. One of the most important innovations in that regard is enabling the storage of more than one bit per cell in the Flash device, i.e., having more than two charge levels per cell. Constrained coding is used in Flash devices to increase reliability via mitigating inter-cell interference that stems from charge propagation among cells. Recently, capacity-achieving constrained codes were introduced to serve that purpose in modern Flash devices, which have more than two levels per cell. While these codes result in minimal redundancy via exploiting the underlying physics, they result in non-negligible complexity increase and access speed limitation since pages cannot be read separately. In this paper, we suggest new constrained coding schemes that have low-complexity and preserve the desirable high access speed in modern Flash devices. The idea is to eliminate error-prone patterns by coding data either only on the left-most page (binary coding) or only on the two left-most pages (4-ary coding) while leaving data on all the remaining pages uncoded. Our coding schemes work for any number of levels$q \geq 4$per cell, offer systematic encoding and decoding, and are capacity-approaching. Since the proposed schemes enable the separation of pages, except the two left-most pages in the case of 4-ary coding, we refer to them as read-and-run (RR) constrained coding schemes as opposed to schemes adopting read-and-wait for other pages. The 4-ary RR coding scheme is introduced in order to limit the rate loss incurred by the binary RR coding schemes, and we show that our 4-ary RR coding scheme is also competitive when it comes to complexity and error propagation. We analyze the new RR coding schemes and discuss their impact on the probability of occurrence of different charge levels. We also demonstrate the performance improvement achieved via RR coding on a practical triple-level cell Flash device.

Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications and data storage systems. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a convolutional manner. The number of partitioned components determines the memory of SC codes. In this paper, we investigate the relation between the performance of SC codes and the density distribution of partitioning matrices. While adopting higher memories results in improved SC code performance, obtaining finite-length, high-performance SC codes with high memory is known to be computationally challenging. We break this computational bottleneck by developing a novel probabilistic framework that obtains (locally) optimal density distributions via gradient descent. Starting from random partitioning matrices abiding by the obtained distribution, we perform low-complexity optimization algorithms that minimize the number of detrimental objects to construct high-memory, high-performance quasi-cyclic SC codes. We apply our framework to various objects of interest, from the simplest short cycles, to more sophisticated objects such as concatenated cycles aiming at finer-grained optimization. Simulation results show that codes obtained through our proposed method notably outperform state-of-the-art SC codes with the same constraint length and optimized SC codes with uniform partitioning. The performance gain is shown to be universal over a variety of channels, from canonical channels such as additive white Gaussian noise and binary symmetric channels, to practical channels underlying flash memory and magnetic recording systems.

The pivotal storage density win achieved by solid-state devices over magnetic devices in 2015 is a result of multiple innovations in physics, architecture, and signal processing. One of the most important innovations in that regard is enabling the storage of more than one bit per cell in the Flash device, i.e., having more than two charge levels per cell. Constrained coding is used in Flash devices to increase reliability via mitigating inter-cell interference that stems from charge propagation among cells. Recently, capacity-achieving constrained codes were introduced to serve that purpose in modern Flash devices, which have more than two levels per cell. While these codes result in minimal redundancy via exploiting the underlying physics, they result in non-negligible complexity increase and access speed limitation since pages cannot be read separately. In this paper, we suggest new constrained coding schemes that have low-complexity and preserve the desirable high access speed in modern Flash devices. The idea is to eliminate error-prone patterns by coding data only on the left-most page while leaving data on all the remaining pages uncoded. Our coding schemes work for any number of levels per cell, offer systematic encoding and decoding, and are capacity-approaching. Since the proposed schemes enable the separation of pages, we refer to them as read-and-run (RR) constrained coding schemes as opposed to schemes adopting read-and-wait for other pages. We analyze the new RR coding schemes and discuss their impact on the probability of occurrence of different charge levels. We also demonstrate the performance improvement achieved via RR coding on a practical triple-level cell Flash device.

The challenge of quantum computing is to combine error resilience with universal computation. There are many finite sets of gates that are universal, and a standard choice is to augment the set of Clifford gates by a non-Clifford unitary such as the T gate. Given a CSS code, we introduce a method of synthesizing all possible diagonal physical gates that preserve the codespace and induce a target logical gate. We denote an 〚n, k = k1− k2, d〛 CSS code $\mathcal{C}$ by $\operatorname{CSS} \left( {X,{\mathcal{C}_2};Z,\mathcal{C}_1^ \bot } \right)$, where the [n, k2] binary code ${\mathcal{C}_2}$ determines the X-stabilizers in $\mathcal{C}$, and the [n, n−k1] binary code $\mathcal{C}_1^ \bot $ determines the Z-stabilizers in $\mathcal{C}$. The diagonal entries of a diagonal physical gate are indexed by binary vectors in $\mathbb{F}_2^n$. We show that a diagonal physical gate preserves the CSS codespace if and only if entries from the same coset of ${\mathcal{C}_2}$ in ${\mathcal{C}_1}$ (same X-logical) are identical. We also show that the target logical operator only specifies ${2^{{k_1}}}$ out of 2ndiagonal entries of the diagonal physical gate. The remaining degrees of freedom can be used to optimize implementation of the physical gate within a particular quantum computing infrastructure. This encompasses optimization with respect to locality of the physical gate, a criterion that is essential to fault tolerance. When the target logical operator is the identity, the physical gates that preserve the CSS code represent noise operators to which the codespace is oblivious. We illustrate our method by providing several examples of code-gate pairs for which the target logical gate is a non-Clifford unitary. The framework is extended to stabilizer codes in https://arxiv.org/abs/2109.13481.

We investigate the theory of affine groups in the context of designing radar waveforms that obey the desired wideband ambiguity function (WAF). The WAF is obtained by correlating the signal with its time-dilated, Doppler-shifted, and delayed replicas. We consider the WAF definition as a coefficient function of the unitary representation of the group a • x + b. This is essentially an algebraic problem applied to the radar waveform design. Prior works on this subject largely analyzed narrow-band ambiguity functions. Here, we show that when the underlying wideband signal of interest is a pulse or pulse train, a tight frame can be built to design that waveform. Specifically, we design the radar signals by minimizing the ratio of bounding constants of the frame in order to obtain lower sidelobes in the WAF. This minimization is performed by building a codebook based on difference sets in order to achieve the Welch bound. We show that the tight frame so obtained is connected with the wavelet transform that defines the WAF.

We consider autocorrelation-based low-complexity decoders for identifying Binary Chirp codewords from noisy signals in N = 2mdimensions. The underlying algebraic structure enables dimensionality reduction from N complex to m binary di- mensions, which can be used to reduce decoding complexity, when decoding is successively performed in the m binary dimensions. Existing low-complexity decoders suffer from poor performance in scenarios with strong noise. This is problematic especially in a vector quantization scenario, where quantization noise power cannot be controlled in the system. We construct two improvements to existing algorithms; a geometrically inspired algorithm based on successive projections, and an algorithm based on adaptive decoding order selection. When combined with a breadth-first list decoder, these algorithms make it possible to approach the performance of exhaustive search with low complexity.

Encoding the scale information explicitly into the representation learned by a convolutional neural network (CNN) is beneficial for many computer vision tasks especially when dealing with multiscale inputs. We study, in this paper, a scaling-translation-equivariant ($\mathcal{ST}$-equivariant) CNN with joint convolutions across the space and the scaling group, which is shown to be both sufficient and necessary to achieve equivariance for the regular representation of the scaling-translation group $\mathcal{ST}$. To reduce the model complexity and computational burden, we decompose the convolutional filters under two pre-fixed separable bases and truncate the expansion to low-frequency components. A further benefit of the truncated filter expansion is the improved deformation robustness of the equivariant representation, a property which is theoretically analyzed and empirically verified. Numerical experiments demonstrate that the proposed scaling-translation-equivariant network with decomposed convolutional filters (ScDCFNet) achieves significantly improved performance in multiscale image classification and better interpretability than regular CNNs at a reduced model size.

Constrained codes are used to prevent errors from occurring in various data storage and data transmission systems. They can help in increasing the storage density of magnetic storage devices, in managing the lifetime of solid-state storage devices, and in increasing the reliability of data transmission over wires. Over the years, designing practical (complexity-wise) capacity-achieving constrained codes has been an area of research gaining significant interest. We recently designed various constrained codes based on lexicographic indexing. We introduced binary symmetric lexicographically-ordered constrained (S-LOCO) codes,$q$-ary asymmetric LOCO (QA-LOCO) codes, and a class of two-dimensional LOCO (TD-LOCO) codes. These families of codes achieve capacity with simple encoding and decoding, and they are easy to reconfigure. We demonstrated that these codes can contribute to notable density and lifetime gains in magnetic recording (MR) and Flash systems, and they find application in other systems too. In this paper, we generalize our work on LOCO codes by presenting a systematic method that guides the code designer to build any constrained code based on lexicographic indexing once the finite set of data patterns to forbid is known. In particular, we connect the set of forbidden patterns directly to the cardinality of the LOCO code and most importantly to the rule that uncovers the index associated with a LOCO codeword. By doing that, we reveal the secret arithmetic of patterns, and make the design of such constrained codes significantly easier. We give examples illustrating the method via codes based on lexicographic indexing from the literature. We then design optimal (rate-wise) constrained codes for the new two-dimensional magnetic recording (TDMR) technology. Over a practical TDMR model, we show notable performance gains as a result of solely applying the new codes. Moreover, we show how near-optimal constrained codes for TDMR can be designed and used to further reduce complexity and error propagation. All the newly introduced LOCO codes are designed using the proposed general method, and they inherit all the desirable properties in our previously designed LOCO codes.

Physical platforms such as trapped ions suffer from coherent noise that does not follow a simple stochastic model. Stochastic errors in quantum systems occur randomly but coherent errors are more damaging since they can accumulate in a particular direction. We consider coherent noise acting transversally, giving rise to an effective error which is a$Z$-rotation on each qubit by some angle$\theta $. Rather than address coherent noise through active error correction, we investigate passive mitigation through decoherence free subspaces. In the language of stabilizer codes, we require the noise to preserve the code space, and to act trivially (as the logical identity operator) on the protected information. Thus, we develop necessary and sufficient conditions for all transversal$Z$-rotations to preserve the code space of a stabilizer code. These conditions require the weight-$2~Z$-stabilizers to cover all the qubits that are in the support of the$X$-component of some stabilizer. Furthermore, the weight-$2~Z$-stabilizers generate a direct product of single-parity-check codes with even block length. By adjusting the sizes of these components, we are able to construct a large family of QECC codes oblivious to coherent noise, one that includes the$[[4L^{2}, 1, 2L]]$Shor codes. The Shor codes are examples of constant excitation codes, where logical qubits are encoded as a code state that is a sum of physical states indexed by binary vectors with the same weight. Constant excitation codes are oblivious to coherent noise since a transversal$Z$-rotation acts as a global phase. We prove that a CSS code is oblivious to coherent noise if and only if it is a constant excitation code, and that if the code is error-detecting, then the (constant) weights in different cosets of the$X$-stabilizers are identical.

We describe in detail the interplay between binary symplectic geometry and notions from quantum computation, with the ultimate goal of constructing highly structured codebooks. The Binary Chirps (BCs) are Complex Grassmannian Lines in$N = 2^{m}$dimensions used in deterministic compressed sensing and random/unsourced multiple access in wireless networks. Their entries are fourth roots of unity and can be described in terms of second order Reed-Muller codes. The Binary Subspace Chirps (BSSCs) are a unique collection of BCs of ranks ranging from$r=0$to$r = m$, embedded in$N$dimensions according to an on-off pattern determined by a rank$r$binary subspace. This yields a codebook that is asymptotically 2.38 times larger than the codebook of BCs, has the same minimum chordal distance as the codebook of BCs, and the alphabet is minimally extended from$\{\pm 1,\pm i\}$to$\{\pm 1,\pm i, 0\}$. Equivalently, we show that BSSCs are stabilizer states, and we characterize them as columns of a well-controlled collection of Clifford matrices. By construction, the BSSCs inherit all the properties of BCs, which in turn makes them good candidates for a variety of applications. For applications in wireless communication, we use the rich algebraic structure of BSSCs to construct a low complexity decoding algorithm that is reliable against Gaussian noise. In simulations, BSSCs exhibit an error probability comparable or slightly lower than BCs, both for single-user and multi-user transmissions.

In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. The recent rise of the blockchain technology is also moving various information systems towards decentralization to achieve high privacy at low costs. While codes with hierarchical locality have been intensively studied in the context of centralized cloud storage due to their effectiveness in reducing the average reading time, those for decentralized storage networks (DSNs) have not yet been discussed. In this paper, we propose a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. This work extends and subsumes our prior work on coding for centralized cloud storage. In particular, our proposed construction not only preserves desirable properties such as scalability and flexibility, which are critical in dynamic networks, but also adapts to arbitrary topologies, a property that is essential in DSNs but has been overlooked in existing works.

Orthogonal Time Frequency Space (OTFS) is a novel framework that processes modulation symbols via a time-independent channel characterized by the delay-Doppler domain. The conventional waveform, orthogonal frequency division multiplexing (OFDM), requires tracking frequency selective fading channels over the time, whereas OTFS benefits from full time-frequency diversity by leveraging appropriate equalization techniques. In this paper, we consider a neural network-based supervised learning framework for OTFS equalization. Learning of the introduced neural network is conducted in each OTFS frame fulfilling an online learning framework: the training and testing datasets are within the same OTFS-frame over the air. Utilizing reservoir computing, a special recurrent neural network, the resulting one-shot online learning is sufficiently flexible to cope with channel variations among different OTFS frames (e.g., due to the link/rank adaptation and user scheduling in cellular networks). The proposed method does not require explicit channel state information (CSI) and simulation results demonstrate a lower bit error rate (BER) than conventional equalization methods in the low signal-to-noise (SNR) regime under large Doppler spreads. When compared with its neural network-based counterparts for OFDM, the introduced approach for OTFS will lead to a better tradeoff between the processing complexity and the equalization performance.

Physical platforms such as trapped ions suffer from coherent noise that does not follow a simple stochastic model. We view coherent errors as rotations about a particular axis, and observe that since they can accumulate coherently over time, they can be more damaging. It is natural to consider coherent noise acting transversally giving rise to an effective error, which is a$Z$-rotation on each qubit by some angle$\theta$. Rather than addressing coherent noise through active error correction, we instead investigate passive mitigation through decoherence free subspaces. In the language of stabilizer codes, we require the noise to preserve the code space, and to act trivially (as the logical identity operator) on the protected information. Thus, we develop necessary and sufficient conditions for all transversal$Z$-rotations to preserve the code space of a stabilizer code. These conditions require the existence of a large number of weight 2$Z$-stabilizers, and together, these weight 2$Z$-stabilizers generate a direct product of single-parity-check codes. By adjusting the size of these components, we are able to construct a large family of CSS codes, oblivious to coherent noise, that includes the$[[4L^{2}, 1,2L]]$Shor codes. Given$m$even and given any$[[n, k, d]]$CSS code, we can construct an$[[mn, k, d^{\prime}\geq d]]$CSS code that is oblivious to coherent noise. This result is generalized to stabilizer codes in [Hu, Liang, Rengaswamy, and Calderbank 2020]. The MacWilliams Identities play a central role in the technical analysis, and classical coding theorists may be interested in connections to classical codes with all weights divisible by some integer$d$.

Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications and data storage systems. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a “convolutional” manner. The number of partitioned components determines the “memory” of SC codes. While adopting higher memories results in improved SC code performance, obtaining optimal SC codes with high memory is known to be hard. In this paper, we investigate the relation between the performance of SC codes and the density distribution of partitioning matrices. We propose a probabilistic framework that obtains (locally) optimal density distributions via gradient descent. Starting from random partitioning matrices abiding by the obtained distribution, we perform low complexity optimization algorithms over the cycle properties to construct high memory, high performance quasi-cyclic SC codes. Simulation results show that codes obtained through our proposed method notably outperform state-of-the-art SC codes with the same constraint length and codes with uniform partitioning.

In various practical systems, certain data patterns are prone to errors if written or transmitted. In magnetic recording and communication over transmission lines, data patterns causing consecutive transitions that are not sufficiently separated are prone to errors. In Flash memory with two levels per cell, data patterns causing high–low–high charge levels on adjacent cells are prone to errors. Constrained codes are used to eliminate error-prone patterns, and they can also achieve other goals. Recently, we introduced efficient binary symmetric lexicographically-ordered constrained (LOCO) codes and asymmetric LOCO (A-LOCO) codes to increase density in magnetic recording systems and lifetime in Flash systems by eliminating the relevant detrimental patterns. Due to their application, LOCO and A-LOCO codes are associated with level-based signaling. Studying the power spectrum of a random signal with certain properties is principal for any storage or transmission system. It reveals important properties such as the average signal power at DC, the bandwidth of the signal, and whether there are discrete power components at certain frequencies. In this paper, we first modify a framework from the literature in order to introduce a method to derive the power spectrum of a sequence of constrained data associated with level-based signaling. We apply our method to infinitely long sequences satisfying symmetric and asymmetric constraints. Next, we show how to generalize the method such that it works for a stream of finite-length codewords as well, thus demonstrating how to overcome the associated finite-length challenges. We use the generalized method to devise closed forms for the spectra of finite-length LOCO and A-LOCO codes from their transition diagrams. Our LOCO and A-LOCO spectral derivations can be performed for any code length and can be extended to other constrained codes. We plot these power spectra, and discuss various important spectral properties for both LOCO and A-LOCO codes. We also briefly discuss an alternative method for deriving the power spectrum and introduce an idea towards reaching the spectra of self-clocked codes.

Flash memory devices are winning the competition for storage density against magnetic recording devices. This outcome results from advances in physics that allow storage of more than one bit per cell, coupled with advances in signal processing that reduce the effect of physical instabilities. Constrained codes are used in storage to avoid problematic patterns, and thus prevent errors from happening. Recently, we introduced binary symmetric lexicographically-ordered constrained codes (LOCO codes) for data storage and data transmission. LOCO codes are capacity-achieving, simple, and can be easily reconfigured. This paper introduces simple constrained codes that support non-binary physical gates in multi, triple, quad, and the currently-in-development penta-level cell (M/T/Q/P-LC) Flash memories. The new codes can be easily modified if problematic patterns change with time. These codes are designed to mitigate inter-cell interference, which is a critical source of error in Flash devices. The occurrence of errors is a consequence of parasitic capacitances in and across floating-gate transistors, resulting in charge propagation from cells being programmed to the highest charge level to neighboring cells being programmed to lower levels or unprogrammed/erased. This asymmetric nature of error-prone patterns distinguishes Flash memories. The new codes are called$q$-ary asymmetric LOCO codes (QA-LOCO codes), and the construction subsumes codes previously designed for single-level cell (SLC) Flash devices (A-LOCO codes). QA-LOCO codes work for a Flash device with any number,$q$, of levels per cell. For$q \geq 4$, we show that QA-LOCO codes can achieve rates greater than$0.95 \log _{2} \!q$input bits per coded symbol. The complexity of encoding and decoding is modest, and reconfiguring a code is as easy as reprogramming an adder. Capacity-achieving rates, affordable encoding-decoding complexity, and ease of reconfigurability support the growing improvement of M/T/Q/P-LC Flash memory devices, as well as lifecycle management as the characteristics of these devices change with time, which increases their lifetime.

Racetrack memory is a promising new non-volatile memory technology, especially because of the density of its 3D implementation. However, for 3D racetrack to reach its potential, certain reliability issues must be overcome. Prior work used per-track encoding to tolerate the shift errors that are unique to racetrack, but no solutions existed for tolerating both shift errors and bit flip errors. We introduce Foosball Coding, which combines per-track coding for shift errors with a novel across-track coding for bit flips. Moreover, our per-track coding scheme methodically explores the design of inter-codeword delimiters and introduces the novel concept of multi-purpose delimiters, in which the existence of multiple delimiter options can be used to provide additional information.

Flash memory devices are winning the competition for storage density against magnetic recording devices. This outcome results from advances in physics that allow storage of more than one bit per cell, coupled with advances in signal processing that reduce the effect of physical instabilities. Constrained codes are used in storage to avoid problematic patterns. Recently, we introduced binary symmetric lexicographically-ordered constrained codes (LOCO codes) for data storage and transmission. This paper introduces simple constrained codes that support non-binary physical gates in multi, triple, quad, and the currently-in-development penta-level cell (M/T/Q/P-LC) Flash memories. The new codes can be easily modified if problematic patterns change with time. These codes are designed to mitigate inter-cell interference, which is a critical source of error in Flash devices. The new codes are called q-ary asymmetric LOCO codes (QA-LOCO codes), and the construction subsumes codes previously designed for single-level cell (SLC) Flash devices (ALOCO codes). QA-LOCO codes work for a Flash device with any number, q, of levels per cell. For q ≥ 4, we show that QA-LOCO codes can achieve rates greater than 0.95log2q information bits per coded symbol. Capacity-achieving rates, affordable encoding-decoding complexity, and ease of reconfigurability support the growing improvement of M/T/Q/P-LC Flash memory devices, as well as lifecycle management as the characteristics of these devices change with time.

We consider codebooks of Complex Grassmannian Lines consisting of Binary Subspace Chirps (BSSCs) in N =2mdimensions. BSSCs are generalizations of Binary Chirps (BCs), their entries are either fourth-roots of unity, or zero. BSSCs consist of a BC in a non-zero subspace, described by an on-off pattern. Exploring the underlying binary symplectic geometry, we provide a unified framework for BSSC reconstruction-both on-off pattern and BC identification are related to stabilizer states of the underlying Heisenberg-Weyl algebra. In a multi-user random access scenario we show feasibility of reliable reconstruction of multiple simultaneously transmitted BSSCs with low complexity.

Universal quantum computation requires the implementation of a logical non-Clifford gate. In this paper, we characterize all stabilizer codes whose code subspaces are preserved under physical T and T†gates. For example, this could enable magic state distillation with non-CSS codes and, thus, provide better parameters than CSS-based protocols. However, among non-degenerate stabilizer codes that support transversal T, we prove that CSS codes are optimal. We also show that triorthogonal codes are, essentially, the only family of CSS codes that realize logical transversal T via physical transversal T. Using our algebraic approach, we reveal new purely-classical coding problems that are intimately related to the realization of logical operations via transversal T. Decreasing monomial codes are also used to construct a code that realizes logical CCZ. Finally, we use Ax's theorem to characterize the logical operation realized on a family of quantum Reed-Muller codes. This result is generalized to finer angle Z-rotations in https://arxiv.org/abs/1910.09333.

The continuous rise of the blockchain technology is moving various information systems towards decentralization. Blockchain-based decentralized storage networks (DSNs) offer significantly higher privacy and lower costs to customers compared with centralized cloud storage associated with specific vendors. Coding is required to retrieve data stored on failing components. While coding solutions for centralized storage have been intensely studied, those for DSNs have not yet been discussed. In this paper, we propose a coding scheme where each node receives extra protection through cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. Our scheme can achieve faster recovery speed compared with existing network coding methods, and can correct more erasure patterns compared with our previous work.

The increasing demand for access to data has led to dramatic increases in data storage densities, and as densities increase, new sources of error appear. Multi-dimensional (MD) graph-based codes are capable of mitigating error sources like interference and channel non-uniformity in dense storage devices. A recent innovation improves the performance of MD spatially-coupled codes that are based on circulants by carefully relocating some circulants to minimize the number of short cycles. However, cycles become more detrimental when they combine together to form more advanced objects, e.g., absorbing sets, including low-weight codewords. In this paper, we show how MD relocations can be exploited to minimize the number of detrimental objects in the graph of an MD code. Moreover, we demonstrate the savings in the number of relocation arrangements earned by focusing on objects rather than their constituent cycles. Our technique is applicable to a wide variety of one-dimensional (OD) codes. Simulation results demonstrate significant lifetime gains achieved by the proposed MD codes on an industry-recommended model for Flash systems, and signal-to-noise ratio gains on an industry-recommended model for magnetic recording systems, both with respect to OD codes with similar parameters. The second order analysis of MD relocations relies on conditions and options for an object, called a pattern, to form a bigger cycle after MD relocations, which are discussed in this paper.

The non-linear binary Kerdock codes are known to be Gray images of certain extended cyclic codes of length codewords by △ z √-1 produces stabilizer states, that are N = 2 over Z4. We show that exponentiating these Z4-valued quantum states obtained using only Clifford unitaries. These states are also the common eigenvectors of commuting Hermitian matrices forming maximal commutative subgroups (MCS) of the Pauli group. We use this quantum description to simplify the derivation of the classical weight distribution of Kerdock codes. Next, we organize the stabilizer states to form N + 1 mutually unbiased bases and prove that automorphisms of the Kerdock code permute their corresponding MCS, thereby forming a subgroup of the Clifford group. When represented as symplectic matrices, this subgroup is isomorphic to the projective special linear group PSL(2, N). We show that this automorphism group acts transitively on the Pauli matrices, which implies that the ensemble is Pauli mixing and hence forms a unitary 2-design. The Kerdock design described here was originally discovered by Cleve et al. (2016), but the connection to classical codes is new which simplifies its description and translation to circuits significantly. Sampling from the design is straightforward, the translation to circuits uses only Clifford gates, and the process does not require ancillary qubits. Finally, we also develop algorithms for optimizing the synthesis of unitary 2-designs on encoded qubits, i.e., to construct logical unitary 2-designs. Software implementations are available at https://github.com/nrenga/symplectic-arxiv18a, which we use to provide empirical gate complexities for up to 16 qubits.

Line codes make it possible to mitigate interference, to prevent short pulses, and to generate streams of bipolar signals with no direct-current (DC) power content through balancing. They find application in magnetic recording (MR) devices, in Flash devices, in optical recording devices, and in some computer standards. This paper introduces a new family of fixed-length, binary constrained codes, named lexicographically-ordered constrained codes (LOCO codes), for bipolar non-return-to-zero signaling. LOCO codes are capacity-achieving, the lexicographic indexing enables simple, practical encoding and decoding, and this simplicity is demonstrated through analysis of circuit complexity. LOCO codes are easy to balance, and their inherent symmetry minimizes the rate loss with respect to unbalanced codes having the same constraints. Furthermore, LOCO codes that forbid certain patterns can be used to alleviate inter-symbol interference in MR systems and inter-cell interference in Flash systems. Numerical results demonstrate a gain of up to 10% in rate achieved by LOCO codes with respect to other practical constrained codes, including run-length-limited codes, designed for the same purpose. Simulation results suggest that it is possible to achieve a channel density gain of about 20% in MR systems by using a LOCO code to encode only the parity bits, limiting the rate loss, of a low-density parity-check code before writing.

The problem of completing high-dimensional matrices from a limited set of observations arises in many big data applications, especially recommender systems. The existing matrix completion models generally follow either a memory- or a model-based approach, whereas geometric matrix completion (GMC) models combine the best from both approaches. Existing deep-learning-based geometric models yield good performance, but, in order to operate, they require a fixed structure graph capturing the relationships among the users and items. This graph is typically constructed by evaluating a pre-defined similarity metric on the available observations or by using side information, e.g., user profiles. In contrast, Markov-random-fields-based models do not require a fixed structure graph but rely on handcrafted features to make predictions. When no side information is available and the number of available observations becomes very low, existing solutions are pushed to their limits. In this article, we propose a GMC approach that addresses these challenges. We consider matrix completion as a structured prediction problem in a conditional random field (CRF), which is characterized by a maximum a posteriori (MAP) inference, and we propose a deep model that predicts the missing entries by solving the MAP inference problem. The proposed model simultaneously learns the similarities among matrix entries, computes the CRF potentials, and solves the inference problem. Its training is performed in an end-to-end manner, with a method to supervise the learning of entry similarities. Comprehensive experiments demonstrate the superior performance of the proposed model compared to various state-of-the-art models on popular benchmark data sets and underline its superior capacity to deal with highly incomplete matrices.

Racetrack memory is an exciting emerging memory technology with the potential to offer far greater capacity and performance than other non-volatile memories. Racetrack memory has an unusual error model, though, which precludes the use of the typical error coding techniques used by architects. In this paper, we introduce GreenFlag, a coding scheme that combines a new construction for Varshamov-Tenegolts codes with specially crafted delimiter bits that are placed between each codeword. GreenFlag is the first coding scheme that is compatible with 3D racetrack, which has the benefit of very high density but the limitation of a single read/write port per track. Based on our implementation of encoding/decoding hardware, we analyze the trade-offs between latency, code length, and code rate; we then use this analysis to evaluate the viability of racetrack at each level of the memory hierarchy.

In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. Codes with hierarchical locality have been intensively studied due to their effectiveness in reducing the average reading time in cloud storage. In this paper, we present the first codes with hierarchical locality that achieve scalability and flexibility in heterogeneous cloud storage using small field size. We propose a double- level construction utilizing so-called Cauchy Reed-Solomon codes. We then develop a triple-level construction based on this double-level code; this construction can be easily generalized into any hierarchical structure with a greater number of layers since it naturally achieves scalability in the cloud storage systems.

We investigate random projections in the context of randomly projected linear discriminant analysis (LDA). We consider the case in which the data of dimension p is randomly projected onto a lower dimensional space before being fed to the classifier. Using fundamental results from random matrix theory and relying on some mild assumptions, we show that the asymptotic performance in terms of probability of misclassification approaches a deterministic quantity that only depends on the data statistics and the dimensions involved. Such results permits to reliably predict the performance of projected LDA as a function of the reduced dimension d <; p and thus helps to determine the minimum d to achieve a certain desired performance. Finally, we validate our results with finite-sample settings drawn from both synthetic data and the popular MNIST dataset.

The binary non-linear Kerdock codes are Gray images of Z4-linear Kerdock codes of length N = 2m. We show that exponentiating z = √-1 by these Z4-valued codewords produces stabilizer states, which are the common eigenvectors of maximal commutative subgroups (MCS) of the Pauli group. We use this quantum description to simplify the proof of the classical weight distribution of Kerdock codes. Next, we partition stabilizer states into N + 1 mutually unbiased bases and prove that automorphisms of the Kerdock code permute the associated MCS. This automorphism group, represented as symplectic matrices, is isomorphic to the projective special linear group PSL(2, N) and forms a unitary 2-design. The design described here was originally discovered by Cleve et al. (2016), but the connection to classical codes is new. This significantly simplifies the description of the design and its translation to circuits.

Line codes make it possible to mitigate interference, to prevent short pulses, and to generate streams of bipolar signals with no direct-current (DC) power content through balancing. They find application in magnetic recording (MR) devices, in Flash devices, and in optical recording devices. This paper introduces a new family of fixed-length, binary constrained codes, named lexicographically-ordered constrained codes (LOCO codes), for bipolar non-return-to-zero signaling. LOCO codes are capacity achieving, the lexicographic indexing enables simple, practical encoding and decoding, and this simplicity is demonstrated through analysis of circuit complexity. Experimental results demonstrate a gain of up to 10% in rate achieved by LOCO codes with respect to practical run-length-limited codes designed for the same purpose. Simulation results suggest that it is possible to achieve channel density gains of about 20% in MR systems by using a LOCO code to encode only the parity bits of a low-density parity-check code before writing.

In order to meet the demands of data-hungry applications, data storage devices are required to be increasingly denser. Various sources of error appear with this increase in density. Multi-dimensional (MD) graph-based codes are capable of mitigating error sources like interference and channel non-uniformity in dense storage devices. Recently, a technique was proposed to enhance the performance of MD spatially-coupled codes that are based on circulants. The technique carefully relocates circulants to minimize the number of short cycles. However, cycles become more detrimental when they combine together to form more advanced objects, e.g., absorbing sets, including low-weight codewords. In this paper, we show how MD relocations can be exploited to minimize the number of detrimental objects in the graph of an MD code. Moreover, we demonstrate the savings in the number of relocation arrangements earned by focusing on objects rather than cycles. Our technique is applicable to a wide variety of one-dimensional (OD) codes. Simulation results reveal significant lifetime gains in practical Flash systems achieved by MD codes designed using our technique compared with OD codes having similar parameters.

Motivated by problems in machine-type wireless communications, we consider codebooks of complex Grassmannian lines in N = 2mdimensions. Binary Chirp (BC) codebooks of prior art are expanded to codebooks of Binary Subspace Chirps (BSSCs), where there is a binary chirp in a subset of the dimensions, while in the remaining dimensions there is a zero. BSSC codebooks have the same minimum distance as BC codebooks, while the cardinality is asymptotically 2.38 times larger. We discuss how BC codebooks can be understood in terms of a subset of the binary symplectic group Sp(2m, 2) in 2m dimensions; Sp(2m, 2) is isomorphic to a quotient group of the Clifford group acting on the codewords in N dimensions. The Bruhat decomposition of Sp(2m, 2) can be described in terms of binary subspaces in m dimensions, with ranks ranging from r = 0 to r = m. We provide a unique parameterization of the decomposition. The BCs arise directly from the full-rank part of the decomposition, while BSSCs are a group code arising from the action of the full group with generic r. The rank of the binary subspace is directly related to the number of zeros (sparsity) in the BSSC. We develop a reconstruction algorithm that finds the correct codeword with O(N log2N) complexity, and present performance results in an additive white Gaussian noise scenario.

Motivated by Fisher divergence, in this paper we present a new set of information quantities which we refer to as gradient information. These measures serve as surrogates for classical information measures such as those based on logarithmic loss, Kullback-Leibler divergence, directed Shannon information, etc. in many data-processing scenarios of interest, and often provide significant computational advantage, improved stability and robustness. As an example, we apply these measures to the Chow-Liu tree algorithm, and demonstrate remarkable performance and significant computational reduction using both synthetic and real data.

Multi-scale spectrum sensing is proposed to overcome the cost of full network state information on the spectrum occupancy of primary users (PUs) in dense multi-cell cognitive networks. Secondary users (SUs) estimate the local spectrum occupancies and aggregate them hierarchically to estimate spectrum occupancy at multiple spatial scales. Thus, SUs obtain fine-grained estimates of spectrum occupancies of nearby cells, more relevant to scheduling tasks, and coarse-grained estimates of those of distant cells. An agglomerative clustering algorithm is proposed to design a cost-effective aggregation tree, matched to the structure of interference, robust to local estimation errors, and delays. Given these multi-scale estimates, the SU traffic is adapted in a decentralized fashion in each cell, to optimize the trade-off among SU cell throughput, interference caused to PUs, and mutual SU interference. Numerical evaluations demonstrate a small degradation in SU cell throughput (up to 15% for a 0 dB interference-to-noise ratio experienced at PUs) compared to a scheme with full network state information, using only one-third of the cost incurred in the exchange of spectrum estimates. The proposed interference-matched design is shown to significantly outperform a random tree design, by providing more relevant information for network control, and a state-of-the-art consensus-based algorithm, which does not leverage the spatio-temporal structure of interference across the network.

Given a collection of strings, each with an associated probability of occurrence, the guesswork of each of them is their position in a list ordered from most likely to least likely, breaking ties arbitrarily. The guesswork is central to several applications in information theory: average guesswork provides a lower bound on the expected computational cost of a sequential decoder to decode successfully the transmitted message; the complementary cumulative distribution function of guesswork gives the error probability in list decoding; the logarithm of guesswork is the number of bits needed in optimal lossless one-to-one source coding; and the guesswork is the number of trials required of an adversary to breach a password protected system in a brute-force attack. In this paper, we consider memoryless string sources that generate strings consisting of independent and identically distributed characters drawn from a finite alphabet, and characterize their corresponding guesswork. Our main tool is the tilt operation on a memoryless string source. We show that the tilt operation on a memoryless string source parametrizes an exponential family of memoryless string sources, which we refer to as the tilted family of the string source. We provide an operational meaning to the tilted families by proving that two memoryless string sources result in the same guesswork on all strings of all lengths if and only if their respective categorical distributions belong to the same tilted family. Establishing some general properties of the tilt operation, we generalize the notions of weakly typical set and asymptotic equipartition property to tilted weakly typical sets of different orders. We use this new definition to characterize the large deviations for all atypical strings and characterize the volume of tilted weakly typical sets of different orders. We subsequently build on this characterization to prove large deviation bounds on guesswork and provide an accurate approximation of its probability mass function.

In multi-user wireless packet networks, interference, typically modeled as packet collision, is the throughput bottleneck. Users become aware of the interference pattern via feedback and use this information for contention resolution and packet retransmission. Conventional random access protocols interrupt communication to resolve contention, which reduces network throughput and increases latency and power consumption. In this paper, we take a different approach, and we develop opportunistic random access protocols rather than pursuing conventional methods. We allow wireless nodes to communicate without interruption and to observe the interference pattern. We then use this interference pattern knowledge and channel statistics to counter the negative impact of interference. We prove the optimality of our protocols using an extremal rank-ratio inequality. An important part of our contributions is the integration of spatial correlation in our assumptions and results. We identify spatial correlation regimes in which inherently outdated feedback becomes as good as idealized instantaneous feedback and correlation regimes in which feedback does not provide any throughput gain. To better illustrate the results, and as an intermediate step, we characterize the capacity region of finite-field spatially correlated interference channels with delayed channel state information at the transmitters.

Deep neural networks have proved very successful on archetypal tasks for which large training sets are available, but when the training data are scarce, their performance suffers from overfitting. Many existing methods of reducing overfitting are data-independent. Data-dependent regularizations are mostly motivated by the observation that data of interest lie close to a manifold, which is typically hard to parametrize explicitly. These methods usually only focus on the geometry of the input data, and do not necessarily encourage the networks to produce geometrically meaningful features. To resolve this, we propose the Low-Dimensional-Manifold-regularized neural Network (LDMNet), which incorporates a feature regularization method that focuses on the geometry of both the input data and the output features. In LDMNet, we regularize the network by encouraging the combination of the input data and the output features to sample a collection of low dimensional manifolds, which are searched efficiently without explicit parametrization. To achieve this, we directly use the manifold dimension as a regularization term in a variational functional. The resulting Euler-Lagrange equation is a Laplace-Beltrami equation over a point cloud, which is solved by the point integral method without increasing the computational complexity. In the experiments, we show that LDMNet significantly outperforms widely-used regularizers. Moreover, LDMNet can extract common features of an object imaged via different modalities, which is very useful in real-world applications such as cross-spectral face recognition.

Diagnosis of melanoma is fraught with uncertainty, and discordance rates among physicians remain high because of the lack of a definitive criterion. Motivated by this challenge, this paper first introduces the Patch Weyl transform (PWT), a 2-dimensional variant of the Weyl transform. It then presents a method for classifying pump-probe images of melanocytic lesions based on the PWT coefficients. Performance of the PWT coefficients is shown to be superior to classification based on baseline intensity, on standard descriptors such as the Histogram of Oriented Gradients (HOG) and Local Binary Patterns (LBP), and on coefficients derived from PCA and Fourier representations of the data.

Filters in a Convolutional Neural Network (CNN) contain model parameters learned from enormous amounts of data. In this paper, we suggest to decompose convolutional filters in CNN as a truncated expansion with pre-fixed bases, namely the Decomposed Convolutional Filters network (DCFNet), where the expansion coefficients remain learned from data. Such a structure not only reduces the number of trainable parameters and computation, but also imposes filter regularity by bases truncation. Through extensive experiments, we consistently observe that DCFNet maintains accuracy for image classification tasks with a significant reduction of model parameters, particularly with Fourier-Bessel (FB) bases, and even with random bases. Theoretically, we analyze the representation stability of DCFNet with respect to input variations, and prove representation stability under generic assumptions on the expansion coefficients. The analysis is consistent with the empirical observations.

Quantum error-correcting codes can be used to protect qubits involved in quantum computation. This requires that logical operators acting on protected qubits be translated to physical operators (circuits) acting on physical quantum states. We propose a mathematical framework for synthesizing physical circuits that implement logical Clifford operators for stabilizer codes. Circuit synthesis is enabled by representing the desired physical Clifford operator in CN×Nas a 2m×2m binary sym-plectic matrix, where N=2m. We show that for an [[ m, m-k ]] stabilizer code every logical Clifford operator has 2k(k+1)/2symplectic solutions, and we enumerate them efficiently using symplectic transvections. The desired circuits are then obtained by writing each of the solutions as a product of elementary symplectic matrices. For a given operator, our assembly of all of its physical realizations enables optimization over them with respect to a suitable metric. Our method of circuit synthesis can be applied to any stabilizer code, and this paper provides a proof of concept synthesis of universal Clifford gates for the well-known [[ 6,4,2 ]] code. Programs implementing our algorithms can be found at https://github.com/nrenga/symplectic-arxiv18a.

We study the network-wide neighbour discovery problem in wireless networks in which each node in a network must discovery the network interface addresses (NIAs) of its neighbour. We work within the rapid on-off division duplex framework proposed by Guo and Zhang in [5] in which all nodes are assigned different on-off signatures which allow them listen to the transmissions of neighbouring nodes during their off slots; this leads to a compressed sensing problem at each node with a collapsed codebook determined by a given node's transmission signature. We propose sparse Kerdock matrices as codebooks for the neighbour discovery problem. These matrices share the same row space as certain Delsarte-Goethals frames based upon Reed Muller codes, whilst at the same time being extremely sparse. We present numerical experiments using two different compressed sensing recovery algorithms, One Step Thresholding (OST) and Normalised Iterative Hard Thresholding (NIHT). For both algorithms, a higher proportion of neighbours are successfully identified using sparse Kerdock matrices compared to codebooks based on Reed Muller codes with random erasures as proposed in [13]. We argue that the improvement is due to the better interference cancellation properties of sparse Kerdock matrices when collapsed according to a given node's transmission signature. We show by explicit calculation that the coherence of the collapsed codebooks resulting from sparse Kerdock matrices remains near-optimal.

In multi-user wireless packet networks interference is the throughput bottleneck. Users become aware of the interference pattern via feedback and use this information for contention resolution and for packet retransmission. We consider networks with spatially correlated wireless links, and we develop an opportunistic automatic repeat request function for these networks. We prove the optimality of our protocol using an extremal rank-ratio inequality for spatially correlated channels.

We extend the lifetime of Flash memory in embedded processors by exploiting the fact that data from sensors is inherently analog. Prior work in the computer architecture community has assumed that all data is digital and has overlooked the opportunities available when working with analog data, such as the data recorded by sensors. In this paper, we introduce redundancy into the quantization of sensor data in order to provide several alternative representations. Notably, we tradeoff distortion-the difference between the sensed analog value and the digital quantization of that value-to improve lifetime. Our simulations show that when combining rate, distortion, and lifetime tradeoffs we can extend Flash lifetime at a far smaller capacity cost compared to prior work. More specifically the simulated system shows that it is possible to achieve up to 2.75× less capacity cost compared to redundant Flash memory and 1.29× less capacity cost compared to the state of the art coding schemes.

In backscatter communications, ultra-low power devices signal by modulating the reflection of radio frequency signals emitted from an external source. Unlike conventional one-way communication, the backscatter channel experiences unique self-interference and spread Doppler clutter. Run-length limited (RLL) codes provide a method for spectrum shaping that requires no hardware changes to the communicating devices. The proposed coding framework is suitable for any arbitrarily-shaped pulse train or continuous wave reader waveform. It exploits the unique channel Doppler spread statistics to offer a trade-off between interference rejection and data rate. Analysis shows that code rates of 1 and 4/5 are achievable when dealing with low spread Doppler channels, which is an improvement over the current rate 1/2 with current mainstream backscatter communication techniques. Simulation results with realistic channel assumptions are analyzed and discussed to confirm the theoretical analysis.

In this paper, a multi-scale approach to spectrum sensing in cognitive cellular networks is proposed. In order to overcome the huge cost incurred in the acquisition of full network state information, a hierarchical scheme is proposed, based on which local state estimates are aggregated up the hierarchy to obtain aggregate state information at multiple scales, which are then sent back to each cell for local decision making. Thus, each cell obtains fine-grained estimates of the channel occupancies of nearby cells, but coarse-grained estimates of those of distant cells. The performance of the aggregation scheme is studied in terms of the trade-off between the throughput achievable by secondary users and the interference generated by the activity of these secondary users to primary users. In order to account for the irregular structure of interference patterns arising from path loss, shadowing, and blockages, which are especially relevant in millimeter wave networks, a greedy algorithm is proposed to find a multi-scale aggregation tree to optimize the performance. It is shown numerically that this tailored hierarchy outperforms a regular tree construction by 60%.

In this paper, we introduce Jenga, a new scheme for protecting 3D DRAM, specifically high bandwidth memory (HBM), from failures in bits, rows, banks, channels, dies, and TSVs. By providing redundancy at the granularity of a cache block-rather than across blocks, as in the current state of the art-Jenga achieves greater error-free performance and lower error recovery latency. We show that Jenga's runtime is on average only 1.03x the runtime of our Baseline across a range of benchmarks. Additionally, for memory intensive benchmarks, Jenga is on average 1.11x faster than prior work.

A locally repairable code with availability has the property that every code symbol can be recovered from multiple, disjoint subsets of other symbols of small size. In particular, a code symbol is said to have (r, t)-availability if it can be recovered from t disjoint subsets, each of size at most r. A code with availability is said to be rate optimal, if its rate is maximum among the class of codes with given locality, availability, and alphabet size. This paper focuses on rate-optimal binary, linear codes with small availability, and makes three contributions. First, it establishes tight upper bounds on the rate of binary linear codes with (r, 2) and (2, 3) availability. Second, it establishes a uniqueness result for binary rate-optimal codes, showing that for certain classes of binary linear codes with (r, 2) and (2, 3)-availability, any rate-optimal code must be a direct sum of shorter rate-optimal codes. Finally, it presents a class of locally repairable codes associated with convex polyhedra, especially, focusing on the codes associated with the Platonic solids. It demonstrates that these codes are locally repairable with t = 2, and that the codes associated with (geometric) dual polyhedra are (coding theoretic) duals of each other.

A new two-dimensional modulation technique called Orthogonal Time Frequency Space (OTFS) modulation designed in the delay-Doppler domain is introduced. Through this design, which exploits full diversity over time and frequency, OTFS coupled with equalization converts the fading, time-varying wireless channel experienced by modulated signals such as OFDM into a time-independent channel with a complex channel gain that is roughly constant for all symbols. Thus, transmitter adaptation is not needed. This extraction of the full channel diversity allows OTFS to greatly simplify system operation and significantly improves performance, particular in systems with high Doppler, short packets, and large antenna arrays. Simulation results indicate at least several dB of block error rate performance improvement for OTFS over OFDM in all of these settings. In addition these results show that even at very high Dopplers (500 Km/h), OTFS approaches channel capacity through linear scaling of throughput with the MIMO order, whereas the performance of OFDM under typical design parameters breaks down completely.

An information-theoretic projection design framework is proposed, of interest for feature design and compressive measurements. Both Gaussian and Poisson measurement models are considered. The gradient of a proposed information-theoretic metric (ITM) is derived, and a gradient-descent algorithm is applied in design; connections are made to the information bottleneck. The fundamental solution structure of such design is revealed in the case of a Gaussian measurement model and arbitrary input statistics. This new theoretical result reveals how ITM parameter settings impact the number of needed projection measurements, with this verified experimentally. The ITM achieves promising results on real data, for both signal recovery and classification.

Motivated by embedded systems and datacenters that require long-life components, we extend the lifetime of Flash memory using rewriting codes that allow for multiple writes to a page before it needs to be erased. Although researchers have previously explored rewriting codes for this purpose, we make two significant contributions beyond prior work. First, we remove the assumption of idealized -- and unrealistically optimistic -- Flash cells used in prior work on endurance codes. Unfortunately, current Flash technology has a non-ideal interface, due to its underlying physical design, and does not, for example, allow all seemingly possible increases in a cell's level. We show how to provide the ideal multi-level cell interface, by developing a virtual Flash cell, and we evaluate its impact on existing endurance codes. Our second contribution is our development of novel endurance codes, called Methuselah Flash Codes (MFC), that provide better cost/lifetime trade-offs than previously studied codes.

We develop a general framework for compressive linear-projection measurements with side information. Side information is an additional signal correlated with the signal of interest. We investigate the impact of side information on classification and signal recovery from low-dimensional measurements. Motivated by real applications, two special cases of the general model are studied. In the first, a joint Gaussian mixture model is manifested on the signal and side information. The second example again employs a Gaussian mixture model for the signal, with side information drawn from a mixture in the exponential family. Theoretical results on recovery and classification accuracy are derived. The presence of side information is shown to yield improved performance, both theoretically and experimentally.

The quantum erasure channel is the simplest example of a quantum communication channel and its information capacity is known precisely. The subclass of quantum error-correcting codes called stabilizer codes is known to contain capacity-achieving sequences for the quantum erasure channel, but no efficient method is known to construct these sequences. In this article, we explicitly describe a capacity-achieving code sequence for the quantum erasure channel. In particular, we show that Calderbank-Shor-Steane (CSS) stabilizer codes constructed from self-orthogonal binary linear codes are capacity-achieving on the quantum erasure channel if the binary linear codes are capacity-achieving on the binary erasure channel. Recently, Reed-Muller codes were shown to achieve capacity on classical erasure channels. Using this, we show that CSS codes constructed from binary Reed-Muller codes achieve the capacity of the quantum erasure channel. The capacity-achieving nature of these CSS codes is also explained from a GF(4) perspective.

An information-theoretic framework is presented for estimating the number of labeled samples needed to train a classifier in a parametric Bayesian setting. Ideas from rate-distortion theory are used to derive bounds for the average L1or L∞distance between the learned classifier and the true maximum a posteriori classifier in terms of familiar information-theoretic quantities and the number of training samples available. The maximum a posteriori classifier is viewed as a random source, labeled training data are viewed as a finite-rate encoding of the source, and the L1or L∞Bayes risk is viewed as the average distortion. The result is a framework dual to the well-known probably approximately correct (PAC) framework. PAC bounds characterize worst-case learning performance of a family of classifiers whose complexity is captured by the Vapnik-Chervonenkis (VC) dimension. The rate-distortion framework, on the other hand, characterizes the average-case performance of a family of data distributions in terms of a quantity called the interpolation dimension, which represents the complexity of the family of data distributions. The resulting bounds do not suffer from the pessimism typical of the PAC framework, particularly when the training set is small.

Fast fading wireless networks with delayed knowledge of the channel state information have received significant attention in recent years. An exception is networks where channels are spatially correlated. This paper characterizes the capacity region of two-user erasure interference channels with delayed knowledge of the channel state information and spatially correlated channels. There are instances where spatial correlation eliminates any potential gain from delayed channel state information and instances where it enables the same performance that is possible with instantaneous knowledge of channel state. The key is an extremal entropy inequality for spatially correlated channels that separates the two types of instances. It is also shown that to achieve the capacity region, each transmitter only needs to rely on the delayed knowledge of the channels to which it is connected.

Recently, sequences of error-correcting codes with doubly-transitive permutation groups were shown to achieve capacity on erasure channels under symbol-wise maximum a posteriori (MAP) decoding. From this, it follows that Reed-Muller and primitive narrow-sense BCH codes achieve capacity in the same setting. In this article, we extend this result to a large family of cyclic codes by considering codes whose permutation groups satisfy a condition weaker than double transitivity. The article combines two simple technical contributions. First, we show that the transition width of a monotone boolean function is O(1/log k), where k is the size of the smallest orbit induced by its symmetry group. The proof is based on Talagrand's lower bound on influences for monotone boolean functions. Second, we consider the extrinsic information transfer (EXIT) function of an Fq-linear cyclic code whose blocklength N divides qt- 1 and is coprime with q - 1. We show that this EXIT function is a monotone boolean function whose symmetry group contains no orbits of size smaller than the smallest prime divisor of t. Combining these, we show that sequences of cyclic codes, whose blocklengths satisfy the above conditions, achieve capacity on the q-ary erasure channel if all prime divisors of t tend to infinity.

This paper offers a characterization of fundamental limits on the classification and reconstruction of high-dimensional signals from low-dimensional features, in the presence of side information. We consider a scenario where a decoder has access both to linear features of the signal of interest and to linear features of the side information signal; while the side information may be in a compressed form, the objective is recovery or classification of the primary signal, not the side information. The signal of interest and the side information are each assumed to have (distinct) latent discrete labels; conditioned on these two labels, the signal of interest and side information are drawn from a multivariate Gaussian distribution that correlates the two. With joint probabilities on the latent labels, the overall signal-(side information) representation is defined by a Gaussian mixture model. By considering bounds to the misclassification probability associated with the recovery of the underlying signal label, and bounds to the reconstruction error associated with the recovery of the signal of interest itself, we then provide sharp sufficient and/or necessary conditions for these quantities to approach zero when the covariance matrices of the Gaussians are nearly low rank. These conditions, which are reminiscent of the well-known Slepian-Wolf and Wyner-Ziv conditions, are the function of the number of linear features extracted from signal of interest, the number of linear features extracted from the side information signal, and the geometry of these signals and their interplay. Moreover, on assuming that the signal of interest and the side information obey such an approximately low-rank model, we derive the expansions of the reconstruction error as a function of the deviation from an exactly low-rank model; such expansions also allow the identification of operational regimes, where the impact of side information on signal reconstruction is most relevant. Our framework, which offers a principled mechanism to integrate side information in high-dimensional data problems, is also tested in the context of imaging applications. In particular, we report state-of-theart results in compressive hyperspectral imaging applications, where the accompanying side information is a conventional digital photograph.

We study the capacity region of two-user erasure interference channels with local delayed channel state information at the transmitters. In our model, transmitters have local mismatched outdated knowledge of the channel gains. We propose a transmission strategy that only relies on the delayed knowledge of the outgoing links at each transmitter and achieves the outer bound for the scenario in which transmitters learn the entire channel state with delay. Our result reveals the subset of the channel state information that affects the capacity region the most. We also identify cases in which local delayed knowledge of the channel state does not provide any gain over the zero knowledge assumption. To do so, we revisit a long-known intuition about interference channels that as long as the marginal distributions at the receivers are conserved, the capacity remains the same. We take this intuition and impose a certain spatial correlation among channel gains such that the marginal distributions remain unchanged. Then, we provide an outer bound on the capacity region of the channel with correlation that matches the capacity region when transmitters do not have access to channel state information.

In this paper, a multiscale approach to spectrum sensing in cognitive cellular networks is analyzed. Observing that wireless interference decays with distance, and that estimating the entire spectrum occupancy across the network entails substantial energy cost and communication overhead, a protocol for distributed spectrum estimation is defined by which secondary users maintain fine-grained estimates of the spectrum occupancy of nearby cells, but coarse-grained estimates of that of distant cells. This is accomplished by arranging the cellular network into a hierarchy of increasingly coarser macro-cells and having secondary users fuse local spectrum estimates up the hierarchy. The spectrum occupancy is modeled as a Markov process, and the system is optimized by defining a probabilistic framework for spectrum sensing and information exchange that balances improvements in spectrum estimation against energy costs. The performance of the multiscale scheme is evaluated numerically, showing that it offers substantial improvements in energy efficiency over local estimation. On the other hand, it is shown that schemes that attempt to estimate the state of the whole network perform poorly, due to the excessive cost of performing information exchange with far away cells, and to the fact that, knowing the spectrum occupancy of distant cells, which experience low interference levels, results in a small increase in reward.

High dimensional data is modeled using low-rank subspaces, and the probability of misclassification is expressed in terms of the principal angles between subspaces. The form taken by this expression motivates the design of a new feature extraction method that enlarges inter-class separation, while preserving intra-class structure. The method can be tuned to emphasize different features shared by members within the same class. Classification performance is compared to that of state-of-the-art methods on synthetic data and on the real face database. The probability of misclassification is decreased when intra-class structure is taken into account.

A novel multi-scale dictionary based Bayesian reconstruction algorithm is proposed for compressive X-ray imaging, which encodes the material's spectrum by Poisson measurements. Inspired by recently developed compressive X-ray imaging systems [1], this work aims to recover the material's spectrum from the compressive coded image by leveraging a reference spectrum library. Instead of directly using the huge and redundant library as a dictionary, which is cumbersome in computation and difficult for selecting those active dictionary atoms, a multi-scale tree structured dictionary is refined from the spectrum library, and following this a Bayesian reconstruction algorithm is developed. Experimental results on real data demonstrate superior performance in comparison with traditional methods.

The Poisson Factor Analysis (PFA) is applied to recover signals from a Poisson compressive sensing system. Motivated by the recently developed compressive X-ray imaging system, Coded Aperture Coherent Scatter Spectral Imaging (CACSSI) [1], we propose a new Bayesian reconstruction algorithm. The proposed Poisson-Gamma (PG) approach uses multiple measurements to refine our knowledge on both sensing matrix and background noise to overcome the uncertainties and inaccuracy of the hardware system. Therefore, a collaborative compressive X-ray image reconstruction algorithm is proposed under a Bayesian framework. Experimental results on real data show competitive performance in comparison with point estimation based methods.

In this paper, we apply the Weyl transform to represent the vocalization of marine mammals. In contrast to other popular representation methods, such as the MFCC and the Chirplet transform, the Weyl transform captures the global information of signals. This is especially useful when the signal has low order polynomial phase. We can reconstruct the signal from the coefficients obtained from the Weyl transform, and perform classification based on these coefficients. Experimental results show that classification using features extracted from the Weyl transform outperforms the MFCC and the Chirplet transform on our collected whales data.

This paper introduces a new ESPRIT-based algorithm to estimate the direction-of-arrival of an arbitrary degree polynomial-phase signal with a single acoustic vector-sensor. The proposed time-invariant ESPRIT algorithm is based on a matrix-pencil pair derived from the time-delayed data-sets collected by a single acoustic vector-sensor. This approach requires neither a prior knowledge of the polynomial-phase signal's coefficients nor a prior knowledge of the polynomial-phase signal's frequency-spectrum. Furthermore, a preprocessing technique is proposed to incorporate the single-forgetting-factor algorithm and multiple-forgetting-factor adaptive tracking algorithm to track a polynomial-phase signal using one acoustic vector sensor. Simulation results verify the efficacy of the proposed direction finding and source tracking algorithms.

Many recent efforts have been devoted to designing sophisticated deep learning structures, obtaining revolutionary results on benchmark datasets. The success of these deep learning methods mostly relies on an enormous volume of labeled training samples to learn a huge number of parameters in a network; therefore, understanding the generalization ability of a learned deep network cannot be overlooked, especially when restricted to a small training set, which is the case for many applications. In this paper, we propose a novel deep learning objective formulation that unifies both the classification and metric learning criteria. We then introduce a geometry-aware deep transform to enable a non-linear discriminative and robust feature transform, which shows competitive performance on small training sets for both synthetic and real-world data. We further support the proposed framework with a formal (K, ϵ)-robustness analysis.

Guesswork forms the mathematical framework for quantifying computational security subject to brute-force determination by query. In this paper, we consider guesswork subject to a per-symbol Shannon entropy budget. We introduce inscrutability rate as the asymptotic rate of increase in the exponential number of guesses required of an adversary to determine one or more secret strings. We prove that the inscrutability rate of any string-source supported on a finite alphabet χ, if it exists, lies between the per-symbol Shannon entropy constraint and log |χ|. We further prove that the inscrutability rate of any finite-order Markov string-source with hidden statistics remains the same as the unhidden case, i.e., the asymptotic value of hiding the statistics per each symbol is vanishing. On the other hand, we show that there exists a string-source that achieves the upper limit on the inscrutability rate, i.e., log |χ|, under the same Shannon entropy budget.

This paper offers a characterization of performance limits for classification and reconstruction of high-dimensional signals from noisy compressive measurements, in the presence of side information. We assume the signal of interest and the side information signal are drawn from a correlated mixture of distributions/components, where each component associated with a specific class label follows a Gaussian mixture model (GMM). We provide sharp sufficient and/or necessary conditions for the phase transition of the misclassification probability and the reconstruction error in the low-noise regime. These conditions, which are reminiscent of the well-known Slepian-Wolf and Wyner-Ziv conditions, are a function of the number of measurements taken from the signal of interest, the number of measurements taken from the side information signal, and the geometry of these signals and their interplay.

This paper studies the performance associated with the classification of linear subspaces corrupted by noise with a mismatched classifier. In particular, we consider a problem where the classifier observes a noisy signal, the signal distribution conditioned on the signal class is zero-mean Gaussian with low-rank covariance matrix, and the classifier knows only the mismatched parameters in lieu of the true parameters. We derive an upper bound to the misclassification probability of the mismatched classifier and characterize its behaviour. Specifically, our characterization leads to sharp sufficient conditions that describe the absence of an error floor in the low-noise regime, and that can be expressed in terms of the principal angles and the overlap between the true and the mismatched signal subspaces.

We consider linear cyclic codes with the locality property, or locally recoverable codes (LRC codes). A family of LRC codes that generalizes the classical construction of Reed-Solomon codes was constructed in a recent paper by I. Tamo and A. Barg (IEEE Trans. IT, no. 8, 2014). In this paper we focus on the optimal cyclic codes that arise from the general construction. We give a characterization of these codes in terms of their zeros, and observe that there are many equivalent ways of constructing optimal cyclic LRC codes over a given field. We also study subfield subcodes of cyclic LRC codes (BCH-like LRC codes) and establish several results about their locality and minimum distance.

The coherence time of a wireless channel is often smaller than the delay with which channel state information is available at transmitters. In this paper, we aim to find the most important subset of the channel state information that transmitters need to learn with delay. We characterize the capacity region of the two-user interference channel with local delayed channel state information at transmitters. We propose a transmission strategy that only relies on the delayed knowledge of the outgoing links at each transmitter and achieves the outer-bound for the scenario in which transmitters learn the entire channel state with delay. We also show that the delayed knowledge of the outgoing links is the minimum delayed knowledge that is required to outperform the no knowledge assumption.

Classical compressive sensing typically assumes a single measurement, and theoretical analysis often relies on corresponding concentration-of-measure results. There are many real-world applications involving multiple compressive measurements, from which the underlying signals may be estimated. In this paper, we establish a new concentration-of-measure inequality for a block-diagonal structured random compressive sensing matrix with Rademacher-ensembles. We discuss applications of this newly-derived inequality to two appealing compressive multiple-measurement models: for Gaussian and Poisson systems. In particular, Johnson-Lindenstrauss-type results and a compressed-domain classification result are derived for a Gaussian multiple-measurement model. We also propose, as another contribution, theoretical performance guarantees for signal recovery for multi-measurement Poisson systems, via the inequality.

This paper proposes a framework for learning features that are robust to data variation, which is particularly important when only a limited number of trainingsamples are available. The framework makes it possible to tradeoff the discriminative value of learned features against the generalization error of the learning algorithm. Robustness is achieved by encouraging the transform that maps data to features to be a local isometry. This geometric property is shown to improve (K, \epsilon)-robustness, thereby providing theoretical justification for reductions in generalization error observed in experiments. The proposed optimization frameworkis used to train standard learning algorithms such as deep neural networks. Experimental results obtained on benchmark datasets, such as labeled faces in the wild,demonstrate the value of being able to balance discrimination and robustness.

The measurement matrix employed in compressive sensing typically cannot be known precisely a priori and must be estimated via calibration. One may take multiple compressive measurements, from which the measurement matrix and underlying signals may be estimated jointly. This is of interest as well when the measurement matrix may change as a function of the details of what is measured. This problem has been considered recently for Gaussian measurement noise, and here we develop this idea with application to Poisson systems. A collaborative maximum likelihood algorithm and alternating proximal gradient algorithm are proposed, and associated theoretical performance guarantees are established based on newly derived concentration-of-measure results. A Bayesian model is then introduced, to improve flexibility and generality. Connections between the maximum likelihood methods and the Bayesian model are developed, and example results are presented for a real compressive X-ray imaging system.

The linear model, in which a set of observations is assumed to be given by a linear combination of columns of a matrix (often termed a dictionary), has long been the mainstay of the statistics and signal processing literature. One particular challenge for inference under linear models is understanding the conditions on the dictionary under which reliable inference is possible. This challenge has attracted renewed attention in recent years, since many modern inference problems (e.g, high-dimensional statistics and compressed sensing) deal with the underdetermined setting, in which the number of observations is much smaller than the number of columns in the dictionary. This paper makes several contributions for this setting when the set of observations is given by a linear combination of a small number of groups of columns of the dictionary, termed the block-sparse case. First, it specifies conditions on the dictionary under which most block submatrices of the dictionary (often termed block subdictionaries) are well conditioned. This result is fundamentally different from prior work on block-sparse inference because: 1) it provides conditions that can be explicitly computed in polynomial time; 2) the given conditions translate into near-optimal scaling of the number of columns of the block subdictionaries as a function of the number of observations for a large class of dictionaries; and 3) it suggests that the spectral norm, rather than the column/block coherences of the dictionary, fundamentally limits the scaling of dimensions of the well-conditioned block subdictionaries. Second, in order to help understand the significance of this result in the context of block-sparse inference, this paper investigates the problems of block-sparse recovery and block-sparse regression in underdetermined settings. In both of these problems, this paper utilizes its result concerning conditioning of block subdictionaries and establishes that near-optimal block-sparse recovery and block-sparse regression is possible for a large class of dictionaries as long as the dictionary satisfies easily computable conditions and the coefficients describing the linear combination of groups of columns can be modeled through a mild statistical prior. Third, the paper reports extensive numerical experiments that highlight the effects of different measures of the dictionary in block-sparse inference problems.

We derive fundamental limits on the reliable classification of linear and affine subspaces from noisy, linear features. Drawing an analogy between discrimination among subspaces and communication over vector wireless channels, we define two Shannon-inspired characterizations of asymptotic classifier performance. First, we define the classification capacity, which characterizes the necessary and sufficient conditions for vanishing misclassification probability as the signal dimension, the number of features, and the number of subspaces to be discriminated all approach infinity. Second, we define the diversity-discrimination tradeoff, which, by analogy with the diversity-multiplexing tradeoff of fading vector channels, characterizes relationships between the number of discernible subspaces and the misclassification probability as the feature noise power approaches zero. We derive upper and lower bounds on these quantities which are tight in many regimes. Numerical results, including a face recognition application, validate the results in practice.

This paper studies conditions for high-dimensional inference when the set of observations is given by a linear combination of a small number of groups of columns of a design matrix, termed the “block-sparse” case. In this regard, it first specifies conditions on the design matrix under which most of its block submatrices are well conditioned. It then leverages this result for average-case analysis of high-dimensional block-sparse recovery and regression. In contrast to earlier works, the results of this paper are fundamentally different because (i) they provide conditions on arbitrary designs that can be explicitly computed in polynomial time, (ii) the provided conditions translate into near-optimal scaling of the number of observations with the number of active blocks of the design matrix, and (iii) they suggest that the spectral norm, rather than the column/block coherences, of the design matrix fundamentally limits the performance of computational methods in high-dimensional settings.

Early detection and treatment of psychiatric disorders on children has shown significant impact in their subsequent development and quality of life. The assessment of psychopathology in childhood is commonly carried out by performing long comprehensive interviews such as the widely used Preschool Age Psychiatric Assessment (PAPA). Unfortunately, the time required to complete a full interview is too long to apply it at the scale of the actual population at risk, and most of the population goes undiagnosed or is diagnosed significantly later than desired. In this work, we aim to learn from unique and very rich previously collected PAPA examples the inter-correlations between different questions in order to provide a reliable risk analysis in the form of a much shorter interview. This helps to put such important risk analysis at the hands of regular practitioners, including teachers and family doctors. We use for this purpose the alternating decision trees algorithm, which combines decision trees with boosting to produce small and interpretable decision rules. Rather than a binary prediction, the algorithm provides a measure of confidence in the classification outcome. This is highly desirable from a clinical perspective, where it is preferable to abstain a decision on the low-confidence cases and recommend further screening. In order to prevent over-fitting, we propose to use network inference analysis to predefine a set of candidate question with consistent high correlation with the diagnosis. We report encouraging results with high levels of prediction using two independently collected datasets. The length and accuracy of the developed method suggests that it could be a valuable tool for preliminary evaluation in everyday care.

Using Shannon theory, we derive fundamental, asymptotic limits on the classification of low-dimensional subspaces from compressive measurements. We identify a syntactic equivalence between the classification of subspaces and the communication of codewords over non-coherent, multiple-antenna channels, from which we derive sharp bounds on the number of classes that can be discriminated with low misclassification probability as a function of the signal dimensionality and the signal-to-noise ratio. While the bounds are asymptotic in the limit of high dimension, they provide intuition for classifier design at finite dimension. We validate this intuition via an application to face recognition.

We investigate design of general nonlinear functions for mapping high-dimensional data into a lower-dimensional (compressive) space. The nonlinear measurements are assumed contaminated by additive Gaussian noise. Depending on the application, we are either interested in recovering the high-dimensional data from the nonlinear compressive measurements, or performing classification directly based on these measurements. The latter case corresponds to classification based on nonlinearly constituted and noisy features. The nonlinear measurement functions are designed based on constrained mutual-information optimization. New analytic results are developed for the gradient of mutual information in this setting, for arbitrary input-signal statistics. We make connections to kernel-based methods, such as the support vector machine. Encouraging results are presented on multiple datasets, for both signal recovery and classification. The nonlinear approach is shown to be particularly valuable in high-noise scenarios.

Codes for storage systems aim to minimize the repair locality, which is the number of disks (or nodes) that participate in the repair of a single failed disk. Simultaneously, the code must sustain a high rate, operate on a small finite field to be practically significant and be tolerant to a large number of erasures. To this end, we construct new families of binary linear codes that have an optimal dimension (rate) for a given minimum distance and locality. Specifically, we construct cyclic codes that are locally repairable for locality 2 and distances 2, 6 and 10. In doing so, we discover new upper bounds on the code dimension, and prove the optimality of enabling local repair by provisioning disjoint groups of disks. Finally, we extend our construction to build codes that have multiple repair sets for each disk.

We study the exact-repair tradeoff between storage and repair bandwidth in distributed storage systems. We give new inner bounds for the tradeoff region and provide code constructions that achieve these bounds.

Repurposing tools and intuitions from Shannon theory, we derive fundamental limits on the reliable classification of high-dimensional signals from low-dimensional features. We focus on the classification of linear and affine subspaces and suppose the features to be noisy linear projections. Leveraging a syntactic equivalence of discrimination between subspaces and communications over vector wireless channels, we derive asymptotic bounds on classifier performance. First, we define the classification capacity, which characterizes necessary and sufficient relationships between the signal dimension, the number of features, and the number of classes to be discriminated, as all three quantities approach infinity. Second, we define the diversitydiscrimination tradeoff, which characterizes relationships between the number of classes and the misclassification probability as the signal-to-noise ratio approaches infinity. We derive inner and outer bounds on these measures, revealing precise relationships between signal dimension and classifier performance.

We provide a rigorous mathematical analysis of two communication strategies: soft decode-and-forward (soft-DF) for relay channels and soft partial interference-cancelation (soft-IC) for interference channels. Both strategies involve soft estimation, which assists the decoding process. We consider LDPC codes, not because of their practical benefits, but because of their analytic tractability, which enables an asymptotic analysis similar to random coding methods of information theory. Unlike some works on the closely-related demodulate-and-forward, we assume non-memoryless, code-structure-aware estimation. With soft-DF, we develop simultaneous density evolution to bound the decoding error probability at the destination. This result applies to erasure relay channels. In one variant of soft-DF, the relay applies Wyner-Ziv coding to enhance its communication with the destination, borrowing from compress-and-forward. To analyze soft-IC, we adapt existing techniques for iterative multiuser detection, and focus on binary-input additive white Gaussian noise interference channels. We prove that optimal point-to-point codes are unsuitable for soft-IC, as well as for all strategies that apply partial decoding to improve upon single-user detection and multiuser detection, including Han-Kobayashi.

Distributed storage systems employ codes to provide resilience to failure of multiple storage disks. In particular, an (n, k) maximum distance separable (MDS) code stores k symbols in n disks such that the overall system is tolerant to a failure of up to n - k disks. However, access to at least k disks is still required to repair a single erasure. To reduce repair bandwidth, array codes are used where the stored symbols or packets are vectors of length ℓ. The MDS array codes have the potential to repair a single erasure using a fraction 1/(n - k) of data stored in the remaining disks. We introduce new methods of analysis, which capitalize on the translation of the storage system problem into a geometric problem on a set of operators and subspaces. In particular, we ask the following question: for a given (n, k), what is the minimum vector-length or subpacketization factor ℓ required to achieve this optimal fraction? For exact recovery of systematic disks in an MDS code of low redundancy, i.e., k/n > 1/2, the best known explicit codes have a subpacketization factor ℓ, which is exponential in k. It has been conjectured that for a fixed number of parity nodes, it is in fact necessary for ℓ to be exponential in k. In this paper, we provide a new log-squared converse bound on k for a given ℓ, and prove that k ≤ 2 log2I(logδℓ + 1), for an arbitrary number of parity nodes r = n - k, where δ = r/(r - 1).

A generalization of Bregman divergence is developed and utilized to unify vector Poisson and Gaussian channel models, from the perspective of the gradient of mutual information. The gradient is with respect to the measurement matrix in a compressive-sensing setting, and mutual information is considered for signal recovery and classification. Existing gradient-of-mutual-information results for scalar Poisson models are recovered as special cases, as are known results for the vector Gaussian model. The Bregman-divergence generalization yields a Bregman matrix, and this matrix induces numerous matrix-valued metrics. The metrics associated with the Bregman matrix are detailed, as are its other properties. The Bregman matrix is also utilized to connect the relative entropy and mismatched minimum mean squared error. Two applications are considered: 1) compressive sensing with a Poisson measurement model and 2) compressive topic modeling for analysis of a document corpora (word-count data). In both of these settings, we use the developed theory to optimize the compressive measurement matrix, for signal recovery and classification.

Some recent memory technologies, including phase change memory (PCM), have lifetime reliabilities that are affected by write operations. We propose the use of coset coding to extend the lifetimes of these memories. The key idea of coset coding is that it performs a one-to-many mapping from each dataword to a coset of vectors, and having multiple possible vectors provides the flexibility to choose the vector to write that optimizes lifetime. Our technique, FlipMin, uses coset coding and, for each write, selects the vector that minimizes the number of bits that must flip. We also show how FlipMin can be synergistically combined with the ability to tolerate bit erasures. Thus, our techniques help to prevent bits from wearing out and can then tolerate those bits that do wear out.

Compressive Sensing is possible when the sensing matrix acts as a near isometry on signals of interest that can be sparsely or compressively represented. The attraction of greedy algorithms such as Orthogonal Matching Pursuit is their simplicity. However they fail to take advantage of both the structure of the sensing matrix and any prior information about the sparse signal. This paper introduces an oblique projector to matching pursuit algorithms to enhance detection of a component that is present in the signal by reducing interference from other candidate components based on prior information about the signal as well as the structure of the sensing matrix. Numerical examples demonstrate that performance as a function of SNR is superior to conventional matching pursuit.

We consider the problem of linear projection design for incoherent optical imaging systems. We propose a computationally efficient method to obtain effective measurement kernels that satisfy the physical constraints imposed by an optical system, starting first from arbitrary kernels, including those that satisfy a less demanding power constraint. Performance is measured in terms of mutual information between the source input and the projection measurement, as well as reconstruction error for real world images. A clear improvement in the quality of image reconstructions is shown with respect to both random and adaptive projection designs in the literature.

Compressed sensing (CS) theory promises one can recover real-valued sparse signal from a small number of linear measurements. Motivated by network monitoring with link failures, we for the first time consider the problem of recovering signals that contain both real-valued entries and corruptions, where the real entries represent transmission delays on normal links and the corruptions represent failed links. Unlike conventional CS, here a measurement is real-valued only if it does not include a failed link, and it is corrupted otherwise. We prove that O((d + 1)max(d, k) log n) nonadaptive measurements are enough to recover all n-dimensional signals that contain k nonzero real entries and d corruptions. We provide explicit constructions of measurements and recovery algorithms. We also analyze the performance of signal recovery when the measurements contain errors.

In this paper, computer-based techniques for stylistic analysis of paintings are applied to the five panels of the 14th century Peruzzi Altarpiece by Giotto di Bondone. Features are extracted by combining a dual-tree complex wavelet transform with a hidden Markov tree (HMT) model. Hierarchical clustering is used to identify stylistic keywords in image patches, and keyword frequencies are calculated for sub-images that each contains many patches. A generative hierarchical Bayesian model learns stylistic patterns of keywords; these patterns are then used to characterize the styles of the sub-images; this in turn, permits to discriminate between paintings. Results suggest that such unsupervised probabilistic topic models can be useful to distill characteristic elements of style.

Codes for distributed storage systems are often designed to sustain failure of multiple storage disks. Specifically, an (n, k) MDS code stores k symbols in n disks such that the overall system is tolerant to a failure of up to n - k disks. However, access to at least k disks is still required to repair a single erasure. To reduce repair bandwidth, array codes are used where the stored symbols or packets are vectors of length ℓ. MDS array codes can potentially repair a single erasure using a fraction l/(n - k) of data stored in the surviving nodes. We ask the following question: for a given (n, k), what is the minimum vector-length or sub-packetization factor ℓ required to achieve this optimal fraction? For exact recovery of systematic disks in an MDS code of low redundancy, i.e. k/n > 1/2, the best known explicit codes [1] have a sub-packetization factor I which is exponential in k. It has been conjectured [2] that for a fixed number of parity nodes, it is in fact necessary for ℓ to be exponential in k. In this paper, we provide new converse bounds on k for a given ℓ We prove that k ≤ ℓ2for an arbitrary but fixed number of parity nodes r = n ™ k. For the practical case of 2 parity nodes, we prove a stronger result that k ≤ 4ℓ.

This paper presents fundamental limits associated with compressive classification of Gaussian mixture source models. In particular, we offer an asymptotic characterization of the behavior of the (upper bound to the) misclassification probability associated with the optimal Maximum-A-Posteriori (MAP) classifier that depends on quantities that are dual to the concepts of diversity gain and coding gain in multi-antenna communications. The diversity, which is shown to determine the rate at which the probability of misclassification decays in the low noise regime, is shown to depend on the geometry of the source, the geometry of the measurement system and their interplay. The measurement gain, which represents the counterpart of the coding gain, is also shown to depend on geometrical quantities. It is argued that the diversity order and the measurement gain also offer an optimization criterion to perform dictionary learning for compressive classification applications.

Motivated by applications in high-dimensional signal processing, we derive fundamental limits on the performance of compressive linear classifiers. By analogy with Shannon theory, we define the classification capacity, which quantifies the maximum number of classes that can be discriminated with low probability of error, and the diversity-discrimination tradeoff, which quantifies the tradeoff between the number of classes and the probability of classification error. For classification of Gaussian mixture models, we identify a duality between classification and communications over non-coherent multiple-antenna channels. This duality allows us to characterize the classification capacity and diversity-discrimination tradeoff using existing results from multiple-antenna communication. We also identify the easiest possible classification problems, which correspond to low-dimensional subspaces drawn from an appropriate Grassmann manifold.

We consider design of linear projection measurements for a vector Poisson signal model. The projections are performed on the vector Poisson rate, $X\in\mathbb{R}_+^n$, and the observed data are a vector of counts, $Y\in\mathbb{Z}_+^m$. The projection matrix is designed by maximizing mutual information between $Y$ and $X$, $I(Y;X)$. When there is a latent class label $C\in\{1,\dots,L\}$ associated with $X$, we consider the mutual information with respect to $Y$ and $C$, $I(Y;C)$. New analytic expressions for the gradient of $I(Y;X)$ and $I(Y;C)$ are presented, with gradient performed with respect to the measurement matrix. Connections are made to the more widely studied Gaussian measurement model. Example results are presented for compressive topic modeling of a document corpora (word counting), and hyperspectral compressive sensing for chemical classification (photon counting).

In this paper, we investigate the problem of compressed learning, i.e. learning directly in the compressed domain. In particular, we provide tight bounds demonstrating that the linear kernel SVMs classifier in the measurement domain, with high probability, has true accuracy close to the accuracy of the best linear threshold classifier in the data domain. Furthermore, we indicate that for a family of well-known deterministic compressed sensing matrices, compressed learning is provided on the fly. Finally, we support our claims with experimental results in the texture analysis application.

This paper is motivated by the challenge of high fidelity processing of images using a relatively small set of projection measurements. This is a problem of great interest in many sensing applications, for example where high photodetector counts are precluded by a combination of available power, form factor and expense. The emerging methods of dictionary learning and compressive sensing offer great potential for addressing this challenge. Combining these methods requires that the signals of interest be representable as a sparse combination of elements of some dictionary. This paper develops a method that aligns the discriminative power of such a dictionary with the physical limitations of the imaging system. Alignment is accomplished by designing a projection matrix that exposes and then aligns the modes of the noise with those of the dictionary. The design algorithm is obtained by modifying an algorithm for designing the pre-filter to maximize the rate and reliability of a Multiple Input Multiple Output (MIMO) communications channel. The difference is that in the communications problem a source is being matched to a channel, whereas in the imaging problem a channel, or equivalently the noise covariance, is being matched to a source. Our results shown that using the proposed communications design framework we can reduce reconstruction error between 20%, after only 20 projections of a 28 × 28 image, and 10% after 100 projections. Furthermore, we noticeably see the superior quality of the reconstructed images.

We consider the problem of reconstructing a data stream from a small subset of its entries, where the data stream is assumed to lie in a low-dimensional linear subspace, possibly corrupted by noise. It is also important to track the change of underlying subspace for many applications. This problem can be viewed as a sequential low-rank matrix completion problem in which the subspace is learned in an online fashion. The proposed algorithm, called Parallel Estimation and Tracking by REcursive Least Squares (PETRELS), identifies the underlying low-dimensional subspace via a recursive procedure for each row of the subspace matrix in parallel, and then reconstructs the missing entries via least-squares estimation if required. PETRELS outperforms previous approaches by discounting observations in order to capture long-term behavior of the data stream and be able to adapt to it. Numerical examples are provided for direction-of-arrival estimation and matrix completion, comparing PETRELS with state of the art batch algorithms.

Melanoma detection relies on visual inspection of skin samples under the microscope via a qualitative set of indicators, causing large discordance among pathologists. New developments in pump-probe imaging enable the extraction of melanin intensity levels from skin samples and provide baseline qualitative figures for melanoma detection and classification. However, such basic figures do not capture the diverse types of cellular structure that distinguish different stages of melanoma. In this paper, we propose an initial approach for feature extraction for classification purposes via Hidden Markov Tree models trained on skin sample melanin intensity images. Our experimental results show that the proposed features provide a mathematical microscope that is able to better discriminate cellular structure, enabling successful classification of skin samples that are mislabeled when the baseline melanin intensity qualitative figures are used.

We introduce an approach to gossip algorithms that exploits three aspects of the wireless medium: superposition, broadcast, and power control. Instead of sending pairwise messages between neighbors on a fixed network topology, we construct gossip algorithms in which nodes can simultaneously recover multiple neighbors' messages and in which nodes can adjust the set of their neighbors by adjusting transmit power. We present two averaging algorithms, each based on a hierarchical clustering of the network. In the first algorithm, clusters of nodes transmit their estimates locally and randomly select a representative node for communications at the next level. In the second, each cluster mutually averages and then cooperatively transmits at the next level. For path-loss environments, these schemes achieve order-optimal or near order-optimal performance.

In this paper, we present a method of detecting the range and Doppler phase of a point target using multiple antennas. As a key illustrative example, we consider a 4 × 4 system employing a unitary matrix waveform set, e.g., formed from Golay complementary sequences. When a non-negligible Doppler shift is induced by the target motion, the waveform matrix formed from the complementary sequences is no longer unitary, resulting in significantly degraded target range estimates. To solve this problem, we adopt a subspace based approach exploiting the observation that the receive matrix formed from matched filtering of the reflected waveforms has a (non-trivial) null-space. Through processing of the waveforms with the appropriate vector from the null-space, we can significantly improve the range detection performance. Also, another very important target aspect is the velocity with which the target is moving, and to determine that, the exact Doppler phase shift induced by the target motion needs to be estimated with reasonable accuracy. To accomplish this task, we develop a strategy that uses the MUSIC algorithm to estimate the Doppler phase, and we use simulations to show that the phase estimates obtained are reasonably accurate even at low SNRs.

The role of random measurement in compressive sensing is analogous to the role of random codes in coding theory. In coding theory, decoders that can correct beyond the minimum distance of a code allow random codes to achieve the Shannon limit. In compressed sensing, the counterpart of minimum distance is the spark of the measurement matrix, i.e., the size of the smallest set of linearly dependent columns. This paper constructs a family of measurement matrices where the columns are formed by exponentiating codewords from a classical binary error-correcting code of block length M. The columns can be partitioned into mutually unbiased bases, and the spark of the corresponding measurement matrix is shown to be O(√M) by identifying a configuration of columns that plays a role similar to that of the Dirac comb in classical Fourier analysis. Further, an explicit basis for the null space of these measurement matrices is given in terms of indicator functions of binary self-dual codes. Reliable reconstruction of k-sparse inputs is shown for k of order M/log(M) which is best possible and far beyond the worst case lower bound provided by the spark.

We consider the recovery of an underlying signal $\mathbf{x}\in\mathbb{C}^m$ based on projection measurements of the form $\mathbf{y}=\mathbf{M}\mathbf{x}+\mathbf{w}$, where $\mathbf{y}\in\mathbb{C}^\ell$ and $\mathbf{w}$ is measurement noise; we are interested in the case $\ell\ll m$. It is assumed that the signal model $p(\mathbf{x})$ is known and that $\mathbf{w}\sim\mathcal{CN}(\mathbf{w};\boldsymbol{0},\bf \Sigma_w)$ for known $\bf \Sigma_w$. The objective is to design a projection matrix $\mathbf{M}\in\mathbb{C}^{\ell\times m}$ to maximize key information-theoretic quantities with operational significance, including the mutual information between the signal and the projections $\mathcal{I}(\mathbf{x};\mathbf{y})$ or the Rényi entropy of the projections $\mbox{h}_\alpha \left( \mathbf{y} \right)$ (Shannon entropy is a special case). By capitalizing on explicit characterizations of the gradients of the information measures with respect to the projection matrix, where we also partially extend the well-known results of Palomar and Verdú from the mutual information to the Rényi entropy domain, we reveal the key operations carried out by the optimal projection designs: mode exposure and mode alignment. Experiments are considered for the case of compressive sensing (CS) applied to imagery. In this context, we provide a demonstration of the performance improvement possible through the application of the novel projection designs in relation to conventional ones, as well as justification for a fast online projection design method with which state-of-the-art adaptive CS signal recovery is achieved.

In this paper, we study a practical coding scheme for the dying binary erasure channel (DBEC), which is a binary erasure channel (BEC) subject to a random fatal failure. We consider the rateless codes and optimize the degree distribution to maximize the average recovery probability. In particular, we first study the upper bound of the average recovery probability, based on which we define the objective function as the gap between the upper bound and the average recovery probability achieved by a particular degree distribution. We then seek the optimal degree distribution by minimizing the objective function. A simple and heuristic approach is also proposed to provide a suboptimal but good degree distribution. Simulation results are presented to show the significant performance gain over the conventional LT codes.

Code diversity integrates space-time coding with beamforming by using a small number of feedback bits to select from a family of space-time codes. Different codes lead to different induced channels at the receiver, where Channel State Information (CSI) is used to instruct the transmitter how to choose the code. Feedback can be combined with sub-optimal low complexity decoding of the component codes to match Maximum-Likelihood (ML) decoding performance of any individual code in the family. It can also be combined with ML decoding of the component codes to improve performance beyond ML decoding performance of any individual code. Prior analysis of code diversity did not take into account the effect of the mobile speed and the delay in the feedback channel. This paper demonstrates the practicality of code diversity in space-time coded systems by showing that performance gains based on instantaneous feedback are largely preserved when long-range prediction of time-varying correlated fading channels is employed to compensate for the effect of the feedback delay. To maintain prediction accuracy for realistic SNR, noise reduction that employs oversampled pilots is used prior to fading prediction. We also propose a robust low pilot rate method that utilizes interleaving to improve the spectral efficiency. Simulations are presented for two channel models: the conventional Jakes model and a realistic physical channel model where the parameters associated with the reflectors vary in time and the arrival rays have different strengths and asymmetric arrival angles.

As it becomes common for wireless service providers (WSP) to employ multiple heterogeneous radio access technologies (RAT), the management of the combined resources across multiple RATs arises as an important issue. The WSP's objective is to assign different users to the different RATs so as to maximize network capacity (or total utility) while ensuring that individual users' quality of service (QoS) requirements are met. In this paper, we consider this resource allocation problem for two scenarios: voice communication and video communication. For voice communication, we propose a stable and optimal assignment scheme based on the deferred acceptance algorithm for both static and online cases. For video communication, identifying the NP-hardness of the problem, we propose and compare a set of heuristic algorithms including a low-complexity, high-performance scheme.

This paper introduces a divide and conquer approach to the design of transmit and receive filters for communication over a Multiple Input Multiple Output (MIMO) Gaussian channel subject to an average power constraint. It involves conversion to a set of parallel scalar channels, possibly with very different gains, followed by coding per sub-channel (i.e. over time) rather than coding across sub-channels (i.e. over time and space). The loss in performance is negligible at high signal-to-noise ratio (SNR) and not significant at medium SNR. The advantages are reduction in signal processing complexity and greater insight into the SNR thresholds at which a channel is first allocated power. This insight is a consequence of formulating the optimal power allocation in terms of an upper bound on error rate that is determined by parameters of the input lattice such as the minimum distance and kissing number. The resulting thresholds are given explicitly in terms of these lattice parameters. By contrast, when the optimization problem is phrased in terms of maximizing mutual information, the solution is mercury waterfilling, and the thresholds are implicit.

Technological constraints severely limit the rate at which analog-to digital converters can reliably sample signals. Recently, Tropp et al. proposed an architecture, termed the random demodulator (RD), that attempts to overcome this obstacle for sparse bandlimited signals. One integral component of the RD architecture is a white noise like, bipolar modulating waveform that changes polarity at a rate equal to the signal bandwidth. Since there is a hardware limitation to how fast analog waveforms can change polarity without undergoing shape distortion, this leads to the RD also having a constraint on the maximum allowable bandwidth. In this paper, an extension of the RD, termed the constrained random demodulator (CRD), is pro posed that bypasses this bottleneck by replacing the original modulating waveform with a run-length limited (RLL) modulating wave form that changes polarity at a slower rate than the signal bandwidth. One of the main contributions of the paper is establishing that the CRD, despite employing a modulating waveform with correlations, enjoys some theoretical guarantees for certain RLL waveforms. In addition, for a given sampling rate and rate of change in the modulating waveform polarity, numerical simulations confirm that the CRD, using an appropriate RLL waveform, can sample a signal with an even wider bandwidth without a significant loss in performance.

The aim of compressed sensing is to recover attributes of sparse signals using very few measurements. Given an overall bit budget for quantization, this paper demonstrates that there is value to redundant measurement. The measurement matrices considered here are required to have the property that signal recovery is still possible even after dropping certain subsets of D measurements. It introduces the concept of a measurement matrix that is weakly democratic in the sense that the amount of information about the signal carried by each of the designated D-subsets is the same. Examples of deterministic measurement matrices that are weakly democratic are constructed by exponentiating codewords from the binary second order Reed Muller code. The value in rejecting D measurements that are on average larger, is to be able to provide a finer grid for vector quantization of the remaining measurements, even after discounting the original budget by the bits used to identify the reject set. Simulation results demonstrate that redundancy improves recovery SNR, sometimes by a wide margin. Optimum performance occurs when a significant fraction of measurements are rejected.

This paper relates the style of 16th century Flemish paintings by Goossen van der Weyden (GvdW) to the style of preliminary sketches or underpaintings made prior to executing the painting. Van der Weyden made underpaintings in markedly different styles for reasons as yet not understood by art historians. The analysis presented here starts from a classification of the underpaintings into four distinct styles by experts in art history. Analysis of the painted surfaces by a combination of wavelet analysis, hidden Markov trees and boosting algorithms can distinguish the four underpainting styles with greater than 90% cross-validation accuracy. On a subsequent blind test this classifier provided insight into the hypothesis by art historians that different patches of the finished painting were executed by different hands.

Precoding has been extensively studied for point-to-point communications, including the problems of constructing the precoding codebook and selecting the best precoder. This paper investigates precoding for a multicast channel in which a base station is sending the same information to all users and each user sends back the index of its best precoding matrix. It is assumed that users do not collaborate and that no channel state information is known at the base station. Optimization problems are formulated to reduce the packet drop rate. A set of probabilistic algorithms that effectively reduce the average package drop rate are presented. It is shown numerically that these new schemes lead to significant improvements.

The sparse signal processing literature often uses random sensing matrices to obtain performance guarantees. Unfortunately, in the real world, sensing matrices do not always come from random processes. It is therefore desirable to evaluate whether an arbitrary matrix, or frame, is suitable for sensing sparse signals. To this end, the present paper investigates two parameters that measure the coherence of a frame: worst-case and average coherence. We first provide several examples of frames that have small spectral norm, worst-case coherence, and average coherence. Next, we present a new lower bound on worst-case coherence and compare it to the Welch bound. Later, we propose an algorithm that decreases the average coherence of a frame without changing its spectral norm or worst-case coherence. Finally, we use worst-case and average coherence, as opposed to the Restricted Isometry Property, to garner near-optimal probabilistic guarantees on both sparse signal detection and reconstruction in the presence of noise. This contrasts with recent results that only guarantee noiseless signal recovery from arbitrary frames, and which further assume independence across the nonzero entries of the signal-in a sense, requiring small average coherence replaces the need for such an assumption.

The Restricted Isometry Property or RIP introduced by Candes and Tao requires an n × p dictionary to act as a near isometry on all k-sparse signals. This paper provides a very simple condition under which a dictionary Φ(C) obtained by exponentiating codewords from a binary linear code C satisfies the RIP with high probability. The method is to bound the difference between the dictionary Φ(C) and a second dictionary A generated by a random Bernoulli process which is known to satisfy the RIP with high probability. The difference Δ - Φ(C) is controlled by the covering radius of C, a fundamental parameter that is bounded above by the number of weights in the dual code C⊥(the external distance of C). The main result complements a more sophisticated asymptotic analysis by Babadi and Tarokh of the distribution of eigenvalues of random submatrices of Φ(C). In this analysis, divergence from the distribution corresponding to the full Bernoulli matrix depends on a different fundamental parameter of C, namely the minimum distance of the dual code C⊥.

This paper addresses spectrally-efficient multiantenna multi-carrier uplink transmission scenarios where the users overlap in time and frequency and are separated using spatial processing at the base station. The robustness of the proposed training sequences to residual carrier frequency offset and phase noise is evaluated analytically. This analysis reveals an interesting design tradeoff between the Peak-to-Average Power Ratio of a training sequence and the increase in channel estimation mean squared error over the ideal case when these two impairments are not present.

This paper investigates the effect of eavesdroppers on network connectivity, using a wiretap model and percolation theory. The wiretap model captures the effect of eavesdroppers on link security. A link exists between two nodes only if the secrecy capacity of that link is positive. Network connectivity is defined in a percolation sense, i.e., connectivity exists if an infinite connected component exists in the corresponding secrecy graph. We consider uncertainty in location of eavesdroppers, which is modeled directly at the network level as correlated failures in the secrecy graph. Our approach attempts to bridge the gap between physical layer security under uncertain channel state information and network level connectivity under secrecy constraints. For square and triangular lattice secrecy graphs, we obtain bounds on the percolation threshold, which is the critical value of the probability of occurrence of an eavesdropper, above which network connectivity does not exist. For Poisson secrecy graphs, degree distribution and mean value of upper and lower bounds on node degree are obtained. Further, inner and outer bounds on the achievable region for network connectivity are obtained. Both analytic and simulation results show that uncertainty in location of eavesdroppers has a dramatic effect on network connectivity in a secrecy graph.

A two-user interference channel is considered where each transmitter has access to a part of the information intended to the other destination. A primary objective is to maximize the information rates, by exploring the cooperation between the transmitters for interference mitigation, based on the partial side information. It is clear that full cooperation between the transmitters is not possible since each transmitter has only a part of the side information. With this insight, several “layered coding” schemes, consisting of binning and superposition at different stages, are developed. These schemes are are carefully built on coding strategies for the classical interference channel and node cooperation mechanisms. In particular, two layered coding schemes, which are based on a combination of MIMO broadcast coding and the Han-Kobayashi (HK) coding, are thoroughly studied : The first one, namely layered coding with binning, makes heavy use of the Gelfand-Pinsker binning and the HK coding and the second one, namely layered superposition coding, involves superposition coding over different tiers. Rate regions corresponding to the proposed schemes are derived. Then the application of these coding schemes are illustrated for the Gaussian case and numerical results corroborate that the proposed layered coding schemes yield substantial gains at high SNR.

The Golden code is a full-rate full-diversity space-time code which has been incorporated in the IEEE 802.16 (WiMAX) standard. The worst case complexity of a tree-based sphere decoder for a square QAM constellation is O(N3), where N is the size of the underlying QAM constellation; the worst case will dominate average decoding complexity on any channel with a significant line of sight component. In this paper, we present a simple algorithm with quadratic complexity for decoding the Golden code that can be employed by mobile terminals with either one or two receive antennas, that is resilient to near singularity of the channel matrix, and that gives essentially maximum likelihood (ML) performance. Dual use is an advantage, since there will likely be some IEEE 802.16 mobile terminals with one receive antenna and some with two antennas. The key to the quadratic algorithm is a maximization of the likelihood function with respect to one of the pair of signal points conditioned on the other. This choice is made by comparing the determinants of two covariance matrices, and the underlying geometry of the Golden code guarantees that one of these choices is good with high probability.

In this paper, we design MMSE-optimal training sequences for multi-user MIMO-OFDM systems with an arbitrary number of transmit antennas and an arbitrary number of training symbols. It addresses spectrally-efficient uplink transmission scenarios where the users overlap in time and frequency and are separated using spatial processing at the base station. The robustness of the proposed training sequences to residual carrier frequency offset and phase noise is evaluated. This analysis reveals an interesting design tradeoff between the peak-to-average power ratio of a training sequence and the increase in channel estimation mean squared error over the ideal case when these two impairments are not present.

The use of beamforming to enable higher data rates in telecommunications is widely appreciated, but performance gains are typically calculated assuming delay-free feedback from the receiver and neglecting processing time. This paper introduces a mathematical framework based on outage probability that measures the extent to which current channel state information is accurate. Performance gains from beamforming can then be evaluated as a function of the currency of system state. Results are provided for Multiple Input Single Output (MISO) and for Multiuser Multiple Input Multiple Output (MU-MIMO) systems. Outage probabilities and effective diversity orders are calculated for widely used methods of beamforming such as Transmit Antenna Selection as a function of the speed of channel variation.

Compressed sensing theory suggests that successful inversion of an image of the physical world from its modal parameters can be achieved at measurement dimensions far lower than the image dimension, provided that the image is sparse in an a priori known basis. The assumed basis for sparsity typically corresponds to a gridding of the parameter space, e.g., an DFT grid in spectrum analysis. However, in reality no physical field is sparse in the DFT basis or in an a priori known basis. No matter how finely we grid the parameter space the sources may not lie in the center of the grid cells and there is always mismatch between the assumed and the actual bases for sparsity. In this paper, we study the sensitivity of compressed sensing (basis pursuit to be exact) to mismatch between the assumed and the actual sparsity bases. Our mathematical analysis and numerical examples show that the performance of basis pursuit degrades considerably in the presence of basis mismatch.

In this paper, we present a method for detecting a point target using multiple antennas when the relative motion between the receivers and the target induces a non-negligible Doppler shift. As a key illustrative example, we consider a 4×4 system employing a unitary matrix waveform set, e.g., formed from Golay complementary sequences. When a non-negligible Doppler shift is induced by the target motion, the wave-form matrix formed from the complementary sequences is no longer unitary, resulting in significantly degraded target range estimates. To solve this problem, we adopt a subspace based approach exploiting the observation that the receive matrix formed from matched filtering of the reflected waveforms has a (non-trivial) null-space. Through processing of the waveforms with the appropriate vector from the null-space, we can significantly improve the detection performance. We provide simulation results to confirm the theoretical analysis.

This paper provides a framework for designing space-time codes to take advantage of a small number of feedback bits from the receiver. The new codes are based on circulant matrices and simple conditions are derived that guarantee full rate and full diversity. In the absence of feedback, Symbol Error Rate (SER) performance is shown to be similar to that of Diagonal Algebraic Space-Time (DAST) codes, both for Maximum Likelihood (ML) decoding and for suboptimal linear decoding. Decoding complexity of circulant codes is similar to the DAST codes and encoding is slightly less complex. In the presence of a small number of feedback bits from the receiver the circulant construction is shown to permit integration of space-time coding with a fixed set of beams by simply advancing the phase on one of the antennas. This integration is not possible within the DAST framework. Integration of space-time codes with beamforming makes it possible to achieve ML decoding performance with only linear decoding complexity or to improve upon ML performance of the original code.

The central goal of compressive sensing is to reconstruct a signal that is sparse or compressible in some basis using very few measurements. However reconstruction is often not the ultimate goal and it is of considerable interest to be able to deduce attributes of the signal from the measurements without explicitly reconstructing the full signal. This paper solves the blind source separation problem not in the high dimensional data domain, but in the low dimensional measurement domain. It develops a Bayesian inference framework that integrates hidden Markov models for sources with compressive measurement. Posterior probabilities are calculated using a Markov Chain Monte Carlo (MCMC) algorithm. Simulation results are provided for one-dimensional signals and for two-dimensional images, where hidden Markov tree models of the wavelet coefficients are considered. The integrated Bayesian framework is shown to outperform standard approaches where the mixtures are separated in the data domain.

This paper investigates pricing of Internet connectivity services in the context of a monopoly ISP selling broadband access to consumers. We first study the optimal combination of flat-rate and usage-based access price components for maximization of ISP revenue, subject to a capacity constraint on the data-rate demand. Next, we consider time-varying consumer utilities for broadband data rates that can result in uneven demand for data-rate over time. Practical considerations limit the viability of altering prices over time to smoothen out the demanded data-rate. Despite such constraints on pricing, our analysis reveals that the ISP can retain the revenue by setting a low usage fee and dropping packets of consumer demanded data that exceed capacity. Regulatory attention on ISP congestion management discourages such ``technical" practices and promotes economics based approaches. We characterize the loss in ISP revenue from an economics based approach. Regulatory requirements further impose limitations on price discrimination across consumers, and we derive the revenue loss to the ISP from such restrictions. We then develop partial recovery of revenue loss through non-linear pricing that does not explicitly discriminate across consumers. While determination of the access price is ultimately based on additional considerations beyond the scope of this paper, the analysis here can serve as a benchmark to structure access price in broadband access networks.

The problem of model selection arises in a number of contexts, such as compressed sensing, subset selection in linear regression, estimation of structures in graphical models, and signal denoising. This paper generalizes the notion of incoherence in the existing literature on model selection and introduces two fundamental measures of coherence-termed as the worst-case coherence and the average coherence-among the columns of a design matrix. In particular, it utilizes these two measures of coherence to provide an in-depth analysis of a simple one-step thresholding (OST) algorithm for model selection. One of the key insights offered by the ensuing analysis is that OST is feasible for model selection as long as the design matrix obeys an easily verifiable property. In addition, the paper also characterizes the model-selection performance of OST in terms of the worst-case coherence, μ, and establishes that OST performs near-optimally in the low signal-to-noise ratio regime for N × C design matrices with μ ≈ O(N-1/2). Finally, in contrast to some of the existing literature on model selection, the analysis in the paper is nonasymptotic in nature, it does not require knowledge of the true model order, it is applicable to generic (random or deterministic) design matrices, and it neither requires submatrices of the design matrix to have full rank, nor does it assume a statistical prior on the values of the nonzero entries of the data vector.

This paper introduces the Reed Muller Sieve, a deterministic measurement matrix for compressed sensing. The columns of this matrix are obtained by exponentiating codewords in the quaternary second order Reed Muller code of length N. For k = O(N), the Reed Muller Sieve improves upon prior methods for identifying the support of a k-sparse vector by removing the requirement that the signal entries be independent. The Sieve also enables local detection; an algorithm is presented with complexity N2log N that detects the presence or absence of a signal at any given position in the data domain without explicitly reconstructing the entire signal. Reconstruction is shown to be resilient to noise in both the measurement and data domains; the ℓ2/ℓ2error bounds derived in this paper are tighter than the ℓ2/ℓ1bounds arising from random ensembles and the ℓ1/ℓ1bounds arising from expander-based ensembles.

Multiple-Input Multiple-Output (MIMO) systems improve the throughput and reliability of wireless communications. Perfect Channel State Information (CSI) is needed at the receiver to perform coherent detection and achieve the optimal gain of the system. In fast fading and low SNR regimes, it is hard or impossible to obtain perfect CSI, which leads the receiver to operate without knowledge of the CSI and perform blind detection. In reality CSI may be available to the receiver but this CSI may be insufficient to support coherent detection. In this paper, we fill the gap between coherent and blind detection by considering a more realistic model where the receiver knows the statistics of the channel, that is Channel Distribution Information (CDI). We propose a new detection algorithm, called Regularized Blind Detection (RBD), where coherent and blind detection can be viewed as special cases in our model. The algorithm estimates CDI from any training symbols that are available and maximizes performance given the estimated CDI. Simulations demonstrate significant improvement in performance over blind detection. Our work can be viewed as a systematic exploration of space between coherent and blind detection with a strong Bayesian statistic flavor.

In this paper, we consider end-to-end secure communication in a large wireless network, where the locations of eavesdroppers are uncertain. Our framework attempts to bridge the gap between physical layer security under uncertain channel state information of the eavesdropper and network level connectivity under security constraints, by modeling location uncertainty directly at the network level as correlated node and link failures in a secrecy graph. Bounds on the percolation threshold are obtained for square and triangular lattices, and bounds on mean degree are obtained for Poisson secrecy graphs. Both analytic and simulation results show the dramatic effect of uncertainty in location of eavesdroppers on connectivity in a secrecy graph.

Certain nonlinear binary codes can be constructed as binary images of Z4-linear codes under the Gray map. Examples include the second-order Reed-Muller code and the Kerdock and Preparata codes. In this paper, we consider a new quaternary code which is an additive subcode of the Z4-linear Kerdock code. The Kerdock code is the direct sum of a one-dimensional quaternary code and the quaternary subcode examined in this paper. This paper calculates the weight distribution of the projective Kerdock code from which the weight distribution of the dual code can be computed. The dual code is a supercode of the quaternary Preparata code. The projective Kerdock code is used to construct a deterministic measurement matrix for compressed sensing. Numerical experiments are presented for sparse reconstruction using the LASSO that show improvement over random Gaussian matrices of the same size.

Providing real-time multimedia services over a besteffort network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. The framework is based on the theoretical modeling where we consider two descriptions and high source coding rate region approximated within small constants. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that we need greater redundancy in the MD streams to protect against such failures. However, one surprising aspect of our study reveals that for large number of users who compete for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

This paper introduces multidimensional generalizations of binary Reed-Muller codes where the codewords are projection operators, and the corresponding subspaces are widely separated with respect to the chordal distance on Grassmannian space. Parameters of these Grassmannian packings are derived and a low complexity decoding algorithm is developed by modifying standard decoding algorithms for binary Reed-Muller codes. The subspaces are associated with projection operators determined by Pauli matrices appearing in the theory of quantum error correction and this connection with quantum stabilizer codes may be of independent interest. The Grassmannian packings constructed here find application in noncoherent wireless communication with multiple antennas, where separation with respect to the chordal distance on Grassmannian space guarantees closeness to the channel capacity. It is shown that the capacity of the noncoherent multiple-input-multiple-output (MIMO) channel at both low and moderate signal-to-noise ratio (SNR) (under the constraint that only isotropically distributed unitary matrices are used for information transmission) is closely approximated by these packings.

This paper focuses on conditional optimization as a decoding primitive for high rate space-time codes that are obtained by multiplexing in the spatial and code domains. The approach is a crystallization of the work of Hottinen which applies to space-time codes that are assisted by quasi-orthogonality. It is independent of implementation and is more general in that it can be applied to space-time codes such as the Golden Code and perfect space-time block codes, that are not assisted by quasi-orthogonality, to derive fast decoders with essentially maximum likelihood (ML) performance. The conditions under which conditional optimization leads to reduced complexity ML decoding are captured in terms of the induced channel at the receiver. These conditions are then translated back to the transmission domain leading to codes that are constructed by multiplexing orthogonal designs. The methods are applied to several block space-time codes obtained by multiplexing Alamouti blocks where it leads to ML decoding with complexityO(N2) whereNis the size of the underlying QAM signal constellation. A new code is presented that tests commonly accepted design principles and for which decoding by conditional optimization is both fast and ML. The two design principles for perfect space-time codes are nonvanishing determinant of pairwise differences and cubic shaping, and it is cubic shaping that restricts the possible multiplexing structures. The new code shows that it is possible to give up on cubic shaping without compromising code performance or decoding complexity.

The Peer-to-Peer (P2P) streaming has shown as an effective solution for wireline video applications, while for the wireless video streaming applications, the limited radio resource and battery energy are the main constraints on the way of P2P applications. An important issue in live video streaming quality of service is to avoid playback buffer underflow, and a challenge from wireless applications is the desire of energy efficiency. The problem we try to solve is how to utilize P2P schemes in video streaming and schedule the video transmission among peers to minimize the "freeze-ups" in playback caused by buffer underflow. In this work, we propose energy-efficient algorithm for the video transmission scheduling in wireless P2P live streaming system, to minimize the playback freeze-ups among peers. Further the algorithm is extended to two scenarios: peers' reluctance of consuming battery energy and allowing overhearing, with alternative energy-efficient algorithms proposed for the second scenario. Numerical results show the effectiveness of the proposed algorithms. The results also demonstrate that peers' selfishness may reduce the energy efficiency, but allowing overhearing could increase energy efficiency.

With the advances in wireless technology and explosive growth of mobile devices and wireless networks, mobile TV is becoming a popular application. The main technical challenge to wireless video broadcast is to provide the best quality of service possible under the radio resource constraints. In this paper we propose an application layer middleware solution that utilizes the scalability in video coding with rateless erasure correction codes to achieve a balance in the quality of service (QoS) and radio resource efficiency. Simulation results demonstrate the effectiveness of the solution.

Perfect space-time block codes (STBCs) were first introduced by Oggier et al. to have full rate, full diversity and non-vanishing determinant. A maximum likelihood decoder based on the sphere decoder has been used for efficient decoding of perfect STBCs. However the worst-case complexity for the sphere decoder is an exhaustive search. In this paper we present a reduced complexity algorithm for 3 times 3 perfect STBC which gives essentially maximum likelihood (ML) performance and which can be extended to other perfect STBC. The algorithm is based on the conditional maximization of the likelihood function with respect to one of the set of signal points given another. There are a number of choices for which signal points to condition on and the underlying structure of the code guarantees that one of the choices is good with high probability. Furthermore, the approach can be integrated with the sphere decoding algorithm with worst case complexity corresponding exactly to that of our algorithm.

We present a pilot-assisted method for estimating the frequency selective channel in a MIMO-OFDM system. The pilot sequence is designed using the DFT of the Golay complementary sequences. Novel exploitation of the perfect autocorrelation property of Golay complementary sequences, in conjunction with OSTBC based pilot waveform scheduling across multiple OFDM frames, facilitates simple separation of the channel mixtures at the receive antennas. The DFT length used to transform the complementary sequence into the frequency domain is shown to be a key critical parameter for correctly estimating the channel. This channel estimation scheme is then extended to antenna arrays of arbitrary sizes.

It is standard practice to integrate outer trellis codes with inner space-time block codes to increase coding gain, but the drawback is a decrease in rate. Jafarkhani and Seshadri have introduced an alternative method of combining multiple inner orthogonal space-time codes with outer trellis codes that both preserves rate and increases coding gain. However their work is limited to orthogonal codes, for which the achievable rate is typically low. This paper presents a method of achieving higher transmission rates by integrating higher rate non-orthogonal space with outer trellis codes, and new methods are introduced to avoid catastrophic codes. The method is presented with reference to the particular example of the silver code, but it applies to all multiplexed orthogonal designs and to more general codes.

Pricing content-providers for connectivity to end- users and setting connection parameters based on the price is an evolving model on the Internet. The implications are heavily debated in telecom policy circles, and some advocates of "Network Neutrality" have opposed price based differentiation in connectivity. However, pricing content providers can possibly subsidize the end-user's cost of connectivity, and the consequent increase in end-user demand can benefit ISPs and content providers. This paper provides a framework to quantify the precise trade-off in the distribution of benefits among ISPs, content-providers, and end-users. The framework generalizes the well-known utility maximization based rate allocation model, which has been extensively studied as an interplay between the ISP and the end-users, to incorporate pricing of content-providers. We derive the resulting equilibrium prices and data rates in two different ISP market conditions: competition and monopoly. Network neutrality based restriction on content-provider pricing is then modeled as a constraint on the maximum price that can be charged to content-providers. We demonstrate that, in addition to gains in total and end- user surplus, content-provider experiences a net surplus from participation in rate allocation under low cost of connectivity. The surplus gains are, however, limited under monopoly conditions in comparison to competition in the ISP market.

The wiretap channel type II with an active eavesdropper is considered in this paper. Compared with the eavesdropper model considered in much of the literature, the eavesdropper considered here can not only overhear but also modify the signal transmitted over the channel. Two modification models are considered. In the first model, the eavesdropper erases the bits it observes. In the second model, the eavesdropper modifies the bits it observes. For this channel with memory (introduced by the activity of the eavesdropper), one should conduct the worst case scenario analysis. Novel concatenated coding schemes that provide perfect security for the communications are developed for both models to give bounds on the achievable secrecy rate. The technique to modify the inner code to maintain the secrecy properties of the outer code may be of independent interest.

The standard approach to quantum fault tolerance is to calculate error thresholds on basic gates in the limit of arbitrarily many concatenation levels. In contrast this paper takes the number of qubits and the target implementation accuracy as given, and provides a framework for engineering the constrained quantum system to the required tolerance. The approach requires solving the full dynamics of the quantum system for an arbitrary admixture (biased or unbiased) of Pauli errors. The inaccuracy between ideal and implemented quantum systems is captured by the supremum of the Schatten-k norm of the difference between the ideal and implemented density matrices taken over all density matrices. This is a more complete analysis than the standard approach, where an intricate combination of worst case assumptions and combinatorial analysis is used to analyze the special case of equiprobable errors. Conditions for fault tolerance are now expressed in terms of error regions rather than a single number (the standard error threshold). In the important special case of a stochastic noise model and a single logical qubit, an optimization over all 2×2 density matrices is required to obtain the full dynamics. The complexity of this calculation is greatly simplified through reduction to an optimization over only three projectors. Error regions are calculated for the standard 5- and 7-qubit codes. Knowledge of the full dynamics makes it possible to design sophisticated concatenation strategies that go beyond repeatedly using the same code, and these strategies can achieve target fault tolerance thresholds with fewer qubits.

The secrecy capacity of relay channels with orthogonal components is studied in the presence of additional passive eavesdropper nodes. The relay and destination receive signals from the source on two orthogonal channels such that the destination also receives transmissions from the relay on its channel. The eavesdropper(s) can overhear either one or both of the orthogonal channels. For a single eavesdropper node, the secrecy capacity is shown to be achieved by apartial decode-and-forward(PDF) scheme when the eavesdropper can overhear only one of the two orthogonal channels. For the case of two eavesdropper nodes, secrecy capacity is shown to be achieved by PDF for a sub-class of channels.

This paper provides new insight into the classical problem of determining both the capacity of the discrete-time channel with uniform output quantization and the capacity achieving input distribution. It builds on earlier work by Gallager and Witsenhausen to provide a detailed analysis of two particular quantization schemes. The first is saturation quantization where overflows are mapped to the nearest quantization bin, and the second is modulo quantization where overflows are mapped to the nearest quantization bin after reduction by some modulus. Both the capacity of modulo quantization and the capacity achieving input distribution are determined. When the additive noise is gaussian and relatively small, the capacity of saturation quantization is shown to be bounded below by that of modulo quantization. In the limit of arbitrarily many uniform quantization levels, it is shown that the difference between the upper and lower bounds on capacity given by Ihara is only 0.26 bits.

As more and more video content is made available and accessed on-demand, content and service providers face challenges of scale. Today's delivery mechanisms, especially unicast, require resources to scale linearly with the number of receivers and library sizes. Unlike these mechanisms, with multicast, the load on a server is relatively independent of the number of receivers. Adopting multicast for on-demand access, however, is challenging because of the need to temporally aggregate requests. In this paper, we investigate the importance of an intelligent scheduler and a good data model for achieving good aggregation of requests into multicast groups. We examine the use of an Earliest Deadline First (EDF)-like scheduler that aims to schedule the transmission of chunks of video according to their deadlines using multicast. We show through analysis that this approach is optimal in terms of the data transmitted by the server. Using trace data from an operational service, we show that our approach reduces server bandwidth by as much as 65% compared to traditional techniques such as unicast and cyclic multicast. Finally, our approach achieves good aggregation even when 50% of the users use a typical VoD stream-control function like skip, to view different parts of the video.

Multiple-input multiple-output (MIMO) functionality has been shown to dramatically increase the capacity of wireless communication systems when the environment provides rich multipath scattering. In a predominantly line-of-sight (LOS) environment, the loss of diversity reduces the potential gain considerably. This can be remedied in part by the use of dual-polarized antennas, which increases the rank of the wireless channel and introduces diversity, while minimizing the antenna's form factor. However the performance of a dualpolarized antenna is still degraded by antenna rotations that are typical of mobile terminal operation. This paper presents a solution which uses a triad antenna at the transmitter and a triad at the receiver, to provide a 8-10 dB gain over the baseline dual-polarized system. A triad is composed of three orthogonal dipoles oriented in perpendicular directions. A triad antenna can generate an arbitrary oscillating dipole moment at the transmitter and consequently an arbitrary polarized electric field at the receiver, subject only to the constraints imposed by the physics of the electromagnetic (EM) field. We show that, in LOS environments, the capacity of the channel is invariant under arbitrary rotations of the transmit and/or receive antennas about their centres. Simulation results show that the performance is stable as the propagation environment varies from rich scattering to pure LOS. A full rate 3 × 3 space-time block code (STBC) is proposed for the triad system that is designed for low complexity decoding.

We design a novel class of space-time codes, called linear diversity-embedding space-time block codes (LDE-STBC) where a high-rate STBC is linearly superimposed on a highdiversity STBC without requiring channel knowledge at the transmitter. In applying this scheme to multimedia wireless communications, each traffic type constitutes a transmission layer that operates at a suitable rate-diversity tradeoff point according to its quality-of-service requirements. This, in turn, provides an unequal-error-protection (UEP) capability to the different information traffic types and allows a form of wireless communications where the high-rate STBC opportunistically takes advantage of good channel realizations while the embedded high-diversity STBC ensures that at least part of the information is decoded reliably. We investigate transceiver design issues specific to LDE-STBC including reduced-complexity coherent decoding and effective schemes to vary the coding gain to further enhance UEP capabilities of the code. Furthermore, we investigate the application of LDE-STBC to wireless multicasting and demonstrate its performance advantage over conventional equal-error-protection STBC.

Networks need to accommodate diverse applications with different quality-of-service (QoS) requirements. New ideas at the physical layer are being developed for this purpose, such as diversity embedded coding, which is a technique that combines high rates with high reliability. We address the problem of how to fully utilize different rate-reliability characteristics at the physical layer to support different types of traffic over a network and to jointly maximize their utilities. We set up a new framework based on utility maximization for networks with composite links, meaning that each link consists of sub-links that can attain different rate-reliability characteristics simultaneously. We incorporate delay, in addition to rate and reliability, into the utility functions. To accommodate different types of traffic, we propose distributed algorithms converging to the optimal rate-reliability-delay tradeoff based on capacity division and priority queueing. Numerical results show that compared with traditional codes, the new codes can provide higher network utilities for all traffic types simultaneously. The results also show that priority queueing achieves higher network utility than capacity division.

In a MIMO multiple-access channel where users employ Space-Time Block Codes (STBC), interference cancellation can be used to suppress co-channel interference and recover the desired signal of each user at the receiver. Leveraging the special properties of Alamouti matrices, we first show that spatial multiplexing of Alamouti signals retains the space-time diversity gain of Alamouti signaling using our proposed low-complexity Alamouti BLAST-MMSE (A-BLAST) Algorithm. Next, in contrast to traditional transmit diversity that focuses on STBC construction at the transmitter, this paper looks at transmit diversity from the perspective of the receiver. In other words, the receiver gets to choose the STBCiquests, which are favourable to the channel assuming a fixed BLAST receive algorithm. In a multiuserMAC setting, we first present a systematic methodology to exploit different decomposition structure in Alamouti matrices, each with different tradeoff between performance and decoding complexity using possibly different MIMO receive algorithms. We then demonstrate that the notion of angles (the inner product of two quaternionic vectors) between multiuser channels determines the performance of MIMO receive algorithms. As an application of the general theory, we transform the decoding problem for several types of Quasi-Orthogonal STBC (QOSTBC) into multiuser detection of virtual Alamouti users. Building upon our A-BLAST Algorithm, we propose new algorithms for decoding single-user and multiuser QOSTBC. In particular, we show that bit error probability is a function of the quaternionic angle between virtual users (for a single user) or multiple users. This angle varies with the type of QOSTBC and leads to a new form of adaptive modulation called code diversity, where feedback instructs the transmitter how to choose from a plurality of codes.

Results for Gaussian relay channels typically focus on maximizing transmission rates for given locations of the source, relay, and destination. We introduce an alternative perspective, where the objective is maximizingcoveragefor a given rate. The new objective captures the problem of how to deploy relays to provide a given level of service to a particular geographic area, where the relay locations become a design parameter that can be optimized. We evaluate the decode-and-forward (DF) and compress-and-forward (CF) strategies for the relay channel with respect to the new objective of maximizing coverage. When the objective is maximizing rate, different locations of the destination favor different strategies. When the objective is coverage for a given rate, and the relay is able to decode, DF is uniformly superior in that it provides coverage at any point served by CF. When the channel model is modified to include random fading, we show that the monotone ordering of coverage regions is not always maintained. While the coverage provided by DF is sensitive to changes in the location of the relay and the path loss exponent, CF exhibits a more graceful degradation with respect to such changes. The techniques used to approximate coverage regions are new and may be of independent interest.

Expander graphs have been recently proposed to construct efficient compressed sensing algorithms. In particular, it has been shown that anyn-dimensional vector that isk-sparse can be fully recovered usingO(klogn) measurements and onlyO(klogn) simple recovery iterations. In this paper, we improve upon this result by considering expander graphs with expansion coefficient beyond3/4and show that, with the same number of measurements, onlyO(k) recovery iterations are required, which is a significant improvement whennis large. In fact, full recovery can be accomplished by at most2kvery simple iterations. The number of iterations can be reduced arbitrarily close tok, and the recovery algorithm can be implemented very efficiently using a simple priority queue with total recovery timeO(nlog(n/k))). We also show that by tolerating a small penalty on the number of measurements, and not on the number of recovery iterations, one can use the efficient construction of a family of expander graphs to come up with explicit measurement matrices for this method. We compare our result with other recently developed expander-graph-based methods and argue that it compares favorably both in terms of the number of required measurements and in terms of the time complexity and the simplicity of recovery. Finally, we will show how our analysis extends to give a robust algorithm that finds the position and sign of theksignificant elements of an almostk-sparse signal and then, using very simple optimization techniques, finds ak-sparse signal which is close to the bestk-term approximation of the original signal.

Internet is experiencing a substantial growth of video traffic. Given the limited network bandwidth resources, how to provide Internet users with good video playback quality-of-service (QoS) is a key problem. For video clips competing bandwidth, we propose an approach of Content-Aware distortion-Fair (CAF) video delivery scheme, which is aware of the characteristics of video frames and ensures max-min distortion-fair sharing among video flows. CAF leverages content-awareness to prioritize packet dropping during congestion. Different from bandwidth fair sharing, CAF targets end-to-end video playback quality fairness among users. The proposed CAF approach does not require rate-distortion modeling of the source, which is difficult to estimate. Instead, it exploits the temporal prediction structure of the video sequences along with a frame drop distortion metric to guide resource allocations and coordinations. Experimental results show that the proposed approach operates with limited overhead in computation and communication, and yields better QoS, especially when the network is congested.

We consider a fading version of the dirty-paper problem, as proposed by Grover and Sahai. In this formulation, the various signals involved are complex-valued, and the interference (known only to the transmitter) is multiplied by a random complex-valued coefficient, whose phase is known only to the receiver. We focus on a compound channel formulation, and seek to maximize the worst-case performance. We present an achievable strategy modeled on the lattice-based approach of Erez, Shamai and Zamir and propose heuristic methods to optimize its parameters. We also derive an upper bound on the maximum achievable transmission rates. Our bounds are shown to be tight in some settings, yielding a complete characterization of capacity. We also provide simulation results, indicating the practical effectiveness of our approaches.

We propose a new full-rate space-time block code (STBC) for two transmit antennas which can be designed to achieve maximum diversity or maximum capacity while enjoying optimized coding gain and reduced-complexity maximum-likelihood (ML) decoding. The maximum transmit diversity (MTD) construction provides a diversity order of 2Nrfor any number of receive antennas Nrat the cost of channel capacity loss. The maximum channel capacity (MCC) construction preserves the mutual information between the transmit and the received vectors while sacrificing diversity. The system designer can switch between the two constructions through a simple parameter change based on the operating signal-to-noise ratio (SNR), signal constellation size and number of receive antennas. Thanks to their special algebraic structure, both constructions enjoy low-complexity ML decoding proportional to the square of the signal constellation size making them attractive alternatives to existing full-diversity full-rate STBCs in [6], [3] which have high ML decoding complexity proportional to the fourth order of the signal constellation size. Furthermore, we design a differential transmission scheme for our proposed STBC, derive the exact ML differential decoding rule, and compare its performance with competitive schemes. Finally, we investigate transceiver design and performance of our proposed STBC in spatial multiple-access scenarios and over frequency-selective channels.

Internet is experiencing an explosive growth of video traffic. Given the limited network bandwidth resources, how to provide Internet users with good video playback quality is a key problem. For video clips competing bandwidth, we propose an approach of content-aware distortion-fair (CAF) video delivery scheme, which is assumed to be aware of the characteristics of video frames and ensures max-min distortion fair sharing among video flows. Different from bandwidth fair sharing, CAF targets video playback quality fairness for the reason that users care about video quality rather than bandwidth. The proposed CAF approach does not need an analytical rate-distortion function which is difficult to estimate, but instead, it uses the explicit distortion of every frame which is induced by frame drop. Our CAF approach is fast and practical with content-aware cooperation. Experimental results show that the proposed approach yields better quality of service when the network is congested compared with the approach not rate-distortion optimized, and it makes competing video clips help each other to get fair playback quality.

To provide real-time multimedia services over a network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Yet such services are beginning to be deployed over best effort networks. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that greater redundancy in the MD streams is needed to protect against such failures. However, one surprising aspect of our study reveals that for large number of users competing for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

The use of complementary codes as a means of reducing radar range sidelobes is well-known, but lack of resilience to Doppler is often cited as a reason not to deploy them. This work describes techniques for providing Doppler resilience with an emphasis on tailoring Doppler performance to the specific aim of target tracking. The Doppler performance can be varied by suitably changing the order of transmission of multiple sets of complementary waveforms. We have developed a method that improves Doppler performance significantly by arranging the transmission of multiple copies of complementary waveforms according to the first order Reed-Muller codes. Here we demonstrate significant tracking gains in the context of accelerating targets by the use of adaptively chosen waveform sequences of this kind, compared to both a fixed sequence of similar waveforms, and an LFM waveform.

For Internet based video broadcasting applications such as IPTV, the peer-to-peer (P2P) streaming scheme has been found to be an effective solution. An important issue in live broadcasting is to avoid playback buffer underflow. How to utilize the playback buffer and upload bandwidth of peers to minimize the freeze-ups in playback, is the problem we try to solve. In this work, we propose a successive water-filling (SWaF) algorithm for the video transmission scheduling in P2P live streaming system, to minimize the playback freeze-ups among peers. SWaF algorithm only needs each peer to optimally transmit (within its uploading bandwidth) part of its available video segments in the buffer to other peers requiring the content and pass small amount message to some other peers. Moreover, SWaF has low complexity and provable optimality. Numerical results demonstrated the effectiveness of the proposed algorithm.

Advances in wireless technologies, such as WiMAX [1], allow high data rates and high reliability through the use of MIMO-OFDM. However, they are not optimally designed for broadcasting. The nature of the wireless medium may cause an entire frame to be in outage with little chance of recovery. One strategy to overcome this deficit is to employ diversity embedding, which protect different bits with different diversity orders. Such codes exhibit the property that even if the entire frame is in outage, a subset of the frame may still be reliably recovered. In this paper, we present space-time codes designed for MIMO-OFDM systems which achieve diversity embedding. We demonstrate how these codes can increase PSNR for video broadcasting in WiMAX.

The standard approach to the design of individual space-time codes is based on optimizing diversity and coding gain. This geometric approach leads to remarkable examples, such as the Golden Code, for which the complexity of Maximum Likelihood (ML) decoding is considerable. Code diversity is an alternative approach where a small number of feedback bits are used to select from a family of space-time codes. Feedback can be combined with sub-optimal low complexity decoding of the component codes to match ML decoding performance of any individual code in the family. It can also be combined with ML decoding of the component codes to improve performance beyond ML decoding performance of any individual code. One method of implementing code diversity is the use of feedback to adapt the phase of a transmitted signal. Phase adaptation with the 4×4 Quasi-Orthogonal Space-Time Code (QOSTBC) is shown to be almost information lossless; that is, this form of space-time coding does not reduce the capacity of the underlying multiple antenna wireless channel. Code diversity can also be used to improve performance of multi-user detection by reducing interference between users. Phase adaptation with two Alamouti users makes it possible for the Zero Forcing (ZF) or decorrelating detector to match the performance of ML joint detection.

In this paper we will examine the effect of different parameters in the quality of real compressively sampled images in the compressed sensing framework. We will select a variety of different real images of different types and test the quality of the recovered images, the recovery time, and required resources when different measurement methods with different parameters are used or when different recovering methods are applied. Then we will propose an algorithm to reduce the noise in the recovered images and sharpen them simultaneously. The algorithm exploits a well-known bilateral filtering in order to increase the confidence in margins and edges, and then uses an adaptive unsharp mask method to sharpen the images. The adaptive unsharp mask method extends the ordinary unsharp mask method and uses machine learning square loss minimization and regression in order to learn the optimal unsharping parameters. We will argue why both bilateral filtering and unsharp mask methods should be used in the algorithm simultaneously. Finally, we will show the results of applying the algorithm on real images that are recovered using the compressed sensing method and we will interpret the experimental results.

Service availability is one of the most closely scrutinized metrics in offering network services. It is important to cost- effectively provision a managed and differentiated network with various service availability guarantees under a unified platform. In particular, demands for availability may be elastic and such elasticity can be leveraged to improve cost-effectiveness. In this paper, we establish the framework of provisioning elastic service availability through network utility maximization, and propose an optimal and distributed solution using differentiated failure recovery schemes. First, we develop a utility function with configurable parameters to represent the satisfaction perceived by a user upon service availability as well as its allowed source rate. Second, adopting Quality of Protection [1] and shared path protection, we transform optimal provisioning of elastic service availability into a convex optimization problem. The desirable service availability and source rate for each user can be achieved using a price-based distributed algorithm. Finally, we numerically show the tradeoff between the throughput and the service availability obtained by users in various network topologies. This investigation quantifies several engineering implications. For example, indiscriminately provisioning service availabilities for different kinds of users within one network leads to noteworthy sub-optimality in total network utility. The profile of bandwidth usage also illustrates that provisioning high service availability exclusively for critical applications leads to significant waste in bandwidth resource.

This paper describes a fundamental correspondence between Boolean functions and projection operators in Hilbert space. The correspondence is widely applicable, and it is used in this paper to provide a common mathematical framework for the design of both additive and nonadditive quantum error correcting codes. The new framework leads to the construction of a variety of codes including an infinite class of codes that extend the original ((5, 6, 2)) code found by Rains It also extends to operator quantum error correcting codes.

Rate and diversity impose a fundamental tradeoff in wireless communication. High-rate space-time codes come at a cost of lower reliability (diversity), and high reliability (diversity) implies a lower rate. However, wireless networks need to support applications with very different quality-of-service (QoS) requirements, and it is natural to ask what characteristics should be built into the physical layer link in order to accommodate them. In this paper, we design high-rate space-time codes that have a high-diversity code embedded within them. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations while the embedded high-diversity code provides guarantees that at least part of the information is received reliably. We provide constructions of linear and nonlinear codes for a fixed transmit alphabet constraint. The nonlinear constructions are a natural generalization to wireless channels of multilevel codes developed for the additive white Gaussian noise (AWGN) channel that are matched to binary partitions of quadrature amplitude modulation (QAM) and phase-shift keying (PSK) constellations. The importance of set-partitioning to code design for the wireless channel is that it provides a mechanism for translating constraints in the binary domain into lower bounds on diversity protection in the complex domain. We investigate the systems implications of embedded diversity codes by examining value to unequal error protection, rate opportunism, and packet delay optimization. These applications demonstrate that diversity-embedded codes have the potential to outperform traditional single-layer codes in moderate signal-to-noise (SNR) regimes.

Designs for transmit alphabet constrained space-time codes naturally lead to questions about the design of rank distance codes. Recently, diversity embedded multilevel space-time codes for flat-fading channels have been designed from sets of binary matrices with rank distance guarantees over the binary field by mapping them onto quadrature amplitude modulation (QAM) and phase-shift keying (PSK) constellations. In this paper, we demonstrate that diversity embedded space-time codes for fading intersymbol interference (ISI) channels can be designed with provable rank distance guarantees. As a corollary, we obtain an asymptotic characterization of the fixed transmit alphabet rate-diversity tradeoff for multiple antenna fading ISI channels. The key idea is to construct and analyze properties of binary matrices with a particular structure (Toeplitz structure) induced by ISI channels.

This paper introduces a new rate-2, full-diversity space-time code for four transmit antennas and one receive antenna. The 4times4 codeword matrix consists of four 2times2 Alamouti blocks with entries fromQ(i,radic5) , and these blocks can be viewed as quaternions which in turn represent rotations inR3. The Alamouti blocks that appear in a codeword are drawn from the icosian ring consisting of all linear combinations of 120 basic rotations corresponding to symmetries of the icosahedron. This algebraic structure is different from the Golden code, but the complex entries are taken from a common underlying field. The minimum determinant is bounded below by a constant that is independent of the signal constellation, and the new code admits a simple decoding scheme that makes use of a geometric correspondence between the icosian ring and theE8lattice.

We describe a method of constructing a sequence (pulse train) of phase-coded waveforms, for which the ambiguity function is free of range sidelobes along modest Doppler shifts. The constituent waveforms are Golay complementary waveforms which have ideal ambiguity along the zero Doppler axis but are sensitive to nonzero Doppler shifts. We extend this construction to multiple dimensions, in particular to radar polarimetry, where the two dimensions are realized by orthogonal polarizations. Here we determine a sequence of two-by-two Alamouti matrices where the entries involve Golay pairs and for which the range sidelobes associated with a matrix-valued ambiguity function vanish at modest Doppler shifts. The Prouhet–Thue–Morse sequence plays a key role in the construction of Doppler resilient sequences of Golay complementary waveforms.

Space–time codes built out of Alamouti components have been adopted in wireless standards such as UMTS, IEEE 802.11n, and IEEE 802.16, where they facilitate higher data rates through multiplexing of parallel data streams and the addition of two or more antennas at the receiver that perform interference cancellation. This correspondence provides new theoretical insight into different algorithms for interference cancellation through a Bayesian analysis that expresses performance as a function of signal-to-noise ratio (SNR) in terms of the “angles” between different space–time coded data streams.

We study the congestion control in a network where the users may have different types of traffic, such as the traffic with fixed/variable rate, delay sensitive/insensitive, etc. To reflect the different requirements on delay by different applications, explicit terms of delay are added to the utility function. We analyze the essential dynamics for the network utility maximization (NUM) with the new utility functions. Compared with the basic NUM where the utility function is only a function of rate, the dynamics for link price is now related to the delay term added in the utility function. The analysis is applied to the system with voice and data traffic, and distributed algorithms are proposed to allocate the resource such that the utility of voice and data is jointly optimized. The numerical results show that by the new price dynamics, we can accomplish optimal congestion control for users with delay sensitive/insensitive traffic in a network. In particular, in a network with data and voice traffic with priority queueing, the algorithm can lead the network to achieve higher quality of voice traffic and higher throughput of data traffic, with the sacrifice of the packet delay of data traffic.

In this paper, we propose a method to exploit waveform agility in modern radars to improve performance in the challenging task of detecting small targets on the ocean surface in heavy clutter. The approach exploits the compound-Gaussian model for sea clutter returns to achieve clutter suppression by forming an orthogonal projection of the received signal into the clutter subspace. Waveform scheduling is then performed by incorporating the information about the clutter into the design of the next transmitted waveform. A simulation study demonstrates the effectiveness of our approach.

Networks need to accommodate diverse applications with different quality-of-service (QoS) requirements. New ideas at the physical layer are being developed for this purpose, such as diversity embedded coding, which is a technique that combines high rates with high reliability. We address the problem of how to fully utilize different rate-reliability characteristics at the physical layer to support different types of traffic over a network and to jointly maximize their utilities. We set up a new framework based on utility maximization for networks with composite links, meaning that each link consists of sub-links that can attain different rate-reliability characteristics simultaneously. We incorporate delay, in addition to rate and reliability, into the utility functions. To accommodate different types of traffic, we propose distributed algorithms for the optimal rate-reliability-delay tradeoff based on capacity division and priority queueing. Numerical results show that compared with traditional codes, the new codes can provide higher network utilities for all traffic types simultaneously. The results also show that priority queueing achieves higher network utility than capacity division.

Service availability is one of the most closely scrutinized metrics in offering network services. The network vendor can earn more revenue from the customers by guaranteeing higher service availability at the cost of higher operational expense. It is important to cost-effectively provision a managed and differentiated network with various service availability guarantees under a unified platform. In this paper, we establish the framework of provisioning elastic service availability through network utility maximization, and propose an optimal and distributed solution using differentiated failure recovery schemes. First, we develop a utility function with configurable parameters to represent the satisfaction perceived by a user upon service availability as well as its allowed source rate. Second, adopting quality of protection [1] and shared path protection, we transform optimal provisioning of elastic service availability into a convex optimization problem. The desirable service availability and source rate for each user can be achieved using a price-based distributed algorithm. Finally, we numerically show the tradeoff between the throughput and the service availability obtained by users in various network topologies. Several quantitative observations are made from this investigation. For example, indiscriminately provisioning service availabilities for different kinds of users within one network leads to noteworthy sub-optimality in total network utility. The profile of bandwidth usage also illustrates that provisioning high service availability exclusively for critical applications leads to significant waste in bandwidth resource.

This paper describes a common mathematical framework for the design of additive and non-additive Quantum Error Correcting Codes. It is based on a correspondence between boolean functions and projection operators. The new framework extends to operator quantum error correcting codes.

Results for Gaussian relay channels typically focus on maximizing transmission rates for given locations of the source, relay and destination. We consider an alternative approach, focusing on maximizing coverage for a given rate. This novel perspective enables treatment of the relay location as a design parameter, producing an extra degree of freedom that may be optimized. Focusing on coverage, we evaluate existing approaches, like decode and forward (DF), compress and forward (CF) and compare them with upper bounds. In the process, we obtain some surprising insights on the performance of these approaches.

Space-time codes built out of Alamouti components have been adopted in wireless standards such as UMTS, IEEE 802.1 In and IEEE 802.16 where they facilitate higher data rates through multiplexing of parallel data streams and the addition of two or more antennas at the receiver that perform interference cancellation. This paper provides new theoretical insight into an algorithm for interference cancellation through a Bayesian analysis that expresses performance as a function of SNR in terms of the ''angles" between different space-time coded data streams. Our approach provides insights into the coupling of channel coding to spatial and polarization degrees of freedom.

This paper reverse-engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse-engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. Then we establish the minimum amount of backoff aggressiveness needed, as a function of density of active users, for uniqueness of Nash equilibrium and convergence of the best response strategy. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse-engineering TCP and BGP, this paper further advances the recent efforts in reverse-engineering layers 2-4 protocols. In contrast to the TCP reverse-engineering results in earlier literature, MAC reverse-engineering highlights the non-cooperative nature of random access.

Network protocols in layered architectures have historically been obtained on anad hocbasis, and many of the recent cross-layer designs are also conducted through piecemeal approaches. Network protocol stacks may instead be holistically analyzed and systematically designed as distributed solutions to some global optimization problems. This paper presents a survey of the recent efforts towards a systematic understanding of “layering” as “optimization decomposition,” where the overall communication network is modeled by a generalized network utility maximization problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as functions of the optimization variables coordinating the subproblems. There can be many alternative decompositions, leading to a choice of different layering architectures. This paper surveys the current status of horizontal decomposition into distributed computation, and vertical decomposition into functional modules such as congestion control, routing, scheduling, random access, power control, and channel coding. Key messages and methods arising from many recent works are summarized, and open issues discussed. Through case studies, it is illustrated how “Layering as Optimization Decomposition” provides a common language to think about modularization in the face of complex, networked interactions, a unifying, top-down approach to design protocol stacks, and a mathematical theory of network architectures.

This paper presents pilot designs for consistent frequency-offset estimation of orthogonal frequency-division multiplexing systems in frequency-selective fading channels. We describe two design approaches, namely, consistency in the probabilistic sense and absolute consistency. Existing preambles and pilot designs in the literature do not guarantee the absolute consistency. We derive general criteria for both approaches, present sufficient conditions on the pilot structures over the maximum carrier frequency offset (CFO) estimation range (half of the sampling rate), and derive simple pilot designs satisfying these conditions. We also extend the sufficient conditions to any arbitrary but fixed CFO estimation range, and present some generalized design patterns. Furthermore, the CFO estimation performances of distinct consistent pilot designs can be quite different at moderate or low signal-to-noise ratio (SNR) due to different statistics of outliers which also yields a link failure. We develop efficient pilot-design criteria that provide both consistency and robustness against outliers at moderate-to-low SNR. Our consistent pilot designs facilitate flexible and economical implementation, while our robust pilot designs enable wireless links with less outage and better resilience

This paper describes a new radar primitive that enables instantaneous radar polarimetry at essentially no increase in signal processing complexity. This primitive coordinates transmission of distinct waveforms on orthogonal polarizations and applies a unitary matched filter bank on receive. This avoids the information loss inherent in single-channel matched filters. A further advantage of this scheme is the elimination of range sidelobes

With the advent of quantum key distribution (QKD) systems, perfect (i.e., information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical error-correcting codes for both error correction (for the honest parties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model that corresponds to such a setting is the wire tap channel introduced by Wyner in 1975. In this correspondence, we study fundamental limits and coding methods for wire tap channels. We provide an alternative view of the proof for secrecy capacity of wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide security at rates below secrecy capacity. For the special case of a noiseless main channel and binary erasure channel, we consider encoder and decoder design for codes achieving secrecy on the wiretap channel; we show that it is possible to construct linear-time decodable secrecy codes based on low-density parity-check (LDPC) codes that achieve secrecy.

This paper designs medium access control (MAC) protocols for wireless networks through the network utility maximization (NUM) framework. A network-wide utility maximization problem is formulated, using a collision/persistence-probabilistic model and aligning selfish utility with total social welfare. By adjusting the parameters in the utility objective functions of the NUM problem, we can also control the tradeoff between efficiency and fairness of radio resource allocation. We develop two distributed algorithms to solve the utility-optimal random-access control problem, which lead to random access protocols that have slightly more message passing overhead than the exponential-backoff protocols, but significant potential for efficiency and fairness improvement. We provide readily-verifiable sufficient conditions under which convergence of the proposed algorithms to a global optimality of network utility can be guaranteed, and numerical experiments that illustrate the value of the NUM approach to the complexity-performance tradeoff in MAC design.

This paper presents pilot designs for consistent frequency offset estimation of OFDM systems in frequency-selective fading channels. We describe two design approaches, namely consistency in the probabilistic sense and absolute consistency. Existing preambles and pilot designs in the literature do not guarantee the absolute consistency. We derive general criteria for both approaches, present sufficient conditions on the pilot structures, and derive simple pilot designs satisfying these conditions. Absolute consistency should not be compromised in emergency-related or other critical communication scenarios and our proposed consistent pilot designs address this need.

The current framework of network utility max- imization for rate allocation and its price-based algorithms assumes that each link provides a fixed-size transmission 'pipe' and each user's utility is a function of transmission rate only. These assumptions break down in many practical systems, where, by adapting the physical layer channel coding or transmission diversity, different tradeoffs between rate and reliability can be achieved. In network utility maximization problems formu- lated in this paper, the utility for each user depends on both transmission rate and signal quality, with an intrinsic tradeoff between the two. Each link may also provide a higher (lower) rate on the transmission 'pipes' by allowing a higher (lower) decoding error probability. Despite non-separability and non- convexity of these optimization problems, we propose new price- based distributed algorithms and prove their convergence to the globally optimal rate-reliability tradeoff under readily-verifiable sufficient conditions. We first consider networks in which the rate-reliability tradeoff is controlled by adapting channel code rates in each link's physical layer error correction codes, and propose two distributed algorithms based on pricing, which respectively implement the 'integrated' and 'differentiated' policies of dynamic rate- reliability adjustment. In contrast to the classical price-based rate control algorithms, in our algorithms each user provides an of- fered price for its own reliability to the network while the network provides congestion prices to users. The proposed algorithms converge to a tradeoff point between rate and reliability, which we prove to be a globally optimal one for channel codes with sufficiently large coding length and utilities whose curvatures are sufficiently negative. Under these conditions, the proposed algorithms can thus generate the Pareto optimal tradeoff curves between rate and reliability for all the users. The distributed algorithms and convergence proofs are extended for wireless MIMO multi-hop networks, in which diversity and multiplexing gains of each link are controlled to achieve the optimal rate- reliability tradeoff.

This paper analyzes and designs medium access control (MAC) protocols for wireless ad-hoc networks through the network utility maximization (NUM) framework. We first reverse-engineer the current exponential backoff (EB) type of MAC protocols such as the BEB (binary exponential backoff) in the IEEE 802.11 standard through a non-cooperative game- theoretic model. This MAC protocol is shown to be implicitly maximizing, using a stochastic subgradient, a selfish local utility at each link in the form of expected net reward for successful transmission. While the existence of a Nash equilibrium can be established, neither convergence nor social welfare optimality is guaranteed due to the inadequate feedback mechanism in the EB protocol. This motivates the forward-engineering part of the paper, where a network-wide utility maximization problem is for- mulated, using a collision and persistence probability model and aligning selfish utility with total social welfare. By adjusting the parameters in the utility objective functions of the NUM problem, we can also control the tradeoff between efficiency and fairness of radio resource allocation through a rigorous and systematic design. We develop two distributed algorithms to solve the MAC design NUM problem, which lead to random access protocols that have slightly more message passing overhead than the current EB protocol, but significant potential for efficiency and fairness improvement. We provide readily-verifiable sufficient conditions under which convergence of the proposed algorithms to a global optimality of network utility can be guaranteed, and through numerical examples illustrate the value of the NUM approach to the complexity-performance tradeoff in MAC design.

We derive a generalization of a result in representation theory. Using this generalization, we construct new families of Grassmannian packings associated with binary Reed-Muller codes and we develop a low complexity decoding algorithm by modifying standard decoding algorithms for these binary codes. The subspaces are associated with projection operators which arise in the theory of quantum stabilizer codes. These Grassmannian packings find application as highly structured examples of dictionaries that admit fast algorithms for identifying sparse representations, and in noncoherent wireless communication with multiple antennas. The capacity of the noncoherent MIMO channel at both low and moderate SNR (under the constraint that only isotropically distributed unitary matrices are used for information transmission) is closely approximated by these packings

The performance of space-time codes is evaluated in terms of diversity gain and coding gain, two measures which describe the worst-case pairwise error probability between codewords at high signal-to-noise ratio (SNR). We introduce the concept of effective coding gain to provide an estimate on the bit error rate (BER) at low-to-moderate SNR. This concept connects the number of nearest neighbours with degradation in error performance. We demonstrate the value of the new concept through analysis of space-time block codes for the quasi-static Rayleigh fading channel

This paper introduces a new full-rate, full-diversity space-time code for 4 transmit antennas. The 4times4 codeword matrix consists of four 2times2 Alamouti blocks with entries from Q(i, radic5), and these blocks can be viewed as quaternions which in turn represent rotations in R3. The Alamouti blocks that appear in a codeword are drawn from the icosian ring consisting of all linear combinations of 120 basic rotations corresponding to symmetries of the icosahedron. This algebraic structure is different from the Golden code, but the complex entries are taken from a similar underlying field. The minimum determinant is bounded below by a constant that is independent of the signal constellation, and the new code admits a simple decoding scheme that makes use of a geometric correspondence between the icosian ring and the E8lattice

Network protocols in layered architectures have historically been obtained primarily on an ad-hoc basis. Recent research has shown that network protocols may instead be holistically analyzed and systematically designed as distributed solutions to some global optimization problems in the form of Network Utility Maximization (NUM), providing insight into what they optimize and structures of the network protocol stack. This paper presents a short survey of the recent efforts towards a systematic understanding of 'layering' as 'optimization decomposition', where the overall communication network is modeled by a generalized NUM problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as functions of the optimization variables coordinating the sub-problems. Different decompositions lead to alternative layering architectures. We summarize several examples of horizontal decomposition into distributed computation and vertical decomposition into functional modules such as congestion control, routing, scheduling, random access, power control, and coding.

We study joint end-to-end congestion control and per-link medium access control (MAC) in ad-hoc wireless networks. We use a network utility maximization formulation, in which by adjusting the types of utility functions, we can accommodate multi-class services as well as exploit the tradeoff between efficiency and fairness of resource allocation. Despite the inherent difficulties of non-convexity and non-separability of the optimization problem, we show that, under readily-verifiable sufficient conditions, we can develop a distributed algorithm that converges to the globally and jointly optimal rate allocation and persistence probabilities. A key contribution is that our results can accommodate general concave utility function rather than just the logarithmic utility function in existing results.

This paper reverse engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. The minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of the best response strategy are established as a function of user density. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse engineering TCP and BGP, this paper completes the recent efforts in reverse engineering the main protocols in layers 2-4.

The current framework of network utility maximization for rate allocation and its price-based algorithms assumes that each link provides a fixed-size transmission "pipe" and each user's utility is a function of transmission rate only. These assumptions break down in many practical systems, where, by adapting the physical layer channel coding or transmission diversity, different tradeoffs between rate and reliability can be achieved. In network utility maximization problems formulated in this paper, the utility for each user depends on both transmission rate and signal quality, with an intrinsic tradeoff between the two. Each link may also provide a higher (or lower) rate on the transmission "pipes" by allowing a higher (or lower) decoding error probability. Despite nonseparability and nonconvexity of these optimization problems, we propose new price-based distributed algorithms and prove their convergence to the globally optimal rate-reliability tradeoff under readily-verifiable sufficient conditions. We first consider networks in which the rate-reliability tradeoff is controlled by adapting channel code rates in each link's physical-layer error correction codes, and propose two distributed algorithms based on pricing, which respectively implement the "integrated" and "differentiated" policies of dynamic rate-reliability adjustment. In contrast to the classical price-based rate control algorithms, in our algorithms, each user provides an offered price for its own reliability to the network, while the network provides congestion prices to users. The proposed algorithms converge to a tradeoff point between rate and reliability, which we prove to be a globally optimal one for channel codes with sufficiently large coding length and utilities whose curvatures are sufficiently negative. Under these conditions, the proposed algorithms can thus generate the Pareto optimal tradeoff curves between rate and reliability for all the users. In addition, the distributed algorithms and convergence proofs are extended for wireless multiple-inpit-multiple-output multihop networks, in which diversity and multiplexing gains of each link are controlled to achieve the optimal rate-reliability tradeoff. Numerical examples confirm that there can be significant enhancement of the network utility by distributively trading-off rate and reliability, even when only some of the links can implement dynamic reliability.

We investigate the theory of the finite discrete Heisenberg-Weyl group in relation to the development of adaptive radar. We contend that this group can form the basis for the representation of the radar environment in terms of operators on the space of waveforms. We also demonstrate, following recent developments in the theory of error correcting codes, that the finite discrete Heisenberg-Weyl group provides a unified basis for the construction of useful waveforms/sequences for radar, communications and the theory of error correcting codes.

We present a family of space-time codes for the noncoherent MIMO channel. The codes are constructed via functions that can be considered as a generalization of boolean functions to commuting projection operators which arise in the theory of quantum stabilizer codes. These space-time codes are strongly related to standard binary Reed-Muller codes. In particular, they can be decoded by adapting a decoding algorithm for Reed-Muller codes. We show that the first subclass of codes from this family, which we view as the first order space-time Reed-Muller codes, allow transmission with rates close to the MIMO noncoherent channel capacity in the low signal to noise ratio (SNR) regime

The current framework of network utility maximization for distributed rate allocation assumes fixed channel code rates. However, by adapting the physical layer channel coding, different rate-reliability tradeoffs can be achieved on each link and for each end user. Consider a network where each user has a utility function that depends on both signal quality and data rate, and each link may provide a 'fatter' ('thinner') information 'pipe' by allowing a higher (lower) decoding error probability. We propose two distributed, pricing-based algorithms to attain optimal rate-reliability tradeoff, with an interpretation that each user provides its willingness to pay for reliability to the network and the network feeds back congestion prices to users. The proposed algorithms converge to a tradeoff point between rate and reliability, which is proved to be globally optimal for codes with sufficiently large codeword lengths and user utilities with sufficiently negative curvatures

We investigate the use of capacity and near-capacity achieving LDPC codes on the wire tap channel, where the dual conditions of reliable communications and security are required. We show that good codes for conventional channels (like BSC and BEC) also have interesting and useful security properties. In this paper we show the connection between the decoding threshold of the code and its security against eavesdropping. We also give practical code constructions for some special cases of the wire tap channel and show that security (in the Shannon sense) is a function of the decoding threshold. Some of these constructions achieve the secrecy capacity as defined by Wyner. These codes provide secure communications without conventional key distribution and provide a physical-layer approach for either secure communications or key distribution

Network Utility Maximization (NUM) has significantly extended the classical network flow problem and provided an emerging framework to design resource allocation algorithms such as TCP congestion control and to understand layering as optimization decomposition. We present a summary of very recent results in the theory and applications of NUM. We show new distributed algorithms that converge to the globally optimal rate allocation for NUM problems with nonconcave utility functions representing inelastic flows, with coupled utility functions representing interference effects or hybrid social-selfish utilities, and with rate-reliability tradeoff through adaptive channel coding in the physical layer. We conclude by discussing how do different decompositions of a generalized NUM problem correspond to different layering architectures.

Two subspaces of a vector space are here called "nonintersecting" if they meet only in the zero vector. Motivated by the design of noncoherent multiple-antenna communications systems, we consider the following question. How many pairwise nonintersecting M/sub t/-dimensional subspaces of an m-dimensional vector space V over a field F can be found, if the generator matrices for the subspaces may contain only symbols from a given finite alphabet A/spl sube/F? The most important case is when F is the field of complex numbers C; then M/sub t/ is the number of antennas. If A=F=GF(q) it is shown that the number of nonintersecting subspaces is at most (q/sup m/-1)/(q/sup Mt/-1), and that this bound can be attained if and only if m is divisible by M/sub t/. Furthermore, these subspaces remain nonintersecting when "lifted" to the complex field. It follows that the finite field case is essentially completely solved. In the case when F=C only the case M/sub t/=2 is considered. It is shown that if A is a PSK-configuration, consisting of the 2/sup r/ complex roots of unity, the number of nonintersecting planes is at least 2/sup r(m-2)/ and at most 2/sup r(m-1)-1/ (the lower bound may in fact be the best that can be achieved).

This paper designs space-time codes for standard PSK and QAM signal constellations that have flexible rate, diversity and require no constellation expansion. Central to this construction are binary partitions of the PSK and QAM constellations that appear in codes designed for the Gaussian channel. The space-time codes presented here are designed by separately specifying the different levels of the binary partition in the space-time array. The individual levels are addressed by either the binary symmetric matrices associated with codewords in a Kerdock code or other families of binary matrices. Binary properties of these sets are sufficient to verify the diversity property of the codewords in the complex domain. Larger sets of binary symmetric matrices (such as the set used in Delsarte-Goethals codes) are used to trade diversity protection for increased rate.

In this paper, we construct a new nonlinear 4x4 full-rate, full-diversity orthogonal space-time block code (STBC) using quaternionic algebra on which the Alamouti code is also based. We also develop a differential encoding and decoding scheme for this code, which also enjoys low decoding complexity

This paper describes the construction of codewords and subspaces are nonintersecting over the finite field. When the alphabet is a finite field, constructions are lifted to the complex field to obtain maximal diversity differential space-time codes for the noncoherent multiple antenna problems. The construction of codewords (i.e. nonintersecting subspaces) subjects to the constraint that the elements of the codewords use symbols from a fixed, small PSK constellation.

The effect of spatial diversity on the throughput and reliability of wireless networks is examined. Spatial diversity is realized through multiple independently fading transmit/receive antenna paths in single-user communication and through independently fading links in multiuser communication. Adopting spatial diversity as a central theme, we start by studying its information-theoretic foundations, then we illustrate its benefits across the physical (signal transmission/coding and receiver signal processing) and networking (resource allocation, routing, and applications) layers. Throughout the paper, we discuss engineering intuition and tradeoffs, emphasizing the strong interactions between the various network functionalities.

Rate and diversity impose a fundamental trade-off in space-time coding. High-rate space-time codes come at a cost of lower diversity, and high reliability (diversity) implies a lower rate. We explore a different point of view where we design high-rate space-time codes that have a high-diversity code embedded within them. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations whereas the embedded high-diversity code ensures that at least part of the information is received reliably. We explore this point of view with design issues, along with some preliminary progress on code constructions and some information-theoretic considerations.

In this paper we study the multiple-access channel where users employ space-time block codes (STBC). The problem is formulated in the context of an inter-symbol interference (IS) multiple-access channel. The algebraic structure of the STBC is utilized to design joint interference suppression, equalization, and decoding schemes. Each user transmits using 2 transmit antennas and a time-reversed space-time block code suitable for frequency-selective channels. We first show that a diversity order of 2M/sub r/(v+1) is achievable at full transmission rate for each user, when we have M/sub r/ receive antennas, channel memory of v and an optimal multi-user maximum-likelihood (ML) decoder is used. Due to the decoding complexity of the ML detectors we study the algebraic structure of linear multiuser detectors, which utilize he properties of the STBC. We do this both in the transform domain (D-domain formulation) and when we impose finite block length constraints (matrix formulation). The receiver is designed to utilize the algebraic structure of the codes in order to preserve the block quaternionic structure of the equivalent channel for each user.

Space-time coding is a bandwidth and power efficient method of communication over fading channels that realizes the benefits of multiple transmit antennas. Specific codes have been constructed using design criteria derived for quasi-static flat Rayleigh or Rician fading, where channel state information is available at the receiver. It is evident that the practicality of space-time codes will be greatly enhanced if the derived design criteria remain valid in the absence of perfect channel state information. It is even more desirable that the design criteria not be unduly sensitive to frequency selectivity and to the Doppler spread. This paper presents a theoretical study of these issues beginning with the effect of channel estimation error. Here it is assumed that a channel estimator extracts fade coefficients at the receiver and for constellations with constant energy, it is proved that in the absence of ideal channel state information the design criteria for space-time codes is still valid. The analysis also demonstrates that standard channel estimation techniques can be used in conjunction with space-time codes provided that the number of transmit antennas is small. We also derive the maximum-likelihood detection metric in the presence of channel estimation errors. Next, the effect of multiple paths on the performance of space-time codes is studied for a slowly changing Rayleigh channel. It is proved that the presence of multiple paths does not decrease the diversity order guaranteed by the design criteria used to construct the space-time codes. Similar results hold for rapid fading channels with or without multiple paths. The conclusion is that the diversity order promised by space-time coding is achieved under a variety of mobility conditions and environmental effects.

In this paper, we study the multiple-access channel where users employ space-time block codes (STBC). The problem is formulated in the context of an intersymbol interference (ISI) multiple-access channel which occurs for transmission over frequency-selective channels. The algebraic structure of the STBC is utilized to design joint interference suppression, equalization, and decoding schemes. Each of the K users transmits using M/sub t/=2 transmit antennas and a time-reversed STBC suitable for frequency-selective channels. We first show that a diversity order of 2M/sub r/(/spl nu/+1) is achievable at full transmission rate for each user, when we have M/sub r/ receive antennas, channel memory of /spl nu/, and an optimal multiuser maximum-likelihood (ML) decoder is used. Due to the decoding complexity of the ML detector we study the algebraic structure of linear multiuser detectors which utilize the properties of the STBC. We do this both in the transform (D-domain) formulation and when we impose finite block-length constraints (matrix formulation). The receiver is designed to utilize the algebraic structure of the codes in order to preserve the block quaternionic structure of the equivalent channel for each user. We also explore some algebraic properties of D-domain quaternionic matrices and of quaternionic circulant block matrices that arise in this study.

We introduce the concept of "democracy," in which the individual bits in a coarsely quantized representation of a signal are all given "equal weight" in the approximation to the original signal. We prove that such democratic representations cannot achieve the same accuracy as optimal nondemocratic schemes.

The information capacity of wireless communication systems can be increased dramatically by employingmultiple transmit and receive antennas [?, ?]. An effective approach to increasing data rate over wireless channels is to employ coding techniques appropriate to multiple transmit antennas, that is space-time coding. Space-time codes introduce temporal and spatial correlation into signals transmitted from different antennas, in order to provide diversity at the receiver, and coding gain over an uncoded system. The spatial-temporal structure of these codes can be exploited to further increase the capacity of wireless systems with a relatively simple receiver structure. This chapter provides an overview of space-time coding techniques and the associated signal processing framework.

We estimate bit error probability bounds for finite-length delay-optimised multi-input multi-output (MIMO) equalizers. These equalizers shorten the impulse response memory of frequency-selective MIMO channels by minimizing the average energy of the error sequence between the equalized MIMO channel impulse response and the target impulse response. We answer an important question in this paper namely, how much asymptotic loss in SNR do we expect as a result of this shortening? A partial distance spectrum for a 2/spl times/2 MIMO channel is evaluated with or without channel shortening equalisers. The union bound is then used to upper bound the bit error probability. Similarly, the lower bound is computed from the squared minimum Euclidean distance. Numerical results show that the expected loss is in the order of 2.5 dB for realistic wireless channel environments.

Wireless systems are subject to a time-varying and unknown a priori combination of cochannel interference, fading, and Gaussian noise. It is well known that multiple antennas can provide diversity in space that allows system tradeoffs between interference suppression and mitigation of fading. This paper describes how to achieve these same tradeoffs through diversity in time provided by channel coding. The mathematical description of time diversity is identical to that of space diversity, and what emerges is a unified framework for signal processing. Decoding algorithms are provided for repetition codes, rate 1/n convolutional codes, first-order Reed-Muller codes, and a new class of linear combination codes that provide cochannel interference suppression. In all cases it is possible to trade performance for complexity by choosing between joint estimation and a novel low-complexity linear canceler structure that treats interference as noise. This means that a single code can be used in a variety of system environments just by changing the processing in the receiver.

The authors note a few misprints exist in the final version of the above-named paper [ibid., vol. 45, pp. 1456–1467, July 1999]. In Definitions 3.4.1, 4.1.1, and 5.4.1, also in the last line of the proof of Theorem 3.5.2.

We document the performance of space-time block codes, which provide a new paradigm for transmission over Rayleigh fading channels using multiple transmit antennas. Data is encoded using a space-time block code, and the encoded data is split into n streams which are simultaneously transmitted using n transmit antennas. The received signal at each receive antenna is a linear superposition of the n transmitted signals perturbed by noise. Maximum likelihood decoding is achieved in a simple way through decoupling of the signals transmitted from different antennas rather than joint detection. This uses the orthogonal structure of the space-time block code and gives a maximum likelihood decoding algorithm which is based only on linear processing at the receiver. We review the encoding and decoding algorithms for various codes and provide simulation results demonstrating their performance. It is shown that using multiple transmit antennas and space-time block coding provides remarkable performance at the expense of almost no extra processing.

Space-time coding is a bandwidth and power efficient method of communication over fading channels that realizes the benefits of multiple transmit antennas. Specific codes have been constructed using design criteria derived for quasi-static flat Rayleigh or Rician fading, where channel state information is available at the receiver. It is evident that the practicality of space-time codes will be greatly enhanced if the derived design criteria remain valid in the absence of perfect channel state information. It is even more desirable that the design criteria not be unduly sensitive to frequency selectivity and to the Doppler spread. This paper presents a theoretical study of these issues beginning with the effect of channel estimation error. Here it is assumed that a channel estimator extracts fade coefficients at the receiver and for constellations with constant energy, it is proved that in the absence of ideal channel state information the design criteria for space-time codes is still valid. The analysis also demonstrates that standard channel estimation techniques can be used in conjunction with space-time codes provided that the number of transmit antennas is small. We also derive the maximum-likelihood detection metric in the presence of channel estimation errors. Next, the effect of multiple paths on the performance of space-time codes is studied for a slowly changing Rayleigh channel. It is proved that the presence of multiple paths does not decrease the diversity order guaranteed by the design criteria used to construct the space-time codes. Similar results hold for rapid fading channels with or without multiple paths. The conclusion is that the diversity order promised by space-time coding is achieved under a variety of mobility conditions and environmental effects.

This paper investigates how closely randomly generated binary source sequences can be matched by convolutional code codewords. What distinguishes it from prior work is that a randomly chosen subsequence with density /spl lambda/ is to be matched as closely as possible. The so-called marked bits of the subsequence could indicate overload quantization points for a source sample generated from the tails of a probability distribution. They might also indicate bits where the initial estimate is considered reliable, as might happen in iterated decoding. The capacity of a convolutional code to interpolate the marked subsequence might be viewed as a measure of its ability to handle overload distortion. We analyze this capacity using a Markov chain whose states are sets of subsets of trellis vertices of the convolutional code. We investigate the effect of memory on the probability of perfect interpolation and calculate the residual rate on the unmarked bits of the binary source sequence. We relate our interpolation methodology to sequence-based methods of quantization and use it to analyze the performance of convolutional codes on the pure erasure channel.

Tail-biting trellis representations of block codes are investigated. We develop some elementary theory, and present several intriguing examples, which we hope will stimulate further developments in this field. In particular, we construct a 16-state 12-section structurally invariant tail-biting trellis for the (24, 12, 8) binary Golay code. This tail-biting trellis representation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventional 12-section trellis for the Golay code, which has 256 states at its midpoint, or with the best quasi-cyclic representation of this code, which leads to a 64-state tail-biting trellis. Unwrapping this tail-biting trellis produces a periodically time-varying 16-state rate-1/2 "convolutional Golay code" with d=8, which has attractive performance/complexity properties. We furthermore show that the (6, 3, 4) quaternary hexacode has a minimal 8-state group tail-biting trellis, even though it has no such linear trellis over F/sub 4/. Minimal tail-biting trellises are also constructed for the (8, 4, 4) binary Hamming code, the (4, 2, 3) ternary tetracode, the (4, 2, 3) code over F/sub 4/, and the Z/sub 4/-linear (8. 4, 4) octacode.

We introduce space-time block coding, a new paradigm for communication over Rayleigh fading channels using multiple transmit antennas. Data is encoded using a space-time block code and the encoded data is split into n streams which are simultaneously transmitted using n transmit antennas. The received signal at each receive antenna is a linear superposition of the n transmitted signals perturbed by noise. Maximum-likelihood decoding is achieved in a simple way through decoupling of the signals transmitted from different antennas rather than joint detection. This uses the orthogonal structure of the space-time block code and gives a maximum-likelihood decoding algorithm which is based only on linear processing at the receiver. Space-time block codes are designed to achieve the maximum diversity order for a given number of transmit and receive antennas subject to the constraint of having a simple decoding algorithm. The classical mathematical framework of orthogonal designs is applied to construct space-time block codes. It is shown that space-time block codes constructed in this way only exist for few sporadic values of n. Subsequently, a generalization of orthogonal designs is shown to provide space-time block codes for both real and complex constellations for any number of transmit antennas. These codes achieve the maximum possible transmission rate for any number of transmit antennas using any arbitrary real constellation such as PAM. For an arbitrary complex constellation such as PSK and QAM, space-time block codes are designed that achieve 1/2 of the maximum possible transmission rate for any number of transmit antennas. For the specific cases of two, three, and four transmit antennas, space-time block codes are designed that achieve, respectively, all, 3/4, and 3/4 of maximum possible transmission rate using arbitrary complex constellations. The best tradeoff between the decoding delay and the number of transmit antennas is also computed and it is shown that many of the codes presented here are optimal in this sense as well.

The information capacity of wireless communication systems may be increased dramatically by employing multiple transmit and receive antennas. The goal of system design is to exploit this capacity in a practical way. An effective approach to increasing data rate over wireless channels is to employ space-time coding techniques appropriate to multiple transmit antennas. These space-time codes introduce temporal and spatial correlation into signals transmitted from different antennas, so as to provide diversity at the receiver, and coding gain over an uncoded system. For large number of transmit antennas and at high bandwidth efficiencies, the receiver may become too complex whenever correlation across transmit antennas is introduced. This paper dramatically reduces encoding and decoding complexity by partitioning antennas at the transmitter into small groups, and using individual space-time codes, called the component codes, to transmit information from each group of antennas. At the receiver, an individual space-time code is decoded by a novel linear processing technique that suppresses signals transmitted by other groups of antennas by treating them as interference. A simple receiver structure is derived that provides diversity and coding gain over uncoded systems. This combination of array processing at the receiver and coding techniques for multiple transmit antennas can provide reliable and very high data rate communication over narrowband wireless channels. A refinement of this basic structure gives rise to a multilayered space-time architecture that both generalizes and improves upon the layered space-time architecture proposed by Foschini (see Bell Labs Tech. J., vol.1, no.2, 1996).

This paper presents the theory and practice of a new advanced modem technology suitable for high-data-rate wireless communications and presents its performance over a frequency-flat Rayleigh fading channel. The new technology is based on space-time coded modulation (STCM) with multiple transmit and/or multiple receive antennas and orthogonal pilot sequence insertion (O-PSI). In this approach, data is encoded by a space-time (ST) channel encoder and the output of the encoder is split into N streams to be simultaneously transmitted using N transmit antennas. The transmitter inserts periodic orthogonal pilot sequences in each of the simultaneously transmitted bursts. The receiver uses those pilot sequences to estimate the fading channel. When combined with an appropriately designed interpolation filter, accurate channel state information (CSI) can be estimated for the decoding process. Simulation results of the proposed modem, as applied to the IS-136 cellular standard, are presented. We present the frame error rate (FER) performance results as a function of the signal-to-noise ratio (SNR) and the maximum Doppler frequency, in the presence of timing and frequency offset errors. Simulation results show that for a 10% FER, a 32-state eight-phase-shift keyed (8-PSK) ST code with two transmit and two receive antennas can support data rates up to 55.8 kb/s on a 30-kHz channel, at an SNR of 11.7 dB and a maximum Doppler frequency of 180 Hz. Simulation results for other codes and other channel conditions are also provided. We also compare the performance of the proposed STCM scheme with delay diversity schemes and conclude that STCM can provide significant SNR improvement over simple delay diversity.

This paper develops coding and signal processing approaches for a novel optical recording channel that arises from electron-trapping phosphor materials. The recording medium allows multiple reads and writes, and one important feature is that the read process serves to erase the disk. This feature would enable vendors of prerecorded video to provide customers with one-time services. For applications where this feature is not desirable, the data can be immediately rewritten. From a communications viewpoint, the most important feature of this new channel is that, subject to a peak constraint, it supports a continuum of recording levels. The combination of read and write processes creates a partial-response channel, and the ability to write a continuum of levels makes it possible to employ precoding techniques, such as the one developed by Tomlinson (1971) and by Miyakawa and Harashima (1969). This is fundamentally different from magnetic data storage, where the read/write process creates a partial-response channel but where it is only possible to write two levels at the input to that channel. This paper shows that the use of precoding and coset codes can significantly improve upon the recording densities (and recording rates) that can be achieved by using M-ary run length constrained codes to eliminate intersymbol interference (ISI) at the output of the read/write process. The approach presented is applicable to any optical recording channel that supports a continuum of recording levels.

In 1948 Shannon developed fundamental limits on the efficiency of communication over noisy channels. The coding theorem asserts that there are block codes with code rates arbitrarily close to channel capacity and probabilities of error arbitrarily close to zero. Fifty years later, codes for the Gaussian channel have been discovered that come close to these fundamental limits. There is now a substantial algebraic theory of error-correcting codes with as many connections to mathematics as to engineering practice, and the last 20 years have seen the construction of algebraic-geometry codes that can be encoded and decoded in polynomial time, and that beat the Gilbert-Varshamov bound. Given the size of coding theory as a subject, this review is of necessity a personal perspective, and the focus is reliable communication, and not source coding or cryptography. The emphasis is on connecting coding theories for Hamming and Euclidean space and on future challenges, specifically in data networking, wireless communication, and quantum information theory.

The problem of finding quantum error correcting codes is transformed into the problem of finding additive codes over the field GF(4) which are self-orthogonal with respect to a certain trace inner product. Many new codes and new bounds are presented, as well as a table of upper and lower bounds on such codes of length up to 30 qubits.

When a block modulation code is concatenated with an error-correction code (ECC) in the standard way, the use of a modulation code with long block lengths results in error propagation. This article analyzes the performance of modified concatenation, which involves reversing the order of modulation and the ECC. This modified scheme reduces the error propagation, provides greater flexibility in the choice of parameters, and facilitates soft-decision decoding, with little or no loss in transmission rate. In particular, examples are presented which show how this technique can allow fewer interleaves per sector in hard disk drives, and permit the use of more sophisticated block modulation codes which are better suited to the channel.

We consider the design of channel codes for improving the data rate and/or the reliability of communications over fading channels using multiple transmit antennas. Data is encoded by a channel code and the encoded data is split into n streams that are simultaneously transmitted using n transmit antennas. The received signal at each receive antenna is a linear superposition of the n transmitted signals perturbed by noise. We derive performance criteria for designing such codes under the assumption that the fading is slow and frequency nonselective. Performance is shown to be determined by matrices constructed from pairs of distinct code sequences. The minimum rank among these matrices quantifies the diversity gain, while the minimum determinant of these matrices quantifies the coding gain. The results are then extended to fast fading channels. The design criteria are used to design trellis codes for high data rate wireless communication. The encoding/decoding complexity of these codes is comparable to trellis codes employed in practice over Gaussian channels. The codes constructed here provide the best tradeoff between data rate, diversity advantage, and trellis complexity. Simulation results are provided for 4 and 8 PSK signal sets with data rates of 2 and 3 bits/symbol, demonstrating excellent performance that is within 2-3 dB of the outage capacity for these channels using only 64 state encoders.

We revisit space-time codes for a mobile communication system that employs multiple antennas at the base station and optional antenna diversity at the mobile station. The realistic case when the channel state is not completely known is considered. It is assumed that the channel estimator extracts the fade coefficients using orthogonal pilot tones. Mismatch analysis is then carried out. It is proved that in the absence of ideal channel state information the design criteria for space-time codes developed in Tarokh et al. (1997) is still valid for the equal energy constellation case. Using our derivation, it is observed that channel estimation techniques commonly used over rapidly fading channels can be used in conjunction with space-time codes provided that the number of transmit antennas is small.

We consider the design of channel codes for improving the data rate and/or the reliability of communications over fading channels using multiple transmit antennas. Here, data is encoded by a channel code and the encoded data is split into n streams that are simultaneously transmitted using n transmit antennas. The received signal at each receive antenna is a linear superposition of the n transmitted signals. We derive performance criteria for designing channel codes under the assumption that the fading is slow and frequency non-selective. Performance is shown to be determined by diversity gain quantified by ranks and coding gain quantified by determinants of certain matrices that are constructed from the code sequences.

Invertible wavelet transforms that map integers to integers are important for lossless representations. We present an approach to build integer to integer wavelet transforms based upon the idea of factoring wavelet transforms into lifting steps. This allows the construction of an integer version of every wavelet transform. We demonstrate the use of these transforms in lossless image compression.

We consider the design of channel codes for improving the data rate and/or the reliability of communications using multiple transmit antennas over a fading channel. It is assumed that the transmitter does not know the channel but seeks to choose a codebook that guarantees a diversity gain of r/sub 1/ when there is no mobility and a diversity gain of r/sub 2//spl ges/r/sub 1/ when the channel is fast fading. A solution to this problem is unveiled in this paper. Here, the encoded data is split into n streams that are simultaneously transmitted using n transmit antennas. The signal received at each receive antenna is a superposition of the faded versions of the n transmitted signals. We derive performance criteria for designing codes having the aforementioned properties. Performance is shown to be determined by diversity advantage quantified by a rank/distance and coding advantage quantified by a determinant/product criterion. The criteria is used to design codes for both slow and rapid fading channels. The constructed codes have remarkable performance in low signal to noise ratios and are suitable for improving the frequency reuse factor under a variety of mobility conditions.

This paper describes how 2-adic numbers can be used to analyze the structure of binary cyclic codes and of cyclic codes defined over Z/sub 2(a)/, a/spl ges/2, the ring of integers modulo 2/sup a/. It provides a 2-adic proof of a theorem of McEliece that characterizes the possible Hamming weights that can appear in a binary cyclic code. A generalization of this theorem is derived that applies to cyclic codes over Z/sub 2(a)/ that are obtained from binary cyclic codes by a sequence of Hensel lifts. This generalization characterizes the number of times a residue modulo 2/sup a/ appears as a component of an arbitrary codeword in the cyclic code. The limit of the sequence of Hensel lifts is a universal code defined over the 2-adic integers. This code was first introduced by Calderbank and Sloane (1995), and is the main subject of this paper. Binary cyclic codes and cyclic codes over Z/sub 2(a)/ are obtained from these universal codes by reduction modulo some power of 2. A special case of particular interest is cyclic codes over Z/sub 4/ that are obtained from binary cyclic codes by means of a single Hensel lift. The binary images of such codes under the Gray isometry include the Kerdock, Preparata, and Delsart-Goethals codes. These are nonlinear binary codes that contain more codewords than any linear code presently known. Fundamental understanding of the composition of codewords in cyclic codes over Z/sub 4/ is central to the search for more families of optimal codes. This paper also constructs even unimodular lattices from the Hensel lift of extended binary cyclic codes that are self-dual with all Hamming weights divisible by 4. The Leech lattice arises in this way as do extremal lattices in dimensions 32 through 48.

An analysis of the generalized cross constellation (GCC) is presented and a new perspective on its coding algorithm is described. We show how the GCC can be used to address generic sets of symbol points in any multidimensional space through an example based on the matched spectral null coding used in magnetic recording devices. We also prove that there is a forbidden rate region of fractional coding rates that are practically unrealizable using the GCC construction. We introduce the idea of a constellation tree and show how its decomposition can be used to design GCCs matching desired parameters. Following this analysis, an algorithm to design the optimal rate GCC from a restriction on the maximum size of its constellation signal set is given, and a formula for determining the size of the GCC achieving a desired coding rate is derived. We finish with an upper bound on the size of the constellation expansion ratio.

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock (1972) and Preparata (1968) codes that can be very simply constructed as binary images, under the Gray map, of linear codes over Z/sub 4/ that are defined by means of parity checks involving Galois rings. This paper describes how Fourier transforms on Galois rings and elementary symmetric functions can be used to derive lower bounds on the minimum distance of such codes. These methods and techniques from algebraic geometry are applied to find the exact minimum distance of a family of Z/sub 4/. Linear codes with length 2/sup m/ (m, odd) and size 2(2/sup m+1/-5m-2). The Gray image of the code of length 32 is the best (64, 2/sup 37/) code that is presently known. This paper also determines the exact minimum Lee distance of the linear codes over Z/sub 4/ that are obtained from the extended binary two- and three-error-correcting BCH codes by Hensel lifting. The Gray image of the Hensel lift of the three-error-correcting BCH code of length 32 is the best (64, 2/sup 32/) code that is presently known. This code also determines an extremal 32-dimensional even unimodular lattice.

Binary m-sequences are maximal-length sequences generated by shift registers of length m, that are employed in navigation, radar, and spread-spectrum communication. It is well known that given a pair of distinct m-sequences, the crosscorrelation function must take on at least three values. This correspondence addresses a conjecture made by Helleseth in 1976, that if m is a power of 2, then there are no pairs of binary m-sequences with a 3-valued crosscorrelation function. This conjecture is proved under the assumption that the three correlation values are symmetric about -1.

The 12-dimensional Coxeter-Todd lattice can be obtained by lifting the ternary Golay code to a code over the integers mod 9 and applying Construction A.

A family of quaternary (Z/sub 4/-alphabet) sequences of length L=2/sup r/-1, size M/spl ges/L/sup 2/+3L+2, and maximum nontrivial correlation parameter C/sub max//spl les/2/spl radic/(L+1)+1 is presented. The sequence family always contains the four-phase family /spl Ascr/. When r is odd, it includes the family of binary Gold sequences. The sequence family is easily generated using two shift registers, one binary, the other quaternary. The distribution of correlation values is provided. The construction can be extended to produce a chain of sequence families, with each family in the chain containing the preceding family. This gives the design flexibility with respect to the number of intermittent users that can be supported, in a code-division multiple-access cellular radio system. When r is odd, the sequence families in the chain correspond to shortened Z/sub 4/-linear versions of the Delsarte-Goethals codes.

A Markovian technique is described to calculate the exact performance of the Viterbi algorithm used as either a channel decoder or a source encoder for a convolutional code. The probability of information bit error and the expected Hamming distortion are computed for codes of various rates and constraint lengths. The concept of tie-breaking rules is introduced and its influence on decoder performance is examined. Computer simulation is used to verify the accuracy of the results. Finally, we discuss the issue of when a coded system outperforms an uncoded system in light of the new results.>

We construct new self-dual and isodual codes over the integers module 4. The binary images of these codes under the Gray map are nonlinear, but formally self-dual. The construction involves Hensel lifting of binary cyclic codes. Quaternary quadratic residue codes are obtained by Hensel lifting of the classical binary quadratic residue codes. Repeated Hensel lifting produces a universal code defined over the 2-adic integers. We investigate the connections between this universal code and the codes defined over Z/sub 4/, the composition of the automorphism group, and the structure of idempotents over Z/sub 4/. We also derive a square root bound on the minimum Lee weight, and explore the connections with the finite Fourier transform. Certain self-dual codes over Z/sub 4/ are shown to determine even unimodular lattices, including the extended quadratic residue code of length q+1, where q/spl equiv/-1(mod8) is a prime power. When q=23, the quaternary Golay code determines the Leech lattice in this way. This is perhaps the simplest construction for this remarkable lattice that is known.>

The paper describes Markov methods for analyzing the expected and worst case performance of sequence-based methods of quantization. We suppose that the quantization algorithm is dynamic programming, where the current step depends on a vector of path metrics, which we call a metric function. Our principal objective is a concise representation of these metric functions and the possible trajectories of the dynamic programming algorithm. We shall consider quantization of equiprobable binary data using a convolutional code. Here the additive group of the code splits the set of metric functions into a finite collection of subsets. The subsets form the vertices of a directed graph, where edges are labeled by aggregate incremental increases in mean squared error (MSE). Paths in this graph correspond both to trajectories of the Viterbi algorithm and to cosets of the code. For the rate 1/2 convolutional code [1+D/sup 2/, 1+D+D/sup 2/], this graph has only nine vertices. In this case it is particularly simple to calculate per dimension expected and worst case MSE, and performance is slightly better than the binary [24, 12] Golay code. Our methods also apply to quantization of arbitrary symmetric probability distributions on [0, 1] using convolutional codes. For the uniform distribution on [0, 1], the expected MSE is the second moment of the "Voronoi region" of an infinite-dimensional lattice determined by the convolutional code. It may also be interpreted as an increase in the reliability of a transmission scheme obtained by nonequiprobable signaling. For certain convolutional codes we obtain a formula for expected MSE that depends only on the distribution of differences for a single pair of path metrics.>

We present an analog of the well-known Weil-Carlitz-Uchiyama (1948, 1957) upper bound for exponential sums over finite fields for exponential sums over Galois rings. Some examples are given where the bound is tight. The bound has immediate application to the design of large families of phase-shift-keying sequences having low correlation and an alphabet of size p/sup e/. p, prime, e/spl ges/2. Some new constructions of eight-phase sequences are provided.>

Binary m-sequences are maximal length sequences generated by shift registers of length m, that are employed in navigation, radar, and spread-spectrum communications systems, because of their crosscorrelation properties. It is well known that given a pair of distinct m-sequences, the crosscorrelation function must take on at least three values. The article considers crosscorrelation functions that take on exactly three values, and where these values are preferred in that they are small. The main result is a proof of a conjecture made by Sarwate and Pursley in 1980, that if m/spl equiv/0 (mod 4) then there are no preferred pairs of binary m-sequences. The proof makes essential use of a deep theorem of McEliece (1971) that restricts the possible weights that can occur in a binary cyclic code.>

Testing of high-speed voiceband modems has revealed a significant increase in distortion for points near the perimeter of a QAM signal constellation. This distortion increases with distance from the center of the constellation and limits performance at data rates above 19.2 kb/s. The perimeter distortion can be reduced by transforming the signal constellation so that points near the center are closer together, and points near the perimeter are further apart. When the channel SNR is high, such a transformation reduces immunity to Gaussian noise because points near the center of the transformed constellation are closer together than in a uniformly spaced constellation with the same average power. This paper demonstrates theoretically that for channel SNRs of practical interest. There is actually a small gain in immunity to Gaussian noise. In fact, an appropriate coded modulation scheme can produce gains of about 0.25 dB.>

Calculates the per-dimension mean squared error /spl mu/(S) of the two-state convolutional code C with generator matrix /spl lsqb/1,1+D/spl rsqb/, for the symmetric binary source S=(0,1), and for the uniform source S=/spl lcub/0,1/spl rcub/. When S=(0,1), the quantity /spl mu/(S) is the second moment of the coset weight distribution, which gives the expected Hamming distance of a random binary sequence from the code. When S=/spl lcub/0,1/spl rcub/, the quantity /spl mu/(S) is the second moment of the Voronoi region of the module 2 binary lattice determined by C. The key observation is that a convolutional code with 2/sup /spl upsi// states gives 2/sup /spl upsi// approximations to a given source sequence, and these approximations do not differ very much. It is possible to calculate the steady state distribution for the differences in these path metrics, and hence, the second moment. The authors only give details for the convolutional code /spl lsqb/1,1+D/spl rsqb/, but the method applies to arbitrary codes. They also define the covering radius of a convolutional code, and calculate this quantity for the code /spl lsqb/1,1+D/spl rsqb/.>

Random overlapping pulse-position modulation (OPPM) sequences result in an unrecoverable error floor on both the probability of erroneous synchronization and the probability of symbol error when only chip synchronization is present. It is known, however, that for a given sequence length M, a subset of the set of all possible sequences is synchronizable in the sense that in the absence of noise, the receiver can correctly symbol synchronize by observing M or more symbol intervals. The authors design finite-state machines and codes over a J-ary alphabet, which produce sequences with the property that every subsequence of length L is synchronizable. Some of the codes, in addition to being synchronizable, produce a coding gain. For an optical Poisson channel the authors introduce joint synchronization and detection algorithms that utilize the memory in the encoded sequences to produce joint estimates of timing and sequences. Their performance is analyzed through simulations and analytical results.>

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z/sub 4/, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z/sub 4/ domain implies that the binary images have dual weight distributions. The Kerdock and "Preparata" codes are duals over Z/sub 4/-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and "Preparata" codes are Z/sub 4/-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z/sub 4/, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the "Preparata" code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z/sub 4/, but extended Hamming codes of length n/spl ges/32 and the Golay code are not. Using Z/sub 4/-linearity, a new family of distance regular graphs are constructed on the cosets of the "Preparata" code.>

Given a code C, invariant linear forms are used to study the designs afforded by codewords of a fixed weight. The most important theorem relating codes and designs is due to Assmus and Mattson [J. Combin. Theory, 6 (1969), pp. 122–151], and this theorem is extended in different ways. For extremal self dual codes over the fields $\mathbb{F}_2 $ and $\mathbb{F}_3 $, it is proved that the t-designs afforded by the codewords of any fixed weight exhibit extra regularity with respect to $( t + 2 )$-sets. The same is true for the design afforded by the codewords of minimum weight in an extremal self-dual code over $\mathbb{F}_4 $. The invariant linear forms are also used to construct Boolean designs with several block sizes, extending previous work by Safavi-Naini and Blake [Utilitas Math., 14 (1978), pp. 49–63], [Ars Combin., 7 (1979), pp. 135–151], [Inform. and Control, 42 (1986), pp. 261–282].

Two combined unequal error protection (UEP) coding and modulation schemes are proposed. The first method multiplexes different coded signal constellations, with each coded constellation providing a different level of error protection. In this method, a codeword specifies the multiplexing rule and the choice of the codeword from a fixed codebook is used to convey additional important information. The decoder determines the multiplexing rule before decoding the rest of the data. The second method is based on partitioning a signal constellation into disjoint subsets in which the most important data sequence is encoded, using most of the available redundancy, to specify a sequence of subsets. The partitioning and code construction is done to maximize the minimum Euclidean distance between two different valid subset sequences. This leads to ways of partitioning the signal constellations into subsets. The less important data selects a sequence of signal points to be transmitted from the subsets. A side benefit of the proposed set partitioning procedure is a reduction in the number of nearest neighbors, sometimes even over the uncoded signal constellation.>

Asymptotic upper bounds on the minimum distance of trellis codes are derived. A universal bound and bounds specific to phase-shift keying (PSK) and quadrature amplitude modulation (QAM) signal sets are obtained.>

The problem of shaping signal constellations that are designed for the Gaussian channel is considered. The signal constellation consists of all points from some translate of a lattice Lambda that lie within a region R. The signal constellation is partitioned into T annular subconstellations Omega /sub o/,..., Omega /sub T-1/, by scaling the region R. Signal points in the same subconstellation are used equiprobably, and a shaping code selects region Omega /sub i/ with frequency f/sub i/. If the signal constellation is partitioned into annular subconstellations of unequal size. then the transmission rate should vary with the choice of codeword in the shaping code. and it will be necessary to queue the data in buffers. It is described how the balanced binary codes constructed by D. E. Knuth (1986) can be used to avoid a data rate that is probabilistic. The basic idea is that if symbols 0 and 1 represent constellations of unequal size. and if all shaping codewords have equally many 0's and 1's, then the data rate will be deterministic.>

An upper bound on the minimum squared distance of trellis codes by packing Voronoi cells is derived and compared with previously known bounds. The authors focus on codes with small memory for modulation formats such as pulse amplitude modulation (PAM), m-ary quadrature amplitude modulation (QAM), and m-ary phase shift keying (PSK). The bound is tight to search results for coset codes with a small number of states.>

Let w/sub 1/=d,w/sub 2/,...,w/sub s/ be the weights of the nonzero codewords in a binary linear (n,k,d) code C, and let w'/sub 1/, w'/sub 2/, ..., w'/sub 3/, be the nonzero weights in the dual code C1. Let t be an integer in the range 0or=d+4 then either the words of any nonzero weight w/sub i/ form a (t+1)-design or else the codewords of minimal weight d form a (1,2,...,t,t+2)-design. If in addition C is self-dual with all weights divisible by 4 then the codewords of any given weight w/sub i/ form either a (t +1)-design or a (1,2,...,t,t+2)-design. The proof avoids the use of modular forms.>

A quasi-symmetric t-design is a t-design with two block intersection sizes p and q (where $p < q$). Quasi-symmetric 3-designs are classified with $p = 1$. The only nontrivial examples are the 4-(23, 7, 1) Witt design, and its residual, a 3-(22, 7, 4) design. This proves a conjecture of Sane and Shrikhande. The method is to reduce the classification problem to that of finding all integer points on the elliptic curves $y^2 = x^3 - 11x^2 + 32x$ and $y^2 = x^3 - 4x + 4$.

Signaling schemes for the Gaussian channel based on finite-dimensional lattices are considered. The signal constellation consists of all lattice points within a region R, and the shape of this region determines the average signal power. Spherical signal constellations minimize average signal power, and in the limit as N to infinity , the shape gain of the N-sphere over the N-cube approaches pi e/6 approximately=1.53 dB. A nonequiprobable signaling scheme is described that approaches this full asymptotic shape gain in any fixed dimension. A signal constellation, Omega is partitioned into T subconstellations Omega /sub 0/, . . ., Omega /sub tau -1/ of equal size by scaling a basic region R. Signal points in the same subconstellation are used equiprobably, and a shaping code selects the subconstellation Omega /sub i/ with frequency f/sub i/. Shaping codes make it possible to achieve any desired fractional bit rate. The schemes presented are compared with equiprobable signaling schemes based on Voronoi regions of multidimensional lattices. For comparable shape gain and constellation expansion ratio, the peak to average power ratio of the schemes presented is superior. Furthermore, a simple table lookup is all that is required to address points in the constellations. It is also shown that it is possible to integrate coding and nonequiprobable signaling within a common multilevel framework.>

A description is given of a methodology for designing baseband line codes with prescribed spectral nulls in the transmitted spectrum. These codes have the property that the transmitted power is adjustable (with a concomitant change in spectral shape, i.e. null width) and can be made arbitrarily close to the innovations power, while keeping the minimum distance between signal points (or sequences) constant. The essential design step requires the spectral factorization of a certain trigonometric polynomial. The line code that results can easily be used in conjunction with a large class of trellis-coded modulation schemes. Specific baseband codes are constructed using a representation of the general theory that involves a dither variable, which is used to create integer symbols and to minimize the size of the symbol alphabet. Emphasis is on the design of line codes with a double null at DC using the symbol alphabet (+or-1, +or-3).>

The authors analyze a model of a movable-head disk system with two read/write heads maintained a fixed distance d apart on each arm. Successive request-addresses are assumed to be independent random variables, uniformly distributed over the set of cylinders. The purpose of the analysis is to find that value of d which minimizes the expected seek time per request, assuming that seek time varies linearly with the distance z traveled by the heads. The authors extend an earlier analysis of this model to more general seek-time characteristics which take into account nonlinear acceleration effects. Detailed results, combining both analysis and simulation experiments, are presented for seek times linear in z/sup alpha /, 0>

H. Imai and S. Hirakawa have proposed (1977) a multilevel coding method based on binary block codes that admits a staged decoding procedure. The author extends the coding method to coset codes and shows how to calculate minimum squared distance and path multiplicity in terms of the norms and multiplicities of the different cosets. The multilevel structure allows the redundancy in the coset selection procedure to be allocated efficiently among the different levels. It also allows the use of suboptimal multistage decoding procedures that have performance/complexity advantages over maximum-likelihood decoding.>

A multilevel approach to the design of DC-free line codes is presented. The different levels can be used for different purposes, for example, to control the maximum accumulated charge or to guarantee a certain minimum distance. The advantages of codes designed by this method over similar codes are the improved run-length/accumulated-charge parameters, higher transmission rate, and the systematic nature of the code construction. The multilevel structure allows the redundancy in the signal selection procedure to be allocated efficiently among the different levels. It also allows the use of suboptimal staged decoding procedures that have performance/complexity advantages over maximum-likelihood decoding.>

Known coset codes are adapted for use on partial response channels or to generate signals with spectral nulls. By using coset precoding and running digital sum feedback, any desired tradeoff can be achieved between the power and spectra of the relevant sequences, up to the optimum tradeoff possible. A fundamental theorem specifying this optimum tradeoff is given. A maximum-likelihood-sequence-estimation (MLSE) decoder for the original code may be used for the adapted code, and such a decoder then attains the minimum squared distance of the original code. These methods sometimes generate codes with greater minimum squared distance than that of the original code; this distance can be attained by augmented decoders, although such decoders inherently require long decoding delays and may be subjected to quasi-catastrophic error propagation. The authors conclude that, at least for sequences supporting large numbers of bits per symbol, coset codes can be adapted to achieve effectively the same performance and complexity on partial response channels, or for sequences with spectral nulls, as they do in the ordinary memoryless case.>

Two mathematical models dealing with optimal placement of directories on disk devices are analyzed. Storage addresses on the disk are approximated by points in the interval [0, 1]. Requests for information on the disk are represented by a sequence of file names. To process a request, a read-write head is first moved to a directory kept on the disk that specifies the address of the file, and then a head is moved to the specified address. The addresses are assumed to be independent and uniform on [0,1]. In the first model we consider a system of two heads separated by a fixed distance d and a directory situated at 0 ≤ x ≤ 1. In the second model we consider a system consisting of one head and n ≥ 2 directories at 0 ≤ x 1 < x 2 < … < x n ≤ 1. For both models we study the problem of finding those values of the parameters that minimize the expected head motion to process a request in statistical equilibrium.

A method is described for modifying classical N-dimensional trellis codes to provide baseband codes that combine a spectral null at DC with significant coding gain. The information rate of the classical code is decreased by one bit, and this extra redundancy is used to keep the running digital sum bounded. Equivalently, if the rate is held constant, then twice as many signal points are needed, causing a power penalty of 6/N dB. Baseband trellis codes are presented for several information rates together with complete spectral plots and performance comparisons. A method of constructing baseband codes with multiple spectral nulls is also described.>

Any code C with covering radius R must satisfy a set of linear inequalities that involve the Lloyd polynomial L/sub R/(x); these generalize the sphere bound. Syndrome graphs associated with a linear code C are introduced to help keep track of low-weight vectors in the same coset of C (if there are too many such vectors C cannot exist). Illustrations show that t(17, 10)=3 and t(23, 15)=3 where t(n, k) is the smallest covering radius of any (n, k) code.>

A new technique is proposed for constructing trellis codes. which provides an alternative to Ungerboeck's method of "set partitioning." The new codes use a signal constellation consisting of points from ann-dimensional lattice\Lambda, with an equal number of points from each coset of a sublattice\Lambda '. One part of the input stream drives a generalized convolutional code whose outputs are cosets of\Lambda ', while the other part selects points from these cosets. Several of the new codes are better than those previously known.

An 8-state trellis code is described that uses a signal constellation from the 8-dimensional Gosset lattice E8. It can be used for example to transmit data at 9.6, 14.4, and 19.2 kbits/s with a nominal coding gain of close to 6 dB.

The nonexistence of a uniformly-packed[70, 58, 5]codeC^{\perp}is proved by examining geometries associated with the3-weight codeC.

Calderbank, Heegard, and Ozarow [1] have suggested a method of designing codes for channels with intersymbol interference, such as the magnetic recording channel. These codes are designed to exploit intersymbol interference. The standard method is to minimize intersymbol interference by constraining the input to the channel using run-length limited sequences. Calderbank, Heegard, and Ozarow considered an idealized model of an intersymbol interference channel that leads to the problem of designing codes for a partial response channel with transfer function(1 - D^{N}) /2, where the channel inputs are constrained to be\pm 1. This problem is considered here. Channel inputs are generated using a nontrivial coset of a binary convolutional code. The coset is chosen to limit the zero-run length of the output of the channel and so maintain clock synchronization. The minimum squared Euclidean distance between outputs corresponding to distinct inputs is bounded below by the free distance of a second convolutional code which we call the magnitude code. An interesting feature of the analysis is that magnitude codes that are catastrophic may perform better than those that are noncatastrophic.

A trellis code is a "sliding window" method of encoding a binary data stream as a sequence of signal points in Rn. When a trellis code is used to encode data at the rate ofkbits/channel symbol, each channel input depends not only on the most recent block ofkbits to enter the encoder, but will also depend on a set of ν bits preceding this block. The ν bits determine the state of the encoder and the most recent block ofkbits generates the channel symbol conditional on the encoder state. The performance of a trellis code depends on a suitably defined minimum distance property of that code. This paper obtains upper bounds on this minimum distance that are better than any previously known.

A mathematical model of computer disk storage devices having two movable read/write heads is studied.Storage addresses are approximated by points in the continuous interval [0, 1], and requests for information on the disk are processed first-come-first-served.We assume that the disk heads are maintained a fixed distance d apart; that is, in processing a request, both heads are moved the same distance in the same direction.Assuming that successive requested locations are independently and uniformly distributed over [0, 1], we calculate the invariant measure of a Markov chain representing successive head positions under the nearer-server rule: Requests in [0, a t] are processed by the left head, those in [1 -d, 1] by the right head, and those in [d, 1 -d] by the nearer of the two heads.Our major objective is the equilibrium expected distance E(d) that the heads are moved in processing a request.For the problem of designing the separation distance d, we show that E (0.44657) ffi 0.16059 ffi mindE(d).Thus, a basic insight of the analysis is that a system with two heads performs more than twice as well as a system with a single head.The results are compared with those for other two-head disk systems.Finally, numerical results are presented that demonstrate that the nearer-server rule is very nearly optimal under the fixed head-separation constraint.

A trellis code is a "sliding window" method of encoding a binary data stream as a sequence of real or complex numbers that are input to a noisy transmission channel. Ungerboeck has constructed simple trellis codes that provide the same noise immunity as is given by increasing the power of uncoded transmission by factors ranging from two to four. His method is to specify an underlying convolutional code and a rule (mapping by set partitioning) that maps the output of this code onto a fixed signal constallation. A new description of a trellis code is given that combines these two steps into one. The new description is analytic rather than graphical. Many practical codes can be described very simply, and strict bounds on performance can be obtained. A method for differential encoding trellis codes is presented that was suggested by the authors' representation.

We establish a square root bound on the minimum weight in the quasi-cyclic binary codes constructed by Bhargava, Tavares, and Shiva. The proof rests on viewing the codes as ideals in a group algebra over GF (4). Theorem 6 answers a question raised by F. J. MacWilliams and N. J. A. Sloane in {\em The Theory of Error-Correcting Codes.} Theorems 3, 4, and 5 provide information about the way the nonzero entries of a codeword of minimum weight are distributed among the coordinate positions.