Another formulation of error-correcting coding problem

Question

Consider classic error-correcting problem:

there is finite set $A$ and string $a_1...a_n$, $a_i \in A$ in the begin.

in the end we have $b_1...b_n$. Set places of errors $E = \{i| a_i\not= b_i \}$, $t = |E|$

We want to find algorithm that coding some string $c_1...c_k \to a_1...a_n$ and $b_1...b_n \to c_1...c_k$. We want $k/n, t/n \to$ max (I simplified some).

In classic case we don't know $E$ and I offer to consider error-correcting problem when we know it.

Has it been considered? What is relations between this problem and classic?

Answer 1

Here's a long comment that can't be put in the comment section:

If you know the location of errors in a binary system, and if errors are just bit flips, you can just flip those erroneous guys again. This ensures 100% error correction for obvious reasons. No coding theory involved. So it must be non-binary or erroneous bits become an illegal letter outside of the given alphabet.

Michael mentioned RAID5 in the comment. The error model for a RAID system is this latter kind, where a bit or digit may be flipped to a special symbol outside of the given legal letters. This kind of error is called an erasure. Here's a link to the Wikipedia article: http://en.wikipedia.org/wiki/Erasure_code.

Erasures are typically studied in the context of data storage, such as hard disks in a large server or optical media like Blu-rays. RAID Michael mentioned is a quintessential example of this. What it does is basically regard each disk as one (often non-binary) digit and encode them by a linear code. So, roughly speaking, you do the check-sum thing for the entire array of disks by seeing each node as one digit.

It might help grasp the concept if you imagine erasures as a "can't read" or "don't know what symbol" kind of error. If you come across a failed data section, you're sure it went wrong. But without any side information, you don't know if they were originally $0$, $1$, or whatever legal letter. It's just illegal data. So, you treat it as a special "can't read" section by assigning a special symbol "erasure" for this type of error.

The "located errors" you asked seem slightly different from erasures because you know which symbol each erroneous guy resulted in, although they can be corrected at least sub-optimally by optimal erasure codes. If there is a known pattern about errors (e.g., $0$ may become $1$, but $1$ never becomes $0$), knowing what symbol an erroneous bit resulted in may greatly help achieve a higher rate.

Of course, if you ask how much you can do better than traditionally studied channels, it all depends on exactly what kind of error model you consider. Since you didn't specify it, if we simply adopt the memoryless symmetrical channel, it's either trivial (i.e., the binary case of "just flip the wrong guy again") or the best possible rate is bounded from below by the capacity of the erasure channel. I don't know how large the gap in capacity is between the erasure channel and the located error channel.

There are many papers about erasures. And your textbook on coding theory may explain erasures well, too. But I haven't seen one that deals with the located error channel like you described.

Answer 2

What you are describing is a modification of the $q$-ary symmetric channel. As pointed out by Yuchiro in a previous answer, your problem is trivial when $q = 2$, meaning that if we have a binary alphabet, then knowing the position of the errors actually tells you what are the correct bits.

Suppose you have an alphabet $\{0,1,2\}$, of size $3$. The way you described you problem, if the symbol $0$ is sent, we can receive either $0$ or $1',2'$, i.e., we know whether the received symbol is wrong. The same happens for $1$ and $2$. Thus, the channel for your model can be described by the following graph:

(I am supposing that the transition probabilities are symmetric). Considering $y$ the output and $x$ the input, the transition matrix is $$P_{ij} = P(y = j |x = i) = \left( \begin{array}{cccccc} p_1 & 0 & 0 & 0 & p_2 & p_2 \\ 0 & p_1 & 0 & p_2 & 0 & p_2 \\ 0 & 0 & p_1 & p_2 & p_2 & 0 \\ \end{array} \right).$$ Maximizing mutual information gives you the capacity. I made a quick calculation and may be wrong, but I got that the capacity is

$$C = p_1 \log 3 + 2 p_2(\log 3 - 1) \mbox{ bits / channel use }$$. This makes a lot of sense, since if $p_1 = 1$ this is $\log 3$, a perfect channel, and if $p_1 = 0$, this is $\log 3 -1$, the capacity of a symmetric channel consisting only of the last three symbols $0', 1', 2'$ as output.

Now you should be able to generalize this for any $q$ with a little extra effort.

Thus, the answer to your question if this is "classic" is "yes", in the sense that you can achieve capacity doing Shannon type strategies (random coding, etc..) or even more modern stuff (e.g, polar codes). On the other hand, I don't think nobody considered the construction of practical codes for this specific channel (to the best of my knowledge).