In recent work, it has been shown that maintaining reliability in analog vector--matrix multipliers can be modeled as the following coding problem. Vectors in $\mathbb{R}^k$ are encoded into codewords of a linear $[n,k,d]$ code $C$ over $\mathbb{R}$ . For prescribed positive reals $δ< Δ$ , additive errors of magnitude at most $δ$ are tolerable and need no handling, yet outlying errors of magnitude greater than $Δ$ are to be located or detected. The trade-off between the ratio $Δ/δ$ and the number of outlying errors that can be handled is determined by the height profile of $C$ ; as such, the height profile provides a finer description of the error handling capability of $C$ , compared to the minimum distance $d$ , which only determines the number of correctable errors. This work contains a further study of the notion of the height profile. Several characterizations of the height profile are presented, thereby yielding methods for computing it. The starting point is formulating this computation as an optimization problem that is solved by a set of linear programs. This, in turn, leads to a combinatorial characterization of the height profile as a maximum (or max--min) over a certain finite set of codewords of $C$ . Moreover, this characterization is shown to have a simple geometric interpretation when the columns of the generator matrix of $C$ all have the same $L_2$ norm. Through examples of several code families, it is demonstrated how the results herein can be used to compute the height profile explicitly.In recent work, it has been shown that maintaining reliability in analog vector--matrix multipliers can be modeled as the following coding problem. Vectors in $\mathbb{R}^k$ are encoded into codewords of a linear $[n,k,d]$ code $C$ over $\mathbb{R}$. For prescribed positive reals $δ< Δ$, additive errors of magnitude at most $δ$ are tolerable and need no handling, yet outlying errors of magnitude greater than $Δ$ are to be located or detected. The trade-off between the ratio $Δ/δ$ and the number of outlying errors that can be handled is determined by the height profile of $C$; as such, the height profile provides a finer description of the error handling capability of $C$, compared to the minimum distance $d$, which only determines the number of correctable errors. This work contains a further study of the notion of the height profile. Several characterizations of the height profile are presented, thereby yielding methods for computing it. The starting point is formulating this computation as an optimization problem that is solved by a set of linear programs. This, in turn, leads to a combinatorial characterization of the height profile as a maximum (or max--min) over a certain finite set of codewords of $C$. Moreover, this characterization is shown to have a simple geometric interpretation when the columns of the generator matrix of $C$ all have the same $L_2$ norm. Through examples of several code families, it is demonstrated how the results herein can be used to compute the height profile explicitly.

arXiv:2602.20366IEEE International Symposium on Information Theory (ISIT)Jun 1, 20260 citations

Tight Lower Bounds on The Single-Error Detection Threshold for Analog Error-Correcting Codes

Zhengyi Jiang, Wenhao Liu, Zhongyi Huang +3 more

Analog error-correcting codes (Analog ECCs) for approximate vector-matrix multiplication have been extensively studied as means to achieve fault-tolerant in-memory computation. The theoretical foundations for such coding schemes, particularly the characterization of their correction capabilities via the height profile, have been well established in recent literature. In this paper, we focus on the case of single-error detection Analog ECCs. Among several open problems related to this case proposed by Ron M. Roth in [1], Problem 1 asks: "Identify the values of $k$ and $n$ for which every linear $[n, k]$ code $\mathcal{C}$ over $\mathbb{R}$ satisfies: $\mathsf{h}_1(\mathcal{C}):=\max_{\boldsymbol{c}\in \mathcal{C}\setminus{\{\boldsymbol{0}\}}}\mathsf{h}_1(\boldsymbol{c})\geq \Big\lceil \frac{k}{n-k} \Big\rceil.\text{"}$ Here, for any $\boldsymbol{x}\in\mathbb{R}^n$ , $\mathsf{h}_1(\boldsymbol{x})$ represents the ratio between the largest and second largest absolute values of $\boldsymbol{x}$ 's entries. As the simplest special case of Problem 1 (with $n-k=2$ ), the following problem was posed as Problem 2 in [1]: "Must every $(n-2)$ -dimensional subspace of $\mathbb{R}^n$ , $n$ even, contain a nonzero vector in which the ratio between the largest and second largest absolute values of its entries is at least $(n/2)-1$ ?" These problems directly pertain to the lower bounds on the single-error detection threshold for Analog ECCs: Problem 1 corresponds to arbitrary $n-k$ and Problem 2 corresponds to $n-k=2$ . In this paper, we provide an affirmative answer to Problem 2 and a rigorous proof using theories related to convex optimization. Furthermore, we extend our analytical method to show that the lower bound in Problem 1 is tight for the case where $n-k$ divides $k$ . Our results fill the gap in the lower bound theory of thresholds for single-error detection in Analog ECCs.Analog error-correcting codes (Analog ECCs) for approximate vector-matrix multiplication have been extensively studied as means to achieve fault-tolerant in-memory computation. The theoretical foundations for such coding schemes, particularly the characterization of their correction capabilities via the height profile, have been well established in recent literature. In this paper, we focus on the case of single-error detection Analog ECCs. Among several open problems related to this case proposed by Ron M. Roth in [1], Problem 1 asks: "Identify the values of $k$ and $n$ for which every linear $[n, k]$ code $\mathcal{C}$ over $\mathbb{R}$ satisfies: $$\mathsf{h}_1(\mathcal{C}):=\max_{\boldsymbol{c}\in \mathcal{C}\setminus{\{\boldsymbol{0}\}}}\mathsf{h}_1(\boldsymbol{c})\geq \Big\lceil \frac{k}{n-k} \Big\rceil.\text{"}$$ Here, for any $\boldsymbol{x}\in\mathbb{R}^n$, $\mathsf{h}_1(\boldsymbol{x})$ represents the ratio between the largest and second largest absolute values of $\boldsymbol{x}$'s entries. As the simplest special case of Problem 1 (with $n-k=2$), the following problem was posed as Problem 2 in [1]: "Must every $(n-2)$-dimensional subspace of $\mathbb{R}^n$, $n$ even, contain a nonzero vector in which the ratio between the largest and second largest absolute values of its entries is at least $(n/2)-1$?" These problems directly pertain to the lower bounds on the single-error detection threshold for Analog ECCs: Problem 1 corresponds to arbitrary $n-k$ and Problem 2 corresponds to $n-k=2$. In this paper, we provide an affirmative answer to Problem 2 and a rigorous proof using theories related to convex optimization. Furthermore, we extend our analytical method to show that the lower bound in Problem 1 is tight for the case where $n-k$ divides $k$. Our results fill the gap in the lower bound theory of thresholds for single-error detection in Analog ECCs.

arXiv:2605.08973May 9, 20260 citations

On asymmetric error-correcting codes

Robert Stephen Cunningham

Mar 1, 19821 citation

In recent work, it has been shown that maintaining reliability in analog vector--matrix multipliers can be modeled as the following coding problem. Vectors in

\mathbb{R}^k

are encoded into codewords of a linear

[n,k,d]

code

C

over

\mathbb{R}

. For prescribed positive reals

δ< Δ

, additive errors of magnitude at most

δ

are tolerable and need no handling, yet outlying errors of magnitude greater than

Δ

are to be located or detected. The trade-off between the ratio

Δ/δ

and the number of outlying errors that can be handled is determined by the height profile of

C

; as such, the height profile provides a finer description of the error handling capability of

C

, compared to the minimum distance

d

, which only determines the number of correctable errors. This work contains a further study of the notion of the height profile. Several characterizations of the height profile are presented, thereby yielding methods for computing it. The starting point is formulating this computation as an optimization problem that is solved by a set of linear programs. This, in turn, leads to a combinatorial characterization of the height profile as a maximum (or max--min) over a certain finite set of codewords of

C

. Moreover, this characterization is shown to have a simple geometric interpretation when the columns of the generator matrix of

C

all have the same

L_2

norm. Through examples of several code families, it is demonstrated how the results herein can be used to compute the height profile explicitly.

k

and

n

for which every linear

[n, k]

code

\mathcal{C}

over

\mathbb{R}

satisfies:

\mathsf{h}_1(\mathcal{C}):=\max_{\boldsymbol{c}\in \mathcal{C}\setminus{\{\boldsymbol{0}\}}}\mathsf{h}_1(\boldsymbol{c})\geq \Big\lceil \frac{k}{n-k} \Big\rceil.\text{"}

Here, for any

\boldsymbol{x}\in\mathbb{R}^n

\mathsf{h}_1(\boldsymbol{x})

represents the ratio between the largest and second largest absolute values of

\boldsymbol{x}

's entries. As the simplest special case of Problem 1 (with

n-k=2

), the following problem was posed as Problem 2 in [1]: "Must every

(n-2)

-dimensional subspace of

\mathbb{R}^n

n

even, contain a nonzero vector in which the ratio between the largest and second largest absolute values of its entries is at least

(n/2)-1

?" These problems directly pertain to the lower bounds on the single-error detection threshold for Analog ECCs: Problem 1 corresponds to arbitrary

n-k

and Problem 2 corresponds to

n-k=2

. In this paper, we provide an affirmative answer to Problem 2 and a rigorous proof using theories related to convex optimization. Furthermore, we extend our analytical method to show that the lower bound in Problem 1 is tight for the case where

n-k

divides

k

. Our results fill the gap in the lower bound theory of thresholds for single-error detection in Analog ECCs.