Almost cover-free codes.
Saved in:
| Title: | Almost cover-free codes. |
|---|---|
| Authors: | Polyansky, N. nikitapolyansky@gmail.com |
| Source: | Problems of Information Transmission. Apr2016, Vol. 52 Issue 2, p142-155. 14p. |
| Subjects: | Information storage & retrieval systems -- Code words, Information processing, Binary codes, Conjunctions (Grammar), Set theory |
| 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 log e/( le). [ABSTRACT FROM AUTHOR] |
| Copyright of Problems of Information Transmission is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
