Almost cover-free codes |
| |
Authors: | N A Polyansky |
| |
Affiliation: | 1.Kharkevich Institute for Information Transmission Problems,Russian Academy of Sciences,Moscow,Russia;2.Probability Theory Department, Faculty of Mathematics and Mechanics,Lomonosov Moscow State University,Moscow,Russia |
| |
Abstract: | We say that an s-subset of codewords of a code X is (s, l)-bad if X contains l other codewords such that the conjunction of these l words is covered by the disjunction of the words of the s-subset. Otherwise, an s-subset of codewords of X is said to be (s, l)-bad. A binary code X is called a disjunctive (s, l) cover-free (CF) code if X does not contain (s, l)-bad subsets. We consider a probabilistic generalization of (s, l) CF codes: we say that a binary code is an (s, l) almost cover-free (ACF) code if almost all s-subsets of its codewords are (s, l)-good. The most interesting result is the proof of a lower and an upper bound for the capacity of (s, l) ACF codes; the ratio of these bounds tends as s→∞ to the limit value log2 e/(le). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|