[icezjvtt] error-correcting permutation code based on adjacency

preprocessing: apply a traditional error correcting code to input data, resulting in a binary string of length n.

encoding: start with a deck of cards numbered and ordered 0 through n (n+1 cards).  we arrange the cards into a new deck, processing the binary string output from the preprocessing step one bit at a time.  the new deck starts with just card 0 from the old deck.  if the next input bit is 0, put the next card from the old deck on the top of the new deck.  if the next input bit is 1, put the next card on the bottom of the new deck.

error model: a small number of cuts.  (to cut, divide the new deck into two segments at a random point, then swap the segments.)  most cards remain next to their neighbors.

decoding: consider the values in order.  for each value, find it in the deck.  examine the values of its 2 neighbors in the deck (next and previous card).  if the 3 cards are monotonically increasing or decreasing, then that is consistent with the card having being placed on top or on bottom during encoding, so output the corresponding bit.  if neither, output an erasure.  then, apply ECC decoding to the resulting string of bits and erasures.

generalization:

things work in chunks of size b.  previously b=2.

preprocessing: radix-convert the message into base b! (b factorial), then apply an error correcting code of base b!.  (this is awkward because it is not a power of 2.  well-known codes are base 2, or base p^n where p is a prime, often 2.)  let the output of the ECC be n digits in base b!.

encoding: old deck of cards numbered 1 to n*(b-1).  initial partially built new deck: just the card number 1.  then, consider b-1 additional cards at a time, ordering them as follows with the partially built deck.  encode one base (b!) input digit from the preprocessed data as permutation of b items: the b-1 cards plus the rest of the partially built new deck treated monolithically as one object.

error model: same as before.  most chunks of size b are assumed to remain undamaged.

decoding: for each chunk of b-1 values, find them in the deck.  there should be at most 1 gap among them.  (if more, then this chunk is an erasure.)  examine the neighbors of the b-1 cards and determine if they are consistent with a permutation.  all the cards of the internal gap, in particular the neighboring cards at the extremities of the internal gap, should have values less than the those of the current chunk.  the external neighbors are larger.  if all consistent, output the number corresponding to that permutation; if not, output erasure.

52 card deck: log(52!)/log(2) = 225 bits absolute maximum encodeable in a permutation with no error correction.

b=2, no ECC preprocessing (this is a bad idea, but gives an upper bound): 51 bits.

b=3: (25*log(3!) + log(2!))/log(2) = 65 bits.

b=4: 17 chunks of 4! exactly because 17*3 = 51.  77 bits.

b=5: (12*log(5!) + log(3!))/log(2) = 85 bits .

as b gets larger, the assumption that most chunks of size b remain undamaged by the error model becomes less and less true.

previously: also error-correcting a permutation, but a different error model in which cards don't go very far from where they start.