Explicit and Optimal Exact-Regenerating Codes for the Minimum-Bandwidth Point in Distributed Storage

In the distributed storage setting that we consider, data is stored across n nodes in the network such that the data can be recovered by connecting to any subset of k nodes. Additionally, one can repair a failed node by connecting to any d nodes while downloading beta units of data from each. Dimakis et al. show that the repair bandwidth d beta can be considerably reduced if each node stores slightly more than the minimum required and characterize the tradeoff between the amount of storage per node and the repair bandwidth. In the exact regeneration variation, unlike the functional regeneration, the replacement for a failed node is required to store data identical to that in the failed node. This greatly reduces the complexity of system maintenance. The main result of this paper is an explicit construction of codes for all values of the system parameters at one of the two most important and extreme points of the tradeoff - the Minimum Bandwidth Regenerating point, which performs optimal exact regeneration of any failed node. A second result is a non-existence proof showing that with one possible exception, no other point on the tradeoff can be achieved for exact regeneration.

A Flexible Class of Regenerating Codes for Distributed Storage

In the distributed storage setting introduced by Dimakis et al., B units of data are stored across n nodes in the network in such a way that the data can be recovered by connecting to any k nodes. Additionally one can repair a failed node by connecting to any d nodes while downloading at most beta units of data from each node. In this paper, we introduce a flexible framework in which the data can be recovered by connecting to any number of nodes as long as the total amount of data downloaded is at least B. Similarly, regeneration of a failed node is possible if the new node connects to the network using links whose individual capacity is bounded above by beta(max) and whose sum capacity equals or exceeds a predetermined parameter gamma. In this flexible setting, we obtain the cut-set lower bound on the repair bandwidth along with a constructive proof for the existence of codes meeting this bound for all values of the parameters. An explicit code construction is provided which is optimal in certain parameter regimes.

Reduced ML-Decoding Complexity, Full-Rate STBCs for 4 Transmit Antenna Systems

For an n(t) transmit, n(r) receive antenna system (n(t) x nr system), a full-rate space time block code (STBC) transmits min(n(t), n(r)) complex symbols per channel use. In this paper, a scheme to obtain a full-rate STBC for 4 transmit antennas and any n(r), with reduced ML-decoding complexity is presented. The weight matrices of the proposed STBC are obtained from the unitary matrix representations of a Clifford Algebra. By puncturing the symbols of the STBC, full rate designs can be obtained for n(r) < 4. For any value of n(r), the proposed design offers the least ML-decoding complexity among known codes. The proposed design is comparable in error performance to the well known Perfect code for 4 transmit antennas while offering lower ML-decoding complexity. Further, when n(r) < 4, the proposed design has higher ergodic capacity than the punctured Perfect code. Simulation results which corroborate these claims are presented.

Training-Symbol Embedded, High-Rate Complex Orthogonal Designs for Relay Networks

Distributed Space-Time Block Codes (DSTBCs) from Complex Orthogonal Designs (CODs) (both square and non-square CODs other than the Alamouti design) are known to lose their single-symbol ML decodable (SSD) property when used in two-hop wireless relay networks using the amplify and forward protocol. For such a network, a new class of high rate, training-symbol embedded (TSE) SSD DSTBCs are proposed from TSE-CODs. The constructed codes include the training symbols within the structure of the code which is shown to be the key point to obtain high rate along with the SSD property. TSE-CODs are shown to offer full-diversity for arbitrary complex constellations. Non-square TSE-CODs are shown to provide better rates (in symbols per channel use) compared to the known SSD DSTBCs for relay networks when the number of relays is less than 10. Importantly, the proposed DSTBCs do not contain zeros in their codewords and as a result, antennas of the relay nodes do not undergo a sequence of switch on and off transitions within every codeword use. Hence, the proposed DSTBCs eliminate the antenna switching problem.

On Network-Error Correcting Convolutional Codes under the BSC Edge Error Model

Convolutional network-error correcting codes (CNECCs) are known to provide error correcting capability in acyclic instantaneous networks within the network coding paradigm under small field size conditions. In this work, we investigate the performance of CNECCs under the error model of the network where the edges are assumed to be statistically independent binary symmetric channels, each with the same probability of error pe(0 <= p(e) < 0.5). We obtain bounds on the performance of such CNECCs based on a modified generating function (the transfer function) of the CNECCs. For a given network, we derive a mathematical condition on how small p(e) should be so that only single edge network-errors need to be accounted for, thus reducing the complexity of evaluating the probability of error of any CNECC. Simulations indicate that convolutional codes are required to possess different properties to achieve good performance in low p(e) and high p(e) regimes. For the low p(e) regime, convolutional codes with good distance properties show good performance. For the high p(e) regime, convolutional codes that have a good slope ( the minimum normalized cycle weight) are seen to be good. We derive a lower bound on the slope of any rate b/c convolutional code with a certain degree.

The Shannon Cipher System With a Guessing Wiretapper: General Sources

The Shannon cipher system is studied in the context of general sources using a notion of computational secrecy introduced by Merhav and Arikan. Bounds are derived on limiting exponents of guessing moments for general sources. The bounds are shown to be tight for i.i.d., Markov, and unifilar sources, thus recovering some known results. A close relationship between error exponents and correct decoding exponents for fixed rate source compression on the one hand and exponents for guessing moments on the other hand is established.

MIMO Precoding With X- and Y- Codes

We consider a slow fading multiple-input multiple-output (MIMO) system with channel state information at both the transmitter and receiver. A well-known precoding scheme is based upon the singular value decomposition (SVD) of the channel matrix, which transforms the MIMO channel into parallel subchannels. Despite having low maximum likelihood decoding (MLD) complexity, this SVD precoding scheme provides a diversity gain which is limited by the diversity gain of the weakest subchannel. We therefore propose X- and Y-Codes, which improve the diversity gain of the SVD precoding scheme but maintain the low MLD complexity, by jointly coding information across a pair of subchannels. In particular, subchannels with high diversity gain are paired with those having low diversity gain. A pair of subchannels is jointly encoded using a 2 2 real matrix, which is fixed a priori and does not change with each channel realization. For X-Codes, these rotation matrices are parameterized by a single angle, while for Y-Codes, these matrices are left triangular matrices. Moreover, we propose X-, Y-Precoders with the same structure as X-, Y-Codes, but with encoding matrices adapted to each channel realization. We observed that X-Codes/Precoders are good for well-conditioned channels, while Y-Codes/Precoders are good for ill-conditioned channels.

A New Full-diversity Criterion and Low-complexity STBCs with Partial Interference Cancellation Decoding

Recently, Guo and Xia gave sufficient conditions for an STBC to achieve full diversity when a PIC (Partial Interference Cancellation) or a PIC-SIC (PIC with Successive Interference Cancellation) decoder is used at the receiver. In this paper, we give alternative conditions for an STBC to achieve full diversity with PIC and PIC-SIC decoders, which are equivalent to Guo and Xia's conditions, but are much easier to check. Using these conditions, we construct a new class of full diversity PIC-SIC decodable codes, which contain the Toeplitz codes and a family of codes recently proposed by Zhang, Xu et. al. as proper subclasses. With the help of the new criteria, we also show that a class of PIC-SIC decodable codes recently proposed by Zhang, Shi et. al. can be decoded with much lower complexity than what is reported, without compromising on full diversity.

Fast-Group-Decodable STBCs via Codes over GF(4)

In this paper we construct low decoding complexity STBCs by using the Pauli matrices as linear dispersion matrices. In this case the Hurwitz-Radon orthogonality condition is shown to be easily checked by transferring the problem to $\mathbb{F}_4$ domain. The problem of constructing low decoding complexity STBCs is shown to be equivalent to finding certain codes over $\mathbb{F}_4$. It is shown that almost all known low complexity STBCs can be obtained by this approach. New codes are given that have the least known decoding complexity in particular ranges of rate.

Precoding with X-codes to increase capacity with discrete input alphabets

We consider Gaussian multiple-input multiple-output (MIMO) channels with discrete input alphabets. We propose a non-diagonal precoder based on X-Codes in to increase the mutual information. The MIMO channel is transformed into a set of parallel subchannels using Singular Value Decomposition (SVD) and X-codes are then used to pair the subchannels. X-Codes are fully characterized by the pairings and the 2 × 2 real rotation matrices for each pair (parameterized with a single angle). This precoding structure enables to express the total mutual information as a sum of the mutual information of all the pairs. The problem of finding the optimal precoder with the above structure, which maximizes the total mutual information, is equivalent to i) optimizing the rotation angle and the power allocation within each pair and ii) finding the optimal pairing and power allocation among the pairs. It is shown that the mutual information achieved with the proposed pairing scheme is very close to that achieved with the optimal precoder by Cruz et al., and significantly better than mercury/waterfilling strategy by Lozano et al.. Our approach greatly simplifies both the precoder optimization and the detection complexity, making it suitable for practical applications.

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.

DMT of multi-hop cooperative networks

Some basic results that help in determining the Diversity-Multiplexing Tradeoff (DMT) of cooperative multihop networks are first identified. As examples, the maximum achievable diversity gain is shown to equal the min-cut between source and sink, whereas the maximal multiplexing gain is shown to equal the minimum rank of the matrix characterizing the MIMO channel appearing across a cut in the network. Two multi-hop generalizations of the two-hop network are then considered, namely layered networks as well as a class of networks introduced here and termed as K-parallel-path (KPP) networks. The DMT of KPP networks is characterized for K > 3. It is shown that a linear DMT between the maximum diversity dmax and the maximum multiplexing gain of 1 is achievable for fully-connected, layered networks. Explicit coding schemes achieving the DMT that make use of cyclic-division-algebra-based distributed space-time codes underlie the above results. Two key implications of the results in the paper are that the half-duplex constraint does not entail any rate loss for a large class of cooperative networks and that simple, amplify-and-forward protocols are often sufficient to attain the optimal DMT.

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.

Improved large-MIMO detection based on damped belief propagation

In this paper, we consider the application of belief propagation (BP) to achieve near-optimal signal detection in large multiple-input multiple-output (MIMO) systems at low complexities. Large-MIMO architectures based on spatial multiplexing (V-BLAST) as well as non-orthogonal space-time block codes(STBC) from cyclic division algebra (CDA) are considered. We adopt graphical models based on Markov random fields (MRF) and factor graphs (FG). In the MRF based approach, we use pairwise compatibility functions although the graphical models of MIMO systems are fully/densely connected. In the FG approach, we employ a Gaussian approximation (GA) of the multi-antenna interference, which significantly reduces the complexity while achieving very good performance for large dimensions. We show that i) both MRF and FG based BP approaches exhibit large-system behavior, where increasingly closer to optimal performance is achieved with increasing number of dimensions, and ii) damping of messages/beliefs significantly improves the bit error performance.

Precoding by Pairing Subchannels to Increase MIMO Capacity With Discrete Input Alphabets

We consider Gaussian multiple-input multiple-output (MIMO) channels with discrete input alphabets. We propose a non-diagonal precoder based on the X-Codes in 1] to increase the mutual information. The MIMO channel is transformed into a set of parallel subchannels using singular value decomposition (SVD) and X-Codes are then used to pair the subchannels. X-Codes are fully characterized by the pairings and a 2 x 2 real rotation matrix for each pair (parameterized with a single angle). This precoding structure enables us to express the total mutual information as a sum of the mutual information of all the pairs. The problem of finding the optimal precoder with the above structure, which maximizes the total mutual information, is solved by: i) optimizing the rotation angle and the power allocation within each pair and ii) finding the optimal pairing and power allocation among the pairs. It is shown that the mutual information achieved with the proposed pairing scheme is very close to that achieved with the optimal precoder by Cruz et al., and is significantly better than Mercury/waterfilling strategy by Lozano et al. Our approach greatly simplifies both the precoder optimization and the detection complexity, making it suitable for practical applications.