[nopilzva] correcting permutation errors in a rectangular array

radix-convert input data into base H! (H factorial), where H is a tunable parameter.  apply an error-correcting code whose alphabet size is H!.  (but I don't know of any code that works on alphabets of factorial size.)  let the output of the code be W characters long.

use a deck of W*H cards.  first, lay out cards in a canonical order in a rectangular grid of height H and width W.  encode a character by permuting cards within a column: each column has H! possible permutations, and each character comes from an alphabet of size H!.  encode the W-character message in the W columns.  after permuting, collect cards row by row.

transmit through a noisy channel, error model described below.

to decode, note that we know the cards which constituted each vertical column because the cards were first laid out in canonical order.  for each original column, examine the locations of its cards and extract its permutation.  hopefully the noisy channel hasn't caused cards to travel so far as to reorder a vertical permutation too frequently.  (collecting cards row by row was key.)  a card needs to get noisily moved a distance greater than W (or maybe W/2) for an error to occur.  the wider the row, the more robust.  because of the error correcting code applied on the first step of the encoding, we can correct some errors.

error model: inspired by kid shuffle (Wikipedia calls it Corgi shuffle or washing the cards).  each card tends to move to a position not too far from where it started.

we describe the error model working on finite list of numbers that starts out in order.  the numbers represent characters in the message.  intermediate data structure: array of FIFO queues.  array might need to support negative indices, so more abstractly a map from integers to FIFO queues.

go through the numbers, inserting number i to the queue at array index i+delta, where delta is an independent and identical distributed integer random variable.  if there is a collision, items accumulate in that queue.  maybe delta is uniform between 0 and deltamax, or -deltamax to +deltamax, or is a bell-shaped distribution.

process the intermediate data structure in order by array index.  easiest is to drain each queue in order.  other possibilities, no longer treating them as queues: randomly permute each queue, emitting the collisions in random order.  or (this is cool) recursively apply this random permutation algorithm to each queue.  probably a different deltamax.