CS Paper Radar

Shaping and Finite-Blocklength Analysis of Quaternionic Alamouti-Type Codes

Juliana G. F. Souza, Yu-Chih Huang

cs.IT ·submitted 2026-10-30 12:59 UTC · v1
theory

Abstract

We study finite $2\times2$ Alamouti-type space--time codes associated with classical maximal orders in definite quaternion algebras over $\mathbb Q$. For the family indexed by primes $q\equiv3\pmod4$, we prove that the Eisenstein case $q=3$ uniquely minimises the finite quotient-alphabet energy at fixed minimum lattice distance and alphabet size. This ordering holds for every integer $p\geq2$, including when the representatives and their common translation are jointly optimised, with an explicit positive gap for every $q>3$. For uniform finite inputs, we derive a controlled high-SNR expansion of the information variance and determine its limiting ratio to the mutual information deficit. The mutual information expansion specialises arbitrary input fading results and gives an explicit remainder. Standard random-coding and second-order achievability tools relate these quantities to reliability over independently faded Alamouti blocks. All alphabets preserve symbol-wise maximum-likelihood detection at the Alamouti level. Numerical energy, mutual information, and error-rate comparisons support the analysis. Centred comparisons with classical Alamouti, Golden, and Silver codes illustrate the trade-off between reliability, symbol rate, and decoding effort.

Closest papers

Nearest neighbours by meaning across the whole index.

A polynomial-time decoding algorithm up to half the square-root bound for quadratic residue and generalized quadratic residue codes

cs.IT ·2026-11-16 ·Phlippe Gaborit, Philippe Lebacque
theory similarity 0.59
Abstract

Binary quadratic residue (QR) codes, introduced by Prange in 1958, are cyclic codes of prime length $p\equiv\pm1\pmod 8$ and dimension $(p+1)/2$ whose minimum distance satisfies the square-root bound $d\ge\sqrt p$. They include the Hamming code $[7,4,3]$ and the Golay code $[23,12,7]$, and were generalized by van Lint and MacWilliams to generalized quadratic residue (GQR) codes of prime-power length $q$, for which the bound $d\ge\sqrt q$ still holds and is attained when $q$ is a square. In coding theory, one usually first finds a lower bound on the minimum distance of a family of codes, and then a polynomial-time algorithm decoding up to half of this bound, as for BCH, Reed--Muller or Gabidulin codes. Until now, GQR codes had resisted this approach: no such algorithm was known, apart from individual short lengths. We give a deterministic algorithm which, for every odd prime power $q\equiv\pm1\pmod 8$, corrects every error pattern of weight at most $\lfloor(\sqrt q-1)/2\rfloor$ in the binary GQR code of length $q$, in $O(q^{9/2})$ operations in $\F_q$. We start from a description of QR codes due to Helleseth, which we extend to GQR codes, and in which the syndrome gives the values of the quadratic character of the error-locator polynomial. We then recover this polynomial by adapting to GQR codes the tools that Kopparty developed for recovering polynomials from noisy character values, with the decoding of dual BCH codes as an application. Since the square-root bound is attained when $q$ is a square, this radius is the largest that can be guaranteed uniformly on the class of GQR codes.

0.15

Linear Codes over $\mathbb{F}_{q}+u\mathbb{F}_{q}$ associated with Simplicial Complexes, Their Gray Images, and Subfield Codes

cs.IT ·2026-09-10 ·Ankit Yadav, Akanksha Tiwari, Ritumoni Sarma
similarity 0.57
Abstract

In recent years, simplicial complexes have gained considerable attention as a useful tool for constructing distance-optimal codes over finite fields. In this article, we construct four infinite families of linear codes over the ring $\mathcal{R}=\mathbb{F}_{q}+u\mathbb{F}_{q}$ with $u^2=0$ using simplicial complexes with one or two maximal elements, and completely determine their Lee weight distributions via exponential-sum techniques. By employing a Gray map on $\mathcal{R}$, we obtain infinite families of distance-optimal codes over $\mathbb{F}_{q}$, including a near-Griesmer family, and establish sufficient conditions for their minimality. Furthermore, we investigate the corresponding subfield codes and derive sufficient conditions for their distance-optimality and minimality, yielding infinite families of Griesmer and near-Griesmer codes.

0.18

Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes

cs.IT ·2026-11-12 ·Yota Maeda, Ruho Kondo
theory similarity 0.57
Abstract · 25 pages

Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small $\varepsilon>0$, we construct a family of random binary codes $C_m$ whose rates approach $\varepsilon^2$ and satisfy \[ \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, \] for all sufficiently large $m$, where $N_m$ is the block length and $c>0$ is independent of $\varepsilon$ and $m$. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed $\varepsilon$, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.

0.18

Quantum codes in the Lee metric

cs.IT quant-phmath.COmath.MG ·2026-10-04 ·Jinkang Guo, Yiqiu Han, Aranya Chakraborty, Shubham P. Jain, Tianhao Liu +2 more
theory similarity 0.56
Abstract

We introduce a quantum coding framework for discrete small-shift noise, in which errors on qudits are modeled as low-weight $X$- and $Z$-type Pauli shifts, analogous to small phase-space displacements in continuous-variable systems. This structure is approximately respected by nuclear-spin noise and captured by the Lee metric, motivating a quantum extension of classical Lee-metric coding theory. We develop such a formalism for stabilizer codes over $\mathbb{Z}_q$ for arbitrary $q$, using joint and separate Lee metrics for the $X$- and $Z$-components of errors. For qubits, the joint metric counts $Y$ errors twice and can yield codes that detect and correct $X$ and $Z$ errors with fewer physical qubits than codes designed for the conventional Hamming metric. We discuss Lee-weight spreading under Clifford gates and qubitize codes over $\mathbb{Z}_4$ via the Gray map, finding codes with two-fold transversal non-qubit-Clifford gates. For quantum CSS Lee-LDPC codes on $n$ qudits, we prove that the Lee distance cannot exceed $O(n)$, uniformly in $q$, demonstrating an unexpected obstruction to using the large internal Hilbert space of a large-$q$ qudit to make high-Lee-distance codes. Under local Metropolis dynamics, certain classical $q$-ary ``helical repetition codes'' have exponentially long memory times at fixed temperature for sufficiently large $q$ (that grows with system length), which can be understood as spontaneous symmetry breaking at finite temperature, even in local one-dimensional models. Hypergraph products of these helical repetition codes provide local two-dimensional quantum codes that inherit self-correction for $Z$ errors, but self-correction for $X$ errors remains an open question.

0.49

Quantum MDS codes from complements of unions of finite-field subsets

cs.IT math-phmath.QA ·2026-09-09 ·Naihong Hu, Hong Ji
similarity 0.56
Abstract · 37 pages

Let $q$ be an odd prime power. We use complements of unions of subsets of $\mathbb F_{q^2}$ as locator sets and establish a sufficient condition under which a generalized Reed--Solomon (GRS) code is Hermitian self-orthogonal. Using cosets of multiplicative subgroups and sets with prescribed trace or norm values, we construct five families of Hermitian self-orthogonal GRS codes over $\mathbb F_{q^2}$. The Hermitian construction then yields five corresponding families of $q$-ary quantum maximum-distance-separable (MDS) codes. Under suitable parameter conditions, these quantum codes have minimum distances greater than $q/2+1$. By comparing codes of the same length, we give conditions under which our codes have strictly larger minimum distances than those obtainable from several previously known constructions based on trace maps, linear transformations, and cosets of multiplicative subgroups, either directly or via the propagation rule. We further show that such improvements occur for infinitely many values of $q$.

0.22

A $Θ(n)$-Multiplicative Improvement of the Gilbert-Varshamov Bound for Linear and Quantum Codes

cs.IT ·2026-11-12 ·Chen Yuan, Ruiqi Zhu
benchmark similarity 0.56
Abstract · 20 pages

The Gilbert-Varshamov (GV) bound is a fundamental benchmark for the existence of error-correcting codes. For non-linear $q$-ary codes of code length $n$, its finite length form is known to admit a multiplicative improvement of order $Θ(n)$. In contrast, for $q$-ary linear codes of arbitrary rates, the best previously known general improvement was only of order $Θ(\sqrt n)$. This leaves open whether the algebraic constraint of linearity inherently prevents a linear-order refinement. We show that it does not. For every fixed prime power $q$ and relative distance $0<δ<1-1/q$, we obtain a $Θ(n)$-multiplicative improvement of the GV bound for $q$-ary linear codes of arbitrary rate, matching the corresponding result for nonlinear codes. Our proof is based on a simple change of viewpoint. Rather than requiring the initial random linear construction to contain no low-weight vectors, we allow $O(n)$ low-weight points, show that they are independent in the underlying projective space, and then eliminate all of them simultaneously at the cost of a single dimension. The key probabilistic ingredient is an exponential bound on nontrivial linear dependencies among low-weight vectors. We further show that this approach can be extended to quantum codes despite the symplectic self-orthogonality constraint. We obtain a $Θ(n)$-multiplicative improvement of the quantum GV bound for every fixed $0<δ<1-1/q^2$ satisfying $H_{q^2}(δ)<1/2$. Thus, the same $Θ(n)$ finite length improvement is applicable to both general linear structure and symplectic self-orthogonality.

0.28

Quantum bivariate bicycle codes with weight-8 checks surpassing the BB benchmark

cs.IT quant-ph ·2026-09-06 ·Liangdong Lu, Ruipan Yang, Guanmin Guo
benchmarktheory similarity 0.55
Abstract

Bivariate bicycle (BB) codes of Bravyi \emph{et al.}~\cite{Bravyi2024} are quantum low-density parity-check codes with weight-$6$ checks, exemplified by $[[144,12,12]]$ with $kd^2/n=12$. We develop the algebraic structure theory of BB-type codes with weight-$8$ checks (weight-$4$ generator polynomials) and use it, together with an exactly validated search pipeline, to construct and certify new codes. We prove an exact dimension formula $k=2\dim R/(A,B)$ (forcing even $k$), a $4\ell m$-element symmetry group on generator pairs, an $X/Z$ distance equality $d_X=d_Z$, and a family of subgroup-coset kernel vectors giving rigorous distance upper bounds and a design rule for high-distance constructions; all distances are computed exhaustively by a cross-validated bit-mask verifier. At $n=144$ the pipeline returns a census of $53$ codes whose strongest members surpass the BB benchmark: $[[144,6,d\ge 15]]$ exceeds the benchmark distance $12$ (certified $d\ge 15$), $[[144,10,12]]$ reaches it with weight-$8$ checks, and $[[144,16,10]]$ encodes a third more logical qubits at $kd^2/n=11.11$ ($7.4\%$ below benchmark) while decoding no worse. At $n=72$, $[[72,14,8]]$ attains $kd^2/n=12.44$---more than twice the same-length BB code---and decodes better; a circuit-level memory experiment places our weight-$8$ codes at $\approx 0.1\%$ pseudo-threshold versus $\approx 0.4\%$ for the BB reference under an identical model, quantifying the threshold cost of the heavier checks. All structural statements are verified numerically on the whole census.

0.16

Quantum Bicycle LDPC Codes with High $kd^2/n$ from Divisor-Driven Search

cs.IT quant-ph ·2026-08-10 ·Liangdong Lu, Guanmin Guo, Yang Liu, Ruipan Yang
similarity 0.55
Abstract · v2: Added references on decoding comparison

Bicycle (two-block circulant) quantum low-density parity-check (LDPC) codes include some of the best known small quantum codes, yet their design has relied on group-algebra formulations in which the dimension and distance are accessible only through matrix computation. We show that in the cyclic case the construction collapses into the polynomial ring $\F_2[x]/(x^{l}-1)$: self-orthogonality is automatic, the quantum dimension is read off from a polynomial gcd, and the minimum distance is certified exactly through the Calderbank correspondence to additive codes over $\F_4$, turning code search into an algebraically pre-filtered enumeration that reaches parameter regimes poorly covered by existing tables. A computer search based on this framework recovers the short codes $[[42,12,4]]_2$ and $[[62,12,4]]_2$ and produces a family of codes with competitive figure of merit $kd^2/n$, including $[[66,20,7]]_2$ with $kd^2/n=14.85$, above the bivariate bicycle code $[[144,12,12]]_2$ ($kd^2/n=12$) at less than half the block length, together with $[[46,2,8]]_2$, $[[66,2,9]]_2$, $[[66,4,8]]_2$, $[[66,6,8]]_2$ and, at $n=90$, $[[90,16,6]]_2$, $[[90,18,6]]_2$, $[[90,20,6]]_2$. An exhaustive census at $n=48$ delineates the boundary of this picture: we exhibit a $[[48,10,6]]_2$ code from a minimal $48$-element group (the Aydin--Tamo--Barg realization uses $72$ elements), and prove that distance $5$ forces a stabilizer-rank loss, which excludes $[[48,10,5]]_2$ from the weight-$8$ symmetric coset family. The framework thus opens a systematic route to bicycle-type quantum LDPC codes beyond the reach of group-theoretic searches, and identifies exactly where genuinely coset-theoretic phenomena begin.

0.32