DocumentCode :
1215041
Title :
Intersecting codes and independent families
Author :
Cohen, Gerard D. ; Zemor, Gilles
Author_Institution :
Ecole Nat. Superieure des Telecommun., Paris, France
Volume :
40
Issue :
6
fYear :
1994
fDate :
11/1/1994 12:00:00 AM
Firstpage :
1872
Lastpage :
1881
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;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/18.340462
Filename :
340462
Link To Document :
بازگشت