Trellis Encoding of memoryless discrete-time sources with a fidelity criterion

For memoryless discrete-time sources and bounded single-letter distortion measures, we derive a bound on the average per-letter distortion achievable by a trellis source code of fixed constraint length. For any fixed code rate greater thanR(D^{ast}), the rate-distortion function atD^{ast}, this bound decreases towardD^{ast}exponentially with constraint length.     

A bound on lightweight sequences with application to definite decoding (Corresp.)

It is shown that the numberMof binary-valuedn-tuples having fractional weightdeltaor less,0 < delta leq frac{1}{3}, such that no twon-tuples agree in anyLconsecutive positions, is bounded by2^{2LH(delta)+1}. A set ofn-tuples is constructed to show that this bound is not likely to be improved upon by any significant factor. This bound is used to show that the ratiod_{DD}/n_{DD}of definite-decoding minimum distance to definite-decoding constraint length is lower bounded byH^{-l}[frac{1}{6} cdot (1 - R)/ (1+R)]asn_{DD}grows without bound.     

Asymptotic performance and complexity of a coding scheme for memoryless channels

The purpose of this paper is to show that decoding complexity need not grow exponentially with the code block length at rates close to channel capacity and also to show the expediency of the approach of imbedding codes in each other. It is demonstrated that it is possible to communicate over a memoryless channel of capacityCat any rateR < Cwith a probability of error of less than2^{-E(R)nu}, E(R) > 0, per block of a length approximately proportional tonu^{2}and with a computational decoding complexity per digit which is asymptotically proportional tonu^{alpha}whennuis large,nu^{alpha}being finite forR < C.(alpha rightarrow mbox{as} R rightarrow C, alpha rightarrow 2 mbox{as} R rightarrow 0).     

Analysis of recurrent codes

A definition of a recurrent code is given in a framework which renders it amenable to mathematical analysis. Recurrent codes for both independent and burst errors are considered, and a necessary and sufficient condition for either type of error correction is established. For burst-error-correcting codes, the problem treated is (for a fixed burst length and redundancy) the minimization of the error-free distance ("guard space") required between bursts. A lower bound is obtained on the guard space, and in certain cases, codes which realize this bound are given. A general code which is close to the lower bound in many cases is also given. For independent errors, a code which will correct any error, provided that no consecutive "n" positions have more than "e" digits in error, is discussed. Fore = 1, a necessary and sufficient condition onnis derived; fore > 1, a lower bound onnis obtained, and for the case of redundancy1/2, an upper bound onnis also derived.     

A weight distribution bound for linear codes

A linear code of block length n possessing minimum weight d has one code word of weight zero, and no other code words of weight less thand. The weight distribution of the code is given by the set of allW(j), d leq j leq n, describing the number of code words having a weight of exactlyj. Exact weight distributions are known for only a handful of linear codes. This paper presents an explicit upper bound uponW(j)as a function ofn, d, andj. The bound has general applicability to all linear codes.     

Bounds for codes over the unit circle

LetCbe a code of lengthnand rateRover the alphabetA(Q)={ exp (2pi 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), wheredelta = 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 fordelta leq 0.93.     

A self-dual even (96, 48, 16) code (Corresp.)

IfC_1, C_2are two codes of the same length, letC_1 neq C_2 = {(alpha + eta,beta + eta, alpha + beta + eta) mid alpha, beta in C_1, eta in C_2}. TakingC_1andC_2to be two extended quadratic residue codes of length 32, it is shown thatC_1 neq C_2is a (96,48,16) self-dual even code with all weights divisible by 4.     

New short constraint length convolutional code constructions for selected rational rates (Corresp.)

New short constraint length convolutional code constructions are tabulated for ratesR=(n-k)/n, k=1,2, cdots ,n-1withn=2, 3,cdots ,8, and for constraint lengthsK=3,4, cdots,8. These codes have been determined by iterative search based upon a criterion of optimizing the free distance profile. Specifically, these codes maximize the free distanced_{f}while minimizing the number of adversaries in the distance, or weight, spectrum. In several instances we demonstrate the superiority of these codes over previously published code constructions at the same rate and constraint length. These codes are expected to have a number of applications, including combined source-channel coding schemes as well as coding for burst or impulsive noise channels.     

A note on extended quadratic residue codes overGF(9)and their ternary images (Corresp.)

We discuss[2(p + 1), p + 1]double circulant codes which are the ternary images of the[p + 1,(p + 1)/2]extended quadratic residue codes over GF(9). Herepis a prime of the formp = 12k pm 5. As a special result we obtain a[64, 32,18]ternary self-dual code which is the largest known code meeting the bound of Mallows and Sloane.     

Computational moments for sequential decoding of convolutional codes

The long standing conjecture is established that, for a discrete memoryless channel, there exists a linear convolutional code with infinite constraint length such that therhoth(rho geq 1)moment of the number ofF-hypotheses in the Fano sequential decoding algorithm is bounded, provided that the transmission rateRis less thanE_{0}( rho,r)/ rho, wherer(x)is a distribution over the channel input alphabet. A new concept of independence for a finite set of message sequences plays an essential role in averaging a product of likelihood ratios over an ensemble of code sequences in a code tree. A simpler version of the method can be applied to the proof of the conjecture for general tree codes.     

A block code for noiseless asynchronous multiple-access OR channel (Corresp.)

A Mock code for the noiseless multiple access OR channel is introduced. An exponential error bound is proven if the sum of the equal code rates of the asynchronousTusers is less thanln 2.     

Some long cyclic linear binary codes are not so bad

We show that when an inner linear cyclic binary code which has an irreducible check polynomial is concatenated with an appropriately chosen maximal-distance-separable outer code, then the overall code is cyclic OverGF(2). Using this theorem, we construct a number of linear cyclic binary codes which are better than any previously known. In particular, by taking the inner code to be a quadratic residue code, we obtain linear cyclic binary codes of lengthN, rateR, and distanceD geq (1 - 2R)N/ sqrt{2 log N}, which compares favorably with the BCH distanceD sim (2 ln R^{-1})N/log N, although it still fails to achieve the linear growth of distance with block length which is possible with noncyclic linear concatenated codes. While this construction yields many codes, including several with block lengths greater than10^{10^5}, we have not been able to prove that there are arbitrarily long codes of this type without invoking the Riemann hypothesis or the revised Artin conjecture, as the existence of long codes of our type is equivalent to the existence of large primespfor which the index of 2 is(p - 1)/2.     

Distance Bounds for an Ensemble of LDPC Convolutional Codes

An ensemble of $(J,K)$ -regular low-density parity- check (LDPC) convolutional codes is introduced and existence-type lower bounds on the minimum distance $d _ {rm L}$ of code segments of finite length $L$ and on the free distance $d _{rm free}$ are derived. For sufficiently large constraint lengths $nu$ , the distances are shown to grow linearly with $nu$ and the ratio $d_ {rm L}/nu$ approaches the ratio $d _{ {rm free}}/nu$ for large $L$ . Moreover, the ratio of free distance to constraint length is several times larger than the ratio of minimum distance to block length for Gallager's ensemble of $(J,K)$-regular LDPC block codes.      

On certain projective geometry codes (Corresp.)

LetVbe an(n, k, d)binary projective geometry code withn = (q^{m}-1)/(q - 1), q = 2^{s}, andd geq [(q^{m-r}-1)/(q - 1)] + 1. This code isr-step majority-logic decodable. With reference to the GF(q^{m}) = {0, 1, alpha , alpha^{2} , cdots , alpha^{n(q-1)-1} }, the generator polynomialg(X), ofV, hasalpha^{nu}as a root if and only ifnuhas the formnu = i(q - 1)andmax_{0 leq l < s} W_{q}(2^{l} nu) leq (m - r - 1)(q - 1), whereW_{q}(x)indicates the weight of the radix-qrepresentation of the numberx. LetSbe the set of nonzero numbersnu, such thatalpha^{nu}is a root ofg(X). LetC_{1}, C_{2}, cdots, C_{nu}be the cyclotomic cosets such thatSis the union of these cosets. It is clear that the process of findingg(X)becomes simpler if we can find a representative from eachC_{i}, since we can then refer to a table, of irreducible factors, as given by, say, Peterson and Weldon. In this correspondence it was determined that the coset representatives for the cases ofm-r = 2, withs = 2, 3, andm-r=3, withs=2.     

Further classifications of codes meeting the Griesmer bound (Corresp.)

For any(n, k, d)binary linear code, the Griesmer bound says thatn geq sum_{i=0}^{k-1} lceil d/2^{i} rceil, wherelceil x rceildenotes the smallest integergeq x. We consider codes meeting the Griesmer bound with equality. These codes have parametersleft( s(2^{k} - 1) - sum_{i=1}^{p} (2^{u_{i}} - 1), k, s2^{k-1} - sum_{i=1}^{p} 2^{u_{i} -1} right), wherek > u_{1} > cdots > u_{p} geq 1. We characterize all such codes whenp = 2oru_{i-1}-u_{i} geq 2for2 leq i leq p.     

Correction of synchronization errors with burst-error-correcting cyclic codes

It is shown that every linear cyclicb-burst-error-correcting code over any finite field can be modified to correct up to(b-2)symbols of synchronization slippage without additional redundancy, while maintaining its additive error-correcting capability in the absence of synchronization errors. For codes that are interleaved to a degreem, the synchronization error-correcting capability ism (b-1) - 1symbols, whereb geq 3is the length of the burst each subcode corrects. This technique gives an optimum burst-error-correcting code a synchronization error-corecfing capability that is only one symbol short of the known upper bound and is hence asymptotically optimal. Moreover, the implementation is very simple.     

Complexity of acceptors for prefix codes (Corresp.)

For a given finite set of messages and their assigned probabilities, Huffman's procedure gives a method of computing a length set (a set of codeword lengths) that is optimal in the sense that the average word length is minimized. Corresponding to a particular length set, however, there may be more than one code. LetL(n)consist of all length sets with largest termn, and, for anyell in L(n), let{cal S}( ell)be the smallest number of states in any finite-state acceptor which accepts a set of codewords with length setell. It is shown that, for alln > 1,n^{2}/(16 log_{2} n) leq max {cal S}(ell) leq 0(n^{2}).ell in L(n)     

Duadic Codes

A new family of binary cyclic(n,(n + 1)/2)and(n,(n - 1)/2)codes are introduced, which include quadratic residue (QR) codes whennis prime. These codes are defined in terms of their idempotent generators, and they exist for all oddn = p_{1}^{a_{1}} p_{2}^{a_{2}} cdots p_{r}^{a_{r}}where eachp_{i}is a primeequiv pm 1 pmod{8}. Dual codes are identified. The minimum odd weight of a duadic(n,(n + 1)/2)code satisfies a square root bound. When equality holds in the sharper form of this bound, vectors of minimum weight hold a projective plane. The unique projective plane of order 8 is held by the minimum weight vectors in two inequivalent(73,37,9)duadic codes. All duadic codes of length less than127are identified, and the minimum weights of their extensions are given. One of the duadic codes of length113has greater minimum weight than the QR code of that length.     

Gleason's theorem on self-dual codes

The weight enumerator of a code is the polynomial begin{equation} W(x,y)= sum_{r=0}^n A_r x^{n-r} y^r, end{equation} wherendenotes the block length andA_r, denotes the number of codewords of weightr. LetCbe a self-dual code overGF(q)in which every weight is divisible byc. Then Gleason's theorem states that 1) ifq= 2 andc= 2, the weight enumerator ofCis a sum of products of the polynomialsx^2 + y^2andx^2y^2 (x^2 - y^2 )^2ifq= 2 andc= 4, the weight enumerator is a sum of products ofx^8 + 14x^4 y^4 + y^8andx^4 y^4 (x^4 - y^4)^4; and 3) ifq= 3 andc= 3, the weight enumerator is a sum of products ofx^4 + 8xy^3andy^3(x^3 - y^3)^3. In this paper we give several proofs of Gleason's theorem.