BiD codes, which are a new family of algebraic codes of length $3^m$, achieve the erasure channel capacity under bit-MAP decoding and offer asymptotically larger minimum distance than Reed-Muller (RM) codes. In this paper we propose fast maximum-likelihood (ML) and max-log-MAP decoders for first-order BiD codes. For second-order codes, we identify their minimum-weight parity checks and ascertain a code property known as 'projection' in the RM coding literature. We use these results to design a belief propagation decoder that performs within 1 dB of ML decoder for block lengths 81 and 243.

We use a simple construction called ‘recursive subproducts’ (that is known to yield good codes of lengths$n^{m}, n \geq 3)$to identify a family of codes sandwiched between first-order and second-order Reed-Muller (RM) codes. These codes are subcodes of multidimensional product codes that use first-order RM codes as components. We identify the minimum weight codewords of all the codes in this family, and numerically determine the weight distribution of some of them. While these codes have the same minimum distance and a smaller rate than second-order RM codes, they have significantly fewer minimum weight codewords. Further, these codes can be decoded via modifications to known RM decoders which yield codeword error rates within 0.25 dB of second-order RM codes and better than CRC-aided Polar codes (in terms of$E_{b} / N_{o}$for lengths$256,512,1024$), thereby offering rate adaptation options for RM codes in low-capacity scenarios.

We introduce Berman-intersection-dual Berman (BiD) codes. These are abelian codes of length 3mthat can be constructed using Kronecker products of a 3×3 kernel matrix. BiD codes offer minimum distance close to that of Reed-Muller (RM) codes at practical blocklengths, and larger distance than RM codes asymptotically in the blocklength. Simulations of BiD codes of length 35= 243 in the erasure and Gaussian channels show that their block error rates under maximum-likelihood decoding are similar to, and sometimes better, than RM, RM-Polar, and CRC-aided Polar codes.

We study a family of subcodes of the$m-\mathbf{dimensional}$product code$\mathcal{C}^{\otimes m}$(‘subproduct codes’) that have a recursive Plotkin-like structure, and which include Reed-Muller (RM) codes and Dual Berman codes as special cases. We denote the codes in this family as$\mathcal{C}^{\otimes[r,m]}$, where$r\in\{0,1,\ \ldots,\ m\}$is the ‘order’ of the code. These codes allow a ‘projection’ operation that can be exploited in iterative decoding, viz., the sum of two carefully chosen subvectors of any codeword in$\mathcal{C}^{\otimes[r,m]}$belongs to$\mathcal{C}^{\otimes[r-1,m-1]}$. Recursive subproduct codes provide a wider range of rates and block lengths compared to RM codes while possessing several of their structural properties, such as the Plotkin-like design, the projection property, and fast ML decoding of first-order codes. Our simulation results for first-order and second-order codes, that are based on a belief propagation decoder and a local graph search algorithm, show instances of subproduct codes that perform either better than or within 0.5 dB of comparable RM codes and CRC-aided Polar codes.

We identify a family of binary codes whose structure is similar to Reed-Muller (RM) codes and which include RM codes as a strict subclass. The codes in this family are denoted as$\mathscr {C}_{n}(r,m)$, and their duals are denoted as$\mathscr {B}_{n}(r,m)$. The length of these codes is$n^{m}$, where$n \geq 2$, and$r$is their ‘order’. When$n=2$,$\mathscr {C}_{n}(r,m)$is the RM code of order$r$and length$2^{m}$. The special case of these codes corresponding to$n$being an odd prime was studied by Berman (1967) and Blackmore and Norton (2001). Following the terminology introduced by Blackmore and Norton, we refer to$\mathscr {B}_{n}(r,m)$as the Berman code and$\mathscr {C}_{n}(r,m)$as the dual Berman code. We identify these codes using a recursive Plotkin-like construction, and we show that these codes have a rich automorphism group, they are generated by the minimum weight codewords, and that they can be decoded up to half the minimum distance efficiently. Using a result of Kumar et al. (2016), we show that these codes achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding. Furthermore, except double transitivity, they satisfy all the code properties used by Reeves and Pfister to show that RM codes achieve the capacity of binary-input memoryless symmetric channels. Finally, when$n$is odd, we identify a large class of abelian codes that includes$\mathscr {B}_{n}(r,m)$and$\mathscr {C}_{n}(r,m)$and which achieves BEC capacity.

We identify a family of binary codes whose structure is similar to Reed-Muller (RM) codes and which include RM codes as a strict subclass. The codes in this family are denoted as ${\mathcal{C}_n}(r,m)$, and their duals are denoted as ${{\mathcal{B}}_n}(r,m)$. The length of these codes is nm, where n ≥ 2, and r is their ‘order’. When n = 2, ${\mathcal{C}_n}(r,m)$ is the RM code of order r and length 2m. The special case of these codes corresponding to n being an odd prime was studied by Berman (1967) and Blackmore and Norton (2001). Following the terminology introduced by Blackmore and Norton, we refer to ${{\mathcal{B}}_n}(r,m)$ as the Berman code and ${\mathcal{C}_n}(r,m)$ as the dual Berman code. We identify these codes using a recursive Plotkin-like construction, and we show that these codes have a rich automorphism group. Applying a result of Kumar et al. (2016) to this set of automorphisms, we show that these codes achieve the capacity of the binary erasure channel (BEC) under bit-MAP decoding.

A class of network codes have been proposed in the literature where the symbols transmitted on network edges are binary vectors and the coding operation performed in network nodes consists of the application of (possibly several) permutations on each incoming vector and XOR-ing the results to obtain the outgoing vector. These network codes, which we will refer to as permute-and-add network codes, involve simpler operations and are known to provide lower complexity solutions than scalar linear codes. The complexity of these codes is determined by their degree which is the number of permutations applied on each incoming vector to compute an outgoing vector. Constructions of permute-and-add network codes for multicast networks are known. In this paper, we provide a new framework based on group algebras to design permute-and-add network codes for arbitrary (not necessarily multicast) networks. Our framework allows the use of any finite group of permutations (including circular shifts, proposed in prior work) and admits a trade-off between coding rate and the degree of the code. Further, our technique permits elegant recovery and generalizations of the key results on permute-and-add network codes known in the literature.

Distributed databases often suffer unequal distribution of data among storage nodes, which is known as `data skew'. Data skew arises from a number of causes such as removal of existing storage nodes and addition of new empty nodes to the database. Data skew leads to performance degradations and thus necessitates `rebalancing' at regular intervals to reduce the amount of skew. We define an r-balanced distributed database as a distributed database in which the storage across the nodes has uniform size, and each bit of the data is replicated in r distinct storage nodes. We consider the problem of designing such balanced databases along with associated rebalancing schemes which maintain the r-balanced property under node removal and addition operations. We present a class of r-balanced databases (parameterized by the number of storage nodes) which have the property of structural invariance, i.e., the databases designed for different number of storage nodes have the same structure. For this class of r-balanced databases, we present rebalancing schemes which use coded transmissions between storage nodes, and characterize their communication loads under node addition and removal. We show that the communication cost incurred to rebalance our distributed database for node addition and removal is optimal, i.e., it achieves the minimum possible cost among all possible balanced distributed databases and rebalancing schemes.

We consider the centralized coded caching system where a library of files is available at the server and their subfiles are cached at the clients as prescribed by a placement delivery array (PDA). We are interested in the problem where a specific file in the library is replaced with a new file at the server, the contents of which are correlated with the file being replaced, and this replacement needs to be communicated to the caches. The server loses the original file when the replacement is done and is unaware of the differences between the two files, whereas each cache has access to specific subfiles of the original file as dictated by the PDA. We model the correlation between the two files by assuming that they differ in at the most subfiles, and aim to reduce the number of bits broadcast by the server to update the caches. We design a new elegant coded transmission strategy for the server to update the caches blindly, and also identify another simple scheme that is based on MDS codes. We then derive converse bounds on the minimum cost ℓ*among all linear strategies. For two well-known families of PDAs – the Maddah-Ali-Niesen scheme and a scheme by Tang & Ramamoorthy and Yan et al. – we show that our new scheme has cost ℓ*(1 + o(1)) when the updates are sufficiently sparse, while the scheme using MDS codes has order-optimal cost when the updates are dense.

The problem of data exchange between multiple nodes with (not necessarily uniform) storage and communication capabilities models several current multi-user communication problems like Coded Caching, Data shuffling, Coded Computing, etc. The goal in such problems is to design communication schemes which accomplish the desired data exchange between the nodes with the optimal (minimum) amount of communication load. In this work, we present a converse to such a general data exchange problem between multiple nodes. The expression of the converse depends only on the number of bits to be moved between different subsets of nodes, and does not assume anything further specific about the parameters in the problem. Specific problem formulations, such as those in Coded Caching, Coded Data Shuffling, Coded Distributed Computing, and some of their variants, naturally can be seen as instances of this generic data exchange problem. Applying our generic converse to such problems, we recover known important converses for these settings and some of their variants in a simpler way. Further, for a generic coded caching problem with multiple transmitters, receivers and cache sizes, we show a new general converse which subsumes many existing results. We also employ our bound to obtain a new tight converse bound for the multi-node removal case in the Coded Data Rebalancing problem, in which nodes must exchange information to ‘rebalance’ a storage cluster after some node failures occur.Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1].

An index code for broadcast channel with receiver side information is locally decodable if each receiver can decode its demand by observing only a subset of the transmitted codeword symbols instead of the entire codeword. Local decodability in index coding is known to reduce receiver complexity, improve user privacy and decrease decoding error probability in wireless fading channels. Conventional index coding solutions assume that the receivers observe the entire codeword, and as a result, for these codes the number of codeword symbols queried by a user per decoded message symbol, which we refer to as locality, could be large. In this paper, we pose the index coding problem as that of minimizing the broadcast rate for a given value of locality (or vice versa) and designing codes that achieve the optimal trade-off between locality and rate. We identify the optimal broadcast rate corresponding to the minimum possible value of locality for all single unicast problems. We present new structural properties of index codes which allow us to characterize the optimal trade-off achieved by: vector linear codes when the side information graph is a directed cycle; and scalar linear codes when the minrank of the side information graph is one less than the order of the problem. We also identify the optimal trade-off among all codes, including non-linear codes, when the side information graph is a directed 3-cycle. Finally, we present techniques to design locally decodable index codes for arbitrary single unicast problems and arbitrary values of locality.

An index code is said to be locally decodable if each receiver can decode its demand using its side information and by querying only a subset of the transmitted codeword symbols instead of observing the entire codeword. Local decodability can be a beneficial feature in some communication scenarios, such as when the receivers can afford to listen to only a part of the transmissions because of limited availability of power. The locality of an index code is the ratio of the maximum number of codeword symbols queried by a receiver to the message length. In this paper we analyze the optimum locality of linear codes for the family of index coding problems whose min-rank is one less than the number of receivers in the network. We first derive the optimal trade-off between the index coding rate and locality with vector linear coding when the side information graph is a directed cycle. We then provide the optimal trade-off achieved by scalar linear coding for a larger family of problems, viz. problems where the min-rank is only one less than the number of receivers. While the arguments used for achievability are based on known coding techniques, the converse arguments rely on new results on the structure of locally decodable index codes.

We consider a point-to-point communication scenario where the receiver intends to maintain a specific linear function of a message vector while the transmitter has access to an updated version of the message. The transmitter is required to broadcast a coded version of the updated message while the receiver must use this codeword and the current value of the linear function to update its contents. Under the assumption that the update is sparse and the transmitter does not know the exact value of the update vector, the objective is to design a linear code, with as small a codelength as possible, that allows successful update of the linear function at the receiver. This problem is motivated by applications to distributed data storage systems. A field-size independent lower bound on the codelength and a coding scheme meeting this bound were given by Prakash and Médard recently. However, this scheme requires a field size that grows quickly with the system parameters. In this paper, we provide a field-size aware analysis of the function update problem, including a tighter lower bound on the codelength, and design codes that allow us to trade-off the codelength for smaller field size requirements. Whenever the achieved codelengths equal those reported by Prakash and Médard the requirements on the size of the finite field are matched as well. Further, we identify the family of function update problems where linear coding provides reduction in codelength compared to a naive transmission scheme, and we also show that every function update problem is equivalent to a generalized index coding or functional index coding problem.

Multicasting K independent messages via multipleinput multiple-output channels to multiple users where each user already has a subset of messages as side information is studied. A general framework of constructing layered space-time index coding (LSTIC) from a large class of space-time block codes (STBC), including perfect STBC, is proposed. We analyze the proposed LSTIC and show that it provides minimum determinant gains that are exponential with the amount of information contained in the side information for any possible side information. When constructed over a perfect STBC, the proposed LSTIC is itself a perfect STBC and hence many desired properties are preserved. To illustrate, we construct LSTIC over the following wellknown STBCs: Golden code; 3×3, 4×4, and 6×6 perfect STBCs; and Alamouti code. Simulation results show that the obtained side information gain can be well predicted by our analysis.

We consider the problem of communicating over noise free broadcast channels where each receiver possesses an erroneous version of the message symbols that it demands from the transmitter as side information, and the number of errors in this side information is upper bounded by a constant. This communication problem, which we refer to as broadcasting with noisy side information (BNSI), has applications in the retransmission phase of downlink networks, and to the best of our knowledge, has no known coding schemes available in the literature. In a BNSI network the transmitter can exploit the noisy side information at the receivers to reduce the number of uses of the broadcast channel. In this paper, using a known code design criterion, we analyze and construct linear coding schemes for BNSI networks. Using a representation of BNSI problems in terms of undirected bipartite graphs, we first derive lower bounds on the optimal codelength of linear codes for these problems. We then utilize the parity-check matrices of appropriately chosen linear error correcting codes to construct valid encoder matrices for BNSI problems. We further optimize this technique by partitioning a BNSI problem into multiple subproblems and applying independent linear encoders for each of these subproblems. Finally, we show that BNSI problems form a strict subset of index coding problems by proving that any given linear BNSI problem is equivalent to a scalar linear index coding problem, albeit with a considerably larger number of receivers than the given BNSI problem.

Multicasting K independent messages via multiple-input multiple-output (MIMO) channels to multiple users where each user already has a subset of messages as side information is studied. A general framework of constructing layered spacetime index coding (LSTIC) from a large class of space-time block codes (STBCs), including perfect STBCs, is proposed. We analyze the proposed LSTIC technique and show that it provides minimum determinant gains that are exponential in the amount of information contained in the side information for any possible side information at the receivers. When constructed over a perfect STBC, the proposed LSTIC is itself a perfect STBC and hence enjoys many desired properties.

Index coding for broadcast channels allows each receiver or client to retrieve its demanded message from its side information and the transmitted codeword. In general, a client may have to observe the entire codeword to decode its demanded message. However, downloading or querying the codeword symbols might involve costs at a client - such as network utilization costs and storage. Traditional index coding does not consider this client perspective, and as a result, for these codes the number of codeword symbols queried by a client per decoded message symbol, which we refer to as locality, could be large. In this paper we study a `client aware' approach to index coding by viewing the problem as a trade-off between the achievable broadcast rate and locality, where the objective is to minimize the rate for a given value of locality and vice versa. We first consider the minimum possible locality 1 and show that the coding scheme based on fractional coloring of the interference graph is optimal for this locality. We then propose index coding schemes with small locality by covering the side information graph using acyclic subgraphs and subgraphs of small minrank. We also show how locality can be accounted for in conventional partition multicast and cycle covering solutions to index coding, thereby yielding locally decodable index codes.

Lattices possess elegant mathematical properties which have been previously used in the literature to show that structured codes can be efficient in a variety of communication scenarios, including coding for the additive white Gaussian noise channel, dirty-paper channel, Wyner-Ziv coding, coding for relay networks, and so forth. We consider the family of single-transmitter multiple-receiver Gaussian channels, where the source transmits a set of common messages to all the receivers (multicast scenario), and each receiver has coded side information, i.e., prior information in the form of linear combinations of the messages. This channel model is motivated by applications to multi-terminal networks, where the nodes may have access to coded versions of the messages from previous signal hops or through orthogonal channels. The capacity of this channel is known and follows from the work of Tuncel (2006), which is based on random coding arguments. In this paper, following the approach of Erez and Zamir, we design lattice codes for this family of channels when the source messages are symbols from a finite field Fpof prime size. Our coding scheme utilizes Construction A lattices designed over the same prime field Fp, and uses algebraic binning at the decoders to expurgate the channel code and obtain good lattice subcodes, for every possible set of linear combinations available as side information. The achievable rate of our coding scheme is a function of the size p of underlying prime field, and approaches the capacity as p tends to infinity.

Lattices possess elegant mathematical properties which have been previously used in the literature to show that structured codes can be efficient in a variety of communication scenarios. We consider the family of single-transmitter multiple-receiver Gaussian channels where the source transmits a set of common messages to all the receivers (multicast scenario), and each receiver has coded side information, i.e., prior information in the form of linear combinations of the messages. This channel model is motivated by applications to multi-terminal networks where the nodes may have access to coded versions of the messages from previous signal hops or through orthogonal channels. The capacity of this channel is known and follows from the work of Tuncel (2006), which is based on random coding arguments. In this paper, following the approach introduced by Erez and Zamir, we show that lattice codes are capacity-optimal for this family of channels. The structured coding scheme proposed in this paper is derived from Construction A lattices designed over prime fields, and utilizes algebraic binning at the decoders to expurgate the channel code and obtain good lattice subcodes, for every possible set of linear combinations available as side information.

We construct error correcting codes for jointly transmitting a finite set of independent messages to an informed receiver which has prior knowledge of the values of some subset of the messages as side information. The transmitter is oblivious to the message subset already known to the receiver and performs encoding in such a way that any possible side information can be used efficiently at the decoder. We construct and identify several families of algebraic error correcting codes for this problem using cyclic and maximum distance separable (MDS) codes. The proposed codes are of short block length, many of them provide optimum or near-optimum error correction capabilities and guarantee larger minimum distances than known codes of similar parameters for informed receivers. The constructed codes are also useful as error correcting codes for index coding when the transmitter does not know the side information available at the receivers.

We consider the special case of index coding over the Gaussian broadcast channel where each receiver has prior knowledge of a subset of messages at the transmitter and demands all the messages from the source. We propose a concatenated coding scheme for this problem, using an index code for the Gaussian channel as an inner code/modulation to exploit side information at the receivers, and an outer code to attain coding gain against the channel noise. We derive the capacity region of this scheme by viewing the resulting channel as a multiple-access channel with many receivers, and relate it to the side information gain - which is a measure of the advantage of a code in utilizing receiver side information - of the inner index code/modulation. We demonstrate the utility of the proposed architecture by simulating the performance of an index code/modulation concatenated with an off-the-shelf convolutional code through bit-interleaved coded-modulation.

The index coding problem involves a sender with K messages to be transmitted across a broadcast channel, and a set of receivers each of which demands a subset of the K messages while having prior knowledge of a different subset as side information. We consider the specific instance of noisy index coding where the broadcast channel is Gaussian and every receiver demands all the messages from the source. We construct lattice index codes for this channel by encoding the K messages individually using K modulo lattice constellations and transmitting their sum modulo a shaping lattice. We introduce a design metric called side information gain that measures the advantage of a code in utilizing the side information at the receivers, and hence its quality as an index code. Based on the Chinese remainder theorem, we then construct lattice index codes for the Gaussian broadcast channel. Among all lattice index codes constructed using any densest lattice of a given dimension, our codes achieve the maximum side information gain.

The index coding problem involves a sender with K messages to be transmitted across a broadcast channel, and a set of receivers each of which demands a subset of the K messages while having a prior knowledge of a different subset as side information. We consider the specific case of noisy index coding where the broadcast channel is Gaussian and every receiver demands all the messages from the source. Instances of this communication problem arise in wireless relay networks, sensor networks, and retransmissions in broadcast channels. We construct lattice index codes for this channel by encoding the K messages individually using K modulo lattice constellations and transmitting their sum modulo a coarse lattice. We introduce a design metric called side information gain that measures the advantage of a code in utilizing the side information at the receivers, and hence, its goodness as an index code. Based on the Chinese remainder theorem, we then construct lattice index codes with large side information gains using lattices over the following principal ideal domains: 1) rational integers; 2) Gaussian integers; 3) Eisenstein integers; and 4) Hurwitz quaternions. Among all lattice index codes constructed using any densest lattice of a given dimension, our codes achieve the maximum side information gain. Finally, using an example, we illustrate how the proposed lattice index codes can benefit Gaussian broadcast channels with more general message demands.

In this paper a MIMO quasi static block fading channel with finite N-ary delay-free, noise-free feedback is considered. The transmitter uses a set of N Space-Time Block Codes (STBCs), one corresponding to each of the N possible feedback values, to encode and transmit information. The feedback function used at the receiver and the N component STBCs used at the transmitter together constitute a Finite Feedback Scheme (FFS). If each of the component codes encodes K independent complex symbols and is of transmission duration T, the rate of the FFS is K/T complex symbols per channel use. Although a number of FFSs are available in the literature that provably achieve full-diversity, there is no known universal criterion to determine whether a given arbitrary FFS achieves full-diversity or not. Further, all known full-diversity FFSs for Ttwhere Ntis the number of transmit antennas, have rate at the most 1. In this paper a universal necessary condition for any FFS to achieve full-diversity is given, using which the notion of Feedback-Transmission duration optimal (FT-optimal) FFSs-schemes that use minimum amount of feedback N given the transmission duration T, and minimum transmission duration given the amount of feedback to achieve full-diversity-is introduced. When there is no feedback (N = 1) an FT-optimal scheme consists of a single STBC with T = Nt, and the proposed necessary condition reduces to the well known necessary and sufficient condition for an STBC to achieve full-diversity, viz. every non-zero codeword difference matrix of the STBC must be of rank Nt. Also, a sufficient condition for full-diversity is given for those FFSs in which the component STBC yielding the largest minimum Euclidean distance is chosen. Using this sufficient condition, full-rate (rate Nt) full-diversity FT-optimal schemes are constructed for all (Nt, T, N) with NT = Nt. These are the first full-rate full-diversity FFSs reported in the literature for Tt. Simulation results show that the new schemes have the best error performance among all known FFSs.

The problem of designing good space-time block codes (STBCs) with low maximum-likelihood (ML) decoding complexity has gathered much attention in the literature. All the known low ML decoding complexity techniques utilize the same approach of exploiting either the multigroup decodable or the fast-decodable (conditionally multigroup decodable) structure of a code. We refer to this well-known technique of decoding STBCs as conditional ML (CML) decoding . In this paper, we introduce a new framework to construct ML decoders for STBCs based on the generalized distributive law (GDL) and the factor-graph-based sum-product algorithm. We say that an STBC is fast GDL decodable if the order of GDL decoding complexity of the code, with respect to the constellation sizeM, is strictly less thanMλ, where λ is the number of independent symbols in the STBC. We give sufficient conditions for an STBC to admit fast GDL decoding, and show that both multigroup and conditionally multigroup decodable codes are fast GDL decodable. For any STBC, whether fast GDL decodable or not, we show that the GDL decoding complexity is strictly less than the CML decoding complexity. For instance, for any STBC obtained from cyclic division algebras which is not multigroup or conditionally multigroup decodable, the GDL decoder provides about 12 times reduction in complexity compared to the CML decoder. Similarly, for the Golden code, which is conditionally multigroup decodable, the GDL decoder is only half as complex as the CML decoder.

A space-time block code (STBC) is said to be multigroup decodable if the information symbols encoded by it can be partitioned into two or more groups such that each group of symbols can be maximum-likelihood (ML) decoded independently of the other symbol groups. In this paper, we show that the upper triangular matrix R encountered during the sphere decoding of a linear dispersion STBC can be rank-deficient even when the rate of the code is less than the minimum of the number of transmit and receive antennas. We then show that all known families of high-rate (rate greater than 1) multigroup decodable codes have rank-deficient R matrix even when the rate is less than the number of transmit and receive antennas, and this rank-deficiency problem arises only in asymmetric MIMO systems when the number of receive antennas is strictly less than the number of transmit antennas. Unlike the codes with full-rank R matrix, the complexity of the sphere decoding-based ML decoder for STBCs with rank-deficient R matrix is polynomial in the constellation size, and hence is high. We derive the ML sphere decoding complexity of most of the known high-rate multigroup decodable codes, and show that for each code, the complexity is a decreasing function of the number of receive antennas.

A Finite Feedback Scheme (FFS) for a quasi-static MIMO block fading channel with finite N-ary delay-free noise-free feedback consists of N Space-Time Block Codes (STBCs) at the transmitter, one corresponding to each possible value of feedback, and a function at the receiver that generates N-ary feedback. A number of FFSs are available in the literature that provably attain full-diversity. However, there is no known full-diversity criterion that universally applies to all FFSs. In this paper a universal necessary condition for any FFS to achieve full-diversity is given, and based on this criterion the notion of Feedback-Transmission duration optimal (FT-optimal) FFSs is introduced, which are schemes that use minimum amount of feedback N for the given transmission duration T, and minimum T for the given N to achieve full-diversity. When there is no feedback (N = 1) an FT-optimal scheme consists of a single STBC, and the proposed condition reduces to the well known necessary and sufficient condition for an STBC to achieve fulldiversity. Also, a sufficient criterion for full-diversity is given for FFSs in which the component STBC yielding the largest minimum Euclidean distance is chosen, using which full-rate (Ntcomplex symbols per channel use) full-diversity FT-optimal schemes are constructed for all Nt> 1. These are the first full-rate full-diversity FFSs reported in the literature for Tt. Simulation results show that the new schemes have the best error performance among all known FFSs.

For a family of Space-Time Block Codes (STBCs) C1, C2, ... , with increasing number of transmit antennas Ni, with rates Ri complex symbols per channel use, i = 1, 2, ... , we introduce the notion of asymptotic normalized rate which we define as limi→∞Ri/Ni, and we say that a family of STBCs is Ri asymptotically-good if its asymptotic normalized rate is non-zero, i.e., when the rate scales as a non-zero fraction of the number of transmit antennas. An STBC C is said to be g-group decodable, g ≥ 2, if the information symbols encoded by it can be partitioned into g groups, such that each group of symbols can be ML decoded independently of the others. In this paper we construct full-diversity g-group decodable codes with rates greater than one complex symbol per channel use for all g ≥ 2. Specifically, we construct delay-optimal, g-group decodable codes for number of transmit antennas Ntthat are a multiple of g2[g-1/2]with rate Nt/g2g-1+ g2-g/2Nt. Using these new codes as building blocks, we then construct non-delay-optimal g-group decodable codes with rate roughly g times that of the delay-optimal codes, for number of antennas Ntthat are a multiple of 2[g-1/2], with delay gNtand rate Nt/2g-1+g-1/2NtFor each g ≥ 2, the new delay-optimal and nondelay-optimal families of STBCs are both asymptotically-good, with the latter family having the largest asymptotic normalized rates among all known families of multigroup decodable codes with delay T ≤ gNt. Also, for g ≥ 3, these are the first instances of g-group decodable codes with rates greater than 1 reported in the literature.

The problem of designing good Space-Time Block Codes (STBCs) with low maximum-likelihood (ML) decoding complexity has gathered much attention in the literature. All the known low ML decoding complexity techniques utilize the same approach of exploiting either the multigroup decodable or the fast-decodable (conditionally multigroup decodable) structure of a code. We refer to this well known technique of decoding STBCs as Conditional ML (CML) decoding. In [1], we introduced a framework to construct ML decoders for STBCs based on the Generalized Distributive Law (GDL) and the Factor-graph based Sum-Product Algorithm, and showed that for two specific families of STBCs, the Toepltiz codes and the Overlapped Alamouti Codes (OACs), the GDL based ML decoders have strictly less complexity than the CML decoders. In this paper, we introduce a `traceback' step to the GDL decoding algorithm of STBCs, which enables roughly 4 times reduction in the complexity of the GDL decoders proposed in [1]. Utilizing this complexity reduction from `traceback', we then show that for any STBC (not just the Toeplitz and Overlapped Alamouti Codes), the GDL decoding complexity is strictly less than the CML decoding complexity. For instance, for any STBC obtained from Cyclic Division Algebras that is not multigroup or conditionally multigroup decodable, the GDL decoder provides approximately 12 times reduction in complexity compared to the CML decoder. Similarly, for the Golden code, which is conditionally multigroup decodable, the GDL decoder is only about half as complex as the CML decoder.

A Space-Time Block Code (STBC) is said to be multigroup ML decodable if the information symbols encoded by it can be partitioned into two or more groups, such that each group of symbols can be ML decoded independently of the other symbol groups. In this paper, we show that the upper triangular matrix R encountered during the sphere decoding of a linear dispersion STBC can be rank-deficient even when the rate of the code is less than the minimum of the number of transmit and receive antennas. We then show that all known families of high rate (rate greater than 1) multigroup ML decodable codes have rank-deficient R matrix, even when the rate is less than the number of transmit and receive antennas, and this rank-deficiency problem arises only when the number of receive antennas is strictly less than the number of transmit antennas. Unlike the codes with full-rank R matrix, the average sphere decoding complexity of the STBCs whose R matrix is rank-deficient is polynomial in the constellation size, and hence is high. We derive the sphere decoding complexity of most of the known high rate multigroup ML decodable codes, and show that for each code, the complexity is a decreasing function of the number of receive antennas.

For a family/sequence of Space-Time Block Codes (STBCs) C1, C2,⋯, with increasing number of transmit antennas Ni, with rates Ricomplex symbols per channel use (cspcu), i = 1,2,⋯, the asymptotic normalized rate is defined as limi→∞Ri/Ni. A family of STBCs is said to be asymptotically-good if the asymptotic normalized rate is non-zero, i.e., when the rate scales as a non-zero fraction of the number of transmit antennas, and the family of STBCs is said to be asymptotically-optimal if the asymptotic normalized rate is 1, which is the maximum possible value. In this paper, we construct a new class of full-diversity STBCs that have the least maximum-likelihood (ML) decoding complexity among all known codes for any number of transmit antennas N>;1 and rates R>;1 cspcu. For a large set of (R,N) pairs, the new codes have lower ML decoding complexity than the codes already available in the literature. Among the new codes, the class of full-rate codes (R=N) are asymptotically-optimal and fast-decodable, and for N>;5 have lower ML decoding complexity than all other families of asymptotically-optimal, fast-decodable, full-diversity STBCs available in the literature. The construction of the new STBCs is facilitated by the following further contributions of this paper: (i) Construction of a new class of asymptotically-good, full-diversity multigroup ML decodable codes, that not only includes STBCs for a larger set of antennas, but also either matches in rate or contains as a proper subset all other high-rate or asymptotically-good, delay-optimal, multigroup ML decodable codes available in the literature. (ii) Construction of a new class of fast-group-decodable codes (codes that combine the low ML decoding complexity properties of multigroup ML decodable codes and fast-decodable codes) for all even number of transmit antennas and rates 1 <; R ≤ 5/4. (iii) Given a design with full-rank linear dispersion matrices, we show that a full-diversity STBC can be constructed from this design by encoding the real symbols independently using only regular PAM constellations.

Recently in, a framework was given to construct low ML decoding complexity Space-Time Block Codes (STBCs) via codes over the finite field F4. In this paper, we construct new full-diversity STBCs with cubic shaping property and low ML decoding complexity via codes over F4for number of transmit antennas N = 2m, m >; 1, and rates R >; 1 complex symbols per channel use. The new codes have the least ML decoding complexity among all known codes for a large set of (N, R) pairs. The new full-rate codes of this paper (R = N) are not only information-lossless and fully diverse but also have the least known ML decoding complexity in the literature. For N ≥ 4, the new full-rate codes are the first instances of full-diversity, information-lossless STBCs with low ML decoding complexity. We also give a sufficient condition for STBCs obtainable from codes over F4to have cubic shaping property, and a sufficient condition for any design to give rise to a full-diversity STBC when the symbols are encoded using rotated square QAM constellations.

Recently, Guo and Xia introduced low complexity decoders called Partial Interference Cancellation (PIC) and PIC with Successive Interference Cancellation (PIC-SIC), which include the Zero Forcing (ZF) and ZF-SIC receivers as special cases, for point-to-point MIMO channels. In this paper, we show that PIC and PIC-SIC decoders are capable of achieving the full cooperative diversity available in wireless relay networks. We give sufficient conditions for a Distributed Space-Time Block Code (DSTBC) to achieve full diversity with PIC and PIC-SIC decoders and construct a new class of DSTBCs with low complexity full-diversity PIC-SIC decoding using complex orthogonal designs. The new class of codes includes a number of known full-diversity PIC/PIC-SIC decodable Space-Time Block Codes (STBCs) constructed for point-to-point channels as special cases. The proposed DSTBCs achieve higher rates (in complex symbols per channel use) than the multigroup ML decodable DSTBCs available in the literature. Simulation results show that the proposed codes have better bit error rate performance than the best known low complexity, full-diversity DSTBCs.

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.

In this paper, we give a new framework for constructing low ML decoding complexity space-time block codes (STBCs) using codes over the Klein groupK. 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 overK, for number of transmit antennasN=2m,m≥ 1, and ratesR>; 1 complex symbols per channel use. WhenR=N, the new STBCs are information-lossless as well. The new class of STBCs have the least known ML decoding complexity among all the codes available in the literature for a large set of (N,R) pairs.

Low complexity decoders called Partial Interference Cancellation (PIC) and PIC with Successive Interference Cancellation (PIC-SIC), which include the Zero Forcing (ZF) and ZF-SIC receivers as special cases, were given by Guo and Xia along with sufficient conditions for a Space-Time Block Code (STBC) to achieve full diversity with PIC/PIC-SIC decoding for point-to-point MIMO channels. In Part-I of this two part series of papers, we give new 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. We then show that PIC and PIC-SIC decoders are capable of achieving the full cooperative diversity available in wireless relay networks and give sufficient conditions for a Distributed Space-Time Block Code (DSTBC) to achieve full diversity with PIC and PIC-SIC decoders. In Part-II, we construct new low complexity full-diversity PIC/PIC-SIC decodable STBCs and DSTBCs that achieve higher rates than the known full-diversity low complexity ML decodable STBCs and DSTBCs.

In this second part of a two part series of papers, we construct a new class of Space-Time Block Codes (STBCs) for point-to-point MIMO channel and Distributed STBCs (DSTBCs) for the amplify-and-forward relay channel that give full-diversity with Partial Interference Cancellation (PIC) and PIC with Successive Interference Cancellation (PIC-SIC) decoders. The proposed class of STBCs include most of the known full-diversity low complexity PIC/PIC-SIC decodable STBCs as special cases. We also show that a number of known full-diversity PIC/PIC-SIC decodable STBCs that were constructed for the point-to-point MIMO channel can be used as full-diversity PIC/PIC-SIC decodable DSTBCs in relay networks. For the same decoding complexity, the proposed STBCs and DSTBCs achieve higher rates than the known low decoding complexity codes. Simulation results show that the new codes have a better bit error rate performance than the low ML decoding complexity codes available in the literature.

For a family/sequence of Space-Time Block Codes (STBCs) C1, C2, ..., with increasing number of transmit antennas Ni, with rates Ricomplex symbols per channel use, i = 1, 2,..., the asymptotic normalized rate is defined as limi→∞Ri/Ni. A family of STBCs is said to be asymptotically-good if the asymptotic normalized rate is non-zero, i.e., when the rate scales as a nonzero fraction of the number of transmit antennas. An STBC C is said to be g-group ML-decodable if its information symbols can be partitioned into g groups, such that each group of symbols can be ML decoded independently of others. In this paper, for g ≥ 2, we construct g-group ML-decodable codes with rates greater than one complex symbol per channel use. These codes are asymptotically good too. For g >; 2, these are the first instances of g-group ML-decodable codes, with rates greater than 1, presented in the literature. We also construct multigroup ML-decodable codes with the best known asymptotic normalized rates. Specifically, we propose delay-optimal 2-group ML-decodable codes for number of antennas N >; 1 with rate N/4 + 1/N for even N and rate N/4 + 5/4N - ½ for odd N. We construct delay optimal, g-group ML-decodable codes, g >; 2, for number of antennas N that are a multiple of g2⌊g-1/2⌋with rate N/g2g-1+ g2-g/2N. We also construct non-delay-optimal g-group ML-decodable codes, g ≥ 2, for number of antennas N that are a multiple of 2⌊g-1/2⌋, with delay gN and rate N/2g-1 + g-1/2N.

In this paper we construct low ML 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 F4domain. The problem of constructing low ML decoding complexity STBCs is shown to be equivalent to finding certain codes over F4. It is shown that almost all known low ML decoding complexity STBCs can be obtained by this approach. New classes of codes are given that have the least known ML decoding complexity in some ranges of rate.

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.