UFCFVK-15-2 Internet of Things 2022 Morse code :: Worksheet 2 (part 2)
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
UFCFVK-15-2 Internet of Things
2022
Morse code :: Worksheet 2 (part 2)
All work is handed in via git/GitLab and will require the skills demonstrated in this worksheet.
If you have not already done so, complete the setup process for you choice of OS, along with worksheet 1. Instructions for this are on Blackboard under Learning Materials.
For this worksheet you should create a new Git repo and all of your work should be pushed to there. Once you have completed the worksheet and pushed your work to Git you should submit the URL to
BB under assignments, worksheet 2.
You repo should contain the following:
• Complete the 2 tasks specified in this worksheet.
• All the Python source code for the worksheet.
• A README.md describing what you have completed, how to run the code, and some examples of each part working.
– This should be written in Markdown (hence the .md)
• Unit tests that test the functionality of your code.
Marking Scheme
• Each task is worth 25% and will include the following metrics:
– Correctness of solutions.
– Comments and overall quality of code.
• Finally,the remaining 25% will include the quality of the READMME.md, the use of Git, and other unspecified additions.
A binary heap is a heap data structure that takes the form of a binary tree. As defined on Wilipedia, or any book on algorithms, a binary specified as a binary tree with two additional constraints:[3]
• Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node’s children, according to some total order.
What is nice about binary heaps is that they are a complete binary tree, which means that all the trees nodes exist. A consequence of this is that in general a not a binary heap is reresented as nodes with pointers to the left and right children, but instead as an array. This leads to array style performance, although there is still potential caching issues, which can additionaly be avoided with implementation of radix trees, but this is beyond the scope of this module.
A binary heap can be respresented as an array (T) and assuming i is ith node, i.e. T[i], then:
• The root element will be at T[0].
• The left child is accessed with T[(2*i)]
• The right child is accessed with T[(2*i)+1]
In part 1 of the worksheet we saw that the decoding of Morse code can be implemented as a binary tree and clearly it is a complete binary tree, i.e. we assume that the input encodings, e.g. .. is the encoding for I. As such the Morse code tree can be implemented as a binary heap.
Note, depending on the mapping of encoded letters the binary tree might have a few empty chil- dren with respect to all parents having two children, in this case an empty child is inserted to make the tree complete.
Consider a subset of the morse tree:
Note that R’s right child is an empty node and would not appear in a valid path in a received message.
This can be represented as the string:
tree = "-ARWL-"
Assuming the current node is A, in the tree, then the remaining message .. would result in the letter L. The index for A is 1, thus by the rule given above when we see a . the left of A is T[(2*i)], i.e.:
tree[(2*1)]
which is
tree[2]
which evaluates to R, i.e. the node to the left of A. As the end of received message has not be reached, i.e. there is still a . to process, the index is update to the position of R, i.e. 2, and the process is reper- ated. Again a . is processed and thus the left of R is T[(2*i)], i.e.
tree[(2*2)]
which is
tree[4]
and evalulates to Land as there are no remaining input to process, the resulting transmited character is L.
Tasks
Use the same Git repo that you used for part 1.
Note part 1 and part 2 can share code, if you so choose, however, it is important that each task can be demonstrated on its own, and you should include tests to demostrate this, with details in
the README how to run them and so on.
Task 1
Implement the following function:
decode_bt(msg: str) -> str
which uses a binary heap for decoding morse messages.
Implement unit tests to validate your implementation.
Finally, to complete this task write a few paragraphs, in the README.md, discussing the differences between decoding more messages using the binary tree from part 1, the binary heap from this task, and a possible implementation using Python dictionaries.
Task 2
This task expores an extended version of Morse code used in Ham Radio conversations, as discussed here.
To begin with forward the following port from the remote development machine, using VS code:
• 10101
note, if you can’t rememeber how to forward ports, then you can refresh you memory by working through the first task in worksheet 2 part 1.
You can now open the following URLs in a browser locally on your machine.
The URL supports the notion of a sender and receiver for morse code, as seen in the following screen shot:
From this image note that the top to boxes allow a name for the sender and receriver to be entered, S1 and R1, respectively, in this case. The next box is the message to be transmitted and finally the morse code is the encoded message that is sent from the sender to the receiver. At the bottom of the page you can see the message has been translated, using the extended notation, and displays the sender, receiver, and the message content. But what is the extended notation?
To understand how the message is constructed you can use your decode function (or the morse code translator URL given in part 1). Feed in the message prouduced in the encoded message box, for the image above this is:
decode(".-. .---- -.. . ... .---- -...- .... .. -...- -.--.")
which will give the output string:
"r1des1=hi=("
If we refer to back to the URL given above for Ham radio conversations we see that a message from a sender to receiver is formated:
receiver de sender msg
where in this case the symbol = is placed before the message and =( after.
Write the following Python functions:
encode_ham(sender: str, receiver: str, msg:str) -> str
decode_ham(msg:str) -> (str, str, str)
The first takes a sender, receiver, and a text message and returns an encoded message of extended morse code. The second takes an encoded messages and returns a tuple, where the first element is the sender, the second is the receiver, and the third is the transmitted message.
Provide unit tests for these functions.
Task 3
For the final task you need to develop a program to talk to the extended morse server. This task com- bines all the things that you have done so far on practical side of this module.
Like the Echo server of worksheet 1 the extended morse server is implemented over a WebSocket, which on the development server is:
uri = "ws://localhost:10102"
The server provides two services:
• echo, sends back the message sent to the sender
• time, sends back the time
To send a message two echo you need to transmite a message of the form:
sender=s
receiver=echo
msg
in the formed by
encode_ham(s, 'echo', msg)
from task 2.
Similarly for time you need to transmite a mesage of the form:
encode_ham(s, 'time', 'hello world')
Once a message is sent to the server, the server will respond with a response.
Implement the following two functions:
send_echo(sender: str, msg: str) -> str
send_time(sender: str) -> str
The send_echo function sends an echo message to the server and returns the decoded message sent back from the server. Similarly the ‘send_timefunction sends a message, requesting the time, to the server and returns the decoded message sent back from the server.
Write unit tests for these new functions.
2023-06-30