(or skip to the n-state switching introduction) The eTextbook " A reduced cost license for unlimited educational copies for named institutions, schools and companies is available. Send a request for info to admin@ternarylogic.com. George Boole's "An investigation of the Laws of Thought..."
is often cited as a beginning of machine logic. However, Boole's investigation
was into (humanly) meaningful logic expressions and not into meaningless
switching rules to be performed by a machine to accomplish a predefined
purpose. That task was achieved about 80 years later by Claude Shannon
in his MIT
Master Thesis: "A symbolic analysis of relay and switching functions."
This thesis is based on a switching algebra. Design of computer devices recognizes three main levels of design: the architecture, the implementation and the realization. My book deals with the implementation or the design of devices applying (in this case) non-binary switching functions. A brief description of the three different levels is provided in the Abstract of Dr. Blaauw's book on computer architectur.e I discovered that binary logic is actualy a limited "poor man's version" of non-binary logic. Many things are possible in non-binary logic that are not possible in basic binary design. If you like thinking about digital design you will enjoy this book. I am still developing "The N-state Switching Video eBook." The Video eBook contains a series of about 25-30 video lectures covering many aspects of the Ternarylogic LLC Intellectual Property (IP) portfolio. Each lecture covers a specific subject in n-state switching and contains a recording of the lecture with slides and illustrative programs. The programs can be run under Matlab or the open source program Freemat. One will have to purchase the lectures, which will
be copy-righted. Included with the purchase will be a one time, non-exclusve,
non-transferable, limited and personal license to the An overview of the Ternarylogic portfolio can be reviewed at www.ternarylogic.com/portfolio.pdf . Computers have become very complex machines, running on processors with millions and millions of circuits and running at clock speeds of 4GHz and higher. The programs running on these machines are even more complex, involving millions of instructions. Despite all this complexity, the stunning fact is that the basic component of all this machinery is the very basic binary switch, which switches between two states. Some people have tried to explain all this complexity from a perspective of "symbol processing." Other have tried to connect our thinking with binary logic, which is the 'language' of binary switching. No matter how it is all explained, the fact remains, that for over 70 years, computing devices as we know them have been based on the simplest of simple switching states: "on" and "off'." This has resulted into a very strange way of approaching computing problems: we first break down problems into very basic statements or instructions and then we re-assemble all these basic statements back into complex statements to run our applications. In many cases, the complexity of the applications leads us to an anthropomorphic approach of machinery and project into it human capabilities. But, computing is still basically "on" and "off" switching, no matter how it appears to us. The subject of computing and logic poses deep philosophical and epistemological issues. However, computing is also a profoundly technical issue. One question that occurs to most "engineering types", among which I count myself, is around the matter of non-binary switching. Binary technology appears to be a given, a fundamental approach to allow a machine to perform instructions. It also appears to be limiting. Just two states? To automate all our thought processes? What would one be able to do with a machine that performs non-binary switching? What would it require? What would it look like? How does one apply it? This website provides some answers. The subject of Multiple-Valued Logic (MVL) is a well studied one. This article of Elena Dubrova provides some background. Even though the article is well written, It may all seem to be quite complex. Despite all kind of philosophical and theoretical musings non-binary switching can be reduced to the simple technical issue of generating a signal according to a non-binary switching rule.
This web page was created a while ago. It is still correct. However, at the time I was concerned about the relation between "switching" and "logic." It seemed to me that "logic" had a higher value than the down-to-earth "switching." This concern has largely disappeared. Logic herein is switching and it is deterministic switching. There is no fuzziness here. Other types of switching (or logic) are known, but will not be dealt with herein. The focus is nonbinary machine logic which provides the switching functions for physically implementing nonbinary computers and processors. I am currently not maintaining or updating this web page. It has a somewhat philosophical vision on logic and knowledge. I believe these are important and fascinating subjects, but they are of less relevance to the hard engineering "switching approach" that I now apply. I gladly refer interested parties to the web page www.nstatelogic.com, which I update on a regular basis. Another technical web page is www.lfsrscrambler.com, where I describe n-state LFSR based scramblers and descramblers, both in Fibonacci and in Galois configuration. Yet another webiste that is n-state related is www.nstatefield.com and deals with n-state finite fields or Galois fields. Certain affairs that have my interest are described on www.lemmatalogic.com and have almost nothing to do with n-state switching. Many of my ideas on n-state switching are novel, useful and non-obvious and thus may be granted a patent. A list of over 30 patents and patent applications can be found on the Ternarylogic website. The patents and patent applications thereon are linked to USPTO publications and provide probably more details than you want or can digest in a single session. A complete overview of the Ternarylogic portfolio is provided in this portfolio overview.
Logic on this instant site is defined as implementing a single input/single output or a two input/single output n-valued truth table, wherein an input can have one of n states and an output can have one of n states; n being an integer of 2 or greater. Selecting n as an integer is only for practical purposes and to facilitate arithmetical operations. A more formal approach would be: an n-valued logic has n different states, each state having a unique identifier.
In general new concepts can be difficult to grasp. They may challenge old concepts in such a way that a whole new way of learning appears to be required. A way of learning that seems to be out of reach for most people. For instance who knows how a system for digital cellular mobile telephony works? Amazingly few people actually do. Not because it is horrendously difficult, but because of the large number of parts and steps involved. It is for most people just too time consuming to master all the aspects. Most people actually want to know about new, exciting concepts and get a feeling for why something works and how to obtain some of the benefits. The problem with most of the new ideas again is the significant number of steps one has to follow. This may create a feeling of not understanding how a result was achieved, because one cannot trace it back to the initial ideas and axioms. In most cases explanations of new concepts may leave even well educated people in a confused state rather than in an enlightened state. The here presented concepts on multi-state switching are very easy to learn and to apply. No special math is required. The logic applied here is a switching logic that is deterministic in nature. Some signals go into a circuit and a signal leaves the circuit. One only needs to know the truth table that describes the circuit. No math, no electronics, no physics are required. Yet, with the very simple tools provided here one can create extremely powerful applications, more powerful than with existing binary switching. It may be hard to believe that extension of binary logic with one or more states can make such a huge difference, but is does. So there is reason for significant excitement: not only because of the power of the new concepts here provided, but also because of how easy to understand these concepts are.
It is assumed that binary logic is a sub-class of an n-state logic system. To keep things simple (yes, really) the n-state switching functions are limited to one-input/one-output and two-input/one-output n-state switching functions. The term multi-valued is used, but value really has nothing to do with logic. In fact we probably should use the term symbol processing. For the sake of convenience and compatibility with binary logic the term Multi-valued Logic or MVL will be applied. MVL is currently applied in error correction coding on CDs, CD-ROMs and DVDs. The amazing capability of optical disks to deal with scratches and surface imperfections is based on the application of a 256-valued Reed Solomon code, wherein each symbol is represented as an 8-bits word. While standard coding theory uses Finite Fields to explain and manipulate codes, MVL can also be used and provides significant novel results. It is probably fair to say that a combination of MVL and GF theory provides a highly effective tool-set in coding. While coding is an application of MVL, it is not the subject of this web site.
Many believe logic to have a meaning. Logic as presented
here will be dealt with as a rule or rather a set of rules that act upon
input states and will create output states. You may call it switching
logic or switching algebra or switching rules. This prevents you from having to look for a meaning of the states. There is none. Examples provided on this site have significance because they may have useful applications, not because they have a deeper meaning.
Multi Valued Logic circuits can be implemented using CMOS micro-electronic technology. One company: Omnibase Logic, based in Austin, TX actually develops and builds MVL electronic circuits in CMOS. The applied technology is called SUS-LOC and was developed and patented by Dan Olson. More information can be found at www.omnibaselogic.com . Carbon nanotubes are another high interest approach for realizing multi-valued logic functions. Other methods such as Negative Differential Resistance (NDR) circuits may also be used for creating multi-valued logic functions.
There is actually an area where logic and meaning have
a mathematical significance. That is in the area of arithmetic. The connection
between switching logic and arithmetic is of course fortunate as it enables
computing circuits. However it also obfuscates the real possibilities
of the multi-valued switching logic. This aspect is beyond the scope of
this site. However readers should be aware that multi-valued switching
finds wide application in error correction coding and decoding. Via a
mathematical trick (by defining extension Galois Fields) one can create
non-binary switching functions that can be realized in binary form. This
is applied in for instance Reed Solomon coding and decoding. One may actually
simplify GF(n) problems by applying an MVL approach. This aspect is part
of a series of pending patents that are beyond the discussion here. - Binary logic, truth tables, functions and signals
- Problems with logic values, states and meaning
- Multi-value logic
- Multi-value logic inverters
- Binary and ternary ripple adders
- Multi-valued signal processing and multi-value logic
- The gates, switches and physics
- The multi-valued latch
- What can you do with it ?
- The strangeness factor
- An analogy
- Patents and Patent Applications
- Sudoku Rules
**LFSR Scramblers/Descramblers**- Contact
The following figure shows a signal a=[0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1]. The shown signal consists of 16 individual binary elements or bits. Another binary signal is b=[1 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0]. The following figure shows the signals 'a' and 'b' applied to the binary function 'NOT EQUAL' realizing the expression:
The VB program can be downloaded in ZIP form by clicking here or on the screenshot. This demonstrates how to apply non-binary logic. Keep in mind that the values 0, 1 and 2 are assigned by us and are not inherent to ternary logic. They can for instance be -1, 0 and +1, which is useful in balancing the DC component of the signals, without changing the essence of the logic functions.
In ternary logic there are three states, which we named '0', '1' and '2'. The inversion of state '0' can be '1' or '2'. The most useful inversion is one that can be reversed. For instance the inversion of '0' can be '2' and the inversion of '2' can be '0'. That leaves '1' to have itself as an inversion. The inversion of the signal a=[0 1 2] would then be a'=[2 1 0]. And the inversion of a' is a''=[0 1 2]. It is not uncommon to hear people assert that the limitations of MVL are caused by the lack of physical multi-value switches. There appears to be some truth to that. But contrary to popular belief we do not need some new exotic physical switching mechanism to realize ternary or multi-valued logic functions. There are sufficient known electronic mechanisms to build any required multi-valued logic functions by applying a limited number of gates. This raises then the question how MVL switching functions have to be selected and configured to realize an MVL latch. It turns out that the MVL latch is an extension of the binary latch. But it is a somewhat unexpected extension. Luckily one can actually create MVL memory element using fewer switching elements. These configurations can be viewed in one of my patent applications. The current or classic latch configuration is selected as example because it is in the same class as the binary latches. The following figure shows a configuration of a 4-valued latch. It is comprised of 4 identical 4-valued switching devices 'latch4', configured in feed-back connection. The circuit has 4 inputs, In_1, In_2, In_3 and In_4. The output Out of the second device is used as the output of the complete Latch. The truth table of the 4-valued device 'latch4' is provided in the following truth table. The way this Latch works is as follows: inputs [In_1 In_2 In-3 In_4] can assume the following values [0 3 3 3]; [3 0 3 3]; [3 3 0 3]; [3 3 3 0] and [3 3 3 3]. The input [0 3 3 3] generates Out=0; The input [3 0 3 3] generates Out=1; The input [3 3 0 3] generates Out=2; The input [3 3 3 0] generates Out=3; The input [3 3 3 3] generates Out= previous Out; Clearly this latch requires translation circuitry to transform a to be retained input value in a combination of 0 and 3s. The output of the second device is selected as system Out, because on this output a not inverted output is generated, as compared to the input. The input state [3 3 3 3] is the neutral state. That means when the inputs are switched to that state, the output generated by the previous input state is retained. The neutral state and the input states are identified using a switching model and selected because it allows for switching of just one input to neutral. One can switch from [3 0 3 3] to [3 3 3 3] by just changing the state on one input. One may switch from [3 0 3 3] to for instance [3 3 3 0] without adverse effects. The output value Out will just change from 1 to 3 with some uncertain intermediate states. However the system will stabilize on the required end value. It is possible to find switching functions that have stable outputs with a larger difference than 1 state between the inputs. Physically that means that several input values have to change at the same time. Failure to switch in an exactly synchronous manner to the neutral state may create unwanted stable intermediate states, and upset the 'latch' performance. One can easily recognize the standard binary latch in this. In a way the result is somewhat disappointing because it requires an inordinate number of switching devices. Fortunately one can create much more compact two-function and even one-function MVL devices with feed-back to realize MVL memory elements. Related to designing the MVL latches is a switching model that will be needed to find the appropriate MVL functions. It has been disclosed in one of my patent applications.
MVL allows us to do things that are not possible in
binary logic and we can achieve them in many more ways than in binary.
MVL functions can be very useful in applications such as line-coding,
data-scrambling, sequence generation for wireless applications, arithmetical
engines, and for what probably would be called digital control and MVL
combinational applications. The details of these applications are beyond
the scope of this introductory web site. However these applications have
been developed, simulated in software, tested and validated. Please take a look at www.ternarylogic.com/portfolio.pdf for an overview of the portfolio. The 9x9 Sudoku matrix is a set of 9 orthogonal reversible 9-valued inverters. Such an inverter is also a sequence of 9 different symbols put in a pseudo-random fashion in the sequence. One can generate such a sequence from a maximum length sequence of 3-valued symbols generated by a word method using 9 overlapping words of 2 ternary symbols. Such a sequence cannot be generated by an LFSR. By replacing each word with its decimal equivalent one then obtains the sequence of 9 different symbols. This sequence can be interpreted as a transposition rule. By performing the transposition rule upon itself and upon the transposition results one can obtain 9 different orthogonal sequences. One can apply this method using a ternary m-sequence of 26 symbols, and thus generating a 26x26 Sudoku matrix of 26 orthogonal sequences of 26 different symbols.
They are called "impossible" figures, which show drawings that appear to be physically impossible.
The Escher drawings appear to be more impossible because of the depiction of a pseudo-physical environment. Feedback in
some cases appear to represent an impossible situation. The following
diagram shows a Linear Feedback Shift Register scrambler with a corresponding
descrambler. (taken from US Patent Application Publication Ser. No. 20090138535.) Yes, that is correct: you need to correctly descramble symbols to correctly descramble. An impossible figure? Not at all. It actually works beautifully, as is demonstrated in the following Matlab/Freemat program. The delay formed by the shift register makes this work. The LFSR (which may be binary or non-binary) in this case is in Galois configuration and is not self-synchronizing. This requires that the initial state of the shift register in the descrambler is identical to the initial state of the shift register of the scrambler. In the following
implementation only sc1, sc3, sc4 and ds4 are considered. To Run: d) for the
4-state case first run the scrambler 'novscramlfsr4gala' to scramble and
Another feature of the above scrambler/descrambler is its public/private mode. In the binary case the function sc4 can be a XOR function whereon an all zero ([0 0 0 0 ...0]) sig_key sequence is provided. This makes sc4 transparent as the output of sc4 provides the same symbols as it received from sc1. For instance it makes the inclusion of sc4 in the descrambler unnecessary. By modifying sig_key to for instance a pseudo-noise sequence, the descrambler, if it did not apply sc4, is no longer able to correctly descramble the scrambled sequence. The same approach can be applied in non-binary or n-state scramblers/descramblers, for instance by using as sc4 a function represented by a standard addition over GF(n). Examples Feel free
to play with the attached programs for educational purposes only. Please
keep in mind that a patent is pending on this subject.
[TOP] |
||