Do Flash Cells Really Jump? Measured Translocation Channels and Lehmer-Syndrome Codes

Rank modulation stores data in flash memory as the order of charges across a group of cells, not as their absolute voltage levels. Because only the order matters, the scheme is unaffected when all cells leak charge together. A whole family of codes has been built on one physical story. One leaky cell loses a large amount of charge suddenly and falls past several neighbours in the ranking, a single error event coding theorists call a translocation. None of those codes has ever been tested against measured flash behaviour, and the story itself has not been checked either. This proposal first measures how cell rankings actually get corrupted in real 3D-NAND. It then builds a code whose decoder is matched to what the measurements show. The code works on the inversion vector, a digit-by-digit description of a permutation in which a single translocation leaves a very specific and cheap-to-search fingerprint.

The core idea fits in two sentences. When one element jumps across $k$ others, its inversion vector changes in one coordinate by some amount and in several other coordinates by exactly one unit, all with the same sign. Parity checks on the inversion vector can therefore be decoded by sweeping over candidate jumps with constant-time incremental updates. That decoder can be weighted by an empirically measured distribution of jump lengths, instead of assuming worst-case or purely local errors.

Where the Directions Stand

The translocation model comes from Rank modulation for translocation error correction and Error-Correction in Flash Memories via Codes in the Ulam Metric. They measure errors with the Ulam distance, which is $n$ minus the length of the longest common subsequence of the two orderings. They prove capacity $1-\delta$ and build interleaved codes that fall well short of it. Multipermutation Codes in the Ulam Metric for Nonvolatile Memories extends this to rankings with ties.

Two lines map permutations into vector spaces so that standard decoders apply. Barg and Mazumdar in Codes in permutations and error correction for rank modulation map permutations to inversion vectors, which are integer vectors under $L_1$ distance. Constructions of Rank Modulation Codes adds a Gray map to binary BCH codes. Both handle only adjacent swaps, measured by the Kendall τ distance. Permutation and Multi-Permutation Codes Correcting Multiple Deletions gives the closest existing solution for translocations: a map into Hamming space with $d_H \le 3 d_U$ and redundancy $(3t-1)\log n + o(\log n)$. Its codes are non-systematic and it does not use inversion vectors.

Every one of these papers reports no measured error rate; the research file finds no reported number for any of them. Constructions of Rank Modulation Codes says explicitly that a probabilistic channel model for flash charge loss is missing. Real measurements do exist, but only for level-based flash storage. Neural Modulation for Flash Memory collected threshold-voltage data from commercial triple-level (TLC) and quad-level (QLC) 3D-NAND chips and fit a conditional generative channel model to them. That paper motivates our measurement design and supplies the level-based comparison point. On the molecular side, DNA Tails for Molecular Flash Memory used Lehmer (inversion-vector) encodings on synthetic DNA and validated them physically, but only against stuck-at errors. That shows inversion-vector codes survive contact with real media, but it does not test translocations.

Core Claim

Let $I_\pi(v)$ be the number of values larger than $v$ that appear before $v$ in the permutation $\pi$. Suppose element $x$ moves rightward past a set $J$ of $k$ elements. Then the inversion vector changes by

$$\Delta = \big|\{y\in J : y > x\}\big|\, e_x \;-\; \sum_{y\in J,\; y<x} e_y ,$$

where $e_v$ is the unit vector on coordinate $v$. A leftward jump flips the signs. So a translocation is one "spike" plus a same-sign run of unit changes on smaller values. Its $L_1$ size is $k$, which is exactly why Kendall-τ codes overpay for long jumps.

We define codes by weighted sums of inversion digits:

$$\mathcal{C} = \Big\{\pi : \sum_{v} h_v^{(i)} I_\pi(v) \equiv c_i \pmod{m},\ i=1,\dots,r\Big\},$$

where $h^{(i)}$ are integer weight vectors, $m$ is the modulus, and $r$ is the number of checks.

The decoder fixes a candidate element $x$ and slides it one position at a time. Each step changes the syndrome by one weight term, so all $n^2$ single-translocation hypotheses are scored in $O(n^2)$ total time. Candidate corrections are ranked by their likelihood under a measured mix of jump lengths and local swaps.

The information digits are the inversion digits themselves. When the syndrome is zero, the data can be read with an $O(n\log n)$ inversion-vector computation and no error-correction decoding. That readout path is missing from the Wang et al. construction.

We do not claim better asymptotic redundancy than Wang et al. The claim is narrower and testable. At matched redundancy and finite block length ($n$ between 16 and 64), a decoder matched to the measured channel should beat worst-case Ulam and Kendall codes in frame error rate and latency. The measurement itself, telling us whether flash errors are really translocation-like, is a result in its own right.

Research Program

Measurement. We program groups of $n$ cells to $n$ distinct target voltages in fine program steps, using a test platform that allows sub-level program control. We then read them back across program-erase cycles and retention bakes. From each readout we record the full displacement structure: how many errors are single long jumps, how many are adjacent swaps, and how many are multi-cell drift. We also record the length distribution of jumps.

If fine-grained program access is unavailable, we fall back on a channel model. Following Neural Modulation for Flash Memory, we fit a conditional generative model to measured voltage data and sample rankings from it. We state clearly that this route is one step removed from hardware. As a secondary physical channel, we examine the rank-order readouts from the DNA tails setting, to see whether its non-stuck errors are translocation-like.

Code design. We choose weights $h$ so that every error pattern within the measured bounded-length ball of radius $2t$ has a distinct nonzero syndrome. For $t=1$ we use Sidon-type sequences in the spirit of the Bose–Chowla construction of Codes in permutations and error correction for rank modulation. For $t=2$ at finite $n$ we use randomized search with exhaustive verification. Parity digits go in the widest-range inversion coordinates. We measure the rate lost to alphabet over-provisioning, a problem Barg and Mazumdar already flagged, rather than hiding it.

Restricting jumps to length at most $K$, set by the measurement, cuts the $t$-error search from $O(n^{2t})$ to $O((nK)^t)$. This also makes the bounded-length translocation problem concrete for the first time.

Baselines

The naive reference point is uncoded rank modulation at the same number of cells. It shows how often measured errors occur at all. Its frame error rate sets the floor every code must improve on.

The strongest adjacent-swap competitor is the inversion-vector, Gray-map, BCH pipeline of Constructions of Rank Modulation Codes. A jump of length $k$ is treated as $k$ swaps. We run it at identical redundancy, with the BCH strength chosen to match our parity budget.

The strongest translocation competitor is the Ulam-to-Hamming code of Permutation and Multi-Permutation Codes Correcting Multiple Deletions. We implement it at matched $n$ and $t$, with its redundancy of $(3t-1)\log n$ and its Hamming decoder. The interleaved construction of Rank modulation for translocation error correction is included at matched rate.

For all of these, no reported result was found on Lacuna for any error-rate metric. We therefore produce their numbers ourselves on the same readouts, and publish implementations so the comparison is auditable.

The level-based comparison is standard TLC storage with a binary code on the same cells at equal bits per cell. For reference, Neural Modulation for Flash Memory reports a 56% raw-bit-error-rate reduction for TLC, 17% for QLC, and 25% longer lifetime in program-erase cycles from learned write pre-distortion. We treat that as the bar a rank-modulation system must reach to be worth building.

Two ablations isolate what is new. The first keeps our code but decodes with a uniform prior over jumps, which isolates the value of the measured channel. The second keeps the measured prior but decodes only translocations, not mixed swaps, which isolates the value of the mixed error model.

Beating a baseline means lower frame error rate at the same bits per cell, redundancy and retention condition, with 95% confidence intervals from independent cell groups. Decoding latency counts toward the verdict: we must match or improve on Wang et al. in operation count.

Why not just…?

Why not just treat a translocation as $k$ adjacent swaps and use the Gray-map BCH code? This is a real threat if measured jumps are short. The theory behind the objection is sound: Barg and Mazumdar show capacity collapses when the required Kendall distance grows quadratically, but that only bites if long jumps occur. The measured jump-length distribution settles the question directly. If nearly all displacements are one or two positions, the Kendall code will likely win on rate, and we will report that the translocation premise fails in practice.

Why not just use the Wang et al. embedding, which already corrects translocations with low redundancy? At matched redundancy, its decoder is designed for worst-case errors and needs full decoding for every read. Our advantage has to come from channel matching, mixed-error handling and zero-syndrome direct readout. If Wang's code equals ours on measured data, the code-design contribution shrinks to the systematic readout path. The measurement result stands regardless.

Why not abandon rank modulation for level-based storage with a learned modulator? Rank modulation's selling point is that it ignores uniform charge drift, but that must be weighed against the measured controller-buffer costs of the neural approach. The honest test is the matched-density comparison against the level-based baseline across retention times. If rank modulation loses even after long retention, where uniform drift dominates, the whole line of work lacks a flash use case. That would be worth knowing.

Why not use a sublinear Ulam-distance approximation instead of algebraic decoding? The algorithm of Near-Optimal Sublinear Time Algorithms for Ulam Distance is randomized and approximates only within a constant factor. A controller that must decode deterministically cannot use it.

Decisive Checks

The first check is whether single long jumps make up a meaningful share of rank errors on measured or measurement-fit channels. The second is whether our decoder reduces frame error rate relative to Wang et al. and the Gray-map BCH code at equal redundancy, and whether the uniform-prior ablation removes most of that gain. The third is whether rank modulation with the best code approaches the reported level-based improvements at equal density. A negative answer to the first check redirects the program toward local-swap codes. A negative answer to the third is itself the empirical validation this literature has lacked.