A Combinatorial Family of Near Regular LDPC Codes

An elementary combinatorial Tanner graph construction for a family of near-regular low density parity check (LDPC) codes achieving high girth is presented. These codes are near regular in the sense that the degree of a left/right vertex is allowed to differ by at most one from the average. The construction yields in quadratic time complexity an asymptotic code family with provable lower bounds on the rate and the girth for a given choice of block length and average degree. The construction gives flexibility in the choice of design parameters of the code like rate, girth and average degree. Performance simulations of iterative decoding algorithm for the AWGN channel on codes designed using the method demonstrate that these codes perform better than regular PEG codes and MacKay codes of similar length for all values of Signal to noise ratio.

Generalized Silver Codes

For an n(t) transmit, n(r) receive antenna system (n(t) x n(r) system), a full-rate space time block code (STBC) transmits at least n(min) = min(n(t), n(r))complex symbols per channel use. The well-known Golden code is an example of a full-rate, full-diversity STBC for two transmit antennas. Its ML-decoding complexity is of the order of M(2.5) for square M-QAM. The Silver code for two transmit antennas has all the desirable properties of the Golden code except its coding gain, but offers lower ML-decoding complexity of the order of M(2). Importantly, the slight loss in coding gain is negligible compared to the advantage it offers in terms of lowering the ML-decoding complexity. For higher number of transmit antennas, the best known codes are the Perfect codes, which are full-rate, full-diversity, information lossless codes (for n(r) >= n(t)) but have a high ML-decoding complexity of the order of M(ntnmin) (for n(r) < n(t), the punctured Perfect codes are considered). In this paper, a scheme to obtain full-rate STBCs for 2(a) transmit antennas and any n(r) with reduced ML-decoding complexity of the order of M(nt)(n(min)-3/4)-0.5 is presented. The codes constructed are also information lossless for >= n(t), like the Perfect codes, and allow higher mutual information than the comparable punctured Perfect codes for n(r) < n(t). These codes are referred to as the generalized Silver codes, since they enjoy the same desirable properties as the comparable Perfect codes (except possibly the coding gain) with lower ML-decoding complexity, analogous to the Silver code and the Golden code for two transmit antennas. Simulation results of the symbol error rates for four and eight transmit antennas show that the generalized Silver codes match the punctured Perfect codes in error performance while offering lower ML-decoding complexity.

Training-Symbol Embedded, High-Rate, Single-Symbol ML-Decodable, Distributed STBCs for Relay Networks

Distributed space-time block codes (DSTBCs) from complex orthogonal designs (CODs) (both square and nonsquare), coordinate interleaved orthogonal designs (CIODs), and Clifford unitary weight designs (CUWDs) are known to lose their single-symbol ML decodable (SSD) property when used in two-hop wireless relay networks using amplify and forward protocol. For such networks, in this paper, three new classes of high rate, training-symbol embedded (TSE) SSD DSTBCs are constructed: TSE-CODs, TSE-CIODs, and TSE-CUWDs. The proposed codes include the training symbols inside the structure of the code which is shown to be the key point to obtain the SSD property along with the channel estimation capability. TSE-CODs are shown to offer full-diversity for arbitrary complex constellations and the constellations for which TSE-CIODs and TSE-CUWDs offer full-diversity are characterized. It is shown that DSTBCs from nonsquare TSE-CODs provide better rates (in symbols per channel use) when compared to the known SSD DSTBCs for relay networks. Important from the practical point of view, the proposed DSTBCs do not contain any zeros in their codewords and as a result, antennas of the relay nodes do not undergo a sequence of switch on/off transitions within every codeword, and, thus, avoid the antenna switching problem.

Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction

Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An [n, k, d] regenerating code permits the data to be recovered by connecting to any k of the n nodes in the network, while requiring that a failed node be repaired by connecting to any d nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case n = d + 1. In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of [n, k, d] and (b) Minimum Storage Regenerating (MSR) codes for all [n, k, d >= 2k - 2], using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number n of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with [n = d + 1, k, d >= 2k - 1].

Multigroup-Decodable STBCs from Clifford Algebras

A Space-Time Block Code (STBC) in K symbols (variables) is called g-group decodable STBC if its maximum-likelihood decoding metric can be written as a sum of g terms such that each term is a function of a subset of the K variables and each variable appears in only one term. In this paper we provide a general structure of the weight matrices of multi-group decodable codes using Clifford algebras. Without assuming that the number of variables in each group to be the same, a method of explicitly constructing the weight matrices of full-diversity, delay-optimal g-group decodable codes is presented for arbitrary number of antennas. For the special case of Nt=2a we construct two subclass of codes: (i) A class of 2a-group decodable codes with rate a2(a−1), which is, equivalently, a class of Single-Symbol Decodable codes, (ii) A class of (2a−2)-group decodable with rate (a−1)2(a−2), i.e., a class of Double-Symbol Decodable codes. Simulation results show that the DSD codes of this paper perform better than previously known Quasi-Orthogonal Designs.

Spreading Sequences for Asynchronous Spectrally Phase Encoded Optical CDMA

In phase encoding optical CDMA (OCDMA) the spreading is achieved by encoding the phase of signal spectrum. In this paper we first derive a mathematical model for the output of phase encoding OCDMA systems. Based on this model we introduce a metric to design spreading sequences for asynchronous transmission. Then we connect the phase encoding sequence design problem to OFDM PMEPR (peak to mean envelope power ratio) problem. Using this connection we conclude that designing sequences with good properties for samples of timing delay guarantees that the same sequence to be good for all timing delays. Finally using generalized bent function we manage to construct a family of sequences which are good for asynchronous phase encoding OCDMA systems and using these sequences we introduce an M-ary modulation scheme for phase encoding OCDMA

Asymptotically optimal cooperative wireless networks without constellation expansion

In this work, we construct a unified family of cooperative diversity coding schemes for implementing the orthogonal amplify-and-forward and the orthogonal selection-decode-and-forward strategies in cooperative wireless networks. We show that, as the number of users increases, these schemes meet the corresponding optimal high-SNR outage region, and do so with minimal order of signaling complexity. This is an improvement over all outage-optimal schemes which impose exponential increases in signaling complexity for every new network user. Our schemes, which are based on commutative algebras of normal matrices, satisfy the outage-related information theoretic criteria, the duplex-related coding criteria, and maintain reduced signaling, encoding and decoding complexities

Achieving the D-MG and DMD Tradeoffs of MIMO fading channels

An overview of our recent results relating to the explicit construction of space-time block codes achieving the DMG tradeoff of the quasi-static fading channel is presented. The results include the explicit construction of D-MG optimal codes,generalization of perfect codes to any number of transmit antennas as well as optimal diversity-multiplexing-delay constructions for the MIMO ARQ Channel.

The Future of Computation

The purpose of life is to obtain knowledge, use it to live with as much satisfaction as possible, and pass it on with improvements and modifications to the next generation.'' This may sound philosophical, and the interpretation of words may be subjective, yet it is fairly clear that this is what all living organisms--from bacteria to human beings--do in their life time. Indeed, this can be adopted as the information theoretic definition of life. Over billions of years, biological evolution has experimented with a wide range of physical systems for acquiring, processing and communicating information. We are now in a position to make the principles behind these systems mathematically precise, and then extend them as far as laws of physics permit. Therein lies the future of computation, of ourselves, and of life.

Coding for High-Density Recording on a 1-D Granular Magnetic Medium

In terabit-density magnetic recording, several bits of data can be replaced by the values of their neighbors in the storage medium. As a result, errors in the medium are dependent on each other and also on the data written. We consider a simple 1-D combinatorial model of this medium. In our model, we assume a setting where binary data is sequentially written on the medium and a bit can erroneously change to the immediately preceding value. We derive several properties of codes that correct this type of errors, focusing on bounds on their cardinality. We also define a probabilistic finite-state channel model of the storage medium, and derive lower and upper estimates of its capacity. A lower bound is derived by evaluating the symmetric capacity of the channel, i.e., the maximum transmission rate under the assumption of the uniform input distribution of the channel. An upper bound is found by showing that the original channel is a stochastic degradation of another, related channel model whose capacity we can compute explicitly.

Generalized distributive law for ML decoding of STBCs

The Generalized Distributive Law (GDL) is a message passing algorithm which can efficiently solve a certain class of computational problems, and includes as special cases the Viterbi's algorithm, the BCJR algorithm, the Fast-Fourier Transform, Turbo and LDPC decoding algorithms. In this paper GDL based maximum-likelihood (ML) decoding of Space-Time Block Codes (STBCs) is introduced and a sufficient condition for an STBC to admit low GDL decoding complexity is given. Fast-decoding and multigroup decoding are the two algorithms used in the literature to ML decode STBCs with low complexity. An algorithm which exploits the advantages of both these two is called Conditional ML (CML) decoding. It is shown in this paper that the GDL decoding complexity of any STBC is upper bounded by its CML decoding complexity, and that there exist codes for which the GDL complexity is strictly less than the CML complexity. Explicit examples of two such families of STBCs is given in this paper. Thus the CML is in general suboptimal in reducing the ML decoding complexity of a code, and one should design codes with low GDL complexity rather than low CML complexity.

On network coding for acyclic networks with delays

Problems related to network coding for acyclic, instantaneous networks (where the edges of the acyclic graph representing the network are assumed to have zero-delay) have been extensively dealt with in the recent past. The most prominent of these problems include (a) the existence of network codes that achieve maximum rate of transmission, (b) efficient network code constructions, and (c) field size issues. In practice, however, networks have transmission delays. In network coding theory, such networks with transmission delays are generally abstracted by assuming that their edges have integer delays. Using enough memory at the nodes of an acyclic network with integer delays can effectively simulate instantaneous behavior, which is probably why only acyclic instantaneous networks have been primarily focused on thus far. However, nulling the effect of the network delays are not always uniformly advantageous, as we will show in this work. Essentially, we elaborate on issues ((a), (b) and (c) above) related to network coding for acyclic networks with integer delays, and show that using the delay network as is (without adding memory) turns out to be advantageous, disadvantageous or immaterial, depending on the topology of the network and the problem considered i.e., (a), (b) or (c).

A generalized network alignment for three-source three-destination multiple unicast networks with delays

The concept of interference alignment when extended to three-source three-destination instantaneous multiple unicast network for the case where, each source-destination pair has a min-cut of 1 and zero-interference conditions are not satisfied, is known to achieve a rate of half for every source-destination pair under certain conditions [6]. This was called network alignment. We generalize this concept of network alignment to three-source three-destination multiple unicast (3S-3D-MU) networks with delays, without making use of memory at the intermediate nodes (i.e., nodes other than the sources and destinations) and using time varying Local Encoding Kernels (LEKs). This achieves half the rate corresponding to the individual source-destination min-cut for some classes of 3S-3D-MU network with delays which do not satisfy the zero-interference conditions.

Maximum rate of 3- and 4-real-symbol ML decodable unitary weight STBCs

It has been shown recently that the maximum rate of a 2-real-symbol (single-complex-symbol) maximum likelihood (ML) decodable, square space-time block codes (STBCs) with unitary weight matrices is 2a/2a complex symbols per channel use (cspcu) for 2a number of transmit antennas [1]. These STBCs are obtained from Unitary Weight Designs (UWDs). In this paper, we show that the maximum rates for 3- and 4-real-symbol (2-complex-symbol) ML decodable square STBCs from UWDs, for 2a transmit antennas, are 3(a-1)/2a and 4(a-1)/2a cspcu, respectively. STBCs achieving this maximum rate are constructed. A set of sufficient conditions on the signal set, required for these codes to achieve full-diversity are derived along with expressions for their coding gain.

Low ML Decoding Complexity STBCs via Codes Over the Klein Group

In this paper, we give a new framework for constructing low ML decoding complexity space-time block codes (STBCs) using codes over the Klein group K. Almost all known low ML decoding complexity STBCs can be obtained via this approach. New full- diversity STBCs with low ML decoding complexity and cubic shaping property are constructed, via codes over K, for number of transmit antennas N = 2(m), m >= 1, and rates R > 1 complex symbols per channel use. When R = N, the new STBCs are information- lossless as well. The new class of STBCs have the least knownML decoding complexity among all the codes available in the literature for a large set of (N, R) pairs.