From Error Detection to Error Correction

Given a code $C$ and a set of error operators ${\color{red}{\cal E}}=\{{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} {\... ...rm 1\mskip-5mu l}}= {\color{red}E}_0,{\color{red}E}_1,{\color{red}E}_2,\ldots\}$ is it possible to determine whether a decoding procedure or subsystem exists such that ${\color{red}{\cal E}}$ is ``correctable'' (by $C$), that is, such that the errors in ${\color{red}{\cal E}}$ do not affect the encoded information? As explained below, the answer is yes and the solution is to check the condition in the following theorem:

$$% latex2html id marker 607\begin{minipage}[b]{6in}\textbf{... ...e that ${\color{red}E}_ix\not={\color{red}E}_jy$.\end{minipage}$$ (8)

Observe that the notion of correctability depends on all the errors in the set under consideration and, unlike detectability, cannot be applied to individual errors.

To see that the condition for correctability in Thm. 8 is necessary, suppose that for some $x\not=y$ in the code and some $i$ and $j$, we have $z={\color{red}E}_ix={\color{red}E}_jy$. If the state $z$ is obtained after an unkown error in ${\color{red}{\cal E}}$, then it is not possible to determine whether the original code word was $x$ or $y$, because we cannot tell whether ${\color{red}E}_i$ or ${\color{red}E}_j$ occurred.

To see that the condition for correctability in Thm. 8 is sufficient, we assume it and construct a decoding method $z\rightarrow \textrm{dec}(z)$. Suppose that after an unknown error occurred, the state $z$ is obtained. There can be one and only one $x$ in the code for which some ${\color{red}E}_{i(z)}\in{\color{red}{\cal E}}$ satisfies the condition that ${\color{red}E}_{i(z)}x=z$. Thus $x$ must be the original code word and we can decode $z$ by defining $x=\textrm{dec}(z)$. Note that it is possible for two errors to have the same effect on some code words. A subsystem identification for this decoding is given by $z\leftrightarrow i(z)\cdot \textrm{dec}(z)$, where the syndrome subsystem's state space consists of error operator indices $i(z)$, and the information-carrying system's consists of the code words $\textrm{dec}(z)$ returned by the decoding. The subsystem identification thus constructed is not necessarily onto the state space of the subsystem pair. That is, for different code words $x$, the set of $i(z)$ such that $\textrm{dec}(z)=x$ can vary and need not be all of the error indices. As we will show, the subsystem identification is onto the state space of the subsystem pair in the case of quantum information. It is instructive to check that, when applied to the examples, this subsystem construction does give a version of the subsystem identifications provided earlier.

It is possible to relate the condition for correctability of an error set to detectability. For simplicity, assume that each ${\color{red}E}_i$ is invertible. (This assumption is satisfied by our examples, but not by error operators such as ``reset bit one to $\mathfrak{0}$''.) In this case, the correctability condition is equivalent to the statement that all products ${\color{red}E}_j^{-1}{\color{red}E}_i$ are detectable. To see the equivalence, first suppose that some ${\color{red}E}_j^{-1}{\color{red}E}_i$ is not detectable. Then there are $x\not=y$ in the code such that ${\color{red}E}_j^{-1}{\color{red}E}_ix = y$. Consequently ${\color{red}E}_ix={\color{red}E}_jy$ and the error set is not correctable. This argument can be reversed to complete the proof of equivalence.

If the assumption that the errors are invertible does not hold, the relationship between detectability and correctability becomes more complicated, requiring a generalization of the inverse operation. This generalization is simpler in the quantum setting.