Asymmetric Multiple Error Correction

Question

In some non-volatile memories, errors are only affect one logic state (just 1->0). Is there a coding technique which could correct k asymmetric errors? I know that the BCH code could correct k random errors, but using the fact that the errors are asymmetric, I want to reduce the number of redundant bits.

Answer 1

There are codes designed precisely for such applications.

A so-called asymmetric distance function (which is itself symmetric but relevant!) plays a part, defined as $$\Delta(x,y)=d_H(x,y)+|w_H(x)-w_H(y)|$$ where $d_H$ and $w_H$ are the familiar Hamming weights. You have the usual bounds applied to this setup (Varshamov, Linear Programming, etc.) and constructions. A somewhat dated but nice tutorial by Klove is at http://www.ii.uib.no/~torleiv/rap95.pdf.

A good keyword for searching literature is 'unidirectional error correction' for coding constructions and the corresponding binary channel is called the $Z-$channel in information theory.

Interestingly, such a channel has positive zero error capacity, since if we call the top symbol $0$ and bottom symbol $1$, and let the Z shape denote the allowed channel transitions, with input symbols on the left, we have that $0\rightarrow 1$ is an impossible transition, and therefore any received $1$ symbol is noise free.