julia代码案例 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 Besides,codes need in .jl form or .ipynb form.
Ifyou are not familiar with bit operation in Julia you can refer to files ‘Julia ipynb’ or ‘Julia instruction.html’.

Binary Vector Spaces and Error Correcting Codes
MAT2040 Linear Algebra (2019 Fall) Project 1
julia代码案例julia代码案例
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 Besides,codes need in .jl form or .ipynb form.
Ifyou are not familiar with bit operation in Julia you can refer to files ‘Julia 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)







where the scalar addition and multiplication operations are defined in (1). Without oth- erwise 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   0   1 1    0  1

A = 1   1  0 , B = 0 1 0 .


For each value α ∈ B, evaluate the scalar-matrix multiplicationαA.
CalculateA + A, A + B and B + B.
0

Calculate the matrix-vector multiplication B1.
Calculate the matrix-matrix multiplicationAB.
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

1   0   1 x1 1



where the variables xi ∈ B.

1   0   1 x3 1



Transform the following matrix to row  echelon form and give the LU decomposition  of the followingmatrix:
1 1

Implement Gaussian elimination for a general binary matrix with Julia. Check thecorrectness by solving 1) and 2) in this
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?



1.2 Binary Vector Spaces
Denote the set of vectors of n binary entries as Bn. We can define scalar multiplication and vector addition similar to (2):  For  scalar α B and vectors a = (a1, . . . , an)T and b = (b1, . . . , bn)T:

α · a1 a1 + b1 

αa =  .  , a + b =  .  . (3)



.

α · an

.

an + bn



We can verify that Bn is a vector space (how?).

For a set of vectors g1, . . . , gk in Bn, their linear combination with coefficients x1, . . . , xk

is

x1g1 + · · · + xkgk = ttx

where tt = g1 · · · gk and x = (x1, . . . , xn)T. The linear span Span{g1, . . . , gk} is a subspace, and is also written as

Span{tt} = {ttx : x ∈ Bk },

where we call tt the generator matrix of Span{tt}. 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.



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 B3 with

1

as a basis.







2.2 Parity-check Coding
 1 



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:



CP =



a

b

a + b

 .a, b ∈ B

 .



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 ƒ= 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:

 a  1 0

 b  = a 0 + b 1 .




Therefore,

CP = Span

1   0



  1  1 

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

Σ1   1   1Σ x = 0.




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
If exactly two equalities hold, one of the parity-check bits y5, y6, y7is
If exactly one equality holds, one of the bits y1, y2, y3is wrong.  All the bits involved in the correct equation are
If no equality holds, bit y4is
Therefore, the (7, 4) Hamming code can correct one error. A codeword of the (7, 4) Hamming code is of the form



x1 x2 x3

 x4  .

x2 + x3 + x4 x1 + x3 + x4 x1 + x2 + x4

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

Question 3. Show that C7,4 is a subspace of B7, 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

0 0

H = . (6) 1



The matrix in (6) is called the parity-check matrix of the (7, 4) Hamming code. Note that all the non-zero vectors in B3  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, 2m − 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 Bm 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.)

Prove that all the codewords of the (2m− 1, 2m − m − 1) Hamming code form a  (2m − m − 1)-dimensional subspace of B2 −1.
(bonus) Write a Julia program to output a generator matrix tt for  a  parity-check matrixH of a (2m −1, 2m −m−1) Hamming code, where tt is a (2m −1)×(2m −m−1) matrix, with the first 2m − m − 1 rows being the identity
(bonus) Give an algorithm to decode a general Hamming code, where at most oneerror occurs. Prove the correctness of the algorithm and implement the algorithm using
原文