Source author record

Vladislav Shchukin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT math.PR

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Bounds on the rate of superimposed codes

A binary code is called a superimposed cover-free $(s,\ell)$ -code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of $\ell$ sets is covered by the union of $s$ others. A binary code is called a superimposed list-decoding $s_L$ -code if the code is identified by the incidence matrix of a family of finite sets in which the union of any $s$ sets can cover not more than $L-1$ other sets of the family. For $L=\ell=1$ , both of the definitions coincide and the corresponding binary code is called a superimposed $s$ -code. Our aim is to obtain new lower and upper bounds on the rate of given codes. The most interesting result is a lower bound on the rate of superimposed cover-free $(s,\ell)$ -code based on the ensemble of constant-weight binary codes. If parameter $\ell\ge1$ is fixed and $s\to\infty$ , then the ratio of this lower bound to the best known upper bound converges to the limit $2\,e^{-2}=0,271$ . For the classical case $\ell=1$ and $s\ge2$ , the given Statement means that our recurrent upper bound on the rate of superimposed $s$ -codes obtained in 1982 is attained to within a constant factor $a$ , $0,271\le a\le1$

preprint2015arXiv

Almost Cover-Free Codes and Designs

An $s$ -subset of codewords of a binary code $X$ is said to be an {\em $(s,\ell)$ -bad} in $X$ if the code $X$ contains a subset of other $\ell$ codewords such that the conjunction of the $\ell$ codewords is covered by the disjunctive sum of the $s$ codewords. Otherwise, the $s$ -subset of codewords of $X$ is said to be an {\em $(s,\ell)$ -good} in~ $X$ .mA binary code $X$ is said to be a cover-free $(s,\ell)$ -code if the code $X$ does not contain $(s,\ell)$ -bad subsets. In this paper, we introduce a natural {\em probabilistic} generalization of cover-free $(s,\ell)$ -codes, namely: a binary code is said to be an almost cover-free $(s,\ell)$ -code if {\em almost all} $s$ -subsets of its codewords are $(s,\ell)$ -good. We discuss the concept of almost cover-free $(s,\ell)$ -codes arising in combinatorial group testing problems connected with the nonadaptive search of defective supersets (complexes). 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.

preprint2015arXiv

Symmetric Disjunctive List-Decoding Codes

A binary code is said to be a disjunctive list-decoding $s_L$ -code (LD $s_L$ -code), $s \ge 2$ , $L \ge 1$ , if the code is identified by the incidence matrix of a family of finite sets in which the union (or disjunctive sum) of any $s$ sets can cover not more than $L-1$ other sets of the family. In this paper, we consider a similar class of binary codes which are based on a {\em symmetric disjunctive sum} (SDS) of binary symbols. By definition, the symmetric disjunctive sum (SDS) takes values from the ternary alphabet $\{0, 1, *\}$ , where the symbol~ $*$ denotes "erasure". Namely: SDS is equal to $0$ ( $1$ ) if all its binary symbols are equal to $0$ ( $1$ ), otherwise SDS is equal to~ $*$ . List decoding codes for symmetric disjunctive sum are said to be {\em symmetric disjunctive list-decoding $s_L$ -codes} (SLD $s_L$ -codes). In the given paper, we remind some applications of SLD $s_L$ -codes which motivate the concept of symmetric disjunctive sum. We refine the known relations between parameters of LD $s_L$ -codes and SLD $s_L$ -codes. For the ensemble of binary constant-weight codes we develop a random coding method to obtain lower bounds on the rate of these codes. Our lower bounds improve the known random coding bounds obtained up to now using the ensemble with independent symbols of codewords.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.