Hengjia Wei
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
Research Subjects
Hengjia Wei has a total of 44 co-authors. Here are the top co-authors by number of shared publications:
- Moshe Schwartz
Department of Electrical and Computer Engineering McMaster University L8S 4K1 Hamilton ON Canada
17 shared publications - Gennian Ge
Capital Normal University
12 shared publications - Antonia Wachter-Zeh
Institute for Communications Engineering, Technical University of Munich (TUM), Munich, Germany
5 shared publications - Hedongliang Liu
Technical University of Munich
5 shared publications - Xin Wang
Capital Normal Univ, Sch Math Sci, Beijing 100048, Peoples R China
4 shared publications - Yeow Meng Chee
National University of Singapore, Singapore, Singapore
4 shared publications
Latest Publications
- Open Access
Elias-type Bounds for Codes in the Symmetric Limited-Magnitude Error Channel
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$.Open AccessElias-type Bounds for Codes in the Symmetric Limited-Magnitude Error Channel
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$. - 25 February 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (5) , 3544-3559
Combinatorial Alphabet-Dependent Bounds for Insdel Codes
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.
- 25 February 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (5) , 3544-3559
Combinatorial Alphabet-Dependent Bounds for Insdel Codes
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.
- 27 November 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (2) , 895-913
Linearized Reed-Solomon Codes With Support-Constrained Generator Matrix and Applications in Multi-Source Network Coding
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.- 27 November 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (2) , 895-913
Linearized Reed-Solomon Codes With Support-Constrained Generator Matrix and Applications in Multi-Source Network Coding
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
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.
Open AccessLinear Network Coding for Robust Function Computation and Its Applications in Distributed Computing
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.
- 3 September 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (11) , 7757-7776
Reconstruction From Noisy Substrings
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.
- 3 September 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (11) , 7757-7776
Reconstruction From Noisy Substrings
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
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$.Open AccessCombinatorial alphabet-dependent bounds for insdel codes
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$. - 7 August 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (12) , 8647-8658
Multiple-Error-Correcting Codes for Analog Computing on Resistive Crossbars
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.
- 7 August 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (12) , 8647-8658
Multiple-Error-Correcting Codes for Analog Computing on Resistive Crossbars
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.
- 25 June 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (8) , 5533-5543
Bounds on the Minimum Field Size of Network MDS Codes
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.
- 25 June 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (8) , 5533-5543
Bounds on the Minimum Field Size of Network MDS Codes
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.
- 29 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Electron Device Letters
- Vol. 45 (7) , 1349-1352
Arbitrary Modulation of Average Dwell Time in Discrete-Time Markov Chains Based on Tunneling Magnetoresistance Effect
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.
- 29 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Electron Device Letters
- Vol. 45 (7) , 1349-1352
Arbitrary Modulation of Average Dwell Time in Discrete-Time Markov Chains Based on Tunneling Magnetoresistance Effect
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
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.
Open AccessMultiple-Error-Correcting Codes for Analog Computing on Resistive Crossbars
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.