Ternary Bibliography

Part of http://www.cs.uiowa.edu/~jones/ternary/
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

W. Alexander, The Ternary Computer, Electronics and Power (10) 2, Feb. 1964.

One of the first clear expositions of ternary computing, including the demonstration of the theoretical optimality of base e and the observation that ternary comes closer to this limit than binary. Introduces balanced ternary notation and gives the truth tables for a ternary adder, along with a proposed implementation. Ends with a discussion of a simple ternary "flip flap flop."

C. Babbage, Passages from the Life of a Philosopher, Longman, Green, Longmand Roberts & Green, London, 1864; 59-63 and 114-116.

The performance penalty of ripple-carry adders is clearly identified, described as successive carriage. The term anticipating carriage is introduced to refer to a mechanism that allowed the construction of a faster adder.

J. Bustoz, A. Feldstein, R. Goodman and S. Linnainmaa, Improved Trailing Digits Estimates Applied to Optimal Computer Arithmetic, Journal fo the ACM, 26 (4), Oct. 1979, 716-730.

A study of round-off errors when shortening floating-point products to the same precision as the multiplicands. The probability distributions of trailing digits are investigated for different number bases, and from this, conclusions are drawn about the impact of number base and rounding rule on the mean multiplicative error. The paper concludes that base 3 is optimal, while bases "2, 4, 6 and sometimes 8, but NOT 16" can be made to perform reasobably well.

J. Connelly, Ternary Computing Testbed 3-Trit Computer Architecture, Cal. Poly., San Luis Obispo, Aug. 29, 2008.

A student project to develop a Spice simulation of an entire (albeit very small) ternary computer. Includes a good summary of the potential beneifts of ternary encoding. Appendix A gives an attempt at finding Unicode symbols for a huge variety of ternary logic operators, many of which are utterly unrelated to the conventional uses of those symbols.

D. Crockford, Base 32 Encoding, http://www.crockford.com/wrmg/base32.html, Nov. 2, 2002.

Crockford's Base32 encoding is carefully thought out to minimize the likelihood of transcription errors when using all of the decimal digits plus most of the letters as digits in a large number base. This scheme is an excellent choice for conveying large binary numbers to someone who must type in a cryptographic key, and the logic behind this system naturally extends to base 27, if that is used for large ternary numbers.

A.P. Dhande, V.T. Ingole, Design of 3-Valued R-S & D Flip - Flops Based on Simple Ternary Gates, World Acadamy of Science, Engineering and Technology 4, 2005.

A.P. Dhande, R.C. Jaiswal and S.S. Dudam, Ternary logic simulator using VHDL, 4th Intl. Conf. Sciences of Electronic Technolgies of Info. and Telcom. (SETIT), Tunisia, Mar. 25-29, 2007.

Uses a sum-of-products approach to implementing ternary functions up to the complexity of the half adder, and gives a methodology for using VHDL to model ternary logic.

A. Doostaregan, M.H. Moaiyeri, K. Navi and O. Hashemipour, On the design of a new low-power CMOS standard ternary logic gates, 15th CSI International Symposium on Computer Architecture and Digital Systems (CADS), Nov. 2010.

Gives several designs for ternary inverters differing primarily in how the middle value is driven. Alternatives include passive pull-to-center when the true and false switches both turn off, averaging with the truen and false switches both on, and active pull to a separate center voltage supply. The final design adopted uses a capacitive voltage divider. Simulations studies are presented of ternary nand and nor gates built using this design.

L.N. Đorđević, The logical synthesis of a ternary adder, Kybernetika, 3 (2), 1967, 102-103.

Gives an unsigned ternary ripple-carry full adder composed to two somewhat optimized half adders constructed of min, max and decoding gates.

M. Fitting, Kleene's three-valued logics and their children Fundamentia Informaticae, 20 (1-3), Mar./Apr./May 1994.

Introduction to Kleene ternary logic where true and false are augmented with unknown, and Belnap quaternary logic where unknown (the bottom value) is the dual of overdefined (the top value), creating a lattice. This paper has a discussion of the consensus and gullability operators. Just as and and or are duals under the exchange of true and false, So are consensus and gullability duals under the exchange of unknown and overdefined.

Gideon Frieder and Clement Luk, Algorithms for Binary Coded Balanced and Ordinary Ternary Operations, IEEE Trans. on Computers, 23 (2), Feb. 1975, 212-215.

Each balanced ternary numbers is represented by a pair of binary numbers, one holding the positive trits, the other the negative trits. Algorithms are given for normalizing, negating, and adding numbers in this representation. Multiplication and division are discussed very briefly. The authors used these algorithms to implement a ternary computer architecture on a microded binary foundation.

R. Goodman and A. Feldstein, Round-off error in products, Computing, 15 (3), 1975, 263-273.

A study of round-off errors when shortening floating-point products to the same precision as the multiplicands. The paper states that "a computer which works in a number system with an odd base and which rounds symmetrically would produce an expected round-off error of zero (clearly the minimum)." Base 3 is not addressed explicitly.

K.S. Gorde, Design and simulation of ternary logic based arithmetic circuits, Terna Eng. College e-Newsletter, 1 (2), Apr./Jun. 2010.

Ternary inverters, nand and nor gates built using passive pull-to-middle logic, and components up to the complexity of balanced ternary full adders. Includes CMOS circuit layouts of Ternary inverters, nand gates and a full adder, all designed for operation from ±5V.

G. Hang and X. Zhou, Novel CMOS Ternary Flip-flops Using Double Pass-Transistor Logic, Int. Conf. on Electric Information and Control Engineering (ICEICE), Apr. 2011.

IBM, IBM 7040 and IBM 7044 Data Processing System Student Text,, 1963, page 66.

The technique used for doing BCD arithmetic on a binary machine described here also works for doing binary-coded ternary arithmetic on a binary machine.

Rogier Jacobsz, The Cylindric Algebras of 4-Valued Logic, MSc Thesis, Universiteit van Amsterdam, Aug. 31, 2011.

Quaternary logic, as in Fitting, 1994. This paper has a discussion of the consensus operator.

Douglas W. Jones, BCD Arithmetic, a tutorial, web site, 1999.

The BCD arithmetic algorithm described briefly in IBM, 1963 is refined and presented in additional detail, breaking it free from archaic assembly languages and making it more accessible to generalization to other number bases.

Douglas W. Jones, Reciprocal Multiplication, a tutorial, web site, 2002.

The division tricks described briefly in Magenheimer, 1987 are presented in additional detail, with worked examples for a variety of divisors.

A.S. Kumar and A.S. Priya, Minimization of Ternary Combinational Circuits -- A Survey, Int. Jour. of Engineering Science and Tech. 2 (8), 2010, 3576-3589.

Any ternary function can be realized by decoding the inputs and then using the outputs of the decoder to select logic levels, but the focus of this work is on the use of ternary multiplexers to implement arbitrary functions, with the goal of minimizing the number of multiplexers used.

S. Lin, Y.B. Kim and F. Lombardi, A novel CNTFET-based ternary logic gate design, Proc. IEEE Int. Midwest Symp. Circuits Syst., pp.435-438 , Aug. 2009.

A carbon nanotube field-effect transistor implementation of a ternary inverter, with the switching thresholds of each transistor determined by the nanotube diameter (3 distinct diameters are used); a complementary FET design takes 6 transistors. Mass production of such devices may be problematic.

Daniel J. Magenheimer, Liz Peters, Karl Pettis, and Dan Zuras, Integer multiplication and division on the HP precision architecture, Proc. 2nd International Conf. on Architectual Support for Programming Languages and Operating Systems, IEEE Computer Society Press, Los Alamitos, 1987, Pages 90-99.

The HP PA-RISC computer did not include multiply and divide in its core instruction set because the amount of logic required for hardware implementations of these operations gave greater performance benefits if applied elsewhere. This was possible because the basic instruction set included a shift-and-add instruction (with arbitrary shift count) allowing multiplication and division by common constants in remarkably few instructions). The same tricks turn out to be applicable on ternary computers.

G.A. Maley and J.L.Walsh, Basic Ternary Logic Circuits, U.S. Patent 3,660,678, May 2, 1972.

After introducing ternary logic and enumerating all 27 functions of one variable, bipolar transistor logic circuits are given (using an eccentric schematic notation) that can be configured to implement any of the 27 functions.

Henry Massalin, Superoptimizer: a look at the smallest program, Proceedings of the second international conference on Architectual support for programming languages and operating systems (ASPLOS II), published as ACM SIGARCH Computer Architecture News 15 (5), 1987, 122-126.

Appendix I.5 is the first presentation of an extraordinarily optimized algorithm for BCD to decimal conversion. This code generalizes to other number bases, including binary-coded ternary to binary conversion and ternary-coded-binary to ternary conversion.

Roy D. Merrill, Jr., Ternary Logic in Digital Computers, DAC '65 Proceedings of the SHARE design automation project, 1965, 6.1-6.17.

General state-of-the art in ternary logic as of 1965, with a good discussion of the application of threshold logic to ternary computing.

H.T. Mouftah, A study on the implementation of three-valued logic, Proceedings of the sixth international symposium on multiple-valued logic, May 1976, 123-126.

An introduction to ternary logic and a brief exposition on the implementation of arbitrary switching circuits using CMOS implementations based on resistive voltage dividers to arrive at a middle value when both high and low switches are turned on.

H.T. Mouftah (misspelled Moufah by the patent office), Ternary Logic Circuits with CMOS Integrated Circuits, U.S. Patent 4,107,549, Aug. 15, 1978.

Using CMOS circuits with resistive voltage dividers as in Mouftah, 1976, this patent presents basic logic gates and then uses them to implement ternary flipflops and static-RAM memory cells.

R. Muskens, On partial and paraconsistent logics, Notre Dame Journal of Formal Logic, 40 (3), 1999, 352-374.

Belnap quaternary logic and variants.

Behrooz Parhami and Michael McKeown, Arithmetic with Binary-Encoded Balanced Ternary Numbers, Proc. 2013 Asilomar Conference on Signals, Systems and Computers, Nov. 3-6, 2013, Pacific Grove, CA, 1130-1133

The focus is on binary coded balanced ternary, but there is a brief discussion of ternary carry-lookahead adders. The brief discussion of balanced ternary multiplication suggests fast parallel implementations. The brief discussion of balanced ternary division significantly oversimplifies the quotient digit selection rule by suggesting that it should be the same as that used in binary nonrestoring division.

F. Prosser, X. Wu, X. Chen, CMOS ternary flip-flops and their applications, Computers and Digital Techniques, IEE Proceedings E-135 (5), Sep. 1988, 266-272.

G.B. Rosenberger, Simultaneous Carry Adder, U.S. Patent 2,966,305, Dec. 27, 1960.

Binary adders with a carry anticipation tree are described.

E. Sipos and C. Miron, Master-Slave Ternary D Flip-Flap-Flops With Triggered Edges Control, Int. Conf. on Automation Quality and Testing Robotics (AQTR), May, 2010.

A.B. Taylor, Report on Weights and Measures, Pharmaceutical Association, 8th Annual Session, Boston, Sept. 15, 1859, 41

This paper includes a wide ranging discussion of different number bases, and with a very consistent naming scheme that includes binary and ternary, but uses octonary, denary and senidenary to refer to what we now call the octal, decimal and hexadecimal number systems.

X.W. Wu and F.P. Prosser, CMOS ternary logic circuits, Circuits, Devices and Systems, IEE Proceedings G-137 (1), Feb. 1990, 21-27.

Discusses the voltage-divider and passive pull-to-center models for arriving at the middle value in the output of ternary logic circuits, along with CMOS binary coded to ternary encoders and ternary to binary decoders. The utility of the latter in implementing arbitrary ternary functions is demonstrated, with simulation results showing that the transfer characteristics of the resulting gates are reasonably good.

T.L. Rodeheffer, Software Integer Division, TR 2008-141, Microsoft, Aug. 26, 2008 Discusses a variety of algorithms for binary integer division. Some of these are very fast and it may be possible to convert some of them to operate in ternary.

M.Yoeli and G.Rosenfeld, Logical Design of Ternary Switching Circuits, IEEE Trans. on Electronic Coputers, EC-14 (1), Feb. 1965, 19-29.

Discusses ternary generalizations of the Karnauch map and tabular approaches to minimizing ternary logic functions into minimal sum-of-products form.

Giuseppe Talarico, Codifica di valori Ternari in Eptaventesimale, October 2013.

This exposition of the heptavintimal number system (in Italian) draws heavily from the discussion of heptavintimal numbers here, while not citing it.