Explicit codes minimizing repair bandwidth for distributed storage

We consider the problem of minimizing the bandwidth required to repair a failed node when data is stored across n nodes in a distributed manner, so as to facilitate reconstruction of the entire data by connecting to any k out of the n nodes. We provide explicit and optimal constructions which permit exact replication of a failed systematic node.

Single real-symbol decodable, high-rate, distributed space-time block codes

A scheme to apply the rate-1 real orthogonal designs (RODs) in relay networks with single real-symbol decodability of the symbols at the destination for any arbitrary number of relays is proposed. In the case where the relays do not have any information about the channel gains from the source to themselves, the best known distributed space time block codes (DSTBCs) for k relays with single real-symbol decodability offer an overall rate of complex symbols per channel use. The scheme proposed in this paper offers an overall rate of 2/2+k complex symbol per channel use, which is independent of the number of relays. Furthermore, in the scenario where the relays have partial channel information in the form of channel phase knowledge, the best known DSTBCs with single real-symbol decodability offer an overall rate of 1/3 complex symbols per channel use. In this paper, making use of RODs, a scheme which achieves the same overall rate of 1/3 complex symbols per channel use but with a decoding delay that is 50 percent of that of the best known DSTBCs, is presented. Simulation results of the symbol error rate performance for 10 relays, which show the superiority of the proposed scheme over the best known DSTBC for 10 relays with single real-symbol decodability, are provided.

Explicit Codes Uniformly Reducing Repair Bandwidth in Distributed Storage

A distributed storage setting is considered where a file of size B is to be stored across n storage nodes. A data collector should be able to reconstruct the entire data by downloading the symbols stored in any k nodes. When a node fails, it is replaced by a new node by downloading data from some of the existing nodes. The amount of download is termed as repair bandwidth. One way to implement such a system is to store one fragment of an (n, k) MDS code in each node, in which case the repair bandwidth is B. Since repair of a failed node consumes network bandwidth, codes reducing repair bandwidth are of great interest. Most of the recent work in this area focuses on reducing the repair bandwidth of a set of k nodes which store the data in uncoded form, while the reduction in the repair bandwidth of the remaining nodes is only marginal. In this paper, we present an explicit code which reduces the repair bandwidth for all the nodes to approximately B/2. To the best of our knowledge, this is the first explicit code which reduces the repair bandwidth of all the nodes for all feasible values of the system parameters.

Explicit and Optimal Codes for Distributed Storage

In the distributed storage coding problem we consider, data is stored across n nodes in a network, each capable of storing � symbols. It is required that the complete data can be reconstructed by downloading data from any k nodes. There is also the key additional requirement that a failed node be regenerated by connecting to any d nodes and downloading �symbols from each of them. Our goal is to minimize the repair bandwidth d�. In this paper we provide explicit constructions for several parameter sets of interest.

On the Successive Refinability of MIMO channels: DMT and codes

Diversity embedded space time codes are high rate codes that are designed such that they have a high diversity code embedded within them. A recent work by Diggavi and Tse characterizes the performance limits that can be achieved by diversity embedded space-time codes in terms of the achievable Diversity Multiplexing Tradeoff (DMT). In particular, they have shown that the trade off is successively refinable for rayleigh fading channels with one degree of freedom using superposition coding and Successive Interference Cancellation (SIC). However, for Multiple-Input Multiple-Output (MIMO) channels, the questions of successive refinability remains open. We consider MIMO Channels under superposition coding and SIC. We derive an upper bound on the successive refinement characteristics of the DMT. We then construct explicit space time codes that achieve the derived upper bound. These codes, constructed from cyclic division algebras, have minimal delay. Our results establish that when the channel has more than one degree of freedom, the DMT is not successive refinable using superposition coding and SIC. The channels considered in this work can have arbitrary fading statistics.

Performance analysis of wavelength/time codes with and without hard-limiter

Fiber-optic CDMA technology is well suited for high speed local-area-networks (LANs) as it has good salient features. In this paper, we model the wavelength/time multiple-pulses-per-row (W/T MPR) FO-CDMA network channel, as a Z channel. We compare the performances of W/T MPR code with and without hard-limiter and show that significant performance improvement can be achieved by using hard-limiters in the receivers. In broadcast channels, MAI is the dominant source of noise. Hence the performance analysis is carried out considering only MAI and other receiver noises are neglected.

D-MG Tradeoff and Optimal Codes for a Class of AF and DF Cooperative Communication Protocols

Cooperative relay communication in a fading channel environment under the orthogonal amplify-and-forward (OAF), non-orthogonal and orthogonal selection decode-and-forward (NSDF and OSDF) protocols is considered here. The diversity-multiplexing gain tradeoff (DMT) of the three protocols is determined and DMT-optimal distributed space-time code constructions are provided. The codes constructed are sphere decodable and in some instances incur minimum possible delay. Included in our results is the perhaps surprising finding that the OAF and NAF protocols have identical DMT when the time durations of the broadcast and cooperative phases are optimally chosen to suit the respective protocol. Two variants of the NSDF protocol are considered: fixed-NSDF and variable-NSDF protocol. In the variable-NSDF protocol, the fraction of time occupied by the broadcast phase is allowed to vary with multiplexing gain. In the two-relay case, the variable-NSDF protocol is shown to improve on the DMT of the best previously-known static protocol for higher values of multiplexing gain. Our results also establish that the fixed-NSDF protocol has a better DMT than the NAF protocol for any number of relays.

On four-group ML decodable distributed space time codes for cooperative communication

A construction of a new family of distributed space time codes (DSTCs) having full diversity and low Maximum Likelihood (ML) decoding complexity is provided for the two phase based cooperative diversity protocols of Jing-Hassibi and the recently proposed Generalized Non-orthogonal Amplify and Forward (GNAF) protocol of Rajan et al. The salient feature of the proposed DSTCs is that they satisfy the extra constraints imposed by the protocols and are also four-group ML decodable which leads to significant reduction in ML decoding complexity compared to all existing DSTC constructions. Moreover these codes have uniform distribution of power among the relays as well as in time. Also, simulations results indicate that these codes perform better in comparison with the only known DSTC with the same rate and decoding complexity, namely the Coordinate Interleaved Orthogonal Design (CIOD). Furthermore, they perform very close to DSTCs from field extensions which have same rate but higher decoding complexity.

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.

Combinatorial Representations of Block Codes

We look at graphical descriptions of block codes known as trellises, which illustrate connections between algebra and graph theory, and can be used to develop powerful decoding algorithms. Trellis sizes for linear block codes are known to grow exponentially with the code parameters. Of considerable interest to coding theorists therefore, are more compact descriptions called tail-biting trellises which in some cases can be much smaller than any conventional trellis for the same code . We derive some interesting properties of tail-biting trellises and present a new decoding algorithm.

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.