Optimal superimposed codes and designs for Renyi's search model (Q5957831)

A binary matrix \(X=(x_i(u))_{{i=1,\ldots, N\atop u=1,\ldots, t}}\) is called a superimposed \((s,t,k)\)-code if the following conditions are fulfilled; the maximal row weight of \(X\) is equal to \(k\) and, for the Boolean sum \(b_s=\bigvee_{s_i\in S}s_i \)~ of any \(s\)-subset \(S\) of columns of \(X\), the equation \(b_s\vee y=b_s\) holds iff \(y\in S\); [cf. \textit{W. H. Kautz} and \textit{R. C. Singleton}, IEEE Trans. Inf. Theory 10, 363-377 (1964; Zbl 0133.12402) and the authors, Probl. Control Inf. Theory 12, 229-242 (1983; Zbl 0524.94016)]. The code \(X\) is called a superimposed \((s,t,k)\)-design if all \(b_s\) with \(|S|\leq s\) are distinct. The authors describe several families of superimposed \((s-1,t,k)\)-codes and \((s,t,k)\)-designs of length \(N\) fulfilling the bound \(N\geq\lceil\frac{st}{k}\rceil\) with equality. These structures are constructed from \((q,k,J)\)-homogeneous codes \(B\); these are codes over \(q\)-nary alphabets fulfilling \(n_j(a)=k\) (for the number \(n_j(a)\) of \(a\)-entries in the \(j\)th row) for any \(j=1,\ldots,J\) and any element \(a\) of the alphabet. A symbol \(b\) of \(B\) is replaced by the binary \(q\)-sequence in which all elements are \(0\) except for the element with number \(b\). This yields a matrix \(X_B\) which, under further conditions on \(B\), is an optimal superimposed code or design.