# Error correction for windowed reads from cyclic tapes

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?

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

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.

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$$.

• 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? Mar 3 at 3:23
• @Moonwalker, I edited my answer to add a more efficient algorithm.
– D.W.
Mar 3 at 8:00
• @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.
– D.W.
Apr 19 at 23:39