A convolutional single-parity-check concatenated coding scheme forhigh-data-rate applications

The coding scheme uses a set of n convolutional codes multiplexed into an inner code and a (n,n-1) single-parity-check code serving as the outer code. Each of the inner convolutional codes is decoded independently, with maximum-likelihood decoding being achieved using n parallel implementations of the Viterbi algorithm. The Viterbi decoding is followed by additional outer soft-decision single-parity-check decoding. Considering n=12 and the set of short constraint length K=3, rate 1/2 convolutional codes, it is shown that the performance of the concatenated scheme is comparable to the performance of the constraint length K=7, rate 1/2 convolutional code with standard soft-decision Viterbi decoding. Simulation results are presented for the K=3, rate 1/2 as well as for the punctured K=3, rate 2/3 and rate 3/4 inner convolutional codes. The performance of the proposed concatenated scheme using a set of K=7, rate 1/2 inner convolutional codes is given     

Systolic array processing of the Viterbi algorithm

Results on efficient forms of decoding convolutional codes based on the Viterbi algorithm by using systolic arrays are presented. Various properties of convolutional codes are discussed. A technique called strongly connected trellis decoding is introduced to increase the efficient utilization of all the systolic array processors. Issues dealing with the composite branch metric generation, survivor updating, overall system architecture, throughput rate, and computational overhead ratio are also investigated. The scheme is applicable to both hard and soft decoding of any rate b/n convolutional code. It is shown that as the length of the code becomes large, the systolic Viterbi decoder maintains a regular and general interconnection structure as well as moderate throughput rate gain over the sequential Viterbi decoder     

A new Reed-Solomon code decoding algorithm based on Newton'sinterpolation

A Reed-Solomon code decoding algorithm based on Newton's interpolation is presented. This algorithm has as main application fast generalized-minimum-distance decoding of Reed-Solomon codes. It uses a modified Berlekamp-Massey algorithm to perform all necessary generalized-minimum-distance decoding steps in only one run. With a time-domain form of the new decoder the overall asymptotic generalized-minimum-distance decoding complexity becomes O(dn), with n the length and d the distance of the code (including the calculation of all error locations and values). This asymptotic complexity is optimal. Other applications are the possibility of fast decoding of Reed-Solomon codes with adaptive redundancy and a general parallel decoding algorithm with zero delay     

New ternary line codes based on trellis structure

The trellis coding technique is applied to line-coded baseband digital transmission systems. For R=n/n+1(n=1,2,3) coding rates, a new codeword assignment model is proposed to accomplish basic requirements for line coding in which each length n binary data sequence is encoded into a length n+1 ternary (+,0,-) line codeword chosen among the code alphabet with 2ⁿ⁺² elements. Assuming Viterbi decoding, the system error performance is improved by increasing the free Euclidean distance between coded sequences. A new algorithm is given for the calculation of the free distance between line-coded sequences so obtained. For R=1/2 and R=3/4 rates, the analytical error performance upper bounds are derived. The power spectral densities of the new line codes are also calculated and compared with those of known line codes     

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     

On the performance of rate 1/2 convolutional codes with QPSK onRician fading channels

Consideration is given to the bit error probability performance of rate 1/2 convolutional codes in conjunction with quaternary phase shift keying (QPSK) modulation and maximum-likelihood Viterbi decoding on fully interleaved Rician fading channels. Applying the generating function union bounding approach, an asymptotically tight analytic upper bound on the bit error probability performance is developed under the assumption of using the Viterbi decoder with perfect fading amplitude measurement. Bit error probability performance of constraint length K=3-7 codes with QPSK is numerically evaluated using the developed bound. Tightness of the bound is examined by means of computer simulation. The influence of perfect amplitude measurement on the performance of the Viterbi decoder is observed. A performance comparison with rate 1/2 codes with binary phase shift keying (BPSK) is provided     

On the cutoff rate of a discrete memoryless channel with(d, k)-constrained input sequences

The cutoff rate of a discrete memoryless channel whose output sequences are from a (d, k) encoder is investigated. A rational rate (d, k) encoder is considered as a finite state machine and maximum-likelihood decoding is used to compute the cutoff rate. Some commonly used (d, k) codes, such as the rate 1/2 (1, 3) code with a two-state encoder, the IBM rate 2/3 (1, 7) code having a five-state encoder, and the IBM rate 1/2 (2, 7) code with a seven-state encoder, are used to illustrate the cutoff rate computation. Results are presented for both the binary symmetric channel (BSC) and the Gaussian noise channel. The performance of a decoder designed for noiseless transmission of (1, 3) code is compared to that of a maximum-likelihood decoder for the (1, 3) code. It is also shown that for the case of the Gaussian noise channel, a gain of about 1.7 dB in signal-to-noise ratio is possible by using 3-bit soft decisions over hard decisions     

A versatile time-domain Reed-Solomon decoder

A versatile Reed-Solomon (RS) decoder structure based on the time-domain decoding algorithm (transform decoding without transforms) is developed. The algorithm is restructured, and a method is given to decode any RS code generated by any generator polynomial. The main advantage of the decoder structure is its versatility, that is, it can be programmed to decode any Reed-Solomon code defined in Galois field (GF) 2^m with a fixed symbol size m. This decoder can correct errors and erasures for any RS code, including shortened and singly extended codes. It is shown that the decoder has a very simple structure and can be used to design high-speed single-chip VLSI decoders. As an example, a gate-array-based programmable RS decoder is implemented on a single chip. This decoder chip can decode any RS code defined in GF (2⁵) with any code word length and any number of information symbols. The decoder chip is fabricated using low-power 1.5-μ, two-layer-metal, HCMOS technology     

A linear bound for sliding-block decoder window size

The author gives an upper bound on the necessary length of a sliding-block decoder window for finite-state codes from arbitrary n -ary data into any constrained system Σ with capacity at least log(n) presented by a graph G with memory m and anticipation a. Specifically, it is shown that the ACH code construction algorithm can be used to construct a code with a sliding-block decoder at rate t:t and with window length m+a+2t, where t is upper-bounded by a linear function of the number of states of G. It is demonstrated that this is the best one can do in the sense that any general upper bound on the decoder window length for finite-state codes into systems Σ with finite memory must grow at least linearly with the number of states of the graph G presenting Σ     

New array codes for multiple phased burst correction

An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q^p-1), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors     

Decoding spherical codes for the Gaussian channel

A decoding algorithm for permutation codes that is equivalent to maximum-likelihood decoding, but less complex than the correlation decoder, is presented. A general construction for iteratively maximum-likelihood decodable (IMLD) codes is proved and used to construct IMLD codes for every dimension n. D. Slepian (1965) defined permutation modulation codes and presented an efficient algorithm for their decoding. Slepian's decoding scheme is one of the principal components of the permutation code decoding algorithm presented     

A new carrier recovery circuit for land mobile satellitecommunication

A DCF (dual carrier filter) reverse-modulation-type carrier recovery circuit is proposed to achieve a low carrier skipping rate and satisfactory phase tracking performance for coherent detection of PSK (phase shift keying) signals in fast Rician fading channels. The proposed scheme employs both narrow and wide bandwidth carrier filters simultaneously for the reverse-modulation-type carrier recovery circuit. It is clarified by computer simulation that the Pe performance of a QPSK (quadriphase shift keying) modem employing the proposed scheme shows an improvement of 1.5 dB in required E_s/N_O at Pe=10⁴ (after Viterbi decoding (R=7/8, K=7), C/M (direct-to-multipath signal power ratio)=10 dB, interleaving size=64×64), compared with conventional coherent detection employing the reverse modulation tank-limiter scheme or the Costas loop scheme     

Comparison of decoding algorithms for trellis coded modulationusing Viterbi algorithm in the presence of intersymbol interference

The letter describes a comparison of some receiver structures suitable for trellis-coded modulation on channels causing intersymbol interference. Simulation results show that a Viterbi decoder treating trellis coding and intersymbol interference as one compound encoding mechanism yields the best performance, which at P_b=10^-4 is about 6 dB in S/N better than any other receiver structure     

Low-Power State-Parallel Relaxed Adaptive Viterbi Decoder

Although it possesses reduced computational complexity and great power saving potential, conventional adaptive Viterbi algorithm implementations contain a global best survivor path metric search operation that prevents it from being directly implemented in a high-throughput state-parallel decoder. This limitation also incurs power and silicon area overhead. This paper presents a modified adaptive Viterbi algorithm, referred to as the relaxed adaptive Viterbi algorithm, that completely eliminates the global best survivor path metric search operation. A state-parallel decoder VLSI architecture has been developed to implement the relaxed adaptive Viterbi algorithm. Using convolutional code decoding as a test vehicle, we demonstrate that state-parallel relaxed adaptive Viterbi decoders, versus Viterbi counterparts, can achieve significant power savings and modest silicon area reduction, while maintaining almost the same decoding performance and very high throughput     

Runlength-limited codes for mixed-error channels

The mixed-error channel (MC) combines the binary symmetric channel and the peak shift channel. The construction of (d, k) constrained t-MC-error-correcting block codes is described. It is demonstrated that these codes can achieve a code rate close to the ( d, k) capacity. The encoding and decoding procedures are described. The performance of the construction depends on a particular partitioning of (d, k) constrained block codes. This partitioning is discussed and various tables of codes are included. Examples on encoding/decoding and on code performance are given     

On the decoding of algebraic-geometric codes

A decoding algorithm for algebraic-geometric codes arising from arbitrary algebraic curves is presented. This algorithm corrects any number of errors up to [(d-g-1)/2], where d is the designed distance of the code and g is the genus of the curve. The complexity of decoding equals σ(n³) where n is the length of the code. Also presented is a modification of this algorithm, which in the case of elliptic and hyperelliptic curves is able to correct [(d-1)/2] errors. It is shown that for some codes based on plane curves the modified decoding algorithm corrects approximately d/2-g/4 errors. Asymptotically good q-ary codes with a polynomial construction and a polynomial decoding algorithm (for q⩾361 on some segment their parameters are better than the Gilbert-Varshamov bound) are obtained. A family of asymptotically good binary codes with polynomial construction and polynomial decoding is also obtained, whose parameters are better than the Blokh-Zyablov bound on the whole interval 0<σ<1/2     

Closest coset decoding of |u|u+v| codes

The general concept of closest coset decoding (CCD) is presented, and a soft-decoding technique for block codes that is based on partitioning a code into a subcode and its cosets is described. The computational complexity of the CCD algorithm is significantly less than that required if a maximum-likelihood detector (MLD) is used. A set-partitioning procedure and details of the CCD algorithm for soft decoding of |u|u+v| codes are presented. Upper bounds on the bit-error-rate (BER) performance of the proposed algorithm are combined, and numerical results and computer simulation tests for the BER performance of second-order Reed-Muller codes of length 16 and 32 are presented. The algorithm is a suboptimum decoding scheme and, in the range of signal-to-noise-power-density ratios of interest, its BER performance is only a few tenths of a dB inferior to the performance of the MLD for the codes examined     

Analysis of a type II hybrid ARQ scheme with codecombining

An analysis is presented of the selective-repeat type II hybrid AR Q (automatic-repeat-request) scheme, using convolutional coding and exploiting code combining. With code combining, at successive decoding attempts for a data packet, the decoder for error correction operates on a combination of all received sequences for that packet rather than only on the two most recent received ones as in the conventional type II hybrid ARQ scheme. It is shown by means of analysis and computer simulations that with code combining, a significant throughput is achievable, even at very high channel error rates     

Rate-compatible punctured convolutional codes (RCPC codes) andtheir applications

The concept of punctured convolutional codes is extended by punctuating a low-rate 1/N code periodically with period P to obtain a family of codes with rate P/(P+l), where l can be varied between 1 and (N-1)P. A rate-compatibility restriction on the puncturing tables ensures that all code bits of high rate codes are used by the lower-rate codes. This allows transmission of incremental redundancy in ARQ/FEC (automatic repeat request/forward error correction) schemes and continuous rate variation to change from low to high error protection within a data frame. Families of RCPC codes with rates between 8/9 and 1/4 are given for memories M from 3 to 6 (8 to 64 trellis states) together with the relevant distance spectra. These codes are almost as good as the best known general convolutional codes of the respective rates. It is shown that the same Viterbi decoder can be used for all RCPC codes of the same M. the application of RCPC codes to hybrid ARQ/FEC schemes is discussed for Gaussian and Rayleigh fading channels using channel-state information to optimise throughput