This paper investigates the design of codes for multiple-input multiple-output (MIMO) multiple access channel (MAC). If a joint maximum-likelihood decoding is to be performed at the receiver, then every MIMO-MAC code can be regarded as a single-user code, where the minimum determinant criterion proposed by Tarokh et al. is useful for designing such codes and for upper bounding the maximum pairwise error probability (PEP), whenever the codes are of finite rate and operate in finite signal-to-noise ratio range. Unlike the case of single-user codes where the minimum determinant can be lower bounded by a fixed constant as code-rate grows, it was proved by Lahtonen et al. that the minimum determinant of MIMO-MAC codes decays as a function of the rates. This decay phenomenon is further investigated in this paper, and upper bounds for the decays of minimum determinant corresponding to each error event are provided. Lower bounds for the optimal decay are established and are based on an explicit construction of codes using algebraic number theory and Diophantine approximation. For some error profiles, the constructed codes are shown to meet the aforementioned upper bounds, hence they are optimal finite-rate codes in terms of PEPs associated with such error events. An asymptotic diversity-multiplexing gain tradeoff (DMT) analysis of the proposed codes is also given. It is shown that these codes are DMT optimal when the values of multiplexing gains are small.

An integral component of a turbo code is a carefully designed interleaver. Interleavers based on quadratic permutation polynomials (moduloN) were introduced by Sun and Takeshita. They have several good properties and have been selected to be used in a cellular phone system. Ryu and Takeshita later initiated the study of the related deinterleavers. Here we extend this latter work and introduce a very efficient method for computing the (degree of the) lowest degree polynomial giving the deinterleaver. Our approach is based on combining two techniques. The Chinese remainder theorem allows us to study one prime power factor ofNat a time. Our other technique is to first present the inverse function as a power series with integer coefficients. ModuloNthat series is actually a polynomial. The polynomials yielding the same function form a coset of the ideal of identically vanishing polynomials. With the aid of a known Gröbner basis of that ideal we then finally identify a minimal degree polynomial within the given coset.

Explicit code constructions for multiple-input multiple-output (MIMO) multiple-access channels (MAC) with$K$users are presented in this paper. The first construction is dedicated to the case of symmetric MIMO-MAC where all the users have the same number of transmit antennas$n_{t}$and transmit at the same level of per-user multiplexing gain$r$. Furthermore, we assume that the users transmit in an independent fashion and do not cooperate. The construction is systematic for any values of$K$,$n_{t}$and$r$. It is proved that this newly proposed construction achieves the optimal MIMO-MAC diversity-multiplexing gain tradeoff (DMT) provided by Tseat high-$\hbox{SNR}$regime.

Multiple-input double-output (MIDO) codes are important in future wireless communications, where the portable end-user device is physically small and will typically contain maximum two receive antennas. Especially tempting is the 4×2 channel, where the four transmitters can either be all at one station, or separated between two different stations. Such channels optimally employ rate-two space-time (ST) codes consisting of 4×4 matrices. Unfortunately, such codes are in general very complex to decode, the worst-case complexity being as high as N8, where N is the size of the complex signaling alphabet. Hence, constructions with reduced complexity are called for. One option, of course, is to use the rate-one codes such as the quasi-orthogonal codes. However, if full multiplexing, i.e., transmission of two symbols per channel use is to be maintained, this option has to be put aside. Recently, some reduced complexity constructions have been proposed, but they have mainly been based on ad hoc methods and have resulted in a specific code instead of a more general class of codes. In this paper, it will be shown that cyclic division algebra (CDA) based codes satisfying certain criteria will always result in at least 25% worst-case complexity reduction, while maintaining full diversity and even the non-vanishing determinant (NVD) property. The reduction follows from the fact that the codes will consist of four Alamouti blocks allowing simplified decoding. At the moment, such reduction is the best known for rate-two MIDO codes,. The code proposed in was the first one to provably fulfill the related algebraic properties, and shall be repeated here as an example. Further, a new low-complexity design resulting from the proposed criteria is presented, and shown to have excellent performance through simulations.

This paper considers certain aspects of some well-known multiple-input single-output (MISO) codes. In the first section it is proved how in some special cases the n + 1 MISO channel can be seen as consisting of several parallel MISO channels having less transmit antennas. It is also pointed out that unitary conjugation does not change the diversity-multiplexing tradeoff (DMT) of a code. These simple results are then applied to analyze the DMT of several well-known MISO codes. In particular its is proved that all the considered codes are DMT optimal. As a by-product of this study it is seen that the full-diversity quasi-orthogonal codes by Su and Xia are unitarily equivalent to division algebraic constructions. This relation is then used to place the constructions by Su and Xia into a wider context. In the latter part of the paper the 2 + 1 slow fading MISO channel is considered and it is proven that one of the previously proposed MISO multi-block codes (MB-codes) has a linear worst-case sphere decoding complexity.

An integral component of a turbo code is a carefully designed interleaver. Interleavers based on quadratic permutation polynomials (modulo N) were introduced by Sun and Takeshita. They have several good properties and were selected to be used in a future cellular phone system. Ryu and Takeshita later initiated the study of the related deinterleavers. Here we extend this latter work and introduce a very efficient method for computing the (degree of the) lowest degree polynomial giving the deinterleaver. Our approach is based on combining two techniques. The Chinese remainder theorem allows us to study one prime factor of N at a time. Our other technique is to first present the inverse function as a power series, and then turn that power series to a low degree polynomial using a Gröbner basis of the ideal of polynomials vanishing modulo a prime power.

It is shown why the discriminant of a maximal order within a cyclic division algebra must be minimized in order to get the densest possible matrix lattices with a prescribed nonvanishing minimum determinant. Using results from class field theory, a lower bound to the minimum discriminant of a maximal order with a given center and index (= the number of Tx/Rx antennas) is derived. Also numerous examples of division algebras achieving the bound are given. For example, a matrix lattice with quadrature amplitude modulation (QAM) coefficients that has 2.5 times as many codewords as the celebrated Golden code of the same minimum determinant is constructed. Also, a general algorithm due to Ivanyos and Ronyai for finding maximal orders within a cyclic division algebra is described and enhancements to this algorithm are discussed. Also some general methods for finding cyclic division algebras of a prescribed index achieving the lower bound are proposed.

Recently, a family of full-rate, full-diversity space-time block codes (STBCs) for 2 times 2 multiple-input multiple-output (MIMO) channels was proposed in the works of Tirkkonen et al., using a combination of Clifford algebra and Alamouti structures, namely twisted space-time transmit diversity code. This family was recently rediscovered by Paredes et al., and they pointed out that such STBCs enable reduced-complexity maximum-likelihood (ML) decoding. Independently, the same STBCs were found in the work of Samuel and Fitz (2007) and named multi-strata space-time codes. In this paper we show how this code can be constructed algebraically from a particular cyclic division algebra (CDA). This formulation enables to prove that the code has the non-vanishing determinant (NVD) property and hence achieves the diversity-multiplexing tradeoff (DMT) optimality. The fact that the normalized minimum determinant is 1/radic(7) places this code in the second position with respect to the golden code, which exhibits a minimum determinant of 1/radic(5), and motivates the name silver code.

In this paper, we construct explicit rate-one, full-diversity, geometrically dense matrix lattices with large, nonvanishing determinants (NVDs) for four transmit antenna multiple-input–single-output (MISO) space-time (ST) applications. The constructions are based on the theory of rings of algebraic integers and related subrings of the Hamiltonian quaternions and can be extended to a larger number of Tx antennas. The usage of ideals guarantees an NVD larger than one and an easy way to present the exact proofs for the minimum determinants. The idea of finding denser sublattices within a given division algebra is then generalized to a multiple-input–multiple-output (MIMO) case with an arbitrary number of Tx antennas by using the theory of cyclic division algebras (CDAs) and maximal orders. It is also shown that the explicit constructions in this paper all have a simple decoding method based on sphere decoding. Related to the decoding complexity, the notion of sensitivity is introduced, and experimental evidence indicating a connection between sensitivity, decoding complexity, and performance is provided. Simulations in a quasi-static Rayleigh fading channel show that our dense quaternionic constructions outperform both the earlier rectangular lattices and the rotated quasi-orthogonal ABBA lattice as well as the diagonal algebraic space-time (DAST) lattice. We also show that our quaternionic lattice is better than the DAST lattice in terms of the diversity-multiplexing gain tradeoff (DMT).

The authors give a construction of multiblock space-time block codes from cyclic division algebras with a givennth root of unity as the nonnorm element. The construction uses local class field theory. Multiblock codes withMblocks can achieve anM-fold increase in diversity.

Since the cyclic division algebras and their orders have become standard material for researchers seeking to construct good MIMO-lattices. The usual construction of the actual lattice corresponds to a cyclic submodule of an order. In a recent submission we studied the problem of identifying those cyclic division algebras that consume the least amount of the available signal space for a given minimum determinant. In this semi-tutorial note some of the material from is recapped together with hopefully illuminating examples. We also motivate our concept of density by previewing upper and lower bounds, and taking a closer look at some of the suggested MIMO-lattices in relation to these bounds.

We show why the discriminant of a maximal order within a cyclic division algebra must be minimized in order to get the densest possible matrix lattices with a prescribed non-vanishing minimal determinant. Using results from class field theory we derive a lower bound to the minimum discriminant of a maximal order with a given center and index (= the number of Tx/Rx antennas). We also give examples of division algebras achieving our bound. For example, we construct a matrix lattice with QAM coefficients that has (inside 'large' subsets of the signal space) 2.5 times as many codewords as the celebrated Golden code of the same minimum determinant. We also give another matrix lattice with coefficients from the hexagonal lattice with an even higher density

A means to construct dense, full-diversity STBCs from maximal orders in central simple algebras is introduced for the first time. As an example we construct an efficient ST lattice code with non-vanishing determinant for 4 transmit antenna MISO application. Also a general algorithm for testing the maximality of a given order is presented. By using a maximal order instead of just the ring of algebraic integers, the size of the code increases without losses in the minimum determinant. The usage of a proper ideal of a maximal order further improves the code, as the minimum determinant increases. Simulations in a quasi-static Rayleigh fading channel show that our lattice outperforms the DAST-lattice due to the properties described above.

We construct some geometrically dense matrix lattices with good minimum determinants for 4 transmit antenna MISO applications. The construction is based on the theory of rings of algebraic integers and related subrings of the Hamiltonian quaternions. Simulations in a quasi-static Rayleigh fading channel show that our dense quaternionic constructions outperform the earlier rectangular lattices as well as the DAST-lattice

Rate one full-diversity orthogonal designs for four transmit antennas are known not to exist so either rate, orthogonality or diversity is compromised. Use of algebraic number theory has lead to full-diversity, rate one code constructions. The use of regular representations of certain rings of algebraic integers and their Hamiltonian quaternionic counterparts to construct lattices of rank 8 that yield rate one full-diversity lattice constellation codes for four transmitting antennas is presented in this paper. The resulting codes require less transmission power per bit. Using number theoretic tools a general lower bound to the minimum Euclidean distance within the received constellation is computed

ML-decoding significant savings can be achieved by taking advantage of the common parts of the different codewords. This idea underlying the construction of the so called BCJR-trellis of a block code. By design, whenever the paths corresponding to two different elements, share an edge between splitting points and have identical components at positions for any channel vector. Thus this trellis can be used for efficient ML-decoding.

The quaternary Calderbank-McGuire (see Des., Codes Cryptogr., vol.10, no.2, 1997) code is a Z/sub 4/-linear code of length 32 which has 2/sup 37/ codewords and a minimum Lee distance of 12. The Gray map of this code is known to be a nonlinear binary (64, 2/sup 37/,12) code. The Z/sub 4/-linear Calderbank-McGuire code can correct all errors with Lee weight /spl les/5. An algebraic decoding algorithm for the code is presented in this paper. Furthermore, we discuss an alternative decoding method which takes advantage of the efficient BCH decoding algorithm.

After a discussion of automorphisms of Reed-Muller codes the authors show that the Reed-Muller code R(r,m) is not Z/sub 4/-linear for 3/spl les/r/spl les/m-2, proving a conjecture by Hammons, Kumar, Calderbank, Sloane, and Sole (1994).

A previously derived upper bound on hybrid sums over Galois rings is combined with a method due to Vinogradov (1954) to obtain an upper bound for the maximum aperiodic and odd correlations of the binary sequences constructed by Shanbhag, Kumar, and Helleseth (see Proc. 1995 IEEE Int. Symp. on Information Theory, 1995).

Slepian-type group codes generated by finite Coxeter groups are considered. The resulting class of group codes is a generalization of the well-known permutation modulation codes of Slepian (1965), it is shown that a restricted initial-point problem for these codes has a canonical solution that can easily be computed. This allows one to enumerate all optimal group codes in this restricted sense and essentially solves the initial-point problem for all finite reflection groups. Formulas for the cardinality and the minimum distance of such codes are given. The new optimal group codes from exceptional reflection groups that are obtained achieve high rates and have excellent distance properties. The decoding regions for maximum-likelihood (ML) decoding are explicitly characterized and an efficient ML-decoding algorithm is presented. This algorithm relies on an extension of Slepian's decoding of permutation modulation and has similar low complexity,.

O. Moreno and P.V. Kumar (IEEE Trans. Inform. Theory, vol.39, no.5, September 1993) showed how Deligne's theorem can be applied to coding theory. They studied certain subcodes of binary Reed-Muller codes and estimated the associated character sums over a field of q/sup 2/ elements. They obtained bounds of the order /spl Oscr/(q). The present paper shows that in one case one can improve the coefficient of q in the estimates. The author also shows that there is an error in Moreno and Kumar's argument and in some cases one needs need to replace a bound of the order /spl Oscr/(q) by a weaker bound of the order /spl Oscr/(q/sup 3/2/).>

Derives a new upper bound for the odd and the aperiodic correlations of binary sequences in the small Kasami family. The approach is based on a technique described in S. Litsyn and A. Tietavainen (1994) that is originally due to I.M. Vinogradov (1954). An essential ingredient in this method is a good upper bound on the discrete Fourier coefficients of a shifted product of a pair of sequences. The author obtains an upper bound of the order O(/spl radic/LlnL) for the maximal aperiodic and odd correlation magnitudes for sequences of length L.>