arxiv: 2604.07730 · v1 · submitted 2026-04-09 · 💻 cs.IT · math.IT

The Asymmetric Hamming Bidistance and Distributions over Binary Asymmetric Channels

Shukai Wang , Cuiling Fan , Chunming Tang , Zhengchun Zhou This is my paper

Pith reviewed 2026-05-10 18:20 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords asymmetric Hamming bidistancebinary asymmetric channelmaximum-likelihood decodingerror probability boundweight distributionprojective codesstrongly regular graphs

0 comments p. Extension

The pith

The asymmetric Hamming bidistance distribution yields a new upper bound on average error probability for binary codes under maximum-likelihood decoding over asymmetric channels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the asymmetric Hamming bidistance as a pair that records the number of 0-to-1 transitions and 1-to-0 transitions between two codewords separately. This two-dimensional distribution is shown to support a fresh upper bound on the average error probability of maximum-likelihood decoding. The bound is proven to be incomparable in general with the two earlier bounds obtained by Cotardo and Ravagnani. The authors compute the full distributions explicitly for several families of linear and nonlinear codes.

Core claim

The central claim is that the asymmetric Hamming bidistance and its two-dimensional distribution capture directional discrepancies between codewords in a way that permits a new upper bound on the average error probability for maximum-likelihood decoding of binary codes over asymmetric channels, and that this bound is incomparable with the two bounds previously derived from other discrepancy measures.

What carries the argument

The asymmetric Hamming bidistance, defined as the ordered pair counting 0-to-1 and 1-to-0 flips between any two codewords, together with the two-dimensional distribution of these pairs over a code.

If this is right

The new bound applies directly to any binary code whose AHB distribution can be determined, including projective codes and designs.
For codes whose performance is indistinguishable by weight distribution alone, the AHB distribution can still produce distinct error-probability bounds.
Explicit AHB distributions are now available for two-weight and three-weight projective codes via strongly regular graphs and for certain nonlinear codes from SBIBDs.
The bound remains valid even when the two transition probabilities of the asymmetric channel differ substantially.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Designers of codes for flash memory or other asymmetric media could use AHB distributions as an optimization criterion instead of minimum distance alone.
The two-dimensional distribution might extend naturally to q-ary asymmetric channels by recording counts for each directed symbol pair.
If the AHB distribution turns out to be computable from the code's association scheme, then existing algebraic machinery for association schemes could yield closed-form bounds for additional code families.

Load-bearing premise

The asymmetric Hamming bidistance distribution supplies strictly more information for distinguishing maximum-likelihood decoding performance than weight distributions or prior discrepancy measures do.

What would settle it

A concrete binary code and asymmetric channel parameters for which the new bound is strictly weaker than both existing bounds, or for which the AHB distribution fails to separate two codes that have identical weight distributions yet different observed error rates.

Figures

Figures reproduced from arXiv: 2604.07730 by Chunming Tang, Cuiling Fan, Shukai Wang, Zhengchun Zhou.

**Figure 3.** Figure 3: Values of the three bounds and true values of Pe(C) in Example 5 for p = 0.1 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 values Bound in Theorem 2 First bound in Lemma 1 Second bound in Lemma 1 True values [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

read the original abstract

The binary asymmetric channel is a model for practical communication systems where the error probabilities for symbol transitions $0\rightarrow 1$ and $1\rightarrow0$ differ substantially. In this paper, we introduce the notion of asymmetric Hamming bidistance (AHB) and its two-dimensional distribution, which separately captures directional discrepancies between codewords. This finer characterization enables a more discriminative analysis of decoding the error probabilities for maximum-likelihood decoding (MLD), particularly when conventional measures, such as weight distributions and existing discrepancy-based bounds, fail to distinguish code performance. Building on this concept, we derive a new upper bound on the average error probability for binary codes under MLD and show that, in general, it is incomparable with the two existing bounds derived by Cotardo and Ravagnani (IEEE Trans. Inf. Theory, 68 (5), 2022). To demonstrate its applicability, we compute the complete AHB distributions for several families of codes, including two-weight and three-weight projective codes (with the zero codeword removed) via strongly regular graphs and 3-class association schemes, as well as nonlinear codes constructed from symmetric balanced incomplete block designs (SBIBDs).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines the asymmetric Hamming bidistance and its 2D distribution to produce an MLD error bound that is incomparable to the Cotardo-Ravagnani bounds, with explicit calculations for projective and SBIBD codes.

read the letter

The core contribution is the asymmetric Hamming bidistance, which tracks the two directions of Hamming distance separately. Its two-dimensional distribution then feeds a new upper bound on average maximum-likelihood error probability over binary asymmetric channels. The authors show this bound is incomparable to the two earlier ones by exhibiting concrete cases where each is tighter than the others. They compute the full distributions for two- and three-weight projective codes (via strongly regular graphs and 3-class schemes) and for nonlinear codes coming from SBIBDs, which supplies the evidence for the incomparability claim. The definitions are given explicitly, the inequality derivations are carried through, and the examples are worked out in detail rather than left as existence statements. That is the part that holds up cleanly. The main limitation is that the new bound's advantage is demonstrated only on these structured families; there is no general algorithm or complexity discussion for computing the AHB distribution on an arbitrary code. For most practical codes this step may remain expensive, so the bound's utility outside the examples is still open. The paper is aimed at specialists in coding theory who already work on asymmetric channels or on distance distributions for MLD. Anyone who needs tighter or alternative bounds for those channels will find the constructions and the side-by-side comparisons useful. It is grounded enough and free of internal contradictions to merit a full referee process rather than a desk rejection.

Referee Report

2 major / 3 minor

Summary. The paper introduces the asymmetric Hamming bidistance (AHB) and its two-dimensional distribution to capture directional discrepancies between codewords over binary asymmetric channels. It derives a new upper bound on the average maximum-likelihood decoding (MLD) error probability for binary codes and proves that this bound is incomparable in general to the two bounds previously obtained by Cotardo and Ravagnani. The authors compute explicit AHB distributions for families of projective two- and three-weight codes (via strongly regular graphs and 3-class association schemes) as well as nonlinear codes arising from symmetric balanced incomplete block designs (SBIBDs), and use these to exhibit concrete cases where the new bound is tighter and cases where an existing bound is tighter.

Significance. If the derivation and incomparability hold, the AHB distribution supplies a strictly finer invariant than ordinary weight distributions or existing discrepancy measures for distinguishing MLD performance on asymmetric channels. The explicit constructions and computations for projective codes and SBIBD-derived codes provide verifiable, non-vacuous examples that support the incomparability claim and illustrate practical applicability. The use of association-scheme machinery to obtain closed-form distributions is a methodological strength that may extend to other code families.

major comments (2)

[§3.2] §3.2, the derivation of the new upper bound: the transition from the two-dimensional AHB distribution to the averaged error-probability expression relies on a union-bound step whose tightness depends on the specific channel parameters p and q; the manuscript should state explicitly whether the bound remains non-vacuous for all 0 < p,q < 1/2 or only in an open subset of that region.
[§5.1] §5.1, the incomparability statement: while the numerical examples for the two-weight and three-weight projective codes demonstrate that neither bound dominates the other, the manuscript does not provide a general analytic condition (in terms of the AHB distribution parameters) under which the new bound is strictly tighter; such a condition would strengthen the claim beyond the computed instances.

minor comments (3)

[§2.1] The definition of the asymmetric Hamming bidistance in §2.1 would benefit from an immediate small example (e.g., the [7,3] simplex code) showing how the two coordinates of the bidistance are computed.
[§2.2] Notation for the two-dimensional distribution (A_{i,j}) is introduced without a clear statement of the normalization convention; it should be stated whether the entries sum to |C| or to |C|(|C|-1).
[Bibliography] The reference to Cotardo and Ravagnani (IEEE Trans. Inf. Theory, 68(5), 2022) appears only in the abstract and introduction; the full bibliographic entry should be repeated in the bibliography section with page numbers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the recommendation of minor revision. We respond to the major comments point by point below.

read point-by-point responses

Referee: [§3.2] §3.2, the derivation of the new upper bound: the transition from the two-dimensional AHB distribution to the averaged error-probability expression relies on a union-bound step whose tightness depends on the specific channel parameters p and q; the manuscript should state explicitly whether the bound remains non-vacuous for all 0 < p,q < 1/2 or only in an open subset of that region.

Authors: We appreciate the referee's observation regarding the union-bound step in the derivation of the upper bound in §3.2. The bound is valid for all channel parameters satisfying 0 < p, q < 1/2. However, as with any union bound, the expression can exceed 1 for larger values of p and q, making it vacuous outside certain regions. The non-vacuous region is an open subset of (0,1/2)^2 that includes small p and q, with the boundary determined by the AHB distribution. We will add a clarifying statement in the revised version of §3.2 to explicitly address this. revision: yes
Referee: [§5.1] §5.1, the incomparability statement: while the numerical examples for the two-weight and three-weight projective codes demonstrate that neither bound dominates the other, the manuscript does not provide a general analytic condition (in terms of the AHB distribution parameters) under which the new bound is strictly tighter; such a condition would strengthen the claim beyond the computed instances.

Authors: The manuscript establishes that the new bound is incomparable to the bounds of Cotardo and Ravagnani by providing specific families of codes where each bound is tighter than the others in turn. These examples, computed using the AHB distributions for projective codes and SBIBD codes, suffice to prove that no bound dominates the others in general. A general analytic condition comparing the bounds for arbitrary AHB distributions is not provided because it would require case-by-case analysis of the two-dimensional distributions and does not admit a simple closed-form expression. We maintain that the explicit examples adequately support the incomparability claim. We can include an additional sentence in §5.1 explaining this if the referee considers it beneficial. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper introduces the asymmetric Hamming bidistance and its two-dimensional distribution via explicit definitions independent of the target bound. The upper bound on average MLD error probability is then derived from this distribution using standard probabilistic arguments. Incomparability to the Cotardo-Ravagnani bounds is established by direct computation of the AHB distributions for concrete families (projective two- and three-weight codes via strongly regular graphs, SBIBD nonlinear codes), without parameter fitting, self-referential definitions, or load-bearing self-citations. The central claims rest on these independent constructions and inequalities rather than reducing to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the introduction of the AHB concept and the derivation of an error-probability bound from its distribution. No explicit free parameters appear in the abstract. The main invented entity is the AHB itself.

axioms (2)

domain assumption Standard model of a binary asymmetric channel with unequal transition probabilities
Invoked as the setting for all subsequent analysis.
standard math Maximum-likelihood decoding rule for binary codes
Used without proof as the decoding criterion whose error probability is bounded.

invented entities (1)

Asymmetric Hamming bidistance (AHB) no independent evidence
purpose: Separately capture directional discrepancies between codewords
Newly defined object whose distribution enables the claimed bound.

pith-pipeline@v0.9.0 · 5507 in / 1392 out tokens · 42205 ms · 2026-05-10T18:20:31.977801+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We introduce the notion of asymmetric Hamming bidistance (AHB) and its two-dimensional distribution... derive a new upper bound on the average error probability... incomparable with the two existing bounds derived by Cotardo and Ravagnani

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[1]

E. R. Berlekamp, Algebraic Coding Theory, New Y ork: McGr aw-Hill, pp. 397-399, 1968

work page 1968
[2]

T. Beth, D. Jungnickel and H. Lenz, Design theory. Cambri dge, U.K.: Cambridge University Press, 1999

work page 1999
[3]

The geometry of two-weig ht codes

R. Calderbank and W. M. Kantor, “The geometry of two-weig ht codes”, Bull. Lond. Math. Soc. , vol. 18, pp. 97–122, 1986

work page 1986
[4]

Flash Memories,

P . Cappelletti, C. Golla, P . Olivo, and E. Zanoni, “Flash Memories,” Boston, MA, USA: Kluwer, 1999

work page 1999
[5]

Cod es for asymmetric limited-magnitude errors with applicati on to multilevel ﬂash memories,

Y . Cassuto, M. Schwartz, V . Bohossian, and J. Bruck, “Cod es for asymmetric limited-magnitude errors with applicati on to multilevel ﬂash memories,” IEEE Trans. Inf. Theory , vol. 56, no. 4, pp. 1582–1595, 2010

work page 2010
[6]

On the theory of binary asy mmetric error correcting codes,

S. D. Constantin, T. R. N. Rao, “On the theory of binary asy mmetric error correcting codes,” Inf. Control, vol. 40, no. 1, pp. 20-36, 1979

work page 1979
[7]

Parameters of codes for the binary asymmetric channel,

G. Cotardo and A. Ravagnani, “Parameters of codes for the binary asymmetric channel,” IEEE Trans. Inf. Theory, vol. 68, no. 5, pp. 2941-2950, 2022

work page 2022
[8]

Combinatorial neural codes from a mathematical coding th eory perspective,

C. Curto, V . Itskov, K. Morrison, Z. Roth, and J. L. Walker , “Combinatorial neural codes from a mathematical coding th eory perspective,” Neural Comput., vol. 25, no. 7, pp. 1891–1925, 2013

work page 1925
[9]

An algebraic approach to the association s chemes of coding theory,

P . Delsarte, “An algebraic approach to the association s chemes of coding theory,” Philips Res. Repts. , 1973

work page 1973
[10]

Weights of linear codes and strongly regu lar normed spaces,

P . Delsarte, “Weights of linear codes and strongly regu lar normed spaces,” Discrete Mathematics, vol. 3, pp. 47-64, 1972

work page 1972
[11]

Error p robabilities for bounded distance decoding,

A. Faldum, J. Lafuente, G. Ochoa and W. Willems, “Error p robabilities for bounded distance decoding,” Des., Codes Crypt., vol. 40, pp. 237–252, 2006

work page 2006
[12]

Coding for the binary asymmet ric channel,

R. Gabrys and L. Dolecek, “Coding for the binary asymmet ric channel,” 2012 International Conference on Computing, Networking and Communications (ICNC), Maui, HI, USA, pp. 461-465, 2012

work page 2012
[13]

Error correcting codes for the asymmetric ch annel,

T. Kløve, “Error correcting codes for the asymmetric ch annel,” Dept. Inform., Univ. Bergen, Bergen, Norway, Tech. Rep., 1981

work page 1981
[14]

Performance improvement of all op tical WDM systems on binary asymmetric channel,

H.S. Mruthyunjaya, “Performance improvement of all op tical WDM systems on binary asymmetric channel,” Int. J. Microw. Opt. Technol. , vol. 2, no. 3, pp. 230-235, 2007

work page 2007
[15]

An anal ysis of the timed Z-channel,

I. S. Moskowitz, S. J. Greenwald, and M. H. Kang, “An anal ysis of the timed Z-channel,” IEEE Trans. Inf. Theory, vol. 44, no. 7, pp. 3162–3168, 1998

work page 1998
[16]

Error probability a nalysis of binary asymmetric channels,

S. M. Moser, P .-N. Chen, H.-Y . Lin, “Error probability a nalysis of binary asymmetric channels,” National Chiao Tun g University, Tech. Rep., 2010

work page 2010
[17]

Bounds on the decoding error probability of binary linear codes via their spectra,

G. Poltyrev, “Bounds on the decoding error probability of binary linear codes via their spectra,” IEEE Trans. Inf. Theory, vol. 40, no. 4, pp. 1284-1292, 1994

work page 1994
[18]

On matched metric and channel problem,

A. Poplawski, “On matched metric and channel problem,” 2016, arXiv:1606.02763

work page arXiv 2016
[19]

On equivalence of binary asymmetric channels regarding the maximum likelihood decoding,

C. Qureshi, S. I. R. Costa, C. B. Rodrigues and M. Firer. “ On equivalence of binary asymmetric channels regarding the maximum likelihood decoding,” IEEE Trans. Inf. Theory , pp. 3528-3537, 2018

work page 2018
[20]

Matched metrics to the binary asymmetri c channels,

C. M. Qureshi, “Matched metrics to the binary asymmetri c channels,” IEEE Trans. Inf. Theory, vol. 65, no. 2, pp. 1106–1112, 2019

work page 2019
[21]

On binary channels and their cascades,

R. Silverman, “On binary channels and their cascades,” IRE Trans. Inf. Theory, , vol. 1, no. 3, pp. 19-27, 1955

work page 1955
[22]

Constructions of combinatori al neural codes with asymmetric discrepancy,

Z. Sun, X. Song and Y . Li, “Constructions of combinatori al neural codes with asymmetric discrepancy,” IEEE Trans. Inf. Theory, DOI 10.1109/TIT.2026.3669230, 2026

work page doi:10.1109/tit.2026.3669230 2026
[23]

A construction of binary constant- weight codes from algebraic curves over ﬁnite ﬁelds,

C. Xing and J. Ling, “A construction of binary constant- weight codes from algebraic curves over ﬁnite ﬁelds,” IEEE Trans. Inf. Theory, vol. 51, no. 10 pp. 3674-3678, 2005

work page 2005
[24]

Optimal combinatorial ne ural codes with matched metric δr: characterization and constructions,

A. Zhang, X. Jing and K. Feng, “Optimal combinatorial ne ural codes with matched metric δr: characterization and constructions,” IEEE Trans. Inf. Theory, vol. 69, pp. 5440–5448, 2023

work page 2023
[25]

Optimal combinatorial neu ral codes via symmetric designs,

X. Zheng, S. Wang and C. Fan, “Optimal combinatorial neu ral codes via symmetric designs,” Des. Codes Cryptogr ., vol. 93, pp. 725–736, 2025

work page 2025