Home News Links Search Feedback Software Elements Researches AOP Degeneracy GTODE Implementations Optimum Download
 Paper-1 TOC-1 Tables Figures Computer Symbols Researches
 Degeneracy Paper-1 Paper-2 Paper-3 Paper-4 Researches
 GTODE Paper-1 Paper-2 Paper-3 Paper-4 Researches

 Contents Abstract, Introduction, pinout analysis, multiplexing-time analysis, optimum radix, Example-1, Example-2, Plot See Also index,

In
Multiple-Valued Logic Systems

By
Abu-Msameh, R. K.

Abstract

The aim of this paper is to present a solution to the optimum radix problem in multiple-valued logic systems.  This paper solves for the optimum radix problem based on the pinout-problem and the multiplexing-time problem of digital components. The paper shows that the quaternary digital system is an optimum solution.  Unlike other solutions provided in current literature, the method of this paper solved for the optimum solution as an exact integer number equal to four.  The solution does not round off its result to the closest integer as in the case of some current solutions in the literature

Keywords: Multiple-Valued Logic Systems, Optimum Radix, Quaternary.

The Optimum Radix In
Multiple-Valued Logic Systems

1- Introduction

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 Zoptimum=B2.  By setting B=2 which corresponds to the binary system and substituting in the optimum equation. (Zoptimum=22=4) we found that the optimum system that will optimize the binary system is the quaternary system.

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 Nz and in the B-radix system by NB and the difference between the two numbers denoted by Ncut where Ncut=NB-Nz. In order to compare the two components in both systems we define the gain in pins-cut between the two systems as Gpins-cut=Ncut/NB. From the preceding equation we have Gpins-cut=(NB-Nz)/NB. Since the component in the B-radix system has a bus with “NB” lines, then this bus must have an equivalent bus in the z-radix system with “Nz” lines so that both buses handle the same amount of data. In order to satisfy this equivalence condition, we have to have ZNz=BNB. By taking the natural log of both sides we obtain NzLn(z)=NBLn(B). By solving for the ratio Nz/NB we obtain Nz/NB=Ln(B)/Ln(z) and substituting in the Gpins-cut we obtain Gpins-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  DB B-digits (ex.  21 bits) and the data size in the z-radix system is given by DZ 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 T0. The total multiplexing-time for the data in the B-system is given by TB=DBT0 and for the z-system it is given by Tz=DzT0. 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 DZ ºDB, but DZ is measured in Z-digits and DB is measured in B-digits. Thus Data=DZ =DB 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=TZ/TB=DZT0/DBT0= DZ/DB= DB Ln(B)/Ln(Z)*1/DB. 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.

 Example-2: Consider B=2 and Z=8. Assume we have 255-bits stored in a component in the B-system. Using the equation Z-digit=Ln(z)/Ln(B) B-digits we get Octal-Digit= Ln(8)/Ln(2)=3 Bits, which is a well known fact: one octal digit=3 bits.  Thus, the 255-bits can be stored by 255/3=85-OctalDigit(OD) in the octal system. A single bit is transferred by one clock cycle and a single OD is transferred by one clock cycle. Thus, we need 255T0 seconds of transmission time in the binary system while we need 85T0 seconds of transmission time in the octal system.  The gain in transmission time is given by Gtime=TZ/TB=85T0/255T0==85/255= 0.333333=33.33% which is the same as Gtime=Ln(B)/Ln(z)= Ln(2)/Ln(8)=33.33%. See illustrative figure below.

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.

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.

 General Information: Ramadan Copyright © 2000 GTODE on Internet Designed by: R. K. Abu-Msameh Last modified: OCT 5, 2011 IEEE International Symposium MVL Logic Technical Committee MVL  International Journal.