1) What would be the encoded version of the message xxy yyx xxy xxy yyx if LZW c
ID: 3914268 • Letter: 1
Question
1) What would be the encoded version of the message
xxy yyx xxy xxy yyx
if LZW compression, starting with the dictionary containing x, y and a space (as described in Section 1.8 of your textbook) were used. Show both the message and the final dictionary.
2) The following message was compressed using LZW compression with the dictionary given below. What is the decompressed message? 22123113431213536 Dictionary
3) Encode the following sentence in ASCII using even parity by adding a parity bit at the high- order (left) end of each character code:
The total cost is $7.25.
To help here are the first two characters:
T 101010100
h 101101000
e …
<Space> …
t …
o …
.
.
.
4) Using the error-correcting code given to the right, decode the following words:
a. 111010 110110
b. 101000 100110 001100
c. 011101 000110 000000 010100
d. 010010 001000 001110 101111 000000 110111 100110
e. 010011 000000 101001 100110
5) List the three main parts of a CPU and briefly describe what each one does.
6) The following are instructions written in the machine language described in Appendix C. Translate them into English.
Example: 18AC = LOAD register 8 with the contents of memory cell AC
a. 7123
b. 70E1
c. A304
d. B100
e. 2BCD
7) Translate the following instructions from English into the machine language described in Appendix C.
a. LOAD register 6 with the hexadecimal value 77.
b. LOAD register 7 with the contents of memory cell 77
c. JUMP to the instruction at memory location 24 if the contents of register 0 equals the value in register A
d. ROTATE register 4 three bits to the right
e. AND the contents of registers E and 2 leaving the result in register 1.
8) What instruction(s) would change in Figure 2.7 in your textbook if the values added were encoded using floating-point, rather than two’s complement? What would the correct instruction(s) be, encoded as a hexadecimal value?
9) Encode the following values using the 8-bit floating-point format described in the textbook. Indicate each case in where a truncation error occurs.
a) -7½
b) ½
c) -3¾
d) 7?32
e) 31?32
encoding Character 1 x 2 y 3 <Space>Explanation / Answer
Answer 1. These are the steps:
1. Firstly initialize the dictionary with single characters. "_" represents a space in the dictionary.
x 1
y 2
_ 3
2. Look for the first substring of "xxy yyx xxy xxy yyx" which is "xx" this is not present in the dictionary. So first replace the first x with 1 and the second x also with 1. Then include xx in the dictionary with value 4.
code: 1, 1
x 1
y 2
_ 3
xx 4
3. The next substring is "y " (note the space at the end of the string). This substring is not present in the dictionary. Firstly y is replaced with 2 and the <space> is replaced with 3, then the substring is included in the dictionary.
code: 1, 1, 2, 3
x 1
y 2
_ 3
xx 4
y_ 5
4. The same procedure is repeated for the next two substrings "yy" and "x ".
code: 1, 1, 2, 3, 2, 2, 1, 3
x 1
y 2
_ 3
xx 4
y_ 5
yy 6
x_ 7
5. The next substring "xx" is in the dictionary, the next substring "xxy" which is not in the dictionary (And "xxy" is added to the dictionary), "xx" is replaced with 4 and the next character y is in the dictionary, so we check for the next substring "y " which is in the dictionary, so we again check for the next substring which is "y y", this is not in the dictionary (we include it in the dictionary and replace "y " with 5 and continue with the procedure.
Finally the code obtained is 1, 1, 2, 3, 2, 2, 1, 3, 4, 5, 8, 2, 6, 1
And the final state of the dictionary is:
x 1
y 2
_ 3
xx 4
y_ 5
yy 6
x_ 7
xxy 8
y_x 9
xxy_ 10
_y 11
yyx 12
Keep adding the strings not observed to the dictionary while replacing the largest possible substring which is observed in the dictionary.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.