The Optimum Radix In 
Multiple-Valued Logic Systems 

1- Introduction

Many characteristics of digital systems are reflected due to their radices such as the data length, circuit complexity, interconnection complexity, the total pins of a digital component, the address bus width, the data bus width, the number of representations, power consumption, the speed of arithmetic operations … etc. Some of these characteristics are enhanced as we increase the radix of a system and some are not.  For example, if the data and address buses lines are decreased, the total number of pins is reduced, interconnection complexity is reduced, …etc.  However, these characteristics are not linearly enhanced all the time and for all types of components as we increase the radix.  Some components may best operated at radix 16, others may be at radix four, and others may be at radix two.  Due to the various changes to these characteristics, the solution to the optimum radix should be an important issue.  Thus, what is the optimum radix relative to given constraints?  Hurst in [1] showed that the optimum radix is equal to e=2.718.  By rounding this number to three, he suggested that three-valued systems are the most economical. In his analysis he assumed that circuit complexity is linearly proportional to the system radix. According to George Abraham in [4] this assumption has to be verified.  Also, according to Butler in [2], practical cases do not support the linearity assumption. Also, based on their analysis on deriving an empirical relation between cost and radix, Allen and Givone in [3] showed that the optimum system is strictly greater than not equal to e=2.71 but they did not solve for the exact value. 

The current study of this paper presents a different approach to the optimum problem. In this paper, we analyzed the optimum problem based on the pinout-problem and the multiplexing-time problem. We assumed the current digital system radix is “B” and the new digital system that will optimize the pinout-problem and the multiplexing-time problem relative to the B-radix system is the z-radix system. By these analysis we derived an overall performance function of digital components that measures the system performance using the gain in pins-cut and the gain in multiplexing-time.  This performance function depends on the system to be optimized and on the optimizing system. We found the first derivative of this performance function and solved for the optimum system to be Z_optimum=B².  By setting B=2 which corresponds to the binary system and substituting in the optimum equation. (Z_optimum=2²=4) we found that the optimum system that will optimize the binary system is the quaternary system. 

2- Optimum Radix

The following analysis of finding the optimum system considers the pinout-problem and the multiplexing-time problem in digital circuits. First, we will analyze with respect to the pinout-problem and then with respect to the multiplexing-time problem.

Assume the current digital system radix is “B” and the new digital system that will optimize the pinout-problem and the multiplexing-time problem relative to the B-radix system is the z-radix system.

Pinout Analysis

Let the number of pins of a data bus in a digital component in the z-radix system be denoted by N_z and in the B-radix system by N_B and the difference between the two numbers denoted by N_cut where N_cut=N_B-N_z. In order to compare the two components in both systems we define the gain in pins-cut between the two systems as G_pins-cut=N_cut/N_B. From the preceding equation we have G_pins-cut=(N_B-N_z)/N_B. Since the component in the B-radix system has a bus with “N_B” lines, then this bus must have an equivalent bus in the z-radix system with “N_z” lines so that both buses handle the same amount of data. In order to satisfy this equivalence condition, we have to have Z^Nz=B^NB. By taking the natural log of both sides we obtain N_zLn(z)=N_BLn(B). By solving for the ratio N_z/N_B we obtain N_z/N_B=Ln(B)/Ln(z) and substituting in the G_pins-cut we obtain G_pins-cut=1-(Ln(B)/Ln(z)).

Example-1: Consider B=2 and Z=16.  Assume we have a 32-bit counter in the binary system.  A DIP package for this counter requires 38 pins.  32 pins for the counter output, two pins for power supply, one pin for the clock signal and one for the clear signal.  An equivalent counter in the hexadecimal system has 12 pins.  8 pins for the counter output, 2 pins for the power supply, one pin for the clock signal, and one pin for the clear signal.

The pins-cut gain is given by Gpins-cut= (NB-Nz)/NB=  (32-8)/32=24/32=75% which is the same as Gpins-cut=1-(Ln(B)/Ln(z))= 1-Ln(2)/Ln(16)=1-0.25=75%.  Note that the counter output is considered to be data bus. See illustrative figure above.

Multiplexing-time Analysis

Assume we have the same set of data stored in similar components in both systems.  Assume we would like to transfer data across a telephone line in each component serially and evaluate the overall multiplexing-time needed to transfer data.  The data size will be measured by the number of digits in each system that represent data itself. Assume data size in the B-radix is given by  D_B B-digits (ex.  21 bits) and the data size in the z-radix system is given by D_Z Z-digits (ex. 7 octal-digit). Each digit in either system is transferred out of the component by one-clock cycle with a period of T₀. The total multiplexing-time for the data in the B-system is given by T_B=D_BT₀ and for the z-system it is given by Tz=DzT₀. To compare both times we have to unify the unit of measurements in both systems. A Z-Digit in the Z-system is equivalent to Ln(z)/Ln(B) digits in B-system.  That is Z-digit=[Ln(z)/Ln(B)] B-digits. We also require that the data in both systems to be equivalent. That is D_Z ºD_B, but DZ is measured in Z-digits and DB is measured in B-digits. Thus Data=D_Z =D_B Ln(B)/Ln(Z) in units of Z-digits. The time needed to transfer a z-digit or a B-digit is equal to the time of one clock cycle. Now we define the gain in transmission-time as Gtime=T_Z/T_B=D_ZT₀/D_BT₀= D_Z/D_B= D_B Ln(B)/Ln(Z)*1/D_B. Finally we get Gtime=Ln(B)/Ln(z).  

The gain in multiplexing-time "Gtime" dose not imply by any means a linear speed-up with higher radices because it measures the relative multiplexing-time of data in the z-radix system to the multiplexing-time of data in the B-radix system. For example, the Gtime(4)=50%, Gtime(8)= 33.33%, Gtime(16)=25%, Gtime(32)=20%, Gtime(256)=12.5%, Gtime(1024)=10%. This data shows that there is not much of gain as we increase the radix and shows no linear enhancement at all. 

             From the aforementioned cases, we will define a function that measures the ‘z’ system performance relative to the ‘B’ system performance on a scale of zero to 100% and call it the Performance-function.  The higher the performance the better the system is. We will define the performance function as Per(Z)=m [Ln(B)/Ln(z)]* [1-(Ln(B)/Ln(z))] where ‘m’ is a normalization factor. From the performance function, we see that as we increase “z” the multiplexing-time decreases and the pins-cut increases and as we decrease “z”, the multiplexing-time increases and the pins-cut decreases. This ensures that for any increased value of ‘z’, there is a reduction in the multiplexing-time and an increase in pins-cut, which what we desire.  

Since the performance function measures the ‘z’ system performance relative to the ‘B’ system performance, then it must satisfy the following two conditions.  (1) The performance must be zero when Z=B because the new system radix is just equal to the old system radix to be optimized and we have no performance is gained at all.  (2) The performance must be zero when ‘z’ approaches infinity because at infinity we move from a discrete system (digital) to a continuous system (analog). If we check the performance function, we find out that it satisfies these two conditions: (1) Per(B)= m [Ln(B)/Ln(B)] [1-(Ln(B)/Ln(B))]= m(1x0)=0; (2) PER(µ)= m(0x1)=0.

By letting Ln(B)/Ln(z)=x and expressing the performance function as a function of “x” we obtain Per(x)= mx(1-x)= m (x-x²). By setting the first derivative to zero and solving for the optimum digital system, we obtain from x=½=Ln(B)/Ln(z) that z=B². By finding the second derivative, we obtain Per"(x)=-2 which implies that there is a maximum gain at the point z=B².  The optimum performance at the point Zoptimum=B² is equal to m/4.  Since the largest measured value for the system performance is 100%, then we normalize the performance function by assuming it is a maximum at the optimum system. Thus, we set m=4 and the performance function becomes

Per(Z)= If we assume that “B” is the binary system and solve for the optimum system we get Zoptimum=B²=2²=4. Thus, the optimum solution that will optimize the pins-cut and multiplexing-time of binary digital systems is the quaternary digital system (radix=4).  See figure shown above, which plots Per(z)=4 [Ln(2)/Ln(z)]* [1-(Ln(2)/Ln(z))]  relative to binary system. Note that this optimum value is not an ideal value.  It may changes when we consider other factors in the analysis such as noise, control bus lines, ..etc.

            The optimum radix is equal to the square of the system radix to be optimized. One of the important aspects to note about this result is that the conversions between the two systems are direct conversions that make the interface units between the two systems fast and simple especially when a mixed radix system is considered. Also, it does not specify an absolute optimum system and gives the optimum system relative to a given system. For example, the optimum system for the binary system is the quaternary system, for the ternary system is the radix-9 system and for the quaternary system is the hexadecimal system and so on. This result agrees with the analysis of George Abraham in [4] p.395 in his statement “ For example, if n is the number of binary devices or circuits which can be integrated monolithically to form new devices which operate at radices higher than the binary (meaning optimum radix=3), then radices higher than the ternary can be more efficient both from the standpoint of storage density as well as component-wise than either the binary or ternary.”

            Hurst in [1] showed that the optimum radix is equal to e=2.718 suggesting that three-valued systems are the most economical. Out result is different from his result because he did not consider the multiplexing-time factor in his analysis and assumed that circuit complexity is linearly proportional to the system radix. According to George Abraham in [4] this assumption has to be verified and he stated in [4] “The validity of the assumption that the equipment complexity is proportional to the product of n and R must be investigated for each configuration under consideration”. Also, according to Butler in [2], practical cases do not support the linearity assumption and he stated in [2] p.v “ ... although practice would suggest something less than a linear relationship. In this case, a larger number of logic levels is optimum”. Also, Allen and Givone in [3] showed that the optimum system is strictly greater than not equal to e=2.71. Thus, the optimum result a agrees with the analysis of George, Butler and Allen.  

4- Conclusion

            In this paper we have shown how the optimum system was found based on the pinout-problem and multiplexing-time problem.  We also have shown (1) that the optimum system, relative to a given system, is given by Zoptimum=B²; (2) that the optimum system which will optimize the properties of the binary system is the quaternary system.

5- References

   1.         S.L. Hurst, “Multiple-Valued Logic-Its Status and its Future, ” IEEE trans. computers, Vol. C-33, No 12, pp.1160-1179, DEC 1984.

   2.         J. T. Butler, “Multiple-Valued Logic in VLSI Design, ” IEEE Computer Society Press Technology Series, 1991.

   3.         C.M. Allen, D.D. Givone “The Allen-Givone Implementation Oriented Algebra, ” in Computer Science and Multiple-Valued Logic: Theory and Applications, D.C. Rine, second edition, D.C. Rine, ed., The Elsevier North-Holland, New York, N.Y., 1984. pp. 268-288.

   4.         G. Abraham, “Multiple-Valued Negative Resistance Integrated Circuits, ” in Computer Science and Multiple-Valued Logic: Theory and Applications, D.C. Rine, second edition, D.C. Rine, ed., The Elsevier North-Holland, New York, N.Y., 1984. pp. 394-446.

   5.         J. L. Baer, “Computer System Architecture,” New York: Computer Science Press, 1989.