3
$\begingroup$

Does it make sense to have an error correction code which acts differently on different states (for example if we run something which runs on the binary string from $0^n \rightarrow 1^n$ involving all combinations, can we make it act biased towards the 1 states and not towards the 0 states)?

$\endgroup$
  • $\begingroup$ Could you be a little more specific? $\endgroup$ – nullgeppetto Nov 21 '13 at 13:14
  • 1
    $\begingroup$ If 0 means 'the machine is working' and 1 means 'the machine has broken down', then you would treat them asymmetrically. $\endgroup$ – Empy2 Nov 21 '13 at 14:15
  • $\begingroup$ For a better answer we probably need a bit more information: background, typical value of $n$, typical desired bias level, description of the type of error events that you cannot protect against with usual means. $\endgroup$ – Jyrki Lahtonen Nov 24 '13 at 17:06
1
$\begingroup$

I'm not sure that I understood your intention correctly. Typing this as an answer as it is too long for a comment.

This is easy, if we use a light to moderate memory convolutional code. It isn't at all difficult to make Viterbi decoding algorithm interpret the received symbols asymmetrically. For example as follows: a received $0$ is treated as something that truly is a $0$ with probability $p>1/2$, and a $1$ with probability $1-p$. We can also declare that a received $1$ truly is a $1$ with probability $q$ and, $0$ with probability $1-q$. Viterbi algorithm then gives you a maximum likelihood input sequence.

If $q>p$, then the algorithm treats $1$s as more certain than $0$s. Is this the kind of bias you had in mind?

A catch is that not all error-correcting codes are amenable to Viterbi decoding. With most convolutional codes this would not pose a problem. What we really need is a trellis representation of the code. In an earlier answer I try to describe, how to construct a trellis representation of a linear block code. For the best (in terms of minimum Hamming distance) known linear codes the resulting trellises tend to have a prohibitive complexity.

$\endgroup$
0
$\begingroup$

Most error correcting codes are designed for something like the Binary Symmetric Channel where there is equal chance of a 0 switching to a 1 or a 1 switching to a 0.

However, information theorists have considered channels that are not symmetric in this sense. I have been told that systems that are more likely to switch from a 1 to 0 than the other way around include flash memory and some optical communication systems. Some keywords to look up are "binary asymmetric channel" or "Z-channel".

If you search google or google scholar for "coding for asymmetric channel" you'll find a number of papers. Unfortunately I don't know anything about the techniques used.

$\endgroup$

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.