New Codes from Old

In this section, we will learn about 5 new code constructions.

Direct Sum Method
Let $C_i$ be a $[n_i, k_i, d_i]_q$ code for $i = 1,2$. Define

$$C = C_1 \oplus C_2 = \{ (\textbf c_1, \textbf c_2) : \textbf c_1 \in C_1, \textbf c_2 \in C_2 \}$$

Example: 1.5.8 in book. Let

$$D = \{ 0 0, 1 1 \}$$

which is a $[2,1,2]_2$ code with generator matrix $[1, 1]$ and a parity check matrix $[1, 1]$. Then,

$$D \oplus D = \{ 0000, 0011, 1100, 1111 \}$$

is a $[4,2,2]_2$ code with generator matrix

$$\begin{bmatrix}1 & 1 & 0 & 0 0 & 0 & 1 & 1 \end{bmatrix}$$

and parity check matrix

$$\begin{bmatrix}0 & 0 & 1 & 1 1 & 1 & 0 & 0 \end{bmatrix}.$$

Theorem 1.5.1   Let $C_1$ be a $[n_1, k_1, d_1]$ code and $C_2$ be a $[n_2,k_2, d_2]$ code. Then $C_1 \oplus C_2$ is an $[n_1 + n_2, k_1 + k_2, \min \{ d_1, d_1\} ]_q$ code with generator matrix $$\begin{bmatrix}G_1 & 0 0 & G_2 \end{bmatrix}$$ and parity check matrix $$\begin{bmatrix}H_1 & 0 0 & H_2 \end{bmatrix}$$

The $(\textbf u : \textbf u + \textbf v)$ construction
Let $C_i$ be an $[n_i, k_i, d_i]_q$ code for $i = 1,2$. Then, define a new code as follows:

$$C = \{ (\textbf u, \textbf u + \textbf v) : \textbf u \in C_1, \textbf v \in C_2 \}.$$

If $C_i$ has generator matrix $G_i$ and parity check matrix $H_i$ for $i = 1,2$, then $C$ has the following generator and parity check matrices:

$$G = \begin{bmatrix}G_1 & G_1 0 & G_2 \end{bmatrix}$$

$$H = \begin{bmatrix}H_1 & 0 -H_1 & H_2 \end{bmatrix}$$

$C$ is a $[2n, k_1 + k_2, \min\{ 2d_1, d_2 \}]$ linear code.

Example: Let $C_1$ be a $[4,3,2]_2$ code with

$$G_1 = \begin{bmatrix}1 & 0 & 0 & 0 0 & 1 & 0 & 1 0 & 0 & 1 & 1 \end{bmatrix}$$

and $C_2$ a $[4,1,4]_2$ code with

$$G_2 = [ 1, 1, 1, 1 ]$$

Then, we can write out $C_1$:

$$C_1 = \{ 0000, 1000, 0101, 0011, 1101, 1011, 0110, 110 \}$$

$$C_2 = \{ 0000, 1111 \}$$

$$C = \{ 00000000, 00001111, 10001000, 10000111, \ldots \}$$

Note that $C$ is a $[8,4,4]_2$ code with

$$G = \begin{bmatrix}1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 0 & 1 & 0 & 1... ... 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}$$

Extending Codes
Let $C$ be an $[n,k,d]_q$ code. Then, define

$$\hat C = \{ x_1, \ldots, x_{n+1} \in \mathbb{F}_q^{n+1} : x_1 + \cdots + x_{n+1} = 0 \}$$

Our parity check matrix has the following form:

$$\hat H = \left[\begin{array}{ccc\vert c} 1 & \ldots & 1 & 1 \hline & & & 0 & H & & \vdots & & & 0 \end{array}\right]$$

This is our in-class exercise.

Example 1.5.4 in the book. Let $\mathcal{H}_{3,2}$ be a $[4,2,3]_3$ code with

$$G = \begin{bmatrix}1 & 0 & 1 & 1 0 & 1 & 1 & -1 \end{bmatrix}$$

$$H = \begin{bmatrix}-1 & -1 & 1 & 0 -1 & 1 & 0 & 1 \end{bmatrix}$$

$$\mathcal{H}_{3,2} = \{ (0,0,0,0), (1,0,1,1), (-1,0,-1,-1), (0,1,1,-1),$$

$$(0,-1,-1,1), (1,1,-1,0), (1,-1,0,-1), (-1,1,0,1) \}$$

$$\hat \mathcal{H}_{3,2} = \{ 0000, 10110, -10-1-10, 011-1-1, 0-1-111, -1-110 \}$$

$$\hat G = \begin{bmatrix}1 & 0 & 1 & 1 & 0 0 & 1 & 1 & -1 & -1 \end{bmatrix}$$

$$\hat H = \begin{bmatrix}1 & 1 & 1 & 1 & 1 -1 & -1 & 1 & 0 & 0 -1 & 1 & 0 & 1 & 0 \end{bmatrix}$$

So, $d = 3$.

From the book,

$$\hat d = \begin{cases}d, & d = d_e d+1, & d = d_o < d_e \end{cases}$$

Puncturing Codes
Let $C$ be an $[n,k,d]_q$ code. Let $T$ be a set of positions of size $t$.
For $t = 1$, say $T = \{ i \}$, then

$$C^T = \{ x_1, \ldots, \hat x_i, \ldots, x_n : x_1, \ldots, x_n \in C \},$$

so $C^T$ is a $[n-t, k^*, d^*]$ code (where $k^*$ and $d^*$ may not necessarily be $k$ and $d$, respectively).

Example: 1.55.2 in the book.
Let $C$ be a $[5,2,2]_2$ code with

$$G = \begin{bmatrix}1 & 1 & 0 & 0 & 0 0 & 0 & 1 & 1 & 1 \end{bmatrix}$$

Let $T_1 = \{ 1 \}$, $T_5 = \{ 5 \}$.

$$C = \{ 00000, 11000, 00111, 11111\}$$

$$C^{T_1} = \{ 0000, 1000, 0111, 1111 \}$$

$$C^{T_5} = \{ 0000, 1100, 0011, 1111 \}$$

Theorem 1.5.2   Assume that $\vert T\vert=1$. For a more general version, we can easily induct on the size of $T$.

(i)

If $d > 1$, $C^T$ is an $[n-1,k,d^*]$ where $d^* = d - 1$if $C$ has a minimum weight code word which is nonzero in the $i^{th}$ coordinate, $d^* = d$ otherwise.

(ii)

If $d = 1$, then $C^T$ is an $[n-1,k,1]$ code if $C$ has no code word of weight 1 whose nonzero entry is in coordinate $i$, otherwise, if $k > 1$, $C^T$ is an $[n-1, k-1, d^*]$ code with $d^* \geq 1$.

Example:

$$C = \{ 000, 001, 110, 111 \}$$

over $\mathbb{F}_2$. $C$ is a $[3,2,1]_2$ code with generator matrix

$$G = \begin{bmatrix}0 & 0 & 1 1 & 1 & 0 \end{bmatrix}$$

Dropping the first coordinate,

$$G_1 = \begin{bmatrix}0 & 1 1 & 0 \end{bmatrix}$$

So, $C^{T_1}$ is a $[2,2,1]_2$ code. Dropping the third coordinate,

$$G_3 = [ 1, 1 ]$$

$C^{T_3}$ is a $[2,1,2]_2$ code.

Shortening Codes
Assume $C$ is a $[n,k,d]_q$ code and $T$ is a set of $t$ positions. Define

$$C(T) := \{ \textbf c \in C : c_i = 0, \forall i \in T \}$$

Then, the shortened code $C_T$ is defined as

$$C_T := C(T)^T$$

Example:
Consider a code $C$ which is $[6,3,2]_2$ and

$$G = \begin{bmatrix}1 & 0 & 0 & 1 & 1 & 1 0 & 1 & 0 & 1 & 1 & 1 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}$$

$$H = \begin{bmatrix}1 & 1 & 1 & 1 & 0 & 0 1 & 1 & 1 & 0 & 1 & 0 1 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}$$

Let $T = {5,6}$.

$$C = \{ 000000, 100111, 010111, 001111, 110000, 101000, 011000, 111111 \}$$

$$C_T = \{ 0000, 1100, 1010, 0110 \}$$

Theorem 1.5.3   Let $C$ be a $[n,k,d]_q$ code and $T$ be a set of $t$ positions.

(i)

$(C^\perp)_T = (C^T)^\perp$ and $(C^\perp)^T = (C_T)^\perp$.

(ii)

If $t < d$, then $C^T$ and $C^\perp$ have dimensions $k$ and $n-t-k$, respectively.

(iii)

If $t = d$ and $T$ is the set of coordinates where a minimum weight codeword is nonzero, then $C^T$ and $(C^\perp)_T$ have dimension $k-1$ and $n-d-k+1$ respectively.

Wednesday, June 8 2004
Presenters: M. Stigge, B. Bockelman
Material: 1.6
For Lecture: 37
Problem Set: 35, 40, 41, 43

Exercise 27:

(a)

$C = \mathcal{H}_{3,2}$ is the $[4,2,3]_3$ code with

$$G = \begin{bmatrix}1 & 0 & 1 & 1 0 & 1 & 1 & -1 \end{bmatrix}.$$

Let $C_1$ be the code punctured on the right and then extended on the right.

$$G_1 = \begin{bmatrix}1 & 0 & 1 & 1 0 & 1 & 1 & 1 \end{bmatrix}$$

$$H_1 = \begin{bmatrix}-1 & -1 & 1 & 0 -1 & -1 & 0 & 1 \end{bmatrix}$$

From this, we can tell that $d = 2$.

(b)

$C$ an $[n,k,d]_q$ code. Let $C_1$ be punctured, then extended. Prove that $C = C_1$ if and only if $C$ is even-like.
For the forward direction, suppose $C = C_1$. As $C_1$ is even-like, then we get instantly that $C$ is even-like.
For the backwards direction, suppose that $C$ is even-like. Then, for all $\textbf x \in C$,

$$x_1 + \cdots + x_n = 0.$$

Therefore,

$$x_n = -(x_1 + \cdots + x_{n-1}).$$

Also, for $\textbf x' = (x_1, \ldots, x_{n-1}, y)$ where

$$x_1 + \cdots + x_{n-1} + y = 0$$

So we get

$$y = -(x_1 + \cdots + x_{n-1}) = x_n,$$

$$\textbf x = \textbf x' \in C_1$$

$$C \subset C_1.$$

On the other hand, suppose that $\textbf z' \in C_1$ and $\textbf z' = z_1, \ldots, z_{n-1}, q$. Then, there exists a $\textbf z \in C$ with $\textbf z = z_1, \ldots, z_n$. Hence, $\textbf z' = \textbf z \in C$ and $C_1 \subset C$. Thus, $C_1 = C$.

(c)

Suppose that $C \subset C^\perp$ and $\textbf 1 \in C$. Then,

$$\textbf x \cdot \textbf y = 0, \, \forall \textbf x, \textbf y \in C.$$

$$\textbf x \cdot \textbf 1 = 0, \, \forall \textbf x \in C$$

Thus,

$$0 = \textbf x \cdot \textbf 1 = x_1 + \cdots + x_n$$

for all $\textbf x \in C$, and $C$ is even-like. By (b), $C = C_1$.

(d)

Prove $C = C_1$ if and only if $\textbf 1 \in C^\perp$.
For the backwards direction, assume that $\textbf 1 \in C^\perp$. Then,

$$\textbf x \cdot \textbf 1 = 0, \, \forall \textbf x \in C$$

$$0 = \textbf x \cdot \textbf 1 = x_1 + x_2 + \cdots + x_n$$

Thus, $C$ is even-like and $C = C_1$.
For the forwards direction, $C = C_1$ so $C$ is evenlike and $x_1 + \cdots + x_n = 0$. Therefore, for all $\textbf x \in C$,

$$\textbf x \cdot \textbf 1 = 0$$

$$\textbf 1 \in C^\perp$$

Exercise 29:
Let $C$ be generated by

$$G = \begin{bmatrix}1 & 1 & 0 & 0 & 0 & 0 0 & 0 & 1 & 1 & 0 & 0 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$$

Let $T_1 = \{1,2\}$ and $T_2 = \{1,3\}$. Show that $(C^\perp)_{T_i} = (C_{T_i})^\perp$ for $i = 1,2$.

Exercise 32:
Prove that the generator and parity check matrices for the code $(u \vert u + v )$ are

$$G = \begin{bmatrix}G_1 & G_1 0 & G_2 \end{bmatrix}$$

and

$$H = \begin{bmatrix}H_1 & 0 -H_1 & H_2 \end{bmatrix},$$

respectively.

Exercise 33:
Prove that $(u \vert u + v )$ construction using $[n,k_i,d_i]$ codes $C_i$ produce dimensions $k = k_1 + k_2$ and $d_{min} = \min\{ 2d_1, d_2 \}$.