The dynamics of group codes: Dual abelian group codes and systems

Fundamental results concerning the dynamics of abelian group codes (behaviors) and their duals are developed. Duals of sequence spaces over locally compact abelian (LCA) groups may be defined via Pontryagin duality; dual group codes are orthogonal subgroups of dual sequence spaces. The dual of a complete code or system is finite, and the dual of a Laurent code or system is (anti-)Laurent. If C and C/sup /spl perp// are dual codes, then the state spaces of C act as the character groups of the state spaces of C/sup /spl perp//. The controllability properties of C are the observability properties of C/sup /spl perp//. In particular, C is (strongly) controllable if and only if C/sup /spl perp// is (strongly) observable, and the controller memory of C is the observer memory of C/sup /spl perp//. The controller granules of C act as the character groups of the observer granules of C/sup /spl perp//. Examples of minimal observer-form encoder and syndrome-former constructions are given. Finally, every observer granule of C is an "end-around" controller granule of C.     

Multilevel construction of block and trellis group codes

The theory of group codes has been shown to be a useful starting point for the construction of good geometrically uniform codes. In this paper we study the problem of building multilevel group codes, i.e., codes obtained combining separate coding at different levels in such a way that the resulting code is a group code. A construction leading to multilevel group codes for semi-direct and direct products is illustrated. The codes that can be obtained in this way are identified. New geometrically uniform Euclidean-space codes obtained from multilevel codes over abelian and nonabelian groups are presented     

MAP algorithms for decoding linear block codes based onsectionalized trellis diagrams

The maximum a posterioriprobability (MAP) algorithm is a trellis-based MAP decoding algorithm. It is the heart of turbo (or iterative) decoding that achieves an error performance near the Shannon limit. Unfortunately, the implementation of this algorithm requires large computation and storage. Furthermore, its forward and backward recursions result in a long decoding delay. For practical applications, this decoding algorithm must be simplifled and its decoding complexity and delay must be reduced. In this paper, the MAP algorithm and its variation's, such as log-MAP and max-log-MAP algorithms, are first applied to sectionalized trellises for linear block codes and carried out as two-stage decodings. Using the structural properties of properly sectionalized trellises, the decoding complexity and delay of the MAP algorithms can be reduced. Computation-wise optimum sectionalizations of a trellis for MAP algorithms are investigated. Also presented in this paper are bidirectional and parallel MAP decodings     

Labelings and encoders with the uniform bit error property withapplications to serially concatenated trellis codes

The well-known uniform error property for signal constellations and codes is extended to encompass information bits. We introduce a class of binary labelings for signal constellations, called bit geometrically uniform (BGU) labelings, for which the uniform bit error property holds, i.e., the bit error probability does not depend on the transmitted signal. Strong connections between the symmetries of constellations and binary Hamming spaces are involved. For block-coded modulation (BCM) and trellis-coded modulation (TCM) Euclidean-space codes, BGU encoders are introduced and studied. The properties of BGU encoders prove quite useful for the analysis and design of codes aimed at minimizing the bit, rather than symbol, error probability. Applications to the analysis and the design of serially concatenated trellis codes are presented, together with a case study which realizes a spectral efficiency of 2 b/s/Hz     

Four state binary QAM trellis code better than known codes

Presents a new one-memory quaternary four-state trellis code, and its four-state binary equivalent code based on a QAM constellation which is 0.52 dB better than the four-state Ungerboeck code.<>     

A Goppa-like bound on the trellis state complexity of algebraic-geometric codes

For a linear code C of length n and dimension k, Wolf (1978) noticed that the trellis state complexity s(C) of C is upper-bounded by w(C):=min(k,n-k). We point out some new lower bounds for s(C). In particular, if C is an algebraic-geometric code, then s(C)/spl ges/w(C)-(g-a), where g is the genus of the underlying curve and a is the abundance of the code.     

Algorithmic construction of trellis codes

An algorithmic approach is proposed whereby long convolutional codes of rate r_c=k/n can easily be constructed for any chosen signal constellation in signal space. These algorithms are iterative, and in each step a number of candidate codes are found which locally maximize the distance (Hamming or Euclidean) between the codewords. The result is not necessarily a free-distance-optimizing code. However, since the construction complexity can be chosen, optimal codes are quite frequently found. The codes ae constructed such that a rapid growth of the column distance is achieved. A method of combining two codes into a single code of twice the constraint length is also presented     

P2 codes: pragmatic trellis codes utilizing puncturedconvolutional codes

A single convolutional code of fixed rate can be punctured to form a class of higher rate convolutional codes. The authors extend this pragmatic approach to the case where the core of the trellis decoder is a Viterbi decoder for a punctured version of the de facto standard, rate 1/2 convolutional code     

Structure, optimization, and realization of FFSK trellis codes

The structure of combinations of (l,k) binary trellis encoders and fast frequency-shift keying (FFSK) modulation is studied. A novel method for the optimization of these combinations is proposed. It is concluded that, regardless of the particular realization, the best combinations can always be obtained by using a so-called matched convolutional code. Optimum FFSK codes of rates 1/2 and 2/3 for up to 64 and 32 states, respectively, are reported. It is shown that the best matched encoders for FFSK modulation are also matched and best for any FFSK-type scheme, where the pulse shape is required to satisfy Nyquist's third criterion     

Erasure-free sequential decoding of trellis codes

An erasure-free sequential decoding algorithm for trellis codes, called the buffer looking algorithm (BLA), is introduced. Several versions of the algorithm can be obtained by choosing certain parameters and selecting a resynchronization scheme. These can be categorized as block decoding or continuous decoding, depending on the resynchronization scheme. Block decoding is guaranteed to resynchronize at the beginning of each block, but suffers some rate loss when the block length is relatively short. The performance of a typical block decoding scheme is analyzed, and we show that significant coding gains over Viterbi decoding can be achieved with much less computational effort. A resynchronization scheme is proposed for continuous sequential decoding. It is shown by analysis and simulation that continuous sequential decoding using this scheme has a high probability of resynchronizing successfully. This new resynchronization scheme solves the rate loss problem resulting from block decoding. The channel cutoff rate, demodulator quantization, and the tail's influence on performance are also discussed. Although this paper considers only the decoding of trellis codes, the algorithm can also be applied to the decoding of convolutional codes     

Differential trellis decoding of convolutional codes

This paper investigates the principle of metric differences for trellis decoding of convolutional codes. Based on this differential method, a new algorithm, referred to as differential trellis decoding (DTD), is proposed. DTD offers an alternative to the conventional “add-compare-select” (ACS) method for implementing the Viterbi algorithm     

Trellis complexity and minimal trellis diagrams of lattices

This paper presents results on trellis complexity and low-complexity trellis diagrams of lattices. We establish constructive upper bounds on the trellis complexity of lattices. These bounds both improve and generalize the similar results of Tarokh and Vardy (see ibid., vol.43, p.1294-1300, 1997). We also construct trellis diagrams with minimum number of paths for some important lattices. Such trellises are called minimal. The constructed trellises, which are novel in many cases, can be employed to efficiently decode the lattices via the Viterbi algorithm. In particular, a general structure for minimal trellis diagrams of D_n lattices is obtained. This structure corresponds to a new code formula for D_n. Moreover, we develop some important duality results which are used in both deriving the upper bounds, and finding the minimal trellises. All the discussions are based on a universal approach to the construction and analysis of trellis diagrams of lattices using their bases     

关于非线性码的格子复杂度

研究了非线性码的格子复杂度.给出了非线性码的维数/长度轮廓的定义,并利用这一定义,将Forney所给出的线性码格子复杂度的新下界推广到了非线性码上去.然后推出了非线性码的Berger-Be′ery上界.     

Limited search trellis decoding of convolutional codes

The least storage and node computation required by a breadth-first tree or trellis decoder that corrects t errors over the binary symmetric channels is calculated. Breadth-first decoders work with code paths of the same length, without backtracking. The Viterbi algorithm is an exhaustive trellis decoder of this type; other schemes look at a subset of the tree or trellis paths. For random tree codes, theorems about the asymptotic number of paths required and their depth are proved. For concrete convolutional codes, the worst case storage for t error sequences is measured. In both cases the optimal decoder storage has the same simple dependence on t. The M algorithm and algorithms proposed by G.J. Foschini (ibid., vol.IT-23, p.605-9, Sept. 1977) and by S.J. Simmons (PhD. diss., Queens Univ., Kingston, Ont., Canada) are optimal, or nearly so; they are all far more efficient than the Viterbi algorithm     

Variable-complexity trellis decoding of binary convolutional codes

Considers trellis decoding of convolutional codes with selectable effort, as measured by decoder complexity. Decoding is described for single parent codes with a variety of complexities, with performance “near” that of the optimal fixed receiver complexity coding system. Effective free distance is examined. Criteria are proposed for ranking parent codes, and some codes found to be best according to the criteria are tabulated, Several codes with effective free distance better than the best code of comparable complexity were found. Asymptotic (high SNR) performance analysis and error propagation are discussed. Simulation results are also provided     

Matrix representation of CPFSK trellis modulation codes

A matrix representation is presented for M-CPFSK signals when the modulation index h=p/q (q>or=M). It simplifies trellis search algorithms that compute minimum distances and other trellis parameters. The matrix representation has been applied to find self-transparent CPFSK trellis modulation codes.<>     

Joint synchronization and demodulation of trellis codes

This paper examines the joint synchronization and detection of Ungerboeck coded modulation. Estimation theory is used to derive a synchronization structure that is efficient in estimating carrier phase and symbol timing. The maximum likelihood receiver generates estimates of carrier phase and timing that are free of data-dependent jitter for any continuous pulse shape. Various feedback schemes to be used with Ungerboeck codes are presented and simulated. Simulations show that efficient estimates of carrier and clock can be found when joint data and parameter estimation of an Ungerboeck coded signal is performed     

Computer design of super-orthogonal space-time trellis codes

Super-orthogonal space-time trellis codes (SOSTTCs) designed by hand can significantly improve the performance of space-time trellis codes. This paper introduces a new representation of SOSTTCs based on a generator matrix that allows a systematic and exhaustive search of all possible codes. This will verify that some of the known codes are optimal, and provides a means to easily implement encoders and decoders with a large number of states without relying on a graphical representation. New codes with up to 256 states that outperform previously known codes are presented     

空时格码迹准则的改进

本文研究空时格码迹设计准则的改进问题.原迹准则的不足在于仅考虑了码的最小迹,故不能有效的选取最优码.针对这一不足,本文首先提出了以迹分布作为衡量码性能主要依据的思路.然而迹分布仍不能完全决定码的性能,于是文中导出了一个新的错误概率上界,并在此基础上又提出了以特征值和方/方和比分布来补充和完善迹分布的思路.最后综合以上两个分布,本文给出了一个改进的空时格码设计准则,并根据这一准则找到了一些新码,仿真结果表明这些新码的性能为目前已知码中最优的.