On /spl Zopf//sub 4/-linear Preparata-like and Kerdock-like codes

We say that a binary code of length n is additive if it is isomorphic to a subgroup of /spl Zopf//sub 2//sup /spl alpha// /spl times/ /spl Zopf//sub 4//sup /spl beta//, where the quaternary coordinates are transformed to binary by means of the usual Gray map and hence /spl alpha/ + 2/spl beta/ = n. In this paper, we prove that any additive extended Preparata (1968) -like code always verifies /spl alpha/ = 0, i.e., it is always a /spl Zopf//sub 4/-linear code. Moreover, we compute the rank and the dimension of the kernel of such Preparata-like codes and also the rank and the kernel of the /spl Zopf//sub 4/-dual of these codes, i.e., the /spl Zopf//sub 4/-linear Kerdock-like codes.     

The rank and kernel of extended 1-perfect /spl Zopf//sub 4/-linear and additive non-/spl Zopf//sub 4/-linear codes

A binary extended 1-perfect code of length n + 1 = 2/sup t/ is additive if it is a subgroup of /spl Zopf//sub 2//sup /spl alpha// /spl times/ /spl Zopf//sub 4//sup /spl beta//. The punctured code by deleting a /spl Zopf//sub 2/ coordinate (if there is one) gives a perfect additive code. 1-perfect additive codes were completely characterized and by using that characterization we compute the possible parameters /spl alpha/, /spl beta/, rank, and dimension of the kernel for extended 1-perfect additive codes. A very special case is that of extended 1-perfect /spl Zopf//sub 4/-linear codes.     

Cyclic codes over GR(4/sup m/) which are also cyclic over /spl Zopf//sub 4/

Let GR(4/sup m/) be the Galois ring of characteristic 4 and cardinality 4/sup m/, and /spl alpha/_={/spl alpha//sub 0/,/spl alpha//sub 1/,...,/spl alpha//sub m-1/} be a basis of GR(4/sup m/) over /spl Zopf//sub 4/ when we regard GR(4/sup m/) as a free /spl Zopf//sub 4/-module of rank m. Define the map d/sub /spl alpha/_/ from GR(4/sup m/)[z]/(z/sup n/-1) into /spl Zopf//sub 4/[z]/(z/sup mn/-1) by d/spl alpha/_(a(z))=/spl Sigma//sub i=0//sup m-1//spl Sigma//sub j=0//sup n-1/a/sub ij/z/sup mj+i/ where a(z)=/spl Sigma//sub j=0//sup n-1/a/sub j/z/sup j/ and a/sub j/=/spl Sigma//sub i=0//sup m-1/a/sub ij//spl alpha//sub i/, a/sub ij//spl isin//spl Zopf//sub 4/. Then, for any linear code C of length n over GR(4/sup m/), its image d/sub /spl alpha/_/(C) is a /spl Zopf//sub 4/-linear code of length mn. In this article, for n and m being odd integers, it is determined all pairs (/spl alpha/_,C) such that d/sub /spl alpha/_/(C) is /spl Zopf//sub 4/-cyclic, where /spl alpha/_ is a basis of GR(4/sup m/) over /spl Zopf//sub 4/, and C is a cyclic code of length n over GR(4/sup m/).     

Generalization of the /spl Sigma//sub 0/-rank criteria for space-time codes

Recently, Liu et al., developed the /spl Sigma//sub 0/-rank criteria for space-time codes. It provides a sufficient condition on codeword and generator matrices defined over finite rings /spl Zopf//sub 2k/(j) to ensure full spatial diversity with 2/sup 2k/-QAM modulation. Here, we generalize the /spl Sigma//sub 0/-rank criteria and derive a sufficient condition on the generator matrices defined over finite rings /spl Zopf//sub 2l/(j) to ensure full spatial diversity with 2/sup 2k/-QAM modulation for any positive integer l/spl les/k. We also show that generator matrices defined over GF(2) satisfying the BPSK stacking construction constraint of Mammons and El Gamal achieve full spatial diversity when used with 2/sup 2k/-QAM modulation.     

Generalized MacWilliams identities for /spl Zopf//sub 4/-linear codes

In this correspondence, the generalized MacWilliams identities between the support weight distributions of a /spl Zopf//sub 4/-linear code of type 4/sup k/ and that of its dual are established.     

On the generators of /spl Zopf//sub 4/ cyclic codes of length 2/sup e/

Results are presented on the generators of ideals in the ring /spl Zopf//sub 4/[x]/(x/sup n/-1). In particular, each ideal (cyclic code) has a unique distinguished set of generators that characterizes any cyclic code. Some results about dual codes are also included.     

Lee metric decoding of alternant codes over /spl Zopf//sub q/

A multi-stage Lee metric list decoding approach for alternant codes over /spl Zopf/(p/sup l/ )where p is prime and l/spl ges/2 is proposed. It is demonstrated that the error-correcting capability of such a decoding scheme increasingly surpasses that of a single-stage decoding approach as the length of the code and l increases.     

Curves on a sphere, shift-map dynamics, and error control for continuous alphabet sources

We consider two codes based on dynamical systems, for transmitting information from a continuous alphabet, discrete-time source over a Gaussian channel. The first code, a homogeneous spherical code, is generated by the linear dynamical system s/spl dot/=As, with A a square skew-symmetric matrix. The second code is generated by the shift map s/sub n/=b/sub n/s/sub n-1/(mod 1). The performance of each of these codes is determined by the geometry of its locus or signal set, specifically, its arc length and minimum distance, suitably defined. We show that the performance analyses for these systems are closely related, and derive exact expressions and bounds for relevant geometric parameters. We also observe that the lattice /spl Zopf//sup N/ underlies both modulation systems and we develop a fast decoding algorithm that relies on this observation. Analytic results show that for fixed bandwidth expansion, good scaling behavior of the mean squared error is obtained relative to the channel signal-to-noise ratio (SNR). Particularly interesting is the resulting observation that sampled, exponentially chirped modulation codes are good bandwidth expansion codes.     

Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes

Given positive integers n and d, let A/sub 2/(n,d) denote the maximum size of a binary code of length n and minimum distance d. The well-known Gilbert-Varshamov bound asserts that A/sub 2/(n,d)/spl ges/2/sup n//V(n,d-l), where V(n,d) = /spl sigma//sub i=0//sup d/(/sub i//sup n/) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that A/sub 2/(n, d)/spl ges/c2/sup n//V(n,d-1)log/sub 2/V(n, d-1) whenever d/n/spl les/0.499. The result follows by recasting the Gilbert-Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed.     

Product-function frames in l/sup 2/(/spl Zopf/)

Frames are the most widely used tool for signal representation in different domains. In this correspondence, we introduce the concept of product-function frames for l/sup 2/(/spl Zopf/). The frame elements of these frames are represented as products of two or more sequences. This forms a generalized structure for many currently existing transforms. We define necessary and sufficient conditions on the frame elements so that they form a frame for l/sup 2/(/spl Zopf/). We obtain windowed transforms as a special case and derive the biorthogonal-like condition. Finally, we introduce a new family of transforms for finite-dimensional subspaces of l/sup 2/(/spl Zopf/), which we call the "scalemodulation transforms". The frame elements of these transforms can be obtained via scaling and modulating a "mother" window. This transform, thus, complements the shift-modulation structure of the discrete-time Gabor transform and the shift-scale structure of the discrete wavelet transform.     

Duality and support weight distributions

We show how to compute the support weight distribution A/sub i//sup r/ for r/spl ges/k-d/sub 2//sup /spl perp//+3, where d/sub 2//sup /spl perp// is the second minimum support weight of a code, provided the weight enumerator of the dual code is known.     

The structure of tail-biting trellises: minimality and basic principles

Basic structural properties of tail-biting trellises are investigated. We start with rigorous definitions of various types of minimality for tail-biting trellises. We then show that biproper and/or nonmergeable tail-biting trellises are not necessarily minimal, even though every minimal tail-biting trellis is biproper. Next, we introduce the notion of linear (or group) trellises and prove, by example, that a minimal tail-biting trellis for a binary linear code need not have any linearity properties whatsoever. We observe that a trellis - either tail-biting or conventional - is linear if and only if it factors into a product of elementary trellises. Using this result, we show how to construct, for any given linear code /spl Copf/, a tail-biting trellis that minimizes the product of state-space sizes among all possible linear tail-biting trellises. We also prove that every minimal linear tail-biting trellis for /spl Copf/ arises from a certain n/spl times/n characteristic matrix, and show how to compute this matrix in time O(n/sup 2/) from any basis for /spl Copf/. Furthermore, we devise a linear-programming algorithm that starts with the characteristic matrix and produces a linear tail-biting trellis for /spl Copf/; which minimizes the maximum state-space size. Finally, we consider a generalized product construction for tail-biting trellises, and use it to prove that a linear code /spl Copf/ and its dual /spl Copf//sup /spl perp///spl Copf//sup /spl perp///spl Copf//sup /spl perp///spl Copf//sup /spl perp// have the same state-complexity profiles.     

Demonstration of 1789 V, 6.68 m/spl Omega/ /spl middot/ cm/sup 2/ 4H-SiC merged-PiN-Schottky diodes

The design, fabrication and characterisation of a high performance 4H-SiC diode of 1789 V-6.6 A with a low differential specific-on resistance (R/sub SP/spl I.bar/ON/) of 6.68 m/spl Omega/ /spl middot/ cm/sup 2/, based on a 10.3 /spl mu/m 4H-SiC blocking layer doped to 6.6/spl times/10/sup 15/ cm/sup -3/, is reported. The corresponding figure-of-merit of V/sub B//sup 2//R/sub SP/spl I.bar/ON/ for this diode is 479 MW/cm/sup 2/, which substantially surpasses previous records for all other MPS diodes.     

On the complexity of multicovering radii

The multicovering radius is a generalization of the covering radius. In this correspondence, we show that lower-bounding the m-covering radius of an arbitrary binary code is NP-complete when m is polynomial in the length of the code. Lower-bounding the m-covering radius of a linear code is /spl Sigma//sub 2//sup P/-complete when m is polynomial in the length of the code. If P is not equal to NP, then the m-covering radius of an arbitrary binary code cannot be approximated within a constant factor or within a factor n/sup /spl epsi// where n is the length of the code and /spl epsi/<1, in polynomial time. Note that the case when m=1 was also previously unknown. If NP is not equal to /spl Sigma//sub 2//sup P/,then the m-covering radius of a linear code cannot be approximated within a constant factor or within a factor n/sup /spl epsi// where n is the length of the code and /spl epsi/<1, in polynomial time.     

MIMO linear equalization with an H/sup /spl infin// criterion

In this paper, we study the problem of linearly equalizing the multiple-input multiple-output (MIMO) communications channels from an H/sup /spl infin// point of view. H/sup /spl infin// estimation theory has been recently introduced as a method for designing filters that have acceptable performance in the face of model uncertainty and lack of statistical information on the exogenous signals. In this paper, we obtain a closed-form solution to the square MIMO linear H/sup /spl infin// equalization problem and parameterize all possible H/sup /spl infin//-optimal equalizers. In particular, we show that, for minimum phase channels, a scaled version of the zero-forcing equalizer is H/sup /spl infin//-optimal. The results also indicate an interesting dichotomy between minimum phase and nonminimum phase channels: for minimum phase channels the best causal equalizer performs as well as the best noncausal equalizer, whereas for nonminimum phase channels, causal equalizers cannot reduce the estimation error bounds from their a priori values. Our analysis also suggests certain remedies in the nonminimum phase case, namely, allowing for finite delay, oversampling, or using multiple sensors. For example, we show that H/sup /spl infin// equalization of nonminimum phase channels requires a time delay of at least l units, where l is the number of nonminimum phase zeros of the channel.     

Asymptotic properties on codeword lengths of an optimal FV code for general sources

This correspondence is concerned with asymptotic properties on the codeword length of a fixed-to-variable length code (FV code) for a general source {X/sup n/}/sub n=1//sup /spl infin// with a finite or countably infinite alphabet. Suppose that for each n /spl ges/ 1 X/sup n/ is encoded to a binary codeword /spl phi//sub n/(X/sup n/) of length l(/spl phi//sub n/(X/sup n/)). Letting /spl epsiv//sub n/ denote the decoding error probability, we consider the following two criteria on FV codes: i) /spl epsiv//sub n/ = 0 for all n /spl ges/ 1 and ii) lim sup/sub n/spl rarr//spl infin///spl epsiv//sub n/ /spl les/ /spl epsiv/ for an arbitrarily given /spl epsiv/ /spl isin/ [0,1). Under criterion i), we show that, if X/sup n/ is encoded by an arbitrary prefix-free FV code asymptotically achieving the entropy, 1/nl(/spl phi//sub n/(X/sup n/)) - 1/nlog/sub 2/ 1/PX/sup n/(X/sup n/) /spl rarr/ 0 in probability as n /spl rarr/ /spl infin/ under a certain condition, where P/sub X//sup n/ denotes the probability distribution of X/sup n/. Under criterion ii), we first determine the minimum rate achieved by FV codes. Next, we show that 1/nl(/spl phi//sub n/(X/sup n/)) of an arbitrary FV code achieving the minimum rate in a certain sense has a property similar to the lossless case.     

Near-ellipsoidal Voronoi coding

We consider a special case of Voronoi coding, where a lattice /spl Lambda/ in /spl Ropf//sup n/ is shaped (or truncated) using a lattice /spl Lambda/'={(m/sub 1/x/sub 1/,...,m/sub n/x/sub n/)|(x/sub 1/,...,x/sub n/)/spl isin//spl Lambda/} for a fixed m_=(m/sub 1/,...,m/sub n/)/spl isin/(/spl Nopf//spl bsol/{0,1})/sup n/. Using this technique, the shaping boundary is near-ellipsoidal. It is shown that the resulting codes can be indexed by standard Voronoi indexing algorithms plus a conditional modification step, as far as /spl Lambda/' is a sublattice of /spl Lambda/. We derive the underlying conditions on m_ and present generic near-ellipsoidal Voronoi indexing algorithms. Examples of constraints on m_ and conditional modification are provided for the lattices A/sub 2/, D/sub n/ (n/spl ges/2) and 2D/sub n//sup +/ (n even /spl ges/4).     

Improving the Gilbert-Varshamov bound for q-ary codes

Given positive integers q,n, and d, denote by A/sub q/(n,d) the maximum size of a q-ary code of length n and minimum distance d. The famous Gilbert-Varshamov bound asserts that A/sub q/(n,d+1)/spl ges/q/sup n//V/sub q/(n,d) where V/sub q/(n,d)=/spl Sigma//sub i=0//sup d/ (/sub i//sup n/)(q-1)/sup i/ is the volume of a q-ary sphere of radius d. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant /spl alpha/ less than (q-1)/q there is a positive constant c such that for d/spl les//spl alpha/n A/sub q/(n,d+1)/spl ges/cq/sup n//V/sub q/(n,d)n. This confirms a conjecture by Jiang and Vardy.     

List decoding from erasures: bounds and code constructions

We consider the problem of list decoding from erasures. We establish lower and upper bounds on the rate of a (binary linear) code that can be list decoded with list size L when up to a fraction p of its symbols are adversarially erased. Such bounds already exist in the literature, albeit under the label of generalized Hamming weights, and we make their connection to list decoding from erasures explicit. Our bounds show that in the limit of large L, the rate of such a code approaches the "capacity" (1 - p) of the erasure channel. Such nicely list decodable codes are then used as inner codes in a suitable concatenation scheme to give a uniformly constructive family of asymptotically good binary linear codes of rate /spl Omega/(/spl epsiv//sup 2//log(1//spl epsiv/)) that can be efficiently list-decoded using lists of size O(1//spl epsiv/) when an adversarially chosen (1 - /spl epsiv/) fraction of symbols are erased, for arbitrary /spl epsiv/ > 0. This improves previous results in this vein, which achieved a rate of /spl Omega/(/spl epsiv//sup 3/log(1//spl epsiv/)).     

Markov types and minimax redundancy for Markov sources

Redundancy of universal codes for a class of sources determines by how much the actual code length exceeds the optimal code length. In the minimax scenario, one designs the best code for the worst source within the class. Such minimax redundancy comes in two flavors: average minimax or worst case minimax. We study the worst case minimax redundancy of universal block codes for Markovian sources of any order. We prove that the maximal minimax redundancy for Markov sources of order r is asymptotically equal to 1/2m/sup r/(m-1)log/sub 2/n+log/sub 2/A/sub m//sup r/-(lnlnm/sup 1/(m-1)/)/lnm+o(1), where n is the length of a source sequence, m is the size of the alphabet, and A/sub m//sup r/ is an explicit constant (e.g., we find that for a binary alphabet m=2 and Markov of order r=1 the constant A/sub 2//sup 1/=16/spl middot/G/spl ap/14.655449504 where G is the Catalan number). Unlike previous attempts, we view the redundancy problem as an asymptotic evaluation of certain sums over a set of matrices representing Markov types. The enumeration of Markov types is accomplished by reducing it to counting Eulerian paths in a multigraph. In particular, we propose exact and asymptotic formulas for the number of strings of a given Markov type. All of these findings are obtained by analytic and combinatorial tools of analysis of algorithms.