On separating codes

Gérard D. Cohen  Sylvia B. Encheva Hans Georg Schaathun
ENST Dept. INFRES  HSH  UiB Dept. of informatics
46, rue Barrault  Bjørnsonsgt. 45  Høyteknologisenteret
F-75634 Paris Cedex 13 N-5528 Haugesund  N-5020 Bergen
France  Norway  Norway
cohen@enst.fr  sbe@hsh.no  georg@ii.uib.no

Abstract

Let Γ be a code of length , and ( ) a pair of disjoint subsets of Γ. We say that ( ) is separated if there exists a coordinate , such that for any codeword ( _{1} _{}) and any codeword ( _{1}^{}_{}^{}) , _{}= _{}^{}. The code Γ is ( )-separating if all pairs ( ) with # = and # = are separated.

Separating codes (or systems) are known from combinatorics, and they have also been applied, under various terminology, for watermarking.

We present some new bounds, generalisations, and constructions for separating codes.

Keywords separating system, intersecting code

Codes séparants

Résumé

Soit Γ un code de longeur , et ( ) un couple de sous-ensembles disjoints de Γ. On dit que ( ) est séparé s’il existe une position telle que pour tout mot ( _{1} _{}) et tout mot ( _{1}^{}_{}^{}) , = _{}^{}. Le code Γ est dit ( )-séparant si tout tel couple où # = et # = est séparé.

Les codes, ou systèmes, séparants sont connus en Combinatoire ; ils ont été utilisés, sous des vocables divers, dans des problèmes de marquage numérique.

Nous présentons de nouvelles bornes, des généralisations et des constructions de codes séparants.

Mots-clefs système séparant, code intersectant

Paris, 3rd April 2001

To appear as technical report at Ecole Nationale Supérieure des Télécommunications, Paris, France.

Skiljande kodar

Samandrag

Lat Γ vera ein kode med leng , og lat ( ) vera eit par av disjunkte delmengder av Γ. Me seier at ( ) er skilt om det er ein plass slik at for alle ord ( _{1} _{}) og alle ord ( _{1}^{}_{}^{}) , har me _{}= _{}^{}. Koden Γ er skiljande om alle slike par med # = og # = er skilde.

Skiljande kodar, eller system, er kjende frå kombinatorikken, og dei har vorte nytta, under ymse namn, til vannmerking og kopivern.

Me skal finna nokre nye grenser, generaliseringar og konstruksjoner for skiljande kodar.

Stikkord skiljande system, snittande kode

Chapter 1

Introduction

The theory of separating systems has been applied in different areas of science and technology such as automata synthesis, technical diagnosis, constructions of hash functions, and authenticating ownership claims.

The following property and generalisations have been studied e.g. by Körner and Simonyi under the set-theoretic terminology of ( )-separation [19]. Associate in a natural way to every row of an array a bipartition of the set of coordinates = 1 2 , i.e. a pair _{}_{}of disjoint subsets of such that _{}_{}= . Then for any ordered -tuple ( _{1} _{2} _{}) of , there is a bipartition which separates _{1} _{2} _{} from _{+1} _{}. The problem of finding the minimum size of such a separating family of partitions for arbitrary remains open. The case of (2 2)-separation is introduced by Sagalovich in the context of automata: two such systems transiting simultaneously from state to ^{}and from to ^{}respectively should be forbidden to pass through a common intermediate state. He has written a long series of papers since the sixties, e.g. [24, 25]; a fairly recent survey can be found in [26]. States are simply binary -tuples and only shortest paths are allowed during transitions; in other words, the only ‘moves’ permitted while transiting from to ^{}are complementing the ( ^{}) bits where and ^{}differ (one at a time). Clearly if the separation property holds, no two such minimal-length paths between and ^{}, and and ^{}will intersect.

The design of self-checking asynchronous networks has been a challenging problem. Friedmann et al. [15] have shown that the unicode singletransition-time asynchronous state assignment correspond to (2 2)- and (2 1)-separating systems.

Digital watermark is a perceptually invisible pattern embedded in a digital image. The watermark can carry information about the owner of the image or the recipient: watermarking for copyright protection, finger-

1

CHAPTER 1. INTRODUCTION

printing [4], or traitor tracing [31]. Codes were introduced in [4] (see also [14]) as a method of ‘digital fingerprinting’ which prevents a coalition of a given size from forging a copy with no member of the coalition being caught, or from framing an innocent user.

The rest of this chapter will be spent on defining basic terminology and notation, whereas in the next section we will discover some bounds on the length and distance of separating codes, as well as some constructions.

In Chapter 3, we will introduce generalised separation and hashing, and give some more general results. Chapter 4 will be dealing with intersecting codes and demonstrate the relation between separation and intersection.

We will try to summarise the known results in form of tables of rates in Chapter 5. Finally we will give some results on maximum weights in Chapter 6.

1.1 Separating Codes

Let be an additive group and 𝕍 the set of -tuples over . An ( ) code Γ is an -subset Γ 𝕍. If is a field of elements and is a - dimensional subspace ≦ 𝕍, then we say that is a [ ]_{}(linear) code.

The feasible set ( ) of some vector set 𝕍 is

( ) := ( _{1}  _{}) 𝕍  1  ( _{1}  _{})  _{}= _{}

In the case of fingerprinting, each user holds one codeword, and a coalition of users make a set of codewords; then ( ) is the set of (false) fingerprints they can produce.

Definition 1 We say that a code is ( )-separating if, for any pair ( ) of disjoint subsets of where # = and # = , the feasible sets are disjoint, i.e. ( ) ( ) = .

In earlier works on watermarking, ( )-separating codes have been called -PIC (partially identifying codes) [10] or -SFP (secure frameproof) [31, 30, 29]. The current terminology appears to be older though [26]. Different special cases have also appeared in litterature; the -frameproof codes from [29] are just ( 1)-separating codes. The (2 1)-separating, binary codes has also been studied in [20].

2

1.2. MINIMUM AND MAXIMUM WEIGHTS

Definition 2 A ( )-configuration is a pair ( ) of disjoint vector sets of sizes and respectively. We say that ( ) is separated if ( ) ( ) = , and otherwise it is non-separated. A ( )-NSC is a non-separated ( )-configuration.

A code is ( )-separating if and only if it contains no ( )-NSC. Obviously, if is ( )-separating, then it is also ( )-separating, and ( ^{}^{})- separating for all ^{}and all ^{}.

Remark 1.1 If : 𝕍 𝕍 is an automorphism, then ( ) is a ( )-NSC if and only if ( ( ) ( )) is a ( )-NSC.

Remark 1.2 If ( ) is a ( )-NSC, then so is ( + c + c) for any c 𝕍. If + c + c , then ^{}for some code ^{}equivalent to . If is linear and , then + c + c .

Remark 1.1 tells us that if is a linear ( )-separating code, then so is any equivalent code. Also, if Γ is a non-linear ( )-separating code, then so is any equivalent code, by Remark 1.2.

1.2 Minimum and Maximum Weights

For any vector c = ( _{1} _{}) 𝕍 we define the support to be

(c) := _{}= 0

For any subset 𝕍, the support is

( ) := _{c} (c)

We define the weight of subsets and codewords to be the size of their support, and denote it (c) := # (c) or ( ) := # ( ).

Let be a linear code. The -th minimum support weight _{}of is the least weight of an -dimensional subcode of . The -th maximum support weight _{}is the largest weight of an -dimensional subcode of . Both these numbers were first studied in [16], and the minimum support weight has received quite some attention following [35], where it was called the -th generalised Hamming weight.

It is clear that _{1} is the minimum distance of the code, and likewise _{1} is the maximum distance of the code; so these two numbers are defined also for non-linear codes. Several general definitions of _{}exist for nonlinear codes, but we will not need any of them here.

3

4

Separation

The first section of this chapter is devoted to necessary conditions for ( ^{})-separation. We will start with lower bounds on in terms of and ^{}. The second half of the section will present bounds on the minimum and maximum distances.

In Section 2.2, we give sufficient conditions for a code to be (2 2)- separating based on minimum and maximum weights. Finally, in Section 2.3, we present some constructions.

2.1 Bounds for linear codes

Proposition 1 Let a and b be two linearly independent codewords, and write = a b + a GF( ) . Then (0 ) is a ( + 1 1)-NSC.

Proof: We shall prove that in every position , at least one codeword in has a 0. If _{}= 0, this holds, so assume _{}= 0. Then b + ( _{}^{1} ) _{}a has 0 in position , as required. □

Corollary 1 If is -ary, linear ( ^{})-separating, then max ^{}.

This bound is tight in the binary case, since (2 2)-separating, binary, linear codes are known to exist (e.g. [26]).

Theorem 1 If is a non-binary, linear ( ^{})-separating, then + ^{}+ 1.

Proof: We have already proved that ^{}. It only remains to prove that we can construct a ( + 2 )-NSC for all such that 2 . Let

5

CHAPTER 2. SEPARATION

0 _{1} _{1} be all the fields elements, where _{0} = 0 and _{1} = 1. Let a and b be two independent codewords. A ( + 2 )-NSC is given by

( _{0}a  _{1} a _{}a a + _{1}b  a + _{+1} b )

First note that _{}a matches 0 on every position not in (a), and a + b match a on every position not in (b). In every position in (a) (b), we get different field values in the first set, and + 1 different field values from the a + _{}b. Since there are only elements in the field, they cannot be separated. □

Proposition 2 If is a linear, ( 1)-separating code, then _{1} + 2.

Proof: We shall prove that if  _{1}  1, then cannot be ( 1)-

separating. Consider a codeword c of maximum weight and let = c GF( ) . Since the code is linear, for every set of 2 coordinate positions, there exist at least 1 non-zero codewords which are zero on these positions. In particular, there is a non-zero codeword a which is zero on every position not in (c). Thus ( ; a) is a ( 1)-NSC. □

Proposition 3 If is a linear, binary (2 2)-separating code, then _{1} 2( 2).

Proof: If 1, the result is trivial. For = 2, it only says that the all-one codeword 1 cannot be in the code , lest (0 1; c c + 1) form a (2 2)-NSC for c 0 1).

We then turn to the case 3. We shall prove that if _{1} 2( 2), then cannot be (2 2)-separating. Consider a codeword c of maximum weight. Since the code is linear, for every set of 2 coordinate positions, there exist at least three non-zero codewords which are zero on these positions, and thus at least one which is not c. In particular, there is a non-zero codeword a which is zero on half the positions not in (c), and one b which is zero on the other half. Thus (0 c; a b) is a (2 2)-NSC. □

Proposition 4 If is non-binary, linear, ( 2)-separating, then _{1} ( 1) .

Proof: Assume for a contradiction that _{1} ( 1) . We shall construct a ( 2)-NSC. Let c be a codeword of minimum weight. By Remark 1.1, we can assume that c is one on every non-zero coordinate. Since the code is linear, for every set of 1 coordinates there exist at least ( 1) non-zero codewords which are zero on these coordinates. For every set of coordinates there exists at least one non-zero codeword which are either one or

6

2.2. (2 2)-SEPARATING CODES

zero on these coordinates. Hence there exist 1 codewords a_{1} a_{1} such that at least one of them is either one or zero on every position in

(c). Hence (0 c; c a_{1}  a_{1} ) is a (2 )-NSC for every = 0 1.  □

2.2 (2 2)-separating codes

Let c^{}c a b be distinct vectors such that ( c^{}c a b ) is a (2 2)-NSC. From this assumption, we will derive some statements on the minimum and maximum weights of any code which is not (2 2)-separating. This will give a sufficient condition for a code to be (2 2)-separating in Theorem 2.

By Remark 1.2, we can assume that c^{}= 0; and by Remark 1.1, we can

assume that c = (1  1 0  0). We write
c = ( _{1} _{2}  _{})
a = ( _{1} _{2}  _{})
b = ( _{1} _{2}  _{})
Let be such that _{}= 1 for  and _{}= 0 for  . Since (0 c; a b)

is a (2 2)-NSC, there is no coordinate such that both _{}0 _{}and 0 _{}.

We consider the sum

Σ := (0 a) + (0 b) + (c a) + (c b)

= (a) + (b) + (a c) + (b c)

We have trivially that

4 _{1} Σ 4 _{1}  (2.1)

Consider now the matrix with rows 0 c a b. Let x_{}be the -th column in this matrix. We have four main types of columns:

Type 0 : x_{}= (0 0 0 0)
Type I : x_{}(0 0 0 ) (0 0 0)  = 0
Type IIa : x_{}(0 1 0 0) (0 1 1 1)
Type IIb : x_{}(0 1 0 1) (0 1 1 0)
Type III : x_{}(0 1 0 ) (0 1 0) (0 1 1 ) (0 1 1)  0 1

No other possibility exists because the rows form a (2 2)-NSC. We have now that

Σ = _{=1}^{}(x_{})  (2.2)

7

where (x_{}) is 0 for Type 0, 2 for Types I and II, and 3 for Type III. Let _{X} denote the number of columns of Type X. Then we get

= _{0} + _{I} + _{II} + _{III}  (2.3)
Σ = 2 _{I} + 2 _{II} + 3 _{III}  (2.4)

Proposition 5 If (0 c; a b) is a (2 2)-NSC, then

Σ = (c) + (a b) + (a + b c)

Proof: We have trivially that

(c) = _{0} + _{I}  (2.5)

Define two vectors

y = ( _{1} _{2}  _{}) := a + b c
z = ( _{1} _{2}  _{}) := a b

We have that

x_{}of Type 0  _{}= 0  _{}= 0
x_{}of Type I  _{}= 1  _{}= 1
x_{}of Type IIa  _{}= 1  _{}= 0
x_{}of Type IIb  _{}= 0  _{}= 1
x_{}of Type III  _{}1 = = 0
( 1)  = = 0

This gives

(a + b c)  =  (y) = _{0} + _{IIb}
(a b) =  (z) = _{0} + _{IIa}

By adding together the two equations above as well as (2.5), we get

3 ( (c) + (a b) + (a + b c)) = 3 _{0} + _{IIa} + _{IIb} + _{I}

From (2.4)and (2.3)we get that

Σ = 3 (3 _{0} + _{IIa} + _{IIb} + _{I}) = (c) + (a b) + (a + b c)

as required. □

We observe that (a b) = (a b) and (0 c) = (c) are distances in the code; hence they are bounded by _{1}. If is linear, (a + b c) is also a distance in the code, and thus bounded by _{1}. If is non-linear, we still have (a + b c) . This gives directly the following theorem.

8

Theorem 2 If a code satisfies 4 _{1} 2 _{1} + , or if 4 _{1} 3 _{1} and it is linear, then it is (2 2)-separating.

Corollary 2 All linear, equidistant codes are (2 2)-separating. A non-linear, equidistant code is (2 2)-separating if 2 _{1} .

The binary linear case of Theorem 2 has previously been proved by Sagalovich [25] (see also [26]). The non-linear case of the corollary was proved in [11].

The non-linear case of the corollary is tight, in fact

= (1000) (0100) (0010) (0001)

is an equidistant (4 4 2) code, but it is not separating. The linear case of the theorem is also tight, as the following example shows.

Example 2.1 From the proposition we get that if (0 c; a b) is a binary (2 2)- NSC and 4 _{1} = 3 _{1}, then

(c) = (a b) = (a + b c) = _{1} = 4
(a) = (b) = (a c) = (b c) = _{1} = 3

It turns out that the only possible (2 2)-NSC is the following, or replications thereof:

; ; ; 0 c a b ; ; ; = ; ; ; 000000 111100 110010 101001 ; ; ;

Note that the linear code a b c has also _{1} = 3 and _{1} = 4.

Proposition 6 If is binary, linear and 2 _{1} _{2}, then it is (2 2)-separating.

Proof: Let (0 c; a b) be a (2 2)-NSC. We consider first the case where a, b, and c are linearly independent. Then a + b, a + b + c, and c are the three non-zero codewords in some 2-dimensional subcode . Thus we get that

(c) + (a b) + (a + b c) = 2 ( a + b c ) 2 _{2}  (2.6)

and by Proposition 5 that

4 _{1} Σ = (c) + (a b) + (a + b c) 2 _{2}
9

If a, b, and c are linearily dependent, then a + b + c = 0, and (2.6)becomes

(c) + (a b) + (a + b c) 2 _{1}

which is stronger. □

It is easy to show that _{2} 3 _{1} 2 , which is a maximum support weight analogue of the Griesmer bound. If this bound is not met with equality, then the above result is stronger than that of Theorem 2.

2.3 (2 2)-separating constructions

The next results provide a way to combine (2 2)-separating codes into new ones.

Theorem 3 [23] Let = _{1} _{2}, with _{2} _{1} and _{2} is not divisible either by 2 or by

3. Suppose _{1}( _{1} _{1}) and _{2}( _{2} _{2}) are binary (2 2)-separating. Then there is a (2 2)-separating ( ) code with = _{1} + 4 _{2}.

Example 2.2 Suppose we take _{1} = _{2} where _{1} = 11 _{1} = 11, then = 121 = 55. Applying Theorem 3 again, with _{1}(11 11) and _{2}(55 121), leads to a (2 2)-separating code with = 1331 = 231.

Take now _{1} = _{2} = 13 _{1} = _{2} = 13, then = 169 = 65. Applying Theorem 3 a second time with _{1} = 13 _{1} = 13 and _{2} = 169 _{1} = 65 leads to a (2 2)-separating code with = 1859 = 273.

It is relatively easy to apply Theorem 2 on codes with few weights, such as the following examples with two- and three-weight codes.

Example 2.3 Take a linear projective code over GF( ^{2}) [5] with length

= \frac{( ^{_{1}} ( 1)^{_{1}})( ^{_{1} 1} ( 1)^{_{1} 1} )}{^{2} 1}

dimension _{1} and weights _{1} = ^{2 _{1} 3} _{2} = ^{2 _{1} 3} + ( )^{_{1} 2} .

In the case = 2 for _{1} = 4 it gives a (45 4^{4})_{4} code, which is (2 2)- separating since it satisfies 4 _{1} 3 _{1}.

Example 2.4 A three-weight code over GF( ) is given in [5] with length

= + 1 + ^{2}( ^{_{1} 1} ( 1)^{_{1} 1} )( ^{_{1} 2} ( 1)^{_{1} 2} ) ( 1)
10

2.3. (2 2)-SEPARATING CONSTRUCTIONS

dimension = 2 _{1} and weights _{1} = ^{2 _{1} 2} ( )^{_{1}} ( )^{_{1} 1} _{2} = 2 _{1} 2 _{3} = ^{2 _{1} 2} ( )^{_{1}}.

In the binary case for = 6 it gives a (39 2^{6})_{2} code, which is (2 2)-separating since it satisfies 4 _{1} 3 _{1}.

11

12

Generalised separation and hashing

A ( _{1} _{2} )-separating hash family, as defined in [32], is the same as a ( _{1} _{2})-separating, -ary code of cardinality . The perfect hash families studied in [32] can also be viewed as a variant of separating codes, if we adopt the following definition.

Definition 3 A sequence ( _{1}  _{}) of pairwise disjoint vector sets is called a ( _{1}  _{})-

configuration if # _{}= _{}for all . Such a configuration is separated if there is a position , such that for all = ^{}every vector of _{}is different from every vector of _{^{}}on position .

A code is ( _{1} _{})-separating if every ( _{1} _{})-configuration is separated.

For = 2, this definition coïncides with the previous one. A ( )- perfect hash family from [32] is a (1 1 1)-separating (with ones) ( ) code. For brevity, we will say that such a code is -hashing. The ( )-partial hashing [3] is (1 1 1 )-separation (with ones) in our terminology.

3.1 Basic results

Define

( _{1}  _{}) := _{=1}^{1} _{= +1}^{}_{}_{}(3.1)

13

CHAPTER 3. GENERALISED SEPARATION AND HASHING

Note that if _{}= 1 for all , then

( _{1}  _{})= { \atop 2}  (3.2)

and if = 2, then

( _{1} _{2})= _{1} _{2}  (3.3)

The following proposition generalises the results on separating and perfect hashing families from [32, 2].

Proposition 7 An (  )_{}code Γ is ( _{1}  _{})-separating if

\frac{}{}1 \frac{1}{( _{1} _{})}

Proof: Suppose Γ is non-( _{1} _{})-separating, and consider some non-

separated ( _{1}  _{})-configuration ( _{1}  _{}) and the sum

Σ := _{=1}^{1} _{= +1}^{}_{( ) _{}_{}}( )

This is the sum of ( _{1}  _{}) distances in the code, so Σ ( _{1}  _{}) .

Each coordinate can contribute at most ( _{1} _{}) to the sum Σ, but if any coordinate does contribute that much, then the configuration is separated on this coordinate. Hence each coordinate can contribute at most ( _{1} _{}) 1 to the sum Σ, and we get

( _{1}  _{}) Σ ( ( _{1}  _{}) 1)

Simplifying this, we get that any non-( _{1} _{})-separating code must satisfy

\frac{}{}1 \frac{1}{( _{1} _{})}

and the proposition follows. □

It must be noted that, to get infinite families of separating codes with good rate, the alphabet size grows extremely rapidly in the _{}-s, due to the Plotkin bound. However, better separating codes can be built by concatenation. Though this construction is well-known in various special cases from the literature [2], we have not found as general a statement as the one we give below.

14

3.1. BASIC RESULTS

Proposition 8 If Γ_{1} is a ( _{1}  _{})-separating, ^{}-ary ( _{1} ) code and Γ_{2} a ( _{1}  _{})-

separating, -ary, ( _{2} ^{}) code, then the concatenated code Γ := Γ_{2} Γ_{1} is a ( _{1} _{})-separating ( _{1} _{2} )_{}code.

Proof: Consider a ( _{1}  _{})-configuration ( _{1}  _{}) in Γ. Then there

is a corresponding configuration in Γ_{1}, ( _{1}^{}_{}^{}) which is separated on some coordinate by assumption. Considering only the positions of Γ corresponding to position in Γ_{2}, we get a ( _{1}^{}_{}^{})-configuration ( _{1}^{}_{}^{}) in Γ_{1} where 1 _{}^{}_{}for all . Since also Γ_{1} is ( _{1} _{})-separating, ( _{1}^{}_{}^{}) is separated on some position . Hence ( _{1} _{}) must be separated, as required. □

Note that the only thing we know about the minimum distance of Γ is that it is at least equal to that of Γ_{1}. In general the concatenated code will not satisfy the requirement of Proposition 7. We will give a thorough example of the technique in Section 3.2.

Proposition 9 If is a linear, ( _{1} _{})-separating code and 3, then _{=1}^{}_{}.

Recall that the case when = 2 was solved in Theorem 1. Proof: First we prove that _{1} + _{2} , for if

1  _{2} c  GF( )

then no third set _{3} will be separated from _{1} and _{2}.

Let _{0} _{1} _{1} be all the field elements, where _{0} = 0 and _{1} = 1. Let a and b be two independent codewords. Let

1 := _{0}a  _{_{1} 1} a
2 := _{_{1}}a  _{_{2} 1} a

and let _{3} _{}be any sequence of pairwise disjoint sets such that

:= _{=3}^{}_{}= a + _{1}b  a + _{^{}}b

where ^{}= _{3} + + _{}. Clearly, _{1} and _{2} are only separated on (a). Also and _{1} are only separated on (b). On any coordinate (a) (b), 1 + _{2} different values occur in _{1} _{2} and ^{}different values occur in . Hence the configuration can only be separated if

+ _{1} + _{2} = _{1} + + _{}

as required. □

15

Corollary 3 If is a linear -ary, ( )-partially hashing code with 2, then .

These bounds are tight, since -hashing codes can be constructed for any .

3.2 The tetracode and compositions thereof

The ternary constructions will make use of three ingredient codes, and apply twice the concatenation method.

The first seed is the remarkable [4 2 3]_{3} tetracode 𝔗, defined by the generator matrix

= 1 1 1 0 0 1 2 1

This code is self-dual and MDS (on Singleton’s bound = + 1). It is both an extended perfect Hamming code and a simplex (all codewords are at distance 3 apart). The next result is a consequence of Theorem 2 and Proposition 7.

Proposition 10 The [4 2 3]_{3} tetracode is both (2 2)- and (3 1)-separating, and 3-hashing.

The fact that the tetracode is 3-hashing was already known from [21]. The codes constructed in the sequel are also 3-hashing, but we do not claim that they are particularly good compared to existing codes. Our main interest is (2 2)- and (3 1)-separation after all.

Let ℜ_{1} be the [9 3 7]_{3^{2}} Reed-Solomon code, which is both (2 2)- and (1 3)-separating, and 3-hashing by Proposition 7. The concatenated code 𝔗 ℜ_{1} has parameters [36 6]_{3}, and by Proposition 8, it is (2 2)- and (1 3)- separating, and 3-hashing. In order to produce infinite families of separating codes, we need the following constructive result from Tsfasmann [33].

Lemma 1 For any 0 there is an infinite families of codes 𝔄( ) with parameters

[  ]_{}for  _{0}( ) and
+ 1 ( \overline{}1)^{1}

We should note that the rate of 𝔄( ) is interesting only for large , but 𝔗 ℜ_{1} allows for concatenation with 𝔄( ) over GF(3^{6}) which may be

16

3.2. THE TETRACODE AND COMPOSITIONS THEREOF

acceptable. Thus consider the family of [ = 3 4 + 1]_{3^{6}} codes 𝔄( ), which has rate ^{}1 4 (3^{3} 1)^{1} = 11 52. The concatenated code 𝔗 ℜ_{1} 𝔄( ) gives an infinite family of linear, ternary (3 1)- and (2 2)-separating and 3-hashing codes with rate ^{}6 0 0352.

If we only want (3 1)-separating and 3-hashing codes, we can obtain a better rate by using the Reed-Solomon code ℜ_{2} with parameters [10 4 7]_{3^{2}}, which results in the concatenated code 𝔗 ℜ_{2} with parameters [40 8]_{3}. Then we take the infinite family 𝔄( ) of codes with parameters [ = 2 3 + 1]_{3^{8}} of rate 1 3 (3^{4} 1)^{1} , and the concatenated code 𝔗 ℜ_{2} 𝔄( ) is an infinite family of linear ternary (3 1)-separating and 3-hashing codes with rate approximately 77 1200 0 0642.

Example 3.1 We sketch a construction with = 4 as well. As in the previous example, we concatenate three codes to build the infinite family. Each code has 3 4 and thus is (2 2)-separating by Proposition 7. The first two are doubly extended Reed-Solomon codes. We take successively:

1. _{1}[5 2 4]_{4};

2. _{2}[17 5 13]_{4^{2}}, getting _{1} _{2}[85 10]_{4};

3. and finally, ( )[ = 3 4 + 1]_{4^{10}} with rate 1 4 (4^{5} 1)^{1} 1 4.

The final outcome is an infinite constructive family of linear quaternary (2 2)- separating codes with rate approximately 1 34 0 029.

17

18

Intersecting codes

Intersecting codes is another known concept from the literature. In this chapter we will see how we can construct separating codes from intersecting codes.

Definition 4 A linear code of dimension is said to be -wise intersecting if any linearly independent codewords have intersecting supports. If , we say that is -wise intersecting if and only if it is -wise intersecting.

It is easy to verify that any -wise intersecting code is also ( 1)-wise intersecting.

4.1 How intersecting codes give separation

Proposition 11 For a linear, binary code, the following properties are equivalent:

1. 3-wise intersection;

2. (2 2)-separation.

The fact that linear, (2 2)-separating codes must be 3-wise intersecting holds not only for binary codes, and it is proved in Proposition 12 below. Unfortunately, this is the only result we have found in the non-binary case.

The fact that -wise intersecting, binary codes gives rise to separating codes can be generalised. The statement of the proposition, to the effect that 1 implies 2, will follow from the special case = 3 = 2 of Proposition 14 below.

19

CHAPTER 4. INTERSECTING CODES

Proposition 12 Every linear (2 2)-separating code is 3-wise intersecting.

Proof: If = 2, three-wise intersection is equivalent to 2-wise intersection according to our definition. Any (2 2)-separating code is (2 1)- separating and hence 2-wise-intersecting by [8].

Suppose is (2 2)-separating, and consider three independent codewords a b c. We shall prove that these three words have intersecting supports. Consider the (2 2)-configuration (0 c + a; a b). Since is (2 2)- separating, there is a position where a is = 0 and b is = 0, and c + a is . Now c is = 0 on position . □

Due to this proposition, we can use many bounds on separating codes as bounds on intersecting codes. For instance, by Theorem 2, every code with 4 3 is 3-wise intersecting. In the binary case, we get that 2 2 implies 3-wise intersection by Proposition 6.

Proposition 13 If is a -wise intersecting, binary, linear code, and Γ is a nonlinear subcode such that any non-zero codewords are linearly independent, then Γ is ( + 1 )-separating for all such that 1 .

Proof: Choose any (two-part) sequence ^{}of + 1 codewords from Γ,

:= (a_{1}^{}a_{}^{}; c_{1}^{}c_{+1}^{})

By Remark 1.2, ^{}is ( + 1 )-separated if and only if := ^{}c_{+1}^{} is. Hence it suffices to show that

= (a_{1}  a_{}; c_{1}  c_{}0)

is ( + 1 )-separated.

Since any codewords in ^{}are linearly independent, so are the first codewords of . The zero vector is of course not independent of anything.

Now, consider

a_{1} + c_{1}  a_{1} + c_{}; a_{1}  a_{}

which is a set of linearly independent codewords from , and hence all non-zero on some coordinate . Since a_{1} + c_{}is non-zero on coordinate , c_{}must be zero for all . Hence , and consequently ^{}, is separated on coordinate . □

Proposition 14 If is a -wise intersecting binary linear code, and Γ is a nonlinear subcode such that any 1 non-zero codewords are linearly independent, then Γ is ( + 1 )-separating for all even such that 1 .

20

4.1. HOW INTERSECTING CODES GIVE SEPARATION

Proof: We define as in the previous proof, and the 1 first codewords of are linearly independent. If c_{}is linearly independent of the others, then we are done by the first proof; hence we assume that c_{}is dependent on the 1 first codewords, and since any 1 codewords are independent, it must in fact be the sum of the 1 first codewords.

By the same argument as in the previous proof, we get one coordinate , where a_{1} + c_{1} a_{1} + c_{1} a_{1} a_{}are all one, and c_{1} c_{1} are zero. Now, c_{}is the sum of the 1 first codewords, of which are 1 and the rest are zero on coordinate . Since is even, c_{}is zero and is separated. □

Note that if is even, then either or + 1 is even; thus we get the following corollary.

Corollary 4 If is a -wise intersecting, linear, binary code for even , and Γ is a nonlinear subcode such that any 1 non-zero codewords are linearly independent, then Γ is ( + 1 )-separating for all such that 1 .

A 3-wise intersecting, binary code is (2 2)-separating according to the above proposition, but no binary linear code is (3 1)-separating; hence the restriction that be even cannot be dropped in general.

It is perhaps not obvious how these propositions may be used to construct non-linear separating codes with a reasonable rate. The remainder of the section is devoted to explaining this.

Lemma 2 Given an [ + 1] linear, binary code , we can extract a non-linear subcode Γ of size 2^{}+ 1 such that any 2 + 1 codewords are linearly independent.

Note that the rate of Γ is approximately where = ( + 1) is the rate of . Proof: Let ^{}be the [2^{}2^{}1 2 + 2] extended BCH code. The columns of the parity check matrix of ^{}make a set Γ^{}of 2^{}vectors from GF(2)^{+1} , such that any 2 + 1 of them are linearly independent. Now there is an isomorphism : GF(2)^{+1} , so let Γ = (Γ^{}) 0 . □

Theorem 4 Given an [ ] -wise intersecting binary (asymptotical) code, there is a construction of a non-linear code Γ of rate ( 1) 2 , which is ( + 1 )-separating.

21

Proof: First consider even, and write = 2 + 2, where 0, the case = 2 is trivial from Proposition 11, anyway. By Proposition 14, we want to extract Γ such that any 2 + 1 codewords are independent, and such Γ exist with rate by Lemma 2.

Then consider odd , and write = 2 + 1, where 0. By Proposition 13, we want to extract Γ such that any 2 + 1 codewords are independent, and such Γ exist with rate by Lemma 2. □

Example 4.1 In [9], it was shown that for sufficiently large , and for any rate 1 \frac{1}{}log(2^{}1), there are -wise intersecting linear, binary [ ] codes of rate . Though non-constructive, this result guarantees the existence, for any , of non-linear, binary codes which are ( + 1 )-separating for all and have rate arbitrarily close to

\frac{1 \frac{1}{}log(2^{}1)}{( 1) 2}

4.2 Binary constructions

In this section we will give some sample constructions of separating codes, based on results on -wise intersection from [9].

Proposition 15 [9] The punctured dual of the 2-error-correcting BCH code with parameters [2^{2 +1} 2 4 + 2 2^{2} 2^{}1], is -wise intersecting.

Example 4.2 For = 4, we get from Proposition 15 a 4-wise intersecting code with parameters [2^{9} 2 18]. Now the shortende code Γ^{}of the 2^{17} codewords having a 1 in the last position (say) is clearly such that any 3 of its elements are independent, thus we get a (3 2)-separating (2^{9} 3 2^{17} + 1) code Γ := Γ^{} 0 by Corollary 4. We can concatenate Γ with the code 𝔄( ) with parameters [ 5 6 + 1]_{2^{18}} from Lemma 1 to get a (3 2)-separating code with rate 0 00557.

If Γ( ) is ( ^{})-separating, then so are the 2 subcodes Γ_{0} (resp. Γ_{1}) having 0 (resp. 1) in the first coordinate. Taking the largest and removing the first coordinate (which no longer separates anything), gives a shortened ( 1 2 ) ( ^{})-separating code.

Proposition 16 There is a constructive infinite sequence of binary ( + 1 )-separating codes of rate 2^{3( 1)} (1 + (1)).

22

4.3. UPPER BOUNDS ON INTERSECTING CODES

This proposition follows directly from the following lemma:

Lemma 3 [9] There is a constructive infinite sequence of -wise intersecting binary codes with rate arbitrarily close to

= 2^{1} \frac{1}{2^{2 +1} 1} \frac{2 + 1}{2^{2} 1} = 2^{2 3} ( + ( ))

Proof: By concatenating geometric [ ]_{}codes from Lemma 1 satisfying (1 2^{1} ) with = 2^{4 +2} , and with a rate arbitrarily close to 2^{1} 1 ( \overline{}1), with the [2^{2 +1} 2 4 + 2 2^{2} 2^{}1] code of Proposition 15, we obtain the result. □

Example 4.3 The 3-wise binary intersecting [126 14] code (case = 3 of Proposition 15), yields a (2 2)-separating code with parameters (126 2^{14}).

Example 4.4 Let = ^{2} . Consider (see Lemma 1) a family of codes 𝔄( ) with

parameters [  ]_{}with  _{0}( ) and
+ 1 ( ^{}1)^{1}

Choosing = 2 = 7, = 3 4 + , (see Proposition 7) and concatenating 𝔄( ) and , the binary [126 14 55] code, yields a constructive infinite sequence 𝔄( ) _{}of binary linear (2 2)-separating codes with rates arbitrarily close to 0 026.

4.3 Upper bounds on intersecting codes

We now present an upper bound on the rate of such codes.

Theorem 5 A -wise intersecting code _{}[ ] gives rise by projection to a ( 1)- wise intersecting code _{1} [ 1].

Proof: Let be a fixed element of minimum weight . Denote by _{}the [ 1] supplementary subspace of 0 in . Consider any ( 1) independent codewords ^{1} ^{1} in _{}. Then ^{1} ^{1} is full rank, hence these codewords of intersect (on the support of ). Thus , the projection of _{}on the support of is a ( 1)-intersecting

[  1] code.  □
23

To get an upper bound on the dimension of such codes in the binary case, we use recursively any upper bound from coding theory, for instance the McEliece et al. bound (see [22]):

2 \frac{1}{2} \overline{\frac{}{}1 \frac{}{}}

For = 3, we get the following sequence of codes:

3[  ]  _{2}[  1 ^{}]  _{1}[ ^{}2]

where _{}is -wise intersecting, and has write rate _{}.

From _{1}, we have that 2 ^{}, which implies that

2 = ( 1) ( ^{}1) ^{}

By the McEliece bound, this implies _{2} 0 28. Finally we have

1 = \frac{}{}\frac{0 28 + 1}{}0 108

where the final bound follows by applying again the McEliece bound. The following corollary arise from the same technique and some other values for .

Corollary 5 The asymptotic rate of the largest -wise intersecting binary code is at most , with _{2} 0 28 _{3} 0 108 _{4} 0 046 _{5} 0 021 _{6} 0 0099.

Note that the McEliece bound is only valid asymptotically. In particular, the [126 14] 3-wise intersecting code from Example 4.3 has rate 1 9 _{3}.

4.4 An upper bound on separation

An extension of arguments from [26] and [19] gives the following theorem.

Theorem 6 If Γ_{}( = _{1} _{}_{}) is ( )-separating, then it gives rise by projection to a code Γ_{+1} with the following properties:

1. Γ_{+1} is ( 1 1)-separating, with parameters ( _{}_{+1} = _{} 2 _{+1});

24

4.4. AN UPPER BOUND ON SEPARATION

2. ^{_{+1}} _{}2.

Proof: It is based on the case = = = 2 studied in [19]. Let Γ_{}be like in the statement of the theorem. With no loss of generality, it contains two codewords ^{}differing exactly in the first _{}coordinates. Now any two non-intersecting coalitions ^{}of respective sizes and , with have nonintersecting feasible sets by hypothesis. Since and ^{} coincide on coordinates _{}+ 1 , this property is kept by projecting on 1 _{}and removing and ^{}from their respective coalitions. This proves 1. To get 2, just note that all projections must be different at the first iteration (when = 2) and apply induction. □

We have, by use of non-binary linear programming bounds (see [1]):

( ) _{}((( 1) ( 2) 2 \overline{( 1) (1 )} ) )

In the ternary case, this gives the following upperbounds on the rates of ( )-separating codes : 0 357 0 168 0 09 for = 2 3 4 respectively.

In the linear ternary case, the previous bounds are shifted, giving 0 168 0 09 for = 2 3 respectively.

25

26

Asymptotic Results

5.1 Binary Codes

In Table 5.1, we present some upper and lower bounds for codes with different separating capabilities. Most of the bounds are known from previous works, the rest is given in form of examples in this section.

Example 5.1 Let be a 4-wise intersecting code with rate

= 1 \frac{log 15}{4} 0 0233

as described in Example 4.1. Make a non-linear subcode Γ as in Lemma 2 such that any three codewords are linearly independent. This gives a (3 2)- separating code with rate ( 1) 2 = 0 0233.

Lemma 4 Given an [ ] linear, binary code , we can extract a non-linear subcode Γ of size 2^{}such that any 2 non-zero codewords are linearly independent.

Proof: Let ^{}be the [2^{}1 2^{}1 2 + 1] BCH code. The columns of the parity check matrix of ^{}make a set Γ^{}of 2^{}1 vectors from GF(2)^{}, such that no 2 of them are linearly independent. Now there is an isomorphism : GF(2)^{}, so let Γ = (Γ^{}) 0 . □

Example 5.2 For = 5, we get from Proposition 15 a 5-wise intersecting code with parameters [2^{11} 2 22], which leads to a non-linear (3 3)-separating code Γ with rate ^{}11 2046 by Lemma 4. We concatenate Γ with the code 𝔄( ) with parameters [ 8 9 + 1]_{2^{22}} from Lemma 1 to obtain a (3 3)-separating code with rate 1 1674 = 0 000597.

27

CHAPTER 5. ASYMPTOTIC RESULTS

Lower bounds  Upper bounds
Linear Non-Linear Linear Nonlinear
( ^{}) Const. Non-const. Const. Non-const.
(2 1) 0.156^{1}  0.21^{1}  —  0.21 [20]  0.28^{1}  0.5 [20]
(3 1) N/A  N/A  0.0448 [8]  —  N/A  ?
(4 1) N/A  N/A  0.0181 [8]  —  N/A  ?
(2 2) 0.026^{4} 0.0642 [26]  —  0.0642 [26] 0.108 [12] 0.28 [26]
(3 2) N/A  N/A  0.00557^{2}  0.0233^{3}  N/A  ?
(3 3) N/A  N/A  0.000597^{5} 0.0156 [3]  N/A  0.0658 [7]

1 Bounds from intersecting codes [9]. 2 Example 4.2. 3 Example 5.1. 4 Example 4.4. 5 Example 5.2.

Table 5.1: Bounds on rates for infinite families of binary codes with various separating properties.

5.2 On linear (2 2)-separation

We will dwell a little extra on the case of (2 2)-separation, and present existence proof of codes with certain rates over different fields. The first lemma is fairly well-known, and can be found in [22].

Lemma 5 Asymptotically, for almost all codes, we have

= \frac{\binom{}{}( 1)^{}}{^{(1 )}} \frac{^{( )} 2^{ln( 1)}}{^{(1 ) ln}}

where is the natural entropy function and = is the rate.

Since we are dealing with the asymptotical case, we normalise by setting = , and we define a function ( ) by

= _{}= ^{( )}

From Lemma 5, we get

(  ) = ( ) + ln( 1) (1 ) ln  (5.1)
28

5.2. ON LINEAR (2 2)-SEPARATION

Note that for a given _{}, there are two solutions for . Setting _{}1, the two solutions will be the minimum and the maximum weights. These are of course also the zeroes of .

Let = _{1} and = _{1} be respectively the minimum and maximum normalised weights. Because and are the zeroes of , we get

( ) + ln( 1) = ( ) + ln( 1)

or

( ) ln( 1) = ln + (1 ) ln(1 )

ln (1 ) ln(1 )

(5.2)

Lemma 6 (Varshamov-Gilbert) For almost all codes, the rate and the normalised minimum distance are related by the following equation

( ) + ln( 1) = (1 ) ln

Proof: This follows from equating (  ) = 0 as in (5.1).  □

We know from Proposition 7 that if 3 4, then the code is (2 2)- separating, hence we can, by substituting = 3 4 in the Gilbert-Varshamov equation, get rates for which asymptotically almost any code is (2 2)- separating. The rates such obtained are presented under ‘Technique I’ in Table 5.2. Due to the Plotkin bound, this does not give anything over small fields.

Technique II in the table is an improvement based on Theorem 2, which says that every code with 4 3 is 2-separating. We insert = 4 3 in (5.2), and get

\frac{}{3} ln( 1) = ln + (1 ) ln(1 )

\frac{4}{3} ln \frac{4}{3} (1 \frac{4}{3}) ln(1 \frac{4}{3})

(5.3)

We have solved this equation numerically for the smallest fields, and the results are given in Table 5.2. Of course, we will always have

0 1

which will bound 3 4 in (5.3). This results in no real solution of (5.3) for 11.

29

Technique I  Technique II Others
max Rate Rate Rate
2 0.5000 0.75 N/A 0.4286 0.01477 0.0642 [26]
3 0.6667 0.75 N/A 0.5695 0.01859 0.0352^{1}
4 0.7500 0.75 N/A 0.6385 0.02206 0.029^{2}
5 0.8000 0.75 0.00459 0.6786 0.02532
7 0.8571 0.75 0.02043 0.7218 0.03153
8 0.8750 0.75 0.02774 0.7340 0.03457
9 0.8889 0.75 0.03427 0.7426 0.03766
11 0.9091 0.75 0.04530 N/A  N/A
13 0.9231 0.75 0.05417 N/A  N/A
16 0.9375 0.75 0.06464 N/A  N/A
17 0.9412 0.75 0.06757 N/A  N/A
19 0.9474 0.75 0.07279 N/A  N/A

1 The concatenated code 𝔗 ℜ_{1} 𝔄( ) from Section 3.2.

(Constructive.) 2 Example 3.1. (Constructive.)

Table 5.2: Rates for which we can guarantee the asymptotical existence of linear (2 2)-separating codes. The number max = ( 1) is the maximum possible minimum distance by the Plotkin bound.

30

On Maximum and Minimum Weights

We have used minimum and maximum support weights a couple of times in this report. Whereas minimum support weights are much studied, the results on maximum weights are rare. In this chapter we will show how bounds on minimum support weights may be applied on maximum support weights. In particular, we will prove a maximum weight analogue of the well-known Griesmer bound.

Some of the idea behind maximum support weights is that _{1} provide a bound on the size of ( ) for any coalition of size . A coalition is a subset , and we can assume, with no loss of generality by Remark 1.2, that 0 . Then it is clear that the detectable bits are those in ( ). Hence # ( ) ^{_{1}} where = # .

6.1 Preliminaries

A linear [ ] code over GF( ) can be represented by a projective multiset

: PG( 1 ) 0 1 2

where PG( 1 ) is the projective ( 1)-space over GF( ), and ( ) is the number of times occurs as a column in the generator matrix of .

We extend the multiset to the power set:

( ) = _{}( ) PG( 1 )

The code has length = (PG( 1 )). The number ( ) is called the value of .

31

CHAPTER 6. ON MAXIMUM AND MINIMUM WEIGHTS

Let

0 := max ( ) PG( 1 )

If _{0} = 1, is a set and is a projective code.

The anticode of is defined [13] by the multiset ^{}, given by

( ) = _{0} ( )  PG( 1 )  (6.1)

We have defined the minimum and maximum support weights _{}and for the code . From previous works on projective multisets [17, 34] it is well known that for each subcode _{}of dimension , there is is a subspace Π_{1} PG( 1 ) of codimension , such that

(Π_{1} ) + ( _{}) =

Therefore the maximum value of a subspace of codimension is _{}, and the minimum value of such a subspace is _{}. It follows from the same argument that _{}_{1} = _{0}.

Consider the value of Π_{1} in the anticode. There are ( ^{}1) (

1) points in Π_{1} . Hence we get from (6.1)that

(Π_{1} ) = _{0} \frac{^{}1}{1} (Π_{1} )  (6.2)

It is obvious from this equation that a subcode of minimum weight in has maximum weight in the anticode (and vice versa).

Lemma 7 If is an [ ] code, then the length of its anticode is

= _{0} \frac{^{}1}{1}

Proof: From (6.2), we get that

= _{^{}}(PG( 1 )) = _{0} \frac{^{}1}{1} _{}(PG( 1 )) = _{0} \frac{^{}1}{1}
□

Lemma 8 If ( _{1} _{}) is the weight hierarchy of , and ( _{1}^{}_{^{}}^{}) the weight hierarchy of its anticode, then

_{}^{}= ( _{}_{1} )\frac{^{}^{}}{1}  _{}
_{}^{}= ( _{}_{1} )\frac{^{}^{}}{1}  _{}

32

6.2. TURNING THE GRIESMER BOUND

Proof: From (6.2)we get that

_{}^{}= ( _{}_{1} )\frac{^{}1}{1} ( _{})
_{}^{}= ( _{}_{1} )\frac{^{}1}{1} ( _{})

If we apply Lemma 7, we get

\begin{aligned}_{}^{} & = _{0} \frac{^{}1}{1}  _{0} \frac{^{}1}{1} + ( _{}) \\ & = _{0} \frac{^{}^{}}{1}  _{} \end{aligned}

\begin{aligned}_{}^{} & = ( _{}_{1} )\frac{^{}1}{1} ( _{}) \\ & = _{0} \frac{^{}^{}}{1} _{} \end{aligned}

as required. □

To find codes with low values for _{}we can search for codes with high minimum support weights _{}and a low value _{0}. Probably we can restrict ourselves to projective codes, such that _{0} = 1.

Remark 6.1 Let ^{}be the anticode of . Then is the anticode of ^{}if and only if there is some point PG( 1 ) of value _{}( ) = 0. In other words if and only if _{0}( ) = _{0}( ^{}).

6.2 Turning the Griesmer Bound

A well-known bound on the minimum support weights, is the Griesmer Bound, which we state below. We will show that, via anticodes, the Griesmer Bound induces a bound on the maximum support weights.

Lemma 9 (Griesmer Bound) For any linear code, we have

_{=0}^{1} \frac{_{1}}{^{}}

33 CHAPTER 6. ON MAXIMUM AND MINIMUM WEIGHTS

Proposition 17 (Remseirg Bound) For any linear code, we have

_{=0}^{1} \frac{_{1}}{^{}}

Proof: From Lemma 8, we have

= _{0}^{}\frac{^{}^{}}{1} _{}^{}

We apply the Griesmer bound to get

_{0}^{}\frac{^{}^{}}{1} _{=0}^{1} \frac{_{1}^{}}{^{}}

We apply again Lemma 8 to get

_{0}^{}\frac{^{}^{}}{1} _{=0}^{1} \frac{1}{^{}}_{0} \frac{^{}^{1}}{1}  _{1}

= _{0}^{}\frac{^{}^{}}{1} _{=0}^{1} _{0} ^{1} \frac{_{1}}{^{}}

= _{0}^{}^{}\frac{^{}1}{1} _{0} _{=1}^{}^{}_{=0}^{1} \frac{_{1}}{^{}}

= ( _{0}^{}_{0}) ^{}\frac{^{}1}{1} + _{=0}^{1} \frac{_{1}}{^{}}

By the definition of anticodes (6.1), it is clear that _{0}^{}_{0}, thus the proposition follows. □

34

Bibliography

[1] Matti Aaltonen. A new upper bound on nonbinary block codes. Discrete Math., 83(2-3):139–160, 1990.

[2] N. Alon. Explicit construction of exponential sized families of - independent sets. Discrete Math., 58(2):191–193, 1986.

[3] A. Barg, G. Cohen, S. Encheva, G. Kabatiansky, and G. Zémor. A hypergraph approach to the identifying parent property. Submitted to SIAM J. on Disc. Methods.

[4] Dan Boneh and James Shaw. Collusion-secure fingerprinting for digital data. IEEE Trans. Inform. Theory, 44(5):1897–1905, 1998.

[5] I. M. Chakravarti. Families of codes with few distinct weights from singular and non-singular hermitian varieties and quadrics in projective geometries and hadamard difference sets and designs associated with two-weight codes. Coding theory and design theory, Part 1, pages 35–50, 1990.

[6] B. Chor, A. Fiat, and M. Naor. Tracing traitors. volume 839 of Springer Lecture Notes in Computer Science, pages 257–270. Springer-Verlag, 1994.

[7] Fan Chung, Ronald Graham, and Tom Leighton. Guessing secrets. Electron. J. Combin., 8, 2001.

[8] Gérard D. Cohen and Sylvia B. Encheva. Efficient constructions of frameproof codes. Electronic Letters, 36(22), 2000.

[9] Gérard Cohen and Gilles Zémor. Intersecting codes and independent families. IEEE Trans. Inform. Theory, 40:1872–1881, 1994.

[10] Gérard D. Cohen and Sylvia B. Encheva. Intersecting codes and partially identifying codes. Technical report, Ecole Nationale Supérieure des Télécommunications, September 2000.

35

[11] Gérard D. Cohen and Sylvia B. Encheva. Identifying codes for copyright protection. Technical report, Ecole Nationale Supérieure des Télécommunications, 2001.

[12] Gérard D. Cohen, Sylvia B. Encheva, and Simon Litsyn. Intersecting codes and partially identifying codes. January 2001.

[13] S. Dodunekov and J. Simonis. Codes and projective multisets. Electron. J. Combin., 5(1), 1998. Research Paper 37.

[14] Tran Van Trung D.R. Stinson and R. Wei. Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. J. Stat. Planning and Inference, 86(2):595–617, 2000.

[15] A. D. Friedman, R. L. Graham, and J.D. Ullman. Universal single transition time asynchronous state assignments. IEEE Trans. Comput., 18:541–547, 1969.

[16] Tor Helleseth, Torleiv Kløve, and Johannes Mykkeltveit. The weight distribution of irreducible cyclic codes with block lengths _{1}(( ^{}

1) ). Discrete Math., 18:179–211, 1977.

[17] Tor Helleseth, Torleiv Kløve, and Øyvind Ytrehus. Generalized Hamming weights of linear codes. IEEE Trans. Inform. Theory, 38(3):1133– 1140, 1992.

[18] Henk D. L. Hollmann, Jack H. van Lint, Jean-Paul Linnartz, and Ludo M. G. M. Tolhuizen. On codes with the identifiable parent property. J. Combin. Theory Ser. A, 82(2):121–133, 1998.

[19] J. Körner and G. Simonyi. Separating partition systems and locally different sequences. SIAM J. Discrete Math., 1:355–359, 1988.

[20] János Körner. On the extremal combinatorics of the Hamming space. J. Combin. Theory Ser. A, 71(1):112–126, 1995.

[21] J. Körner and K. Marton. New bounds for perfect hashing via information theory. European Journal of Combinatorics, 9:523–530, 1988.

[22] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977.

[23] T. Nanya and Y. Tohma. On universal single transition time asynchronous state assignments. IEEE Trans. Comput., 27:781–782, 1978.

36

[24] Yu. L. Sagalovich. A method for increasing the reliability of finite automata. Problems of Information Transmition, 1(2):27–35, 1965.

[25] Yu. L. Sagalovich. State Assignment and Reliability of Automata. Svyaz, Moscow, 1975. In Russian.

[26] Yu. L. Sagalovich. Separating systems. Problems of Information Transmition, 30(2):105–123, 1994.

[27] Hans Georg Schaathun. Upper bounds on weight hierarchies of extremal non-chain codes. Discrete Math., 2000. To appear in the Tverberg Anniversary Volume.

[28] Hans Georg Schaathun. The weight hierarchy of product codes. IEEE Trans. Inform. Theory, 46(7):2648–2651, November 2000.

[29] J. N. Staddon, D. R. Stinson, and R. Wei. Combinatorial properties of frameproof and traceability codes. September 2000.

[30] D. R. Stinson, Tran van Trung, and R. Wei. Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. J. Statist. Plann. Inference, 86(2):595–617, 2000. Special issue in honor of Professor Ralph Stanton.

[31] D. R. Stinson and R. Wei. Combinatorial properties and constructions of traceability schemes and frameproof codes. SIAM J. Discrete Math., 11(1):41–53 (electronic), 1998.

[32] D. R. Stinson, R. Wei, and L. Zhu. New constructions for perfect hash families and related structures using combinatorial designs and codes. J. Combin. Des., 8(3):189–200, 2000.

[33] Michael A. Tsfasman. Algebraic-geometric codes and asymptotic problems. Discrete Appl. Math., 33(1-3):241–256, 1991. Applied algebra, algebraic algorithms, and error-correcting codes (Toulouse, 1989).

[34] Michael A. Tsfasman and Serge G. Vlăduţ. Geometric approach to higher weights. IEEE Trans. Inform. Theory, 41(6, part 1):1564–1588, 1995. Special issue on algebraic geometry codes.

[35] Victor K. Wei. Generalized Hamming weights for linear codes. IEEE Trans. Inform. Theory, 37(5):1412–1418, 1991.

37