Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2401.17801 · IEEE International Symposium on Information Theory (ISIT)

Weighted-Hamming Metric for Parallel Channels

Sebastian Bitzer, Alberto Ravagnani, Violetta Weger

Published Jul 7, 2024• 1 citation
arXivHTMLPDF

Abstract

Independent parallel q-ary symmetric channels are a suitable transmission model for several applications. The weighted-Hamming metric is tailored to this setting and enables optimal decoding performance. We show that some weighted-Hamming-metric codes exhibit the unusual property that all errors beyond half the minimum distance can be corrected. Nevertheless, a tight relation between the error-correction capability of a code and its minimum distance can be established. Generalizing their Hamming-metric counterparts, upper and lower bounds on the cardinality of a code with a given weighted-Hamming distance are obtained. Finally, we propose a simple code construction with optimal minimum distance for specific parameters.

DOI
10.1109/isit57864.2024.10619239

Related papers

Weight distribution bounds to relate minimum distance, list decoding, and symmetric channel performance

Donald Kougang-Yombi, Jan Hązła

We study relationships between worst-case and random-noise properties of error correcting codes. More concretely, we consider connections between minimum distance, list decoding radius, and block error probability on noisy channels. A recent result of Pernice, Sprumont, and Wootters established the tight connection between list decoding radius and symmetric channel performance for linear codes. We extend this result to general codes. The proof proceeds by directly bounding the weight distribution rather than by sharp threshold techniques. We then turn to the relation between minimum distance and symmetric channel performance. The results we just described imply that a $q$-ary code of relative distance $δ$ has vanishing error probability on the symmetric channel up to the Johnson radius $J_q(δ)$. We improve upon this bound in the case of linear codes, for a range $δ$, for $q\ge 4$. In our proof we consider the \emph{erasure} properties of codes, and bound their weight distribution through inequalities introduced by Samorodnitsky. The latter part of the proof gives a more general technique that bounds the symmetric channel performance of a linear code with constant relative distance and good erasure channel performance.

arXiv:2604.02994•Apr 3, 2026•0 citations

A lower bound on the minimum distance of chained Gallager codes

Victor Zyablov, Florian Hug, Rolf Johannesson

Based on the combination of two regular Gallager (Low-Density Parity-Check (LDPC)) codes, we will introduce a new code construction, called Chained Gallager codes. Following Gallager’s method we will derive a lower bound on the normalized minimum distance for the ensemble of Chained Gallager codes. Applying this lower bound on the normalized minimum distance to different transmissions schemes with two parallel and independent channels, the error correcting capabilities will be studied, stressing the advantages of Chained Gallager codes.

•Jan 1, 2009•0 citations

Construction of Quasi-Cyclic GF(q)-LDPC Codes Achieving the Upper Bound on the Minimum Hamming Distance

Xinmei Wang

In order to construct nonbinary low-density parity-check(LDPC) codes with good waterfall and error floor properties,a method to improve the minimum Hamming distance of a class of nonbinary quasi-cyclic(QC) LDPC codes is presented.Two upper bounds on the minimum Hamming distance are derived for the nonbinary QC LDPC codes whose parity-check matrices consist of weight-2 columns.A special base matrix design allowing linear encoding in a parallel manner is also proposed.In addition,the design principals are given,according to which,the parallel and efficiently encodable codes reaching the upper bound on the minimum Hamming distance can be developed.Simulation shows that the proposed codes have both good waterfall and error floor properties.

Beijing Youdian Xueyuan xuebao•Jan 1, 2012•0 citations

The subfield metric and its application to quantum error correction

Markus Grassl, Anna-Lena Trautmann, Violetta Weger

We introduce a new weight and corresponding metric over finite extension fields for asymmetric error correction. The weight distinguishes between elements from the base field and the ones outside of it, which is motivated by asymmetric quantum codes. We set up the theoretic framework for this weight and metric, including upper and lower bounds, asymptotic behavior of random codes, and we show the existence of an optimal family of codes achieving the Singleton-type upper bound.

arXiv:2212.00431•Journal of Algebra and Its Applications•Sep 16, 2023•0 citations

On Application of the Modulus Metric to Solving the Minimum Euclidean Distance Decoding Problem

Vyacheslav Davydov

We prove equivalence of using the modulus metric and Euclidean metric in solving the soft decoding problem for a memoryless discrete channel with binary input and Q -ary output. For such a channel, we give an example of a construction of binary codes correcting t binary errors in the Hamming metric. The constructed codes correct errors at the output of a demodulator with Q quantization errors as ( t + 1)( Q − 1) − 1 errors in the modulus metric. The obtained codes are shown to have polynomial decoding complexity.

Problems of Information Transmission•Apr 1, 2019•2 citations

On Optimal Codes for Additive Noise Channels

Al Moufid

One of the fundamental goals of coding theory is to find optimal codes, in terms of achieving the largest probability of correct decoding. Most of the foundational works on optimal codes use three assumptions. First, optimality is defined relative to a code’s rate and minimum Hamming distance, and not its probability of correct decoding. The problem is that the former conditions are not always good indicators for the latter. Second, for practicality only optimal codes with some kind of algebraic structure are considered, the most common being linearity. While linear codes have practical advantages, it is known that often the best codes are not linear. Thirdly, codes are usually proven optimal only for memoryless channels. However, there are many real-life channels which exhibit memory. Attempts to extend these results often make use of interleaving. This technique renders some of these channels with memory equivalent to a memoryless one with respect to the decoder. However, this comes with two disadvantages namely: we fail to exploit the channel’s memory and we add latency to the communication system. In this thesis, we seek optimal codes which require milder conditions than those aforementioned. Specifically, we describe a class of optimal q-ary block codes over additive noise channels, which are a generalization of a class of optimal codes from Hamada. We prove these codes are optimal using our novel method of analyzing the probability of correct decoding of block codes based on so-called error indexed decoder regions. Our method allows us to prove that these codes must be either a linear code or a coset of one.

•Sep 22, 2020•0 citations
Independent parallel q-ary symmetric channels are a suitable transmission model for several applications. The weighted-Hamming metric is tailored to this setting and enables optimal decoding performance. We show that some weighted-Hamming-metric codes exhibit the unusual property that all errors beyond half the minimum distance can be corrected. Nevertheless, a tight relation between the error-correction capability of a code and its minimum distance can be established. Generalizing their Hamming-metric counterparts, upper and lower bounds on the cardinality of a code with a given weighted-Hamming distance are obtained. Finally, we propose a simple code construction with optimal minimum distance for specific parameters.
We study relationships between worst-case and random-noise properties of error correcting codes. More concretely, we consider connections between minimum distance, list decoding radius, and block error probability on noisy channels. A recent result of Pernice, Sprumont, and Wootters established the tight connection between list decoding radius and symmetric channel performance for linear codes. We extend this result to general codes. The proof proceeds by directly bounding the weight distribution rather than by sharp threshold techniques. We then turn to the relation between minimum distance and symmetric channel performance. The results we just described imply that a qqq-ary code of relative distance δδδ has vanishing error probability on the symmetric channel up to the Johnson radius Jq(δ)J_q(δ)Jq​(δ). We improve upon this bound in the case of linear codes, for a range δδδ, for q≥4q\ge 4q≥4. In our proof we consider the \emph{erasure} properties of codes, and bound their weight distribution through inequalities introduced by Samorodnitsky. The latter part of the proof gives a more general technique that bounds the symmetric channel performance of a linear code with constant relative distance and good erasure channel performance.
Based on the combination of two regular Gallager (Low-Density Parity-Check (LDPC)) codes, we will introduce a new code construction, called Chained Gallager codes. Following Gallager’s method we will derive a lower bound on the normalized minimum distance for the ensemble of Chained Gallager codes. Applying this lower bound on the normalized minimum distance to different transmissions schemes with two parallel and independent channels, the error correcting capabilities will be studied, stressing the advantages of Chained Gallager codes.
In order to construct nonbinary low-density parity-check(LDPC) codes with good waterfall and error floor properties,a method to improve the minimum Hamming distance of a class of nonbinary quasi-cyclic(QC) LDPC codes is presented.Two upper bounds on the minimum Hamming distance are derived for the nonbinary QC LDPC codes whose parity-check matrices consist of weight-2 columns.A special base matrix design allowing linear encoding in a parallel manner is also proposed.In addition,the design principals are given,according to which,the parallel and efficiently encodable codes reaching the upper bound on the minimum Hamming distance can be developed.Simulation shows that the proposed codes have both good waterfall and error floor properties.
We prove equivalence of using the modulus metric and Euclidean metric in solving the soft decoding problem for a memoryless discrete channel with binary input and Q -ary output. For such a channel, we give an example of a construction of binary codes correcting t binary errors in the Hamming metric. The constructed codes correct errors at the output of a demodulator with Q quantization errors as ( t + 1)( Q − 1) − 1 errors in the modulus metric. The obtained codes are shown to have polynomial decoding complexity.
One of the fundamental goals of coding theory is to find optimal codes, in terms of achieving the largest probability of correct decoding. Most of the foundational works on optimal codes use three assumptions. First, optimality is defined relative to a code’s rate and minimum Hamming distance, and not its probability of correct decoding. The problem is that the former conditions are not always good indicators for the latter. Second, for practicality only optimal codes with some kind of algebraic structure are considered, the most common being linearity. While linear codes have practical advantages, it is known that often the best codes are not linear. Thirdly, codes are usually proven optimal only for memoryless channels. However, there are many real-life channels which exhibit memory. Attempts to extend these results often make use of interleaving. This technique renders some of these channels with memory equivalent to a memoryless one with respect to the decoder. However, this comes with two disadvantages namely: we fail to exploit the channel’s memory and we add latency to the communication system. In this thesis, we seek optimal codes which require milder conditions than those aforementioned. Specifically, we describe a class of optimal q-ary block codes over additive noise channels, which are a generalization of a class of optimal codes from Hamada. We prove these codes are optimal using our novel method of analyzing the probability of correct decoding of block codes based on so-called error indexed decoder regions. Our method allows us to prove that these codes must be either a linear code or a coset of one.