A procedure is described to produce efficient turbo-code interleavers. It is well suited to the selection of interleavers that produce a large minimum distance for the resulting turbo codes. A feature of these interleavers is that the final state of the two elementary encoders is simultaneously zero. Examples are given and the corresponding codes are simulated. They seem to be among the best ones for rate 1/3 turbo codes.

We give a proof of a theorem on the common divisibility of polynomials and permuted polynomials (over GF(2)) by a polynomial g(x).

One describes procedures to generate the codewords of a Reed-Solomon code over GF(2/sup m/) having all their symbols in a GF(2) subspace of GF(2/sup m/). Some of the described encoders are systematic binary encoders and some are only partly systematic.

Let S(8) denote the set of the eight admissible signals of an 8PSK communication system. The alphabet S(8) is endowed with the structure of Z/sub 8/, the set of integers taken modulo 8, and codes are defined to be Z/sub 8/-submodules of Z/sub 8//sup n/. Three cyclic codes over Z/sub 8/ are then constructed. Their length is equal to 6, 8, and 7, and they, respectively, contain 64, 64, and 512 codewords. The square of their Euclidean minimum distance is equal to 8, 16-4/spl radic/2 and 10-2/spl radic/2, respectively. The size of the codes of length 6 and 7 can be doubled while the Euclidean minimum distance remains the same.>

The connectivity of a two-dimensional radio network as a function of the range of the transmitters is still an open problem. It has bee conjectured that the critical range of this problem is the same as the one for the covering problem. The analysis of the one-dimensional problem makes it clear that situations can exist where these two ranges are different. It is conjectured that the critical ranges of the two-dimensional problems are also different. The author presents results to substantiate this conjecture.>

A modified Hebbian rule using the matrix G=sgn(X/sup T/X) to induce a certain mapping is discussed. This mapping g is specified as soon as one has chosen the m*n matrix X over U to construct G by use of the above expression. The analysis of g relies on simple counting arguments and on the use of Stirling's approximation to obtain asymptotic results.>

Two problems of information transmission on the permuting mailbox (or relay) channel are considered. Such a channel is characterized by the cardinality epsilon of the alphabet and the number b of letters in the mailbox. In the case b=1, an upper bound is obtained on the achievable rate in the jamming situation. In the case epsilon =2, it is proven that time-sharing is not always the best solution when both main users wish to transmit information to a third user.>

The following two problems are dealt with: P1) finding the smallest rate,R, of a binary code of lengthnadmitting a prescribed covering radius\rho n; P2) discovering whether a majority of codes with any rate larger thanRadmits the given covering radius. For the class of unrestricted (nonlinear) codes a solution to both problems is obtained by an elementary averaging argument. The solution to P1 isR = 1 - H(\rho) + O(n^{-1} \log n)and the answer to P2 is positive. As for the more interesting class of linear codes, Goblick's extension method shows that the solution to P1 is the same as in the unrestricted case; in contrast, P2 seems to remain an open question. A simple derivation of Goblick's result is presented, and a discussion is made of the positive conjecture concerning P2 for linear codes.

LetCbe a code of lengthnand rateRover the alphabetA(Q)=\{ \exp (2\pi ir/Q): r=O,1, \cdots ,Q-1\}, and letd(C)be the minimum Euclidean distance ofC. For largen, the lower and upper bounds are obtained in parametric form on the achievable pairs(R, \delta), where\delta = d^{2}(C)/nholds. To obtain these bounds, the arguments leading to the Gilbert bound and the Elias bound, respectively, are applied to the alphabetA(Q). ForQ \rightarrow \infty, they are shown to be expressible in terms of the modified Bessel function of the first kind. The Elias type bound is compared with the Kabatyanskii-Levenshtein (K-L) bound that holds for less restrictive alphabets. It turns out that our upper bound improves the K-L bound for\delta \leq 0.93.

The error correcting capabilities are studied of some binary codes used on channels where both independent and burst errors may occur. The compound distance profile is introduced, and a lower bound on this profile is obtained for a class of modified maximum distance separable codes. Several constructions are presented as an illustration.

For a class of binary systematic codes of lengthnand cardinality2^{k}, including the class of linear(n, k)binary cyclic codes, it is shown that the number of codewords of weight\lfloor \omega n \rfloorcannot be much larger than2^{kH(\omega).

Two classes of multiple-word correcting convolutional encoders are defined and analyzed. We obtain some conditions for these encoders to be noncatastrophic, and we describe ways to check the (word) minimum distance of the generated codes. The first class can easily be analyzed by algebraic means, but the redundancy of the corresponding codes is not arbitrarily iow. The codes generated by the second class of encoders may have a lower redundancy, but their analysis requires the use of a computer program.

Maximum distance separable (MDS) convolutional codes are defined as the row space overF(D)of totally nonsingular polynomial matrices in the indeterminateD. These codes may be used to transmit information onnparallel channels when a temporary or even an infinite break can occur in some of these channels. Their algebraic properties are emphasized, and the relevant parameters are introduced. On this basis two decoding procedures are described. Both procedures correct arbitrarily long error sequences that may occur at the same time in some of thenchannels. Some specific constructions of MDS convolutional codes are presented.

The problem of the explicit construction of encoders achieving Shannon's capacity and admitting a simple decoding algorithm is considered. A solution based on Justesen's idea of variable concatenated codes is given for the case of a symmetric memoryless channel with an input alphabet of prime power order, under the assumption that the information messages are equiprobable. This construction remains good for a nonsymmetric channel provided the encoding rate is smaller than a well-defined "pseudocapacity." In case the channel is regular, it is shown that the error probability after decoding is an exponentially decreasing function of the block length for any encoding rate less than the channel capacity.

A finite-state code (FSC) is the set of output sequences of a finite-state encoder. The case is considered where the period of the eneoder is one and the code is used as an error-correcting code. In this context the Levenshtein distance will measure the discrepancy between an information sequence and its estimate, and the minimum Hamming distance will be taken as the criterion of efficiency. The class of binary autocomplementary FSC's (BAC's) satisfies a lower bound on the minimum Hamming distance that is essentially equivalent to the well-known Gilbert bound for block codes. Examples of good BAC's are provided in the last section.

By use of known bounds on constant-weight binary codes, new uppper bounds are obtained on the cardinality of binary codes correcting asymmetric errors. Some constructions are exhibited that come close to these bounds. For single-error-correcting codes some constructions are derived from the Steiner systemS(5, 6,12), and for double-error-correcting codes some constructions are derived from the Nordstrom-Robinson code.

No abstract

LetMbe a binary autoregressive source to be encoded within a specified Hamming distortion\delta. A binaryn-tuple is called\sigma-central if it is at distance\leq n(\delta + \sigma)from at least2^{nH(\delta - \sigma)}typical sequences produced by the sourceM. It is first shown that, in the region where the Shannon rate-distortion bound is achieved, there exist "good codes" consisting only of\sigma-central words. Next, the characterization problem is studied; the basic conjecture is that a central sequence is well-characterized by its level, which is the Hamming weight of an image sequence. The problem is solved for the memoryless source. In general, ifN(k,r)is defined to be the mean number of typicaln-tuples at distance\leq r = n \deltafrom then-tuples of levelk=n \xi, then it is shown thatn^{-l} \log N(k,r)becomes arbitrarily close toH(\delta)for an explicitly determined unique value of\xi.

Three binary linear codes of length 27 and 28 are described. They contain more vectors than any previously known codes with the same length and minimum distance.

A specific criterion is presented to check the noncatastrophic property of encoders for a convolutional code with a certain type of automorphism. In most cases to which the criterion is applicable, only a very small amount of computation is required.

Binary causal sliding block encoders with feedback are described. They are shown to provide an optimum causal encoding of the symmetric memoryless source. Their rate-distortion function is also obtained for the symmetric first-order Markov source.

A sliding block encoding scheme easily derivable from block encoding is presented. It is shown to perform arbitrarily close to the rate distortion function when the source is stationary and memoryless.

The encoded sequences of an(n,k)convolutional code are treated as sequences of polynomials in the ring of polynomials moduloX^{n} - 1. Any such sequence can then be written as a power series in two variablesw(X,D), where the polynomial coefficient ofD^{j}is the "word" at time unitjin the sequence. Necessary and sufficient conditions on the ring "multiplication" for the set of such sequences so that the set becomes alinear associative algebra are derived. Cyclic convolutional codes (CCC's)are then defined to be left ideals in this algebra. A canonical decomposition of a CCC into minimal ideals is given which illuminates the cyclic structure. As an application of the ideas in the paper, a number of CCC's with large free distance are constructed.

A construction is given for low rate cyclic convolutional codes with optimal free distance. These codes are of the alternating maximum length sequence type.

The class of alternating cyclic maximum-length sequence convolutional codes is defined, and all optimal codes are constructed for(n,k) =

A stochastic model is described for the decoder of an optimal burst-correcting convolutional code. From this model, an upper bound is obtained for\bar{p}, the error probability per word after decoding.

An algorithm has been devised to find typeB_1optimal convolutional codes. All typeB_1optimal