AATA Parity-Check and Generator Matrices

Section 8.3 Parity-Check and Generator Matrices

We need to find a systematic way of generating linear codes as well as fast methods of decoding. By examining the properties of a matrix

H

and by carefully choosing

H,

it is possible to develop very efficient methods of encoding and decoding messages. To this end, we will introduce standard generator and canonical parity-check matrices.

🔗

Suppose that

H

is an

m \times n

matrix with entries in

Z_{2}

and

n > m .

If the last

m

columns of the matrix form the

m \times m

identity matrix,

I_{m},

then the matrix is a canonical parity-check matrix. More specifically,

H = (A ∣ I_{m}),

where

A

is the

m \times (n - m)

matrix

(\begin{matrix} a_{11} & a_{12} & \dots & a_{1, n - m} \\ a_{21} & a_{22} & \dots & a_{2, n - m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m, n - m} \end{matrix})

🔗

and

I_{m}

is the

m \times m

identity matrix

(\begin{matrix} 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 1 \end{matrix}) .

🔗

With each canonical parity-check matrix we can associate an

n \times (n - m)

standard generator matrix

G = (\frac{I_{n - m}}{A}) .

🔗

Our goal will be to show that an

x

satisfying

G x = y

exists if and only if

H y = 0 .

Given a message block

x

to be encoded, the matrix

G

will allow us to quickly encode it into a linear codeword

y .

🔗

Example 8.23.

🔗

Suppose that we have the following eight words to be encoded:

(000), (001), (010), \dots, (111) .

🔗

For

A = (\begin{matrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix}),

🔗

the associated standard generator and canonical parity-check matrices are

G = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix})

🔗

and

H = (\begin{matrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{matrix}),

🔗

respectively.

🔗

Observe that the rows in

H

represent the parity checks on certain bit positions in a

6

-tuple. The

1

s in the identity matrix serve as parity checks for the

1

s in the same row. If

x = (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}),

then

0 = H x = (\begin{matrix} x_{2} + x_{3} + x_{4} \\ x_{1} + x_{2} + x_{5} \\ x_{1} + x_{3} + x_{6} \end{matrix}),

🔗

which yields a system of equations:

\begin{aligned} x_{2} + x_{3} + x_{4} & = 0 \\ x_{1} + x_{2} + x_{5} & = 0 \\ x_{1} + x_{3} + x_{6} & = 0 . \end{aligned}

🔗

Here

x_{4}

serves as a check bit for

x_{2}

and

x_{3};

x_{5}

is a check bit for

x_{1}

and

x_{2};

and

x_{6}

is a check bit for

x_{1}

and

x_{3} .

The identity matrix keeps

x_{4},

x_{5},

and

x_{6}

from having to check on each other. Hence,

x_{1},

x_{2},

and

x_{3}

can be arbitrary but

x_{4},

x_{5},

and

x_{6}

must be chosen to ensure parity. The null space of

H

is easily computed to be

\begin{array}{cccc} (000000) & (001101) & (010110) & (011011) \\ (100011) & (101110) & (110101) & (111000) . \end{array}

🔗

An even easier way to compute the null space is with the generator matrix

G

(Table 8.24).

🔗

Table 8.24. A matrix-generated code

Message Word $x$	Codeword $G x$
$000$	$000000$
$001$	$001101$
$010$	$010110$
$011$	$011011$
$100$	$100011$
$101$	$101110$
$110$	$110101$
$111$	$111000$

🔗

Theorem 8.25.

🔗

H \in M_{m \times n} (Z_{2})

is a canonical parity-check matrix, then

Null (H)

consists of all

x \in Z_{2}^{n}

whose first

n - m

bits are arbitrary but whose last

m

bits are determined by

H x = 0 .

Each of the last

m

bits serves as an even parity check bit for some of the first

n - m

bits. Hence,

H

gives rise to an

(n, n - m)

-block code.

🔗

We leave the proof of this theorem as an exercise. In light of the theorem, the first

n - m

bits in

x

are called information bits and the last

m

bits are called check bits. In Example 8.23, the first three bits are the information bits and the last three are the check bits.

🔗

Theorem 8.26.

🔗

Suppose that

G

is an

n \times k

standard generator matrix. Then

C = {y : G x = y for x \in Z_{2}^{k}}

is an

(n, k)

-block code. More specifically,

C

is a group code.

Proof.

Let

G x_{1} = y_{1}

and

G x_{2} = y_{2}

be two codewords. Then

y_{1} + y_{2}

is in

C

since

G (x_{1} + x_{2}) = G x_{1} + G x_{2} = y_{1} + y_{2} .

We must also show that two message blocks cannot be encoded into the same codeword. That is, we must show that if

G x = G y,

then

x = y .

Suppose that

G x = G y .

Then

G x - G y = G (x - y) = 0 .

However, the first

k

coordinates in

G (x - y)

are exactly

x_{1} - y_{1}, \dots, x_{k} - y_{k},

since they are determined by the identity matrix,

I_{k},

part of

G .

Hence,

G (x - y) = 0

exactly when

x = y .

🔗

Before we can prove the relationship between canonical parity-check matrices and standard generating matrices, we need to prove a lemma.

🔗

Lemma 8.27.

🔗

Let

H = (A ∣ I_{m})

be an

m \times n

canonical parity-check matrix and

G = (\frac{I_{n - m}}{A})

be the corresponding

n \times (n - m)

standard generator matrix. Then

H G = 0 .

Proof.

Let

C = H G .

The

i j

th entry in

C

\begin{aligned} c_{i j} & = \sum_{k = 1}^{n} h_{i k} g_{k j} \\ = \sum_{k = 1}^{n - m} h_{i k} g_{k j} + \sum_{k = n - m + 1}^{n} h_{i k} g_{k j} \\ = \sum_{k = 1}^{n - m} a_{i k} δ_{k j} + \sum_{k = n - m + 1}^{n} δ_{i - (m - n), k} a_{k j} \\ = a_{i j} + a_{i j} \\ = 0, \end{aligned}

where

δ_{i j} = {\begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases}

is the Kronecker delta.

🔗

Theorem 8.28.

🔗

Let

H = (A ∣ I_{m})

be an

m \times n

canonical parity-check matrix and let

G = (\frac{I_{n - m}}{A})

be the

n \times (n - m)

standard generator matrix associated with

H .

Let

C

be the code generated by

G .

Then

y

is in

C

if and only if

H y = 0 .

In particular,

C

is a linear code with canonical parity-check matrix

H .

Proof.

First suppose that

y \in C .

Then

G x = y

for some

x \in Z_{2}^{m} .

By Lemma 8.27,

H y = H G x = 0 .

Conversely, suppose that

y = (y_{1}, \dots, y_{n})^{t}

is in the null space of

H .

We need to find an

x

Z_{2}^{n - m}

such that

G x^{t} = y .

Since

H y = 0,

the following set of equations must be satisfied:

\begin{aligned} a_{11} y_{1} + a_{12} y_{2} + \dots + a_{1, n - m} y_{n - m} + y_{n - m + 1} & = 0 \\ a_{21} y_{1} + a_{22} y_{2} + \dots + a_{2, n - m} y_{n - m} + y_{n - m + 2} & = 0 \\ ⋮ \\ a_{m 1} y_{1} + a_{m 2} y_{2} + \dots + a_{m, n - m} y_{n - m} + y_{n - m + m} & = 0 . \end{aligned}

Equivalently,

y_{n - m + 1}, \dots, y_{n}

are determined by

y_{1}, \dots, y_{n - m} :

\begin{aligned} y_{n - m + 1} & = a_{11} y_{1} + a_{12} y_{2} + \dots + a_{1, n - m} y_{n - m} \\ y_{n - m + 2} & = a_{21} y_{1} + a_{22} y_{2} + \dots + a_{2, n - m} y_{n - m} \\ ⋮ \\ y_{n} & = a_{m 1} y_{1} + a_{m 2} y_{2} + \dots + a_{m, n - m} y_{n - m} . \end{aligned}

Consequently, we can let

x_{i} = y_{i}

for

i = 1, \dots, n - m .

🔗

It would be helpful if we could compute the minimum distance of a linear code directly from its matrix

H

in order to determine the error-detecting and error-correcting capabilities of the code. Suppose that

\begin{aligned} e_{1} & = (100 \dots 00)^{t} \\ e_{2} & = (010 \dots 00)^{t} \\ ⋮ \\ e_{n} & = (000 \dots 01)^{t} \end{aligned}

🔗

are the

n

-tuples in

Z_{2}^{n}

of weight

1 .

For an

m \times n

binary matrix

H,

H e_{i}

is exactly the

i

th column of the matrix

H .

🔗

Example 8.29.

🔗

Observe that

(\begin{matrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{matrix}) (\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) = (\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}) .

🔗

We state this result in the following proposition and leave the proof as an exercise.

🔗

Proposition 8.30.

🔗

Let

e_{i}

be the binary

n

-tuple with a

1

in the

i

th coordinate and

0

’s elsewhere and suppose that

H \in M_{m \times n} (Z_{2}) .

Then

H e_{i}

is the

i

th column of the matrix

H .

🔗

Theorem 8.31.

🔗

Let

H

be an

m \times n

binary matrix. Then the null space of

H

is a single error-detecting code if and only if no column of

H

consists entirely of zeros.

Proof.

Suppose that

Null (H)

is a single error-detecting code. Then the minimum distance of the code must be at least

2 .

Since the null space is a group code, it is sufficient to require that the code contain no codewords of less than weight

2

other than the zero codeword. That is,

e_{i}

must not be a codeword for

i = 1, \dots, n .

Since

H e_{i}

is the

i

th column of

H,

the only way in which

e_{i}

could be in the null space of

H

would be if the

i

th column were all zeros, which is impossible; hence, the code must have the capability to detect at least single errors.

Conversely, suppose that no column of

H

is the zero column. By Proposition 8.30,

H e_{i} \neq 0 .

🔗

Example 8.32.

🔗

If we consider the matrices

H_{1} = (\begin{matrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{matrix})

🔗

and

H_{2} = (\begin{matrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{matrix}),

🔗

then the null space of

H_{1}

is a single error-detecting code and the null space of

H_{2}

is not.

🔗

We can even do better than Theorem 8.31. This theorem gives us conditions on a matrix

H

that tell us when the minimum weight of the code formed by the null space of

H

2 .

We can also determine when the minimum distance of a linear code is

3

by examining the corresponding matrix.

🔗

Example 8.33.

🔗

If we let

H = (\begin{matrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{matrix})

🔗

and want to determine whether or not

H

is the canonical parity-check matrix for an error-correcting code, it is necessary to make certain that

Null (H)

does not contain any

4

-tuples of weight

2 .

That is,

(1100),

(1010),

(1001),

(0110),

(0101),

and

(0011)

must not be in

Null (H) .

The next theorem states that we can indeed determine that the code generated by

H

is error-correcting by examining the columns of

H .

Notice in this example that not only does

H

have no zero columns, but also that no two columns are the same.

🔗

Theorem 8.34.

🔗

Let

H

be a binary matrix. The null space of

H

is a single error-correcting code if and only if

H

does not contain any zero columns and no two columns of

H

are identical.

Proof.

The

n

-tuple

e_{i} + e_{j}

has

1

s in the

i

th and

j

th entries and 0s elsewhere, and

w (e_{i} + e_{j}) = 2

for

i \neq j .

Since

0 = H (e_{i} + e_{j}) = H e_{i} + H e_{j}

can only occur if the

i

th and

j

th columns are identical, the null space of

H

is a single error-correcting code.

🔗

Suppose now that we have a canonical parity-check matrix

H

with three rows. Then we might ask how many more columns we can add to the matrix and still have a null space that is a single error-detecting and single error-correcting code. Since each column has three entries, there are

2^{3} = 8

possible distinct columns. We cannot add the columns

(\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) .

🔗

So we can add as many as four columns and still maintain a minimum distance of

3 .

🔗

In general, if

H

is an

m \times n

canonical parity-check matrix, then there are

n - m

information positions in each codeword. Each column has

m

bits, so there are

2^{m}

possible distinct columns. It is necessary that the columns

0, e_{1}, \dots, e_{m}

be excluded, leaving

2^{m} - (1 + m)

remaining columns for information if we are still to maintain the ability not only to detect but also to correct single errors.

Prev Top Next