EECE 320 Homework, Spring 2008

#include <iostream> #include <cmath> using namespace std; int main() { int list[4]={0,1}; for (int i=0;i<4;i++) switch (i) case '1': cout<<list[i]<<endl; break; case '2': cout<<list[i]<<endl; break; return 0; } EECE 320 Homework #1 XXXX XXX 12/10/2007 American University of Beirut Question 1 Question 2 a) (110011+011010) b) (100001-000011) 1 1 0 1 1 1 110011 56 1 10 10 10 10 1 33 + 011010 26 - 0 0 0 0 1 1 3 1 001101 77 0 1 1 1 1 0 30 c) (7768+4328) d) 9=01001 1 1 5=00101 -5=11011 7 7 6 510 1 1 1 + 4 3 2 282 0 1 0 0 1 9 1 4 3 0 792 + 1 1 0 1 1 -5 1 0 0 1 0 0 4 Decimal Hexadecimal Octal Unsigned Binary Signed 2’s Complement Signed- Magnitude 3855 F0F 7417 111100001111 0111100001111 0111100001111 1.125 1.2 1.1 1.001 01.001 -10 10110 11010 56.625 38.A 70.5 111000.101 0111000.101 15 F 17 00001111 01111 00001111 -31 11100001 111111 97 61 141 1100001 01100001 01100001 0.9375 0.F 0.74 0.1111 0.1111 -2.75 110.11 2 Question 3 a) N = 2n M = 2n - 1 b) N = - 2n M = -2(n - 1) + ( 2(n - 1) -1 )= - 1 c) N = 0 M = - (2(n - 1) – 1) Question 4 a) 210 = 1024 11111111112 = 210 – 1 = 102310 (10 bits) Therefore since 10 bits allow 1023 different combinations (or numbers), then we require a minimum of 10 bits to represent a controller with 1000 different states. b) 2 bits  4 different possibilities (00, 01, 10, 11) Therefore since the controller has two states, then there will be 4 possibilities for the first state and then a remaining 3 for the final state.  12 state encodings are possible. c) The given is the same as part (b) however this time we have 4 states for the controller. So, we will have 4 possibilities for the first state, 3 for the second, 2 for the third and 1 possibility left for the last state.  24 state encodings are possible. d)  Signed magnitude representation, requires the computer to execute more tasks for one operation, hence more memory & more time. This is because the computer has to read if the number is positive or negative then place the bigger number at the top and then subtract.  There are two representations for the number 0 (0000,1000) in signed magnitude. 3 Question 5 This is the C++ code. I used the concept of two dimensional dynamic arrays to write this code: //Abraham Hajjar 200600686 09/10/2007 EECE 320 #include < iostream > #include < cmath > using namespace std; int main() { int **p; int n=0; int num; cout<<"Please enter in number of bits n: "<<endl; cin>>n; num=pow(2,n); p=new int* [num]; for (int i=0;i<num;i++) p[i]=new int[n]; for (int t=0;t<num;t++) { for (int r=0;r<n;r++) { p[t][r]=0; } } p[0][n-1]=0; p[1][n-1]=1; for(int h=1;h<n;h++) { for (i=0;i<pow(2,h);i++) { int mid=pow(2,h); for(int z=0;z<n;z++) { p[mid+i][n-1-z]=p[mid-1-i][n-1-z]; 4 } p[mid+i][n-h-1]=1; p[mid-i-1][n-h-1]=0; } } for (t=0;t<num;t++) { for (int r=0;r<n;r++) { cout<<p[t][r]<<" "; } cout<<endl; } return 0; } For n=1 5 For n =3 For n=4 6 For n=6 7 EECE 320 – Digital Systems Design Homework 1 - Solution Fall 2007-2008 Problem 1 [44 points]: Complete the following table by writing each number in the required representation. Use the minimum possible number of bits. Decimal Hexadecimal Octal Unsigned binary Signed 2’s Complement Signed- Magnitude 3855 F0F 7417 111100001111 0111100001111 0111100001111 1.125 1.2 1.1 1.001 01.001 01.001 -10 10110 11010 56.625 38.A 70.5 111000.101 0111000.101 0111000.101 15 F 17 00001111 01111 01111 -31 11100001 111111 97 61 141 1100001 01100001 01100001 110.11 0.9375 0.F 0.74 0.1111 0.1111 00.1111 110.11 Problem 2 [16 points]: Perform the following addition and subtraction operations. Verify the results for each part by mapping the calculations to the decimal number system. Show the steps of your work (including carries and borrows) in order to get credit for your solution. (a) Unsigned binary: 110011 + 011010 = ? carry: 11 1 110011 51 + + 011010 26 -------------- ---------- 1001101 77 (b) Unsigned binary: 100001 – 000011 = ? borrow: 0111(10) 100001 33 - - 000011 3 -------------- ---------- 011110 30 (c) Octal: 776 + 432 = ? carry: 111 776 510 + + 432 282 -------------- ---------- 1430 792 (d) Subtract +5 from +9 using 5-bit two’s complement representation carry: 11 1 01001 +9 + + 11011 -5 -------------- ---------- 100100 4 The carry is excluded; the result is 00100  +4 Problem 3 [9 points]: Let N = 1 000 … 000 (n zeros), and M = 111 … 111 (n ones). What is the decimal value of M and N assuming: (a) Unsigned binary representation N = 2n M = 2n – 1 (b) Two’s complement representation N = – 2n M = – 1 (c) Signed-magnitude representation N = 0 M = – (2n-1 – 1) Problem 4 [11 points]: (a) How many bits are required to represent a controller with 1000 different states? Required bits = ceiling (log2 1000) = 10 bits (b) How many different 2-bit binary state encodings are possible in a controller with 2 states? Number of 2-bit binary state coding = = 12 (c) How many different 2-bit binary state encodings are possible in a controller with 4 states? Number of 2-bit binary state coding = 4! = 24 (d) List two advantages of two’s complement representation over signed-magnitude representation. o Zero has only one representation o Subtraction/addition easier (less computations) Problem 5 [20 points]: Write a program in C++ to find the Gray code for a given number of bits n using the algorithm presented in class. Your program should take as input the variable n (integer > 0) and give as output the Gray-encoded list of codewords in a neat and clear format. Include with your homework solution a printed copy of all code that you wrote. Include as well a printout of the output of your program for the following cases: n = 1, n = 3, n = 4, and n = 6. For n = 1: Gray code: 0, 1 For n = 3: Code: 0 0 0, 1 0 0, 1 1 0, 0 1 0, 0 1 1, 1 1 1, 1 0 1, 0 0 1 For n = 4: Code: 0 0 0 0, 1 0 0 0, 1 1 0 0, 0 1 0 0, 0 1 1 0, 1 1 1 0, 1 0 1 0, 0 0 1 0, 0 0 1 1, 1 0 1 1, 1 1 1 1, 0 1 1 1, 0 1 0 1, 1 1 0 1, 1 0 0 1, 0 0 0 1 EECE320 – Digital Systems Design Homework 1 XXX Fall 2007-2008 XXXX Problem 1: Decimal Hexadecimal Octal Unsigned binary Signed 2’s Complement Signed Magnitude 3855 F0F 7417 111100001111 0111100001111 0111100001111 1.125 1.16 1.1 1.001 01.001 01.001 -10 10110 11010 56.625 38.A 70.5 111000.101 0111000.101 0111000.101 15 0F 017 00001111 000001111 000001111 -31 11100001 10011111 97 61 181 1100001 01100001 01100001 -1.25 110.11 101.01 0.9375 0.F 0.74 0.1111 00.1111 00.1111 -2.75 101.01 110.11 Problem 2: a- Unsigned binary: 110011 + 011010: 110011 = 1+2+16+32 =51 110011 011010 = 2+8+16 =26 + 011010 ≡ 51 + 26 = 77 1001101 1001101 =1+4+8+64 = 77 b- Unsigned binary: 100001 – 000011: 100001= 1+32 =33 100001 000011= 1+2 =3 -000011 ≡ 33 – 3 = 30 011110 011110 =2+4+8+16 = 30 c- Octal: 776 + 432: 776= 6+7*8+7*64 =510 776 432=2+3*8+4*64 =282 +432 ≡ 510 + 282 = 792 1430 1430 =3*8+4*64+512 =792 d- +9 = 01001 +5= 00101 → -5= 11011 9-5=+9+ (-5) 01001 +11011 1 00100 00100 = 4 = 9-5 Problem 3: N = 1 000…000 (n zeroes) M = 111…111 (n ones) a- N = 2^n M = (2^n)-1 b- N = -2^n M = -1 c- N = 0 M = -(2^(n-1) – 1) Problem 4: a- 2^9= 512, 2^10=1024. So we need 10 bits to represent a controller with 1000 different states. b- 00, 01, 10, 11. Therefore there are 12 (4*3) 2-bit binary encodings possible in a controller with 2 states. c- There are 24 (4*3*2*1) 2-bit binary encodings possible in a controller with 4 states. d- 1) Zero has 2 signed and magnitude representations (0000 and 1000) while it has a unique two’s complement representation. 2) Addition and subtraction is easier in 2’s complement representation. Problem 5: #include < iostream > #include < cmath > using namespace std; int main() { int **p; int n=0; int num; cout<<"Please enter in number of bits n: "<<endl; cin>>n; num=pow(2,n); p=new int* [num]; for (int i=0;i<num;i++) p[i]=new int[n]; for (int t=0;t<num;t++) { for (int r=0;r<n;r++) { p[t][r]=0; } } p[0][n-1]=0; p[1][n-1]=1; for(int h=1;h<n;h++) { for (i=0;i<pow(2,h);i++) { int mid=pow(2,h); for(int z=0;z<n;z++) { p[mid+i][n-1-z]=p[mid-1-i][n-1-z]; } p[mid+i][n-h-1]=1; p[mid-i-1][n-h-1]=0; } } for (t=0;t<num;t++) { for (int r=0;r<n;r++) { cout<<p[t][r]<<" "; } cout<<endl; } return 0; } #include < iostream > #include < cmath > using namespace std; int graycode(int n,int m); int main() { int n=1; int m=0; cout<<"Please enter in n: "<<endl; cin>>n; m=pow(2,n); graycode(n,m); return 0; } int graycode(int n,int m) { cout<<endl; if(n==1) { cout<<1<<endl; return 0; } else if(m>=(n+1)) { cout<<endl; return graycode(n,m-1); } else { cout<<endl; return graycode(n,m-1); } } Question 5 This is the C++ code. I used the concept of two dimensional dynamic arrays to write this code: #include < iostream > #include < cmath > using namespace std; int main() { int **p; int n=0; int num; cout<<"Please enter in number of bits n: "<<endl; cin>>n; num=pow(2,n); p=new int* [num]; for (int i=0;i<num;i++) p[i]=new int[n]; for (int t=0;t<num;t++) { for (int r=0;r<n;r++) { p[t][r]=0; } } p[0][n-1]=0; p[1][n-1]=1; for(int h=1;h<n;h++) { for (i=0;i<pow(2,h);i++) { int mid=pow(2,h); for(int z=0;z<n;z++) { p[mid+i][n-1-z]=p[mid-1-i][n-1-z]; } p[mid+i][n-h-1]=1; p[mid-i-1][n-h-1]=0; } } for (t=0;t<num;t++) { for (int r=0;r<n;r++) { cout<<p[t][r]<<" "; } cout<<endl; } return 0; } For n=1 For n =3 For n=4 For n=6 C++ Code # include <iostream> # include <iomanip> # include <string> # include <cmath> using namespace std; int main () { int N; cout<<"Enter N (from 1 to n)"<<endl; cin>>N; string * p; p= new string [pow(2,N)]; p[0]="0"; p[1]="1"; for (int i=1;i<N;i++) for (int j=0; j<pow(2,i);j++) { int half=pow(2,i); p[half+j]=p[half-1-j]; p[half+j]="1"+p[half+j]; p[half-1-j]= "0"+p[half-1-j]; } for (i=0;i<pow(2,N);i++) cout<<setw(10)<<i<<setw(20)<<p[i]<<endl; return 0;} Output for n=1 for n=3 for n=4 for n=6