Algorithm | 计算机组成原理 – HW

2022-09-22

HW

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

算法代写 代写算法 Algorithm代写 代写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