jsp@b.gp.cs.cmu.edu (John Pieper) (06/12/87)
One distinct advantage of a (+1, 0, -1) number representation is that no carry-propagation is required for adders. Since the minor cycle of a machine usually corresponds closely with the propagation delay through a carry chain, this allows for faster machines (neglecting several other limiting factors :-) The speed of these adders can be used in a parallel multiplier with four-bit Booth encoding to rival and/or beat a Wallace scheme, depending on the technology used. Of course, you need 50% more memory to store numbers in this representation... -- ------------------------------------------------------------- John Pieper jsp@n.sp.cs.cmu.edu Carnegie-Mellon University "Supersonicus Siliconus"? What we need is Warp speed! -- ------------------------------------------------------------- John Pieper jsp@n.sp.cs.cmu.edu Carnegie-Mellon University "Supersonicus Siliconus"? What we need is Warp speed!
rroot@edm.UUCP (uucp) (06/18/87)
In article <35@b.gp.cs.cmu.edu>, jsp@b.gp.cs.cmu.edu (John Pieper) writes: > > One distinct advantage of a (+1, 0, -1) number representation is that no > carry-propagation is required for adders. Since the minor cycle of a machine You will still have carry propogation in many instances, even if you always do manage to normalize a number. Granted you may not have to carry as OFTEN (on the random case), but carry will still be necessary from time to time. -- ------------- Stephen Samuel {ihnp4,ubc-vision,seismo!mnetor,vax135}!alberta!edm!steve
fritz@polecat.UUCP (06/19/87)
In article <163@edm.UUCP> rroot@edm.UUCP (uucp) writes: >In article <35@b.gp.cs.cmu.edu>, jsp@b.gp.cs.cmu.edu (John Pieper) writes: >> >> One distinct advantage of a (+1, 0, -1) number representation is that no >> carry-propagation is required for adders. Since the minor cycle of a machine > >You will still have carry propogation in many instances, even if you always >do manage to normalize a number. Granted you may not have to carry as OFTEN >(on the random case), but carry will still be necessary from time to time. Addition in minimal balanced signed-digit ternary does indeed still require carry propagation, since it is an irredundant number system. Signed-digit binary addition, however, requires no carry propagation (or, more accurately, has an absolutely bounded maximum carry length) using the same digit set. (Reference: Kai Hwang, ``Computer Arithmetic: Principles, Architecture, and Design,'' John Wiley & Sons, New York, 1979, pp.107-112. This only covers the case of r>=3, for which carry length is limited to 1; for r=2, carry length is limited to 2, and a slightly more complex addition algorithm is needed for the general case, but ``totally parallel'' addition and subtraction are still possible.) In other words: using (+1,0,-1) for representing numbers in ternary doesn't eliminate carry propagation in addition; using the same digit set for binary numbers allows absolutely bounded carry propagation during addition. I've actually designed a multiplier chip using a restricted form of this type of arithmetic. In terms of circuitry, the adders are quite similar to carry- save full adders; the advantage over a standard carry-save array multiplier comes in sign handling (it's much easier to get the design right when the number system takes care of the sign rather than making you worry about it). Fritz Nordby. fritz@vlsi.caltech.edu cit-vax!fritz
jsp@b.gp.cs.cmu.edu (John Pieper) (06/19/87)
> In article <35@b.gp.cs.cmu.edu>, jsp@b.gp.cs.cmu.edu (John Pieper) writes: > > > > One distinct advantage of a (+1, 0, -1) number representation is that no > > carry-propagation is required for adders. Since the minor cycle of a > > You will still have carry propogation in many instances, even if you always > do manage to normalize a number. Granted you may not have to carry as OFTEN > (on the random case), but carry will still be necessary from time to time. Unless you mean integer overflow (which is always a problem on fixed-word-length machines) there is no carry propagation. There are carries, but these are limited to affect at most the next two bits. Since each bit S[i] of the sum depends only on A[i] thru A[i-2] and B[i] thru B[i-1] of the operands, we can add in time O(k) instead of O(log n). See TAKAGI et al, IEEE Trans. Comp., Sep 1985. -- ------------------------------------------------------------- John Pieper jsp@n.sp.cs.cmu.edu Computer Science Department Carnegie-Mellon University Pittsburgh, Pa 15213 "Supersonicous Siliconous"? What we need is Warp speed!