Permutation Modulation: Hiding Bits in the Order of Things

n ! n! ways to say something


Motivation

In the field of communications most schemes grow in the number of bits that can be encoded as 𝒪︀ ( log 2 ( n ) ) \mathcal{O}(\log_2(n)) , where n n is a measure of the amount of resources (channels, power etc).

David Slepian outlined in March 1965 a method that grows faster than this, at a rate of 𝒪︀ ( log 2 ( n ! ) ) \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 from n resources Bits carried per symbol as the number of resources n grows from 1 to 16. Picking one of n (log2 n) reaches 4 bits at n = 16; picking an order of n things (log2 n!) reaches 44.3 bits. 0102030401481216 log2 n4 bits log2 n! 44.3 bits n, the resources bits per symbol

To be a bit more careful about what I’m comparing against: the log 2 ( n ) \log_2(n) schemes here are the power-efficient ones, pulse position modulation (PPM) and its orthogonal-signalling cousins, where one pulse lands in one of n n slots. Something like QAM in every slot will happily grow linearly in n 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,

log 2 ( n ! ) ≈ n log 2 n − n log 2 e + 1 2 log 2 ( 2 π n ) , \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 𝒪︀ ( n log n ) \mathcal{O}(n \log n) , and the bits per slot keep growing as log 2 n \log_2 n , rather than shrinking like log 2 n n \frac{\log_2 n}{n} as they do for PPM.

The paper is D. Slepian, “Permutation Modulation”, 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, 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 if you want the gory details.

A Look at Permutation and Some Notation

Consider a list containing d d objects, [ ρ 1 , ρ 2 , … , ρ d ] [\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 S . For the case of three elements, where a list can be [ 1 , 2 , 3 ] [1,2,3] , all possible combinations in S S will look as follows:

S = 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 S (denoted by | S | \lvert S \rvert ), we find that for d d elements, we gain d ! d! different combinations!

Every order of three levels The six permutations of the levels 1, 2 and 3, each drawn as three pulses in time slots t1 to t3: [3 2 1], [3 1 2], [2 3 1], [2 1 3], [1 3 2] and [1 2 3]. Six codewords from three slots. t1t2t3 [3 2 1] t1t2t3 [3 1 2] t1t2t3 [2 3 1] t1t2t3 [2 1 3] t1t2t3 [1 3 2] t1t2t3 [1 2 3]

Repeated elements

The list doesn’t have to hold d 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 k distinct values μ 1 < μ 2 < … < μ k \mu_1 < \mu_2 < \dots < \mu_k , and value μ i \mu_i appears m i m_i times, with m 1 + m 2 + … + m k = d m_1 + m_2 + \dots + m_k = d . The number of distinct orderings is then the multinomial coefficient

| S | = d ! m 1 ! m 2 ! ⋯ m k ! . \lvert S \rvert = \frac{d!}{m_1!\, m_2! \cdots m_k!}.

All distinct ( m i = 1 m_i = 1 for every i i ) gives back d ! d! . At the other extreme, a single 1 1 and d − 1 d-1 zeros gives d ! 1 ! ( d − 1 ) ! = d \frac{d!}{1!\,(d-1)!} = d , which is exactly PPM: a pulse in one of d 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 n resources: a time slot, a frequency, a wavelength, a wire. The receiver measures all n n of them, and has to work out which ordering was sent.

To send b b bits we need 2 b ≤ | S | 2^b \leq \lvert S \rvert , so with all-distinct levels we get b = ⌊ log 2 ( n ! ) ⌋ b = \lfloor \log_2(n!) \rfloor bits per codeword. For n = 16 n = 16 that’s 44 bits from 16 slots, against 4 bits from 16-slot PPM.

That floor is a small annoyance: n ! 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 ⌊ log 2 | S | ⌋ 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

𝐱 1 = [ μ 1 , … , μ 1 ⏟ m 1 , μ 2 , … , μ 2 ⏟ m 2 , … , μ k , … , μ k ⏟ m k ] , \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 I = n ! m 1 ! m 2 ! ⋯ m k ! 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 ≤ μ 1 < μ 2 < … < μ k 0 \leq \mu_1 < \mu_2 < \dots < \mu_k , and a codeword is any rearrangement of 𝐱 1 \mathbf{x}_1 with any choice of signs on its non-zero entries. If h h of the entries are non-zero, that’s

M II = 2 h n ! m 1 ! m 2 ! ⋯ m k ! 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 2^h and not 2 n 2^n .

The same trick as before shows what familiar schemes are hiding in here:

Initial vector 𝐱 1 \mathbf{x}_1 Variant Codewords What it is
[ 1 , 0 , … , 0 ] [1, 0, \dots, 0] I n n PPM / orthogonal signalling
[ 1 , 0 , … , 0 ] [1, 0, \dots, 0] II 2 n 2n Biorthogonal signalling
[ 1 , … , 1 , 0 , … , 0 ] [1, \dots, 1, 0, \dots, 0] ( w w ones) I ( n w ) \binom{n}{w} Multi-pulse PPM
[ 1 , 1 , … , 1 ] [1, 1, \dots, 1] II 2 n 2^n BPSK in every slot
[ 1 , 2 , … , n ] [1, 2, \dots, n] I n ! n! The full permutation code

Familiar schemes as permutation codes One example codeword from each scheme in the table, drawn as four pulses in four slots. PPM: a single pulse, here in slot 3. Biorthogonal: a single pulse that may be negative, here minus one in slot 2. Multi-pulse PPM: two pulses, in slots 1 and 4. BPSK in every slot: plus or minus one in every slot, here + - - +. Full permutation: the levels 1 to 4 in some order, here 3 1 4 2. Variant It1t2t3t4Variant IIt1t2t3t4Variant It1t2t3t4Variant IIt1t2t3t4Variant It1t2t3t4 PPMBiorthogonalMulti-pulse PPMBPSK in every slotFull permutationblue: positive pulsered: negative pulse

I really like this table. A lot of schemes that are taught as separate things are just different choices of 𝐱 1 \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 𝐱 1 \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, ‖ 𝐱 ‖ 2 = ∑ i m i μ i 2 \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, 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 μ i \mu_i with a μ j \mu_j , the two codewords differ in exactly two places, and

‖ 𝐱 − 𝐱 ′ ‖ 2 = 2 ( μ j − μ i ) 2. \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 min 2 = 2 min i ( μ i + 1 − μ i ) 2. 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 𝐱 1 \mathbf{x}_1 , which is how PPM turns into the simplex code, the classic answer for n n equally likely signals with a fixed energy.

There’s a nice geometric way to see this. Every rearrangement of 𝐱 1 \mathbf{x}_1 has the same sum, c = ∑ i m i μ i c = \sum_i m_i \mu_i , so every Variant I codeword lies on the hyperplane

H = { 𝐱 ∈ ℝ n : ∑ i x i = c } . 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 ) (n-2) -sphere of radius 1 − c 2 / n \sqrt{1 - c^2/n} . More radius means more room to spread the codewords out, and the radius is biggest when c = 0 c = 0 , that is, when the hyperplane passes through the origin. Slepian showed that optimal Variant I codes satisfy ∑ i m i μ i = 0 \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 ] [1, 2, 3] (mean removed and normalised) sit on a circle around the sphere, at the corners of a regular hexagon.

Variant I codewords in three dimensions The six orderings of the levels 1, 2 and 3, with the mean removed and scaled to unit energy, drawn on the unit sphere. They all sit on the plane x1 + x2 + x3 = 0, at the corners of a regular hexagon on the great circle where that plane cuts the sphere. A dashed smaller circle shows where the codewords would sit if the mean were not removed. x1x2x3 c ≠ 0 (dashed):a smaller circle, sothe points crowd together [1 2 3][2 1 3][3 1 2][3 2 1][2 3 1][1 3 2]Mean removed (c = 0):the biggest circle,a regular hexagon

That hexagon has a name, the permutohedron: the shape you get by taking every ordering of [ 1 , 2 , … , n ] [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, 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 × 3 ! = 48 2^3 \times 3! = 48 points, a hexagon of 6 in each of the 8 octants.

Variant II codewords in three dimensions The 48 Variant II codewords for three levels in three dimensions: every ordering of the levels with every choice of signs, on the unit sphere. They form 8 small hexagons, one in each octant, each hexagon being the 6 orderings for one pattern of signs. Points on the far side of the sphere are drawn faint. x1x2x3 levels ≈ [0.22, 0.52, 0.82] (the rule of thumb for n = 3), 2³ × 3! = 48 codewords

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 n levels distinct) the energy is

E = Δ 2 ∑ i = 1 n ( i − n + 1 2 ) 2 = Δ 2 n ( n 2 − 1 ) 12 , 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

d min 2 E = 24 n ( n 2 − 1 ) . \frac{d^2_\text{min}}{E} = \frac{24}{n(n^2-1)}.

That falls off like n − 3 n^{-3} , which is not great. This is the catch, and why I said permutation modulation sits in between. Squeezing n 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 min 2 / E b d^2_\text{min}/E_b (where E b = E / log 2 M E_b = E/\log_2 M ; bigger is better), next to the bits each scheme carries:

n n PPM bits PPM d min 2 / E b d^2_\text{min}/E_b Full permutation bits Full permutation d min 2 / E b d^2_\text{min}/E_b Multi-pulse PPM ( w = n / 2 w = n/2 ) bits Multi-pulse d min 2 / E b 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 𝐱 1 = [ 1 , 0 , … , 0 ] \mathbf{x}_1 = [1, 0, \dots, 0] , multi-pulse PPM is w w ones and n − w n - w zeros, all mean-removed.)

Bits against distance per bit Minimum squared distance per unit energy per bit (higher is more robust) against bits per codeword, for n from 2 to 16 slots, all mean-removed. PPM climbs from 4 to 8.5 while carrying at most 4 bits. The full permutation code reaches 44 bits at n = 16 but its distance per bit falls to 0.26. Multi-pulse PPM with half the slots on sits in between: 13.7 bits at n = 16 with distance per bit 6.8. 02468125102050 PPM, n = 2: 1.00 bits, d²/Eb = 4.00PPM, n = 3: 1.58 bits, d²/Eb = 4.75PPM, n = 4: 2.00 bits, d²/Eb = 5.33PPM, n = 5: 2.32 bits, d²/Eb = 5.80PPM, n = 6: 2.58 bits, d²/Eb = 6.20PPM, n = 7: 2.81 bits, d²/Eb = 6.55PPM, n = 8: 3.00 bits, d²/Eb = 6.86PPM, n = 9: 3.17 bits, d²/Eb = 7.13PPM, n = 10: 3.32 bits, d²/Eb = 7.38PPM, n = 11: 3.46 bits, d²/Eb = 7.61PPM, n = 12: 3.58 bits, d²/Eb = 7.82PPM, n = 13: 3.70 bits, d²/Eb = 8.02PPM, n = 14: 3.81 bits, d²/Eb = 8.20PPM, n = 15: 3.91 bits, d²/Eb = 8.37PPM, n = 16: 4.00 bits, d²/Eb = 8.53 Full permutation, n = 2: 1.00 bits, d²/Eb = 4.00Full permutation, n = 3: 2.58 bits, d²/Eb = 2.58Full permutation, n = 4: 4.58 bits, d²/Eb = 1.83Full permutation, n = 5: 6.91 bits, d²/Eb = 1.38Full permutation, n = 6: 9.49 bits, d²/Eb = 1.08Full permutation, n = 7: 12.30 bits, d²/Eb = 0.88Full permutation, n = 8: 15.30 bits, d²/Eb = 0.73Full permutation, n = 9: 18.47 bits, d²/Eb = 0.62Full permutation, n = 10: 21.79 bits, d²/Eb = 0.53Full permutation, n = 11: 25.25 bits, d²/Eb = 0.46Full permutation, n = 12: 28.84 bits, d²/Eb = 0.40Full permutation, n = 13: 32.54 bits, d²/Eb = 0.36Full permutation, n = 14: 36.34 bits, d²/Eb = 0.32Full permutation, n = 15: 40.25 bits, d²/Eb = 0.29Full permutation, n = 16: 44.25 bits, d²/Eb = 0.26 Multi-pulse PPM (w = n/2), n = 2: 1.00 bits, d²/Eb = 4.00Multi-pulse PPM (w = n/2), n = 3: 1.58 bits, d²/Eb = 4.75Multi-pulse PPM (w = n/2), n = 4: 2.58 bits, d²/Eb = 5.17Multi-pulse PPM (w = n/2), n = 5: 3.32 bits, d²/Eb = 5.54Multi-pulse PPM (w = n/2), n = 6: 4.32 bits, d²/Eb = 5.76Multi-pulse PPM (w = n/2), n = 7: 5.13 bits, d²/Eb = 5.98Multi-pulse PPM (w = n/2), n = 8: 6.13 bits, d²/Eb = 6.13Multi-pulse PPM (w = n/2), n = 9: 6.98 bits, d²/Eb = 6.28Multi-pulse PPM (w = n/2), n = 10: 7.98 bits, d²/Eb = 6.38Multi-pulse PPM (w = n/2), n = 11: 8.85 bits, d²/Eb = 6.49Multi-pulse PPM (w = n/2), n = 12: 9.85 bits, d²/Eb = 6.57Multi-pulse PPM (w = n/2), n = 13: 10.74 bits, d²/Eb = 6.65Multi-pulse PPM (w = n/2), n = 14: 11.74 bits, d²/Eb = 6.71Multi-pulse PPM (w = n/2), n = 15: 12.65 bits, d²/Eb = 6.78Multi-pulse PPM (w = n/2), n = 16: 13.65 bits, d²/Eb = 6.83 bits per codeword (log scale)d²min / EbPPMMulti-pulse PPMFull permutationn = 16n = 2PPMFull permutationMulti-pulse PPM (w = n/2)

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 n = 16 already carries over three times the bits of PPM for about 20% less distance per bit.

Choosing μ i \mu_i and m i m_i for a given n n and rate is an optimisation problem, and Slepian worked through it in the paper, along with what happens as n 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 m_i = 1 ), since optimising the integer m i 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 simplex optimiser with the energy fixed to 1.

The blunt approach gets expensive fast. For Variant II with n = 5 n = 5 there are 2 5 × 5 ! = 3840 2^5 \times 5! = 3840 codewords, so finding the minimum distance naively means 3840 2 ≈ 1.5 × 10 7 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 (n!)^2 .

Running enough of these optimisations, I fitted a rule of thumb for the best Variant II levels:

μ i ′ = ( i + 1 ) ( 1 + n + 1 9 ) − n + 1 10 , i = 0 , 1 , … , n − 1 , \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 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.

Keeping four of six codewords Looking straight down on the plane of the Variant I code in three dimensions. Left: the hexagon of six codewords with four kept, where the closest kept pair is still one hexagon side apart, a distance equal to the radius. Right: four points arranged as a square on the same circle, where the closest pair is the radius times the square root of two apart. closest pair: d = rclosest pair: d = √2 r Four corners of the hexagonA square(two orderings thrown away)(41% further apart)

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 of spacing electrons on a sphere), and against plain QAM. Variant II with n = 4 n = 4 gives log 2 ( 2 4 × 4 ! ) ≈ 8.6 \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. Optimum (maximum likelihood) detection means finding the codeword closest to 𝐫 \mathbf{r} . Done naively, that’s comparing 𝐫 \mathbf{r} against all M M codewords, and for n = 16 n = 16 with distinct levels that’s 16 ! ≈ 2 × 10 13 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 𝐱 1 \mathbf{x}_1 so that ∑ j r j x j \sum_j r_j x_j is as big as possible. The 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 m_k largest ones the level μ k \mu_k , the next m k − 1 m_{k-1} the level μ k − 1 \mu_{k-1} , and so on down.

That’s it! Detection is just sorting, 𝒪︀ ( n log n ) \mathcal{O}(n \log n) work instead of 𝒪︀ ( M ) \mathcal{O}(M) .

Detection by sorting Left: the received values 2.7, 0.8 and 2.2 in slots t1 to t3, noisy versions of the codeword [3 1 2]. Middle: ranking them gives slot t2 the lowest rank, then t3, then t1. Right: handing the levels out by rank gives back the codeword [3 1 2]. No thresholds are involved. t1t2t3lowest at the bottomt1t2t3 Received2.70.82.2Sortt2 → rank 1t3 → rank 2t1 → rank 3Codeword312

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 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 b bits we have an integer 0 ≤ B < 2 b ≤ n ! 0 \leq B < 2^b \leq n! , and the factorial number system (via the Lehmer code) gives a neat one-to-one map between integers below n ! n! and orderings. Every ordering is used at most once, and no table of n ! n! entries is needed.

Let’s write it out and give it a burl, for the all-distinct case:

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 B = 4 with levels [ 1 , 2 , 3 ] [1, 2, 3] gives the codeword [ 3 , 1 , 2 ] [3, 1, 2] . If it arrives as [ 2.7 , 0.8 , 2.2 ] [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 ] [3, 1, 2] , and that decodes to 4 4 . Scale the received values by 10 and add 5 and you get exactly the same answer.

As written this is 𝒪︀ ( n 2 ) \mathcal{O}(n^2) for the list pops, which can be brought down to 𝒪︀ ( n log n ) \mathcal{O}(n \log n) with a Fenwick tree, and for big n 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 𝒪︀ ( n log n ) \mathcal{O}(n \log n) , is there a scheme that gets 𝒪︀ ( n 1 + ϵ ) \mathcal{O}(n^{1+\epsilon}) ? My bet was graphs. A graph on r r vertices has ( r 2 ) \binom{r}{2} possible edges, so the number of graphs grows like 2 r 2 / 2 2^{r^2/2} , which makes n ! 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 M points in n n dimensions with energy at most 1, so every point sits in the unit ball, and say every pair is at least d d apart. Put a ball of radius d / 2 d/2 around each point. None of them overlap, and they all fit inside a ball of radius 1 + d / 2 1 + d/2 , so comparing volumes,

M ( d 2 ) n ≤ ( 1 + d 2 ) n ⟹ log 2 M ≤ n log 2 ( 1 + 2 d ) . 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 volume bound, nothing exotic.

The packing argument Codewords inside the unit circle (the power limit), each at least d from the others. Balls of radius d/2 around them never overlap, and all of them fit inside a circle of radius 1 + d/2. Comparing areas, or volumes in n dimensions, bounds how many codewords there can be. 1dPower limit: radius 1Balls of radius d/2 roundeach codeword never overlapDashed: radius 1 + d/2,which holds them allSo M (d/2)ⁿ ≤ (1 + d/2)ⁿHere: 19 codewords

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 n , the distance can shrink polynomially, d = n − c d = n^{-c} , and the bound gives

log 2 M ≤ ( c + o ( 1 ) ) n log 2 n . \log_2 M \leq (c + o(1))\, n \log_2 n.

So n log n n \log n is the ceiling, and permutation modulation is already in the top class. To get n 1 + ϵ n^{1+\epsilon} bits, you need log 2 ( 1 / d ) \log_2(1/d) to grow like n ϵ n^\epsilon , which means d ≲ 2 − n ϵ d \lesssim 2^{-n^\epsilon} , which means an SNR that grows exponentially in n n .

It’s the same story from Shannon’s side. The capacity of n n real dimensions is n 2 log 2 ( 1 + SNR ) \tfrac{n}{2}\log_2(1 + \text{SNR}) , and with an SNR that is polynomial in n n , that’s Θ ( n log n ) \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 n grows Best possible bits Example
Constant Θ ( n ) \Theta(n) QAM on every channel
Polynomial in n n Θ ( n log n ) \Theta(n \log n) Permutation modulation
Exponential in n n n 1 + ϵ n^{1+\epsilon} and up Graph modulation, if it existed

The SNR each growth rate needs The smallest SNR that Shannon's formula allows for carrying a given number of bits over n real dimensions, against n from 2 to 32. n bits needs a constant 4.8 dB. log2 n! bits, the permutation code's rate, needs an SNR that grows slowly, reaching 21 dB at n = 32. n(n - 1)/2 bits, graph modulation's edge count, needs an SNR that grows by about 3 dB per extra dimension, reaching 93 dB at n = 32. 02040608010028162432 n bits (QAM-like), n = 2: 2.0 bits need 4.8 dBn bits (QAM-like), n = 4: 4.0 bits need 4.8 dBn bits (QAM-like), n = 8: 8.0 bits need 4.8 dBn bits (QAM-like), n = 16: 16.0 bits need 4.8 dBn bits (QAM-like), n = 24: 24.0 bits need 4.8 dBn bits (QAM-like), n = 32: 32.0 bits need 4.8 dB log₂ n! bits (permutation), n = 2: 1.0 bits need 0.0 dBlog₂ n! bits (permutation), n = 4: 4.6 bits need 5.9 dBlog₂ n! bits (permutation), n = 8: 15.3 bits need 11.2 dBlog₂ n! bits (permutation), n = 16: 44.3 bits need 16.6 dBlog₂ n! bits (permutation), n = 24: 79.0 bits need 19.8 dBlog₂ n! bits (permutation), n = 32: 117.7 bits need 22.1 dB n(n−1)/2 bits (graph), n = 2: 1.0 bits need 0.0 dBn(n−1)/2 bits (graph), n = 4: 6.0 bits need 8.5 dBn(n−1)/2 bits (graph), n = 8: 28.0 bits need 21.0 dBn(n−1)/2 bits (graph), n = 16: 120.0 bits need 45.2 dBn(n−1)/2 bits (graph), n = 24: 276.0 bits need 69.2 dBn(n−1)/2 bits (graph), n = 32: 496.0 bits need 93.3 dB n (real dimensions)minimum SNR (dB)constantpolynomialexponentialn bits (QAM-like)log₂ n! bits (permutation)n(n−1)/2 bits (graph)

Permutation modulation’s n log n n \log n isn’t a way round Shannon, it is Shannon at an SNR that grows with n n . Remember from the distance section that the full permutation code’s d min d_\text{min} shrinks like n − 3 / 2 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 Θ ( r 2 ) \Theta(r^2) edge bits, would need r 2 ≲ n log n r^2 \lesssim n \log n , so r = 𝒪︀ ( n log n ) r = \mathcal{O}(\sqrt{n \log n}) vertices: it caps itself straight back to Θ ( n log n ) \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 E_8 lattice’s symmetry group sneak in), the biggest finite group of symmetries of ℝ n \mathbb{R}^n you can build from rational matrices has order 2 n n ! 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 Θ ( n log n ) 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 ∼ n − 3 / 2 d \sim n^{-3/2} , the packing bound allows about 3 2 n log 2 n \tfrac{3}{2} n \log_2 n bits, and Slepian’s code gets n log 2 n n \log_2 n . There’s half an n log 2 n 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 m time slots, each carrying one n 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 ! ) \log_2(m!) bits on top of the m log 2 ( n ! ) m \log_2(n!) :

bits = m log 2 ( n ! ) + log 2 ( m ! ) . \text{bits} = m \log_2(n!) + \log_2(m!).

Permuting codebooks across slots Four time slots, each carrying a four-level permutation codeword. Each slot uses a different generating word, labelled A to D, with its own set of levels. Which generating word goes in which slot (here C, A, D, B) is itself a permutation and carries log2 4! = 4.6 extra bits, on top of the ordering of levels inside each slot. slot 1slot 2slot 3slot 4 slot 1, codebook C, position 1: level 0.8slot 1, codebook C, position 2: level 0.35slot 1, codebook C, position 3: level 0.9slot 1, codebook C, position 4: level 0.45slot 2, codebook A, position 1: level 0.5slot 2, codebook A, position 2: level 1.0slot 2, codebook A, position 3: level 0.25slot 2, codebook A, position 4: level 0.75slot 3, codebook D, position 1: level 1.05slot 3, codebook D, position 2: level 0.85slot 3, codebook D, position 3: level 0.2slot 3, codebook D, position 4: level 0.4slot 4, codebook B, position 1: level 0.15slot 4, codebook B, position 2: level 0.7slot 4, codebook B, position 3: level 0.55slot 4, codebook B, position 4: level 0.95 Slot assignment (a permutation of the codebooks): C A D BCADBInside each slot: an ordering of that codebook's levels, log₂ 4! bits per slotAcross slots: which codebook goes where, another log₂ 4! bits per block

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 S n ≀ S m 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, in 𝒪︀ ( m 3 ) \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 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 10^{-3} ):

Slots Scheme Bits SNR at BER 10 − 3 10^{-3}
n = 4 n = 4 , m = 16 m = 16 Permutation code in each slot 64 13.9 dB
n = 4 n = 4 , m = 16 m = 16 Permuted codebooks 108 23.6 dB
n = 4 n = 4 , m = 16 m = 16 16-QAM 128 16.5 dB
n = 8 n = 8 , m = 8 m = 8 Permutation code in each slot 120 20.4 dB
n = 8 n = 8 , m = 8 m = 8 Permuted codebooks 135 22.5 dB

What the codebook layer costs Bits per 64-dimension block against the SNR needed for a bit error rate of 1e-3. At n = 4, m = 16, permuting codebooks takes the plain permutation code from 64 bits at 13.9 dB to 108 bits at 23.6 dB, while 16-QAM gets 128 bits at 16.5 dB. At n = 8, m = 8, it goes from 120 bits at 20.4 dB to 135 bits at 22.5 dB. 60801001201401214161820222426better ↖ n = 4, m = 16, Permutation code per slot: 64 bits at 13.94 dBn = 8, m = 8, Permutation code per slot: 120 bits at 20.41 dB n = 4, m = 16, Permuted codebooks: 108 bits at 23.61 dBn = 8, m = 8, Permuted codebooks: 135 bits at 22.51 dB n = 4, m = 16, 16-QAM: 128 bits at 16.48 dB SNR needed for BER 10⁻³ (dB)bits per 64-dim blockn = 4: 64 bitsn = 4: 108 bits, +9.7 dB16-QAM: 128 bitsn = 8: 120 bitsn = 8: 135 bits, +2.1 dBPermutation code per slotPermuted codebooks16-QAM

At n = 4 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 n . But the price falls quickly as n n grows, from 9.6 dB for the extra bits at n = 4 n = 4 to 2.1 dB at n = 8 n = 8 , and the theory says that for big n n you can have up to about n ! \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 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 n C 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 2^{R\, n \log n} , the same n log n 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.). The constant R R is only known to sit between 3 / 8 3/8 (Galaxy codes, 2025) and 1 / 2 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, under the name ‘rank modulation’ (A. Jiang, R. Mateescu, M. Schwartz and J. Bruck, “Rank Modulation for Flash Memories”, IEEE Transactions on Information Theory, 2009).

A flash cell stores data as an amount of charge, and conventional multi-level 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 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.

Push-to-the-top Four flash cells with charges in the order cell 2 highest, then cell 4, cell 1, cell 3. Pushing cell 3 to the top injects charge until it is above every other cell; it does not need to hit an exact level. The new order is cell 3, cell 2, cell 4, cell 1. cell 1cell 2cell 3cell 4cell 1cell 2cell 3cell 4 cell 1: rank 3cell 2: rank 1cell 3: rank 4cell 4: rank 2cell 1: rank 4cell 2: rank 2cell 4: rank 3 cell 3: rank 1 Before3142order: 2 > 4 > 1 > 3After pushing cell 34213order: 3 > 2 > 4 > 1push

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: 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 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, 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 M -ary FSK with permutation codes. Each codeword is a permutation of the M 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 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 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 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” (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 𝒪︀ ( n log n ) \mathcal{O}(n \log n) and parallelises well in hardware (sorting networks), 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 n , nothing can beat Θ ( n log n ) \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 𝐱 1 \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.