Linear uniform codes

Linear uniform codes are linear codes with minimum distance equal to average distance, and hence are optimum from minimum-distance point of view. A unified approach to block and convolutional codes is taken, leading to a simpler encoder for convolutional uniform codes.     

Binary uniform codes

An algorithm to construct all linear binary uniform codes is given. The algorithm makes use of block codes due to Macdonald.     

Punctured uniform codes

The structure of a uniform convolutional code, i.e., a code whose average distance is equal to its minimum distance, is examined, and results in a parity equation lattice. From this lattice, punctured uniform codes, i.e., uniform codes with parity bits deleted, are constructed, which can be threshold decoded and have limited error propagation. An "optimum" deletion sequence is provided. Some of the punctured uniform codes are optimal from a minimum-distance view point.     

Geometrically uniform multidimensional PSK trellis codes

The recently developed group theory of geometrically uniform trellis-coded modulation (TCM) is applied to the case of multidimensional PSK signal constellations. A general algorithm to construct geometrically uniform partitions of signal constellations is described and applied to multidimensional PSK signals. Examples of application to TCM employing 3*8 PSK signalling are presented.<>     

Generalized pairwise complementary codes with set-wise uniform interference-free windows

This paper introduces an approach to generate generalized pairwise complementary (GPC) codes, which offer a uniform interference free windows (IFWs) across the entire code set. The GPC codes work in pairs and can fit extremely power efficient quadrature carrier modems. The characteristic features of the GPC codes include: the set size is 2K, the processing gain is 4NK, and the IFW's width is 8N identically for all codes in a set, where K is the times to perform Walsh-Hadamard expansions and N is element code length of seed complementary codes. Therefore, by using different N, the IFW width of a GPC code set can be adjusted with its set size unchanged. Each GPC code set consists of two code groups, with each having K codes, and they have sparsely and uniformly distributed autocorrelation side lobes and cross-correlation levels outside the IFWs.     

A new decoding algorithm for geometrically uniform trellis codes

A new decoding algorithm for geometrically uniform trellis codes is presented. The group structure of the codes is exploited in order to improve the decoding process. Analytical bounds to the algorithm performance and to its computational complexity are derived. The algorithm complexity does not depend on the number of states of the trellis describing the code. Extensive simulations yield results on the algorithm performance and complexity, and permit a comparison with the Viterbi algorithm and the sequential Fano algorithm     

The serial concatenation of rate-1 codes through uniform random interleavers

Until the analysis of repeat accumulate codes by Divsalar et al. (1998), few people would have guessed that simple rate-1 codes could play a crucial role in the construction of "good" binary codes. We construct "good" binary linear block codes at any rate r<1 by serially concatenating an arbitrary outer code of rate r with a large number of rate-1 inner codes through uniform random interleavers. We derive the average output weight enumerator (WE) for this ensemble in the limit as the number of inner codes goes to infinity. Using a probabilistic upper bound on the minimum distance, we prove that long codes from this ensemble will achieve the Gilbert-Varshamov (1952) bound with high probability. Numerical evaluation of the minimum distance shows that the asymptotic bound can be achieved with a small number of inner codes. In essence, this construction produces codes with good distance properties which are also compatible with iterative "turbo" style decoding. For selected codes, we also present bounds on the probability of maximum-likelihood decoding (MLD) error and simulation results for the probability of iterative decoding error.     

Distance properties of expander codes

The minimum distance of some families of expander codes is studied, as well as some related families of codes defined on bipartite graphs. The weight spectrum and the minimum distance of a random ensemble of such codes are computed and it is shown that it sometimes meets the Gilbert-Varshamov (GV) bound. A lower bound on the minimum distances of constructive families of expander codes is derived. The relative minimum distance of the expander code is shown to exceed the product bound, i.e., the quantity /spl delta//sub 0//spl delta//sub 1/ where /spl delta//sub 0/ and /spl delta//sub 1/ are the minimum relative distances of the constituent codes. As a consequence of this, a polynomially constructible family of expander codes is obtained whose relative distance exceeds the Zyablov bound on the distance of serial concatenations.     

Geometrically uniform TCM codes over groups based on L×MPSKconstellations

The theory of geometrically uniform signal sets and codes over groups is applied to the case of L×MPSK constellations. Conditions for rotational invariance of group codes are discussed. The tables of geometrically uniform partitions found in Benedetto et al. (1993) are used to construct good geometrically uniform trellis codes over nonbinary Abelian groups. The present authors consider L×4PSK and L×8PSK constellations used to transmit information rates of 1 and 2 bit/two dimensions, respectively; and present tables of good codes over generating groups (Z4)^L and (Z8)^L,for L ranging from 1 to 4. In most cases, they improve the tables of codes known so far. Moreover, the geometrical uniformity of codes allows a very easy performance evaluation, so that the authors also present a complete set of curves of error event probability for the obtained codes     

Geometrically uniform partitions of L×MPSK constellations andrelated binary trellis codes

The theory of geometrically uniform trellis codes is applied to the case of multidimensional PSK (phase shift keying) constellations. The symmetry group of an L×MPSK (M-ary PSK) constellation is completely characterized. Conditions for rotational invariance of geometrically uniform partitions of a signal constellation are given. Through suitable algorithms, geometrically uniform partitions of L×MPSK (M=4,8,16 and L=1,2,3,4) constellations are found, which present good characteristics in terms of the set of distances at a given partition level, the maximum obtainable rotational invariance, and the isomorphism of the quotient group associated with the partition. These partitions are used as starting points in a search for good geometrically uniform trellis codes based on binary convolutional codes     

Several properties of short LDPC codes

In this paper, we present several properties on minimum distance(d/sub min/) and girth(G/sub min/) in Tanner graphs for low-density parity-check (LDPC) codes with small left degrees. We show that the distance growth of (2, 4) LDPC codes is too slow to achieve the desired performance. We further give a tight upper bound on the maximum possible girth. The numerical results show that codes with large G/sub min/ could outperform the average performance of regular ensembles of the LDPC codes over binary symmetric channels. The same codes perform about 1.5 dB away from the sphere-packing bound on additive white Gaussian noise channels.     

Geometrical properties of orthogonal space-time codes

We discuss the geometrical properties of a transmission scheme with orthogonal space-time codes. In particular, we show that the transmission channel can be interpreted as the rotation of a vector of transmit symbols in an Euclidean space, together with an attenuation and additive noise. We show that the receiver - as intuitively obvious - essentially has to perform a back-rotation. This geometrical interpretation applies to real vector spaces of signals, i.e., the complex transmit and receive symbols have to be split up into their real and imaginary parts.     

Some basic properties of fix-free codes

A variable-length code is a fix-free code if no codeword is a prefix or a suffix of any other codeword. This class of codes is applied to speed up the decoding process, for the decoder can decode from both sides of the compressed file simultaneously. We study some basic properties of fix-free codes. We prove a sufficient and a necessary condition for the existence of fix-free codes, and we obtain some new upper bounds on the redundancy of optimal fix-free codes     

Generation of codes with good autocorrelation properties

The letter describes a conceptually simple method of generating impulse equivalent burst and cyclic codes, using an all-pass autoregressive moving average (ARMA) filter. These infinite impulse response burst codes may be converted into cyclic codes of arbitrary length, while retaining their low autocorrelation time sidelobe performance. Their extension to orthogonal coding is explored.     

Using partial unit memory codes to improve distance properties of woven turbo codes

Partial unit memory (PUM) codes are reputed for their excellent distance properties and lower decoding complexity compared to equivalent convolutional codes. Woven turbo codes (WTCs) are constructed, which outperform turbo codes, using component PUM codes. Simulation results confirm that WTCs based on PUM codes outperform those based on equivalent convolutional codes, as reflected by their respective minimum distances, which is also calculated.     

System-theoretic properties of convolutional codes over rings

Convolutional codes over rings are particularly suitable for representing codes over phase-modulation signals. In order to develop a complete structural analysis of this class of codes, it is necessary to study rational matrices over rings, which constitutes the generator matrices (encoders) for such convolutional codes. Noncatastrophic, minimal, systematic, and basic generator matrices are introduced and characterized by using a canonical form for polynomial matrices over rings. Finally, some classes of convolutional codes, defined according to the generator matrix they admit, are introduced and analyzed from a system-theoretic point of view     

Combinatorial properties of frameproof and traceability codes

In order to protect copyrighted material, codes may be embedded in the content or codes may be associated with the keys used to recover the content. Codes can offer protection by providing some form of traceability (TA) for pirated data. Several researchers have studied different notions of TA and related concepts in previous years. “Strong” versions of TA allow at least one member of a coalition that constructs a “pirate decoder” to be traced. Weaker versions of this concept ensure that no coalition can “frame” a disjoint user or group of users. All these concepts can be formulated as codes having certain combinatorial properties. We study the relationships between the various notions, and we discuss equivalent formulations using structures such as perfect hash families. We use methods from combinatorics and coding theory to provide bounds (necessary conditions) and constructions (sufficient conditions) for the objects of interest     

Polyphase codes with good nonperiodic correlation properties

N-phase Codes are described which have an autocorrelation function with one main peak and very small side peaks. WithNphases anN^{2}long pulse sequence is generated. Properties have been verified forNup to8and a rule for main peak-to-side-peak ratio is conjectured for largerN. ForNgreater than5. the ratio is substantially better than the best ratios which have been shown for binary bipolar codes. Doppler shift effects appear to be similar to those of linear FM radar pulse compression.     

On the Hamming distance properties of group codes

Under certain mild conditions, the minimum Hamming distance D of an (N, K, D) group code C over a non-abelian group G is bounded by D⩽N -2K+2 if K⩽N/2, and is equal to 1 if K>N/2. Consequently, there exists no (N, K, N-K+1) group code C over an non-abelian group G if 1<K<N. Moreover, any normal code C with a non-abelian output space has minimum Hamming distance equal to D=1. These results follow from the fact that non-abelian groups have nontrivial commutator subgroups. Finally, if C is an (N, K, D) group code over an abelian group G that is not elementary abelian, then there exists an (N, K, D) group code over a smaller elementary abelian group G'. Thus, a group code over a general group G cannot have better parameters than a conventional linear code over a field of the same size as G     

Covering properties of convolutional codes and associated lattices

The paper describes Markov methods for analyzing the expected and worst case performance of sequence-based methods of quantization. We suppose that the quantization algorithm is dynamic programming, where the current step depends on a vector of path metrics, which we call a metric function. Our principal objective is a concise representation of these metric functions and the possible trajectories of the dynamic programming algorithm. We shall consider quantization of equiprobable binary data using a convolutional code. Here the additive group of the code splits the set of metric functions into a finite collection of subsets. The subsets form the vertices of a directed graph, where edges are labeled by aggregate incremental increases in mean squared error (MSE). Paths in this graph correspond both to trajectories of the Viterbi algorithm and to cosets of the code. For the rate 1/2 convolutional code [1+D², 1+D+D²], this graph has only nine vertices. In this case it is particularly simple to calculate per dimension expected and worst case MSE, and performance is slightly better than the binary [24, 12] Golay code. Our methods also apply to quantization of arbitrary symmetric probability distributions on [0, 1] using convolutional codes. For the uniform distribution on [0, 1], the expected MSE is the second moment of the “Voronoi region” of an infinite-dimensional lattice determined by the convolutional code. It may also be interpreted as an increase in the reliability of a transmission scheme obtained by nonequiprobable signaling. For certain convolutional codes we obtain a formula for expected MSE that depends only on the distribution of differences for a single pair of path metrics