Tunneling-Augmented Simulated Annealing for Short-Block LDPC Code Construction
Atharv Kanchi · 2026
Read Tunneling-Augmented Simulated Annealing for Short-Block LDPC Code Construction by Atharv Kanchi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-07365.txt.
Introduction
Kanchi builds short-block LDPC codes by tuning parity-check matrices with tunneling-augmented simulated annealing plus local polish. The goal penalizes short cycles, trapping-set shapes, and degree breaks, for low-latency links where short-length effects rule. At block lengths 64 to 128, the codes beat random LDPC codes by a tenth to just over one decibel. They average near half a decibel and sit within six tenths of a decibel of progressive edge growth. Yet wiping out 1906 trapping patterns adds only eight hundredths of a decibel.
Catalog record
| CREATOR | Atharv Kanchi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49963 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.07365
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tunneling-Augmented Simulated Annealing for Short-Block LDPC Code Construction Atharv Kanchi Abstract Designing high-performance error-correcting codes at short blocklengths is critical for low-latency communication systems, where decoding is governed by finite-length and graph-structural effects rather than asymptotic properties. This paper presents a global discrete optimization framework for constructing short-block linear codes by directly optimizing parity-check matrices. Code design is formulated as a constrained binary optimization problem with penalties for short cycles, trapping-set-correlated substructures, and degree violations. We employ a hybrid strategy combining tunneling-augmented simulated annealing (TASA) with classical local refinement to explore the resulting non-convex space. Experiments at blocklengths 64-128 over the AWGN channel show 0.1-1.3 dB SNR gains over random LDPC codes (average 0.45 dB) and performance within 0.6 dB of Progressive Edge Growth. In constrained regimes, the method enables design tradeoffs unavailable to greedy approaches. However, structural improvements do not always yield decoding gains: eliminating 1906 trapping set patterns yields only +0.08 dB improvement. These results position annealing-based global optimization as a complementary tool for application-specific code design under multi-objective constraints. I Introduction Error-correcting codes are a foundational component of modern digital communication systems, enabling reliable transmission over noisy channels. While many classical and capacity-approaching constructions perform well at large blocklengths, their performance often degrades significantly in the short-blocklength regime. This limitation is increasingly relevant as emerging applications such as ultra-reliable low-latency communications, satellite IoT, and industrial control systems impose strict constraints on latency, decoding complexity, and blocklength. At short blocklengths, asymptotic guarantees no longer accurately predict performance. Instead, decoding behavior is dominated by finite-length effects and the local structure of the code’s Tanner graph. In particular, short cycles, stopping sets, and trapping sets can severely degrade the performance of iterative decoders, even when minimum distance properties are acceptable. As a result, code design in this regime requires explicit control over graph-theoretic structure rather than reliance on asymptotic optimality. Low-Density Parity-Check (LDPC) codes are attractive candidates for short-block applications due to their flexible structure and efficient iterative decoding. However, constructing high-performance short LDPC codes remains challenging. Random constructions often yield poor structural properties, while greedy heuristics such as Progressive Edge Growth (PEG) optimize for specific metrics, such as girth, but struggle to simultaneously balance multiple competing design objectives. Moreover, these methods are difficult to adapt to additional constraints such as forbidden subgraph patterns, prescribed degree distributions, or block-structured parity-check matrices. Because short-block code design involves multiple competing structural objectives, including girth, cycle multiplicity, and degree constraints, greedy constructions optimized for a single metric may produce suboptimal overall decoding performance. This motivates the use of global optimization methods that can balance several structural penalties simultaneously. From a computational perspective, LDPC code construction can be viewed as a discrete combinatorial optimization problem: given a target blocklength and rate, one seeks a parity-check matrix that optimizes decoding-relevant structural metrics under practical constraints. This problem is inherently high-dimensional, non-convex, and multi-objective, with a rugged optimization landscape dominated by local minima. These characteristics limit the effectiveness of purely local or greedy construction techniques. In this work, we investigate a global optimization framework for short-block LDPC code construction based on tunneling-augmented simulated annealing (TASA). The method extends classical simulated annealing [ 12 ] with a decaying tunneling-inspired perturbation term, motivated by the quantum annealing literature [ 10 , 17 ] , to better escape local minima in the rugged LDPC design landscape. The algorithm is implemented entirely on classical hardware. Combined with classical local refinement, TASA provides an efficient mechanism for exploring the high-dimensional discrete design space. The primary contributions of this paper are as follows: 1. We formulate short-block LDPC code construction as a constrained discrete optimization problem over parity-check matrices, incorporating penalties for short cycles, stopping sets, and degree violations. 2. We introduce a hybrid optimization framework that combines global exploration via tunneling-augmented simulated annealing with classical local refinement to escape poor local minima. 3. We empirically evaluate the proposed method at blocklengths between 64 and 128 bits over the AWGN channel, demonstrating 0.1–1.3 dB SNR gains over random LDPC construction at BLER =10^{-2} and competitive performance (within 0.6 dB) relative to mature Progressive Edge Growth heuristics. 4. We analyze performance under several constrained design regimes, including forbidden subgraph constraints, block-structured codes, and irregular degree profiles, demonstrating when global optimization enables design tradeoffs unavailable to greedy methods and when structural improvements do not translate to decoding gains. The remainder of the paper is organized as follows. Section II reviews related work. Section III formulates the code construction problem. Section IV describes the proposed optimization method. Section V presents the experimental setup. Section VI reports results, and Section VII discusses implications and limitations. II Related Work II-A Classical LDPC Code Construction Low-Density Parity-Check (LDPC) codes were introduced by Gallager [ 7 ] and later rediscovered by MacKay [ 16 ] , demonstrating near-capacity performance under iterative decoding. At asymptotic blocklengths, LDPC codes approach Shannon capacity [ 22 ] , but their performance at short blocklengths depends critically on Tanner graph structure. For short-block LDPC construction, the Progressive Edge Growth (PEG) algorithm [ 9 ] has become a widely adopted greedy heuristic. PEG constructs codes by sequentially adding edges to maximize local girth, producing graphs with favorable cycle distributions. Extensions such as Decoder-Optimized PEG [ 13 ] and Improved PEG [ 8 ] refine this approach by incorporating decoding-specific metrics. However, PEG’s greedy nature limits its ability to explore global structural tradeoffs or incorporate multiple simultaneous constraints [ 20 ] . Recent work has explored systematic construction methods for short LDPC codes [ 18 ] , including combinatorial designs and structured matrix approaches, though these methods typically target specific algebraic properties rather than direct performance optimization. II-B Graph-Theoretic Performance Metrics The performance of iteratively decoded LDPC codes is strongly influenced by graph-theoretic structures. Di et al. [ 3 ] analyzed stopping sets on the binary erasure channel, demonstrating how small stopping sets limit finite-length performance. Dolecek et al. [ 4 ] characterized absorbing sets and their role in error floor phenomena. Richardson [ 21 ] identified trapping sets as a primary cause of decoding failures at moderate-to-high SNR, motivating explicit avoidance of harmful substructures during code design. Wang et al. [ 24 ] proposed methods for constructing codes with prescribed girth, though computational complexity limits applicability to very short blocks. These results establish that short-block LDPC performance requires optimization of multiple competing graph metrics beyond minimum distance alone. II-C Optimization-Based Code Design Several prior works have applied optimization techniques to LDPC construction. Venkiah et al. [ 23 ] formulated short-block code design as an integer programming problem, though scalability remains limited. Campello et al. [ 1 ] employed differential evolution for irregular LDPC design, demonstrating that metaheuristic search can discover codes competitive with algebraic constructions. Yang et al. [ 25 ] proposed a systematic methodology combining algebraic structure with iterative improvement. However, these approaches have not explored annealing frameworks augmented with tunneling-inspired perturbations. TASA provides a principled alternative by combining the thermal exploration of simulated annealing [ 12 ] with a decaying tunneling term motivated by quantum annealing [ 10 ] , offering more structured escape from local minima than purely random restarts. II-D Physics-Inspired Optimization Quantum annealing, introduced by Kadowaki and Nishimori [ 10