CS Paper Radar

Anchored Iterative Decoding of Reed-Solomon Product Codes for High-Rate Magnetic Tape Storage

Alexander Chvanov, Nikolay Malkovsky

cs.IT ·submitted 2026-11-06 12:04 UTC · v1

Abstract

We present a decoding algorithm for a Reed--Solomon product code targeted at the demanding reliability requirements of modern magnetic tape storage. For a code $RS(256, 224)\times RS(175, 173)$ in a BSC we achieve post-decoding bit error rate (BER) of $10^{-20}$ at $\approx 5.3\times 10^{-3}$ raw BER while maintaining the common requirement to detect and correct 4 out of 32 dead tracks. We resolve two common problems of miscorrections and stall patterns that arise under such a high raw BER via simplified versions of anchor decoding and binary image analysis. The highest efficiency is achieved by performing an unlimited iterative decoder, which performs decoding iterations until no changes are made. We give an empirical analysis of the average number of iterations: below the raw BER of $5\times 10^{-3}$, four half-iterations are performed on average while improving substantially over a decoder that always performs 4 half-iterations. We provide a CPU implementation achieving 100-200 megabytes/s single-core throughput on a regular laptop and a design of a potential hybrid FPGA-CPU implementation of our decoder.

Closest papers

Nearest neighbours by meaning across the whole index.

An SCL-Aware Design of PAC Codes

cs.IT ·2026-10-29 ·Tyler Kann, Shrinivas Kudekar, Matthieu R. Bloch
similarity 0.59
Abstract

We develop design methodologies for the rate profile of polarization-adjusted convolutional (PAC) codes tailored to successive cancellation list (SCL) decoding. The crux of our approach is two-fold: first is the creation of a modified density evolution Gaussian approximation (DEGA), called conditional DEGA (CDEGA), to analyze the decoding process in the presence of errors; second is the creation of a dangerous-path occupancy metric to find the conditional occupancy of bit-errors in a finite list. Our approach not only illuminates the role of rate-one precoding, but also provides insight into why certain information sets are particularly well suited to PAC codes. We demonstrate the usefulness of CDEGA and dangerous-path metrics with algorithms that create new information sets, as well as precoders that are extremely sparse yet competitive. In particular, we design codes of length $N \leq 512$ with various rates and list sizes, all of which offer at least half a dB gain over traditional PAC codes at an FER of $10^{-3}$ and improve upon state-of-the-art results.

0.30

FMT: Lossless Image Compression in a Fixed Number of Parallel Steps

cs.CV ·2026-11-17 ·Ammar Ali
position similarity 0.58
Abstract

Learned lossless codecs make smaller files than common classical codecs, yet the images we archive and train on still use classical codecs. A main reason is time: a learned codec takes seconds to decode a photo that a classical codec opens in milliseconds, and their faster variants give up most of their gain in size. We argue that much of this time is spent waiting, not computing: the network waits for the values it conditions on, and the arithmetic decoder reads them one at a time. We introduce FMT (Fixed-step Multiscale Tree), a lossless image format whose decoding order and entropy coder are designed together so that neither wait grows with the image. FMT stores an image as a coarse-to-fine tree whose steps hold independent values: a GPU predicts each step at once and decodes it in parallel rANS lanes that carry their states from step to step, so an image of any size decodes in a fixed number of sequential steps. On this tree we build a family of bit-exact codecs, from a rule with no network to large networks, and no codec we ran on the same GPU beats any of them on both size and speed. Without a network, FMT beats NVIDIA's HTJ2K on size and speed; with a large one, it decodes Kodak photos 9 to 61X faster than learned codecs we ran on the same A100, at the same size or smaller.

0.40

Zero-shot diffusion image compression with sectioned codebooks and one channel code

eess.IV cs.ITeess.SP ·2026-11-14 ·Dinanath Padhya
similarity 0.58
Abstract · 14 pages, 6 figures, 7 tables

Zero-shot diffusion codecs such as Turbo-DDCM compress images without any training. In each coded step, the encoder selects noise vectors from one codebook and transmits a single index for the selected set. We propose sectioned codebooks. A coded step is divided into sections, and each section has its own large codebook and transmits its best vector as a short field of bits. A model based on order statistics quantifies how well the bits of a step are used and predicts the gain of sectioned codebooks from measurements of Turbo-DDCM alone. Fast Walsh-Hadamard transforms make sections of $2^{20}$ vectors practical. At equal bits, sectioned codebooks improve the PSNR of Turbo-DDCM by 0.18 to 0.51 dB on three datasets, improve LPIPS and DISTS, and save 16 to 21% of the bits at equal PSNR. Codecs that are robust to channel errors by design are usually compared only with unprotected codecs. We compare them, at equal total bits, with a codec protected by one channel code. With one BCH code, the sectioned codec outperforms all reported results of Robust Turbo-DDCM and BitFlat on two datasets, by up to 7.74 dB at the highest bit error rate. At the lowest bit error rate its margin over BitFlat is only 0.08 to 0.16 dB. When the code fails, the receiver can still decode the fields as received. Additional experiments cover burst errors and packet loss, and all observed gains of robust codecs stay within a limit derived from the channel capacity.

0.17

Computed Permutation Trellis Coding: Near-Optimal Quantization from Two Multiplications and a 64-Byte Table

cs.IT cs.AIcs.ARcs.LG ·2026-11-17 ·Muhammed Fatih Balın
similarity 0.58
Abstract · 38 pages, 6 figures, 27 tables

We propose Computed Permutation Trellis Coding (CPTC), a low-bit quantization format for tensors written once and read many times. Formats that round each value on its own, such as INT4 and FP4, waste a large part of their bits against the information-theoretic ideal. Trellis codes recover this loss by encoding values jointly, but prior decoders either need a large lookup table for their best quality or compute values with a hash that restricts what they can decode. CPTC's decoder multiplies its state by two coefficients and adds the top bits of the products to index a 64-byte table. Because that sum is not uniformly distributed, the rarely used ends of a small table can hold values far out in the tails. One decoder serves every bit width from 1 to 6, reproduces the standard integer and floating-point formats exactly, and comes within 0.07 bits of the ideal at 4 bits. It matches a random-permutation trellis code whose table is thousands of times larger, and exceeds every QTIP codebook. In LLM weight quantization without fine-tuning, CPTC has the lowest KL divergence to the unquantized model at every tested bit width on Llama 3.1 8B and 70B Instruct against QTIP's codebooks (by up to 27%). The decoder has been built into the AWS Trainium 4 AI accelerator, where it runs at the throughput of the native FP4 and FP8 formats for a negligible fraction of the systolic array's area. Fused encoding kernels quantize an 8B model's linear layers in under two minutes on one GPU and, in cycle-level simulation, on one Trainium 4 chip.

0.40

PMR-Aided Shifted-Pruning SCL-Flip Decoding for CRC-Aided Polar Codes

cs.IT ·2026-10-19 ·Niloufar Hosseinzadeh, Mohammad Morsali, Mohsen Moradi, Hessam Mahdavifar
similarity 0.57
Abstract · 6 pages, 4 figures. Submitted to IEEE ICC 2027

We propose a posterior-mass rescue (PMR)-aided shifted-pruning SCL-flip decoder for CRC-aided polar codes. After CRC-aided SCL (CA-SCL) and differential-metric shifted-pruning recovery fail to find a CRC-valid candidate, PMR locally continues discarded prefixes stored during the initial CA-SCL pass, ranked by estimated posterior mass, without increasing the shifted-pruning retry budget. Simulation results for a (128, 64) code with the Reed-Muller (RM) rate profile and a (256, 128) code with the polarization-weight (PW) rate profile, both using an 11-bit CRC, show lower observed FER than SCLF-Diff (T = 15) and the considered literature baselines under the evaluated recovery budgets, with observed FER close to that of SCLF-Diff (T = 20). At the reported moderate and high SNRs, the average reconstruction-aware path-step count is within a few percent of that of SCLF-Diff (T = 20), while at 2.0 dB it is 9.4% and 4.3% higher for the two codes, respectively. The proposed decoder also has a larger worst-case path-step bound.

0.34

Task-Oriented Boolean Function Computation: Practical Code Constructions

cs.IT ·2026-10-01 ·Yangshuo He, Guanding Yu, Jingge Zhu
similarity 0.56
Abstract

Task-oriented communication conveys information that is necessary for downstream tasks. For binary decision tasks, this paradigm is information-theoretically formalized by Boolean function computation (BFC) via channels, where the receiver aims to determine the value of a function unknown to the transmitter. In this paper, we devise a practical code construction for the BFC problem based on a Reed-Solomon code. For noiseless binary channels, we derive finite-blocklength worst-case error bounds. By defining a rate function that captures how supported message length scales with channel uses, we characterize the rate-reliability tradeoff for different Boolean function families. With respect to this rate function, the proposed construction achieves an asymptotic computation rate of $1/2$. We further extend this construction to noisy channels by packing multiple BFC tasks into a single block and concatenating them with a conventional channel code. The corresponding finite-blocklength guarantees are expressed in terms of effective channel uses per function evaluation. With a channel code rate $R_c$, this construction achieves an asymptotic computation rate of $R_c/2$, yielding $C/2$ when capacity-achieving channel codes are employed. Numerical results illustrate the derived bounds and demonstrate substantial performance gains over conventional transmission. As examples, the proposed scheme achieves SNR coding gains of approximately $3.4$ and $6.4$ dB at an average task error probability of $10^{-5}$ for the exact-weight and rank-test tasks, respectively.

0.07

Insdel Decoding Algorithms for Maximum Distance Separable Codes

cs.IT ·2026-10-25 ·Bencheng Fan, Margreta Kuijper, Jingge Zhu
similarity 0.55
Abstract

In this paper, we focus on decoding MDS linear block codes for insdel errors. Building on our recent work for two-dimensional Reed-Solomon codes, we present a decoding algorithm for bounded distance decoding for the general insertion-and-deletion scenario that can be used for any MDS code of rate at most half. Our algorithm employs a sliding window and has a time complexity smaller than brute-force decoding. In particular, for optimal Reed-Solomon codes, it corrects insdel errors up to the half-Singleton bound, which exceeds the scope of existing methods. Additionally, for the special cases of insertion-only and deletion-only insdel error patterns, we present two different algorithms with a time complexity smaller than our general algorithm.

0.19

The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats

cs.DC cs.DS ·2026-09-15 ·Yakiv Shavidze
similarity 0.55
Abstract · 7 pages, 5 figures, 6 tables. Sixth paper in the ACEAPEX series (see arXiv:2606.04268, 2606.18900, 2606.24531, 2607.18541, 2608.10188). Code…

Random access into compressed data is normally bought with density. We measure the exchange rate. Across four formats and nine axes on a common corpus, the cost of cutting a 254 MB archive into independently addressable 16 KiB units is 1.632% of the archive for an absolute-offset format against 6.57% for seekable zstd, and the gap widens as the unit shrinks: at 4 KiB, 5.33% against 10.06%. Because the cost is small, several properties follow that are usually unavailable: splitting an archive is free and occasionally profitable (-0.28% on tiled input), append needs no format change, seek latency does not depend on position, and one archive is read by both a CPU and a GPU decoder. We give three structural results with proofs and bit-perfect verification - that the repeat-distance chain of an LZ77 parse forms a substitution monoid and is therefore prefix-scannable without touching the bitstream, that self-overlapping matches are periodic rather than chained, and that dependency depth admits an encoder-enforced bound - and we report each measured limit together with the mechanism that sets it. Seventeen rejected directions are listed with their numbers, including one that improved density by 26% and was declined. Every claim carries a level: reproducible by command, measured with a stated reason, or estimated. The measurement tool is released separately (DOI 10.5281/zenodo.22713364) with 435 provenanced records.

0.50