Description
Objectives of this assignment
• Understand short problem descriptions for which an assembly-language
solution is required.
• Use AVR assembly language to write solutions to three such small problems.
• Use AVR Studio to implement, simulate and test your solution. (We will not
need to use the Arduino mega2560 boards for this assignment.)
• Hand draw a flowchart corresponding to your solution to the second problem.
• You are not to use AVR functions in this assignment.
Part (a): Edit distance
One specialization in computer science and mathematics is information theory,
invented in the 1940s when the possibilities for the digital representation of data and
signals were first deeply investigated. An example of a concept in information theory
is edit distance, which describes how much one data string differs from another data
string. If we examine binary numbers instead of data strings, we can see an edit
distance more clearly. For example, consider the 8-bit binary equivalents of 198 and
81:
11000110
01010001
The numbers are clearly different, and one measure of this is found by determining
the number of bit positions in which the two binary numbers differ. Shown below are
these two numbers again but with the different bits noted in bold:
11000110
01010001
That is, if we denote bit 7 as the left-most bit of each number, then bits 7, 4, 2, 1 and 0
(i.e., five bits) are different between each number. The edit distance of these two
binary numbers is therefore five (5).
Your task for part (a) is to complete the code in edit-distance.asm within the
project csc230-a1-part-a provided to you. Please read this file for more details on
what is required.
• The values for which you will find the edit distance will be registers r16 and
r17
• The computed edit distance must be stored in r25.
Some test cases are provided to you in the provided assembly file.
Part (b): Resetting the right-most contiguous sequence of bits
Another common task when working with bit sequences is to identify and work with
contiguous set bits. For example, consider the bit sequence shown below, with several
of the set bits shown in a bold font:
01011100
We say that the bolded set bits constitute the right-most contiguous set bits. That is,
bits 4, 3, and 2 are set. If we reset the right-most contiguous set bits of the example just
given, the result is:
01000000
Your task for part (b) is to complete the code in reset-rightmost.asm in the project
csc230-a1-part-b provided to you. Please read this file for more details on what is
required.
• The bit sequence for which the right-most contiguous set bits must be reset is
in r16.
• The result must be stored in r25.
Some test cases are provided to you in the provided assembly file.
You must also draw by hand the flowchart of your solution and submit a scan or
smartphone photo of the diagram as part of your assignment submission; please
ensure this is a JPEG or PDF named “reset-rightmost-flowchart.jpg” or “resetrightmost-flowchart.pdf” depending on the file format you have chosen. (Please:
No BMPs or Word files! We beg of you!)
Part (c): Addition of two packed BCDs numbers
In lectures we have seen that a number such as 7210 may be represented as an eightbit two’s complement number: 0b01001000. Another form for representing decimal
numbers that was once popular is called binary-coded decimal (BCD). For a given
number, each decimal digit (from 0 to 9) was encoded in a four-bit field. The BCD
representation of 7210 is 0b01110010, i.e., where the left nibble (0111) represents 7
and the right nibble (0010) represents 2. A larger decimal number would therefore
require more groups of four bits, that is, four bits per decimal digit.
Put differently, one result of BCD is that the hexadecimal version of the number
appears identical to the decimal, even though they are in different bases. That is, 0x72
in a BCD encoding has the same meaning as 7210.
Performing arithmetic with BCD numbers is, however, definitely not the same as with
the ordinary two’s-complement encoding we have examined in class! For example,
adding together 0x35 (5310) and 0x49 (7310) as two’s complement numbers results in
0x6E (12610). However, as BCD, the addition 0x35 and 0x49 is 0x84. This also suggest
that the largest number which can be represented in a byte using BCD is 0x99. (We
will only concern ourselves in this assignment with positive numbers.)
Your task for part (c) is to complete the code in bcd-addition.asm in the project
csc230-a1-part-c provided to you. The code is to add two numbers represented in
BCD.
• The BCD operands for addition are in r16 and r17.
• The right-most two BCD digits of addition result must be in r25.
• The carry (either 0 or 1) resulting from the addition must be in r24.
Please read the ASM file for more detail on what is required. In your solution you will
wish to make use of the cbr and swap instructions (amongst others).
What you must submit
• Your completed work in the three source code files (edit-distance.asm,
reset-rightmost.asm, bcd-addition.asm). Do not change the names of
these files! Please do not submit any other AVR 7 Studio project files.
Please do not submit ZIP files.
• Your work must use the provided skeleton files. Any other kinds of solutions
will not be accepted. (Again: Do not submit ZIP files containing the Microchip
projects!)
• The scan / smartphone photo of your hand-drawn flowchart with the name
of “reset-rightmost-flowchart.jpg” or “resetrightmost-flowchart.pdf” depending on the format you have chosen.
Evaluation
• 3 marks: Edit Distance solution is correct for a variety of byte pairs values
(part a).
• 3 marks: Reset Rightmost is correct for different byte values (part b).
• 1 mark: Hand-drawn flowchart for Rest-rightmost solution is correctly
prepared (part a).
• 2 marks: BCD addition solution is correct for different pairs of BCD values
(part c).
• 1 mark: All submitted code is properly formatted (i.e., indenting and
comments are suitably used), and files correctly named.
Total marks: 10
