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 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 = (a_ij) and B = (b_ij):

αA = (α · a_ij), A + B = (a_ij + b_ij), (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 .

 

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

0

• Calculate the matrix-vector multiplication B1.

4. Calculate the matrix-matrix multiplicationAB.
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

1   0   1 x1 1

 

where the variables x_i ∈ B.

1   0   1 x₃ 1

 

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

1 1

3. 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  = (a₁, . . . , a_n)^T  and b = (b₁, . . . , b_n)^T:

α · a₁ a₁ + b₁ 

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

 

.

α · a_n

.

a_n + b_n

 

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

For a set of vectors g₁, . . . , g_k in Bn, their linear combination with coefficients x₁, . . . , x_k

is

x₁g₁ + · · · + x_kg_k = ttx

where  tt =  g₁ · · · g_k and x = (x₁, . . . , x_n)^T. The linear span Span{g₁, . . . , g_k} 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 x₁, . . . , x_n is transmitted through a communication channel, and the outputs are bits y₁, . . . , y_n. As the channel is not reliable, y_i may not be the same as x_i. Here we consider the case that there exists at most 1 error, i.e., x_i = y_i 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 C_R 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, C_R 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 C_P of all the vectors of the form (a, b, a + b)^T is called the (3, 2) parity-check code:

 

C_P =



a

b

a + b

 .a, b ∈ B

 .

 

Suppose that the three channel outputs are y₁, y₂, y₃ when using the (3, 2) parity-check code.  If there is no errors,  y₁ + y₂  = y₃, and if there is one error,  y₁ + y₂  ƒ= y₃.  Under   the condition that at most one error occurs, we can check whether there exists an error by comparing y₁ + y₂ and y₃.  If y₁ + y₂ = y₃, we know there is no errors and the information bits are y₁ and y₂. 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,

C_P = Span

1   0

 

  1  1 

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

x₁ + x₂ + x₃ = 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 x₁, x₂, x₃, x₄. In addition to the 4 information bits, three more parity-check bits x₅, x₆, x₇ are transmitted when using the (7, 4) Hamming code:

x₅ = x₂ + x₃ + x₄

x₆ = x₁ + x₃ + x₄

x₇ = x₁ + x₂ + x₄. (5)

Please note that each of x₁, x₂, x₃ appears in two parity checks, and x₄ appears in all thae three parity checks.

Suppose that 7 bits y₁, . . . , y₇ 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 y_i in place of x_i.

• If all the three equalities hold, there exists no
• If exactly two equalities hold, one of the parity-check bits y₅, y₆, y₇is
• If exactly one equality holds, one of the bits y₁, y₂, y₃is wrong.  All the bits involved in the correct equation are
• If no equality holds, bit y₄is

Therefore, the (7, 4) Hamming code can correct one error. A codeword of the (7, 4) Hamming code is of the form

 

x₁ x₂ x₃

 x4  .

x₂ + x₃ + x₄ x₁ + x₃ + x₄ x₁ + x₂ + x₄

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

Question 3. Show that C_7,4 is a subspace of B7, and find a generator matrix where the first 4 rows form an identity matrix.

Question 4. Show that C_7,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 ∈ C_7,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 = h_j, 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 (2^m − 1, 2^m − m − 1) Hamming code,  where m  is a positive integer.   The parity check  matrix of a Hamming code is an    m × (2^m − 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.)

2. Prove that all the codewords of the (2^m− 1, 2^m − m − 1) Hamming code form a  (2^m − m − 1)-dimensional subspace of B2 −1.
3. (bonus) Write a Julia program to output a generator matrix tt  for  a  parity-check matrixH of a (2^m −1, 2^m −m−1) Hamming code, where tt is a (2^m −1)×(2^m −m−1) matrix, with the first 2^m − m − 1 rows being the identity
4. (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

原文

 

 

最先出自天才代写 Python代写服务    julia代写