1
$\begingroup$

I have been studying quantum error correction codes and as background, I am currently studying the theory of classical linear codes. Despite many efforts, I am unable to understand the following excerpt:

Any given parity check u divides Hamming space exactly in half,into those vectors which satisfy u and those that do not.Therefore,the 2^k vectors of a linear subspace in 2^n Hamming space can satisfy at most n−k linearly independent parity checks.These parity checks together form the parity check matrix H, which is another way to define the linear subspace.

$\endgroup$
1
  • $\begingroup$ Have you taken linear algebra? $\endgroup$ May 1 '20 at 7:52
1
$\begingroup$

Any given parity check $u$ divides Hamming space exactly in half, into those vectors which satisfy $u$ and those that do not.

Suppose your Hamming space is $X = \{0,1\}^n$. A non-zero parity check $u$ divides $X$ into two sets: $X_0 = \{ x \in X \mid \langle x,u \rangle = 0 \}$ and $X_1 = \{ x \in X \mid \langle x,u \rangle = 1 \}$. The two sets have equal size $2^{n-1}$.

Indeed, let $v$ be some non-zero vector such that $\langle u,v \rangle = 1$ (for example, $v$ could contain a single 1 entry, at some index in which $u$ also has a 1 entry). If $x \in X_0$ then $x + v \in X_1$, and conversely, if $x \in X_1$ then $x + v \in X_0$. Hence we can partition $X$ into pairs $(x,x+v)$ in which the first member is in $X_0$ and the second in $X_1$.

Here are two illustrating examples. If $u = (1,\underbrace{0,\ldots,0}_{n-1\text{ copies}})$ then $X_0$ consists of all vectors with 0 in the first coordinate, and $X_1$ consists of all vectors with 1 in the first coordinate. If $u = (\underbrace{1,\ldots,1}_{n \text{ copies}})$ then $X_0$ consists of all vectors with even parity, and $X_1$ consists of all vectors with odd parity.

Therefore, the $2^k$ vectors of a linear subspace in $2^n$ Hamming space can satisfy at most $n−k$ linearly independent parity checks. The statement here actually doesn't follow from the preceding statement. However, it is similar in spirit (and a generalization of the preceding statement). Earlier we have considered a single parity check $u$. We showed that if $u$ is non-zero, then the set $\{x \in X \mid \langle x,u \rangle = 0\}$ contains exactly half the space. If $u = 0$ then it consists of the entire space.

Now we are considering the common solutions of $m$ different vectors $u_1,\ldots,u_m$. The set $C = \{x \in X \mid \langle x,u_1 \rangle = \cdots = \langle x,u_m \rangle = 0\}$ contains at least $2^{n-m}$ vectors. If the vectors are linearly independent (this generalizes the condition $u \neq 0$), then $C$ contains exactly $2^{n-m}$ vectors. More generally, $C$ contains $2^{n-d}$ vectors, where $d$ is the dimension of the linear span of the vectors $u_1,\ldots,u_m$. I won't prove all these statements, but this is basic linear algebra.

If $C$ is a linear subspace containing $2^k$ vectors, and every element $x \in C$ satisfies $\langle x,u_1 \rangle = \cdots = \langle x,u_m \rangle = 0$, then the dimension of the span of $u_1,\ldots,u_m$ is at most $n-k$, per the discussion above. If we know that $u_1,\ldots,u_m$ are linearly independent, then the dimension of their span is $m$, and so $m \leq n-k$.

These parity checks together form the parity check matrix $H$, which is another way to define the linear subspace.

We can describe a linear code in two ways. One is using a generator matrix $G$: the linear code consists of all linear combinations of the rows. The other is using a parity check matrix $H$: the code consists of all vectors whose inner product with each row is 0. (Some books use rows, other columns.) Using our earlier notation, the rows of $H$ are just the vectors $u_1,\ldots,u_m$, where we insist that the vectors be linearly independent (the same holds for generator matrices).

Here is an example. Let $n = 3$, and consider the code whose generator matrix is $$ \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} $$ (We note that the same code has many generator matrices, and many parity check matrices.)

The code consists of all linear combinations of the rows: $$ \begin{matrix} 0 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix} $$ You can check that these are exactly the vectors with even parity. Hence a parity check matrix for this code (in this degenerate case, the unique parity check matrix) is $$ \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} $$ We can also treat this as a generator matrix of a code. The resulting code is known as the dual code (dual to the code for which this matrix functions as a parity check matrix).

$\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.