Title :
Intersecting codes and independent families
Author :
Cohen, Gerard D. ; Zemor, Gilles
Author_Institution :
Ecole Nat. Superieure des Telecommun., Paris, France
fDate :
11/1/1994 12:00:00 AM
Abstract :
A binary intersecting code is a linear code with the property that any two nonzero codewords have intersecting supports. These codes appear in a wide variety of contexts and applications, e.g., multiple access, cryptography, and information theory. This paper is devoted partly to the study of intersecting codes, and partly to their use in constructing large t-independent families of binary vectors. The latter subject has by now been extensively studied and has application in VLSI testing, defect correction, E-biased probability spaces, and derandomization. By concatenation methods we construct codes with the highest known fate asymptotically. We then generalize the concept to t-wise intersecting codes: we give bounds on the achievable rate of such codes, both existential and constructive. We show how t-wise intersecting codes can be used to obtain (t+1)-independent families. With this method we obtain improved asymptotical constructions of t-independent families. Complexity issues are discussed
Keywords :
binary sequences; cryptography; information theory; linear codes; E-biased probability spaces; VLSI testing; asymptotical code constructions; binary intersecting code; binary vectors; code rate; concatenation methods; cryptograph; defect correction; derandomization; independent families; information theory; intersecting supports; linear code; multiple access; nonzero codewords; Circuit testing; Cryptography; Decoding; Linear code; Parity check codes; Protocols; Terminology; Very large scale integration;
Journal_Title :
Information Theory, IEEE Transactions on