Introduction
Python代写两个程序，一个是CRC校验码的仿真器，另一个是Dijkstra算法。
CRC Simulation
In this part, you are going to implement a simulator of cyclic redundancy
check (CRC) code and test its performance. You can reuse parts of codes in Lab
2. The procedure is summarized as follows:
- Randomly generate an N-bit information stream. You need to set N=8 this time. (You can reuse the code in Lab 2.)
- Using the generator G=1001, generate the CRC bits and derive an (N+3)-bit coded stream. (Hint: implement long division in this step.)
- Send the coded stream into a random flipping channel with bit-flip probability p. You need to test three cases: p=0.1, p=0.05, and p=0.02. (You can reuse the code in Lab 2.)
- The receiver checks the received bits. (Hint: implement long division in this step). Then, there will be three possibilities:
A) None of the bits are flipped.
B) Some of the bits are flipped, and this is detected by the CRC.
C) Some of the bits are flipped, but this is not detected by the CRC. - Repeat the above procedure many times (e.g., 100000 or more). Find out the probabilities of A), B), and C).
To self-check if you have done correctly, you can check with the following
websites
Online CRC calculation
https://www.ghsi.de/CRC/
Binary to Decimal to Hexadecimal Converter
https://www.mathsisfun.com/binary-decimal-hexadecimal-converter.html
Questions
- Use your simulator to find out the simulated probabilities of A), B), and C) under p=0.1, p=0.05, and p=0.02.
- Compute the theoretical probabilities of A), B), and C), and compare them with your simulation results. (Hint: Please consider the error patterns divisible by 1001. Approximations can be made in this step, i.e., consider those “common” error patterns but ignore those “rare” error patterns.)
You need to submit your code in a separate file, using the name
Lastname_Firstname_CRC.py.
Dijkstra’s Algorithm
In this question, you will implement Dijkstra’s algorithm in Python and find
the shortest paths from one source node to any nodes in the network. There are
n nodes in the network. The edge lengths (costs) are represented by an n*n
matrix. The i-th row and j-th column of the matrix indicates the length (or
cost) from node i to node j. If there is no edge between node i and node j,
their length (cost) is set to be 65535. In Python, we use a two-dimensional
list to indicate the edge lengths (costs). For example, suppose n=3 (the
indices of the nodes are 0, 1, and 2), then we set
m=[[0,1,65535],[1,0,2],[65535,2,0]] to represent the following graph. The
lengths from node 0 to node 0, 1, and 2 are 0, 1, and 65535, respectively. The
lengths from node 1 to node 0, 1, and 2 are 1, 0, and 2, respectively. The
lengths from node 2 to node 0, 1, and 2 are 65535, 2, and 0, respectively.
Note that the length from node i to itself is 0, and the length from node i to
node j is equal to the length from node j to node i.
In the program, use Dijkstra’s algorithm to find the shortest distances from
an arbitrary source node to any nodes. (You do not need to use a heap to find
the minimum. It is acceptable to use min() to find the minimum in a list.) You
must use m, n, and v to denote the two-dimensional matrix, number of nodes,
and the index of source node respectively. m, n, and v must be assigned at the
beginning (i.e., first three lines) of your codes. Your output should be in
the following format [a0,a1,…,an-1], where a0,a1,…,an-1 denote the shortest
distances from the source node (v) to node 0, node 1, …, node (n-1).
Example:
Here come your Python codes
m=[[0,1,65535],[1,0,2],[65535,2,0]]
n=3
v=0
############
## Your code
## Your code
## Your code
## Your code
## Your code
############
—|—
Output: [0,1,3]
Reason: the shortest distances from node 0 (v) to nodes 0, 1, 2 are 0, 1, 3
respectively.
Warning: Your code will be tested against various test cases (under different
m, n, and v). You need to submit your code in a separate file, using the name
Lastname_Firstname_Dijkstra.py.
