On coding of underdetermined sequences with a fidelity criterion (Q845514)

Let \({\mathcal K}_n(l) \; (l \leq n),\) be the class of all sequences of length \(n\) with \(l\) Boolean symbols (0 and 1) and \(n - l\) indefinite symbols \(*,\) and let \(N_n(l)\) be the minimum cardinality of a set of sequences obtained from elements of \({\mathcal K}_n(l)\) by replacing all the indefinite symbols by Boolean symbols. \textit{E. I. Nechiporuk} [Dokl. Akad. Nauk SSSR 163, 40--42 (1965; Zbl 0139.11703)] has proved that \[ l\leq \text{log} N_n(l) \leq l+c \;\text{log} n \tag{1} \] The author calls this \textit{Nechiporuk effect.} The Nechiporuk effect was proved for underdetermined sequences of the general form by the author in [Probl. Kibern. 34, 133--150 (1978; Zbl 0415.94018) and Dokl. Akad. Nauk, Ross. Akad. Nauk 397, No. 2, 178--180 (2004; Zbl 1057.94009)]. In this paper (1) is extended to general underdetermined data. It is shown that the effect holds for coding with a fidelity criterion, where fidelity is understood in a rather broad sense.