--- title: "Permutation Modulation: Hiding Bits in the Order of Things" date: 2026-11-19T09:00:00Z draft: false category: research excerpt: "Sending bits in the order of things, not the things themselves." --- # $n!$ ways to say something --- ## Motivation In the field of communications most schemes grow in the number of bits that can be encoded as $\mathcal{O}(\log_2(n))$, where $n$ is a measure of the amount of resources (channels, power etc). [David Slepian](https://en.wikipedia.org/wiki/David_Slepian) outlined in March 1965 a method that ~wave:grows faster~ than this, at a rate of $\mathcal{O}(\log_2(n!))$, which I hope to give some insight on in this post, as it may become a significant part of communications in the future, given the computing power we now have. ![Bits per symbol against resources n from 1 to 16: log2 n reaches 4 bits at n = 16 while log2 n! reaches 44.3 bits](perm-growth.svg) To be a bit more careful about what I'm comparing against: the $\log_2(n)$ schemes here are the power-efficient ones, [pulse position modulation](https://en.wikipedia.org/wiki/Pulse-position_modulation) (PPM) and its orthogonal-signalling cousins, where one pulse lands in one of $n$ slots. Something like [QAM](https://en.wikipedia.org/wiki/Quadrature_amplitude_modulation) in every slot will happily grow linearly in $n$, but pays for it in power. Permutation modulation sits in between, and it has a party trick when it comes to detection that I think makes it worth knowing about. :bigthink: Using [Stirling's approximation](https://en.wikipedia.org/wiki/Stirling%27s_approximation), $$\log_2(n!) \approx n\log_2 n - n\log_2 e + \tfrac{1}{2}\log_2(2\pi n),$$ so the number of bits grows as $\mathcal{O}(n \log n)$, and the bits _per slot_ keep growing as $\log_2 n$, rather than shrinking like $\frac{\log_2 n}{n}$ as they do for PPM. The paper is D. Slepian, ["Permutation Modulation"](https://doi.org/10.1109/PROC.1965.3680), _Proceedings of the IEEE_, vol. 53, no. 3, pp. 228–236, 1965. It is short and very readable, and I'd recommend it. I first ran into permutation modulation in my [fourth year project](/posts/graph-modulation/), where it was the benchmark: the only scheme I could find that beats linear growth, and the thing my graph modulation was trying to beat in turn. Graph modulation didn't pan out, but I spent a good chunk of that project simulating and optimising permutation codes, and some of what I found is in this post, along with the proof, years later, that graph modulation _can't_ work. The [full report is here](/publications/pdf/GraphModulation.pdf) if you want the gory details. ## A Look at Permutation and Some Notation Consider a list containing $d$ objects, $[\rho_1, \rho_2, \dots , \rho_d ] $. We can permute this list by swapping elements until every single combination exists, and store them all in a single set $S$. For the case of three elements, where a list can be $[1,2,3]$, all possible combinations in $S$ will look as follows: $S =$ {[ 3 2 1 ], [ 3 1 2 ], [ 2 3 1 ], [ 2 1 3 ], [ 1 3 2 ], [ 1 2 3 ]} By counting the number of lists in $S$ (denoted by $\lvert S \rvert$), we find that for $d$ elements, we gain $d!$ different combinations! ![The six orders of the levels 1, 2 and 3 drawn as three pulses in three time slots](perm-codewords.svg) ### Repeated elements The list doesn't have to hold $d$ different things. If some of the entries repeat, swapping two equal entries gives the same list back, so we get fewer distinct orderings. Say we have $k$ distinct values $\mu_1 < \mu_2 < \dots < \mu_k$, and value $\mu_i$ appears $m_i$ times, with $m_1 + m_2 + \dots + m_k = d$. The number of distinct orderings is then the [multinomial coefficient](https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients) $$\lvert S \rvert = \frac{d!}{m_1!\, m_2! \cdots m_k!}.$$ All distinct ($m_i = 1$ for every $i$) gives back $d!$. At the other extreme, a single $1$ and $d-1$ zeros gives $\frac{d!}{1!\,(d-1)!} = d$, which is exactly PPM: a pulse in one of $d$ slots. So PPM is already a permutation code, it's just the least ambitious one! ## Applying Permutation to Communications The idea is simple enough to fit in a sentence: pick a starting list of signal levels, and send information by choosing _which order_ to transmit them in. Each entry of the list goes out on one of the $n$ resources: a time slot, a frequency, a wavelength, a wire. The receiver measures all $n$ of them, and has to work out which ordering was sent. To send $b$ bits we need $2^b \leq \lvert S \rvert$, so with all-distinct levels we get $b = \lfloor \log_2(n!) \rfloor$ bits per codeword. For $n = 16$ that's 44 bits from 16 slots, against 4 bits from 16-slot PPM. That floor is a small annoyance: $n!$ is almost never a power of two, so there are always some codewords left over. In my project I just threw away everything past the first $2^{\lfloor \log_2 \lvert S \rvert \rfloor}$, so for three levels, 4 of the 6 orderings get used and 2 are wasted. The spare codewords could be put to work (as an error check, say), and _which_ ones you throw away matters too, which I'll come back to. ### Variant I and Variant II codes Slepian defined two families of these codes, which he called Variant I and Variant II (I tend to think of them as type 1 and type 2). **Variant I** codes are what we've seen so far. Start from an initial vector $$\mathbf{x}_1 = [\,\underbrace{\mu_1, \dots, \mu_1}_{m_1}, \underbrace{\mu_2, \dots, \mu_2}_{m_2}, \dots, \underbrace{\mu_k, \dots, \mu_k}_{m_k}\,],$$ and the codebook is every distinct rearrangement of it, giving $$M_\text{I} = \frac{n!}{m_1!\, m_2! \cdots m_k!}$$ codewords. **Variant II** codes also let you flip the sign of each entry. Here the levels are non-negative, $0 \leq \mu_1 < \mu_2 < \dots < \mu_k$, and a codeword is any rearrangement of $\mathbf{x}_1$ with any choice of signs on its non-zero entries. If $h$ of the entries are non-zero, that's $$M_\text{II} = 2^h \, \frac{n!}{m_1!\, m_2! \cdots m_k!}$$ codewords. Flipping the sign of a zero doesn't give you anything new, which is why it's $2^h$ and not $2^n$. The same trick as before shows what familiar schemes are hiding in here: | Initial vector $\mathbf{x}_1$ | Variant | Codewords | What it is | |---|---|---|---| | $[1, 0, \dots, 0]$ | I | $n$ | PPM / orthogonal signalling | | $[1, 0, \dots, 0]$ | II | $2n$ | Biorthogonal signalling | | $[1, \dots, 1, 0, \dots, 0]$ ($w$ ones) | I | $\binom{n}{w}$ | Multi-pulse PPM | | $[1, 1, \dots, 1]$ | II | $2^n$ | BPSK in every slot | | $[1, 2, \dots, n]$ | I | $n!$ | The full permutation code | ![One example codeword from each scheme as four pulses: PPM with one pulse in slot 3, biorthogonal with a negative pulse in slot 2, multi-pulse PPM with pulses in slots 1 and 4, BPSK with plus, minus, minus, plus, and the full permutation code with levels 3, 1, 4, 2](scheme-family.svg) I really like this table. A lot of schemes that are taught as separate things are just different choices of $\mathbf{x}_1$ and of which variant to use. There's a practical split between the two as well. Variant I only ever sends the values in $\mathbf{x}_1$, so if they're all non-negative it works with intensity modulation, where you can't send a negative amount of light. Variant II needs signed signals, so it belongs on a carrier with a phase to flip (radio, or coherent optics). ### Maximising Distance Every codeword is a rearrangement of the same entries, so every codeword has exactly the same energy, $\lVert \mathbf{x} \rVert^2 = \sum_i m_i \mu_i^2$. Geometrically, all the codewords sit on the surface of a sphere, which makes these [_spherical codes_](https://en.wikipedia.org/wiki/Spherical_code), and the job of the designer is to spread them out on that sphere as much as possible. How far apart are two codewords? The closest pairs come from swapping two entries. If we swap a $\mu_i$ with a $\mu_j$, the two codewords differ in exactly two places, and $$\lVert \mathbf{x} - \mathbf{x}' \rVert^2 = 2(\mu_j - \mu_i)^2.$$ So the minimum distance is set by the two levels that are closest together: $$d_\text{min}^2 = 2 \min_i (\mu_{i+1} - \mu_i)^2.$$ The first easy win is to **remove the mean**. Subtracting the same constant from every entry doesn't change any of the differences, so it doesn't change any distance, but it does lower the energy. The best constant to subtract is the mean of $\mathbf{x}_1$, which is how PPM turns into the _simplex_ code, the classic answer for $n$ equally likely signals with a fixed energy. There's a nice geometric way to see this. Every rearrangement of $\mathbf{x}_1$ has the same sum, $c = \sum_i m_i \mu_i$, so every Variant I codeword lies on the hyperplane $$H = \left\{ \mathbf{x} \in \mathbb{R}^n : \textstyle\sum_i x_i = c \right\}.$$ If we fix the energy at 1, the codewords also lie on the unit sphere, so they're stuck on the intersection of the two: a smaller $(n-2)$-sphere of radius $\sqrt{1 - c^2/n}$. More radius means more room to spread the codewords out, and the radius is biggest when $c = 0$, that is, when the hyperplane passes through the origin. Slepian showed that optimal Variant I codes satisfy $\sum_i m_i \mu_i = 0$; I proved the hyperplane version of this in my project before realising it was the same statement. For three dimensions you can see it: the six codewords of $[1, 2, 3]$ (mean removed and normalised) sit on a circle around the sphere, at the corners of a regular hexagon. ![The six orderings of 1, 2 and 3, mean removed and normalised, on the unit sphere: a regular hexagon on the great circle where the plane x1 + x2 + x3 = 0 cuts the sphere, with a dashed smaller circle showing where they would sit without removing the mean](variant1-sphere.svg) That hexagon has a name, the [permutohedron](https://en.wikipedia.org/wiki/Permutohedron): the shape you get by taking every ordering of $[1, 2, \dots, n]$ as a point. Its edges join orderings that differ by one swap of neighbouring values, so the edges are exactly the nearest-neighbour pairs. In four dimensions it's a [truncated octahedron](https://en.wikipedia.org/wiki/Truncated_octahedron), and beyond that I'll leave it to your imagination. Variant II codewords don't have this problem, since flipping signs changes the sum, and they spread out over the whole sphere. In three dimensions all-distinct levels give $2^3 \times 3! = 48$ points, a hexagon of 6 in each of the 8 octants. ![48 Variant II codewords on the unit sphere: every ordering and sign pattern of three levels, forming a small hexagon in each of the eight octants](variant2-sphere.svg) The signs pick the octant and the ordering picks the point within its hexagon. This is a much better use of the sphere than Variant I's single ring, which is part of why Variant II did better in my simulations. The second is to **space the levels evenly**, since the smallest gap is all that matters. With mean-removed, evenly spaced levels a gap $\Delta$ apart, everything can be written down. For the full permutation code (all $n$ levels distinct) the energy is $$E = \Delta^2 \sum_{i=1}^{n}\left(i - \tfrac{n+1}{2}\right)^2 = \Delta^2\,\frac{n(n^2-1)}{12},$$ and so $$\frac{d^2_\text{min}}{E} = \frac{24}{n(n^2-1)}.$$ That falls off like $n^{-3}$, which is not great. This is the catch, and why I said permutation modulation sits _in between_. Squeezing $n$ distinct levels into a fixed amount of energy puts them very close together. A fair comparison has to be per bit, so here's $d^2_\text{min}/E_b$ (where $E_b = E/\log_2 M$; bigger is better), next to the bits each scheme carries: | $n$ | PPM bits | PPM $d^2_\text{min}/E_b$ | Full permutation bits | Full permutation $d^2_\text{min}/E_b$ | Multi-pulse PPM ($w = n/2$) bits | Multi-pulse $d^2_\text{min}/E_b$ | |---|---|---|---|---|---|---| | 4 | 2 | 5.33 | 4.58 | 1.83 | 2.58 | 5.17 | | 8 | 3 | 6.86 | 15.30 | 0.73 | 6.13 | 6.13 | | 16 | 4 | 8.53 | 44.25 | 0.26 | 13.65 | 6.83 | (PPM is $\mathbf{x}_1 = [1, 0, \dots, 0]$, multi-pulse PPM is $w$ ones and $n - w$ zeros, all mean-removed.) ![Distance per bit against bits per codeword for n from 2 to 16: PPM rises to 8.5 but stays under 4 bits, the full permutation code reaches 44 bits while its distance per bit falls to 0.26, and multi-pulse PPM sits between them](distance-tradeoff.svg) So the full permutation code buys a huge number of bits with a lot of power, and PPM does the opposite. The interesting codes are in the middle, using a handful of levels each repeated many times. Multi-pulse PPM with $n = 16$ already carries over three times the bits of PPM for about 20% less distance per bit. Choosing $\mu_i$ and $m_i$ for a given $n$ and rate is an optimisation problem, and Slepian worked through it in the paper, along with what happens as $n$ grows large. ### Optimising the levels numerically In my project I attacked the level-setting problem head on for the all-distinct case ($m_i = 1$), since optimising the integer $m_i$ as well was far too hard to fit in. The approach was blunt: write a function that takes a generating list, builds the whole codebook, and returns its minimum distance, then hand that to the [Nelder–Mead](https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method) simplex optimiser with the energy fixed to 1. The blunt approach gets expensive fast. For Variant II with $n = 5$ there are $2^5 \times 5! = 3840$ codewords, so finding the minimum distance naively means $3840^2 \approx 1.5 \times 10^7$ distances, and the optimiser wants that number many times over. Symmetry saves you most of it: every orthant holds the same arrangement of points, so it's enough to look at the points in one orthant and their nearest neighbours in the next, and distance is symmetric so only half the pairs are needed. That brought it down to roughly $(n!)^2$. Running enough of these optimisations, I fitted a rule of thumb for the best Variant II levels: $$\mu_i' = (i + 1)\left(1 + \frac{n+1}{9}\right) - \frac{n+1}{10}, \qquad i = 0, 1, \dots, n-1,$$ normalised to unit energy. It's an empirical fit and nothing more, but it made a very good starting point for the optimiser, which then only had to polish it. How good were the optimised codes? Against random generating lists, the optimised Variant II codes won every test, and the gap grew with $n$. The one place they lost was Variant I in three dimensions, which comes back to that floor from earlier: with only 4 of the 6 hexagon points in use, arranging 4 points in a square beats any 4 corners of a hexagon. Choosing which codewords to throw away is its own optimisation problem, and one I never got to. ![Looking straight down on the Variant I plane: keeping four of the six hexagon corners leaves the closest pair one radius apart, while four points in a square on the same circle are the square root of two times further apart](trim-square.svg) The square isn't a permutation code any more (no rearrangement of a single list gives you it), which is the point: once you're throwing codewords away anyway, the structure that made permutation codes nice is no longer the only thing worth keeping. To see how well permutation uses the space, I compared it against a code I built to spread points as evenly as possible over the sphere (I called it Thomson modulation, after the [Thomson problem](https://en.wikipedia.org/wiki/Thomson_problem) of spacing electrons on a sphere), and against plain QAM. Variant II with $n = 4$ gives $\log_2(2^4 \times 4!) \approx 8.6$ bits, trimmed to 8, which over two complex channels is 4 bits per channel, the same as 16-QAM. Both the Thomson code and 16-QAM beat it on bit error rate. That was the honest conclusion: permuting a single vector doesn't use the space especially well. What it _does_ have, and what an evenly spaced cloud of points doesn't, is structure that makes it cheap to detect, which brings us to the good bit. ### Detection This is my favourite part. The receiver gets $\mathbf{r} = \mathbf{x} + \mathbf{n}$, where $\mathbf{n}$ is [white Gaussian noise](https://en.wikipedia.org/wiki/Additive_white_Gaussian_noise). Optimum (maximum likelihood) detection means finding the codeword closest to $\mathbf{r}$. Done naively, that's comparing $\mathbf{r}$ against all $M$ codewords, and for $n = 16$ with distinct levels that's $16! \approx 2 \times 10^{13}$ comparisons per received word. Not ideal. But all the codewords have the same energy, so the closest codeword is the one with the biggest correlation $\mathbf{r} \cdot \mathbf{x}$. And we want to pair up the entries of $\mathbf{r}$ with the entries of $\mathbf{x}_1$ so that $\sum_j r_j x_j$ is as big as possible. The [rearrangement inequality](https://en.wikipedia.org/wiki/Rearrangement_inequality) says you do that by matching the biggest with the biggest, the second biggest with the second biggest, and so on. So, for Variant I, the optimum detector is: 1. Sort the received values. 2. Give the $m_k$ largest ones the level $\mu_k$, the next $m_{k-1}$ the level $\mu_{k-1}$, and so on down. That's it! Detection is ~wave:just sorting~, $\mathcal{O}(n \log n)$ work instead of $\mathcal{O}(M)$. ![Detection by sorting: received values 2.7, 0.8 and 2.2 are ranked, giving slot t2 rank 1, t3 rank 2 and t1 rank 3, and handing out the levels by rank gives back the codeword 3, 1, 2](sort-detect.svg) For Variant II it's barely harder: sort by _magnitude_, hand out the levels by rank in the same way, then copy each non-zero entry's sign from the sign of the received value. There's a really nice consequence of this. Sorting only cares about which value is bigger than which, so the decision doesn't change if the receiver applies _any_ increasing function to $\mathbf{r}$ first. An unknown gain, an unknown DC offset, a compressive amplifier, all of it is invisible to a Variant I detector. With ordinary amplitude levels you'd need to estimate the gain and offset to set your decision thresholds. Here, the codeword is its own reference. Coming from optical wireless, where an unknown amount of ambient light adds an offset and the channel gain shifts every time someone moves, I find this very appealing. #### Sorting against brute force, in simulation In my project I treated these as two different decoders: a "maximum likelihood" one that took the dot product of the received vector with every codeword and picked the biggest, and a "rank" decoder that sorted (one call to MATLAB's `sort`, with a separate sign detector for Variant II). Then I simulated both over the optimised codes to see what the sort cost me. For Variant I, brute force came out ahead, but only by fractions of a decibel at a bit error rate of $10^{-3}$. For Variant II the two were practically on top of each other, with sorting very slightly _ahead_ on bit error rate. With hindsight I can explain both. Sorting is exactly maximum likelihood over the _full_ codebook, but I'd trimmed the codebook down to a power of two, and the brute-force search only looked at codewords that could actually have been sent. Sorting doesn't know about the trimming, so now and then it lands on a codeword that was thrown away, and that's where the fraction of a decibel goes. And maximum likelihood minimises the chance of getting the _codeword_ wrong, not the number of wrong _bits_, so a decoder that settles each sign on its own can come out slightly ahead on bit errors. Either way the conclusion was the same: sorting gets you essentially all of the performance for a tiny fraction of the work, and its output goes straight into the conversion back to bits. ### Mapping bits to permutations The last piece is turning a block of bits into an ordering and back. With $b$ bits we have an integer $0 \leq B < 2^b \leq n!$, and the [factorial number system](https://en.wikipedia.org/wiki/Factorial_number_system) (via the [Lehmer code](https://en.wikipedia.org/wiki/Lehmer_code)) gives a neat one-to-one map between integers below $n!$ and orderings. Every ordering is used at most once, and no table of $n!$ entries is needed. Let's write it out and give it a burl, for the all-distinct case: ```python from math import factorial def encode(b, levels): """Map an integer 0 <= b < n! to an ordering of distinct levels.""" pool = sorted(levels) word = [] for i in range(len(pool), 0, -1): idx, b = divmod(b, factorial(i - 1)) word.append(pool.pop(idx)) return word def detect(received, levels): """Optimum detection in Gaussian noise: sort, then hand out levels by rank.""" order = sorted(range(len(received)), key=lambda j: received[j]) word = [0] * len(received) for level, j in zip(sorted(levels), order): word[j] = level return word def decode(word): """Inverse of encode.""" pool = sorted(word) b = 0 for i, x in enumerate(word): idx = pool.index(x) b += idx * factorial(len(word) - 1 - i) pool.pop(idx) return b ``` Sending $B = 4$ with levels $[1, 2, 3]$ gives the codeword $[3, 1, 2]$. If it arrives as $[2.7, 0.8, 2.2]$, sorting puts slot 2 lowest, then slot 3, then slot 1, so the detector gives back $[3, 1, 2]$, and that decodes to $4$. Scale the received values by 10 and add 5 and you get exactly the same answer. As written this is $\mathcal{O}(n^2)$ for the list pops, which can be brought down to $\mathcal{O}(n \log n)$ with a [Fenwick tree](https://en.wikipedia.org/wiki/Fenwick_tree), and for big $n$ the integers are much wider than 64 bits. In 1965 that was real work. Today it isn't, which is a big part of why I think this deserves another look. ## Can anything grow faster? My fourth year project asked one question: if permutations get you $\mathcal{O}(n \log n)$, is there a scheme that gets $\mathcal{O}(n^{1+\epsilon})$? My bet was graphs. A graph on $r$ vertices has $\binom{r}{2}$ possible edges, so the number of graphs grows like $2^{r^2/2}$, which makes $n!$ look tiny. I couldn't make it work, and I finished the project with a list of the ways it _didn't_ work and a hunch that I'd been missing a trick. Seven years later I came back to it with a fleet of agents (Claude Fable doing the heavy lifting) and a much less polite question: is there a proof that it can't work? There is, and it's short enough that I'm a bit embarrassed I didn't find it as an undergrad. :sadparrot: ### The ceiling Take any codebook of $M$ points in $n$ dimensions with energy at most 1, so every point sits in the unit ball, and say every pair is at least $d$ apart. Put a ball of radius $d/2$ around each point. None of them overlap, and they all fit inside a ball of radius $1 + d/2$, so comparing volumes, $$M \left(\frac{d}{2}\right)^n \leq \left(1 + \frac{d}{2}\right)^n \quad\Longrightarrow\quad \log_2 M \leq n \log_2\!\left(1 + \frac{2}{d}\right).$$ That's the whole argument. It's the standard [sphere packing](https://en.wikipedia.org/wiki/Sphere_packing) volume bound, nothing exotic. ![Codewords inside the unit circle with non-overlapping balls of radius d/2 around each, all inside a dashed circle of radius 1 + d/2](packing.svg) Now, the minimum distance against the noise is what sets the SNR you need for a given error rate. If you're willing to let the SNR grow _polynomially_ with $n$, the distance can shrink polynomially, $d = n^{-c}$, and the bound gives $$\log_2 M \leq (c + o(1))\, n \log_2 n.$$ So $n \log n$ is the ceiling, and permutation modulation is already in the top class. To get $n^{1+\epsilon}$ bits, you need $\log_2(1/d)$ to grow like $n^\epsilon$, which means $d \lesssim 2^{-n^\epsilon}$, which means an SNR that grows _exponentially_ in $n$. It's the same story from [Shannon's](https://en.wikipedia.org/wiki/Channel_capacity) side. The capacity of $n$ real dimensions is $\tfrac{n}{2}\log_2(1 + \text{SNR})$, and with an SNR that is polynomial in $n$, that's $\Theta(n \log n)$. That reframes the motivation at the top of this post a bit, and I think it's the most important thing I've learned about this whole topic: | SNR as $n$ grows | Best possible bits | Example | |---|---|---| | Constant | $\Theta(n)$ | QAM on every channel | | Polynomial in $n$ | $\Theta(n \log n)$ | Permutation modulation | | Exponential in $n$ | $n^{1+\epsilon}$ and up | Graph modulation, if it existed | ![The minimum SNR Shannon allows against n: n bits needs a constant 4.8 dB, log2 n! bits needs an SNR rising to 21 dB at n = 32, and n(n-1)/2 bits needs an SNR rising about 3 dB per dimension to 93 dB](snr-price.svg) Permutation modulation's $n \log n$ isn't a way round Shannon, it _is_ Shannon at an SNR that grows with $n$. Remember from the distance section that the full permutation code's $d_\text{min}$ shrinks like $n^{-3/2}$ at fixed energy: that's exactly the polynomially growing SNR being paid for. The win is that permutation modulation reaches that class with a structure you can decode by sorting, rather than with a giant unstructured codebook. The verification pass also went through the obvious ways to wriggle out (cleverer soft decoders, peak versus average power, feedback, MIMO, nonlinear channels, even quantum) and closed each one with a standard converse. ### What that means for graph modulation Graph modulation, carrying $\Theta(r^2)$ edge bits, would need $r^2 \lesssim n \log n$, so $r = \mathcal{O}(\sqrt{n \log n})$ vertices: it caps itself straight back to $\Theta(n \log n)$. The ambiguity I kept hitting in the project, where my cut-based scheme mapped several graphs to the same signal, wasn't a missing trick. It was the geometry asserting itself. The group theory route is closed too. Apart from a handful of small dimensions (where exceptional objects like the $E_8$ lattice's symmetry group sneak in), the biggest finite group of symmetries of $\mathbb{R}^n$ you can build from rational matrices has order $2^n n!$, and that group is exactly the signed permutations: Slepian's Variant II. He'd already used the biggest one in 1965, and even the exceptions are $2^{\Theta(n \log n)}$, so nothing changes. So, as far as I'm concerned, the open question from my project is closed, negatively. That's an unsatisfying answer, but a much better one than "I couldn't find it". ### Squeezing out a better constant The class is fixed, but the constant in front isn't. At the full permutation code's own minimum distance, $d \sim n^{-3/2}$, the packing bound allows about $\tfrac{3}{2} n \log_2 n$ bits, and Slepian's code gets $n \log_2 n$. There's half an $n \log_2 n$ on the table. The idea I had for this (before I knew the bound) was to permute _codebooks_ as well as levels. Take $m$ time slots, each carrying one $n$-dimensional permutation codeword, and give each slot its own generating word, all of them different. Then which generating word goes in which slot is _itself_ a permutation, and carries another $\log_2(m!)$ bits on top of the $m \log_2(n!)$: $$\text{bits} = m \log_2(n!) + \log_2(m!).$$ ![Four slots, each holding a four-level permutation codeword from a different generating word, labelled C, A, D and B; the order of the generating words across the slots is itself a permutation](wreath.svg) Every slot still holds one codeword at unit energy, so the power in each slot stays exactly fixed. In group theory terms the codebook is an orbit of the [wreath product](https://en.wikipedia.org/wiki/Wreath_product) $S_n \wr S_m$, which turns out to be the biggest permutation symmetry you can use without moving energy between slots. Decoding stays cheap. Sort each slot once, and you can score it against every generating word. Then pick the best one-to-one assignment of generating words to slots with the [Hungarian algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm), in $\mathcal{O}(m^3)$. That combination is exact maximum likelihood. The catch is that the generating words have to be told apart, and at small $n$ there isn't much room to put them. In simulation (64 dimensions per block, SNR needed for a bit error rate of $10^{-3}$): | Slots | Scheme | Bits | SNR at BER $10^{-3}$ | |---|---|---|---| | $n = 4$, $m = 16$ | Permutation code in each slot | 64 | 13.9 dB | | $n = 4$, $m = 16$ | Permuted codebooks | 108 | 23.6 dB | | $n = 4$, $m = 16$ | 16-QAM | 128 | 16.5 dB | | $n = 8$, $m = 8$ | Permutation code in each slot | 120 | 20.4 dB | | $n = 8$, $m = 8$ | Permuted codebooks | 135 | 22.5 dB | ![Bits per block against SNR needed: at n = 4 permuting codebooks goes from 64 to 108 bits for 9.7 dB more, while 16-QAM gets 128 bits at 16.5 dB; at n = 8 it goes from 120 to 135 bits for 2.1 dB more](wreath-results.svg) At $n = 4$ it's a bad deal: 16-QAM gets more bits for 7 dB less, which is the same thing my project kept finding, QAM wins at small $n$. But the price falls quickly as $n$ grows, from 9.6 dB for the extra bits at $n = 4$ to 2.1 dB at $n = 8$, and the theory says that for big $n$ you can have up to about $\sqrt{n!}$ codebooks for free, which is where the 1.5× comes from. The closest published relative I know of is multi-mode OFDM with index modulation, which permutes whole 2-D constellations across subcarriers, and is this idea with trivially small slots. As far as I can tell, nobody has put permutation codes _inside_ the slots, and I'm writing it up properly. ### The one honest loophole: identification Every bound above assumes the receiver wants to know _which_ message was sent. Change the question to "was it message $m$, yes or no?" and the rules change completely. That's _identification_: think of a wake-up radio that only needs to know whether it was its own name that was called. Ahlswede and Dueck showed in 1989 that with randomised encoding you can identify around $2^{2^{nC}}$ messages, doubly exponential, at a constant SNR. With a deterministic encoder over a Gaussian channel, the count is $2^{R\, n \log n}$, the _same_ $n \log n$ scale as permutation modulation, and that's no coincidence: the constructions are ball packings in the power sphere, the same geometry as everything above ([Salariseddigh et al.](https://arxiv.org/abs/2010.04239)). The constant $R$ is only known to sit between $3/8$ ([Galaxy codes](https://arxiv.org/abs/2501.12548), 2025) and $1/2$, and that gap is an active research area right now. This is where the graphs might get a second life. My cut-based graph codes died because several graphs looked the same at the receiver. Identification codes have overlapping decision regions _on purpose_: the receiver only tests the one graph it cares about. Whether graph-structured codebooks make good identification codes is a question I'd love to see answered. ## Current Real World Applications ### Rank modulation A close relative of permutation modulation has been proposed for storing data in [flash memory](https://en.wikipedia.org/wiki/Flash_memory), under the name 'rank modulation' (A. Jiang, R. Mateescu, M. Schwartz and J. Bruck, ["Rank Modulation for Flash Memories"](https://doi.org/10.1109/TIT.2009.2018336), _IEEE Transactions on Information Theory_, 2009). A flash cell stores data as an amount of charge, and conventional [multi-level](https://en.wikipedia.org/wiki/Multi-level_cell) flash reads a cell by comparing its charge against fixed thresholds. This causes two problems: - **Writing is slow and fiddly.** You can add charge to a cell but you can't take a bit back out without erasing a whole block, so the controller has to creep up on the target level in small steps, checking as it goes, to avoid overshooting. - **Charge leaks over time.** As the cells drift, levels slide across the fixed thresholds and bits flip. Rank modulation stores information in the _relative order_ of the charges in a group of $n$ cells, and nothing else. That is exactly a Variant I code with distinct levels, except the levels aren't fixed in advance: only their order matters. Both problems get easier: - **Writing** uses an operation called "push-to-the-top": pick a cell and inject charge until it's above every other cell in the group. There's no precise target to hit, it only has to end up highest, so overshooting is harmless. Any ordering can be reached with a sequence of these pushes. - **Reading** is a sort, the same as our detector, so there are no thresholds. If all the cells leak at a similar rate, the order survives even though every absolute level has moved, which is the gain and offset invariance from earlier doing real work. ![Four flash cells before and after pushing cell 3 to the top: cell 3 goes from lowest to highest without needing to hit an exact level, changing the order from 2, 4, 1, 3 to 3, 2, 4, 1](push-to-top.svg) The errors that do happen look different, too. Noise and leakage tend to swap the order of two cells that were close in charge, so the natural way to measure errors is the [_Kendall tau distance_](https://en.wikipedia.org/wiki/Kendall_tau_distance): the number of swaps of neighbours it takes to turn one ordering into another. That's spawned a whole line of work on error-correcting codes over permutations under the Kendall tau metric (Barg and Mazumdar, "Codes in Permutations and Error Correction for Rank Modulation", _IEEE Transactions on Information Theory_, 2010, is a good place to start). The paper also has [Gray codes](https://en.wikipedia.org/wiki/Gray_code) for rank modulation, orderings you can step through with one push-to-the-top each, which is handy for storing a value that gets incremented. As far as I can tell this is still a research proposal rather than something in the SSD in your laptop, but it's the most developed modern use of the idea. ### Power line communications The other place permutations turn up is [power line communications](https://en.wikipedia.org/wiki/Power-line_communication), which has some truly horrible noise: narrowband interferers that wipe out one frequency for a long time, and impulses that wipe out everything for a short time. Vinck's proposal ("Coded Modulation for Power Line Communications", 2000) combines $M$-ary [FSK](https://en.wikipedia.org/wiki/Frequency-shift_keying) with permutation codes. Each codeword is a permutation of the $M$ frequencies, sent one per time slot, so every frequency is used exactly once per codeword. A narrowband interferer then corrupts at most one symbol in each codeword, and an impulse corrupts at most one time slot, and a code with a large [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) between permutations can correct both. This is a different flavour from Slepian's codes. The distance is Hamming distance between orderings rather than Euclidean distance between signal vectors, but it's the same object underneath. ### Index modulation and friends Permutation modulation also has a big family of descendants in radio, which send information in _which_ resources are used, not just in what is sent on them. - [**Spatial modulation**](https://en.wikipedia.org/wiki/Spatial_modulation) has several transmit antennas but only switches one on at a time, so the choice of antenna carries bits on top of the symbol it sends. - **[OFDM](https://en.wikipedia.org/wiki/Orthogonal_frequency-division_multiplexing) with index modulation** leaves some subcarriers empty and lets the pattern of active subcarriers carry bits, on top of the QAM symbols on the active ones. - **Parallel combinatory** schemes (an older idea from spread spectrum) send a few of a larger set of spreading codes at once, and the choice of which few carries information. Squint and these are multi-pulse PPM from the table above, with the "on" entries carrying a symbol of their own. They've had a lot of attention as candidates for 5G and beyond, and the same counting trick is what gets them extra bits. If you want the whole family tree, N. Ishikawa, S. Sugiura and L. Hanzo, ["50 Years of Permutation, Spatial and Index Modulation: From Classic RF to Visible Light Communications and Data Storage"](https://arxiv.org/abs/1803.03939) (_IEEE Communications Surveys & Tutorials_, 2018) is a great survey, and it was the starting point for my literature review back in 2019. ## Where it might go I said at the start that permutation modulation might become a significant part of communications in the future. I'll stand by that, but with some honesty from the distance section: full permutation codes are power hungry, so the useful versions repeat a small number of levels many times. And thanks to the ceiling, I no longer expect anything to come along and beat it by a whole growth class: the gains left are in the constant, and in structure that is cheap to decode. What keeps me interested: - **Detection is cheap.** Sorting is $\mathcal{O}(n \log n)$ and parallelises well in hardware ([sorting networks](https://en.wikipedia.org/wiki/Sorting_network)), no matter how big the codebook gets. - **Gain and offset don't matter.** For Variant I, any increasing distortion at the receiver is free. That suits channels that drift, from optical links in ambient light to cells in flash memory. - **It's already in the top class.** At an SNR that grows polynomially with $n$, nothing can beat $\Theta(n \log n)$, and permutation codes get there with a decoder that is just a sort. - **It unifies a lot.** PPM, multi-pulse PPM, orthogonal, biorthogonal and simplex signalling are all special cases, so a receiver built to sort can handle a whole family of schemes by changing $\mathbf{x}_1$. If you've used permutation codes in anger, or you've seen rank modulation in real hardware, please get in touch, I'd love to hear about it.