Constructions and bounds for systematic tEC/AUED codes

Several methods of constructing systematic t-error correcting/all unidirectional error-detecting codes are described. These codes can be constructed by adding a tail to a linear t-error correcting code, but other constructions presented are more of an ad hoc nature. These codes will often be found as suitably chosen subsets of nonsystematic tEC/AUED codes. Further bounds on the word length of systematic tEC/AUED codes are derived, and extensive tables are given     

New multilevel codes over GF(q)

Set partitioning is applied to multidimensional signal spaces over GF(q), i.e., GFⁿ¹(q) (n1⩽q ), and it is shown how to construct both multilevel block codes and multilevel trellis codes over GF(q). Multilevel (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d_min⩾d are presented. These codes use Reed-Solomon codes as component codes. Longer multilevel block codes are also constructed using q-ary block codes with block length longer than q+1 as component codes. Some quaternary multilevel block codes are presented with the same length and number of information symbols as, but larger distance than, the best previously known quaternary one-level block codes. It is proved that if all the component block codes are linear. the multilevel block code is also linear. Low-rate q-ary convolutional codes, word-error-correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multilevel trellis codes over GF(q) or binary-to-q-ary trellis codes     

A coding scheme for m-out-of-n codes

A scheme for the construction of m-out-of-n codes based on the arithmetic coding technique is described. For appropriate values of n, k, and m, the scheme can be used to construct an (n,k) block code in which all the codewords are of weight m. Such codes are useful, for example, in providing perfect error detection capability in asymmetric channels such as optical communication links and laser disks. The encoding and decoding algorithms of the scheme perform simple arithmetic operations recursively, thereby facilitating the construction of codes with relatively long block sizes. The scheme also allows the construction of optimal or nearly optimal m-out-of-n codes for a wide range of block sizes limited only by the arithmetic precision used     

Optimal type-B1 convolutional codes of rate 4/5

It is reported that two optimal type-B1 burst correcting convolutional codes of rate 4/5 were found by computer search. The B ₀ matrices of these codes are given. In octal, the columns are written as (53,357,756,1555,1000) and (53,357,1555,1203,1000), respectively     

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     

Constructions of rate (n-1)/n puncturedconvolutional codes with minimum required SNR criterion

Rate (n-1)/n punctured convolutional codes (n up to 10 and memory length up to 8) are constructed which minimize the required signal-to-noise ratio (SNR) for a bit-error rate (BER) of 10^-9 with and without the restriction of using only four different code generators. Many of these codes improve the free distance and reduce the required SNR more than half a decibel over previously reported codes with the same parameters. This is equivalent to reducing the decoder complexity by one half for the same performance. These codes have many potential applications in systems that require performance improvements with little room for coding overhead     

Construction of t-EC/AUED codes

A t-EC/AUED code is constructed by appending a single check symbol from an alphabet S to each word of an n-bit binary t-EC code of even weight. Conditions are derived for the construction of S and a procedure is given which, for some values of t, n, leads to codes with fewer check bits than known codes with equivalent properties     

Some rate 1/3 and 1/4 binary convolutional codes with an optimum distance profile (Corresp.)

A tabulation of binary systematic convolutional codes with an optimum distance profile for rates1/3and1/4is given. A number of short rate1/3binary nonsystematic convolutional codes are listed. These latter codes are simultaneously optimal for the following distance measures: distance profile, minimum distance, and free distance; they appear attractive for use with Viterbi decoders. Comparisons with previously known codes are made.     

On (k, t)-subnormal covering codes

The concept of a (k, t)-subnormal covering code is defined. It is discussed how an amalgamated-direct-sumlike construction can be used to combine such codes. The existence of optimal (q, n, M) 1 codes C is discussed such that by puncturing the first coordinate of C one obtains a code with (q, 1)-subnorm 2     

Short convolutional codes with maximal free distance for rates 1/2, 1/3, and 1/4 (Corresp.)

This paper gives a tabulation of binary convolutional codes with maximum free distance for ratesfrac{1}{2}, frac{1}{3}, andfrac{1}{4}for all constraint lengths (measured in information digits)nuup to and includingnu = 14. These codes should be of practical interest in connection with Viterbi decoders.     

Optimum parameter combinations for multi-h phase codes

It has been believed that the superiority of multi-h phase codes over constant-h continuous-phase frequency shift keying (CPFSK) schemes is based entirely on the longer temporal separation of any two signal paths. This assumption forces the number of states in the receiver to be lower bounded and requires a fast processor in the receiver. Counterexamples to this common belief are presented as well as results of a systematic search for good multi-h codes for a given bandwidth and complexity constraints. It is shown that quaternary multi-h codes exist for which the first merge of the phase paths in the phase tree is not delayed as compared to the CPFSK scheme, yet which still offer a significant coding gain over the corresponding CPFSK signals. Some quaternary and octal multi-h codes are found with large minimum distance values and a smaller number of receiver states than those known previously     

'Diffuse' threshold decodable rate 1/2 convolutional codes

This paper shows the existence (by construction) of ratefrac{1}{2}convolutional codes that correct bursts of lengthBortrandom errors. The codes have memory length and guard space requirements that are asymptotically4Band minimal effective length. Kohlenberg introduced the term "diffuse code" for his two random-error or single-burst error-correcting codes with minimal effective length and both a memory and guard-space requirement of3B + 1. To this point, there does not seem to be any procedure for finding codes with minimal effective length and guard space requirements asymptotically3B.     

Improved rate 1/4 convolutional codes

The performance of parallel architectures for generating rate 1/4 high constraint length convolutional codes is examined via information weight distributions. It is found that these codes offer a significant decoding advantage, while having a comparable bit error rate (BER) performance to classical codes     

Rate-1/2 component codes for nonbinary turbo codes

The iterative decoding structure and component maximum a posteriori decoders used for decoding binary concatenated codes can be extended to the nonbinary domain. This paper considers turbo codes over nonbinary rings, specifically ternary, quaternary, penternary, hexernary, and octernary codes. The best rate-1/2 component codes are determined using a practical search algorithm. The performance of the resulting rate-1/3 turbo codes on an additive white Gaussian noise channel using q-ary phase-shift keying modulation is given.     

Block-coded M-PSK modulation over GF(M)

Channel codes where the redundancy is obtained not from parity symbols, but from expanding the channel signal-set, are addressed. They were initially proposed by G. Ungerboeck (1982) using a convolutional code. Here, a block coding approach is given. Rate m/(m+1) coded 2^m+1-ary phase-shift keying (PSK) is considered. The expanded signal-set is given the structure of a finite field. The code is defined by a square nonsingular circulant generator matrix over the field. Binary data are mapped on a dataword, of the same length as the codewords, over an additive subgroup of the field. The codes using trellises are described, and then the Viterbi algorithm for decoding is applied. The asymptotic coding gain ranges from 1.8 to 6.0 dB for QPSK going from blocklength 3 to 12. For 8-PSK, the gain is from 0.7 to 3.0 dB with blocklength 4 to 8. With only four states in the trellis, codes of any length for QPSK and 8-PSK are constructed, each having an asymptotic coding gain of 3.0 dB. Simulation results are presented. It is found that the bit-error rate performance at moderate signal-to-noise ratios is sensitive to the number of nearest and next-nearest neighbors     

A note on D-ary Huffman codes

An upper bound on the redundancy of D-ary Huffman codes in terms of the probability p₁ of the most likely source letter is provided. For large values of p₁, the bound improves the one given by R.G. Gallager (1978). Additionally, some results known for the binary case (D=2) are extended to arbitrary D-ary Huffman codes. As a consequence, a tight lower bound that corrects a bound recently proposed by J.D. Golic and M.M. Obradovic (1987) is derived     

On the structure of rate1/nconvolutional codes

We show what choice there is in assigning output digits to transitions of a binary rate1/ncode trellis so that the latter will correspond to a convolutional code. We then prove that in any ratefrac{1}{2}noncatastrophic code of constraint lengthupsiloneach binary sequence of length2j(1 leq j leq upsilon - 1)is associated with exactly2^{upsilon -j -1}distinct pathsjbranches long. As a consequence of the above properties nondegenerate codes with branch complementarity are fully determined by the topological relationship of the trellis transitions associated with output pairs 00. Finally, we derive a new upper bound on free distance of rate1/nconvolutional codes and use our results to determine the length of the largest input sequence that can conceivably result in an output whose weight is     

The (d,k) subcode of a linear block code

A simple technique employing linear block codes to construct (d,k) error-correcting block codes is considered. This scheme allows asymptotically reliable transmission at rate R over a BSC channel with capacity C_BSC provided R ⩽C_d,k-(1+C_BSC), where C_d,k is the maximum entropy of a (d,k ) source. For the same error-correcting capability, the loss in code rate incurred by a multiple-error correcting (d,k) code resulting from this scheme is no greater than that incurred by the parent linear block code. The single-error correcting code is asymptotically optimal. A modification allows the correction of single bit-shaft errors as well. Decoding can be accomplished using off-the-shelf decoders. A systematic (but suboptimal) encoding scheme and detailed case studies are provided