Codes correct successive swaps with blockwise encoding and decoding

Concatenation Locality under Successive Adjacent Transpositions

Information Theory

Summary

This paper looks at ways to fix errors in messages where some parts have been swapped right next to each other, called adjacent transpositions. The authors show how to build long codes by joining together multiple smaller blocks that can each be independently encoded and decoded. Their methods let you check for errors efficiently by testing only a fixed number of blocks, no matter how long the message is. They provide detailed constructions for binary codes that use close to the least extra bits possible and work quickly. The work also proves some limits on how much of a message needs to be seen to recover earlier parts reliably.

What this means in practice

  • For data storage engineers: Implement blockwise encoding and decoding that efficiently corrects clusters of swapped bits in large data with predictable redundancy.
  • For communication system developers: Build error-correcting protocols that handle bursts of adjacent swaps in messages using reusable encoders and decoders per block size.

A theory result. No direct application yet.

Authors

Adelin Ataba, Aryeh Lev Zabokritskiy

Abstract

We study codes correcting up to $t\geq1$ successive adjacent transpositions, using block concatenation to support blockwise encoding and decoding. A fixed set $P$ of words of length $b$ over a $q$-symbol alphabet generates, for every $m$, the length-$mb$ code of all concatenations of $m$ words from $P$. For our explicit constructions, the prepared encoder and decoder depend only on the block parameters and are reused at every concatenation length. We first prove that correction at every concatenation length is certified by a single finite test at $2t+1$ blocks, and this test is tight over a $q$-symbol alphabet exactly when $\binom q2\geq2t$. For binary words and $b\geq2t+1$, we give an explicit construction with total redundancy at most $mt\log_2 b+O_t(m)$, matching the optimal per-block redundancy $t\log_2 b+O_t(1)$ among block sets correcting at every concatenation length. Among all binary $t$-correcting codes of length $mb$, the optimal total redundancy is $t\log_2(mb)+O_t(1)$. Using all concatenations of one block set makes our total redundancy grow linearly in $m$ and buys independent block encoding, with one encoder and decoder at every length. The construction encodes and decodes in time linear in $mb$ for fixed $b,t$, and recovers the $j$-th source block from the first $jb$ received symbols. We also prove that, whenever the length-$mb$ code corrects $t$ transpositions, the $j$-th source block is determined within $2tb$ received symbols beyond position $jb$, and that explicit binary block sets with rates tending to one as $b$ grows with $t$ fixed attain this bound in the worst case. Finally, we prove that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.