A general construction of space-time trellis codes for PSK signal sets

The diversity order and coding gain are crucial for the performance of a multiple antenna communication system. It is known that space-time trellis codes (STTC) can be used to achieve these objectives. In particular, we can use STTCs to obtain large coding gains. Many attempts have been made to construct STTCs which achieve full-diversity and good coding gains, though a general method of construction does not exist. Delay diversity code (rate-1) is known to achieve full-diversity, for any number of transmit antennas and any signal set, but does not give a good coding gain. A product distance code based delay diversity scheme (Tarokh, V. et al., IEEE Trans. Inform. Theory, vol.44, p.744-65, 1998) enables one to improve the coding gain and construct STTCs for any given number of states using coding in conjunction with delay diversity; it was stated as an open problem. We achieve such a construction. We assume a shift register based model to construct an STTC for any state complexity. We derive a sufficient condition for this STTC to achieve full-diversity, based on the delay diversity scheme. This condition provides a framework to do coding in conjunction with delay diversity for any signal constellation. Using this condition, we provide a formal rate-1 STTC construction scheme for PSK signal sets, for any number of transmit antennas and any given number of states, which achieves full-diversity and gives a good coding gain.

A unified construction of space-time codes with optimal rate-diversity tradeoff

The problem of constructing space-time (ST) block codes over a fixed, desired signal constellation is considered. In this situation, there is a tradeoff between the transmission rate as measured in constellation symbols per channel use and the transmit diversity gain achieved by the code. The transmit diversity is a measure of the rate of polynomial decay of pairwise error probability of the code with increase in the signal-to-noise ratio (SNR). In the setting of a quasi-static channel model, let n(t) denote the number of transmit antennas and T the block interval. For any n(t) <= T, a unified construction of (n(t) x T) ST codes is provided here, for a class of signal constellations that includes the familiar pulse-amplitude (PAM), quadrature-amplitude (QAM), and 2(K)-ary phase-shift-keying (PSK) modulations as special cases. The construction is optimal as measured by the rate-diversity tradeoff and can achieve any given integer point on the rate-diversity tradeoff curve. An estimate of the coding gain realized is given. Other results presented here include i) an extension of the optimal unified construction to the multiple fading block case, ii) a version of the optimal unified construction in which the underlying binary block codes are replaced by trellis codes, iii) the providing of a linear dispersion form for the underlying binary block codes, iv) a Gray-mapped version of the unified construction, and v) a generalization of construction of the S-ary case corresponding to constellations of size S-K. Items ii) and iii) are aimed at simplifying the decoding of this class of ST codes.

On Two-User Gaussian Multiple Access Channels With Finite Input Constellations

Constellation Constrained (CC) capacity regions of two-user Single-Input Single-Output (SISO) Gaussian Multiple Access Channels (GMAC) are computed for several Non-Orthogonal Multiple Access schemes (NO-MA) and Orthogonal Multiple Access schemes (O-MA). For NO-MA schemes, a metric is proposed to compute the angle(s) of rotation between the input constellations such that the CC capacity regions are maximally enlarged. Further, code pairs based on Trellis Coded Modulation (TCM) are designed with PSK constellation pairs and PAM constellation pairs such that any rate pair within the CC capacity region can be approached. Such a NO-MA scheme which employs CC capacity approaching trellis codes is referred to as Trellis Coded Multiple Access (TCMA). Then, CC capacity regions of O-MA schemes such as Frequency Division Multiple Access (FDMA) and Time Division Multiple Access (TDMA) are also computed and it is shown that, unlike the Gaussian distributed continuous constellations case, the CC capacity regions with FDMA are strictly contained inside the CC capacity regions with TCMA. Hence, for finite constellations, a NO-MA scheme such as TCMA is better than FDMA and TDMA which makes NO-MA schemes worth pursuing in practice for two-user GMAC. Then, the idea of introducing rotations between the input constellations is used to construct Space-Time Block Code (STBC) pairs for two-user Multiple-Input Single-Output (MISO) fading MAC. The proposed STBCs are shown to have reduced Maximum Likelihood (ML) decoding complexity and information-losslessness property. Finally, STBC pairs with reduced sphere decoding complexity are proposed for two-user Multiple-Input Multiple-Output (MIMO) fading MAC.

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.

The Treewidth of MDS and Reed-Muller Codes

The constraint complexity of a graphical realization of a linear code is the maximum dimension of the local constraint codes in the realization. The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parameterization of the maximum-likelihood decoding complexity for linear codes. In this paper, we show the surprising fact that for maximum distance separable codes and Reed-Muller codes, treewidth equals trelliswidth, which, for a code, is defined to be the least constraint complexity (or branch complexity) of any of its trellis realizations. From this, we obtain exact expressions for the treewidth of these codes, which constitute the only known explicit expressions for the treewidth of algebraic codes.

Leveraging coherent distributed space-time codes for noncoherent communication in relay networks via training

For point to point multiple input multiple output systems, Dayal-Brehler-Varanasi have proved that training codes achieve the same diversity order as that of the underlying coherent space time block code (STBC) if a simple minimum mean squared error estimate of the channel formed using the training part is employed for coherent detection of the underlying STBC. In this letter, a similar strategy involving a combination of training, channel estimation and detection in conjunction with existing coherent distributed STBCs is proposed for noncoherent communication in Amplify-and-Forward (AF) relay networks. Simulation results show that the proposed simple strategy outperforms distributed differential space-time coding for AF relay networks. Finally, the proposed strategy is extended to asynchronous relay networks using orthogonal frequency division multiplexing.

Systematic Construction of Linear Transform Based Full-Diversity, Rate-One Space-Time Frequency Codes

In this paper, we generalize the existing rate-one space frequency (SF) and space-time frequency (STF) code constructions. The objective of this exercise is to provide a systematic design of full-diversity STF codes with high coding gain. Under this generalization, STF codes are formulated as linear transformations of data. Conditions on these linear transforms are then derived so that the resulting STF codes achieve full diversity and high coding gain with a moderate decoding complexity. Many of these conditions involve channel parameters like delay profile (DP) and temporal correlation. When these quantities are not available at the transmitter, design of codes that exploit full diversity on channels with arbitrary DIP and temporal correlation is considered. Complete characterization of a class of such robust codes is provided and their bit error rate (BER) performance is evaluated. On the other hand, when channel DIP and temporal correlation are available at the transmitter, linear transforms are optimized to maximize the coding gain of full-diversity STF codes. BER performance of such optimized codes is shown to be better than those of existing codes.

On the Conversion of Hensel Codes to Farey Rationals

Three different algorithms are described for the conversion of Hensel codes to Farey rationals. The first algorithm is based on the trial and error factorization of the weight of a Hensel code, inversion and range test. The second algorithm is deterministic and uses a pair of different p-adic systems for simultaneous computation; from the resulting weights of the two different Hensel codes of the same rational, two equivalence classes of rationals are generated using the respective primitive roots. The intersection of these two equivalence classes uniquely identifies the rational. Both the above algorithms are exponential (in time and/or space).

Space-Time Codes Achieving the DMD Tradeoff of the MIMO-ARQ Channel

For the quasi-static, Rayleigh-fading multiple-input multiple-output (MIMO) channel with n(t) transmit and n(r) receive antennas, Zheng and Tse showed that there exists a fundamental tradeoff between diversity and spatial-multiplexing gains, referred to as the diversity-multiplexing gain (D-MG) tradeoff. Subsequently, El Gamal, Caire, and Damen considered signaling across the same channel using an L-round automatic retransmission request (ARQ) protocol that assumes the presence of a noiseless feedback channel capable of conveying one bit of information per use of the feedback channel. They showed that given a fixed number L of ARQ rounds and no power control, there is a tradeoff between diversity and multiplexing gains, termed the diversity-multiplexing-delay (DMD) tradeoff. This tradeoff indicates that the diversity gain under the ARQ scheme for a particular information rate is considerably larger than that obtainable in the absence of feedback. In this paper, a set of sufficient conditions under which a space-time (ST) code will achieve the DMD tradeoff is presented. This is followed by two classes of explicit constructions of ST codes which meet these conditions. Constructions belonging to the first class achieve minimum delay and apply to a broad class of fading channels whenever n(r) >= n(t) and either L/n(t) or n(t)kslashL. The second class of constructions do not achieve minimum delay, but do achieve the DMD tradeoff of the fading channel for all statistical descriptions of the channel and for all values of the parameters n(r,) n(t,) L.

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), nonorthogonal 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 (ST) 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 orthogonal and the nonorthogonal amplify-and-forward (NAF) protocols have identical DMT when the time durations of the broadcast and cooperative phases are optimally chosen to suit the respective protocol. Moreover our code construction for the OAF protocol incurs less delay. 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. The variable-NSDF protocol is shown to improve on the DMT of the best previously known static protocol when the number of relays is greater than two. Also included is a DMT optimal code construction for the NAF protocol.

Ternary Barker codes

Certain ternary codes having good autocorrelation properties akin to Barker codes are described.

Optical Barker codes

Certain binary codes having good autocorrelation properties akin to Barker codes are studied.

Systematic search for optical Barker codes with minimum length

A method that yields optical Barker codes of smallest known lengths for given discrimination is described.

Optical Barker codes

Certain binary codes having good autocorrelation properties akin to Barker codes are studied.