Algorithm | 计算机组成原理 – HW

HW

Algorithm | 计算机组成原理- 这个题目属于一个计算机组成原理的代写任务, 是比较典型的数制换算等代写方向

1

a

The number of bits are bits.

b

The number of hexadecimal characters is.

c

i

ii

####### 0: 0

####### 3: 10000

####### 6: 100010

####### 9: 100011

####### C: 10010

####### E: 10011

####### 7: 10100

####### D: 101010

####### A: 1010110

####### 2: 1010111

####### B: 101100

####### 4: 1011010

####### 5: 1011011

####### 8: 101110

####### 1: 101111

####### F: 11

iii

the total number of bits is

bits

2

a

Appearently, the answer for the permutation of length is.

b

According to a) since in terms for , there are one-pass permutations. So the length of bits is

c

We can encoding the permutation in these way:

d

• for [2,1,4,3,5,6]:[0,1,0,1,1]
• for [1,4,2,3,6,5]:[1,0,1,1,0]
• for [1,2,3,5,4,6]:[1,1,1,0,1]

e

• For 00110, it is non-decodable.
• For 10101, it is[2,1,4,3,6,5]
• For 11110, it is non-decodable.

3

a

i

as it must need 6 ‘N’s and 9 ‘E’s, the bits is 15.

ii

####### 001111010101110

iii

####### 100011100011111

iv

EEEEEEEENENNNNN

v

####### NENNNENENENNNEE

b

The theoretically optimal number of bits needed to uniquely encode each path is .

c

The encoding Algorithm is as follow:

EncodePermutation(a[1],...a[n] array of integers)

1. For i from 2 to n
2. If a[i]>a[i-1] then
3. let i-1-th bit of encoding as 1
4. else
5. let i-1-th bit of encoding as 0
6. return code

d

The path is : ENNNEEENNNEEEEE

So for the process encoding:

E 1 N 0 N 0 N 0 E 1 E 1 E 1 N 0 N 0 N 0 E 1 E 1 E 1 E 1 E 1

So the code is 100011100011111

e

It is non-decodable.

4

a

Since each letter in QWERTYUIOP needs four bits to encode, bits are required to encode each -character string over the alphabet

b

c

i

the encode for the string is 0000 0110 0111 0010 0100

ii

the encode for the string is 0100 0011 1000 0110 1001

EncodePath(a[1],...a[15] array of the path)

1. For i from 1 to 15
2. If a[i]==’N’ then
3. the i-th bit of code is 0
4. else
5. the i-th bit of code is 1
6. return code

EncodeString(a[1],...a[n] array of the string)

1. For i from 1 to n
2. If a[i]==’Q’ then
3. the i-th bit of code is 0000
4. else if a[i]==’W’ then
5. the i-th bit of code is 0001
6. else if a[i]==’E’ then
7. the i-th bit of code is 0010
8. else if a[i]==’R’ then
9. the i-th bit of code is 0011
10. else if a[i]==’T’ then
11. the i-th bit of code is 0100
12. else if a[i]==’Y’ then
13. the i-th bit of code is 0101
14. else if a[i]==’U’ then
15. the i-th bit of code is 0110
16. else if a[i]==’I’ then
17. the i-th bit of code is 0111
18. else if a[i]==’O’ then
19. the i-th bit of code is 1000
20. else if a[i]==’P’ then
21. the i-th bit of code is 1001 22.return code

iii

the decode for the string is QWERT.

iv

It is non-decodable.

d

According to the theory of huffman code construction, the number of bits required for the theoretically optimal encoding of each -character

string over the alphabet is

e

Let me assume the probability of each letter occuring in the string is equal. So we using huffman code to construct the code for each letter as follow:

• O 000
• P 001
• Q 0100
• W 0101
• E 0110
• R 0111
• T 100
• Y 101
• U 110
• I 111

i

for ‘QUIET’, the encode for it is 0100 110 111 0110 100

ii

for ‘TROUP’, the encode for it is 100 0111 000 110 001

iii

For 00000001001000110 the decode for it is non-decodable.

iv

For 10001001101010111 the decode for it is TQUYR