1
$\begingroup$

I have an array of N symbols written on a cyclic tape. I read a sequence of M symbols starting from a random place on the tape. What error correcting scheme and even a coding scheme should I use for such "channel"?

Also will this problem be simpler if tape is not cyclic?

$\endgroup$
3
  • 1
    $\begingroup$ Do you want an optimal scheme or just something simple that's likely to work reasonably well in practice? $\endgroup$
    – D.W.
    Mar 2 at 3:08
  • $\begingroup$ @D.W. I need practical solution, which will be not so hard to implement. $\endgroup$
    – Moonwalker
    Mar 2 at 21:43
  • $\begingroup$ I'm thinking about using "start of the message" symbol with Reed–Solomon code. $\endgroup$
    – Moonwalker
    Mar 2 at 22:20
1
$\begingroup$

You mentioned in a comment that your messages are very short, only 7-10 bits long. Another option is to explicitly construct a code, with encoding and decoding done via a lookup table rather than by an algorithm or a formula.

For instance, suppose you have $K=7$-bit messages, that you will encode to a $N=30$-bit codeword that will be written onto the tape, and then you'll read $M=13$ bits starting from somewhere on the tape. Let $p(c)$ denote the set of $M$-bit sequences that could be read if $c$ was the codeword on the tape, i.e., $p(c)$ is the set of all $M$-bit sequences of $c$ (i.e., the $M$-bit prefixes of all cyclical shifts of $c$). Let $e(m)$ denote the encoding of the 7-bit message $m$; we'll construct $e$ below. Consider the following algorithm to choose a lookup table for $e$:

  1. Let $S := \emptyset$.

  2. For each $K$-bit message $m$:

    a. Pick $c$ randomly from all $N$-bit sequences such that $p(c)$ has no overlap with $S$.

    b. Let $e(m) := c$ and $S := S \cup p(c)$.

If the algorithm gets stuck, then go back to step 1 and restart. When this algorithm finishes, it will built up an encoder $e$, as a lookup table; you can then build up a decoder as follows:

  1. For each $K$-bit message $m$:

    • For each $s \in e(m)$, set $d(s) := m$.

One inefficient way to implement step 2a is with rejection sampling: pick $c$ randomly from $\{0,1\}^N$, compute $p(c)$, and check whether it has any intersection with $S$; if there's no intersection, then keep it, otherwise repeat with a new $c$. The probability that a randomly chosen $c$ is acceptable will be about $(1 - N / 2^{M-K})^N$ (or higher) in each step, so for some parameter choices this might be OK, but with others, it might be too slow.

Another (possibly faster) way to implement step 2a is to choose $c$ bit-by-bit. In more detail:

  1. For $i:=1,2,\dots,N$:

    • Pick $c_i$ randomly.

    • If $c_{i-M+1},\dots,c_{i-1},c_i \in S$:

      • Flip $c_i$. If $c_{i-M+1},\dots,c_{i-1},c_i \in S$, discard $c_1,\dots,c_i$ and go back to step 1, starting over from the beginning (starting with $i=1$).

A third way to implement step 2a, if $N$ is not too large, is to build a giant bitvector that stores the subset $T$ of $\{0,1\}^N$ of safe $N$-bit sequences, i.e., the subset $T = \{c \in \{0,1\}^N : p(C) \cap S = \emptyset\}$. Each time we add some value, call it $s$, to $S$ in step 2b, we can remove all $N$-bit values that contain $s$ as a substring from $T$. There will be $N \times 2^{N-M}$ such values to remove from $T$. Then, step 2a amounts to picking randomly from $T$. This will be inefficient if $N$ is large, though, and I'm not sure it has any advantages over the second way.

If you have a set value of $K$ and $N$, you'll probably have to experiment with different values of $M$ to see what is the smallest value for which you can construct an explicit code in this way.

$\endgroup$
1
$\begingroup$

I don't know if this problem has been studied, and I bet there will be better solutions, but I'll suggest a scheme that I suspect might work well enough, even if it's not optimal.

Naive approach: brute-force decoding

I would bet that any erasure code would work, if combined with brute-force decoding. For decoding, I am imagining that a naive algorithm is to enumerate all possibilities for what the starting point was, decode under that assumption, and check whether it leads to a correct reconstruction that is consistent with that assumption (i.e., all symbols you read match). Heuristically, I would expect that typically there will be only one decoding that is consistent with the observed data. This might be a bit slow -- decoding might take $O(MN)$ time for many codes, because of need to try all $O(N)$ possibilities for the starting point -- but if that's acceptable, it should be something that's easy to implement.

For instance, you could use a Reed-Solomon code. To encode a message, you treat it as a polynomial $p(x)$ of degree less than $M$ (say, of degree $M-1-\lg N$) over some finite field (i.e., the bits of the message determine the coefficients of $p(x)$). Then, you write $p(\alpha^i)$ in the $i$th position on the tape, for $i=1,2,\dots,N$ (where $\alpha$ is a fixed element of the finite field). For each guess at where the read symbols might have started from, you can decode using polynomial interpolation. The entire procedure will take $O(MN \log M)$ time, to decode.

Faster approach: rolling hash

Here is an alternative that should be me faster: it runs in linear time. I expect it will be close to optimal.

Encoding algorithm. Let $C$ be a small constant, to be chosen later. Let's suppose we have a message that is $M-C$ symbols long. We'll compute a Rabin-Karp rolling hash of the message, a hash that is $C$ symbols long, and append it to the message. Then, we'll repeat these $M$ symbols cyclically, to get a $N$-symbol word. That will be the codeword that is the encoding of the message. Encoding can be done in $O(N)$ time.

Decoding algorithm. Given an observed value $Y$ with $M$ symbols, we'll try all $M$ possibilities for cyclically shifting it to see which is correct. We can recognize when we have the correct shift because the last $C$ symbols will be the valid hash of the first $M-C$ symbols.

Naively, this decoding procedure would take $O(M^2)$ time. However, we can use the properties of the Rabin-Karp rolling hash to make decoding much more efficient. Let $H(x)$ denote the Rabin-Karp hash of $x$. Note that we can apply the Rabin-Karp rolling hash to $Y$ and learn $H(Y_{1..i})$ for each $i$; we can compute all $M$ of these hashes in $O(M)$ time. From $H(Y_{1..i-1})$ and $H(Y_{1..j})$, we can compute $H(Y_{i..j})$ in $O(1)$ time. Also, given two hashes $H(x_1)$ and $H(x_2)$, we can compute the hash $H(x_1||x_2)$ of the concatenation of $x_1$ and $x_2$ in $O(1)$ time. Thus, for any candidate cyclical shift of $Y$, we can compute the hash of the first $M-C$ symbols in $O(1)$ time, given the precomputed values $H(Y_{1..i})$, and thereby check whether this candidate shift is correct (by comparing that hash to the last $C$ symbols of the shifted value). This decoding algorithm does an initial $O(M)$-time precomputation to compute all of the $H(Y_{1..i})$ values, and then checks $M$ candidates, each of which takes $O(1)$ time, for a total decoding time of $O(M)$.

Choosing parameters. Lastly, I need to describe how we choose the constant $C$. I suggest choosing it so that it is very unlikely that any incorrect decoding will survive the hash-value check. Suppose each symbol is $b$ bits long. Then, a $C$-symbol hash is $bC$ bits long, and each incorrect candidate shift has a $1/2^{bC}$ chance of being wrongly accepted (by having the hash value match just by sheer chance). We test $M$ candidate shifts, so there is about a $M/2^{bC}$ chance that one of these is wrongly accepted. We might set as a goal that this chance should be at most $1/2^{50}$ (so that the chance of wrongly accepting an invalid message is less than the chance of being struck by lightning multiple times, and less than the chance of a cosmic ray hitting your computer and causing a bitflip error, i.e., negligibly small). This means we need $M/2^{bC} \le 1/2^{50}$, so it suffices to take $C = \lceil(50 + \lg M)/b \rceil$.

$\endgroup$
9
  • $\begingroup$ Thank you! I understood that with Reed-Solomon I actually don't need the "begin of the message" symbol, which is great! Also, can I somehow guess erasures or, better rely only on error correction? $\endgroup$
    – Moonwalker
    Mar 3 at 3:23
  • 1
    $\begingroup$ @Moonwalker, I edited my answer to add a more efficient algorithm. $\endgroup$
    – D.W.
    Mar 3 at 8:00
  • 1
    $\begingroup$ @Moonwalker, when you say "permutations", do you mean "cyclic shifts"? There are n! permutations but n cyclic shifts. After the decoder decodes, did you do the extra step to "check whether it leads to a correct reconstruction that is consistent with that assumption (i.e., all symbols you read match)"? One way to do that is decode, then re-encode and check that the result is the same as what you tried to decode. $\endgroup$
    – D.W.
    Apr 19 at 23:39
  • 1
    $\begingroup$ @Moonwalker, I added another answer as well. $\endgroup$
    – D.W.
    Apr 20 at 1:57
  • 1
    $\begingroup$ @Moonwalker, ok, well, it's always possible I have made a mistake or missed something. If you tried it and it doesn't work, maybe it just doesn't work. $\endgroup$
    – D.W.
    Apr 24 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.