Low-density parity-check (LDPC) codes are serious contenders to turbo codes in terms of decoding performance. One of the main problems is to give an explicit construction of such codes whose Tanner graphs have known girth. For a prime power q and m/spl ges/2, Lazebnik and Ustimenko construct a q-regular bipartite graph D(m,q) on 2q/sup m/ vertices, which has girth at least 2/spl lceil/m/2/spl rceil/+4. We regard these graphs as Tanner graphs of binary codes LU(m,q). We can determine the dimension and minimum weight of LU(2,q), and show that the weight of its minimum stopping set is at least q+2 for q odd and exactly q+2 for q even. We know that D(2,q) has girth 6 and diameter 4, whereas D(3,q) has girth 8 and diameter 6. We prove that for an odd prime p, LU(3,p) is a [p/sup 3/,k] code with k/spl ges/(p/sup 3/-2p/sup 2/+3p-2)/2. We show that the minimum weight and the weight of the minimum stopping set of LU(3,q) are at least 2q and they are exactly 2q for many LU(3,q) codes. We find some interesting LDPC codes by our partial row construction. We also give simulation results for some of our codes.

We study certain projections of binary linear codes onto larger fields. These projections include the well-known projection of the extended Golay [24,12,8] code onto the hexacode over $\mbox{GF}(4)$ and the projection of the Reed--Muller code R(2,5) onto the unique self-dual [8,4,4] code over $\mbox{GF}(4)$. We give acharacterization of these projections, and we construct several binary linear codes which have best known optimal parameters, for instance, [20,11,5], [40,22,8], [48,21,12], and [72,31,16]. We also relate the automorphism group of a quaternary code to that of the corresponding binary code.

We present a cyclotomic approach to the construction of all binary duadic codes of prime lengths. We calculate the number of all binary duadic codes for a given prime length and that of all duadic codes that are not quadratic residue codes. We give necessary and sufficient conditions for p such that all binary duadic codes of length p are quadratic residue (QR) codes. We also show how to determine some weights of duadic codes with the help of cyclotomic numbers.

We classify the self-dual Z/sub 4/ codes of all lengths from 10 through 15, extending the previous classification through length 9.

A set of n-tuples over Z/sub 4/ is called a code over Z/sub 4/ or a Z/sub 4/ code if it is a Z/sub 4/ module. We prove that any Z/sub 4/-cyclic code C has generators of the form (fh, 2fg) where fgh=x/sup n/-1 over Z/sub 4/ and |C|=4/sup deg g/2/sup deg h/. We also show that C/sup /spl perp// has generators of the form (g/sup */h/sup */, 2f/sup */g/sup */). We show that idempotent generators exist for certain cyclic codes. A particularly interesting family of Z/sub 4/-cyclic codes are quadratic residue codes. We define such codes in terms of their idempotent generators and show that these codes also have many good properties which are analogous in many respects to properties of quadratic residue codes over a field. We show that the nonlinear binary images of the extended QR codes of lengths 32 and 48 have higher minimum weights than comparable known linear codes.

J.H. Conway and N.J.A. Sloane (see ibid., vol.36, no.6, p.1319-33, Nov. 1990) give weight enumerators of several self-dual codes with the highest possible minimal distance whose existence was not known. A generator matrix for one of these, a Type I (64, 32, 12) code, is given, proving its existence. The method of construction is described.>

Some construction techniques for self-dual codes are investigated, and the authors construct a singly-even self-dual (48,24,10)-code with a weight enumerator that was not known to be attainable. It is shown that there exists a singly-even self-dual code C' of length n=48 and minimum weight d=10 whose weight enumerator is prescribed in the work of J.H. Conway et al. (see ibid., vol.36, no.5, p.1319-33, 1990). Two self-dual codes of length n are called neighbors, provided their intersection is a code of dimension (n/2)-1. The code C' is a neighbor of the extended quadratic residue code of length 48.>

If C is a code, an orphan is a coset that is not a descendant. Orphans arise naturally in the investigation of the covering radius. Case C has only even-weight vectors and minimum distance of at least four. Cosets that are orphans are characterized, and then the existence is proved of a family of orphans of first-order Reed-Muller codes R(1, m). For m>

An attempt at directly constructing a (24, 12, 10) extremal quaternary code is reported. The attempt at directly constructing the generator matrix of the code is detailed. It was found that no such code exists.>

The covering radius r of a code is the maximum distance from any vector in the space containing the code to the nearest codeword. The authors introduce a new function l(m,r), called the length function, which equals the smallest length of a binary code of codimension m and covering radius r. They investigate basic properties of the length function. Projective geometries over larger fields are used to construct families of codes which improve significantly the upper bound for l(m,2) obtained by amalgamation of Hamming codes. General methods are developed for ruling out the existence of codes of covering radius 2 with a given codimension and length resulting in lower bounds for l(m,2). A table is presented which gives the best results now known for l(m,r) with m>

It is shown that all extremal codes are homogeneous. This implies that each punctured code of an extremal code has the same weight distribution, which can be calculated directly from the weight distribution of the parent extremal code.>

All maximal self-orthogonal and self-dual codes of lengthnwheren\leq 9are completely classified. A generator matrix, Hamming weight distribution, and order of the monomial group of each of these codes are given.

We introduce exceptionally simple decoding algorithms for the two extended Golay codes. The algorithms are based on recent methods of Conway and Curtis of finding the unique blocks containing five points in either the(5,8,24)Steiner system or the(5,6,12)Steiner system. These decoding methods are simple enough to enable decoding extended Golay codes by hand. Both of the methods involve relations between the extended Golay codes and other self-dual codes. Proofs are given explaining these relationships and why the decoding methods work. The decoding algorithms are explained and illustrated with many examples.[3, chap.12]has facts about the Mathieu group and some details about decoding the Golay 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 prime\equiv \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.

It is known that every self-dual binary code which is not doubly even is a "child" of a doubly even parent. It will be shown that an(n-2,(n-2)/2)child of an(n,n/2,d)doubly even parent has covering radius\geq d-1. Every extremal doubly even(32,16,8)code has covering radius6and every extremal doubly even(48,24,12)code has covering radius8. The complete coset weight distribution of the(32,16,8)quadratic residue code is given, as well as bounds or exact values for the covering radii of all extremai doubly even codes of length less than or equal to96.

It is an interesting open question whether a self-dual quaternary(24,12,10)codeCexists. It was shown by Conway and Pless that the only primes which can be orders of permutations in the group ofCare 11, 7, and 3. In this correspondence we eliminate 11 and 7 not only as permutations but also as orders of monomials in the group ofC. This is done by reducing the problems to the consideration of several codes and finding low weight vectors in these codes.

An interesting open question is whether a(72, 36, 16)doubly even codeCexists. In [3] the odd prime numbers which can divide the order of the group ofCwere determined and23is the largest of these. Twenty-three is eliminated by reducing the problem to the consideration of348codes, each of which is shown to have minimum weight12or less. One of these codes, denoted byC', arises from the(a + x, b + x, a + b + x)construction whereaandbare in one quadratic residue code andxis in the other. The weight distribution ofC'is given.

It is an interesting open question whether an extremal (72, 36, 16) doubly even code C exists. In [3] the odd prime numbers which can divide the order of the group of C were determined. The largest of these, 23, was eliminated by finding weight 12 vectors in 384 codes [8]. The next largest prime remaining is 17. It is shown that 17 is also not possible by reducing the problem to the consideration of16.17^{3}codes and then finding a weight 12 vector, by computer, in each of these codes.

A partial classification is given of the self-dual codes of length 24 over GF (3). The main results are as follows: there are exactly two codes with minimum Hamming distanced=9; most of the codes haved=6and are indecomposable; one code withd=6has a trivial automorphism group (this is the first such self-dual code that has been found); the codes generated by the59inequivalent24 \times 24Hadamard matrices have been investigated and there appear to be only nine inequivalent codes (two withd=9and seven withd=6); and in all there are27decomposable codes, at least96indecomposable codes withd=6, and the total number of inequivalent codes is at least140.

Self-orthogonal ternary codes of minimum weight3may be analyzed in a straightforward manner using the theory of glueing introduced in earlier papers. The present paper describes a method for studying codes of minimum weight6: the supports of the words of weight6form what is called a center set. Associated with each center set is a graph, and all the graphs that can arise in this way are known. These techniques are used to classify the ternary self-dual codes of length20: there are24inequivalent codes,17of which are indecomposable. Six of the codes have minimum weight6.

All self-dual codes over GF(3) and GF(4) of length 16 are found. The self-dual codes of shorter length are described in a concise and systematic notation. A number of new techniques ("promotion" and "demotion," "tag olng? and "subtraction") are given for constructing codes. Finally, several new extremal self-dual codes are given which have length greater than 16.

Generator matrices, weight distributions, and automorphism groups are given for all (26,13,6), (28,14,6), and (30,15,6) binary self-dual codes. These results are obtained from the earlier enumeration made by J. H. Conway and the author of all (32,16) self-dual doubly even codes.

This is a first attempt to develop shift-register-based encryption methods with nonlinear characteristics. We propose some new stream enciphering schemes composed of standard components which are easy to implement and appear to be difficult to break by either a linear attack or statistical analysis.