Math 896 - Coding Theory
``Problem Set'' Problems from June 7, 2005

# 27

(a)

Let ${\mathcal C}= {\mathcal H}_{3,2}$ be the $[4,2,3]$ tetracode over ${\mathbb{F}}_3$ defined in Example 1.3.3 with generator matrix

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

Give the generator matrix of the code obtained from ${\mathcal C}$ by puncturing on the right-most coordinate and then extending on the right. Also determine the minimum weight of the resulting code.

(b)

Let ${\mathcal C}$ be a code over ${\mathbb{F}}_q$. Let ${\mathcal C}_1$ be the code obtained from ${\mathcal C}$ by puncturing on the right-most coordinate and then extending this punctured code on the right. Prove that ${\mathcal C}= {\mathcal C}_1$ if and only if ${\mathcal C}$ is an even-like code.

(c)

With ${\mathcal C}_1$ defined as in (b), prove that if ${\mathcal C}$ is self-orthogonal and contains the all-one code word ${\mathbf 1}$, then ${\mathcal C}= {\mathcal C}_1$.

(d)

With ${\mathcal C}_1$ defined as in (b), prove that ${\mathcal C}= {\mathcal C}_1$ if and only if the all-one vector ${\mathbf 1}$ is in $C^\perp$.

Solution:

(a)

Let ${\mathcal C}_1$ denote the code obtained by puncturing on the right-most coordinate and then extending this punctured code on the right. Then, by deleting the right most column of $G$ (call this matrix $G_1$) and then adding a column (on the right) to $G_1$ so that the rows sum to zero, we find that

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

is a generator matrix for ${\mathcal C}_1$. As $G_1$ is in standard form we have that

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

is a parity check matrix for ${\mathcal C}_1$. The first and second columns are linearly dependent and no 1 column is linearly dependent, so the minimum weight of ${\mathcal C}_1$ is 2 by Thm. 1.4.14.

(b)

By construction, every extended code (every code obtained from another by the extension method) is even-like. So ${\mathcal C}_1$ is even-like. Thus, if ${\mathcal C}= {\mathcal C}_1$, then ${\mathcal C}$ is even-like. Conversely, suppose ${\mathcal C}$ is even-like and let ${\mathbf x}\in {\mathcal C}$. Say, ${\mathbf x}= x_1x_2 \cdots x_n \in {\mathbb{F}}_q^n$. Since ${\mathcal C}$ is even-like, $x_1 + x_2 + \cdots + x_n = 0 \in {\mathbb{F}}_q^n$. So $x_n = -(x_1 + \cdots + x_{n-1})$. By first puncturing ${\mathbf x}$ and then extending, we have the codeword ${\mathbf x}' = x_1x_2 \cdots x_{n-1}y \in {\mathcal C}_1$ where $x_1 + x_2 + \cdots + x_{n-1} + y = 0 \in {\mathbb{F}}_q^n$ (by the extension construction). That is, $y = -(x_1 + \cdots + x_{n-1}) = x_n$. Thus, ${\mathbf x}= {\mathbf x}'$, so ${\mathbf x}\in {\mathcal C}_1$, and therefore ${\mathcal C}\subseteq {\mathcal C}_1$. Furthermore, for any ${\mathbf z}' \in {\mathcal C}_1$, there is a code ${\mathbf z}\in {\mathcal C}$ such that ${\mathbf z}$ punctured and then extended is ${\mathbf z}'$. Then by the same arguments, ${\mathbf z}' = {\mathbf z}$, so ${\mathcal C}_1 \subseteq {\mathcal C}$. Therefore, ${\mathcal C}_1 = {\mathcal C}$.

(c)

Suppose ${\mathcal C}$ is self-orthogonal and ${\mathbf 1}\in {\mathcal C}$. Since ${\mathcal C}$ is self-orthogonal, ${\mathbf x}\cdot {\mathbf y}= 0$ for all ${\mathbf x}, {\mathbf y}\in {\mathcal C}$. In particular, ${\mathbf x}\cdot {\mathbf 1}= 0$ for all ${\mathbf x}\in {\mathcal C}$. So $0 = {\mathbf x}\cdot {\mathbf 1}= x_1 + x_2 + \cdots + x_n$ for every ${\mathbf x}\in {\mathcal C}$. So ${\mathcal C}$ is even-like. Therefore, by part (b), ${\mathcal C}= {\mathcal C}_1$.

(d)

Suppose ${\mathbf 1}\in {\mathcal C}^\perp$. Then ${\mathbf x}\cdot {\mathbf 1}= 0$ for all ${\mathbf x}\in {\mathcal C}$. Therefore, $0 = {\mathbf x}\cdot {\mathbf 1}= x_1 + \cdots + x_n$ for all ${\mathbf x}\in {\mathcal C}$. Therefore, ${\mathcal C}$ is even-like and so by part (b), ${\mathcal C}= {\mathcal C}_1$. Conversely, if ${\mathcal C}= {\mathcal C}_1$, then by part (b), ${\mathcal C}$ is even-like. So $x_1 + x_2 + \cdots + x_n = 0$ for every ${\mathbf x}\in {\mathcal C}$. That is, ${\mathbf 1}\cdot {\mathbf x}= x_1 + \cdots + x_n = 0$. So, by definition, ${\mathbf 1}\in {\mathcal C}^\perp$.

# 29

Let ${\mathcal C}$ be the code of length 6 given by the generator matrix

$$G= \left[% \begin{array}{cccccc} 1 & 1 & 0 & 0 & 0 & 0 \\ ... ... & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ \end{array}% \right].$$

Give generator matrices of $({\mathcal C}^\bot)_{T_i}$ and $({\mathcal C}_{T_i})^\bot$ when $T_1 = \{1,2\}$ and $T_2 = \{1,3\}$.

Solution:
The code given by $G$ is

$${\mathcal C}= \{ 000000, 000011, 001100, 110000, 001111, 110011, 111100, 111111\}.$$

This means that

$${\mathcal C}(T_1) = \{000000,000011, 001100, 001111\}$$    and $$\quad {\mathcal C}(T_2) = \{000000, 000011\},$$

so

$${\mathcal C}_{T_1} = \{0000, 0011, 1100, 1111\}$$    and $$\quad {\mathcal C}_{T_2} =\{0000, 0011\}.$$

Hence ${\mathcal C}_{T_1}$ and ${\mathcal C}_{T_2}$ are given by the generator matrices

$$G_1 = \left[% \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 ... ...eft[% \begin{array}{cccc} 0 & 0 & 1 & 1 \end{array} \right],$$

respectively.

Now, ${\mathcal C}_{T_1}$ can be viewed as a direct sum of two 2-fold repetition codes, since the generator matrix $G_1$ can be written in block diagonal form, with the blocks equal to $[1 1]$. Thus, a parity check matrix for $G_1$ is also given in block diagonal form, where the blocks are parity check matrices for the 2-fold repetition code. However, $[1 1]$ is a parity check matrix for the 2-fold by example 1.2.2. Thus, ${\mathcal C}_{T_1}$ is self-dual and has a parity check matrix, $H_1$, equal to $G_1$.

Now, let

$$H_2 = \left[% \begin{array}{cccc} 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{array}% \right].$$

This is a parity check matrix for ${\mathcal C}_{T_2}$ because it has the correct size ( since $n=4$ and $k=1$), $H_2 \bf {x} = \bf {0}$ for each $\bf {x} \rm\in {\mathcal C}_{T_2}$, and now suppose $\bf {x} = \rm x_1 x_2 x_3 x_4 \in {\mathbb{F}}_2^4$ such that $H_2 \bf {x} = \bf {0}$. This means precisely that $x_3+x_4=0$, $x_2=0$, and $x_1=0$ by multiplying out, which means that $\bf {x}\rm = 0011$ or $0000$, so $\bf {x}$ is in ${\mathcal C}_{T_2}$.

By Exercise 4, $H_1$ and $H_2$ are generator matrices for $({\mathcal C}_{T_1})^\bot$ and $({\mathcal C}_{T_2})^\bot$ respectively.

Now, from $G$ we also have that a parity check matrix for ${\mathcal C}$ is $H = G$ because ${\mathcal C}$ is the direct sum of three 2-fold repetition codes, and by the same argument as above, $H$ is a block diagonal matrix with $[1 1]$ blocks. This means that $H = G$ is a generator matrix for ${\mathcal C}^\bot$. Thus, ${\mathcal C}= {\mathcal C}^\bot$, and so by the above work, $G_1$ and $G_2$ are generator matrices for ${\mathcal C}_{T_1}= ({\mathcal C}^\bot)_{T_1}$ and ${\mathcal C}_{T_2}= ({\mathcal C}^\bot)_{T_2}$, respectively.

#32

Prove that the generator and parity check matrices for the code obtained in the $(\mathbf{u}\mid\mathbf{u}+\mathbf{v})$ are $G=\begin{bmatrix}G_1 & G_1 \ 0 & G_2\end{bmatrix}$ and $H=\begin{bmatrix}H_1 & 0\\ -H_2 & H_2\end{bmatrix}$.

Solution:
Let $\mathcal{C}_1$ and $\mathcal{C}_2$ be $[n,k_1,d_1]$ and $[n,k_2,d_2]$ codes respectively, with $\mathcal{C}=\{(\mathbf{u},\mathbf{u}+\mathbf{v})\mid \mathbf{u}\in \mathcal{C}_1, \mathbf{v}\in\mathcal{C}_2\}$. The rows of $G$ are evidently in $\mathcal{C}$ since they are of the form $(\mathbf{u},\mathbf{u})$ or $(\mathbf{0},\mathbf{v})$ with $\mathbf{u}\in\mathcal{C}_1$ and $\mathbf{v}\in\mathcal{C}_2$. So the span of the rows is in $\mathcal{C}$. Given $(\mathbf{u},\mathbf{u}+\mathbf{v})$ in $\mathcal{C}$ we have $\mathbf{x}G_1=\mathbf{u}$ and $\mathbf{y}G_2=\mathbf{v}$ for some $\mathbf{x} \in {\mathbb{F}}_q^{n-k_1},\mathbf{y}\in\mathbb{F}_q^{n-k_2}$. Then the sizes of the matrices and vectors are such that

$$\begin{bmatrix}\mathbf{x} & \mathbf{y}\end{bmatrix}\begin{bmatrix... ..._2\end{bmatrix}=\begin{bmatrix}\mathbf{u} & \mathbf{u}+\mathbf{v}\end{bmatrix}.$$

So $\mathcal{C}$ is spanned by the rows of $G$.

A linear dependence relation on the rows of $G$ gives a dependence relation on the rows of $G_1$ since the only non-zero entries in the first $n$ columns of $G$ are the rows of $G_1$. Since the rows of $G_1$ are independent the relation on the rows of $G$ can not involve the first $k_1$ rows (the rows containing $G_1$). So the dependence can only involve the bottom $k_2$ rows. But this gives a dependence relation on the rows of $G_2$ since the only non-zero entries in the last $k_2$ rows of $G$ are the rows of $G_2$. Because the rows of $G_2$ are independent the only possible linear dependence relation on the rows of $G$ is trivial. So $G$ is a generator matrix for $\mathcal{C}$.

Notice that $H$ has size $((n-k_1)+(n - k_2)) \times (n+n) = (2n - (k_1+k_2)) \times (2n)$ which is the appropriate size for a parity check matrix of ${\mathcal C}$ (given that $G$ above is a generating matrix for ${\mathcal C}$). Let $\mathbf{u} \in {\mathcal C}_1$ and $\mathbf{v} \in {\mathcal C}_2$. Then

$$\begin{bmatrix}H_1 & 0\ -H_2 & H_2\end{bmatrix}\begin{bmatrix}\m... ...atrix}H_1\mathbf{u} \ -H_2\mathbf{u}+H_2(\mathbf{u}+\mathbf{v}) \end{bmatrix}.$$

Since $H_1$ and $H_2$ are parity check matrices for $\mathcal{C}_1$ and $\mathcal{C}_2$ we have

$$\begin{bmatrix}H_1\mathbf{u} \\ -H_2\mathbf{u}+H_2(\mathbf{u}+\m... ...H_1\mathbf{u} \ H_2\mathbf{v}\end{bmatrix}=\begin{bmatrix}0 \ 0\end{bmatrix}.$$

Thus $\mathcal{C}$ is contained in the kernel of $H$. If we have any vector in the kernel of $H$, write it as two vectors $\begin{bmatrix}\mathbf{x} & \mathbf{y}\end{bmatrix}$ where $\mathbf{x}$ is the first $n$ coordinates and $\mathbf{y}$ the last $n$ coordinates. Then

$$\begin{bmatrix}0\ 0\end{bmatrix}= \begin{bmatrix}H_1 & 0\ -H_2 ... ...trix} =\begin{bmatrix} H_1\mathbf{x}\ H_2(\mathbf{y}-\mathbf{x})\end{bmatrix}.$$

So $H_1\mathbf{x}=0$, hence $\mathbf{x}$ is in $\mathcal{C}_1$. Also $\mathbf{y}-\mathbf{x}$ is in the kernel of $H_2$, so $\mathbf{y}-\mathbf{x}$ is in $\mathcal{C}_2$. Therefore $\mathbf{y}=\mathbf{x}+\mathbf{v}$ for some $\mathbf{v}\in\mathcal{C}_2$. So if we let $\mathbf{u}=\mathbf{x}$ we have

$$\begin{bmatrix}\mathbf{x}\ \mathbf{y}\end{bmatrix}= \begin{bmatrix}\mathbf{u}\ \mathbf{u}+\mathbf{v}\end{bmatrix}.$$

So the kernel of $H$ is precisely $\mathcal{C}$. Thus $H$ is a parity check matrix.

# 33

Prove that the ( $\mathbf{u} \hspace{.1in}\vert \hspace{.1in} \mathbf{u}+\mathbf{v}$) construction using $[n,k_i,d_i]$ codes $C_i$ produces a code of dimension $k = k_1 + k_2$ and minimum weight $d = \min\{2d_1,d_2\}$.

Solution:
Suppose $\mathcal{C}$ is created using the $(\textbf{u}\;\vert\;\textbf{u}+\textbf{v})$ construction using $[n,k_i,d_i]$ codes $\mathcal{C}_i$. In $\char93 32$, we proved that $G$ (defined in $\char93 32$) is a generator matrix for ${\mathcal C}$. In particular, according to our convention, $G$ has full rank. Thus, the dimension of ${\mathcal C}$ is the number of rows of $G$ which is $k_1 + k_2$. Thus $k = k_1 + k_2$.

Let $H_1$ and $H_2$ be the parity check matrices for $C_1$ and $C_2$, respectively. Let $d$ denote the minimum weight of $C$. We show $d = \min\{2d_1,d_2\}$.

Recall that Corollary 1.4.14 gives us that a linear code has minimum weight $d$ if and only if its parity check matrix has a set of $d$ linearly dependent columns, and no set of $d-1$ linearly dependent columns.

For the ( $\mathbf{u} \hspace{.1in}\vert \hspace{.1in} \mathbf{u}+\mathbf{v}$) linear code, we have that the parity check matrix is given by

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

where $H_1$ and $H_2$ are the parity check matrices for the codes $C_1$ and $C_2$, respectively. For convenience, we introduce the block notation:

$$H = \begin{bmatrix}I & II \end{bmatrix},$$   where$$\hspace{.1in} I = \begin{bmatrix}H_1 \ -H_2\end{bmatrix}$$   and$$\hspace{.1in}II = \begin{bmatrix}0 \ H_2\end{bmatrix}$$

We make two observations:

• If there is a linearly dependent set of $j$ columns from block I of $H$, then there is a linearly dependent set of $j$ columns from $H_1$, and a linearly dependent set of $j$ columns from $H_2$.
• If there is a linearly dependent set of $j$ columns from block II of $H$, then there is a linearly dependent set of $j$ columns from $H_2$.
  

We consider four cases.

Case (i) $d_1=d_2$. In this case, there is a set of $d_2$ linearly dependent columns from the columns of $H_2$, and the corresponding columns of block II give a set of $d_2$ linearly dependent columns of $H$. Moreover, there is no linearly dependent set of fewer than $d_2$ columns from block II. Similarly, there is no linearly dependent set of fewer than $d_1$ columns from $H_1$; there is no linearly dependent set of fewer than $d_1$ columns from block I. For this reason, any set of columns from $H$ including fewer than $d_1$ columns from block I cannot be linearly dependent. Hence, $d_1=d_2$ is the smallest integer $z$ such that there is a set of $z$ linearly dependent columns from $H$, and no linearly dependent set with fewer than $z$ columns; $d = d_2 = d_1 < 2d_1$, implying $d = \min\{2d_1,d_2\}$ in this case.

Case (ii) $d_2 < d_1$. In this case, there is a linearly dependent set of $d_2$ columns from $H_2$, and no linearly dependent set of columns from $H_2$ with fewer than $d_2$ elements. Hence, there is a linearly dependent set of $d_2$ columns from block II of $H$, and no linearly dependent set of columns from block II of $H$ with fewer than $d_2$ elements. Now, since (via the first observation) any linearly dependent set of $z$ columns from block I implies the existence of a set of $z$ columns from $H_1$ that is linearly dependent, any linearly dependent set of columns from block I must have at least $d_1$ elements. Similarly, any set of columns from $H$ that includes columns from block I must contain at least $d_1$ columns from block $I$. Hence, $d_2$ is the smallest $z$ for which there is a set of $z$ linearly dependent columns from $H$ and no set of linearly dependent columns from $H$ contains less than $z$ elements. Thus, $d = d_2 < d_1 < 2d_1$, so $d = \min\{2d_1,d_2\}$.

Case (iii) $2d_1 < d_2$. In this case, there is a linearly dependent set of $d_1$ columns from $H_1$, say $\{i_1, \ldots, i_{d_1}\}$. Then the corresponding columns of $H$ taken with the same coefficients and the columns $i_{n+i_1}, \ldots, i_{n+i_{d_1}}$ of $H$ also with the same coefficients yields a linear equation summing to zero amongst $2d_1$ columns of $H$. Thus, $d \le 2d_1$. Now suppose $\mathcal{I} = \{i_1,\ldots ,i_s\} \subseteq \{1,\ldots ,2n\}$ is a minimal set of indices representing a linearly dependent set of columns from $H$ (that is, no fewer than $s$ columns are linearly dependent). Then $s \le 2d_1$ and $d = s$. Let $\mathcal{I}'$ be the indices of columns appearing in block I. Then $\mathcal{I}'$ must represent linearly dependent columns of $H_1$ and so must be empty or of at least of cardinality $d_1$. If $\mathcal{I}'$ is empty, then $\mathcal{I}$ represents a linear dependence on the columns of $H_2$ and so $s \ge d_2 > 2d_1$, a contradiction. Since $s < d_2$, the relation must be trivial on the columns of $H_2$. Since the relation is not trivial in block I, the relation on block I must be exactly countered on block II (otherwise there are nonzero coefficients on the columns of $H_2$). Thus, the relation has $s = 2\vert\mathcal{I}'\vert \ge 2d_1$ columns. Therefore, $d = s = 2d_1 < d_2$. So $d = \min\{2d_1,d_2\}$.

Case (iv) $d_1 < d_2 < 2d_1$. As there is a set of $d_2$ columns of $H_2$ which are linearly dependent, the corresponding $d_2$ columns of $H$ in block II are linearly dependent. So $d \le d_2$. Any nontrivial relation on the columns of $H$ which is nontrivial on the columns of $H_2$ must consist of at least $d_2$ elements. From the arguments of Case (iii), we have seen that any nontrivial relation on $H$ which is trivial on the columns of $H_2$ must have at least $2d_1 > d_2$ columns. Thus, any nontrivial relation on the columns of $H$ must have at least $d_2$ columns involved. Therefore, $d \ge d_2$. Therefore, $d = d_2 < 2d_1$, so $d = \min\{2d_1,d_2\}$.