392
`
`[41
`[51
`WI
`
`[71
`
`PI
`
`[91
`WI
`
`WI
`WI
`
`REFERENCES
`F. J. MacWilliams and N. J. A. Sloane, The Theory of’ Error-Correcring
`Codes. New York: North Holland, 1977.
`S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and
`Applications. Englewood Cliffs, NJ: Prentice-Hall, 1982.
`V. I. Koahik, “Bounds on undetected error probability and optimum
`group codes in a channel with feedback,” Telecommun. Radio Eng., vol.
`20, no. 1, pt. 2, pp. 87-92, Jan. 1965.
`V. K. Leontev, “Error-detecting encoding,” Probl. Inform. Transmission,
`vol. 8, pp. 86-92, 1972.
`V. I. Levenshtein, “Bounds on the probability of undetected error,”
`Probl. Inform. Transmission, vol. 13, pp. 1-12, 1978.
`S. K. Leung-Yan-Cheong and M. E. Hellman, “Concerning a bound on
`undetected error probability,”
`IEEE Trans. Iform. Theory, vol. IT-22,
`no. 2, pp. 235-237, Mar. 1976.
`S. K. Leung-Yan-Cheong, E. R. Barnes, and D. U. Friedman, “Some
`properties of undetected error probability of linear codes,” IEEE Trans.
`Theory, vol. IT-25, no. 1, pp. 110-112, Jan. 1979.
`Inform.
`J. K. Wolf, A. M. Michelson, and A. H. Levesque, “On the probability
`of undetected error for linear block codes,” IEEE Trans. Commun., vol.
`COM-30, no. 2, pp. 317-324, Feb. 1982.
`T. Kasami, T. Klove, and S. Lin, “Linear block codes for error detection,”
`IEEE Truns. Inform. Theory, vol. IT-29, no. 1, pp. 131-136, Jan. 1983.
`T. Helleseth, T. Klove, and J. Mykkeltveit, “The weight distribution of
`irreducible cyclic codes with block lengths n,( q’ - 1)/N,” Discrete Math.,
`vol. 18, pp. 179-211, 1977.
`J. MacWilliams, “A
`theorem on the distribution of weights in a sys-
`tematic code,” Bell Syst. Tech. J., vol. 42, pp. 79-94, Jan. 1963.
`R. Padovani and J. K. Wolf, “Data transmission using error detection
`codes,” in GLOBECOM ‘82, IEEE Global Telecom. Conf., Miami, Nov.
`29-Dec. 2, 1982, pp. 626-631.
`
`On an Infinite Series of [4n, 2 n ] Binary Codes
`LkON ti. H. E. DRIESSEN, MEMBER, IEEE
`
`correspondence deals with an infinite series of binary,
`Abstract-This
`reversible [4n, 2n, 41, n 1 2, unequal error protection codes, which are
`majority logic de&able. The weight emtmerators and automorphism groups
`are determined completely. For n .even the codes are ,self dual. By pasting
`together copies of a [4n, 2n, 41 code, binary codes with parameters
`[8n,2n,8]
`for n L 2,
`[8n,2n,l2]
`for n 24,
`and [12n,2n,16]
`and
`[16n, 2n, 241 for n > 3 are obtained.
`I.
`INTRODUCTION
`The decoder with the best error correction performance for an
`[n, k, d] binary code to be used on a binary symmetric channel,
`is a complete nearest neighbor decoder [l, p. 111. That is, any
`received word is mapped into a codeword that is nearest in
`Hamming distance. In many applications not all message bits are
`equally important and errors in more important bits are more
`serious than errors in less important bits. The question arises to
`what extent error patterns of weight greater than 1 (d - 1)/2]
`can be decoded such that the most important message bits are
`correctly retrieved. This is the same as asking for an [n, k, d]
`binary unequal error protection (UEP) code which is optimal [2],
`[31.
`In an experimental digital recorder we have implemented an
`optimal [12,6,4] binary UEP code [4], which guarantees the two
`most important message bits to be protected against two bit
`errors in the corresponding codeword. This code is a member of
`an infinite class of [4n, 2 n, 41 binary UEP codes which will be
`defined and studied in the next section. The [12,6,4] UEP code is
`used as an example throughout the correspondence.
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-30, NO. 2, MARCH 1984
`
`In Section III constructions of [4nr, 2 n] binary codes are given
`for r = 1,2, 3, and 4. These constructions are based on a detailed
`knowledge of the weight structure of the codes from Section II.
`Several codes constructed in this correspondence are optimal in
`the sense that they have the largest minimum distance known for
`a binary code with the same length and dimension [5].
`The notation we use and basic concepts will be explained
`where necessary. For additional information on coding theory or
`group theory the reader is referred to [l] and [6], respectively.
`II.
`INFINITE SERIES OF [4n, 2 n, 41 BINARY CODES
`AN
`this section we define and study an infinite class of
`In
`[4n, 2n, 41, n 2 2, binary codes. As these codes may be consid-
`ered to be generalizations of the code F16 of [7], they are denoted
`by 4;.
`Let Z, be the n by n identity matrix and let J, be the
`Definition:
`n-by-n all-one matrix. The code I;k, is defined by the generator
`matrix
`
`Gdn:=
`
`b(2) = g(“+‘),
`
`Let gci) be the ith row of G4,, and let the codewords b(l),
`1 I
`i I 2n, be defined by
`b(l) = g(l) md
`p-u
`= g(‘) + g(r),
`21iIn,
`p) = g(n+l) + g(“+‘)
`21iIn.
`The code generated by { b(‘): 3 I
`i I 2 n } is called Ban.
`Let V, be ‘the n-dimensional vector space over GF(2); On
`denotes the all-zero word in V, and 1, denotes the all-one word
`in y?. For A c V, and x E V, we denote by x + A the coset of A
`obtained by (componentwise modulo 2) addition of x to each
`element of A.
`The cosets B4;, b(l) + B4,,, bc2) + B4,,, and b(l) + bc2) + Bdn are
`denoted by Bdw B”
`and B”
`respectively. Clearly Fb,, =
`B”’
`BdT U Biz U B>j u”%iA!%e shall 4n”dw derive the weight enumer-
`ators of these cosets of B4,,.
`The (Hamming) weight of x E V, is denoted by wt (x) and the
`(Hamming) weight enumerator of A c V, is denoted by W(A ;
`z), where z is an indeterminate.
`Lemma: A codeword c E F4,, can be expressed as c =
`i, j I 1 it holds
`(x3 Y>G4,,,, where x E Z$ and y E V,. For 0 I
`that c E BiJ, if and only if wt(x) = imod
`and wt( y) =jmod2.
`The lemma immediately follows from the observation that
`
`c =
`
`(~9 Y)G,,
`
`=i
`
`x,g(i)
`
`+
`
`yjg(n+~)
`
`L
`j=l
`
`i=l
`
`i=2
`
`+
`
`2
`j=2
`
`i=l
`
`yj(g(n+j)
`
`+ g(n+l))
`
`+
`
`pi"+"j$lYj~
`
`Theorem 1: The weight enumerators of the cosets of B4* in Fd,,
`are
`
`WB4:;
`
`z)
`
`Manuscript received August 13, 1982; revised March 29, 1983.
`The author is with Philips Research Laboratories, P.O. Box 80.000, 5600 JA
`Eindhoven, The Netherlands.
`
`W(B,‘,o; z) = W(Bj;;
`
`z) = 2”-’
`
`y’
`
`( 2i 1 J2)1+2+41,
`
`WB,‘:;
`
`z)
`
`= 22n-2z2n
`
`0018-9448/84/0300-0392$01.00 01984 IEEE
`
`IPR2018-1556
`HTC EX1055, Page 1
`
`

`

`IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-30, NO. 2, MARCH 1984
`
`393
`
`Proof: From the Lemma we deduce that
`c E B4y if and only if wt (x) and wt ( y) are even, in which
`case c = (x, x, y, y) and wt(c) = 2(wt(x) + wt( y)),
`if and only if wt (x)
`is odd and wt ( y) is even, in
`c E Biz
`which case c = (x,x, y, y + 1,) and wt(c) = n + 2wt(x),
`if and only if wt (x)
`is even and wt ( y) is odd, in
`c E Bji
`whichcasec=(x+
`ln,x,y,y)andwt(c)=
`n+ 2wt(y),
`c E BlA if and only if wt (x) and wt ( y) are odd, in which case
`c = (x + l,, x, y, y + 1,) and wt(c) = 2n.
`The expressions for the weight enumerators are now easily found.
`Q.E.D.
`From Theorem 1 we know that Fan, n 2 2, has minimum
`distance 4. There is a generalization of the concept of minimum
`distance, called separation vector, the value of which strongly
`depends on the encoding procedure [2], [3]. Let h(l), h(‘);
`.,hck)
`be k basis codewords according to which the encoding takes
`place. That is, if tn E V,, the corresponding codeword is c(m) =
`m,h(‘) + m,ld2) +
`. . . + m,hck). The separation vector s =
`(Sl, S2,‘. . ,s,) is defined bysi:= min{wt(c(m)): m E.V~, m, =
`l}
`for 1 I
`i 5 k. A separation vector s guarantees the correct
`if the number of errors in the code
`retrieval of message bit mi
`word c(m) is at most [(sI - 1)/2],
`[2], [3]. If not all s, are equal
`to the minimum distance, the code is said to have the unequal
`error protection property. For n 2 3, the code F4, has the UEP
`property. We state this in Theorem 2.
`Theorem 2: The code F4,,, n 2 2, has the following properties:
`a) Fdn is reversible.
`b) F4, is equivalent to its dual code.
`c) Fan is self dual if and only if n is even.
`d) F4, is equivalent to a double circulant code.
`e) If the message word m E V,, is encoded as c(m) = mlbC1)
`. . . + m2nb(2n), then F4,, n 2 3, has the UEP
`+ m2bC2) +
`property with separation vector s, si = s2 = n + 2, and
`si = 4 for 3 I
`i 5 2n.
`f) F4, is majority logic decodable.
`Proof:
`a) The reversibility
`matrix G+
`b) The matrix obtained from G4,, by interchanging the columns
`i and n + i for 1 _< i 5 n and 2n + 1 I
`i 4 3n is a parity check
`matrix for F4,.
`c) Ed, is self dual if and only if G4,,GTn = Ozn, thus if and only
`if n is even.
`d) The matrix formed by taking the columns of G,, in the
`order n + i, i,2n + i,3n + i for i = 1,2;..,n,
`is the generator
`matrix of a quasi-cyclic code with shift 2.
`e) If m E V,,, then c(m) E B4;lm*.
`.,szn):
`The separation vector is s = (si, s2;.
`Sl = min {wt(c):
`c E Bi’f, U Biz}
`= n + 2,
`s2 = min{wt(c):cEB~~UB~~}=n+2,
`c E Fan}
`si = wt(b(‘)) = 4 = min {wt(c):
`For n 2 3 this proves the UEP property of Ed,.
`f) For m E V,, we define x(m) and y(m) as
`
`follows immediately
`
`from
`
`the generator
`
`and
`for 3 I
`
`i 5 2n.
`
`x(m):=
`
`i
`i=l
`
`i
`
`m2i-1, m3, m5,...,m2n-1
`
`i
`
`and
`
`y(m):=
`
`i m2,, m4, m6,..‘,m2n
`( i=l
`
`.
`
`i
`
`Then we have
`c(m) = (x(m), u(m>)G,
`= (x(m) + m21n, x(m), y(m), v(m) + mll,,).
`
`Let 2 be the received word. We have to find a number of
`checks on each message bit m, such that with majority
`logic
`decoding the error protection as specified by e) is achieved. For
`j = 1,2,3,4 we definepi:= C:=l?(j-l)n+i. Consider m, first.
`If n is even, then it is easy to find n + 2 orthogonal checks [3]
`i < n. If n is
`on ml, namely pi, p2, and ?2n+r + E3n+i for 1 I
`odd we again have the n orthogonal checks c2,,+ i + ?3n+i for
`1 I
`i I n but the other checks, although orthogonal to the previ-
`ous ones, will not be mutually orthogonal. Note that p2, 2, +
`^
`c,+l + ~1, and 22 + G+2 + p1 are three checks on m, which
`only involve the bits ?,; . ., 2,“.
`If these checks are mutually
`equal, which happens to be so if
`there are no errors among
`L
`Cl,‘. ‘,%I, then p2 is considered as a double check on ml.
`If the
`three checks are not mutually equal, which happens to be so if
`exactly one error occurs among ?,, . . . , ?,, , then p2 and p2 + 1
`are considered as checks on ml (or no check is considered).
`It is easily seen that a majority vote on the n + 2 checks on ml,
`found as explained above, guarantees m, to be correctly retrieved
`if at most 1 (n + 1)/2] errors occur in 2. In a similar way n + 2
`checks on m2 are found.
`Once we have m, and m 2, four orthogonal checks on m 2i _ 1 for
`2 5 i 5 n are ?i + m2, ?n+i, p1 + & + m, + (m2
`if n is even),
`mdP2 + cn+i + m,. In a similar way four orthogonal checks on
`Q.E.D.
`m2i for 2 I
`i I n are found.
`Example: Let n = 3. The code F12 is generated by
`f)“’ = p
`= (LO, &LO, o,o, 090, 1, 1,1)
`
`@’
`
`= &4)
`
`=
`(l,l,l,o,o,o,l,o,o,l,o,o)
`b(3) = g(l) + g(2) = (1, LO, 1, l,O, o,o, o,o, 0,O) \
`b(4) = g(4) + g(5) = (0, o,o,o, o,o, l,l, O,l, 1,O)
`b(5) = g(l) + g(3) = (LO, 1, l,O, LO, o,o, O,O,O)
`b(6) = g(4) + $6) = (O,O,O, o,o, O,l, O,l, l,O, 1) j
`
`generate B,,
`
`in F12 are
`The weight enumerators of the cosets of B,,
`=l + 6z4 + 9zs,
`W4”;
`z)
`12z5 + 4z9,
`W( B;;; z) = W(B;;;
`z) =
`=
`16~~.
`WB::;
`z)
`F12 is equivalent to the double circulant code with
`culants (100000) and (110101).
`F12 is a [12,6,4] code with separation vector (5,5,4,4,4 4). This
`is optimal [3], [4]. The check sets on m,, m2;.
`.,m6 are
`^
`^
`4
`= Cl + ClO,
`= E, +
`i?,,,
`ml
`m, = 2, f ?,,,
`
`the cir-
`
`elsep, + 1.
`
`m2 = C, + ?,,
`m2 = C, + C,,
`m2 = ?, + Z,,
`m2 = t, + 2, + t, = p3,
`+ cl2 + Es
`m2 = p3 if 2, + 2s + 2, = E,, + ?,, + t, = c -10
`^
`elsep, + 1.
`
`m3=2,+m2,
`m3 = Z,,
`m3 = ?, + 2, -I- m,,
`m3 = 2, i- ?, + m,.
`m5 = i?, + m2,
`m5 = Z,,
`m5 = t, + e2 + ml,
`^
`I
`m5 = c4 •t c5 + m,.
`
`m4 = t,,
`m4 = C,, + m,,
`m4 = ?, •t 2, + m2,
`m4 = L?,, •t ?,, •t m2,
`m6 = t,,
`m6 = Z,, + m,,
`m6 = ?, + ?, •t m2,
`e
`m6 = cl0 + i?,, + m2.
`
`IPR2018-1556
`HTC EX1055, Page 2
`
`

`

`394
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-~& NO. 2, MARCH 1984
`
`We have proved that Aut (F4,) = T, X &, X 3, X S/, X SL.
`Q.E.D.
`
`Example: Let n = 3.
`T, =
`((1>,(1,12>(2,11)(3,10)(4,9)(5,8)(6,7)).
`L, =
`((1>,(1,4),(2,5>,(3,6),(1,4)(2,5),(1,4)(3,6),
`(2,5)(3,6>,(1,4>(2,5>(3,6)}.
`((1>,(1,4>(2,5),(1,4>(3,6),(2,5)(3,6)}.
`{(1>,(7,lO>,(8,ll>,(9,12),(7,10)(8,11),
`(7,10)(9,12),
`(8,11)(9,12),
`(7,10)(8,11)(9,12)}.
`
`L3 =
`R, =
`
`+ l),
`
`- 2) ... (2n,2n
`
`The code F, is an [8,4,4] code with weight enumerator W(F8;
`Z) = 1 + 1424 + z8 and hence F8 is the nearly perfect and self
`dual [8,4,4] extended Hamming code or, equivalently, the first-
`order Reed-Muller code of length 8 [l, p. 281. Consequently the
`automorphism group of 10, is the general affine group GA(3) [l,
`p. 3761 of order 1344. The automorphism group of F4,, n 2 3, is
`given by Theorem 3.
`If ?r is a permutation of { 1,2,. . , n }, then r~ induces a mapping
`of V, onto V, as follows:
`the word x E V, is mapped onto
`g(x)
`=
`(x,-l(l),
`x,-1(2),‘.
`.,x,-y,)).
`The automorphism group of A c V, is denoted by Aut (A).
`Theorem 3: Let the permutations 7, hi, and p,, 1 I
`i I n, of
`., 4n) be given by
`{1,2;.
`- 1)(3,4n
`7 = (1,4n)(2,4n
`A, = (i, n + i),
`pi = (2n + i,3n + i).
`Let T,, L,, &,, R,, and R,, be the groups generated by r, {xi:
`1 < i I n},
`{ hihi: 1 I
`i < j I n}, {pi: 1 5 i 4,n}, and { p,p,:
`1 I
`i < j I n }, respectively. Let S,’ be the symmetric group on n
`points acting on {1,2;..,n}
`and
`{n + 1, n + 2;..,n
`+ n}
`simultaneously. Let Sl be the symmetric group on n points acting
`+
`on (2n + 1,2n + 2;.., 2n + n} and (3n + 1,3n + 2;..,3n
`n} simultaneously. The automorphism groups of B4n and F4,,,
`n 2 3, respectively, are
`Aut (B,,)
`= T, x L, x R, X S; X S;
`Aut (F4,) = T, X z, x &, X S, X S,r.
`Both groups are l-transitive groups acting on 4n points and have
`order 22”+‘(n!)2 and 22”-‘(n!)2,
`respectively.
`Proof: A permutation of the coordinate set acting on words
`is weight-preserving. From theorem 1 it follows that for n 2 3
`any codeword of F4, having weight 4 is in B4,,. Since B4n is
`generated by codewords of weight 4, we have that for n 2 3
`Aut ( F4n) is a subgroup of Aut ( B4n).
`From the lemma we know that
`{(x,x,y,y):x~
`V,,wt(x)iseven;
`B4n=
`y E &,wt(y)iseven}.
`Due to the special form of the elements of B4n we define the pairs
`of coordinates {i, n + i}, 1 5 i I n,
`to be left pairs and the
`pairs (2n + i,3n + i}, 1 I
`i I n, to be right pairs.
`A word is equivalently represented by the set of its nonzero
`coordinates. So c E B4n if and only if c is the union of an even
`number of left pairs and an even number of right pairs. For
`n 2 3, an automorphism of B4n must send pairs into pairs.
`Moreover, if an automorphism of B4n sends a left pair into a left
`pair, then all left pairs are sent into left pairs and all right pairs
`into right pairs; if an automorphism sends a left pair into a right
`pair, then all left pairs are sent into right pairs and vice versa.
`From Theorem 2 a) we know that T is an automorphism of F4n; T
`has order 2 and sends left pairs into right pairs and vice versa.
`Any automorphism of B4n leaving the coordinates 2 n + 1,2 n +
`. ,4n fixed is the product of a permutation leaving every left
`2;.
`pair fixed and a permutation of the left pairs and hence is an
`element of L,, X SL. Any element of L, X S,’ is an automorphism
`of B4n. Similarly any element of R, x SL is an automorphism of
`B 47l’
`We have proved that Aut (B4,,) = T, x L, x R, x S! x S,l.
`As we saw above, Aut (F4,)
`is a subgroup of Aut ( B4,,). An
`automorphism of B4n is an automorphism of F4:4n if and only if b(l)
`and bc2) are sent into codewords of F4,. For 7~ E S,’ we have
`a(bc2)) = bc2) and a(b’“)
`= g (no)). Hence S! c Aut ( F4,,). Anal-
`ogously SL C Aut (F4n). For r E R, we have v(bc2’) = bc2), but
`= (10 . . . 0,lO
`... O,y,y+
`l,,)forsomeyE
`I$,which
`.(b’“)
`according to the lemma is a codeword of F4,, if and only if wt ( y)
`is even. So x(b”)) E F4, if and only if r E R,,. Analogously for
`VI E L, we have +rr E Aut ( F4”) if and only if r E z,.
`
`(8,11)(9,12)}.
`
`R, =
`
`s; =
`
`s; =
`
`(7,10)(9,12),
`ll),
`(7,10)(8,
`{(I),
`((1),(1,2>(4,5),(1,3>(4,6),(2,3)(5,6),
`(1,2,3>(4,5,6>,(1,3,2)(4,6,5)}.
`(8,9)(11,12),
`((I),
`(7, @(lo, 111, (7,9)(10,12),
`(7,8,9)(10,11,12),
`(7,9,8)(10,12,11>>
`.
`]Aut(B,,)] = 4608 and ]Aut(Fi,)] = 1152.
`III.
`COMBINING CODES
`In this section we use the structure of the codes F4,,, defined
`and studied in Section II,
`to obtain linear codes with other
`parameters. Some of these codes are good in the sense that they
`have the largest minimum distance known [5].
`Concatenating or “pasting” two words x and y of length n and
`m, respectively, to form a new word 1x1 y], gives a word of length
`n + m:
`
`lxlyl=
`(X1,X2,...,X,,Y1,Y2,...,Ym)..
`Let x(l), xc’),. . .,xck) and y(l), yc2);. .,yck’ be k basis code-
`words for an [n,, k, d,] and an [n,, k, d2] code, respectively. A
`pasting of these codes may be the [nl + n2, k, d] code with
`~,(l)l~(l)l
`. . .,lxWly’k’l
`as k basis codewords, where d 2 d, +
`d,.
`’
`Theorem 4: Let the code Gs,,, n 2 2, of length 8n be generated
`by
`
`+ 14,J,
`i = 1,2,
`Ib(‘)I
`Ib(’
`3 5 i 5 2n.
`I2
`The code G,, is an [8n, 2n, 81 code and for n 2 3 it has the UEP
`property with separation vectors, si = s2 = 4n and s, = 8, 3 < i
`5 2n.
`The weight enumerator of G,, is
`
`W(G,,;
`
`z) = ‘g’
`
`‘$
`
`( li)(
`
`;j)z2(4i+4J)
`
`+ 3 . 22n-2z4n.
`
`Proof: Obviously G,, has dimension 2 n. Let Ix] y ] be any
`codeword of G,,.
`If x E B4T,
`then y = x and, according to
`Theoreml,wt(y)=wt(x)=4rforsomer,O<r<2[n/2].If
`then
`If x E Bit U BiE,
`x E B,‘,:, then y = x and wt(x) = 2n.
`y = x + 14rz and wt ( y) = 4n - wt (x). The separation vector
`Q.E.D.
`and the weight enumerator are now easily found.
`Theorem 5: Let the code HBn, n 2 2, of length 8n be generated
`by
`
`lb(‘)
`lb”’
`I7
`lb”’ + b(‘+l)
`lb”’
`I 9
`lb@n)lb(2”) + b(3) + b(4)1,
`
`i = 1,2,
`3 I
`i I2ri
`
`- 1,
`
`ThecodeHs,isan[8n,2n,d]codewhered=2(n+2)ifn=2,
`3 and d = 12 otherwise. For n 2 5, HBn has the UEP property
`with separation vector s, si = s2 = 2(n + 2) and s, = 12 for
`3 5 i 5 2n.
`
`IPR2018-1556
`HTC EX1055, Page 3
`
`

`

`IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-30, NO. 2, MARCH 1984
`
`395
`
`Proof: Obviously Hsn has dimension 2 n. Let Ix] y I be any
`codeword of Hsn. If x E Bii U Bit,
`then alsoy E B:A U Biz and
`so, according to Theorem 1, wt (Ix] y]] = 2(n + 2) + 4r for some
`If XEB~~,
`then alsoy~B~~
`and
`r, O<r<2[(n-1)/21.
`hence wt (x) = wt ( y) = 2n.
`If x E B4y,
`then also y E B4T.
`Clearly wt (x) = 0 if and only if wt ( y) = 0. If wt (x) = 4, then
`either x = b(”
`for some i, 3 I
`i I 2n or x = b(‘) + b(i+2r)
`for
`some r and i, 0 < r < n and 3 I
`i 5 2n - 2r.
`In both cases
`wt ( y) 2 8. From this we deduce that if wt ( y) = 4, then wt (x)
`2 8. The separation vector is now easily derived.
`Q.E.D.
`Example: Let n = 3. The code G24 is a [24,6,8] code with
`weight enumerator 1 + 6z8 + 48~‘~ + 9~‘~. The separation vec-
`tor of G,, is (12,12,8,8,8,8).
`The code H24 is a [24,6, lo] code. The weight enumerator,
`determined by inspection, is
`W(ZZ,,; z) = 1 + 182” + 28~‘~ + 12~‘~ + 3~‘~ + 22”.
`The proofs of the following theorems are omitted since they are
`similar to the proofs of Theorem 4 and Theorem 5.
`Theorem 6: Let the code Z12,,, n 2 2, of length 12n be gen-
`erated by
`lb(‘) lb”’ + l,,lb”’
`I?
`,
`lb(‘) lb”’
`lb”’ + b(‘+‘)
`lb(2n)lb(*n)
`lb@) + b(3) + b@)l,
`
`i = 1,2,
`3IiI2n-1,
`
`d] code where d = 12 if n = 2 and
`The code K12,, is a [12n,2n,
`d = 16 otherwise. All weights are divisible by 4. For n 2 4, K12n
`has the UEP property with separation vectors, si = s2 = 4n + 4,
`and s, = 16 for 3 I
`i I 2n.
`is a [36,6,16] code. The
`Example: Let n = 3. The code K,,
`inspection (compare with
`weight enumerator is determined b
`z) = 1 + 38~‘~ + 142 2x + 11~~~.
`Z3& W(K,,;
`
`SUMMARY
`In this correspondence an infinite class of [4n, 2n, 41, n 2 2,
`binary codes has been studied in some detail. In particular the
`weight enumerators and automorphism groups have been de-
`termined. The detailed knowledge of the weight structure of these
`codes has led to several other infinite series of binary codes.
`
`REFERENCES
`F. J. MacWilliams and N. .I. A. Sloane, The Theory of Error Correcting
`Codes. Amsterdam: North-Holland, 1977.
`L. A. Dunning and W. E. Robbins, “Optimal encoding of linear block
`Inform. Corm., vol. 37, pp. 150-177,
`codes for unequal error protection,”
`May 1978.
`tonics on linear uneaual error orotection codes:
`W. .I. van Gils. “Two
`Bounds on their length and cyclic code classes,” IEEE> Trans. Inform.
`Theory, vol. IT-29, pp. 866-876, Nov. 1983.
`L. M. H. E. Driessen, Dutch Patent Nr. 8105799, Dec. 1981.
`H. .I. Helgert and R. D. Stinaff, “Minimum-distance bounds for binary
`Trans. Inform. Theory, vol. IT-19, pp. 344-356, May
`linear codes.” IEEE
`1973.
`M. Hall, The Theory of Groups. New York: McMillan, 1964.
`V. Pless, “A classification of self-orthogonal codes over GF (2),” Dtscrete
`Math., vol. 3, pp. 209-246, 1972.
`
`VI
`PI
`
`[31
`
`[41
`[51
`
`[61
`[71
`
`Further Classifications of Codes Meeting the
`Griesmer Bound
`TOR HELLESETH
`
`an
`Abstract-For
`(n, k, d) binary linear code, the Griesmer bound
`r’ d/2’], where [ x 1 denotes the smallest integer > x.
`says that n > Cf:/
`We consider codes meeting the Griesmer bound with equality. These codes
`have parameters
`
`( s(2k -
`
`l)-
`
`,
`
`i2u1+
`&l),k,&-
`i=l
`r=l
`i
`> up > 1. We characterize all such codes whenp = 2
`where k > u1 >
`or u,ml - u, > 2 for 2 < i 6 p.
`
`I.
`INTRODUCTION
`We let an (n, k, d) code be a binary linear code of length n,
`dimension k, and minimum distance of at least d. We let n (k, d)
`be the smallest integer n such that an (n, k, d) code exists. Many
`efforts have been made
`to
`find
`codes with parameters
`(n(k, d), k, d). For an extensive list of bounds on n(k, d)
`the
`reader should consult the tables of Helgert and Stinaff [l].
`A general lower bound on n(k, d), due to Griesmer [2], says
`k-l
`c
`i=O I
`
`n(k,d)>
`
`f
`
`,
`1
`
`(1.1)
`
`Manuscript received September 27, 1982; revised March 7, 1983. This work
`was presented in part at the IEEE International Symposium on Information
`Theory, Les Arcs, France, June 21-25, 1982.
`The author
`is with CHOD Norway/SEC, Oslo Mil/Akershus, Oslo 1,
`Norway.
`
`I,
`1,
`31,i<2n-1,
`If+) + b(3) + b@)lb%) + $3) + b(4)/.
`
`i = 1,2,
`
`d] code where d = 12 if n = 2 and
`The code Z12n is a [12n,2n,
`d = 16 otherwise. For n 2 3, Z12n has the UEP property with
`I
`separation vectors, si = s2 = 5n + 2 ,ands, = 16for3
`i I 2n.
`Theorem 7: Let the code J16n, n 2 2, of length 16n be gen-
`erated by
`lb(‘) lb”’ + 14,Jbci)
`lb(‘) + b(‘+‘)
`lb”’
`lb(‘)
`
`lb(‘) + l,,
`lb(‘) + /,(I+‘)
`
`lb@n)/b@)
`
`The code J16n is a [16n, 2 n, d ] code where d = 16 if n = 2 and
`d = 24 otherwise. For n 2 4, J16n has the UEP property with
`separation vectors, si = s2 = 8n, and si = 24 for 3 I
`i I 2n.
`Example: Let n = 3. The code Z36 is a [36,6,16] code with
`separation vector (17,17,16,16,16,16), and the code J48 is a
`[48,6,24] code. The weight enumerators of both codes can be
`determined without writing out all codewords,
`
`z) = 1 + 6~‘~ + 242” + 16~” + 6z2’ + 8z21 + 3z24
`
`w(z36;
`and
`
`W( J48; z) = 1 + 60~~~ + 3~~~.
`
`Copies of F4h, may be combined in many other ways, yielding
`codes again with other parameters or codes with the same param-
`eters but with another weight enumerator. As an example of this
`latter statement we give the following theorem.
`Theorem 8: Let the code K12n, n 2 2, of length 12n be gen-
`erated by
`lb(‘) lb’”
`I,
`lb”’ + bc2)
`/b(2)
`lb@) lb(‘) + b(2)
`I3
`lb(3) lb’% + b(4) lb@)
`IT
`lb(‘) lb”’ + b(l+l)lb(‘) + b(‘-1) I,
`lb(2+(2n)
`lb@“) + b@-l)l.
`
`4IiI2n-1,
`
`0018-9448/84/0300-0395$01.00 01984 IEEE
`
`IPR2018-1556
`HTC EX1055, Page 4
`
`