Classical and Quantum Error-Correcting Codes — Examples

The codewords are $000$ and $111$, and [L2] gives $d(C)=3$. For $x=(x_0,x_1,x_2)$, multiplication gives $Hx=(x_0+x_1,x_1+x_2)$, so $Hx=0$ exactly when $x_0=x_1=x_2$ and $\ker H=C$. The first two columns of $H$ form $\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]$, an invertible triangular matrix over $F_2$, so the rows of $H$ are independent. Therefore $H$ is a parity-check matrix by [L1]; the field operations are valid by [F1].

Direct multiplication gives the weight-at-most-one syndromes $s(000)=00$, $s(100)=10$, $s(010)=11$, and $s(001)=01$, all distinct. For $r=101$, [L3] gives $s(r)=Hr=(1+0,0+1)=11$, so the unique matching error is $e=010$ and $r-e=111$. The distinct syndromes give the one-error correction in [L4].

If coordinates $0,1$ are erased in $r=101$, the received value at coordinate $2$ is $1$, so $111$ is compatible and $000$ is not. More generally, two compatible codewords would differ only in $S$, so their distance would be at most $2<3$, contradicting [L4]. Hence $111$ is the unique completion.

If instead $000$ is sent, the two-bit error $e=110$ produces $r^{\mathrm{\prime }}=110$. Then $d_H(r^{\mathrm{\prime }},000)=2$ but $d_H(r^{\mathrm{\prime }},111)=1$, so $111$ is the unique radius-one decoding candidate. The unique-radius-one rule therefore miscorrects this word; [L4] gives no correction guarantee for the two-bit error.

The last four rows of $G$ form $I_4$, so its columns are independent and [L1] gives $\dim C=4$. The first three columns of $H$ form $I_3$, so for every $y\in F_2^3$ the input $(y_0,y_1,y_2,0,0,0,0)$ maps to $y$. Also, a linear combination of the rows of $H$ has its first three entries equal to its three coefficients, so the rows are independent and [F5] gives rank $3$. For $x=(a,b,c,d)$, $Gx=(a+b+d,a+c+d,b+c+d,a,b,c,d)$; applying the three rows of $H$ gives $(0,0,0)$. Thus $HG=0$ and $C\subseteq \ker H$.

The map $H:F_2^7\to F_2^3$ is onto by its first three columns, so [F3] gives $\dim \ker H=7-3=4$. The subspace $C$ also has dimension $4$ by step 1.1; [F4] now gives $C=\ker H$.

The columns of $H$ are $100,010,001,110,101,011,111$. They are all nonzero and pairwise distinct. A weight-one vector has syndrome one of these columns; a weight-two vector has syndrome the sum of two distinct columns, which is nonzero in characteristic two. Thus $C$ has no nonzero word of weight below $3$. The word $e_0+e_1+e_3$ has syndrome $100+010+110=000$ and weight $3$, so it lies in $C$ and $d(C)=3$.

Multiplying $H$ by the zero word and each unit vector gives $s(0000000)=000$, $s(1000000)=100$, $s(0100000)=010$, $s(0010000)=001$, $s(0001000)=110$, $s(0000100)=101$, $s(0000010)=011$, and $s(0000001)=111$; each nonzero value is the corresponding column of $H$. These eight syndromes are distinct, so [L3] guarantees unique correction of any one bit flip.

The map $(a,b)\mapsto (a,a+b,a+2b,a+3b)$ is injective because its first two coordinates recover $a$ and $b$. Hence the displayed $G$ has independent columns and [L1] gives $\dim C=2$.

Multiplication gives $HG=0$: the four row-column dot products are $10,10,10,20$, all zero in $F_5$. The first two columns of $H$, $(4,0)$ and $(3,3)$, are independent, so its column rank is $2$; [F5] makes its row rank $2$ as well.

If $b=0$ and $(a,b)\mathrm{\ne }(0,0)$, then $f(x)=a$ has no roots. If $b\mathrm{\ne }0$, the equation $a+bx=0$ has the unique solution $x=-a{b}^{-1}$, so at most one of the four distinct evaluation points is a root. Every nonzero codeword therefore has weight at least $3$, and $f(x)=x$ gives $(0,1,2,3)$ of weight $3$. Thus $d(C)=3$.

The columns of $H$ are $h_0=(4,0)$, $h_1=(3,3)$, $h_2=(2,4)$, and $h_3=(1,3)$. Their six pairwise determinants in $F_5$ are $2,1,2,1,1,2$, all nonzero, so no two are scalar multiples. A nonzero error $a{e}_j$ has syndrome $a{h}_j$; within one position distinct nonzero $a$ give distinct syndromes, and across positions equality would force proportional columns. Hence all $4\cdot 4=16$ nonzero one-symbol errors have distinct syndromes.

Therefore $C=\mathrm{im}G\subseteq \ker H$. By [F3], $\dim \ker H=4-2=2=\dim C$; [F4] gives $C=\ker H$.

For example, the error $e=2e_1$ has syndrome $2h_1=(6,6)=(1,1)$ in $F_5^2$. Since $d(C)=3$, [L3] gives unique one-symbol correction. The example uses the evaluation-code definition; its exact distance and syndrome claims above are proved here rather than inferred from a source formula.

From the standard pairing in [F1], $⟨e_i,e_j{⟩}_L={\sum }_{r<2}{\delta }_{ri}\overline{{\delta }_{rj}}={\delta }_{ij}$, so $e_0,e_1$ are orthonormal. Each physical factor is also $Q_2$ with this pairing; [F2] gives $⟨u_x,u_y{⟩}_P={\prod }_{k<3}{\delta }_{x_k{y}_k}$, and [F3] gives the ordered product basis. Thus $u_{000},u_{111}$ are orthonormal, and $V$ is isometric. For each basis vector $u_x$, [F5] gives $⟨e_i,V^{\ast }{u}_x{⟩}_L=⟨V{e}_i,u_x{⟩}_P$, which is $1$ for $(i,x)=(0,000)$ or $(1,111)$ and $0$ otherwise. Since $⟨e_i,y{⟩}_L=\overline{y_i}$, this computes $V^{\ast }{u}_{000}=e_0$, $V^{\ast }{u}_{111}=e_1$, and $V^{\ast }{u}_x=0$ for the other six basis strings. Thus $P=V{V}^{\ast }$ has exactly the stated diagonal entries and is the code projector in [L1] and [L2].

The map $E_X$ sends $u_{000}$ to $u_{100}$ and $u_{111}$ to $u_{011}$, both orthogonal to the code subspace by [F3]. Thus $P{E}_{X}P=0$, so $E_X$ is detectable with scalar $0$. By [F1] and [F4], its action on elementary tensors is $X\otimes I\otimes I$; hence it is supported on the first wire and has weight at most $1$.

The map $E_Z$ fixes $u_{000}$ and negates $u_{111}$. Thus $P{E}_{Z}P$ acts by eigenvalues $+1$ and $-1$ on the two-dimensional code subspace and is not a scalar multiple of $P$. By [F1] and [F4], it is $Z\otimes I\otimes I$, so it has weight at most $1$. It is non-detectable; every weight-zero operator is detectable by [L5]. Therefore the minimum non-detectable weight is $d=1$, and $\mathrm{wt}(E_Z)=d$.

By [L6], every operator of weight $<d=1$ is detectable; step 1.3 exhibits a non-detectable operator of weight exactly $d$. Thus the detection boundary is sharp, and no correction-map claim follows.