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 codes1
2
3
4
5
6
7
8
9
10m=[[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.