代写CLab、代写CMorse Code、代写c/c++Binary tree article on BTSmart

日期：2018-08-20 09:39

Lab 8 - Morse Code

22 Points

Warning

This lab is much more involved than the previous ones (it is similar in scope to

ToasterOven; conceptually more difficult, but less code), and will take you more time.

You will need to start early and read this lab carefully. Failure to plan is planning to fail.

Introduction

Morse code is a very old standard for communication, in which each character is a

combination of “dots” (short pulses) and “dashes” (longer pulse) that was used

extensively in the mid-1800’s onwards to connect towns and cities together. Proficient

operators could achieve rates of up to 40 words a minute on both transmission and

decoding.1

It is no longer widely used, but has some special applications in aviation and

maritime domains, and in assistive technology for people with movement disabilites.

In this lab, you will make a simple Morse decoder. The user presses a Morse sequence

using push buttons on the I/O Shield, and the signal will be decoded into Morse

characters, which will in turn be decoded into letters and numbers. Working

implementations of the OLED and Buttons libraries are provided for you. This lab builds

on your previous experience with event-driven programming and state machines.

Additionally, this lab uses a binary tree data structure to perform quick morse decoding.

You will write two recursive functions to build and verify a morse decoding binary tree.

Reading

• Morse code article on Wikipedia

• Binary tree article on BTSmart (Sections 1-4)

Concepts

• Pointers and malloc()

1 Note that there is an international standard timing for trained Morse operators that is much, much too

fast for you to be able to coherently test your code. In this lab we have slowed down the timings so that

you can ensure you are doing the right decoding. These are controlled via #defines within Morse.h, so

they could be changed once you are sure your code works correctly.

• Timers

• Finite state machines

• Abstract Data Type: Binary trees

• Recursion

Required Files:

• BinaryTree.c

• BinaryTreeTest.c

• Morse.c

• MorseTest.c

• Lab08_main.c

• README.txt

Provided files

• DO NOT EDIT these files:

o BinaryTree.h – This file declares an interface for creating and working with

binary trees. You will be implementing the corresponding BinaryTree.c file.

o Morse.h – This file contains the API that you will be implementing in the aptly

named Morse.c file. It will use a binary tree (Morse tree) to decode Morse code

strings. This library will entirely wrap the Buttons library AND the BinaryTree.h

library, such that Lab08_main.c will only needs to include Morse.h to do

everything related to Morse code functionality.

o BOARD.c/h – Standard library files for CMPE13.

o Lab8SupportLib.a (Buttons.h, Oled.h, OLED.h, OLED_driver.h, ascii.h) – These

files provide helper functions that you will need to use within your code. The

header files contain comments that should clarify how the code is to be used.

See Lab08 if you don’t remember how to use them.

• EDIT these files (included as *_template.c, you must rename them):

o BinaryTreeTest.c – provides a main() that is used for unit testing the BinaryTree

functions that you have coded. Just like in previous labs, you will need to code

your own test harness, and exclude it from the project when done testing.

o MorseTest.c – provides a main() that is used for unit testing Morse.c. Again, you

must write your own test harness.

o Lab08_main.c - This file includes main() template where you will integrate the

Morse.h functions into an event-driven Morse decoder.

• CREATE these files:

o BinaryTree.c

o Morse.c

Assignment requirements:

• Binary tree library: Implement the functions defined in BinaryTree.h in a corresponding

BinaryTree.c.

1. All functions must use recursion when traversing the tree.

2. Any constants used must be declared as an enum type or #defined.

3. There should be no printing except within the TreePrint() function.

4. All functions should only malloc() as much space as they need

5. All functions must check for null pointers and malloc() failures.

▪ You are NOT obligated to free() nodes if a malloc() failure occurs during

the creation of child nodes, but you should check for this failure and

avoid runtime errors.

• Binary tree test harness: Unit testing the implementation of functions defined in

BinaryTree.c/h.

1. Create a test harness that tests your BinaryTree functions and ensures that

they return the correct values. As always, tests should be thorough and

diverse.

2. Be very careful to test the functions on a non-existent tree (i.e: NULL).

• Morse code library: Implement all of the functions defined in Morse.h.

1. MorseInit() should create exactly one binary tree containing the Morse

decoding tree. MorseDecode() must use this tree to decode MORSE events.

▪ MorseDecode() should decode all alphanumeric characters,

representing alphabetic characters as only their upper-case

representation.

2. All constants and enums in Morse.h must be used and cannot be redeclared in

Morse.c.

▪ Any additional constants used must be declared as an enum type or

#defined.

3. MorseInit() and MorseDecode() are “wrappers” around the BinaryTree.h

library. MorseCheckEvents() is a wrapper around the Buttons.h library.

Lab08_main.c should NOT include Buttons.h or BinaryTree.h – only Morse.c

needs to include these libraries!

4. No user input/output should be done within this library. No printf()s, no OLED

functions.

• main(): Your main() within Lab08_main.c must implement the following functionality

using the provided code and your Morse code library.

1. Initialize the Morse decoder and check its return value, printing out an error

message calling FATAL_ERROR()2

if it fails.

2. Use Timer2's ISR to check for Morse events at 100Hz. The results of

CheckMorseEvents() should be returned to a module variable that is checked

in the main loop. Main() should never call CheckMorseEvents().

▪ Neither the Buttons.h library nor the BinaryTree.h library should be

#included or used directly within Lab08_main.c, as all necessary

functionality is entirely contained within the Morse library.

3. There should be no terminal input or output in your submitted program.

4. Build 3 helper functions within Lab08_main.c:

▪ OledAddToTopLine() – When MORSE_DOT or MORSE_DASH events are

generated, it prints that symbol onto the top line.

▪ OledClearTopLine() – When NEW_LETTER, NEW_WORD, or ERROR

events are received, it should clear the top line.

▪ OledUpdateBottomLine() -- Appends new characters onto the bottom

line (line 2). When CHAR_DECODED events are received, it should

append the decoded char to line 2. When NEW_WORD events are

received, it should append an empty space character (after the

decoded character, of course). When ERROR events are received, it

should append a BAD_CHAR character.

5. In your main loop, poll for MorseEvents set by MorseCheckEvents.

▪ Some MorseEvents require action prior to the Detected events should

be sent to appropriate Oled helper functions. MorseDecode() can also

generate MorseEvents, which should also be sent to appropriate Oled

helper functions.

6. The user can input DOTs and DASHs by varying how long they press down BTN4

to specify the Morse code representation of an alphanumeric character. These

are shown on the bottom line of the OLED as they're entered.

7. If the button is unpressed for more than 1 second,

3

it signals the end of

decoding an alphanumeric character. If the button is pressed again, the

current character should be decoded and the top line cleared.

8. If the button continues to be unpressed for an additional second (2 seconds

total),

4

the current character should be decoded and the top line cleared while

also adding a space after the character.

9. malloc() (or calloc()) will be used in this lab to generate the Morse tree, so

add a comment to your README.txt file indicating the necessary heap size for

correct program functionality.

2

FATAL_ERROR() is defined in Board.h

3 This is #defined in Morse.h as ticks of the 100Hz timer, MORSE_LETTER_TIMEOUT

4 This is also #defined in Morse.h as MORSE_WORD_TIMEOUT

• Code style: Follow the standard style formatting procedures for syntax, variable names,

and comments.

• Readme: Create a file named README.txt containing the following items. Note that

spelling and grammar count as part of your grade so you'll want to proof-read this

before submitting. This will follow the same rough outline as a lab report for a regular

science class. It should be on the order of three paragraphs with several sentences in

each paragraph.

1. First you should list your name and the names of anyone else who you have

collaborated with.5

2. In the next section you should provide a summary of the lab in your own

words. Highlight what you thought were the important aspects of the lab. If

these differ from how the lab manual presents things, make a note of that.

3. The following section should describe your approach to the lab. What was your

general approach to the lab? Did you read the manual first or what were your

first steps? What went wrong as you worked through it? What worked well?

How would you approach this lab differently if you were to do it again? Did you

work with anyone else in the class? How did you work with them and what did

you find helpful/unhelpful?

4. The final section should describe the results of you implementing the lab. How

did it end up finally? How many hours did you end up spending on it? What'd

you like about it? What did you dislike? Was this a worthwhile lab? Do you

have any suggestions for altering it to make it better? What were the hardest

parts of it? Did the points distribution for the grading seem appropriate? Did

the lab manual cover the material in enough detail to start you off? Did

examples or discussions during class help you understand this lab or would

more teaching on the concepts in this lab help?

Grading

This assignment is worth 22 points. 23 points are possible, giving a 1 point cushion:

• 13 -- Automated tests:

o 5 - BinaryTree:

▪ 2.5 – BinaryTreeCreate() creates a correct binary tree

▪ 1.0 – BinaryTreeCreate() correctly handles malloc() failures at all

levels

▪ 0.5 – BinaryTreeCreate() allocates the correct amount of memory

o 7 – Morse:

5 NOTE: collaboration != copying. If you worked with someone else, be DETAILED in your description of

what you did together. If you get flagged by the code checker, this is what will save you.

▪ 1 -- MorseInit() creates a correct binary tree.

▪ 2 -- MorseDecode() returns correctly decoded chars on valid

Morse sequences

▪ 1 – MorseDecode() reports errors correctly

▪ 2 – MorseCheckEvents() correctly detects DOTs and DASHes

▪ 1 – MorseCheckEvents() correctly detects NEW_LETTERs and

NEW_WORDs.

• 10 - Human Component:

o 1.0 – BinaryTreePrint() prints a binary tree correctly.

o 1.0 – MorseCheckEvents() countdown timers are implemented correctly.

o 1.0 – BinaryTreeTest.c

o 1.0 – MorseTest.c

o 3.0 – Lab08_main.c:

▪ 3 points: OLED screen displays correct information and reacts

appropriately to user input

• Shows sequence of dots and dashes on top line

• Clears top line after decoding is complete

• Appends decoded characters, spaces, and error symbols to

bottom line

o 1.5 – Code style

o 1.5 – README

• Deductions:

o 0 points for any file that does not compile! Be sure to submit early!

o – 1 IO from any module function (besides BinaryTreePrint())

o 0 points for any BinaryTree() functions that do not use recursion

o – 2 for nonreactive code

▪ blocking code

▪ code that runs continuously in the main loop (besides event

polling)

o – 1 for any compiler warnings

o – 1 for including Buttons.h or BinaryTree.h in Lab08_main.c

o Other deductions at grader’s discretion

Morse tree

Morse code is a representation of the standard English alphabet via a sequence of dots

and dashes. Because there can only be dots and dashes for representing a single

character, a binary tree can store the patterns for all the characters that can be encoded

by Morse code. While there are Morse code representations for many characters in

many languages, this lab focuses on only the alphanumeric characters within the ASCII

character set. A Morse tree with those characters in them is shown above.

To decode a Morse string (that is, a sequence of dots and daashes), you traverse the

tree starting at its root. With each new character, you move either right or left, until all

the characters have been read. The node that you end up at is the character that the

Morse string represented.

For example, to decode "-.." you first start at the root node. The first character in the

Morse string is a dash, so you branch to the right to the “T” node. The next two

characters are then both dots and so you branch left twice going through the “N” node

and ending on 'D', which is the alphanumeric character represented by the Morse string

'-..'

Note that not all nodes correspond to characters. A Morse string that maps to an

empty node is not a valid Morse string. Also, any Morse string longer than 5 dots

or dashes does not map to any location on the tree, so these are also not valid

Morse strings.

The function MorseInit() is where you will initialize your own Morse tree. You

should represent empty nodes with a non-alphanumeric character that you choose that

signifies an invalid Morse string. You will also need to extend some of the leaves of the

tree. These new leaves should also use an invalid-Morse-string character.

Binary trees

A binary tree is a common data structure used in programming. The term "binary"

refers to the number of children allowed for each node, in this case 2 (ternary trees are

also common and they have 3 children per node).

The binary tree library that you will implement stores a single character in each node

within the tree and only allows for perfect binary trees. Perfect binary trees are trees in

which all levels of the tree are full. This means that the tree has (2

levels – 1) nodes.6

It

should be noted that a Morse tree abovie is not a perfect tree. However, if we fill in all

of the empty nodes with a special character, and extend the leaves of the tree to be the

same level, then we have a perfect tree.

In this lab, we will work only with perfect binary trees. We represent each node with a

struct, containing a pointer to the left child node, a pointer to the right child node, and a

char with the contents of that node7

.

6 Remember that when using binary, 2n

is (1<<n). Do NOT use the math library to raise 2 to power of n.

7 This should feel a bit familiar, as it is quite similar to the LinkedList struct from a previous lab. However,

unlike our doubly-linked lists, our tree nodes have no concept of “parent,” and the location of one node is

not in general sufficient to find the rest of the tree. Whenver you create a binary tree in this lab, you

MUST keep track of the root node of the tree, since there is no other way to locate the full tree.

Recursion

With binary trees, or in fact trees of any type, recursion is an indispensable technique. A

recursive routine takes one of two actions. The first action is simple and easily

implemented, and is applied only to very simple “base cases.” The second action

reduces any other case to a base case, or at least simplifies that case, bringing it closer

to a base case. This routine is applied over and over again until all cases have been fully

simplified and resolved.

Wikipedia has a quite thorough description of recursion that would be a good starting

point, though we recommend jumping directly to the examples section.

In our case, our recursive functions are meant to apply to binary trees, with base cases

occurring at the “leaf” nodes. So our functions will take the general form:

If current node is a leaf node:

Handle current node

Return

Else:

Call self with right child

Call self with left child

Return

Printing the Binary Tree

BinaryTree.h includes functions to return the left and right child of a given node of the

binary tree. A full implementation of a binary tree would include insertions, deletions,

and various traversals; however these are beyond the scope of this class.8

One function which will be quite useful for this lab is the TreePrint() function, which

prints out the tree (rotated CCW 90°) so that you can immediately see the tree

structure. This function is recursive and has some subtlety involved. The first and most

important thing is for TreePrint() to be robust to being called with a NULL pointer.9

8 This is not an Abstract Data Types (ADT) class, and in this class we introduce some of the concepts as

they are useful. There are other classes who focus exclusively on ADTs and how to use them.

9

It is very important to NEVER dereference the NULL pointer. That is, if root is NULL, you cannot call the

child (root->left) as you will be attempting to follow the NULL pointer. Deferencing the NULL pointer

causes very strange crashes and weird things to happen. Do NOT do it.

If the tree looks like: Then calling TreePrint results in:

This printout has rotated the tree CCW 90°. As you will see, printing this way can be

easily accomplished with a simple recursion algorithm.

The basic idea is to increment the number of spaces to print for each level in, then go

right down the tree and do it again. Drop a line, print the spaces and the character

(remembering to substitute something for unprintable characters), then go left down

the tree and do it again. That is, each call to TreePrint has two calls to TreePrint inside it,

one for the right child, and one for the left child. This is the recursion.

The top-level call to TreePrint() would look like TreePrint(rootNode, 0), were rootNode

is the root node of the tree, and 0 is the number of spaces that should appear before

the root node. The pseudocode for the recursive TreePrint call is:

If root is NULL:

return

Else:

Increment n_spaces by LEVEL_SPACES

TreePrint(right child, n_spaces)

Print ‘\n’, followed by n_spaces, followed by current node’s char

TreePrint(left child, space)

return

By following this algorithm, the rightmost node data gets printed on the first line with a

number of spaces that is equivalent to LEVEL_SPACES x levels deep that it is. Make sure

you understand what is happening by going through the algorithm yourself by hand on a

simple tree.

We’ll say it twice: Go through this algorithm yourself, by hand, with a simple tree.

Creating the Binary Tree

Creating the tree requires using recursion in a slightly different way. In TreePrint(), we

recursed by passing a number of spaces that increased as the function got closer to the

root nodes. That was a sensible approach, since the leaf nodes already had information

about their leaf-iness (their children were NULL pointers). However, TreeCreate()

cannot rely on that information, since the leaf nodes do not yet exist! So TreeCreate()

passes a number that decreases as the function gets closer to the root node.

A top-level call to TreeCreate looks like: TreeCreate(dataString, level), where dataString

is a pointer to an array of chars, and level is the total number of levels in the tree to

create. So, to create the tree from the previous section, we would call

TreeCreate(“ABDECFG”, 3). Then, the pseudocode would be:

If Level == 0 (base case):

Return NULL

Else (non-base case):

Allocate current node

Current node’s data = first character of dataString

Right child = TreeCreate(right child dataString, level-1)

Left child = TreeCreate(left child dataString, level-1)

Return pointer to current node

Your full implementation must be a bit more developed than this. It must allocate space

for the current node. It should check for malloc fails, both for its own allocation and its

children. It must also determine what substring to pass to each child.

This is a bit harder to do on paper, since allocation is not an operation you generally

have to perform with paper, but we nonetheless recommend that you attempt it.

Working algorithms through on paper becomes more and more important as the

algorithms become more complex and abstract.

Morse Events

This lab again relies on the event-driven programming paradigm. The events that are

important in this lab will be those generated by the Morse library, which in turn relies

on the Buttons library. An interrupt for Timer 2, which triggers every 100Hz, has been

provided as a way to repeatedly call the MorseEvents event checkers in the background.

MorseCheckEvents signals that an event has occurred by returning the event. The ISR

must store the returned event in a module-level variable so that the rest of the program

can access the events.

MorseCheckEvents will also use a state machine. Though MorseCheckEvents is called

synchronously, its internal state machine should be asynchronous. This is achieved by

maintaining an internal event-checking system inside of MorseCheckEvents. Here is the

pseudocode for MorseCheckEvents():

update WORD timer

update LETTER timer

update DASH timer

check for button events

if a button event or timeout event was detected:

run morse event checking SM

Events with parameters

In previous labs, events were given as single enum. In some situations, it is useful to

attach more information to events. This lab provides an example of such a situation:

When a character is decoded, we would like to be able to record this event, but we do

not wish to have an event for “A”, an event for “B”, etc.

Instead, we now represent events as structs, with a parameter for the type of event and

a parameter for data associated with the event.

Most events do not require a parameter, but they still use the same event struct. When

handling these events, simply ignore the parameter field.

Countdown Timers

In the previous lab, we used a free-running timer to calculate all our time events. In this

lab, we will use a different technique to handle event timing. We will maintain several

countdown timers. A countdown timer is simply a number that is decremented

regularly until it hits zero, at which point an event is generated (in this case, by setting a

flag).

You can think of a countdown timer as a two-state SM:

Once in the idle state, the timer is stuck in that state, doing nothing, until some other

process resets the timer (in this case, the event-checking state machine can reset each

timer as needed).

Note that a full switch/case structure is not needed to implement a simple countdown

timer. That approach is overkill, though it is an acceptable approach.

Morse Events

In this lab you will again implement a state machine. The state machine diagram below

illustrates how to implement the MorseCheckEvents() function to convert button

events and timeout events (which are used only in MorseCheckEvents()) into Morse

events (which are used in Lab08_main.c).

To understand this state machine better, it is important to understand how the various

button events for BTN4 are translated into Morse events based on how long it has been

in between the button events. The way to properly figure out how the state machine

works and to understand it is to “walk” your way through the states imagining inputs

and checking the output. MorseCheckEvents() should be checked inside the 100Hz

timer interrupt (which increments a counter) and nominally return MORSE_EVENT_NONE

as the default.

For example, if the user is entering an “A”:

(1) The user begins by pressing the button. This triggers a transition to the DOT

state.

(2) They release almost immediately, so the state machine transitions to

WAITING_FOR_PULSE and signals a DOT event.

(3) The user then quickly presses the button again, transitioning to DOT, starting

the DASH timer, and beginning a second morse symbol. This time, the user

holds the button for half a second.

(4) During this time, the DASH_TIMEOUT occurs, causing a transition to the DASH

state.

(5) Now, when the user lifts their finger, the transition signals a DASH event.

(6) The user presses nothing for a second, giving the letter timer a chance to

generate a LETTER_TIMEOUT, so a NEW_LETTER event is generated.

See if you can figure out the timing for printing out “ANT MAN”.

Once you have figured out how the state machine works, it is much easier to test that

your state machine works correctly. For this function, it is very challenging to test this

effectively without human input, so it is sufficient to end your test harness with an

interactive portion. Run MorseCheckEvents() continuously (with perhaps an intentional

delay) and print the results in a readable way.

Iterative Design Plan

The first step of the Lab is to get the BinaryTree functions working and tested. Use the

binary tree functions to experiment (and print the output) to figure out how to encode

the Morse Tree.

Since you will be implementing from a state machine, the general way to implement this

is to implement one state transition at a time. You can printf inside MorseCheckEvents()

to check the states are transitioning the way they should. Ensure that you comment

those lines out before you submit your code. By starting with the display functionality in

this lab, being able to confirm state transitions will be simple because then you can just

view the OLED.

We have not provided an iterative design plan because you should be comfortable

approaching these labs and getting started. If you are not, please see the professor or

TA/tutor for help in planning on how to start this lab. Making an iterative design plan is

worthwhile as these labs can be complicated and focusing on a specific feature to

implement will make sure you can still move forward, one feature at a time.