A (48, 31, 8) linear code (Corresp.)

709

CORRESPONDENCE

Lemma 2 follows from the inequality

A (48,31,8) Linear Code VENKAT

logQE

N+l Qw _

log

=

Q&j

+

log!&

Q’ klj

@i/j

’

Remark: Lemma 2 provides an alternate proof of convergence of Blahut’s algorithm. Lemma 3: The approximation error e(r) = F(p,Q’+‘,q’)

- P

(which by Lemma 1 is always nonnegative) is inversely proportional to the number of iterations. In particular, if Q’ is chosen such that each row is a uniform probability vector (i.e., Qk,j’ = l/n for each j,k), then e(r) I 1 r

log

II

+

c

c

j

pj&k,j

log

&klJ

k

-< 1 log n. r Proof: By Lemma 2, we have

@)

AND

SUDHAKAR

M. REDDY

Abstract-In this paper we construct a linear code having length 48, minimum distance 8, and containing 231 codewords. This code is obtained by augmenting a (48,22,8) linear code with 2g - 1 cosets so that the minimum distance is not reduced. The (48,22,8) code used is the direct product of a (16,11,4) extended Hamming code and a (3,2,2) single-parity-check code. The new code has twice as many codewords as the best linear or nonlinear code previously known.

I. INTRODUCTION In this paper a linear code with the parameters (length, number of information positions, minimum distance) = (48,318) is constructed. This code has a higher rate than the best linear or nonlinear code previously known with this length and minimum distance. The construction of this code involves two steps: 1) form the direct product of the (16,11,4) extended Hamming code and the (3,2,2) single-parity-check code; the result is a (48,22,8) code; and 2) augment [8] the (48,22,8) code with 2’ - 1 cosets such that the minimum distance is not reduced. The weight structure of the cosets of the (16,5,8) first-order Reed-Muller code that belong to the second-order Reed-Muller code were partially helpful in choosing the required coset leaders. The augmentation of the product code was achieved with the use of a technique suggested earlier [l]. This involves the use of the concept of the so-called “augmented syndrome” [l 1.

Also, by Lemma 1, F(p,Qr+l,q’)

V. RAO

II. CONSTRUCTION

I F(p,Q’,q’-‘)

5 . . + I . . . s F(p,Q2,q1)

therefore,

r [%&Y+‘,q ‘)

- F:] I

i

[F(p,Q’+‘,q’)

- F].

(7)

Let C be the direct product of the codes C, and C,, where C, is the (16,11,4) extended Hamming code and C, is the (3,2,2) code. Let GH and G, be the generator matrices of C, and C,, respectively. If G, = [;::I, then the generator matrix G, of C can be written as

By (6) and (7) we have G, =

Gz 0

1

0 GH GH GH '

where Substituting

iooooooioooioiii 1 Q;,, = ; ,

K i

we have GH = log

n

+

c

c

j

PJ&k,J

k

log

&k/J

I

I 1 log n r

which completes the proof. ACKNOWLEDGMENT

The author is grateful to Prof. J. Ziv for his helpful suggestions.

0100000100010100 0010000100010010 0001000100010001 0000100100000110 0000010100000101 0000001100000011 0000000010010110 0000000001010101 0000000000110011 0 0 0 0,o 0 0 0 0 0 0 0

11

11

and 0 is a 11 x 16 zero matrix. A word in C, say X, can be written as X = [albla

0 b]

REFERENCES [ll R. E. Blahut, “Computation of channel capacity and rate-distortion functions,” IEEE Trans. Inform. Theory, vol. IT-18, pp. 460473, July 1972. [2] S. Arimoto, “An algorithm for computingthe ca acity of arbitrary discrete memoryless channels,” IEEE Trans. In Parm. Theory, vol. IT-18, pp. 14-20, Jan. 1972. [3] R. E. Blahuf, “Computation ofinformation measure,” Ph.D. dissertation Cornell Umv., Ithaca, N.Y., Aug. 1972.

Manuscript received January 23, 1973; revised March 5, 1973. This research was supported in part by the National Science Foundation under Grant GK-36377. V. V. Rao was with the Department of Electrical Engineering, University of Iowa, Iowa City, Iowa. He is currently with the Department of Electrical Engineering, Indian Institute of Technology, Madras, India. S. M. Reddy is with the Department of Electrical Engineering, University of Iowa, Iowa City, Iowa.

710

IEEETRANSACTIONSONINFORMATIONTHEORY,SEPTEMElER 1973

where a and /J are 16-bit vectors in C, and “0” is the componentwise mod-two sum operation, Clearly C is a (48,22,8) linear code. The dual of C, is the (16,5,8) Reed-Muller code [3], [4]. Let this code be C3 and its generator matrix be 0000000011111111 0000111100001111 G,=0011001100110011. 0101010101010101 I 1111111111111111 Let C’ be the following code: C’=

{X:X=

1

a@albla@b,whereaandb~C~anda~C~}.

Lemma I: C’ is a (48,27,8) linear code. Proof: Clearly C’ is a linear code with 227 words. Let X1

and X2 E C’ and X1 # X2. Let x, = [a 0 a,lb,lu, x2

=

b2

@

a2P2lf72

0 b,] @ b21.

Then x1 0 x2 =

[(a,

0 UJ 0 (a1 0

=

[AIBIC].

Another way to establish the parameters of C” is to determine its weight distribution. A convenient way to derive the weight distribution of C” is to derive the weight distribution of the dual code of C” and then use the MacWilliams identity [13] to obtain the weight distribution of C”. Helgert [12] has obtained the weight distribution of the dual code of C”, which is given in the following (since the dual code of C” has 2l’ words it was feasible to obtain the weight distribution by listing all the codewords):

az)lb, 0 b,l(u, 0 UJ 0 (b, 0 b,)]

4

lb 80 3063 7 168 14640 21 504 38 160 21 504 14640 7 168 3 063 80 1

* 12 16 18 20 22 24 26 28 30 32 36 48.

The weight distribution of C” was obtained by Sloane [14] and is given as follows: At

If a, @ a2 = 0, then X1 @ X, E C and hence has a weight (number of ones in X1 0 X2) of at least 8. If a, 0 a2 $ 0, then a, @ a2 has a weight of at least 8. Furthermore, A 0 B 0 C = a1 @ a2 and hence the weight of [A I BI C] is at least 8. Q.E.D. Let C, be the code whose generator matrix G4 is given in the following: 0111000010000000 G=OOIOOOO1llOOOOOO 4 1001000011000000’ 0000000000111010 [

I

Let C” be the code defined in the following: C” = {X: X = [u 0 fl 0 ajb 0 ala 0 b 0 a], where a, b E C1, p E Car and a E C,}. Theorem 1: C” is a (48,31,8) linear code. Proof: Rigorous proof of Theorem 1 is unrewardingly

tedious and not given here. However, a detailed proof appears in [6, ch. V]. A brief sketch of the proof follows. If p and a are fixed in X = [a 0 /? 0 aI6 0 ala 0 b 0 a] and all possible values for a and b are allowed, we generate a coset of C, the (48,22,8) product code. There are 2’ choices for fl and a. Therefore to prove that C” is a (48,31,8) linear code, we have to show that 1) C” is a linear code; 2) the 2’ cosets are all different; and 3) in each coset the minimum-weight vectors have weight of at least 8. The first two points are easy to establish. To establish 3 we need to investigate the nature of the augmented syndromes [l ] for the cosets. The generator matrix, G”, of C” can be written as follows: rGH

L

G4

0

G4

‘%l

G4]

1 7 530 92 160 1080384 7 342080 34408911 111507456 255566784 417 404 928 492663 180 417404928 255 566784 111507456 34408911 7 342080 1080384 92 160 7 530 1

4’s 40 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10 8 0.

III, DISCUSSION The motivation for this work was provided. by a recent paper [9] in which a new generalization of the Golay code was given. In this generalization of the (24,12,8) extended Golay code, a class of linear codes with the ratio of minimum distance to length equal to + were obtained. The code given in this paper is constructed on lines similar to the codes of [9], but uses a secondorder Reed-Muller code as a component code in the product code to be extended, instead of a first-order Reed-Muller code [9]. We pose generalization of the code given here as an open question. The code given has twice as many codewords as the best known linear or nonlinear [lo] code. After reading our work, Helgert [12] showed that the dual of C” (the code given now) has minimum weight 12, and that by deleting 12 appropriate positions a (36,20,8) linear code can be obtained. This linear code is an ontimum code.

711

CORRESPONDENCE

Johnson [ll ] has recently given new upper bounds on the number of codewords in a binary code. His upper bound for a minimum-distance-eight code of length 48 is larger than 232. Therefore it is possible that a (48,32,8) code might exist. ACKNOWLEDGMENT

The authors would like to thank the anonymous referees and Prof. J. L. Massey for suggestions that have helped improve the presentation of the paper. REFERENCES [l] Morris Goldberg, “Easily decoded error-correcting codes and techniques for their generation,” Ph.D. dissertation Imperial College of Sctence and Technology,, Univ. London, London, England, 1971. [2] P. Elias, “Error-free codmg,” IRE Trans. Inform. Theory, vol. PGIT-4, pp. 29-37, Sept. 1954. [3] I. S. Reed, “A class of multiple-error-correcting codes and the decoding scheme,” IRE Trans. Inform. Theory, vol. PGIT-4, pp. 38-49, Sept. 1954. [4] D. E. Muller, “Applications of Boolean algebra to switching circuit design and to error detection,” IRE Trans. Electron. Comput., vol. EC-3, pp. 6-12, Sept. 1954. [5] W. W. Peterson and E. J. Weldon, Error Correcting Codes. Cambridge, Mass.: M.I.T. Press, 1972. [6] V. V. Rao, “Reed-Muller codes: weight enumeration and applications in augmenting certain product codes,” Ph.D. dissertation, Univ. Iowa, Iowa City, Iowa, Aug. 1972. [7] S. M. Johnson, “On upper bounds for unrestricted binary errorcorrecting codes,” IEEE Trans. Inform. Theory, vol. IT-17, pp. 466-

_._, _-., .1971..

478.hlv

[8] E. R. Berlekamp, Algebraic Coding Theory. New York: McGrawHill, 1968. [9] N. J. A. Sloane, S. M. Reddy, and C. L. Chen, “New binary codes,” IEEE Trans. Inform. Theory, vol. IT-18, pp. 503-510, July 1972. [lo] N. J. A. Sloane and D. S. Whitehead, “A new family of single-errorcorrecting codes,” IEEE Trans. Inform. Theory, vol. IT-16, pp. 717719. Nov. 1970. [ll] S. M. Johnson, “On upper bounds for unrestricted binary errorcorrecting codes,” IEEE Trans. Inform. Theory, vol. IT-17, pp. 466478, July 1971. [12] S. J. Helgert, private communication, Sept. 1972. [13] F.. J. MacWdliams, “A theorem on the distribution of weights in a systematic code,” Bell Syst. Tech. J., vol. 42, pp. 79-94, 1963. [14] N. J. A. Sloane, private communication, Feb. 1973.

CODE CONSTRUCTION

There are several known classes of binary (k + m, k) codes having 2m members which meet the VG bound. Because of its algebraic simplicity, the class of inner codes used by Justesen will also be used here. As the outer code, we will use a BCH code over GF (2’) of length 2m - 1 with K information symbols. The inner code is then chosen to be a (k + m, k) code with k = s, m = bs, and b = 1,2,3; . . . A codeword is formed by first encoding a K-tuple of s-bit information characters into a (2m - 1)-character BCH-codeword. This word, now represented as the vector

a = [aO,al,.. .,a2m-21,

is then encoded into a codeword c as follows: c = [C&,.

Construction-the

E. J. WELDON,

Low-Rate

. ‘,CZrn-l]<

The (b + l)-element column matrix cI is defined as CLT- - [ai,aido,aiail,

* . .,aid”-‘1

where a is primitive in GF (2’) and where (ib- i,ibm2, * . . ,io) is the (radix-2s)-form of i. That is i =

i.

+

il

*

2s +

i2 *

22s +

. - * +

ibml

.2@-l)s,

OIi,I2S--1.

(3)

In this construction, the field element 0 is used in place of a”-i. With this definition, it can be seen that a given nonzero (b + I)-tuple with elements in GF (2’) having a nonzero parity section can appear in exactly one row. The number of the row to which a (b + l)-tuple (y,ye,yi, * * *,ybml) belongs is given by the radix-2” number log(T)

Justesen’s

ai E GF (2’)

+ 2S.log(?j

+ 22~.log(~)

+ ***

Case

(4)

JR.

using the more general class of BCH codes, rather than RS codes as originally proposed, the results of Justesen [l] are improved for code rates below 0.07. The value of d/n for the new codes approaches the Varsharmov-Gilbert bound (0.5) as the rate approaches zero. Abstract-By

Justesen’s construction [l ] employs an outer Reed-Solomon (RS) code of length 2”’ - 1 “concatenated” with every code in a class of binary codes. The construction relies on the fact that the class of binary codes chosen has the properties that i) a given nonzero vector can appear in at most one code, and ii) there are 2m - 1 codes in the class. The only known classesof codes with both of these properties have rate R 2 0.5. In this note, we use a Bose-Chaudhuri-Hoquengchen (BCH) code as the outer code; this permits the use of a class of binary inner codes of any rate. For overall rate R < 0.07 or so, this change improves on Justesen’s results. As R approaches zero, the ratio of minimum distance to code length (d/n) for our construction approaches 0.5; i.e., the Varshamov-Gilbert (VG) bound.

Manuscript received September 29, 1972; revised February 1, 1973. The author is with the Department of Electrical Engineering, University of Hawaii, Honolulu, Hawaii 96822, and ADTECH Incorporated, Honolulu, Hawaii.

where logarithms are taken to the base u. Of course, nonzero vectors with all parity checks equal to zero or all information symbols equal to zero appear in no codes. MINIMUM

DISTANCE CALCULATION

A direct consequence of the fact that, except for vectors appearing in no codes, a nonzero vector can appear in only one code is that the class composed of the 2bs - 1 binary (s(b + l),s) codes used in the preceding construction satisfies the VG bound. Since the outer code has minimum distance dBCH, the minimum distance of the code is bounded by (5)

where db is the largest integer such that (6) For an individual code the design distance do, whose value is given by the BCH bound, provides a fairly tight lower bound on d aCH. The following lemma provides a somewhat loose bound for short codes, but for large values of II this bound differs little from the exact form of the BCH bound.