辅导 COMP1860 Building Our Digital World: Computer Systems and Architecture辅导 Python编程

Building Our Digital World:  Computer Systems and Architecture

COMP1860

Activity Sheet 2.5

This worksheet contains a combination of formative  activities  (which contribute towards your learning) and summative activities  (which you will complete and submit to be assessed as part of your portfolio).

Every exercise marked with a red border is a summative exercise and must be submitted as part of your portfolio. You should use PebblePad to submit portfolio activities. In addition, you may be required to submit other activities — the module teaching staff will provide instructions.

Activities marked by (*) are advanced, and may take some time to complete.

Expectations:

1.  Timeliness   You  should complete all of the activities in the order provided and submit your portfolio evidence on PebblePad before the completion date (Friday, 07/03/2025, at 17:00).

2.  Presentation   You should present all of your work clearly and concisely following any additional guidance provided by the module staff in the module handbook.

3.  Integrity   You are responsible that the evidence you submit as part of your portfolio evidence is entirely your own work.  You can find out more about academic integrity on the Skill@library website.  All work you submit for assessment is subject to the academic integrity policy.

Feedback:   Feedback on formative activities will be provided via Lab classes and tutorials.  Feedback on evidence submitted as part of the portfolio will be available on PebblePad.

Support opportunities:    Support with the activity sheet is available in the Lab classes and tutorials.  Individual support is available via the online booking system.

Expected time for completion:    2-3 hours.

Expected complete date:   Friday, 07/03/2025, at 17:00

Coursework summary

In this activity sheet, you will be implementing a small library to compute the parity of a bit string.  Using a single parity bit generates a code that can detect a single error but cannot correct it.  Useful references for this activity sheet are the same as for Activity Sheets 2.3 and 2.4.

Learning outcomes

On completion of this activity sheet, you will have:

1.  developed and tested a simple error-detecting code;

2.  implemented a library of functions to implement encoding and decoding of a parity-based code; and

3.  utilised a simulator of the Hack Virtual Machine to test and debug the library.

Instructions

Please submit your Sys .vm file to the Activity Sheet 2.5 assessment on Gradescope.  To complete this activity sheet, your solution to the portfolio question will need to pass at least 75% of the tests.  When this happens,  Gradescope will return an 8-character string for you to add as evidence in the PebblePad workbook for this activity sheet.

Outline.   This activity sheet will help you develop functions for the Hack Virtual Machine to encode a 15-bit string into 16 bits with a single parity bit. The Hack computer uses 16-bit words, and for this activity we will assume that the 15 right-most bits contain the 15 bit of information, whereas the left-most bit contains the parity of the string.

We will consider that the index of the bits in a string increase from right to left, starting from 0.  For example, the 16-bit string a has the bits:

a15  a14  a13  a12  a11  a10  a9  a8  a7  a6  a5  a4  a3  a2  a1  a0

For our purposes, a15  is the parity bit, which can be computed from the 15 information bits a14 , a13 , . . . , a1 , a0 .

The parity bit can be defined in many ways. One simple definition is

In other words, the parity bit is 1 if an odd number of information bits are set to one, and it is 0 if the number of information bits sets to 1 is even.

Using logic operations, the parity bit can be defined as

a15  = a14  ⊕ a13  ⊕ a12 ⊕ a11 ⊕ a10 ⊕ a9 ⊕ a8 ⊕ a7 ⊕ a6 ⊕ a5 ⊕ a4 ⊕ a3 ⊕ a2 ⊕ a1 ⊕ a0 ,                     (1)

where ⊕ denotes the exclusive  or  (xor) operation.

The steps below will guide you in the development of this project using (1). The description is very detailed, but the implementations themselves are not long. The longest and most difficult functions to implement are Sys .shiftLeft (no more than 20 lines) and Sys .computeParity (around 30 lines). You can use the supplied file Sys .vm as a skeleton for your final submission – you can do things differently, but you should ensure that your Sys .vm runs as expected with the supplied Sys .tst. Otherwise, your submission might not work as expected on Gradescope.

Bit operations.   In this activity sheet, you will deal with bit strings, and you will therefore rely heavily on bit-level operations. The tool to achieve this kind of low-level manipulations are  bitmasks, which can be used to set, clear, and read individual bits from a bit string.

Setting a bit means that the result of the operation will have that bit equal to 1, and all other bits will remain unchanged. If that bit is already a 1, the operation does not modify it.  To set the ith bit, you should create a bitmask with all bits but the ith set to 0, and you should take the bitwise or between this bitmask and the value whose bit you want to set.  This bitmask is equivalent to the decimal number 2i.  For example, to set the third bit from the right, the bitmask to use is

0000000000001000

which is equivalent to the decimal number 23  = 8. In the Hack virtual machine, we can set the third bit of the string representing 4023 with the following three instructions

push  constant        8  //  0000000000001000

push  constant  4023  //  0000111110110111

or                              //  0000111110111111  is  at  the  top  of  the  stack .

The same bitmask can also be used to read the value of the ith bit of a string, taking the bitwise and between the bitmask and the value whose ith bit you want to read.  For example, we can read the third bit of the string representing 1323

push  constant        8  //  0000000000001000

push  constant  1323  //  0000010100101011

and                               //  0000000000001000  is  at  the  top  of  the  stack .

To check whether the bit is set, you can compare it with 0 using either eq or neq.

Clearing a bit means that the result of the operation will have that bit equal to 0, and all other bits will remain unchanged.  To clear the ith bit, you should create a bitmask with all bits but the ith set to 1, and you should take the and between this bitmask and the value whose you want to clear.  In 2’s complement, this bitmask is equivalent to the decimal number —(2i + 1). For example, to clear the third bit from the right, the bitmask to use is

1111111111110111

which in 2’s complement is equivalent to the decimal number —(23 + 1) = —8.  In the Hack virtual machine, we can clear the third bit of the bit string representing 348 as follows

push  constant      0

push  constant      9

sub                           //  1111111111110111  is  at  the  top  of  the  stack .

push  constant  348  //  0000000101011100

and                           //  0000000101010100  is  at  the  top  of  the  stack .

3. Implement the function Sys.computeParity, which computes the parity of the 15 right-most bits of the bit string at the top of the stack. Note that the value of the left-most bit (the 16th from the right) should be ignored by this function. This is the most complex functions in this project, and its implementation relies on both Sys .xor and Sys .shiftLeft.  The function can be implemented in multiple ways – and example is provided in snippet of C code below.

uint16  parityBit  =  0;

for(i  =  0;  i  <  15;  i++)  {

uint16  bitmask  =  1  <<  i;  //  Shift  constant  1  left  by  i  positions .

uint16  ithBit  =  inputString  &  bitmask;

if  (ithBit  !=  0)

parityBit  =  parityBit  ^  1;

}

In this snippet,  uint16 represents the default  16-bit format of the Hack computer,  the  << operator  is the Sys .shiftLeft function you have defined, the & operator represents the bitwise and (and operation of the Hack Virtual Machine), and the ^ operator represents the bitwise xor operator (Sys .xor function you have defined above).  To test your implementation in the emulator, you can change the function definition of  Sys .init in Sys .vm to:

function  Sys .init  0

push  constant  31                  \\  00000000  00011111

call  Sys .computeParity  1  \\  10000000  00011111

This code pushes onto the stack 31, which has an odd number of bits set to 1, and the call to Sys .computeParity should leave 1 at the top of the stack.