MAT2040留学生讲解、辅导Linear Algebra、Python编程语言辅导、讲解Python
辅导Web开发|讲解留学生Prolo
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