Multiple-Error-Correcting Codes for
Analog Computing on Resistive Crossbars

Hengjia Wei and Ron M. Roth Hengjia Wei is with the Peng Cheng Laboratory, Shenzhen 518055, China (e-mail: [email protected]). He is also with the School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an 710049, China, and the Pazhou Laboratory (Huangpu), Guangzhou 510555, China.Ron M. Roth is with the Computer Science Department, Technion––Israel Institute of Technology, Haifa 3200003, Israel (e-mail: [email protected]).The work of H. Wei was supported in part by the major key project of Peng Cheng Laboratory under grant PCL2023AS1-2 and the National Natural Science Foundation of China under Grant 12371523. The work of R. M. Roth was supported in part by Grant No. 1713/20 from the Israel Science Foundation.

Abstract

Error-correcting codes over the real field are studied which can locate outlying computational errors when performing approximate computing of real vector–matrix multiplication on resistive crossbars. Prior work has concentrated on locating a single outlying error and, in this work, several classes of codes are presented which can handle multiple errors. It is first shown that one of the known constructions, which is based on spherical codes, can in fact handle multiple outlying errors. A second family of codes is then presented with ${0\textrm{--}1}$ parity-check matrices which are sparse and disjunct; such matrices have been used in other applications as well, especially in combinatorial group testing. In addition, a certain class of the codes that are obtained through this construction is shown to be efficiently decodable. As part of the study of sparse disjunct matrices, this work also contains improved lower and upper bounds on the maximum Hamming weight of the rows in such matrices.

Index Terms:

Fault-tolerant computing, linear codes over the real field, vector–matrix multiplication, sparse group testing, disjunct matrices with limited row weights

I Introduction

Vector–matrix multiplication is a computational task that is found in numerous applications, including machine learning (e.g., deep learning) and signal processing. Designing circuits for vector–matrix multiplication requires achieving high computational throughput while concurrently ensuring minimal energy consumption and a compact physical footprint. These criteria have prompted recent proposals to incorporate resistive memory technology into analog computing architectures.

Let ${\mathbf{u}}$ be a row $\ell$ -vector and $A$ be an $\ell\times n$ matrix—both with (nonnegative) entries in $\mathbb{R}$ or $\mathbb{Z}$ . In current implementations of vector–matrix multiplication [1],[9],[10],[14],[22], the matrix $A=(a_{i,j})$ is realized as a crossbar of $\ell$ row conductors and $n$ column conductors with programmable nano-scale resistors at the junctions. The resistor at the junction $(i,j)$ is set to have conductance that is proportional to the entry $a_{i,j}$ of $A$ . Each entry $u_{i}$ of ${\mathbf{u}}$ is converted into a voltage level that is proportional to $u_{i}$ and fed to the corresponding row conductor. Then the product ${\mathbf{c}}={\mathbf{u}}A$ , carried out over the real field $\mathbb{R}$ , can be computed by reading the currents at the column conductors. Negative entries in ${\mathbf{u}}$ or $A$ can be accommodated by duplication of the circuit.

Recently, the second author proposed two classes of coding schemes to locate computational errors under two distinct scenarios: exact integer vector–matrix multiplication [18] and approximate real vector–matrix multiplication [19]. We next describe the second scenario, as it will be the subject of this work as well.

In the model described in [19], the ideal computation ${\mathbf{c}}={\mathbf{u}}A\in\mathbb{R}^{n}$ may be distorted by two types of errors, which lead to a read vector

{\mathbf{y}}={\mathbf{c}}+\boldsymbol{\varepsilon}+{\mathbf{e}}\in\mathbb{R}^{n},

(1)

where ${\mathbf{e}},\boldsymbol{\varepsilon}\in\mathbb{R}^{n}$ . The entries of $\boldsymbol{\varepsilon}$ are all within the interval $[-\delta,\delta]$ for some prescribed threshold $\delta$ , representing small computational errors that are tolerable, while the entries of ${\mathbf{e}}$ represent outlying errors that may be caused by events such as stuck cells or short cells in the array (and may have large magnitudes). The goal is to design a coding scheme that allows to locate all the non-zero entries of ${\mathbf{e}}$ that are outside an interval $[-\Delta,\Delta]$ , for the smallest $\Delta$ , provided that the number of outlying errors does not exceed a prescribed number $\tau$ . A more general setting includes the option of detecting $\sigma$ additional errors and, as shown in [19], in this case the value ${\lambda}=2\tau+\sigma$ plays a role when analyzing the correction capability of a coding scheme.

The encoding scheme presented in [19] can be characterized by a linear $[n,k]$ code ${\mathcal{C}}$ over $\mathbb{R}$ : we allocate $r=n-k$ columns of the matrix $A$ for redundancy so that each row of $A$ forms a codeword of ${\mathcal{C}}$ . Then the result of the multiplication of any input real row vector ${\mathbf{u}}$ by the matrix $A$ is also a codeword of ${\mathcal{C}}$ .

In crude terms (with more details to be provided in Section II), the required condition from the linear code ${\mathcal{C}}$ is that it has a decoder that locates all the outlying errors of magnitude above $\Delta$ , whenever the Hamming weight of ${\mathbf{e}}$ does not exceed $\tau$ ; moreover, if the decoder returns a set of locations (rather than just detects errors), then ${\mathbf{e}}$ should be nonzero at all these locations. Linear codes over $\mathbb{R}$ which satisfy this condition are referred to as analog error-correcting codes.

For the case ${\lambda}=2\tau+\sigma\leqslant 2$ (which includes the single error location/detection cases, i.e., $(\tau,\sigma)=(0,1),(1,0)$ ), code constructions were proposed in [19] for several trade-offs between the redundancy $r$ and the smallest attainable ratio $\Delta/\delta$ . One of the constructions for ${\lambda}=2$ has a sparse parity-check matrix over $\{-1,0,1\}$ and attains $\Delta/\delta\leqslant 2\lceil 2n/r\rceil$ , for every even redundancy $r\geqslant\sqrt{n}$ ; another construction has a parity-check matrix that forms a spherical code and attains $\Delta/\delta=O(n/\sqrt{r})$ with $r=\Theta(\log n)$ .

In this work, we present several classes of codes over $\mathbb{R}$ for a wide range of values ${\lambda}$ , and compute upper bounds on the attainable ratios $\Delta/\delta$ , in terms of $n$ , $r$ , and ${\lambda}$ ; see Table I. When ${\lambda}=2$ , our bounds coincide with those presented in [19],[20]. One of the classes is actually the spherical code scheme of [19] when constructed with redundancy $r=\Theta({\lambda}^{2}\log n)$ : we show that these codes can still attain $\Delta/\delta=O(n/\sqrt{r})$ yet for a wide range of ${\lambda}\geqslant 2$ . In our analysis we make use of the restricted isometry property (and a variant thereof) of matrices of low coherence—a tool which is widely used in compressed sensing [2],[3].

A second class of codes to be presented is based on disjunct matrices with limited row weights—a notion that has been applied, inter alia, in combinatorial group testing [11]. Employing the known construction of disjunct matrices of [11], for any $n,\ell,{\lambda}\in\mathbb{Z}^{+}$ such that $n^{1/(\ell+1)}$ is a prime power and ${\lambda}\leqslant\lceil n^{1/(\ell+1)}/\ell\rceil$ , our codes attain $\Delta/\delta\leqslant 2n^{\ell/(\ell+1)}$ with $r\leqslant\ell{\lambda}n^{1/(\ell+1)}$ .

Our study also includes a new family of disjunct matrices (which, in turn, can then be employed in our code construction mentioned above). Specifically, for any positive integer $\rho\leqslant\sqrt{n}$ such that $n/\rho$ is a prime power, we construct optimal disjunct matrices with maximum row weight ${}\leqslant\rho$ , achieving the lower bound on the number of rows as stated in [11]; formerly, such disjunct matrices were exclusively established for $\rho=\sqrt{n}$ . Moreover, by deriving a new lower bound on the number of rows, we show that the construction in [11] of disjunct matrices with maximum row weight $\rho\geqslant\sqrt{n}$ is asymptotically optimal.

The paper is organized as follows. We begin, in Section II, by providing notation and known results used throughout the paper. This section also contains our new lower bound on the number of rows of a disjunct matrix with limited row weights.

In Section III, we analyze the spherical code construction and establish its performance for a wide range of values ${\lambda}$ .

In Section IV, we present the code construction that is based on disjunct matrices with limited row weights. Efficient decoding algorithms to locate the outlying errors are also presented.

In Section V, we present our new family of optimal disjunct matrices. Employing these matrices in our code construction, for any (fixed) rational number $\alpha\in[1/2,1)$ they attain $r\leqslant{\lambda}n^{\alpha}$ and $\Delta/\delta\leqslant 2{\lambda}n/r$ for infinitely many values of $n$ . Interestingly, these parameters align with those of the single-error-correcting codes in [19] (wherein $r$ can be any even integer such that $r(r-1)\geqslant n$ and $\Delta/\delta\leqslant 2\lceil 2n/r\rceil$ ).

TABLE I: Summary of the

[n,k{\geqslant}n{-}r]

codes

{\mathcal{C}}

over

\mathbb{R}

$\displaystyle r$	Attainable $\displaystyle\Delta/\delta$	$\displaystyle{\lambda}$	Comments	Reference
$\displaystyle\Theta(\log n)$	$\displaystyle O\left\lparen\frac{n}{\sqrt{r}}\right\rparen$	$\displaystyle 2$		Prop. 5 in [20]
$\displaystyle\Theta({\lambda}^{2}\log n)$	$\displaystyle O\left\lparen\frac{n}{\sqrt{r}}\right\rparen$	$\displaystyle O\left\lparen\sqrt{\frac{n}{\log n}}\right\rparen$		Cor. 14
$\displaystyle r\leqslant n\leqslant r(r-1)$	$\displaystyle 2\left\lceil\frac{2n}{r}\right\rceil$	$\displaystyle 2$		Prop. 6 in [19]
$\displaystyle\frac{{\lambda}n}{\rho}$	$\displaystyle\frac{2{\lambda}n}{r}$	$\displaystyle{\lambda}\leqslant\rho$	$\displaystyle\rho\in\mathbb{Z}^{+}$ , $\displaystyle\rho\leqslant\sqrt{n}$ , $\displaystyle\frac{n}{\rho}$ is a prime power	Cor. 25
$\displaystyle\frac{{\lambda}n}{\rho}$	$\displaystyle\frac{2{\lambda}n}{r}$	$\displaystyle{\lambda}\leqslant\min\{\rho,p_{1}^{e_{1}},p_{2}^{e_{2}},\ldots\}$	$\displaystyle\rho\in\mathbb{Z}^{+}$ , $\displaystyle\rho\leqslant\sqrt{n}$ , $\displaystyle\frac{n}{\rho}=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots$	Thm. 27
$\displaystyle(\ell{\lambda}-\ell+1)q$	$\displaystyle\frac{2(\ell{\lambda}-\ell+1)n}{r}$	$\displaystyle{\lambda}\leqslant\lceil q/\ell\rceil$	$\displaystyle\ell\in\mathbb{Z}^{+}$ , $\displaystyle q$ is a prime power, $\displaystyle n=q^{\ell+1}$	Cor. 16

II Preliminaries

For integers $\ell\leqslant n$ , we denote by $[\ell:n]$ the integer subset $\left\{z\in\mathbb{Z}\,:\,\ell\leqslant z<n\right\}$ . We will use the shorthand notation ${\left[{n}\right]}$ for ${\left[{0:n}\right]}$ , and we will typically use ${\left[{n}\right]}$ to index the entries of vectors in $\mathbb{R}^{n}$ . Similarly, the entries of an $r\times n$ matrix $H=(H_{i,j})$ will be indexed by $(i,j)\in{\left[{r}\right]}\times{\left[{n}\right]}$ , and $H_{i}$ and ${\mathbf{h}}_{j}$ will denote, respectively, row $i$ and column $j$ in $H$ . For a subset ${\mathcal{J}}\subseteq{\left[{n}\right]}$ , the notation $(H)_{\mathcal{J}}$ stands for the $r\times\lvert{\mathcal{J}}\rvert$ submatrix of $H$ that is formed by the columns that are indexed by ${\mathcal{J}}$ .

Unless specified otherwise, all logarithms are taken to base $2$ .

II-A Analog error-correcting codes

Given $\delta,\Delta\in\mathbb{R}^{+}$ , let

{\mathcal{Q}}(n,\delta)\triangleq\left\{\boldsymbol{\varepsilon}=(\varepsilon_{j})\in\mathbb{R}^{n}\,:\,\lVert\boldsymbol{\varepsilon}\rVert_{\infty}\leqslant\delta\right\}

be the set of all tolerable error vectors with threshold $\delta$ , where $\lVert\boldsymbol{\varepsilon}\rVert_{\infty}$ stands for the infinity norm $\max_{j\in{\left[{n}\right]}}\lvert\varepsilon_{j}\rvert$ . For ${\mathbf{e}}=(e_{j})_{j}\in\mathbb{R}^{n}$ , define

{\mathsf{Supp}}_{\Delta}({\mathbf{e}})\triangleq\left\{j\in{\left[{n}\right]}\,:\,\lvert e_{j}\rvert>\Delta\right\}.

In particular, ${\mathsf{Supp}}_{0}({\mathbf{e}})$ is the ordinary support of ${\mathbf{e}}$ . We use ${\mathsf{w}}({\mathbf{e}})$ to denote the Hamming weight of ${\mathbf{e}}$ . The set of all vectors of Hamming weight at most $w$ in $\mathbb{R}^{n}$ is denoted by ${\mathcal{B}}(n,w)$ .

Let ${\mathcal{C}}$ be a linear $[n,k]$ code over $\mathbb{R}$ . A decoder for ${\mathcal{C}}$ is a function ${\mathcal{D}}:\mathbb{R}^{n}\rightarrow 2^{{\left[{n}\right]}}\cup\{{\mathrm{``e"}}\}$ which returns a set of locations of outlying errors or an indication ${\mathrm{``e"}}$ that errors have been detected. Given $\delta,\Delta\in\mathbb{R}^{+}$ and prescribed nonnegative integers $\tau$ and $\sigma$ , we say that the decoder ${\mathcal{D}}$ corrects $\tau$ errors and detects $\sigma$ additional errors with respect to the threshold pair $(\delta,\Delta)$ , or that ${\mathcal{D}}$ is a $(\tau,\sigma)$ -decoder for $({\mathcal{C}},\Delta:\delta)$ , if the following conditions hold for every ${\mathbf{y}}$ as in (1), where ${\mathbf{c}}\in{\mathcal{C}}$ , $\boldsymbol{\varepsilon}\in{\mathcal{Q}}(n,\delta)$ , and ${\mathbf{e}}\in{\mathcal{B}}(n,\tau+\sigma)$ .

(D1): If ${\mathbf{e}}\in{\mathcal{B}}(n,\tau)$ then ${\mathrm{``e"}}\neq{\mathcal{D}}({\mathbf{y}})\subseteq{\mathsf{Supp}}_{0}({\mathbf{e}})$ .
(D2): If ${\mathcal{D}}({\mathbf{y}})\neq{\mathrm{``e"}}$ then ${\mathsf{Supp}}_{\Delta}({\mathbf{e}})\subseteq{\mathcal{D}}({\mathbf{y}})$ .

Let ${\mathbf{x}}=(x_{j})_{j\in{\left[{n}\right]}}$ be a nonzero vector in $\mathbb{R}^{n}$ and let $\pi$ be a permutation on ${\left[{n}\right]}$ such that

\lvert x_{\pi(0)}\rvert\geqslant\lvert x_{\pi(1)}\rvert\geqslant\cdots\geqslant\lvert x_{\pi(n-1)}\rvert.

Given an integer ${\lambda}\in{\left[{n}\right]}$ , the ${\lambda}$ -height of ${\mathbf{x}}$ , denoted by ${\mathsf{h}}_{\lambda}({\mathbf{x}})$ , is defined as

{\mathsf{h}}_{\lambda}({\mathbf{x}})\triangleq\left\lvert\frac{x_{\pi(0)}}{x_{\pi({\lambda})}}\right\rvert,

and we formally define ${\mathsf{h}}_{n}({\mathbf{x}})\triangleq\infty$ . For a linear code ${\mathcal{C}}\neq\{{\mathbf{0}}\}$ over $\mathbb{R}$ , its ${\lambda}$ -height, denoted by ${\mathsf{h}}_{\lambda}({\mathcal{C}})$ , is defined by

{\mathsf{h}}_{\lambda}({\mathcal{C}})\triangleq\max_{{\mathbf{c}}\in{\mathcal{C}}\setminus\{{\mathbf{0}}\}}{\mathsf{h}}_{\lambda}({\mathbf{c}}).

The minimum Hamming distance of ${\mathcal{C}}$ , denoted by ${\mathsf{d}}({\mathcal{C}})$ , can be related to $({\mathsf{h}}_{\lambda}({\mathcal{C}}))_{\lambda}$ by

{\mathsf{d}}({\mathcal{C}})=\min\{{\lambda}\in{\left[{n+1}\right]}\,:\,{\mathsf{h}}_{\lambda}({\mathcal{C}})=\infty\}.

(2)

Theorem 1 ([19],[21]).

Let ${\mathcal{C}}$ be a linear $[n,k]$ code over $\mathbb{R}$ . There is a $(\tau,\sigma)$ -decoder for $({\mathcal{C}},\Delta:\delta)$ , if and only if

\Delta/\delta\geqslant 2\,{\mathsf{h}}_{2\tau+\sigma}({\mathcal{C}})+2.

Theorem 1 motivated in [19] to define for every ${\lambda}\in{\left[{n+1}\right]}$ the expression

\Gamma_{\lambda}({\mathcal{C}})\triangleq 2\,{\mathsf{h}}_{\lambda}({\mathcal{C}})+2,

(3)

so that $\Gamma_{2\tau+\sigma}({\mathcal{C}})$ is the smallest ratio $\Delta/\delta$ for which there is a $(\tau,\sigma)$ -decoder for $({\mathcal{C}},\Delta:\delta)$ . Equivalently, $\Gamma_{2\tau+\sigma}$ is the smallest $\Delta$ such that there is a $(\tau,\sigma)$ -decoder for $({\mathcal{C}},\Delta:1)$ . Thus, given $n$ and ${\lambda}$ , our aim is to construct linear codes ${\mathcal{C}}$ over $\mathbb{R}$ with both $\Gamma_{\lambda}({\mathcal{C}})$ and redundancy $r$ as small as possible.

For the case ${\lambda}=2\tau+\sigma\leqslant 2$ , a characterization of $\Gamma_{1}({\mathcal{C}})$ and $\Gamma_{2}({\mathcal{C}})$ was presented in [19] in terms of the parity-check matrix of ${\mathcal{C}}$ . In the next proposition, we present a generalization of that characterization to any ${\lambda}\in{\left[{1:{\mathsf{d}}({\mathcal{C}})}\right]}$ . Given a parity-check matrix $H$ of ${\mathcal{C}}$ over $\mathbb{R}$ , let

{\mathcal{S}}={\mathcal{S}}(H)\triangleq\left\{H\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\,:\,\boldsymbol{\varepsilon}\in{\mathcal{Q}}(n,1)\right\}

(4)

and

	$\displaystyle 2{\mathcal{S}}\triangleq{\mathcal{S}}+{\mathcal{S}}$	$\displaystyle=$	$\displaystyle\left\{H(\boldsymbol{\varepsilon}+\boldsymbol{\varepsilon}^{\prime})^{\top\scriptscriptstyle{\!}}\,:\,\boldsymbol{\varepsilon},\boldsymbol{\varepsilon}^{\prime}\in{\mathcal{Q}}(n,1)\right\}$
		$\displaystyle=$	$\displaystyle\left\{H\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\,:\,\boldsymbol{\varepsilon}\in{\mathcal{Q}}(n,2)\right\}.$

Note that ${\mathcal{S}}$ is the set of all the syndrome vectors (with respect to $H$ ) that can be obtained when there are no outlying errors, assuming that $\delta=1$ . Also, for $\Delta\in\mathbb{R}^{+}$ let

{\mathcal{B}}_{\Delta}(n,{\lambda})\triangleq\left\{{\mathbf{e}}\in{\mathcal{B}}(n,{\lambda})\,:\,\lVert{\mathbf{e}}\rVert_{\infty}>\Delta\right\},

(6)

i.e., ${\mathcal{B}}_{\Delta}(n,{\lambda})$ consists of all the vectors ${\mathbf{e}}\in\mathbb{R}^{n}$ such that both ${\mathsf{w}}({\mathbf{e}})\leqslant{\lambda}$ and ${\mathsf{Supp}}_{\Delta}({\mathbf{e}})\neq\varnothing$ .

Proposition 2.

Given a linear $[n,k{>}0]$ code ${\mathcal{C}}$ over $\mathbb{R}$ , let $H$ be a parity-check matrix of ${\mathcal{C}}$ and let ${\lambda}\in{\left[{1:{\mathsf{d}}({\mathcal{C}})}\right]}$ . Then

\Gamma_{\lambda}({\mathcal{C}})=\min\bigl{\{}\Delta\in\mathbb{R}^{+}:\,H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\notin 2{\mathcal{S}}\;\;\textrm{for all ${\mathbf{e}}\in{\mathcal{B}}_{\Delta}(n,{\lambda})$}\bigr{\}}.

(7)

Proof:

We first show that $\Delta^{*}\triangleq\Gamma_{\lambda}({\mathcal{C}})$ is contained in the minimand set in (7). Assume to the contrary that there is a vector ${\mathbf{e}}\in{\mathcal{B}}_{\Delta^{*}}(n,{\lambda})$ such that $H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\in 2{\mathcal{S}}$ , namely, $H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}=H\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}$ for some $\boldsymbol{\varepsilon}\in{\mathcal{Q}}(n,2)$ . Then ${\mathbf{e}}-\boldsymbol{\varepsilon}\in{\mathcal{C}}$ and, so,

{\mathsf{h}}_{\lambda}({\mathcal{C}})\geqslant{\mathsf{h}}_{\lambda}({\mathbf{e}}-\boldsymbol{\varepsilon})\geqslant\frac{\lVert{\mathbf{e}}\rVert_{\infty}-2}{2}>\frac{\Delta^{*}-2}{2}.

This, in turn, implies

\Gamma_{\lambda}({\mathcal{C}})\stackrel{{\scriptstyle\textrm{\scriptsize\eqref{eq:defGamma}}}}{{=}}2\,{\mathsf{h}}_{\lambda}({\mathcal{C}})+2>\Delta^{*},

which is a contradiction.

We next show that $\Gamma_{\lambda}({\mathcal{C}})$ is indeed the minimum of the set in (7). Assuming to the contrary that this set contains some $\Delta<\Gamma_{\lambda}({\mathcal{C}})$ , there is a nonzero codeword ${\mathbf{c}}\in{\mathcal{C}}$ such that

{\mathsf{h}}_{\lambda}({\mathbf{c}})>\frac{\Delta-2}{2}.

Without loss of generality we can assume that

c_{0}\geqslant\lvert c_{1}\rvert\geqslant\lvert c_{2}\rvert\geqslant\cdots\geqslant\lvert c_{n-1}\rvert,

where $\lvert c_{\lambda}\rvert=2$ and (thus) $c_{0}>\Delta-2$ . Define the vectors ${\mathbf{e}},\boldsymbol{\varepsilon}\in\mathbb{R}^{n}$ as follows:

\begin{array}[]{ccc@{\!\;}ccccccccc@{\!\;}cc}{\mathbf{e}}&=&(&c_{0}{+}2&c_{1}&c_{2}&\ldots&c_{{\lambda}-1}&0&0&\ldots&0&)&,\\ \boldsymbol{\varepsilon}&=&(&-2&0&0&\ldots&0&c_{\lambda}&c_{{\lambda}+1}&\ldots&c_{n-1}&)&.\end{array}

Then ${\mathbf{c}}={\mathbf{e}}+\boldsymbol{\varepsilon}$ and $\boldsymbol{\varepsilon}\in{\mathcal{Q}}(n,2)$ , namely, $H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}=-H\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\in 2{\mathcal{S}}$ . On the other hand ${\mathbf{e}}\in{\mathcal{B}}_{\Delta}(n,{\lambda})$ , which means that $\Delta$ is not in the minimand in (7), thereby reaching a contradiction.

Propositions 9 and 8 in [19] are special cases of Proposition 2 for ${\lambda}=1$ and ${\lambda}=2$ , respectively. Proposition 2 holds (vacuously) also when ${\lambda}\geqslant{\mathsf{d}}({\mathcal{C}})$ : in this case the minimand in (7) is empty (since ${\mathcal{C}}$ contains nonzero codewords in ${\mathcal{B}}(n,{\lambda})$ with arbitrary infinity norms), while $\Gamma_{\lambda}({\mathcal{C}})=\infty$ (from (2)).

We end this subsection by mentioning two of the constructions for ${\lambda}=2$ that were presented in [19].

Theorem 3 ([19, Proposition 6]).

Let $H$ be an $r\times n$ matrix over $\{-1,0,1\}$ which satisfies the following three conditions:

1.

all columns of $H$ are distinct,
2.

each column in $H$ contains exactly two nonzero entries, the first of which being a $1$ , and
3.

each row has Hamming weight $\lfloor 2n/r\rfloor$ or $\lceil 2n/r\rceil$ .

(In particular, these conditions require that $n\leqslant r(r-1)$ .) The linear $[n,k{\geqslant}n{-}r]$ code ${\mathcal{C}}$ over $\mathbb{R}$ with a parity-check matrix $H$ satisfies $\Gamma_{2}({\mathcal{C}})\leqslant 2\cdot\lceil 2n/r\rceil$ .

When $r$ is even, the inequality $n\leqslant r(r{-}1)$ is also sufficient for having a matrix $H$ that satisfies the conditions of the theorem [12].

A second construction is presented in [19] that is based on spherical codes. The construction will be recapped in Section III, and the next theorem summarizes its properties.

Theorem 4 ([20, Proposition 5]).

There exists a linear $[n,k{=}n{-}r]$ code ${\mathcal{C}}$ over $\mathbb{R}$ with $\Gamma_{2}({\mathcal{C}})=O(n/\sqrt{r})$ , whenever $r/\log n$ is bounded away from (above) $1$ .

II-B Disjunct matrices

Let $n,r\in\mathbb{Z}^{+}$ and let $D\in{\left[{n}\right]}$ . An $r\times n$ matrix $H=(H_{i,j})$ over $\{0,1\}$ is called $D$ -disjunct if the union of the supports of any $D$ columns of $H$ does not contain the support of any other column. In other words, for any column index $j\in{\left[{n}\right]}$ and a subset ${\mathcal{J}}\subseteq{\left[{n}\right]}\setminus\{j\}$ of $D$ additional column indexes there is a row index $i\in{\left[{r}\right]}$ such that $H_{i,j}=1$ while $H_{i,j^{\prime}}=0$ for all $j^{\prime}\in{\mathcal{J}}$ . (Equivalently, every $r\times(D+1)$ submatrix of $H$ contains $D+1$ rows that form the identity matrix.)

A $(D,\rho)$ -disjunct matrix is a $D$ -disjunct matrix whose rows all have weights bounded from above by $\rho\in\mathbb{Z}^{+}$ .

Disjunct matrices play a crucial role in the area of group testing, which studies how to identify a set of at most $D$ positive items from a batch of $n$ total items. The basic strategy of group testing is to group the items into several tests, i.e., some subsets of items. In each test, a positive outcome indicates that at least one of the items included in this test is positive and a negative outcome indicates that all items included are negative. A disjunct matrix $H$ describes a nonadaptive group testing scheme: we use the tests to index the rows and use items to index the columns. Then the $i$ th test contains the $j$ th item if and only if $H_{i,j}=1$ . It is not very difficult to see that the $D$ -disjunct property ensures that this testing scheme can identify all the positive items as long as their number is at most $D$ .

The first explicit construction of disjunct matrices was proposed by Kautz and Singleton [13]. Their construction uses a Reed–Solomon (RS) outer code concatenated with binary unit vectors and requires $r=O(D^{2}\log_{D}^{2}n)$ tests, which matches the best known lower bound, $\Omega(D^{2}\log_{D}n)$ , in [7],[8] when $D=\Theta(n^{\alpha})$ for some fixed $\alpha\in(0,1)$ . Subsequently, Porat and Rothschild [17] proposed another explicit construction, which is similar to the Kautz–Singleton construction but uses a code meeting the Gilbert–Varshamov (G–V) bound as the outer code. Their construction achieves $r=O(D^{2}\log n)$ and outperforms the Kautz–Singleton construction in the regime where $D=O({\mathrm{poly}}(\log n))$ .

More recently, motivated by practical applications in group testing and wireless communication, Inan et al. investigated disjunct matrices with constraints on either the maximal row weight (i.e, $(D,\rho)$ -disjunct matrices) or the maximal column weight [11]. In the context of this paper, we focus on $(D,\rho)$ -disjunct matrices and demonstrate in Section IV that $(D,\rho)$ -disjunct matrices can be used to construct analog error-correcting codes.

Inan et al. first examined the Kautz–Singleton construction and the Porat–Rothschild construction and computed the maximum row weight $\rho$ of the corresponding disjunct matrices.

Theorem 5 ([11, Theorems 2 and 3]).

The Kautz–Singleton construction yields a $(D,\rho)$ -disjunct $r\times n$ matrix with constant row weight $\rho=n/\sqrt{r}$ and

r=O\left\lparen\left\lparen\frac{D\log n}{\log(D\log n)}\right\rparen^{2}\right\rparen.

The Porat–Rothschild construction yields a $(D,\rho)$ -disjunct $r\times n$ matrix where $\rho=\Omega(n/D)$ and $r=O(D^{2}\log n)$ .

In the Porat–Rothschild construction, the number of rows, $r=O(D^{2}\log n)$ , meets the lower bound $\Omega(D^{2}\log_{D}n)$ when $D$ is fixed. The following result shows that in a $(D,\rho)$ -disjunct matrix with $r=O(\log n)$ rows one must have $\rho=\Theta(n)$ ; so, in a regime where $D$ is fixed, both $r$ and $\rho$ in the Porat–Rothschild construction meet their respective lower bounds.

Lemma 6.

Let $H$ be a $(D,\rho)$ -disjunct $r\times n$ matrix, where $r\leqslant a\log n$ for some fixed $a$ . Then $\rho=\Theta(n)$ .

Proof:

Since $H$ is $D$ -disjunct, it cannot contain two identical columns and, so, $a\geqslant 1$ . Let $\alpha\in\left\lparen 0,1/2\right\rparen$ be such that $h(\alpha)=1/(2a)$ , where $h(\cdot)$ is the binary entropy function. Then

\sum_{i=0}^{\lfloor\alpha r\rfloor}\binom{r}{i}\leqslant 2^{rh(\alpha)}\leqslant\sqrt{n}.

Hence, there are at least $n-\sqrt{n}$ columns in $H$ each of which has weight at least $\alpha r$ . By counting the number of $1$ s in $H$ , we get that

r\rho\geqslant(n-\sqrt{n})(\alpha r),

which implies that $\rho\geqslant(n-\sqrt{n})\alpha$ .

Inan et al. proved the following generic lower bound on the number of rows of a $(D,\rho)$ -disjunct matrix.

Theorem 7 ([11, Theorem 8]).

A $(D,\rho)$ -disjunct $r\times n$ matrix must satisfy

r\geqslant\begin{cases}\displaystyle\frac{(D+1)n}{\rho},&\textrm{if $\rho>D+1$,}\\ \;n,&\textrm{if $\rho\leqslant D+1$.}\end{cases}

They also modified the Kautz–Singleton construction by changing the dimension of the outer RS code and obtained the following result.

Theorem 8 ([11, Theorem 8]).

Let $\ell\in\mathbb{Z}^{+}$ , let $q$ be a prime power, and set

n=q^{\ell+1}\quad\textrm{and}\quad\rho=q^{\ell}=n^{\ell/(\ell+1)}.

Also, let $D\in\mathbb{Z}^{+}$ be such that $\ell D+1\leqslant q$ . The Kautz–Singleton construction yields a $(D,\rho)$ -disjunct $r\times n$ matrix with constant row weight $\rho$ and

r=(\ell D+1)\cdot q=\frac{(\ell D+1)n}{\rho}.

Substituting $\ell=1$ in Theorem 8 yields a construction for $\rho=\sqrt{n}$ with $r=(D+1)n/\rho$ , which, in view of Theorem 7, is optimal with respect to $r$ . In Section V, for any $\rho\leqslant\sqrt{n}$ such that $n/\rho$ is a prime power, we construct optimal $(D,\rho)$ -disjunct matrices with number of rows $r=(D+1)n/\rho$ .

We end this section with a new lower bound on the number of rows of $(D,\rho)$ -disjunct matrices; this bound, in turn, will imply that for any (fixed) $\ell\geqslant 2$ , the matrices in Theorem 8 are asymptotically optimal when $D=o\bigl{(}n^{1/(\ell(\ell+1))}\bigr{)}$ . We use the following terms (as defined in the proof of Theorem 4 in [11]). In an $r\times n$ binary matrix $H=({\mathbf{h}}_{j})_{j\in{\left[{n}\right]}}$ , a row $i\in[r]$ is said to be private for a column $j\in{\left[{n}\right]}$ if row $i$ contains a $1$ only at column $j$ . Similarly, a private set for column $j$ is defined as a subset ${\mathcal{R}}\subseteq{\mathsf{Supp}}_{0}({\mathbf{h}}_{j})$ such that ${\mathcal{R}}\not\subseteq{\mathsf{Supp}}_{0}({\mathbf{h}}_{j^{\prime}})$ for any $j^{\prime}\in{\left[{n}\right]}\setminus\{j\}$ .

Theorem 9.

Let $n,\ell,D,\rho\in\mathbb{Z}^{+}$ be such that $\rho\geqslant\ell D+1$ . Any $(D,\rho)$ -disjunct $r\times n$ matrix must satisfy

r\geqslant\frac{\ell D+1}{\rho}\left\lparen n-\max\left\{\binom{r}{\ell},\binom{2\ell}{\ell}\right\}\right\rparen.

In particular, if $\max\{\binom{r}{\ell},\binom{2\ell}{\ell}\}=o(n)$ , then

r\geqslant\frac{(\ell D+1)n}{\rho}\cdot(1-o(1)).

Proof:

Let $H$ be a $(D,\rho)$ -disjunct $r\times n$ matrix where $\rho\geqslant\ell D+1$ . Consider the columns that have weight ${}\leqslant D$ and denote their number by $n_{1}$ . Since $H$ is $D$ -disjunct, each of these columns must have a private row; hence, $n_{1}\leqslant r$ . Remove these columns along with the corresponding private rows and let $H^{\prime}$ be the resulting $(r-n_{1})\times(n-n_{1})$ matrix. Clearly, $H^{\prime}$ is $(D,\rho)$ -disjunct and each column in $H^{\prime}$ has weight ${}\geqslant D+1\geqslant\ell$ .

Next, consider the columns of $H^{\prime}$ that have weight ${}\leqslant\ell D$ and denote their number by $n_{2}$ . Since $H^{\prime}$ is $D$ -disjunct, each of these columns must have a private set of size at most $\ell$ . Note that these private sets cannot be nested. If $2\ell\leq r-n_{1}$ , it follows from the Lubell–Yamamoto–Meshalkin inequality (see [15]) that $n_{2}\leqslant\binom{r-n_{1}}{\ell}\leqslant\binom{r}{\ell}$ ; if $2\ell>r-n_{1}$ , it follows from Sperner’s theorem that $n_{2}\leqslant\binom{r-n_{1}}{\lfloor(r-n_{1})/2\rfloor}\leqslant\binom{2\ell}{\ell}$ . Hence, $n_{2}\leq\max\{\binom{r}{\ell},\binom{2\ell}{\ell}\}$ . We remove these $n_{2}$ columns from $H^{\prime}$ and count the number of $1$ s in the resulting matrix in two ways; doing so, we get

(n-n_{1}-n_{2})(\ell D+1)\leqslant(r-n_{1})\rho,

which implies that

$\displaystyle r\rho$	$\displaystyle\geqslant$	$\displaystyle(n-n_{2})(\ell D+1)+n_{1}(\rho-(\ell D+1))$
	$\displaystyle\geqslant$	$\displaystyle(n-n_{2})(\ell D+1)$
	$\displaystyle\geqslant$	$\displaystyle\left\lparen n-{\max\left\{\binom{r}{\ell},\binom{2\ell}{\ell}\right\}}\right\rparen(\ell D+1).$

Taking $\ell$ fixed and $D=o\bigl{(}n^{1/(\ell(\ell+1))}\bigr{)}$ , we get $r^{\ell}=(\ell D+1)^{\ell}n^{\ell/(\ell+1)}=o(n)$ . Hence, for this parameter range, the construction in Theorem 8 asymptotically attains the lower bound in Theorem 9.

III The Spherical-Code Construction: Locating Multiple Errors

When ${\lambda}=2$ , the spherical code construction of [19] yields a linear $[n,n-r]$ code ${\mathcal{C}}$ over $\mathbb{R}$ with redundancy $r=\Theta(\log n)$ and with $\Gamma_{2}({\mathcal{C}})=O(n/\sqrt{r})$ . In this section, we use Proposition 2 to analyze the multiple-error-correcting capability of ${\mathcal{C}}$ . In particular, we show that for any fixed ${\lambda}>2$ , we still have $\Gamma_{\lambda}({\mathcal{C}})=O(n/\sqrt{r})$ .

We first recap the construction. Let $B$ be a linear $[r,\kappa,d]$ code over $\mathbb{F}_{2}$ which satisfies the following two properties:

(B1): $B$ contains the all-one codeword, and—
(B2): ${\mathsf{d}}(B^{\perp})>2$ .

Let $n=2^{\kappa-1}$ and let $B_{0}$ be the set of the $n$ codewords of $B$ whose first entry is a $0$ . Let $H=H(B)$ be the $r\times n$ matrix over $\mathbb{R}$ whose columns are obtained from the codewords in $B_{0}$ by replacing the ${0\textrm{--}1}$ entries by $\pm 1/\sqrt{r}$ . The code ${\mathcal{C}}(B)$ is defined as the $[n,k{\geqslant}n{-}r]$ code over $\mathbb{R}$ with the parity-check matrix $H$ .

Remark 1.

Properties (B1)–(B2) imply that $B$ has a generator matrix with an all-one row and with columns that are all distinct. This, in turn, requires that $\kappa\geqslant 1+\log r$ . We will in fact assume that the latter inequality is strict (in order to have $r<n$ ), in which case $d<r/2$ .

Remark 2.

In what follows, we will also use codes $B$ which—in addition to satisfying properties (B1)–(B2)—attain the G–V bound, i.e.,

\frac{\kappa}{r}\geqslant 1-h(d/r),

where $h(\cdot)$ is the binary entropy function. E.g., when $r$ is a power of $2$ , the construction of a generator matrix of such a code $B$ can start with the $1+\log r$ rows of the generator matrix of the first-order binary Reed–Muller code (thereby guaranteeing properties (B1)–(B2)), followed by iterations of adding rows that are within distance ${}\geqslant d$ from the linear span of the already-selected rows. (As shown in [17], this process can be carried out by a deterministic algorithm in time $O(2^{\kappa}r)=O(nr)$ .)

The property of ${\mathsf{d}}(B^{\perp})>2$ guarantees that any two rows of $H$ are orthogonal which, in turn, implies that

\lVert H\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\rVert_{2}\leqslant\frac{n}{\sqrt{r}},\quad\textrm{for every $\boldsymbol{\varepsilon}\in{\mathcal{Q}}(n,1)$}.

Equivalently,

\lVert{\mathbf{s}}\rVert_{2}\leqslant\frac{4n^{2}}{r},\quad\textrm{for every ${\mathbf{s}}\in 2{\mathcal{S}}$},

(8)

where ${\mathcal{S}}={\mathcal{S}}(H)$ and $2{\mathcal{S}}$ are as defined in (4)–(II-A). The minimum Hamming distance of $B$ and property (B1) jointly imply that for any two distinct columns ${\mathbf{h}}_{i}$ and ${\mathbf{h}}_{j}$ in $H$ ,

\lvert{\mathbf{h}}_{i}^{\top\scriptscriptstyle{\!}}\cdot{\mathbf{h}}_{j}\rvert=\cos(\phi_{i,j})\leqslant 1-\frac{2d}{r},

(9)

where $\phi_{i,j}$ is the angle between ${\mathbf{h}}_{i}$ and ${\mathbf{h}}_{j}$ . Then, using geometric arguments, it is shown in [19] that

\Gamma_{2}({\mathcal{C}}(B))\leqslant\frac{n/\sqrt{r}}{\min_{i\neq j}\sin(\phi_{i,j})}\leqslant\frac{n}{\sqrt{d(1-d/r)}}.

As argued in [19], we can now select $B$ to be a linear $[r,\kappa,d]$ code over $\mathbb{F}_{2}$ that satisfies properties (B1)–(B2) with both $\kappa/r$ and $d/r$ bounded away from $0$ , in which case the code ${\mathcal{C}}(B)$ has $r=\Theta(\log n)$ and $\Gamma_{2}({\mathcal{C}}(B))=O(n/\sqrt{r})$ .

Turning now to ${\lambda}>2$ , we make use of of the following concepts used in the theory of compressed sensing [2],[3],[4],[6]. Let $H=({\mathbf{h}}_{j})_{j\in{\left[{n}\right]}}$ be an $r\times n$ matrix over $\mathbb{R}$ and let ${\lambda}\in{\left[{1:n{+}1}\right]}$ and $\gamma\in\mathbb{R}^{+}$ . We say that $H$ satisfies the restricted isometry property (RIP) of order ${\lambda}$ with constant $\gamma$ , if for every ${\mathbf{e}}\in{\mathcal{B}}(n,{\lambda})$ ,

(1-\gamma)\lVert{\mathbf{e}}\rVert_{2}^{2}\leqslant\lVert H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\rVert_{2}^{2}\leqslant(1+\gamma)\lVert{\mathbf{e}}\rVert_{2}^{2}.

In what follows we concentrate on matrices whose columns are unit vectors, i.e., $\lVert{\mathbf{h}}_{j}\rVert_{2}=1$ for all $j\in{\left[{n}\right]}$ . For such matrices, we define the coherence by

\mu(H)\triangleq\max_{i\neq j}\,\lvert{\mathbf{h}}_{i}^{\top\scriptscriptstyle{\!}}\cdot{\mathbf{h}}_{j}\rvert.

Proposition 10 ([2, Proposition 1]).

Let $H$ be an $r\times n$ matrix over $\mathbb{R}$ with columns that are unit vectors and with coherence $\mu=\mu(H)$ , and let ${\lambda}\in\mathbb{Z}^{+}$ be such that ${\lambda}\leqslant n$ . Then $H$ satisfies the RIP of order ${\lambda}$ with constant $({\lambda}-1)\mu$ .

Under the conditions of Proposition 10, for every ${\mathbf{e}}\in{\mathcal{B}}(n,{\lambda})$ we then have

\lVert H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\rVert_{2}^{2}\geqslant(1-({\lambda}-1)\mu)\lVert{\mathbf{e}}\rVert_{2}^{2}.

(10)

Theorem 11.

Let $B$ be a linear $[r,\kappa,d{<}r/2]$ code over $\mathbb{F}_{2}$ that satisfies properties (B1)–(B2). Denote

\vartheta\triangleq 1-\frac{2d}{r},

(11)

and let ${\lambda}\in\mathbb{Z}^{+}$ be such that ${\lambda}\leqslant\lceil 1/\vartheta\rceil$ . Then

\Gamma_{\lambda}({\mathcal{C}}(B))\leqslant\frac{2n}{\sqrt{r(1-({\lambda}-1)\vartheta)}}.

In particular, if $B$ attains the G–V bound, then

\Gamma_{\lambda}({\mathcal{C}}(B))\leqslant\frac{2n}{\sqrt{r-({\lambda}-1)\sqrt{2\cdot r\cdot\ln\,(2n)}}},

for every ${\lambda}\in\mathbb{Z}^{+}$ for which the denominator under the outer square root is positive.

Proof:

Let $H=H(B)$ be the $r\times n$ parity-check matrix that was used to define ${\mathcal{C}}(B)$ and let $\mu=\mu(H)$ . Each column in $H$ is a unit vector and, so, from (9) we get

\mu\leqslant 1-\frac{2d}{r}\stackrel{{\scriptstyle\textrm{\scriptsize\eqref{eq:vartheta}}}}{{=}}\vartheta.

(12)

Let

\Delta\triangleq\frac{2n}{\sqrt{r(1-({\lambda}-1)\vartheta)}},

(13)

where the condition ${\lambda}\leqslant\lceil 1/\vartheta\rceil$ guarantees that $({\lambda}-1)\vartheta<1$ . Also, let ${\mathbf{e}}$ be an arbitrary vector in ${\mathcal{B}}_{\Delta}(n,{\lambda})$ (see (6)). For such a vector,

\lVert{\mathbf{e}}\rVert_{2}\geqslant\lVert{\mathbf{e}}\rVert_{\infty}>\Delta

(14)

and, so,

	$\displaystyle\left\lVert H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\right\rVert_{2}^{2}$	$\displaystyle\stackrel{{\scriptstyle\textrm{\scriptsize\eqref{eq:cohtoRIP}}}}{{\geqslant}}$	$\displaystyle(1-({\lambda}-1)\mu)\lVert{\mathbf{e}}\rVert_{2}^{2}$		(15)
		$\displaystyle\stackrel{{\scriptstyle\textrm{\scriptsize\eqref{eq:muvartheta}+\eqref{eq:enorm}}}}{{>}}$	$\displaystyle(1-({\lambda}-1)\vartheta)\Delta^{2}\stackrel{{\scriptstyle\textrm{\scriptsize\eqref{eq:Delta1}}}}{{=}}\frac{4n^{2}}{r}.$		(15)

It therefore follows from (8) that

H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\notin 2{\mathcal{S}},

and by Proposition 2 we thus conclude that $\Gamma_{\lambda}({\mathcal{C}}(B))\leqslant\Delta$ .

If $B$ attains the G–V bound, then

\frac{\kappa}{r}\geqslant 1-h(d/r)=1-h(1/2-(\vartheta/2))>\vartheta^{2}/c,

(16)

where $c=2\ln 2$ . From $n=2^{\kappa-1}$ we then get

\log\,(2n)=\kappa>r\cdot\vartheta^{2}/c,

\vartheta<\sqrt{\frac{c\cdot\log\,(2n)}{r}}=\sqrt{\frac{2\cdot\ln\,(2n)}{r}}\;.

Hence, in this case,

	$\displaystyle\Gamma_{\lambda}({\mathcal{C}}(B))\leqslant\Delta$	$\displaystyle=$	$\displaystyle\frac{2n}{\sqrt{r(1-({\lambda}-1)\vartheta)}}$
		$\displaystyle<$	$\displaystyle\frac{2n}{\sqrt{r-({\lambda}-1)\sqrt{2\cdot r\cdot\ln\,(2n)}}}\;.$

The next lemma (which is proved in the Appendix) presents an alternative to the bound (10) that leads to some improvement on Theorem 11. For $\vartheta\in(0,1)$ and a positive integer ${\lambda}\leqslant\lceil 1/\vartheta\rceil$ , we introduce the notation

\eta_{\lambda}(\vartheta)\triangleq\frac{1}{1/\vartheta+2-{\lambda}}.

Remark 3.

In the range $1\leqslant{\lambda}\leqslant\lceil 1/\vartheta\rceil$ we have $\eta_{\lambda}(\vartheta)<1$ . Also, it is easy to verify by differentiation that in that range of $\vartheta$ (when ${\lambda}$ is assumed to be fixed), the mapping $\vartheta\mapsto(1+\vartheta)\left\lparen 1-\eta_{\lambda}(\vartheta)\right\rparen$ is non-increasing.

Lemma 12.

Let $H$ be an $r\times n$ matrix over $\mathbb{R}$ with columns that are unit vectors and with coherence $\mu=\mu(H)$ , and let ${\lambda}\in\mathbb{Z}^{+}$ be such that ${\lambda}\leqslant\min\left\{\lceil 1/\mu\rceil,n\right\}$ . Then for every ${\mathbf{e}}\in{\mathcal{B}}(n,{\lambda})$ ,

\lVert H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\rVert_{2}^{2}\geqslant(1+\mu)\left\lparen 1-\eta_{\lambda}(\mu)\right\rparen\lVert{\mathbf{e}}\rVert_{\infty}^{2}.

Theorem 13.

Under the conditions of Theorem 11,

\Gamma_{\lambda}({\mathcal{C}}(B))\leqslant\frac{2n}{\sqrt{r\cdot(1+\vartheta)(1-\eta_{\lambda}(\vartheta))}}\;.

Proof:

Let

\Delta\triangleq\frac{2n}{\sqrt{r\cdot(1+\vartheta)(1-\eta_{\lambda}(\vartheta))}}\;.

(17)

Referring to the proof of Theorem 11, by applying Lemma 12 we can replace (15) by

	$\displaystyle\left\lVert H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\right\rVert_{2}^{2}$	$\displaystyle\geqslant$	$\displaystyle(1+\mu)\left\lparen 1-\eta_{\lambda}(\mu)\right\rparen\lVert{\mathbf{e}}\rVert_{\infty}^{2}$
		$\displaystyle\!\!\!\!\stackrel{{\scriptstyle\textrm{\scriptsize\eqref{eq:muvartheta}+\eqref{eq:enorm}+Remark~{}\ref{rem:RIP-alt}}}}{{>}}\!\!\!\!$	$\displaystyle(1+\vartheta)\left\lparen 1-\eta_{\lambda}(\vartheta)\right\rparen\Delta^{2}\stackrel{{\scriptstyle\textrm{\scriptsize\eqref{eq:Delta2}}}}{{=}}\frac{4n^{2}}{r}.$

And as in that proof, we then conclude that $\Gamma_{\lambda}({\mathcal{C}}(B))\leqslant\Delta$ .

When $1<{\lambda}<1+1/\vartheta$ , we have

1-\vartheta({\lambda}-1)<(1+\vartheta)(1-\eta_{\lambda}(\vartheta))

and so, Theorem 13 is stronger than Theorem 11. The improvement of Theorem 13 is seen best when ${\lambda}$ is close to $\lceil 1/\vartheta\rceil$ .¹¹1This means that given $n$ and $r$ , we select ${\lambda}$ to be close to the largest possible and analyze which values of $\Gamma_{\lambda}({\mathcal{C}}(B))$ can then be attained. For example, when ${\lambda}=1/\vartheta$ , Theorem 11 yields the upper bound

\Gamma_{\lambda}({\mathcal{C}}(B))\leqslant\sqrt{{\lambda}}\cdot\frac{2n}{\sqrt{r}},

while from Theorem 13 we get:

\Gamma_{\lambda}({\mathcal{C}}(B))\leqslant\sqrt{\frac{2{\lambda}}{{\lambda}+1}}\cdot\frac{2n}{\sqrt{r}}<\sqrt{8}\cdot\frac{n}{\sqrt{r}}.

(18)

In fact, (18) is the bound we get in Theorem 11 when we reduce ${\lambda}$ (by almost half) to $1/(2\vartheta)+1$ while, for this ${\lambda}$ , Theorem 13 yields

\Gamma_{\lambda}({\mathcal{C}}(B))\leqslant\sqrt{\frac{2{\lambda}}{2{\lambda}-1}}\cdot\frac{2n}{\sqrt{r}}.

When ${\lambda}\ll 1/\vartheta$ , the upper bounds in both theorems approach $2n/\sqrt{r}$ .

Corollary 14.

For any $n,{\lambda}\in\mathbb{Z}^{+}$ there exists a linear $[n,k{\geqslant}n{-}r]$ code ${\mathcal{C}}$ over $\mathbb{R}$ with

r=2{\lambda}^{2}\lceil\ln\,(2n)\rceil

and

\Gamma_{\lambda}({\mathcal{C}})<\sqrt{8}\cdot\frac{n}{\sqrt{r}}\leqslant\frac{2n}{{\lambda}\sqrt{\ln\,(2n)}}.

Proof:

Write $\vartheta=1/{\lambda}$ and let $B$ be a linear $[r,\kappa,d]$ code over $\mathbb{F}_{2}$ that satisfies properties (B1)–(B2) with parameters

r=2{\lambda}^{2}\lceil\ln\,(2n)\rceil\quad\textrm{and}\quad d={\lambda}({\lambda}-1)\lceil\ln\,(2n)\rceil,

in which case

\vartheta\triangleq 1-\frac{2d}{r}=\frac{1}{{\lambda}}.

Indeed, by the G–V bound (16), such a code exists with dimension

\kappa>\frac{r\cdot\vartheta^{2}}{2\ln 2}\geqslant\log\,(2n)

and, so, the respective code ${\mathcal{C}}(B)$ has length $2^{\kappa-1}>n$ and can be shortened to form a linear $[n,k{\geqslant}n{-}r]$ code ${\mathcal{C}}$ over $\mathbb{R}$ . Finally, since ${\lambda}=1/\vartheta$ , we get from (18) that $\Gamma_{\lambda}({\mathcal{C}})\leqslant\Gamma_{\lambda}({\mathcal{C}}(B))<\sqrt{8}\cdot n/\sqrt{r}$ .

Remark 4.

The last corollary is non-vacuous when ${\lambda}=O\bigl{(}\sqrt{n/\log n}\bigr{)}$ (otherwise we have $r>n$ ). When ${\lambda}=2$ , the corollary coincides with Theorem 4.

Remark 5.

In Corollary 14, we can make $r$ grow more slowly with ${\lambda}$ at the expense of a faster growth with $\log n$ , while keeping the same upper bound $\Gamma_{\lambda}({\mathcal{C}})\leqslant\sqrt{8}\cdot n/\sqrt{r}$ . Specifically, in the proof, we take $B$ to be the dual of an extended binary BCH primitive code [16, p. 280], or as a concatenation of a RS outer code with the first-order binary Reed–Muller code. In both cases we have, for a parameter $t\in\mathbb{Z}^{+}$ ,

\vartheta=1-\frac{2d}{r}=O\left\lparen\frac{t}{\sqrt{r}}\right\rparen\quad\textrm{and}\quad\kappa=\Theta(t\log r),

i.e.,

\vartheta=O\left\lparen\frac{\kappa}{\sqrt{r}\cdot\log r}\right\rparen.

Substituting $\kappa=\lceil\log\,(2n)\rceil$ and $\vartheta=1/{\lambda}$ then yields

r\log^{2}r=O\left\lparen{\lambda}^{2}\log^{2}n\right\rparen,

which is non-vacuous when ${\lambda}=O(\sqrt{n})$ .

IV Code Construction Based on Disjunct Matrices

In this section, we study the relationship between analog error-correcting codes and disjunct matrices. Specifically, we consider linear codes over $\mathbb{R}$ with parity-check matrices that are $(D,\rho)$ -disjunct: we first study their properties (Theorem 15) and then propose decoding algorithms for these codes.

Theorem 15.

Let $H$ be a $({\lambda}{-}1,\rho)$ -disjunct $r\times n$ matrix, for some ${\lambda},\rho\in{\left[{1:n{+}1}\right]}$ , and let ${\mathcal{C}}$ be the linear $[n,k{\geqslant}n{-}r]$ code over $\mathbb{R}$ that has $H$ as a parity-check matrix. Then

\Gamma_{\lambda}({\mathcal{C}})\leqslant 2\rho.

Proof:

We show that $\Delta=2\rho$ is contained in the minimand set in (7); the result will then follow from Proposition 2. Given any vector ${\mathbf{e}}=(e_{j})_{j\in{\left[{n}\right]}}\in{\mathcal{B}}_{\Delta}(n,{\lambda})$ , write ${\mathcal{J}}={\mathsf{Supp}}_{0}({\mathbf{e}})$ and let $t\in{\mathcal{J}}$ be a position at which $\lvert e_{t}\rvert>\Delta$ . Since $H$ is $({\lambda}{-}1)$ -disjunct and $\lvert{\mathcal{J}}\rvert\leqslant{\lambda}$ , there is a row index $i\in{\left[{r}\right]}$ such that $(H_{i})_{\mathcal{J}}$ contains a $1$ only at position $t$ . Therefore,

\left\lvert H_{i}{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\right\rvert=\lvert e_{t}\rvert>\Delta=2\rho.

(19)

On the other hand, since ${\mathsf{w}}(H_{i})\leqslant\rho$ , for every $\boldsymbol{\varepsilon}\in{\mathcal{Q}}(n,2)$ we have $\lvert H_{i}\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\rvert\leqslant 2\rho$ , namely,

\lvert s_{i}\rvert\leqslant 2\rho,\quad\textrm{for every ${\mathbf{s}}=(s_{v})_{v\in{\left[{r}\right]}}\in 2{\mathcal{S}}$}.

(20)

By (19) and (20) we get that $H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\notin 2{\mathcal{S}}$ , thus establishing that $\Delta=2\rho$ is contained in the minimand in (7).

Combining Theorem 15 with Theorem 8, we obtain the following result.

Corollary 16.

Let $\ell\in\mathbb{Z}^{+}$ , let $q$ be a prime power, and set $n=q^{\ell+1}$ . Then for any positive integer ${\lambda}\leqslant\lceil q/\ell\rceil$ there is an explicit construction of a linear $[n,k{\geqslant}n{-}r]$ code ${\mathcal{C}}$ over $\mathbb{R}$ such that

r=(\ell{\lambda}-\ell+1)q

and

\Gamma_{\lambda}({\mathcal{C}})\leqslant 2q^{\ell}=\frac{2(\ell{\lambda}-\ell+1)n}{r}.

In particular, by taking $\ell=1$ , for any ${\lambda}\leqslant\sqrt{n}$ one can obtain a linear code ${\mathcal{C}}$ with

r={\lambda}\sqrt{n}\quad\textrm{and}\quad\Gamma_{\lambda}({\mathcal{C}})\leqslant 2\sqrt{n}=\frac{2{\lambda}n}{r}.

It is worth noting that when ${\lambda}=2$ , the bound $\Gamma_{2}({\mathcal{C}})\leqslant 4n/r$ coincides with the one in Theorem 3 (although $r$ in that theorem can take multiple values, including values that are smaller than $2\sqrt{n}$ ). We also note that in Corollary 16, we have $r=\Theta({\lambda}n^{\alpha})$ and $\Gamma_{\lambda}({\mathcal{C}})=O({\lambda}n/r)$ , for certain (fixed) $\alpha\in(0,1/2]$ and infinitely many values of $n$ . In Section V, we present a construction of disjunct matrices which produce codes with similar dependence of $r$ and $\Gamma_{\lambda}(\cdot)$ on $n$ and ${\lambda}$ , yet for $\alpha\in[1/2,1)$ .

Next, we compare the construction of Corollary 14 with the case $\ell=1$ in Corollary 16 (as this case yields the slowest growth of $r$ with $n$ ). For the former we have $\Gamma_{\lambda}({\mathcal{C}})\leqslant\sqrt{8}\cdot n/\sqrt{r}$ , while for the latter $\Gamma_{\lambda}({\mathcal{C}})=\sqrt{n}$ , which is smaller since $r<n$ . Yet the construction of Corollary 16 requires $r={\lambda}\sqrt{n}$ , which can match the redundancy, $2{\lambda}^{2}\lceil\ln\,(2n)\rceil$ , in Corollary 14 only when

{\lambda}=\Omega\left\lparen{\sqrt{n}}/{\log n}\right\rparen

(still, by Remark 4, this range partially overlaps with the range of ${\lambda}$ for which the codes in Corollary 14 are realizable).

Remark 6.

The construction of Theorem 15, when applied with the Porat–Rothschild disjunct matrices in Theorem 5, yields $r=O({\lambda}^{2}\log n)$ (i.e., a similar guarantee to that in Corollary 14) yet with $\Gamma_{\lambda}({\mathcal{C}})=\Omega(n/{\lambda})$ , which is $\Omega(\sqrt{\log n})$ times larger than the respective value in Corollary 14.

In the remainder of this section, we present decoders for linear codes with parity-check matrices that are $({\lambda}{-}1,\rho)$ -disjunct. In Subsection IV-A we present a decoder for the generic case, yet its complexity is $O(r{\lambda}n^{\lambda})$ , i.e., polynomial only when ${\lambda}$ is fixed. A much more efficient algorithm is presented in Subsection IV-B, yet under the additional assumption that the column weights in the parity-check matrix are also constrained.

IV-A Decoder for the generic disjunct construction

Our first decoder, denoted by $\overline{{\mathcal{D}}}$ , is presented in Algorithm 1.

\triangleright

H=(H_{i,j})

is a

({\lambda}{-}1,\rho)

-disjunct

r\times n

matrix

\triangleright

\tau,\sigma\in\mathbb{Z}_{\geqslant 0}

are such that

2\tau+\sigma={\lambda}

Input: vector

{\mathbf{y}}\in\mathbb{R}^{n}

Output: subset

\overline{{\mathcal{D}}}({\mathbf{y}})\subseteq{\left[{n}\right]}

Set

\Lambda=\{({\mathcal{T}},{\mathcal{J}})\,:\,\varnothing\neq{\mathcal{T}}\subseteq{\mathcal{J}}\subseteq{\left[{n}\right]}\;\textrm{and}\;\lvert{\mathcal{J}}\rvert\leqslant\tau+\sigma\}

For each

({\mathcal{T}},{\mathcal{J}})\in\Lambda

, let

{\mathcal{R}}({\mathcal{T}},{\mathcal{J}})=\left\{i\in[r]\,:\,{\mathsf{w}}((H_{i})_{\mathcal{T}})={\mathsf{w}}((H_{i})_{\mathcal{J}})=1\right\}

\overline{{\mathcal{D}}}({\mathbf{y}})\leftarrow\varnothing

{\mathbf{s}}=(s_{i})_{i\in{\left[{r}\right]}}\leftarrow H{\mathbf{y}}^{\top\scriptscriptstyle{\!}}

while

\exists({\mathcal{T}},{\mathcal{J}})\in\Lambda

s.t.

\lvert s_{i}\rvert>\rho

for all

i\in{\mathcal{R}}({\mathcal{T}},{\mathcal{J}})

\overline{{\mathcal{D}}}({\mathbf{y}})\leftarrow\overline{{\mathcal{D}}}({\mathbf{y}})\cup{\mathcal{T}}

\Lambda\leftarrow\Lambda\setminus\{({\mathcal{T}},{\mathcal{J}})\}

end while

return

\overline{{\mathcal{D}}}({\mathbf{y}})

Algorithm 1 Decoder

\overline{{\mathcal{D}}}

for codes from disjunct matrices

Theorem 17.

Let ${\mathcal{C}}$ be a code as in Theorem 15. Then the mapping $\overline{{\mathcal{D}}}:\mathbb{R}^{n}\rightarrow 2^{{\left[{n}\right]}}$ that is defined by Algorithm 1 is a $(\tau,\sigma)$ -decoder for $({\mathcal{C}},2\rho:1)$ .

Proof:

Assume a received (read) vector

{\mathbf{y}}={\mathbf{c}}+{\mathbf{e}}+\boldsymbol{\varepsilon},

where ${\mathbf{c}}\in{\mathcal{C}}$ , $\boldsymbol{\varepsilon}\in{\mathcal{Q}}(n,1)$ , and ${\mathbf{e}}\in{\mathcal{B}}(n,\tau+\sigma)$ .

We first show that

{\mathsf{Supp}}_{2\rho}({\mathbf{e}})\subseteq\overline{{\mathcal{D}}}({\mathbf{y}}).

(21)

Take ${\mathcal{T}}={\mathsf{Supp}}_{2\rho}({\mathbf{e}})$ and ${\mathcal{J}}={\mathsf{Supp}}_{0}({\mathbf{e}})$ . Then for every $i\in{\mathcal{R}}({\mathcal{T}},{\mathcal{J}})$ , since ${\mathsf{w}}((H_{i})_{\mathcal{T}})=1$ and $(H_{i})_{{\mathcal{J}}\setminus{\mathcal{T}}}={\mathbf{0}}$ , we have

\lvert s_{i}\rvert=\lvert H_{i}{\mathbf{e}}^{\top\scriptscriptstyle{\!}}+H_{i}\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\rvert\geqslant{\underbrace{\lvert H_{i}{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\rvert}_{{}>2\rho}}-\underbrace{\lvert H_{i}\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\rvert}_{{}\leqslant\rho}>2\rho-\rho=\rho.

(22)

Hence, $({\mathcal{T}},{\mathcal{J}})$ passes the check in the while loop and, so, the set ${\mathcal{T}}$ is joined into $\overline{{\mathcal{D}}}({\mathbf{y}})$ , thereby establishing (21).

Next, we assume that ${\mathsf{w}}({\mathbf{e}})\leqslant\tau$ and show that

\overline{{\mathcal{D}}}({\mathbf{y}})\subseteq{\mathsf{Supp}}_{0}({\mathbf{e}}).

(23)

Write ${\mathcal{K}}={\mathsf{Supp}}_{0}({\mathbf{e}})$ ; then $\lvert{\mathcal{K}}\rvert\leqslant\tau$ . Let $({\mathcal{T}},{\mathcal{J}})$ be a pair in $\Lambda$ that passes the check in the while loop, i.e., $\lvert s_{i}\rvert>\rho$ for all $i\in{\mathcal{R}}({\mathcal{T}},{\mathcal{J}})$ . We claim that ${\mathcal{T}}\subseteq{\mathcal{K}}$ . Otherwise, take a $t\in{\mathcal{T}}\setminus{\mathcal{K}}$ . Since $H$ is $({\lambda}{-}1)$ -disjunct and

\lvert{\mathcal{J}}\cup{\mathcal{K}}\rvert\leqslant\lvert{\mathcal{J}}\rvert+\lvert{\mathcal{K}}\rvert\leqslant(\tau+\sigma)+\tau={\lambda},

there is a row index $i\in[r]$ such that $H_{i,t}=1$ and $H_{i,j}=0$ for all $j\in\left\lparen{\mathcal{J}}\cup{\mathcal{K}}\right\rparen\setminus\{t\}$ . Then ${\mathsf{w}}((H_{i})_{\mathcal{T}})={\mathsf{w}}((H_{i})_{\mathcal{J}})=1$ and, so, $i\in{\mathcal{R}}({\mathcal{T}},{\mathcal{J}})$ . On the other hand, we also have $(H_{i})_{\mathcal{K}}={\mathbf{0}}$ , from which we get

\lvert s_{i}\rvert=\lvert{\underbrace{H_{i}{\mathbf{e}}^{\top\scriptscriptstyle{\!}}}_{0}}+H_{i}\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\rvert\leqslant\rho.

Yet this means that the pair $({\mathcal{T}},{\mathcal{J}})$ does not pass the check in the while loop, thereby reaching a contradiction. We conclude that when ${\mathsf{w}}({\mathbf{e}})\leqslant\tau$ , any set ${\mathcal{T}}$ that is joined into $\overline{{\mathcal{D}}}({\mathbf{y}})$ in the while loop is a subset of ${\mathcal{K}}={\mathsf{Supp}}_{0}({\mathbf{e}})$ , thus establishing (23).

Eqs. (21) and (23), in turn, imply that the function $\overline{{\mathcal{D}}}$ in Algorithm 1 satisfies conditions (D2) and (D1), respectively, in the definition of a $(\tau,\sigma)$ -decoder for $({\mathcal{C}},2\rho:1)$ .

We note that

\lvert\Lambda\rvert=\sum_{j=1}^{\tau+\sigma}\binom{n}{j}(2^{j}-1)=O(n^{\tau+\sigma})=O(n^{\lambda}).

Given a pair $({\mathcal{T}},{\mathcal{J}})\in\Lambda$ , checking the conditions in the while loop of Algorithm 1 can be done in $O(r{\lambda})$ time.

IV-B Decoder when columns in $H$ are also weight-constrained

Let ${\mathcal{C}}$ be a code as in Theorem 15 and $w$ be a positive integer. We next present a more efficient $(\tau,\sigma)$ -decoder for $({\mathcal{C}},2\rho:1)$ under the following two additional conditions on $H$ :

(H1): Every row of $H$ has weight at least $2$ .
(H2): Every column of $H$ has weight at most $w$ .

Condition (H1) is not really limiting: the case where $H$ contains rows of weight $1$ is degenerate, as then there are positions on which all the codewords in ${\mathcal{C}}$ are identically $0$ (and, thus, these coordinates can be ignored, thereby reducing the decoding to a shorter code). In Section V, we present constructions of $(D,\rho)$ -disjunct matrices that satisfy conditions (H1)–(H2).

We will use the following lemma.

Lemma 18.

Let $H$ be a $({\lambda}{-}1)$ -disjunct $r\times n$ matrix that satisfies condition (H1). Given any nonempty subset ${\mathcal{J}}\subseteq{\left[{n}\right]}$ of size $\lvert{\mathcal{J}}\rvert\leqslant{\lambda}$ , for every column index $j\in{\mathcal{J}}$ there exist at least ${\lambda}+1-\lvert{\mathcal{J}}\rvert$ nonzero rows in the submatrix $(H)_{\mathcal{J}}$ that contain a $1$ only at column $j$ .

Proof:

The proof is by backward induction on $\lvert{\mathcal{J}}\rvert$ , with the induction base, $\lvert{\mathcal{J}}\rvert={\lambda}$ , following from the definition of a $({\lambda}{-}1)$ -disjunct matrix.

Turning to the induction step, suppose that $0<\lvert{\mathcal{J}}\rvert\leqslant{\lambda}-1$ and let $j$ be any column index in ${\mathcal{J}}$ . By the disjunct property, there exists a row index $i\in{\left[{r}\right]}$ such that $(H_{i})_{\mathcal{J}}$ contains a $1$ only at position $j$ . By condition (H1), there is at least one index $j^{\prime}\in{\left[{n}\right]}\setminus{\mathcal{J}}$ for which $H_{i,j^{\prime}}=1$ . Letting ${\mathcal{J}}^{\prime}={\mathcal{J}}\cup\{j^{\prime}\}$ , by the induction hypothesis there are at least ${\lambda}+1-\lvert{\mathcal{J}}^{\prime}\rvert={\lambda}-\lvert{\mathcal{J}}\rvert$ nonzero rows in $(H)_{{\mathcal{J}}^{\prime}}$ that contain a $1$ only at column $j$ ; clearly, none of these rows is indexed by $i$ since $(H_{i})_{{\mathcal{J}}^{\prime}}$ contains two $1$ s. Altogether there are at least ${\lambda}+1-\lvert{\mathcal{J}}\rvert$ nonzero rows in $(H)_{\mathcal{J}}$ that contain a $1$ only at column $j$ .

Remark 7.

Applying Lemma 18 with $\lvert{\mathcal{J}}\rvert=1$ implies that the weight of every column in $H$ must be at least ${\lambda}$ (recall that we have used this fact in the proof of Theorem 9). Hence, $(\lambda{-}1)$ -disjunct matrices can satisfy conditions (H1) and (H2) only when $w\geqslant{\lambda}$ .

Given $\rho\in\mathbb{R}^{+}$ and a vector ${\mathbf{s}}=(s_{i})_{i\in{\left[{r}\right]}}\in\mathbb{R}^{r}$ (such as a syndrome that is computed with respect to $H$ ), we let ${\mathbf{\chi}}_{\rho}({\mathbf{s}})$ be the real row vector $(\chi_{i})_{i\in{\left[{r}\right]}}\in\{0,1\}^{r}$ whose entries are given by

\chi_{i}=\begin{cases}0,&\textrm{if $\lvert s_{i}\rvert\leqslant\rho$},\\ 1,&\textrm{otherwise}.\\ \end{cases}

Theorem 19.

Let ${\mathcal{C}}$ be a code as in Theorem 15 and suppose that $H$ also satisfies conditions (H1)–(H2). For nonnegative integers $\tau$ and $\sigma$ such that

2\tau+\sigma\leqslant 2{\lambda}-w\;(\leqslant{\lambda}),

(24)

let $\widetilde{{\mathcal{D}}}:\mathbb{R}^{n}\rightarrow 2^{{\left[{n}\right]}}$ be defined for every ${\mathbf{y}}\in\mathbb{R}^{n}$ by

\widetilde{{\mathcal{D}}}({\mathbf{y}})\triangleq{\mathsf{Supp}}_{{\lambda}-\tau-\sigma}\left\lparen{\mathbf{\chi}}_{\rho}({\mathbf{s}})H\right\rparen,

(25)

where ${\mathbf{s}}=H{\mathbf{y}}^{\top\scriptscriptstyle{\!}}$ . Then $\widetilde{{\mathcal{D}}}$ is a $(\tau,\sigma)$ -decoder for $({\mathcal{C}},2\rho:1)$ .

Proof:

Assume a received (read) vector

{\mathbf{y}}={\mathbf{c}}+{\mathbf{e}}+\boldsymbol{\varepsilon},

where ${\mathbf{c}}\in{\mathcal{C}}$ , $\boldsymbol{\varepsilon}\in{\mathcal{Q}}(n,1)$ , and ${\mathbf{e}}\in{\mathcal{B}}(n,\tau+\sigma)$ .

We first show that

{\mathsf{Supp}}_{2\rho}({\mathbf{e}})\subseteq\widetilde{{\mathcal{D}}}({\mathbf{y}}).

(26)

Take ${\mathcal{J}}={\mathsf{Supp}}_{0}({\mathbf{e}})$ and let $j\in{\mathsf{Supp}}_{2\rho}({\mathbf{e}})\;(\subseteq{\mathcal{J}})$ . By Lemma 18 we get that the submatrix $(H)_{\mathcal{J}}$ contains at least

{\lambda}+1-\lvert{\mathcal{J}}\rvert\geqslant{\lambda}+1-\tau-\sigma

(27)

rows with a $1$ only at column $j$ . Denoting by ${\mathcal{R}}$ the set of indexes of these rows, for every $i\in{\mathcal{R}}$ , the respective entry $s_{i}$ in the syndrome ${\mathbf{s}}$ satisfies:

\lvert s_{i}\rvert=\lvert H_{i}{\mathbf{e}}^{\top\scriptscriptstyle{\!}}+H_{i}\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\rvert\geqslant\lvert H_{i}{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\rvert-\lvert H_{i}\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\rvert>\rho

(similarly to (22)). It follows that the respective entry, $\chi_{i}$ , in ${\mathbf{\chi}}_{\rho}({\mathbf{s}})$ equals $1$ and, so, the supports of ${\mathbf{\chi}}_{\rho}({\mathbf{s}})$ and the column ${\mathbf{h}}_{j}$ in $H$ overlap on at least $\lvert{\mathcal{R}}\rvert$ positions. Hence,

{\mathbf{\chi}}_{\rho}({\mathbf{s}})\cdot{\mathbf{h}}_{j}\geqslant\lvert{\mathcal{R}}\rvert\stackrel{{\scriptstyle\textrm{\scriptsize\eqref{eq:overlap1}}}}{{\geqslant}}{\lambda}+1-\tau-\sigma,

i.e., $j\in{\mathsf{Supp}}_{{\lambda}-\tau-\sigma}\left\lparen{\mathbf{\chi}}_{\rho}({\mathbf{s}})H\right\rparen\triangleq\widetilde{{\mathcal{D}}}({\mathbf{y}})$ . We conclude that

j\in{\mathsf{Supp}}_{2\rho}({\mathbf{e}})\;\Longrightarrow\;j\in\widetilde{{\mathcal{D}}}({\mathbf{y}}),

thereby establishing (26).

Next, we assume that ${\mathsf{w}}({\mathbf{e}})\leqslant\tau$ and show that

\widetilde{{\mathcal{D}}}({\mathbf{y}})\subseteq{\mathsf{Supp}}_{0}({\mathbf{e}}).

(28)

Write ${\mathcal{K}}={\mathsf{Supp}}_{0}({\mathbf{e}})$ and let $j\in{\left[{n}\right]}\setminus{\mathcal{K}}$ . Lemma 18, now applied with ${\mathcal{J}}={\mathcal{K}}\cup\{j\}$ , implies that the submatrix $(H)_{\mathcal{J}}$ contains at least

{\lambda}+1-\lvert{\mathcal{J}}\rvert\geqslant{\lambda}-\tau

(29)

rows with a $1$ only at column $j$ . Letting ${\mathcal{R}}$ be the set of indexes of these rows, for every $i\in{\mathcal{R}}$ we then have $(H_{i})_{\mathcal{K}}={\mathbf{0}}$ and, so, the respective entry in the syndrome ${\mathbf{s}}$ satisfies:

\lvert s_{i}\rvert=\lvert{\underbrace{H_{i}{\mathbf{e}}^{\top\scriptscriptstyle{\!}}}_{0}}+H_{i}\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\rvert\leqslant\rho,

namely, $\chi_{i}=0$ . Hence, the number of positions on which the supports of ${\mathbf{\chi}}_{\rho}({\mathbf{s}})$ and ${\mathbf{h}}_{j}$ overlap is at most

{\mathsf{w}}({\mathbf{h}}_{j})-\lvert{\mathcal{R}}\rvert\stackrel{{\scriptstyle\textrm{\scriptsize(H2)+\eqref{eq:overlap2}}}}{{\leqslant}}w-({\lambda}-\tau)\stackrel{{\scriptstyle\textrm{\scriptsize\eqref{eq:tausigma}}}}{{\leqslant}}{\lambda}-\tau-\sigma

and, so,

(0\leqslant)\;{\mathbf{\chi}}_{\rho}({\mathbf{s}})\cdot{\mathbf{h}}_{j}\leqslant{\lambda}-\tau-\sigma,

i.e., $j\notin{\mathsf{Supp}}_{{\lambda}-\tau-\sigma}\left\lparen{\mathbf{\chi}}_{\rho}({\mathbf{s}})H\right\rparen\triangleq\widetilde{{\mathcal{D}}}({\mathbf{y}})$ . We conclude that when ${\mathsf{w}}({\mathbf{e}})\leqslant\tau$ ,

j\notin{\mathsf{Supp}}_{0}({\mathbf{e}})\;\Longrightarrow\;j\notin\widetilde{{\mathcal{D}}}({\mathbf{y}}),

thereby establishing (28).

Eqs. (26) and (28), in turn, imply that the function ${\mathbf{y}}\mapsto\widetilde{{\mathcal{D}}}({\mathbf{y}})$ defined in (25) is a $(\tau,\sigma)$ -decoder for $({\mathcal{C}},2\rho:1)$ .

The decoder (25) is easy to compute: it consists of a multiplication of $H$ to the right by ${\mathbf{y}}$ to obtain the syndrome ${\mathbf{s}}$ , and then to the left by a binary vector which is a quantized copy of ${\mathbf{s}}$ . Since $H$ is a ${0\textrm{--}1}$ matrix whose rows and columns have limited weights (at most $\rho$ and $w$ , respectively), the decoding requires less than $2\min\{r\rho,wn\}$ real additions.

We note that the condition (24) (which was used in our analysis), is generally stricter than the condition $2\tau+\sigma\leqslant{\lambda}$ which, by Theorems 15 and 17, is sufficient for having a $(\tau,\sigma)$ -decoder for $({\mathcal{C}},2\rho:1)$ . These two conditions coincide when $w={\lambda}$ , and this case is characterized in the next lemma.

Lemma 20.

Let $H=({\mathbf{h}}_{j})_{j\in{\left[{n}\right]}}$ be a $({\lambda}{-}1)$ -disjunct $r\times n$ matrix that satisfies conditions (H1)–(H2) with $w={\lambda}$ . Then the following holds.

M1): Every column of $H$ has weight (exactly) ${\lambda}$ .
M2): The supports of every two distinct columns of $H$ intersect on at most one coordinate.

Equivalently, for every $j\neq j^{\prime}$ in ${\left[{n}\right]}$ :

\lVert{\mathbf{h}}_{j}\rVert_{2}=\sqrt{{\lambda}}\quad\textrm{and}\quad\lvert{\mathbf{h}}_{j}^{\top\scriptscriptstyle{\!}}\cdot{\mathbf{h}}_{j^{\prime}}\rvert\leqslant 1

(and, thus, the columns of $H$ constitute a spherical code).

Proof:

Condition (M1) follows from Lemma 18 when applied with $\lvert{\mathcal{J}}\rvert=1$ (see Remark 7), and condition (M2) follows from applying the lemma with $\lvert{\mathcal{J}}\rvert=2$ .

We end this section by presenting a simple decoder for the detection-only case, i.e., $\tau=0$ . In this case, we actually do not need conditions (H1)–(H2), and we can handle any $\sigma\leqslant{\lambda}$ .

Theorem 21.

Let ${\mathcal{C}}$ be a code as in Theorem 15 and let $\widehat{{\mathcal{D}}}:\mathbb{R}^{n}\rightarrow\{\varnothing,{\mathrm{``e"}}\}$ be defined by

\widehat{{\mathcal{D}}}({\mathbf{y}})=\begin{cases}\varnothing,&\textrm{if ${\mathbf{\chi}}_{\rho}({\mathbf{s}})={\mathbf{0}}$},\\ {\mathrm{``e"}},&\textrm{otherwise},\\ \end{cases}

where ${\mathbf{s}}=H{\mathbf{y}}^{\top\scriptscriptstyle{\!}}$ . Then $\widehat{{\mathcal{D}}}$ is a $(0,{\lambda})$ -decoder for $({\mathcal{C}},2\rho:1)$ .

Proof:

Condition (D1) pertains only to the error vector ${\mathbf{e}}={\mathbf{0}}$ , in which case

\lVert{\mathbf{s}}\rVert_{\infty}=\lVert{\underbrace{H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}}_{{\mathbf{0}}}}+H\boldsymbol{\varepsilon}^{\top\scriptscriptstyle{\!}}\rVert_{\infty}\leqslant\rho.

Consequently, ${\mathbf{\chi}}_{\rho}({\mathbf{s}})={\mathbf{0}}$ and we have $\widehat{{\mathcal{D}}}({\mathbf{y}})=\varnothing$ , as required.

As for condition (D2), we have $\widehat{{\mathcal{D}}}({\mathbf{y}})\neq{\mathrm{``e"}}$ only when ${\mathbf{\chi}}_{\rho}({\mathbf{s}})={\mathbf{0}}$ . Now, in the proof of Theorem 19, we have established (26) without using conditions (H1)–(H2); hence, we can apply (26) to conclude that

{\mathsf{Supp}}_{2\rho}({\mathbf{e}})\subseteq{\mathsf{Supp}}_{{\lambda}-\tau-\sigma}\bigl{(}{\mathbf{\chi}}_{\rho}({\mathbf{s}})H\bigr{)}\bigm{|}_{\tau=0,\sigma={\lambda}}=\varnothing=\widehat{{\mathcal{D}}}({\mathbf{y}}),

as required.

V Constructions of Disjunct Matrices with Weight-Constrained Rows and Columns

In this section, we present several constructions for $(D,\rho)$ disjunct matrices which satisfy conditions (H1)–(H2) with $w=D+1$ . Our constructions are based on combinatorial designs. We start by recalling several definitions.

Let $t,r,s\in\mathbb{Z}^{+}$ be such that $r\geqslant s\geqslant t$ . A $t$ - $(r,s,1)$ packing design is a pair $(X,{\mathfrak{B}})$ , where $X$ is a set of $r$ elements (called points) and ${\mathfrak{B}}$ is a collection of $s$ -subsets (called blocks) of $X$ , such that every $t$ -subset of $X$ is contained in at most one block. Furthermore, a packing design is called resolvable if its blocks can be partitioned into sets (parallel classes) ${\mathcal{P}}_{0},{\mathcal{P}}_{1},\ldots,{\mathcal{P}}_{\rho-1}$ such that each point is contained in exactly one block in each ${\mathcal{P}}_{i}$ .

The incidence matrix of packing design $(X,{\mathfrak{B}})$ is an $|X|\times|{\mathfrak{B}}|$ binary matrix $H=(H_{x,\beta})$ whose rows and columns are indexed by the elements of $X$ and ${\mathfrak{B}}$ , respectively, and for each $x\in X$ and $\beta\in{\mathfrak{B}}$ ,

H_{x,\beta}=\begin{cases}1,&\textrm{if $x\in\beta$,}\\ 0,&\textrm{if $x\notin\beta$}.\end{cases}

Proposition 22.

Let $(X,{\mathfrak{B}})$ be a resolvable $t$ - $(r,s,1)$ packing design with $\rho$ parallel classes. Then its incidence matrix $H$ is a $D$ -disjunct matrix with constant row weight $\rho$ , where $D=\lfloor(s-1)/(t-1)\rfloor$ .

Proof:

Write $H=({\mathbf{h}}_{\beta})_{\beta\in{\mathfrak{B}}}$ and let $\beta_{0},\beta_{1},\ldots,\beta_{D}$ be arbitrary $D+1$ blocks in ${\mathfrak{B}}$ . Since $(X,{\mathfrak{B}})$ is a $t$ - $(r,s,1)$ packing design, every two blocks of ${\mathfrak{B}}$ have at most $t-1$ common points. Then $\left\lvert\beta_{0}\cap\beta_{j}\right\rvert\leqslant t-1$ for all $1\leqslant j\leqslant D$ and, so,

\left\lvert\beta_{0}\cap\left\lparen\cup_{j=1}^{D}\beta_{j}\right\rparen\right\rvert\leqslant\sum_{j=1}^{D}\left\lvert\beta_{0}\cap\beta_{j}\right\rvert\leqslant D(t-1)<s=\lvert\beta_{0}\rvert,

where the third inequality follows from $D=\lfloor(s-1)/(t-1)\rfloor$ . It follows that

\beta_{0}\setminus\left\lparen\cup_{j=1}^{D}\beta_{j}\right\rparen\neq\varnothing,

namely, there is a point $x\in X$ such that $H_{x,\beta_{0}}=1$ whereas $H_{x,\beta_{j}}=0$ for all $1\leqslant j\leqslant D$ . Hence, $H$ is $D$ -disjunct.

Next, we consider the row weight, ${\mathsf{w}}(H_{x})$ , where $x$ is any point in $X$ : this weight equals the number of blocks in ${\mathfrak{B}}$ which contain $x$ . Since $x$ is contained in exactly one block in each parallel class and there are in total $\rho$ parallel classes, we get ${\mathsf{w}}(H_{x})=\rho$ .

A transversal design ${\mathrm{TD}}(s,g)$ is a triple $(X,{\mathfrak{G}},{\mathfrak{B}})$ , where $X$ is a set of $sg$ points, ${\mathfrak{G}}$ is a partition of $X$ into $s$ partition elements (groups), each of size $g$ , and ${\mathfrak{B}}$ is a collection of $s$ -subsets (blocks) of $X$ such that every $2$ -subset of $X$ is contained either in one group or in one block, but not both. A ${\mathrm{TD}}(s,g)$ is called resolvable if its blocks can be partitioned into parallel classes.

It is easy to see that in a ${\mathrm{TD}}(s,g)$ , each block intersects with each group at exactly one point. A direct calculation shows that there are $g^{2}$ blocks and each point is contained in $g$ blocks. So, if it is resolvable, then the blocks should be partitioned into $g$ parallel classes.

It is known that the existence of a resolvable ${\mathrm{TD}}(s,g)$ is equivalent to the existence of $s-1$ mutually orthogonal latin squares of side $g$ , while the latter can be constructed by using linear polynomials (e.g., see Theorem 3.18 and Construction 3.29 in [5, Section III.3]). In the following example, we use linear polynomials to construct resolvable ${\mathrm{TD}}$ s directly.

Example 1.

Let $q$ be a prime power. We can construct a resolvable ${\mathrm{TD}}(q,q)$ as follows. Take $X=\mathbb{F}_{q}\times\mathbb{F}_{q}$ , ${\mathfrak{G}}=\left\{\{y\}\times\mathbb{F}_{q}\right\}_{y\in\mathbb{F}_{q}}$ , and ${\mathfrak{B}}=\left\{\beta_{a,b}\right\}_{(a,b)\in\mathbb{F}_{q}\times\mathbb{F}_{q}}$ , where

\beta_{a,b}=\left\{(y,ay+b)\,:\,y\in\mathbb{F}_{q}\right\}.

For each $a\in\mathbb{F}_{q}$ , let ${\mathcal{P}}_{a}=\left\{\beta_{a,b}\right\}_{b\in\mathbb{F}_{q}}$ ; clearly, $\left\{{\mathcal{P}}_{a}\right\}_{a\in\mathbb{F}_{q}}$ is a partition of ${\mathfrak{B}}$ .

Each block $\beta_{a,b}$ has size $q$ , which equals the number of groups, and every $2$ -subset of the form $\{(y,z),(y,z^{\prime})\}$ (which is contained in one group) cannot be contained in any block. For a $2$ -subset $\{(y,z),(y^{\prime},z^{\prime})\}$ with $y\neq y^{\prime}$ , the system of equations

\begin{cases}ay+b=z\\ ay^{\prime}+b=z^{\prime}\end{cases}

has a unique solution for $(a,b)$ ; hence, there is a unique block in ${\mathfrak{B}}$ which contains that $2$ -subset. Therefore, $(X,{\mathfrak{G}},{\mathfrak{B}})$ is a transversal design. Moreover, for each $a\in\mathbb{F}_{q}$ and each point $(y,z)\in X$ , there is a unique $b\in\mathbb{F}_{q}$ such that $ay+b=z$ . Hence, each ${\mathcal{P}}_{a}$ is a parallel class.

Lemma 23.

If there is a resolvable ${\mathrm{TD}}(s,g)$ , then for every $2\leqslant s^{\prime}\leqslant s$ and $1\leqslant g^{\prime}\leqslant g$ , there is a $2$ - $(s^{\prime}g,s^{\prime},1)$ packing design with $g^{\prime}$ parallel classes.

Proof:

From a resolvable ${\mathrm{TD}}(s,g)$ we can form a resolvable ${\mathrm{TD}}(s^{\prime},g)$ by deleting $s-s^{\prime}$ groups. This resolvable design consists of $g$ parallel classes. We can take $g^{\prime}$ of them to form a $2$ - $(s^{\prime}g,s^{\prime},1)$ packing design.

Theorem 24.

Let $n,\rho,D\in\mathbb{Z}^{+}$ be such that $n/\rho$ is a prime power and $D+1\leqslant\rho\leqslant\sqrt{n}$ . There is an explicit construction of a $(D,\rho)$ -disjunct $r\times n$ matrix with constant row weight $\rho$ , constant column weight $D+1$ , and (therefore) number of rows

r=\frac{(D+1)n}{\rho},

thereby attaining the bound in Theorem 7.

Proof:

Since $n/\rho$ is a prime power, we can take a resolvable ${\mathrm{TD}}(n/\rho,n/\rho)$ from Example 1. Then, according to Lemma 23, for any $D,\rho$ such that $D+1\leqslant\rho\leqslant n/\rho$ , we can construct a $2$ - $((D+1)n/\rho,D+1,1)$ packing with $\rho$ parallel classes. Since each parallel class consists of $n/\rho$ blocks, the total number of blocks is $n$ . So, the incidence matrix $H$ of this packing is of order $r\times n$ , where $r=(D+1)n/\rho$ , and constant row weight $\rho$ . Moreover, according to Proposition 22, $H$ is $D$ -disjunct.

Combining Theorem 24 with Theorem 15 yields the following result.

Corollary 25.

Let $n,\rho,{\lambda}\in\mathbb{Z}^{+}$ be such that $n/\rho$ is a prime power and ${\lambda}\leqslant\rho\leqslant\sqrt{n}$ . There is an explicit construction of a linear $[n,k{\geqslant}n{-}r]$ code ${\mathcal{C}}$ over $\mathbb{R}$ with

r=\frac{{\lambda}n}{\rho}\quad\textrm{and}\quad\Gamma_{\lambda}({\mathcal{C}})\leqslant 2\rho=\frac{2{\lambda}n}{r}.

We note that the ${\mathrm{TD}}(q,q)$ in Example 1 is equivalent to a $[q,2]$ (extended) RS code over $\mathbb{F}_{q}$ : each block $\beta_{a,b}$ in the ${\mathrm{TD}}$ corresponds to a codeword whose positions are indexed by the elements of $y\in\mathbb{F}_{q}$ . An element $(y,z)$ contained in the block indicates that in the corresponding codeword there should be a symbol $z$ at the position which is indexed by $y$ .

In the Kautz–Singleton construction, the columns of the disjunct matrix are the codewords of the binary code that is obtained by concatenating a RS outer code over $\mathbb{F}_{q}$ with the binary code which consists of the words in $\{0,1\}^{q}$ of Hamming weight $1$ . In light of this, it is not difficult to see that the incidence matrix of the ${\mathrm{TD}}$ in Example 1 is actually the disjunct matrix from the Kautz–Singleton construction with an RS outer code of dimension $2$ . Hence, the disjunct matrices in Theorem 24 can also be obtained by carefully choosing the columns of the Kautz–Singleton disjunct matrix which correspond to the selected parallel classes.

We have the following product construction of ${\mathrm{TD}}$ ’s, which yields more disjunct matrices. The proof of this construction is straightforward and is therefore omitted.

Proposition 26.

Let $(X,{\mathfrak{G}},{\mathfrak{B}})$ be a resolvable ${\mathrm{TD}}(s,g)$ with a group partition ${\mathfrak{G}}=\{\gamma_{i}\}_{i\in{\left[{s}\right]}}$ and with parallel classes ${\mathcal{P}}_{j}$ , $j\in{\left[{g}\right]}$ , and let $(X^{\prime},{\mathfrak{G}}^{\prime},{\mathfrak{B}}^{\prime})$ be a resolvable ${\mathrm{TD}}(s,g^{\prime})$ with a group partition ${\mathfrak{G}}^{\prime}=\{\gamma_{i}^{\prime}\}_{i\in{\left[{s}\right]}}$ and with parallel classes ${\mathcal{P}}_{j}^{\prime}$ , $j\in{\left[{g^{\prime}}\right]}$ . For any two blocks $\beta\in{\mathfrak{B}}$ and $\beta^{\prime}\in{\mathfrak{B}}^{\prime}$ , denote

\beta\otimes\beta^{\prime}\triangleq\{(x_{i},x_{i}^{\prime})\,:\,i\in{\left[{s}\right]}\},

where $x_{i}$ (respectively, $x_{i}^{\prime}$ ) is the unique element in $\beta\cap\gamma_{i}$ (respectively, $\beta^{\prime}\cap\gamma_{i}^{\prime}$ ), $i\in{\left[{s}\right]}$ . Then the set of points

\bigcup_{i\in{\left[{s}\right]}}(\gamma_{i}\times\gamma_{i}^{\prime}),

the group partition $\{\gamma_{i}\times\gamma_{i}^{\prime}\,:\,i\in{\left[{s}\right]}\}$ , and the set of blocks

\{\beta\otimes\beta^{\prime}\,:\,(\beta,\beta^{\prime})\in{\mathfrak{B}}\times{\mathfrak{B}}^{\prime}\},

form a resolvable ${\mathrm{TD}}(s,gg^{\prime})$ with $gg^{\prime}$ parallel classes

{\mathcal{P}}_{j,j}\triangleq\{\beta\otimes\beta^{\prime}\,:\,(\beta,\beta^{\prime})\in{\mathcal{P}}_{j}\times{\mathcal{P}}_{j^{\prime}}^{\prime}\},\quad j,j^{\prime}\in{\left[{g}\right]}\times{\left[{g^{\prime}}\right]}.

Theorem 27.

Let $n,\rho$ be positive integers such that $\rho\leqslant\sqrt{n}$ and $\rho$ divides $n$ , and let $p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots$ be the prime factorization of $n/\rho$ . Let $p^{e}=\min_{i}\{p_{i}^{e_{i}}\}$ .

(i) For any positive integer $D<\min\{p^{e},\rho\}$ , there is an explicit construction of a $D$ -disjunct $r\times n$ matrix with constant row weight $\rho$ and constant column weight $D+1$ , where $r=(D+1)n/\rho$ (thereby attaining the bound of Theorem 7).

(ii) For any positive integer ${\lambda}$ such that ${\lambda}\leqslant\min\{p^{e},\rho\}$ , there is a linear $[n,k{\geqslant}n{-}r]$ code ${\mathcal{C}}$ over $\mathbb{R}$ with

r=\frac{{\lambda}n}{\rho}\quad\textrm{and}\quad\Gamma_{\lambda}({\mathcal{C}})\leqslant 2\rho=\frac{2{\lambda}n}{r}.

Proof:

Since $p^{e}=\min_{i}\{p_{i}^{e_{i}}\}$ , there is a resolvable ${\mathrm{TD}}(p^{e},p_{i}^{e_{i}})$ for each $i$ . Using the product construction recursively, we obtain a resolvable ${\mathrm{TD}}(p^{e},n/\rho)$ . Then, according to Lemma 23, for any $D,\rho$ such that $D<\min\{\rho,p^{e}\}$ and $\rho\leqslant n/\rho$ , we can construct a $2$ - $((D+1)n/\rho,D+1,1)$ packing with $\rho$ parallel classes. Parts (i) and (ii) then follow from Proposition 22 and Theorem 15, respectively.

Proof:

We first observe that the entries along the main diagonal of $H^{\top\scriptscriptstyle{\!}}H$ are all $1$ and that the absolute value of each off-diagonal entry is at most $\mu$ . Hence,

$\displaystyle\lVert H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\rVert_{2}^{2}$	$\displaystyle=$	$\displaystyle{\mathbf{e}}H^{\top\scriptscriptstyle{\!}}H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}$	(30)
	$\displaystyle\geqslant$	$\displaystyle\lVert{\mathbf{e}}\rVert_{2}^{2}-\mu\sum_{0\leqslant i\neq j<n}\lvert e_{i}e_{j}\rvert$
	$\displaystyle=$	$\displaystyle(1+\mu)\lVert{\mathbf{e}}\rVert_{2}^{2}-\mu\sum_{i\in{\left[{n}\right]}}\lvert e_{i}\rvert\sum_{j\in{\left[{n}\right]}}\lvert e_{j}\rvert$
	$\displaystyle=$	$\displaystyle(1+\mu)\lVert{\mathbf{e}}\rVert_{2}^{2}-\mu\lVert{\mathbf{e}}\rVert_{1}^{2}.$

We next minimize the expression (30) over ${\mathbf{e}}$ under the constraint that ${\mathbf{e}}\in{\mathcal{B}}(n,{\lambda})$ and $\lVert{\mathbf{e}}\rVert_{\infty}$ is given. Assuming without loss of generality that $e_{0}=\lVert{\mathbf{e}}\rVert_{\infty}$ and that $e_{j}=0$ for all $j\in{\left[{{\lambda}:n}\right]}$ , we claim that the minimum is attained when $\lvert e_{1}\rvert=\lvert e_{2}\rvert=\ldots=\lvert e_{{\lambda}-1}\rvert$ . Otherwise, if $\lvert e_{i}\rvert\neq\lvert e_{j}\rvert$ for some $1\leqslant i<j<{\lambda}$ then replacing both $e_{i}$ and $e_{j}$ by $(\lvert e_{i}\rvert+\lvert e_{j}\rvert)/2$ would reduce the term $\lVert{\mathbf{e}}\rVert_{2}^{2}$ while keeping $\lVert{\mathbf{e}}\rVert_{1}^{2}$ unchanged.

Substituting $\lvert e_{i}\rvert\leftarrow x$ for all $i\in{\left[{1:{\lambda}}\right]}$ in (30) yields the following quadratic expression in $x$ :

(1+\mu)(e_{0}^{2}+({\lambda}-1)x^{2})-\mu(e_{0}+({\lambda}-1)x)^{2}.

(31)

The coefficient of $x^{2}$ is $(1-({\lambda}-2)\mu)({\lambda}-1)$ , which is positive under our assumption ${\lambda}\leqslant\lceil 1/\mu\rceil$ ; hence, (31) attains a global minimum at $x_{\min}=e_{0}\cdot\eta_{\lambda}(\mu)$ . Plugging this value into (31) yields the result.

The lower bound in Lemma 12 can be written more explicitly as

\lVert H{\mathbf{e}}^{\top\scriptscriptstyle{\!}}\rVert_{2}^{2}\geqslant\frac{1+\mu}{1-({\lambda}-2)\mu}\cdot\left\lparen 1-({\lambda}-1)\mu\right\rparen\cdot\lVert{\mathbf{e}}\rVert_{\infty}^{2}.

Comparing with (10), the bound in Lemma 12 is expressed in terms of $\lVert{\mathbf{e}}\rVert_{\infty}$ rather than $\lVert{\mathbf{e}}\rVert_{2}$ , yet the multiplying constant therein is larger when $\mu>0$ and ${\lambda}>1$ .

References

[1] B. E. Boser, E. Sackinger, J. Bromley, Y. L. Cun, and L. D. Jackel, “An analog neural network processor with programmable topology,” IEEE J. Solid-State Circuits, vol. 26, no. 12, pp. 2017–2025, Dec. 1991.
[2] J. Bourgain, S. J. Dilworth, K. Ford, S. Konyagin, and D. Kutzarova, “Explicit constructions of RIP matrices and related problems,” Duke Math. J., vol. 159, no. 1, pp. 145–185, 2011.
[3] E. Candès, “The restricted isometry property and its implications for compressed sensing,” C.R. Acad. Sci. Paris, Ser. I, vol. 346, pp. 589–592, 2008.
[4] E. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489–509, Feb. 2006.
[5] C. Colbourne and J. Dinitz, Handbook of combinatorial designs, second edition. CRC press Boca Raton, FL, 2007.
[6] D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289–1306, Apr. 2006.
[7] A. G. D’yachkov and V. V. Rykov, “Bounds on the length of disjunctive codes,” Probl. Peredachi Inf., vol. 18, no. 3, pp. 7–13, 1982.
[8] Z. Füredi, “On $r$ -cover-free families,” J. Combin. Theory Ser. A, vol. 73, no. 1, pp. 172–173, 1996.
[9] M. Hu, C. E. Graves, C. Li, Y. Li, N. Ge, E. Montgomery, N. Davila, H. Jiang, R. S. Williams, J. J. Yang, Q. Xia, and J. P. Strachan, “Memristor-based analog computation and neural network classification with a dot product engine,” in Adv. Mater., vol. 30, Mar. 2018, paper no. 1705914.
[10] M. Hu, J. P. Strachan, Z. Li, E. M. Grafals, N. Davila, C. Graves, S. Lam, N. Ge, J. Yang, and R. S. Williams, “Dot-product engine for neuromorphic computing: Programming 1T1M crossbar to accelerate matrix-vector multiplication,” in Proc. 53rd ACM/EDAC/IEEE Design Automat. Conf. (DAC), Austin, TX, 2016, paper no. 19.
[11] H. A. Inan, P. Kairouz, and A. Özgür, “Sparse combinatorial group testing,” IEEE Trans. Inf. Theory, vol. 66, no. 5, pp. 2729–2742, May 2020.
[12] G. Katona and A. Seress, “Greedy construction of nearly regular graphs,” European J. of Combin., vol. 14, pp. 213–229, 1993.
[13] W. Kautz and R. Singleton, “Nonrandom binary superimposed codes,” IEEE Trans. Inf. Theory, vol. 10, no. 4, pp. 363–377, Oct. 1964.
[14] F. J. Kub, K. K. Moon, I. A. Mack, and F. M. Long, “Programmable analog vector-matrix multipliers,” IEEE J. Solid-State Circuits, vol. 25, no. 1, pp. 207–214, Feb. 1990.
[15] D. Lubell, “A short proof of Sperner’s lemma,” J. Combin. Theory Ser. A, vol. 1, no. 2, p. 299, 1966.
[16] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Amsterdam: North-Holland, 1977.
[17] E. Porat and A. Rothschild, “Explicit non-adaptive combinatorial group testing schemes,” IEEE Trans. Inf. Theory, vol. 57, no. 12, pp. 7982–7989, Dec. 2011.
[18] R. M. Roth, “Fault-tolerant dot-product engines,” IEEE Trans. Inf. Theory, vol. 65, no. 4, pp. 2046–2057, Apr. 2019.
[19] ——, “Analog error-correcting codes,” IEEE Trans. Inf. Theory, vol. 66, no. 7, pp. 4075–4088, Jul. 2020.
[20] ——, “Fault-tolerant neuromorphic computing on nanoscale crossbar architectures,” in Proc. 2020 IEEE Inf. Theory Workshop (ITW), Mumbai, India, 2022, pp. 202–207.
[21] ——, “Correction to “analog error-correcting codes”,” IEEE Trans. Inf. Theory, vol. 69, no. 6, pp. 3793–3794, Jan. 2023.
[22] A. Shafiee, A. Nag, N. Muralimanohar, R. Balasubramonian, J. P. Strachan, M. Hu, R. S. Williams, and V. Srikumar, “ISAAC: A convolutional neural network accelerator with in-situ analog arithmetic in crossbars,” in Proc. ACM/IEEE 43rd Annu. Int. Symp. Comput. Archit. (ISCA), Seoul, Korea, Jun. 2016, pp. 14–26.

Multiple-Error-Correcting Codes for Analog Computing on Resistive Crossbars

Abstract

Index Terms:

I Introduction

II Preliminaries

II-A Analog error-correcting codes

Theorem 1 ([19],[21]).

Proposition 2.

Proof:

Theorem 3 ([19, Proposition 6]).

Theorem 4 ([20, Proposition 5]).

II-B Disjunct matrices

Theorem 5 ([11, Theorems 2 and 3]).

Lemma 6.

Proof:

Theorem 7 ([11, Theorem 8]).

Theorem 8 ([11, Theorem 8]).

Theorem 9.

Proof:

III The Spherical-Code Construction: Locating Multiple Errors

Remark 1.

Remark 2.

Proposition 10 ([2, Proposition 1]).

Theorem 11.

Proof:

Remark 3.

Lemma 12.

Theorem 13.

Proof:

Corollary 14.

Proof:

Remark 4.

Remark 5.

IV Code Construction Based on Disjunct Matrices

Theorem 15.

Proof:

Corollary 16.

Remark 6.

IV-A Decoder for the generic disjunct construction

Theorem 17.

Proof:

IV-B Decoder when columns in HH are also weight-constrained

Lemma 18.

Proof:

Remark 7.

Theorem 19.

Proof:

Lemma 20.

Proof:

Theorem 21.

Proof:

V Constructions of Disjunct Matrices with Weight-Constrained Rows and Columns

Proposition 22.

Proof:

Example 1.

Lemma 23.

Proof:

Theorem 24.

Proof:

Corollary 25.

Proposition 26.

Theorem 27.

Proof:

Proof:

References

Multiple-Error-Correcting Codes for
Analog Computing on Resistive Crossbars

IV-B Decoder when columns in $H$ are also weight-constrained