[2010 년디지털시스템설계및실험중간고사 2 답안지 ] 출제 : 채수익 1. (a) (10 pts) Robertson diagram Quotient 와 remainder 의 correction 을뒤로미루는것이 non-restoring division 이다. 즉, q = 1, 2r 0 1, 2r <0, r = 2r q D 만일연산결과 remainder와 dividend의 sign이다를경우, correction step이필요하다. (1) dividend와 divisor가 sign이같으면, remainder에 D를더하고, quotient에서 ulp를뺀다. (2) divident와 divisor의 sign이다르면, remainder에서 D를빼고, quotient에 ulp를더한다. 또한만일중간에 remainder가 0이된다면, correction이필요하다. 이경우, remainder에 D를더하고, quotient에서 ulp를뺀다. Robertson diagram 을정확히그린경우 (5 pts) - x, y 축의값들을정확히기술하지않았을경우 (-2 pts) - x, y 축이의미하는바를정확히기술하지않았을경우 (-2 pts) - q 가해당영역에서어떤의미를갖는지정확히기술하지않았을경우 (-1 pts) Non-restoring division algorithm 에대한설명을정확히한경우 (5 pts) - q 와 r 가어떻게결정되는지수식혹은말로설명하지않았거나틀렸을경우 (-1 pts) - 연산결과의부호 correction step 에대해서설명하지않았거나틀렸을경우 (-1 pts) - Zero remainder 의경우에대한 correction 을설명하지않았거나틀렸을경우 (-1 pts)
(b) (10 pts) 1, 1을각각 0, 1로표기한다고가정하면, Step 1. Shift the given number one bit position to the left Step 2. Complement the most significant bit Step 3. Shift a 1 into the least significant position 2 s complement number로바꾸는알고리듬을기술한경우 (10 pts) 11 을 01로바꾼다고쓴경우를비롯해일반적이지않은경우 (5 pts) 2. (1) (4 pts) Base는 2고, hidden bit를사용한다. E = 0는, f = 0인경우 zero에해당하고, f 0인경우 denormalized number에해당한다. E = 255는, f = 0인경우 ± 에해당하고, f 0인경우 NaN에해당한다. 1 < E < 254인경우에는 E가 8 bit이고, f가 23 bit이며, S가 1 bit이라고기술하고, base는 2, hidden bit를사용한다고기술한경우 (1 pts) E = 0인경우에대해기술한경우 (1 pts) E = 255인경우에대해기술한경우 (1 pts) 1 < E < 254인경우에대해기술한경우 (1 pts) 각경우에대해하나라도틀리게쓴경우, 해당경우에대해 0 pts 부여 (2) (4 pts) 빠져있는 block 이있거나잘못된경우 -1 pts 씩 4 개이상잘못된경우 0 pts
(3) (4 pts) Exponenet comparison and significand alignment significand addition/subtraction post-normalization and rounding 에대한내용을 block에대한설명과함께기술설명이일부빠져있는경우 (-1 pts) (4) (8 pts) Shifter를 barrel shifter로구현 leading 0s detect를미리수행두가지이상적당한아이디어들을기술한경우 (8 pts) 한가지만기술한경우 (6 pts) 3. (1) (10 pts) (MRRE) 각경우에대해 5 pts 씩 사소한실수 (-1 pts 씩 ) (2) (5 pts) 1 0.36 2 = 4ln2 2 ( 주의 : hidden bit의존재로 ulp가 2 이다 ) 사소한실수 (-1 pts 씩 ) 4. (1) (5 pts)
위는 8-bit adder의관한경우로, 16-bit adder의경우, 한 step이더있게된다. 또한최초의 step 에서 LSB의경우, full adder가 1개만필요한것에유의한다. Step 0 to Step 1. Full adder 31개 Step 1 to Step 2. 1-bit 2to1 Mux 30개 (=2*2*7+2) - 예를들어, i=6인경우에 c_in이 0, 1인경우각각에대해 i=7의 sum과 carry out을각각선택해야한다. LSB를제외하면반복되므로, 2*2*7이며, LSB에해당하는경우는 i=0가이미결정되어있기때문에 i=1의 sum과 carry out을선택하기위한 mux가각각 1개씩필요하다. Step 2 to Step 3. 1-bit 2to1 Mux 21개 Step 3 to Step 4. 1-bit 2to1 Mux 15개 Step 4 to result. 1-bit 2to1 Mux 9개총 FA 31개, 1-bit 2to1 mux 75개 Block diagram이나말로위의구현방법을설명 (3 pts) - 16-bit carry save adder를쓴경우 (1 pts) - Multi step으로구성하지않고최초의 stage에대해서만 conditional sum을한경우 (1 pts) Full adder와 1-bit 2to1 mux의개수 ( 각각 1 pts) ( 주의 : 1-bit 2to1 mux의개수임 ) (2) (10 pts) module mux_2to1(x, a, b, select); parameter n = 8; input select; input [n-1:0] a, b; output [n-1:0] x; wire [n-1:0] a, b, x; assign x = (select == 1'b0)? a : b;
endmodule module full_adder(sum, c_out, a, b, c_in); input a, b, c_in; output sum, c_out; wire sum, c_out, tmp1, tmp2, tmp3; assign sum = a ^ b ^ c_in; assign tmp1 = a & b; assign tmp2 = b & c_in; assign tmp3 = a & c_in; assign c_out = tmp1 tmp2 tmp3; endmodule module conditional_sum_adder(sum, c_out, a, b, c_in) input [15:0] a, b; input c_in; output [15:0] sum; output c_out; block diagram 에맞게끔코딩 endmodule Full adder, mux module 각각 3 pts Conditional sum adder를맞게기술한경우 (4 pts) (1) 에서 conditional sum adder를잘못기술하고이를 verilog로쓴경우 (2 pts) 5. (15 pts) associative (5 pts) 증명은아래와같다. (P,G ) (P,G ) (P,G )=(P P,G +P G ) (P,G )= (P P P,G +P G +P P G ) = P (P P ),G +P (G +P G ) =(P,G ) (P P,G +P G )=(P,G ) ((P,G ) (P,G )) commutative (5 pts) 성립하지않는다. 반례 : (0, 0) (1, 1) = (0, 0) (0, 1) = (1, 1) (0, 0) idempotent (5 pts) 증명은아래와같다. (P, G) (P, G) = (P P, G+P G) = (P, G) associative, commutative, idempotent 가무엇인지기술할경우, 각항목당 2 pts
proof, 혹은 disproof 를맞게제시한경우, 각항목당 5 pts Proof 나 disproof 없이 fundamental carry operator 만기술한경우 (2 pts) 그외경우, (0 pts) 6. 위의표를참고하여문제를푼다. n 을 2 의 power 로표현되는 4 이상의정수로제한했으므로, 위 의표에서는 4, 8, 16, 32 에대한경우를참고하면된다. (1) (5 pts) 맞을경우 (5 pts) 2 (log (n) 1) n 2를이용한경우 (3 pts) ( 각 level 사이가 integer라는조건이추가로있기때문에 approximation이계산될뿐, 정확한값이도출되지는않는다 ) n이고정된한경우 ( 예를들어, n = 4인경우 ) 에대해서만쓴경우 (1 pts) 그외 (0 pts) (2) (5 pts) log (n) 1 맞을경우 (5 pts) 식의정리가덜된경우 (3 pts) (ceiling function 등이남아있는경우 ) n이고정된한경우 ( 예를들어, n = 4인경우 ) 에대해서만쓴경우 (1 pts) 그외 (0 pts) (3) (5 pts) 위의 level 에 2D 와 3D 를곱해서비교해보면, 4D (log (n) 1)>3 (log (n) 1) (3,2) counter 의 delay 가더크다. 즉, 주어진조건에서항상 (4,2) compressor 를사용한곱셈기가항상빠르다. 맞을경우 (5 pts) 틀릴경우 (0 pts)
7. (1) (5 pts) l= log(k/2) log(3/2) 단, 위의경우는 approximation 으로정확한값은 (2) 의 table 을참고한다. 위의수식중하나를쓰고 approximation 이라는말을쓴경우 (5 pts) approximation 이라는말이없는경우 (-1 pts) Level 수를직접얻지는못하지만, 관련된수식을쓴경우 (3 pts) (2) (5 pts) 위의 table 과정확히일치하는경우 (5 pts) 사소한실수 (-1 pts) (1) 의수식을사용하여 table 을만든경우 (-3 pts) 8. (1) (5 pts) sequential_multiplier (A, X, n) P <- 0; for (i = 0; i < n; i++) { if (X[i] == 1) { P = P + A; } P >>> 1; // arithmetic shift } if (X < 0 && P < 0) { P = P A; } return P 위와같이 pseudo-code 형태로 sequential multiplier를기술한경우 (5 pts) - Booth algorithm 등다른형태로기술한경우 (-1 pts)
마지막의 correction step을쓰지않았거나틀린경우 (-2 pts) (2) (10 pts) (1) 에서제시한알고리즘과유사한형태로기술한경우 (10 pts) (multi-cycle도상관없음 ) adder만기술한경우 (5 pts) 마지막의 correction step을쓰지않은경우 (-3 pts) Verilog code의합성가능성은무관함 9. (1) (6 pts) Logic levels : L + l (L = log n) Fanout : 2 +1 Wiring tracks : 2 Logic level, fanout, wiring track이라는단어를기술한경우 ( 각 1 pts) 수식을제대로기술한경우 ( 각 1 pts) (2) (5 + 2 pts)
맨위의그림을문제의조건에맞게변형한다. 단, black 사각형과 gray 사각형의구분은아래의그림을따른다. P, G generator / fundamental carry operator / sum generator 각각 1 pts ( 다맞은경우 +2 pts) 사각형의경우, black과 gray를정확히맞춘경우에만 2 pts (3) (5 pts) Maximum delay는 MSB에서발생한다. (2) 의그림을참고하면, 1D+4D+2D = 7D 정확히수치가맞은경우에만 5 pts, 틀리면 0 pts (4) (10 pts) P, G generator / fundamental carry operator / sum generator 각각에대해 2 pts 씩 이를이용해 Sklansky adder 를기술한경우 (4 pts) 10. (1) (5 pts) x x x x y y y operation comments 0 0 0 0 0 0 0 +0 string of zeros 0 0 1 0 0 0 1 +A a single 1 0 1 0 0 0 1 0 +2A a single 1 0 1 1 0 0 1 1 +3A two 1 s 1 0 0 0 1 0 0-4A beginning of 1 s 1 0 1 0 0 1 1-3A alternating 1 1 0 0 0 1 0-2A beginning of 1 s 1 1 1 0 0 0 1 -A beginning of 1 s 0 0 0 1 0 0 1 +A end of 1 s 0 0 1 1 0 1 0 +2A end of 1 s
0 1 0 1 0 1 1 +3A alternating 0 1 1 1 1 0 0 +4A end of 1 s 1 0 0 1 0 1 1-3A two 0 s 1 0 1 1 0 1 0-2A a single 0 1 1 0 1 0 0 1 -A a single 0 1 1 1 1 0 0 0 +0 string of 1 s Recoding table이정확한경우 (comments는상관없음 ) (5 pts) 일부실수가있는경우 (-1 pts씩 ) (2) (5 pts) Partial products의개수가줄어든다. 장점을정확하게쓴것이한가지이상있는경우 (5 pts) single 0나 single 1에대한처리를쓴경우 (3 pts) (radix-2에서 radix-4로갈때의장점 ) (3) (10 pts) Unsigned를곱할경우, MSB에 0을추가해줘야제대로된결과가나온다. Radix 8 modified Booth s algorithm을사용하면, partial product의개수가 3개로줄어든다. 또한중간에 3-bit shift를해주어야하며, 최대 4A까지더하거나빼기때문에아래와같이덧셈이이루어진다. 2 bit 3 bit 3 bit 3 bit 2 bit 3 bit 3 bit 3 bit 가장아랫부분의덧셈에서 half adder를사용하고이후부터는 full adder를사용한다고하자. 따라서 delay는 10 FA + 1 HA가된다. 이와같은덧셈이 partial product의개수인 3회만큼일어나므로, delay = 30 FA+3 HA ( 단, shift 및 recoding table을읽어오는데걸리는 delay는무시한다고가정한다 ) MSB에 0을추가해줘야한다는내용이있음 (3 pts) 덧셈이몇회이루어지는가 (partial product의개수 ) 에대한설명 (3 pts) Delay가맞을경우 (4 pts) - Carry save adder 형태로구현한경우 17 FA+1 HA로쓴경우 (4 pts) - 4A, 3A 등에대한경우를생각하지않고한경우 (2 pts)