2024-02-14

Classical Linear Codes

Definition: An [n,k] linear code $C$ uses n bits to encode k bits of information. n is generally greater then k. Kaufman encoding is a specific kind of [n,k] code. This can be specified by an $n\times k$ generator matrix, called $G$. The entries of $G$ are elements of the set $\{0,1\}$

Starting with a message source, we can see the figure below

> insert figure 1 here

In terms of linear algebra, we can represent x as the result of operating on u with $G$

$$x=Gu$$

Example: Three bit repetition code Generator matrix

$$G=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]⟹G[0]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]=\bar{0}(000)$$

What is $G[1]$

$$G[1]=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right][1]=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]=\bar{1}(111)$$

This is a [3,1] code in the [n,k] code format. 

Example 2: $[6,2]$ code

$$G=\left[\begin{array}{cc}1& 0\\ 1& 0\\ 1& 0\\ 0& 1\\ 0& 1\\ 0& 1\end{array}\right]G[0,0]=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\\ 0\\ 0\end{array}\right]$$ $$G[0,1]=\left[\begin{array}{c}0\\ 0\\ 0\\ 1\\ 1\\ 1\end{array}\right]G[1,1]=\left[\begin{array}{c}1\\ 1\\ 1\\ 1\\ 1\\ 1\end{array}\right]$$

There are $2^k$ code-words, each of length “n”. To describe any linear code, you need $n\cdot 2^k$ bits to describe. This adds up quickly.

Encoding with generator matrix is super simple and transparent.

After encoding, you can use a parity check matrix to detemine if an error occured.

Parity Check Matrix

• Equivalent formulation

$$Hx=0$$

This matrix is $n-k\ast =H;x=n$

$$Hx=0\text{ if there is no error}$$

Using linear independnce we can rewrite A as the following:

$$H=[A|I_{n-k}]$$

How to get from H→G

$$u=\left(\begin{array}{c}{u}_1\\ .\\ .\\ .\\ u_k\end{array}\right)$$ $$x=\left(\begin{array}{c}{x}_1\\ .\\ \\ .\\ .\\ x_m\end{array}\right)$$ $$Hx=[A|I_{n-k}]\left[\begin{array}{c}{x}_1\\ .\\ .\\ .\\ x_n\end{array}\right]=0$$ $$A\left[\begin{array}{cc}{x}_1& \\ .& \\ .& \\ .& \\ x_k& \end{array}\right]+\left[\begin{array}{c}{x}_{k+1}\\ .\\ .\\ .\\ x_k\end{array}\right]=0$$ $$⟸HG=0\{\begin{array}{l}Hx=0\\ x=Gu\end{array}$$

Why did we do this in the first place? Error correction!!

Parity operator “spits out” syndrome vector.

Error Correction

Current function

$$e=y-x=e_1\dots e_n$$

Encode

$$x=Gu$$

Figure out what H is for the $[6,2]$ code

Setting up for quantum error correction

• Hamming distance
  • Concept of “distance” which provides insight into error correction
  • Definition: Hamming distance between two vectors

$$x=x_1\dots x_m$$ $$y=y_1\dots y_m$$

Is the # of places where they differ.

Example:

$$d((1,0,1,1,1),(0,0,1,0,1))=2$$

Hamming weight of $x=x_1\dots x_m$ is the number of non-zero entries

Example:

$$W(1,0,1,1,1)=4$$

The hamming distance can be defined as :

$$d(x,y)=wt(x-y)$$

The stronger an error correction scheme is, the larger the hamming weight it can handle.