MAT2040留学生代做、代写Linear Algebra、Python编程语言代写、代做Python代写

日期：2019-10-26 11:41

Binary Vector Spaces and Error Correcting Codes

MAT2040 Linear Algebra (2019 Fall)

Project 1

Project Instructions:

? Read the following text and answer the questions given in and after the text.

? For questions that need Julia, both codes and results should be reported. Besides,

codes need in .jl form or .ipynb form.

? If you are not familiar with bit operation in Julia you can refer to files ‘Julia instruction.ipynb’

or ‘Julia instruction.html’.

1 Binary Vector Spaces

1.1 Binary Matrices

The vector spaces introduced in our course have real/complex numbers as scalars, but the

concept of vector spaces can be extended to scalars that take only discrete values. The

simplest example is that scalars can only take binary values 0 and 1 (also known as bits)

with the following binary operations:

0 + 0 = 0 0 · 0 = 0

0 + 1 = 1 0 · 1 = 0

1 + 0 = 1 1 · 0 = 0

1 + 1 = 0 1 · 1 = 1 (1)

We can think of 0 and 1 as the logical values FALSE and TRUE, respectively, and hence

regard the addition as XOR and multiplication as AND. Note that ?1 = 1 for the above

algebra.

Let B = {0, 1}. With the addition and multiplication operations defined in (1), B is also

called a binary field. Same as the matrices/vectors defined over real numbers R, we can

similarly define matrices/vectors with entries in B, which are called binary matrices/vectors.

Matrix calculus can be defined with respect to the binary operations defined above: For

scalar α ∈ B and m × n binary matrices A = (aij ) and B = (bij ):

αA = (α · aij ), A + B = (aij + bij ), (2)

1

where the scalar addition and multiplication operations are defined in (1). Without otherwise

specified, all matrices and vectors in this document are binary with the operations

defined in (2).

Question 1. Consider binary matrices A and B over B:

1. For each value α ∈ B, evaluate the scalar-matrix multiplication αA.

2. Calculate A + A, A + B and B + B.

3. Calculate the matrix-vector multiplication B

4. Calculate the matrix-matrix multiplication AB.

5. Implement function of matrix addition and matrix-matrix multiplication in Julia.

Check the correctness by solving 2 and 4 in this question. (Hint: You can use the

similar function in homework 2)

For a binary matrix over B, Gaussian elimination can be applied similarly.

Question 2. 1. Solve the system of binary linear equations，

where the variables xi ∈ B.

2. Transform the following matrix to row echelon form and give the LU decomposition

of the following matrix:

3. Implement Gaussian elimination for a general binary matrix with Julia. Check the

correctness by solving 1) and 2) in this question.

Using row echelon form, we can also determine the solution types of system of binary

linear equations. (You do NOT need to answer following questions are for the project.)

What are the solution types of a general system of binary linear equations? What is the

difference compared with the systems of linear equations studied in our course?

2

1.2 Binary Vector Spaces

Denote the set of vectors of n binary entries as B

n

. We can define scalar multiplication

and vector addition similar to (2): For scalar α ∈ B and vectors a = (a1, . . . , an). (3)

We can verify that B

n

is a vector space (how?).

For a set of vectors g1, . . . , gk in B

n

, their linear combination with coefficients x1, . . . , xk

is

x1g1 + · · · + xkgk = Gx

where G =

g1 · · · gk

and x = (x1, . . . , xn)

T. The linear span Span{g1, . . . , gk} is a

subspace, and is also written as

Span{G} = {Gx : x ∈ B

k

},

where we call G the generator matrix of Span{G}. The concepts of linearly independence

and basis can be similarly defined for binary vector spaces.

2 Error Correcting Codes

As practical communication channels are all not reliable, error correcting codes are employed

to protect the information in communication. Suppose that a sequence of bits x1, . . . , xn is

transmitted through a communication channel, and the outputs are bits y1, . . . , yn. As the

channel is not reliable, yi may not be the same as xi

. Here we consider the case that there

exists at most 1 error, i.e., xi = yi for all but one i in {1, . . . , n}.

2.1 Repetition Coding

Using repetition coding, we repeat each information bit three times for communication.

For information 0, three bits 0, 0, 0 are transmitted through the channel; for information 1,

three bits 1, 1, 1 are transmitted through the channel. We can represent each channel input

binary sequence by a column vector, called a codeword, and we call the set CR of the two

codewords the binary 3-repetition code, i.e.,

This 3-repetition code can correct 1 error: the information bit must be the one appears

at least twice among the three channel outputs. For example, if (1, 0, 1)T is the sequence of

channel outputs, the information must be 1.

3

As one bit of information is transmitted by communicating 3 bits, we say the coding

rate of this code is 1/3.

Besides, CR is a subspace of B

as a basis.

2.2 Parity-check Coding

Let’s try to communicate two bits a and b by using the channel 3 times. The coding rate

is now 2/3, better than the 3-repetition code. In addition to the transmission of these two

information bits, parity-check coding further transmits a+b, which is called the parity check.

The collection CP of all the vectors of the form (a, b, a + b)

T is called the (3, 2) parity-check

code:

Suppose that the three channel outputs are y1, y2, y3 when using the (3, 2) parity-check

code. If there is no errors, y1 + y2 = y3, and if there is one error, y1 + y2 6= y3. Under

the condition that at most one error occurs, we can check whether there exists an error by

comparing y1 + y2 and y3. If y1 + y2 = y3, we know there is no errors and the information

bits are y1 and y2. Otherwise, we know there is an error, but we do not know where is the

error! Though this code cannot correct one error, it can always detect when there is an

error.

The codeword of this parity-check code can be written as a linear combination form:

Moreover, CP is the solution set of the binary linear equation

x1 + x2 + x3 = 0. (4)

The equation in (4) is called the parity-check equation of the (3, 2) parity-check code, and

can be written in the matrix form

2.3 Hamming Codes

A better use of parity checks can not only improve the rate, but also correct one error. Such

an example is the (7, 4) Hamming code, where 7 channel uses transmit 4 information bits.

Suppose that the four information bits are x1, x2, x3, x4. In addition to the 4 information

bits, three more parity-check bits x5, x6, x7 are transmitted when using the (7, 4) Hamming

code:

x5 = x2 + x3 + x4

x6 = x1 + x3 + x4

x7 = x1 + x2 + x4. (5)

Please note that each of x1, x2, x3 appears in two parity checks, and x4 appears in all thae

three parity checks.

Suppose that 7 bits y1, . . . , y7 are received, where at most one bit is different from the

corresponding input. For decoding the information bits, we verify the three parity-check

equalities in (5) with yi

in place of xi

.

? If all the three equalities hold, there exists no errors.

? If exactly two equalities hold, one of the parity-check bits y5, y6, y7 is wrong.

? If exactly one equality holds, one of the bits y1, y2, y3 is wrong. All the bits involved

in the correct equation are correct.

? If no equality holds, bit y4 is wrong.

Therefore, the (7, 4) Hamming code can correct one error.

A codeword of the (7, 4) Hamming code is of the form

Denote the collection of all the codewords of the above form as C7,4.

Question 3. Show that C7,4 is a subspace of B

7

, and find a generator matrix where the

first 4 rows form an identity matrix.

Question 4. Show that C7,4 is the solution set of the system of binary linear equations

Hx = 0 where

The matrix in (6) is called the parity-check matrix of the (7, 4) Hamming code. Note

that all the non-zero vectors in B

3 appears as the column of H exactly once. Suppose that

x ∈ C7,4 is transmitted and the received bits form the vector y. We can write that

y = x + e

where e is called the error vector with at most one non-zero entry.

To decode the Hamming code, we can calculate the syndrome s = Hy. As all the

codewords satisfy the linear equations Hx = 0, we have

s = H(x + e) = Hx + He = He.

If e = 0, we know s = 0. If e has the j entry nonzero, then s = hj , the jth column of H.

Therefore, by calculating the syndrome, we can identify the location of the error and hence

correct it.

Question 5. When y = (1, 1, 0, 1, 0, 0, 1)T

, what should x be if at most one error occurs?

Question 6. Implement a decoder algorithm for the (7, 4) Hamming code taking y as input

and giving x. Check the correctness of your algorithm by solving Question 5.

Besides the (7, 4) Hamming code, we have more general (2m ? 1, 2

m ? m ? 1) Hamming

code, where m is a positive integer. The parity check matrix of a Hamming code is an

m × (2m ? 1) binary matrix where each nonzero vectors in B

m appears exactly once in the

columns.

Question 7. 1. Write a Julia program to generate the parity check H for an input value

of m. (Note that H is not unique.)

2. Prove that all the codewords of the (2m ? 1, 2

m ? m ? 1) Hamming code form a

(2m ? m ? 1)-dimensional subspace of B

2m?1

.

3. (bonus) Write a Julia program to output a generator matrix G for a parity-check

matrix H of a (2m ?1, 2

m ?m?1) Hamming code, where G is a (2m ?1)×(2m ?m?1)

matrix, with the first 2m ? m ? 1 rows being the identity matrix.

4. (bonus) Give an algorithm to decode a general Hamming code, where at most one

error occurs. Prove the correctness of the algorithm and implement the algorithm

using Julia.

6