HWHengjia Wei

Hengjia Wei

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Hengjia Wei has a total of 44 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Elias-type Bounds for Codes in the Symmetric Limited-Magnitude Error Channel

    by Zhihao Guan, Hengjia Wei

    We study perfect error-correcting codes in $\mathbb{Z}^n$ for the symmetric limited-magnitude error channel, where at most $e$ coordinates of an integer vector may be altered by a value whose magnitude is at most $s$. Geometrically, such codes correspond to tilings of $\mathbb{Z}^n$ by the symmetric limited-magnitude error ball $\mathcal{B}(n,e,s,s)$. Given $n$ and $s$, we adapt the geometric ideas underlying the Elias bound for the Hamming metric to the distance $d_s$ tailed for this channel, and derive new necessary conditions on $e$ for the existence of perfect codes / tilings, without assuming any lattice structure. Our main results identify two distinct regimes depending on the error magnitude. For small error magnitudes ($s \in \{1, 2\}$), we prove that if the number of correctable errors does not exceed a certain fraction of $n$, then it is asymptotically bounded by $e = \mathcal{O}(\sqrt{n \log n})$. In contrast, for larger magnitudes ($s \geq 3$), we establish a significantly sharper bound of $e < \sqrt{12.36n}$, which holds without any restriction on $e$ being below a given fraction of $n$. Finally, by extending our method to non-perfect codes, we derive an upper bound on packing density, showing that for codes correcting a linear or $Ω(\sqrt{n})$ number of errors, the density is bounded by a factor inversely proportional to the error magnitude $s$.

  • Combinatorial Alphabet-Dependent Bounds for Insdel Codes

    by Xiangliang Kong, Itzhak Tamo, Hengjia Wei

    Error-correcting codes resilient to synchronization errors such as insertions and deletions are known as insdel codes. In this paper, we present several new combinatorial upper and lower bounds on the maximum size of q-ary insdel codes. Our main upper bound is a sphere-packing bound obtained by solving a linear programming (LP) problem. It improves upon previous results for cases when the distance d or the alphabet size q is large. Our first lower bound is derived from a connection between insdel codes and matchings in special hypergraphs. This lower bound, together with our upper bound, shows that for fixed block length n and edit distance d, when q is sufficiently large, the maximum size of insdel codes is $ \frac {q^{n-\frac {d}{2}+1}}{\binom {n}{\frac {d}{2}-1}}(1 \pm o(1))$ . The second lower bound refines Alon et al.’s recent logarithmic improvement on Levenshtein’s GV-type bound and extends its applicability to large q and d.


  • Linearized Reed-Solomon Codes With Support-Constrained Generator Matrix and Applications in Multi-Source Network Coding

    by Hedongliang Liu, Hengjia Wei, Antonia Wachter-Zeh, Moshe Schwartz

    Linearized Reed-Solomon (LRS) codes are evaluation codes based on skew polynomials. They achieve the Singleton bound in the sum-rank metric and therefore are known as maximum sum-rank distance (MSRD) codes. In this work, we give necessary and sufficient conditions for the existence of MSRD codes with a support-constrained generator matrix. The conditions on the support constraints are identical to those for MDS codes and MRD codes. The required field size for an $[n,k]_{q^{m}}$ LRS codes with support-constrained generator matrix is $q\geq \ell +1$ and $m\geq \max _{l\in [\ell]}\{k-1+\log _{q}k, n_{l}\}$ , where $\ell $ is the number of blocks and $n_{l}$ is the size of the l-th block. The special cases of the result coincide with the known results for Reed-Solomon codes and Gabidulin codes. For the support constraints that do not satisfy the necessary conditions, we derive the maximum sum-rank distance of a code whose generator matrix fulfills the constraints. Such a code can be constructed from a subcode of an LRS code with a sufficiently large field size. Moreover, as an application in network coding, the conditions can be used as constraints in an integer programming problem to design distributed LRS codes for a distributed multi-source network.


  • Open Access

    Linear Network Coding for Robust Function Computation and Its Applications in Distributed Computing

    by Hengjia Wei, Min Xu, Gennian Ge

    We investigate linear network coding in the context of robust function computation, where a sink node is tasked with computing a target function of messages generated at multiple source nodes. In a previous work, a new distance measure was introduced to evaluate the error tolerance of a linear network code for function computation, along with a Singleton-like bound for this distance. In this paper, we first present a minimum distance decoder for these linear network codes. We then focus on the sum function and the identity function, showing that in any directed acyclic network there are two classes of linear network codes for these target functions, respectively, that attain the Singleton-like bound. Additionally, we explore the application of these codes in distributed computing and design a distributed gradient coding scheme in a heterogeneous setting, optimizing the trade-off between straggler tolerance, computation cost, and communication cost. This scheme can also defend against Byzantine attacks.

  • Reconstruction From Noisy Substrings

    by Hengjia Wei, Moshe Schwartz, Gennian Ge

    This paper studies the problem of encoding messages into sequences which can be uniquely recovered from some noisy observations about their substrings. The observed reads comprise consecutive substrings with some given minimum overlap. This coded reconstruction problem has applications in DNA storage. We consider both single-strand reconstruction codes and multi-strand reconstruction codes, where the message is encoded into a single strand or a set of multiple strands, respectively. Various parameter regimes are studied. New codes are constructed, some of whose rates asymptotically attain the upper bounds.


  • Open Access

    Combinatorial alphabet-dependent bounds for insdel codes

    by Xiangliang Kong, Itzhak Tamo, Hengjia Wei

    Error-correcting codes resilient to synchronization errors such as insertions and deletions are known as insdel codes. Due to their important applications in DNA storage and computational biology, insdel codes have recently become a focal point of research in coding theory. In this paper, we present several new combinatorial upper and lower bounds on the maximum size of $q$-ary insdel codes. Our main upper bound is a sphere-packing bound obtained by solving a linear programming (LP) problem. It improves upon previous results for cases when the distance $d$ or the alphabet size $q$ is large. Our first lower bound is derived from a connection between insdel codes and matchings in special hypergraphs. This lower bound, together with our upper bound, shows that for fixed block length $n$ and edit distance $d$, when $q$ is sufficiently large, the maximum size of insdel codes is $ \frac{q^{n-\frac{d}{2}+1}}{{n\choose \frac{d}{2}-1}}(1 \pm o(1))$. The second lower bound refines Alon et al.'s recent logarithmic improvement on Levenshtein's GV-type bound and extends its applicability to large $q$ and $d$.

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

    by Hengjia Wei, Ron M. Roth

    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–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.


  • Bounds on the Minimum Field Size of Network MDS Codes

    by Hengjia Wei, Moshe Schwartz

    We study network maximum distance separable (MDS) codes, which are a class of network error-correcting codes whose distance attains the Singleton-type bound. The minimum field size of a network MDS code is of particular interest, since it impacts the computing complexity at the network nodes. Previous constructions of network MDS codes, which are applicable to general single-source multicast networks, require large field sizes. In this paper, for two specific classes of network topologies, we derive upper and lower bounds on the minimum field size of the corresponding network MDS codes and present explicit constructions. The proposed upper bounds significantly improve upon the previous ones and differ from the lower bounds only by a small factor, which is asymptotically no more than 2. Additionally, we extend the concept of linear network error-correction coding from the scalar case to the vector case, and demonstrate a class of networks in which the minimum field size of the vector network MDS code is substantially smaller than that of the scalar case.


  • Arbitrary Modulation of Average Dwell Time in Discrete-Time Markov Chains Based on Tunneling Magnetoresistance Effect

    by Xihui Yuan, Jiajia Jian, Zheng Chai, Hengjia Wei, Xue Zhou, Yizhu Wen, Yadong Liu, Wentao Yan, Yingtong He, Jian Fu Zhang, et al.

    Stochastic processes (SPs) are widely used in many real-world fields, especially AI algorithms and models. A discrete-time Markov chain (DTMC) is a fundamental SP where the probability of each event depends only on the state attained in the previous event. DTMC is extensively used in signal processing and information theory, but the hardware generation of DTMC remains hindered by the difficulty in arbitrarily modulating the averaged dwell times (ADTs), i.e. the average time that the DTMC stays at one state. In this paper, we propose a two-step procedure to modulate the ADTs of a DTMC generated from single magnetic tunnel junction (MTJ), without being limited by additional restrictions such as a fixed ratio between the ADTs, widening the SP applications scope of the MTJ-based DTMC. This method has been verified via mathematical derivation and electrical characterization. The generation throughput and power consumption can also be conveniently modulated. This procedure provides a new hardware solution for the generation of stochastic signal in semiconductor IC chips.


  • Open Access

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

    by Hengjia Wei, Ron M. Roth

    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 $\zeroone$~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.