Chapter 5 Induction148
AnnC 1 -bit adderadds twonC 1 -bit binary numbers. More precisely, an
nC 1 -bit adder takes two lengthnC 1 binary strings
̨nWWDan:::a 1 a 0 ;
ˇnWWDbn:::b 1 b 0 ;and a binary digit,c 0 , as inputs, and produces a lengthnC 1 binary string
nWWDsn:::s 1 s 0 ;and a binary digit,cnC 1 , as outputs, and satisfies the specification:
num. ̨n/Cnum.ˇn/Cc 0 D 2 nC^1 cnC 1 Cnum.n/: (5.10)There is a straighforward way to implement annC 1 -bit adder as a digital circuit:
annC 1 -bitripple-carry circuithas 1 C2.nC1/binary inputs
an;:::;a 1 ;a 0 ;bn;:::;b 1 ;b 0 ;c 0 ;andnC 2 binary outputs,
cnC 1 ;sn;:::;s 1 ;s 0 :
As in Problem 3.5, the ripple-carry circuit is specified by the following formulas:
siWWDai XOR bi XOR ci (5.11)
ciC 1 WWD.ai ANDbi/OR.ai AND ci/OR.bi ANDci/;: (5.12)for 0 in.
(a)Verify that definitions (5.11) and (5.12) imply thatanCbnCcnD2cnC 1 Csn: (5.13)for alln 2 N.
(b)Prove by induction onnthat annC 1 -bit ripple-carry circuit really is annC 1 -
bit adder, that is, its outputs satisfy (5.10).
Hint:You may assume that, by definition of binary representation of integers,
num. ̨nC 1 /DanC 12 nC^1 Cnum. ̨n/: (5.14)