Almost cover-free codes and designs

Arkadii D’yachkov, Ilya Vorobyev, Nikita Polyanskii, Vladislav Shchukin

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


An s-subset of codewords of a binary code X is said to be (s,ℓ)-bad in X if the code X contains a subset of ℓ other codewords such that the conjunction of the ℓ codewords is covered by the disjunctive sum of the s codewords. Otherwise, the s-subset of codewords of X is called (s,ℓ)-good in X. A binary code X is said to be a cover-free (CF) (s,ℓ)-code if the code X does not contain (s,ℓ)-bad subsets. In this paper, we introduce a natural probabilistic generalization of CF (s,ℓ)-codes, namely: a binary code X is said to be an almost CF (s,ℓ)-code if the relative number of its (s,ℓ)-good s-subsets is close to 1. We develop a random coding method based on the ensemble of binary constant weight codes to obtain lower bounds on the capacity of such codes. Our main result shows that the capacity for almost CF (s,ℓ)-codes is essentially greater than the rate for ordinary CF (s,ℓ)-codes.

Original languageEnglish
Pages (from-to)231-247
Number of pages17
JournalDesigns, Codes, and Cryptography
Issue number1-2
Publication statusPublished - 1 Jan 2017
Externally publishedYes


  • Almost cover-free codes
  • Capacity
  • Designs
  • Random coding bound


Dive into the research topics of 'Almost cover-free codes and designs'. Together they form a unique fingerprint.

Cite this