N-state Switching with N greater than 2



	N-State Switching © 2005-2011 Copyright Peter Lablans. All rights reserved You may use the contents of this website for non-commercial purposes only. Acknowledgement of copyright is required. Please note that marked patent protected Intellectual Property is contained within this document. 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. Preface This web site provides an introduction to concepts in n-state or multi-valued switching or logic. It has become quite long, which has happened unintentionally. As a shortcut one may jump directly to the Table of Content by clicking here. One can jump back to the Table of Content by clicking on the title of a chapter. Skip or ignore the math parts on this site if you find it confusing. These are meant to clarify, but are not essential in understanding the switching aspects. The following detailed articles explain aspects around n-state switching: www.nstateswitch.com - explains implementing an n-state truth table; www.nstatememory.com - develops n-state switching based memory latches; www.nstatemultiply.com - an example how n-state switching can accelerate arithmetical circuits; www.lfsrscrambler.com - several n-state implementations of self-synchronizing descramblers; www.nstatelfsr.com - about LFSR based sequence generators; and www.nstatefield.com - brief introduction to n-state finite fields and alternate finite fields GF(n). Values and states The use of numerical values to represent a logic state implies that a logic state has a value or represents a value. This aspect is further enhanced by using 2-state or binary switching functions to evaluate modulo-2 arithmetical expressions. The use of the word logic further carries the very charged value of 'true' and 'false.' However, a logic or switching circuit knows of no value: it only has one of n states. A signal that represents a state may have a certain value, for instance 1 Volt or 2 Volt. However, the value may also be for instance a light wavelength such as 'red' or 'blue.' It is somewhat unusual to call 'blue' a value, though there is no reason why 'blue' cannot be a value. It is also preferred to emphasize that n-state switching is in essence a technical implementation. While multi-valued logic also can reflect a technical implementation, and is intended to do so herein, many people provide a 'deeper' meaning to logic, be it binary or multi-valued. Both multi-valued logic and n-state switching functions herein are defined by truth tables and inverter tables and thus are the same. To emphasize the technology aspect of n-state switching, n-state and n-state switching is preferred, though multi-valued and logic are still used herein. Switching functions and input values Advantages of multi-valued switching over binary switching are often explained by comparing higher radix number representation with radix-2 or binary representation. If a memory cell can store a single digit, then it is easy to see that a "decimal" memory cell is more efficient than a radix-2 memory cell. The decimal cell can store digit 0, 1, 2, 3, 4 , 5, 6, 7, 8 or 9. For a binary memory to store the digit 9 at least 4 binary individual cells are required. ( decimal 9 is binary 1 0 0 1). Some quick calculation shows that radix n representation is 2log n more efficient than binary representation. While that is not bad, it is not very exciting. A second and more advantageous aspect is the number of switching functions that exist in an n-state or n-valued switching system. The number of 2-input switching functions increases exponentially with n. This site is focused on the switching functions not on number representation. The n-state switch An n-state switch with n>2 herein is a device with at least one input that is enabled to receive a signal that has one of up to n states and an output that provides a signal that has one of at least 2 states and up to n states. [The "up to" will probably be confusing. It is not required to define all n of the input signal states. For instance, a two-input/single output 5-state device may receive at each input only states 0, 1, and 2 and generate on an output the modulo-5 sum (0, 1, 2, 3 and 4) of the input states. In that case the output has more potential states (5 states) than any of the inputs (3 states). In a further example one may have a two-input/single output 5-state device that compares the input states and provides a 0 when a <b, a 1 when a = b and a 2 when b> a. In that example the output only has one of 3 states, while each of the inputs may have one of 5 states. In both examples an input state is equated with a modulo-n number.] If the n-state switch has only one input it may be called an inverter or n-state inverter. People sometimes get confused by that term because of the use of 'binary inverter.' One may also apply the term 'n-state converter.' The n-state switch may also have at least two inputs and at least one output and may be defined by the name of the function it performs, such as modulo-n addition, greater than function, multiplication over GF(n) or just by a symbol such as 'sc.' One may define an n-state switching (or logic) function by its n-state switching table. One may assign symbols 'a' and 'b' to inputs and a resulting signal 'c' to an output and use a symbolic expression such as {c → a sc b} to symbolically represent the n-state switch. There is no deeper meaning intended to n-state switching by this web site. It is merely a technical concept. State '0' does not mean 'no', state '1' does not mean 'yes' and state '2' does not mean 'perhaps' or 'don't know.' No limitation is implied to what a 'signal' is. It may be an electrical signal, it may be an optical signal, it may be the presence of a material, it may be a quantum-mechanical state of a material, it may be a mechanical state of a device. One of n-states may be a magnitude based linear variant of a signal, such as a voltage. It may also be a non-magnitude based occurrence of a phenomenon, such as wavelength dependency of an electro-magnetic wave. Logic on this web-site is used in the sense of a switching rule. A truth table expresses a switching rule. Multiple-Valued Logic (MVL) is a well established scientific discipline. There is a long and documented history of MVL theories and concepts. Unfortunately, in many instances MVL is reduced to Fuzzy Logic. MVL has its own organizations, for instance inside IEEE as the Multiple-Valued Logic Technical Committee of the IEEE Computer Society. This group organizes an annual symposium on the state of MVL which will take place on May 23-25, 2011, in Tuusula, Finland. Unfortunately, this group is very much theoretically oriented and does little to explain MVL to the masses or even to explain MVL to interested individuals. There appear to be overview articles that are published by IEEE which are only accessible by members and/or for payment it seems. It is probably fairly easy to visualize a 2-input/1-output n-state switch, if one puts a little effort into it. This web site hopefully will be helpful in that effort. It may turn out to be much more difficult to visualize a static n-state memory device that is based on n-state switching functions. It is entirely possible to develop a device that 'stores' an n-state signal based on a feedback configuration, which may be called an n-state RAM. Such a device is not obvious and requires some efforts to understand. N-state RAMs are different from known n-state memories that work by storing an electrical charge, which may be called n-state DRAMs. Different implementations of n-state RAMs can be found in this issued patent and this published patent application. Introduction When I tell people about non-binary or multi-state switching, especially people who are at least somewhat familiar familiar with the concept of binary switching, they get excited. They tell me how they at some stage have wondered what non-binary switching would look like. What does it look like? What does it do? And most importantly: how is it different from binary switching? This website provides at least some answers to the above questions, without going into an expansive theoretical analysis. Another question that is often asked is: can non-binary switching applied in a useful way? An answer to that important question is also provided. In binary logic one may use a device with 2 inputs and one output. Such a device may realize for instance an AND function. A diagram of such a device having inputs A and B and output C is shown below. The relationship between A, B and C may be provided in an expression (A AND B) = C. Another and more commonly used way is to provide a truth table of the AND function. This truth table is provided below. The inputs A and B can each assume one of two states: 0 or 1. For each combination of A and B the AND function will generate a state for C. The state of C is shown under the horizontal line and right to the vertical line in the truth table. One can see for instance that for A=1 and B=1 that C=1. For all other combinations of A and B the state of C is 0. The values above the horizontal line and left of the vertical line only serve as a reference to the input states. The term "state" is used. One may also use the term "value". The above circuit may be called a two-valued or a binary circuit, and its corresponding truth table a 2-valued truth table. The signals A and B may assume one of 2 states of values (0 or 1). Another term for 2-valued is binary. The 2-valued or binary truth table is a 2 x 2 matrix. In n-state logic or n-valued logic signals are used that may assume one of n values or n states with n>2. An n-valued truth table has n input values on input A and n input values on input B. This means that the truth table is an n x n matrix. The following shows an example of a 4-valued logic function, being defined as ADDMOD4 or the modulo-4 adder. The circuit is shown below. The truth table of the function is shown below. The truth table of this function is a 4 x 4 matrix. A signal in a 4-valued or 4-state logic can assume one of 4 possible states or values. This is really all the fundamental knowledge required for n-state switching. Truth tables may show some particular or useful properties. Finding and applying these properties is one of the purposes of n-state switching. Many people wonder if this expansion of states or values is allowed or possible. The answer is : yes, it is allowed. There is no fundamental reason why one should be limited to only two possible states for a signal. Content of this site An effort has been made to keep things simple. Some theory has to be applied, but readers probably are already familiar with most of the concepts. 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 White Papers Sudoku Rules Addition and Multiplication Tables in GF(2^m) N-state Spread Spectrum Sequences Switching Algebra The curious case of the n-valued partial product carry N-state sequence synchronization and correlation Contact 1. Binary logic, truth tables, functions and signals Binary logic describes the switching behavior of a binary (electronic) switch. Such a switch has two input signals ('a' and 'b') and one output signal ('c'), as shown in the next figure. A property of the input and output signals is that they all can assume one of two values in general given as '0' and '1'. The shown switch executes the binary 'exclusive or' or 'NOT EQUAL' function. This means that the output c is '1' if 'a ≠ b'. Or if written for all possible combinations of 'a' and 'b': - If 'a = 0' and 'b = 0' then 'c' is 0 (because 'a' and 'b' are equal). - If 'a'= 0' and 'b = 1' then 'c' is 1 (because 'a' and 'b' are not equal). - If 'a'= 1' and 'b = 0' then 'c' is 1 (because 'a' and 'b' are not equal). - If 'a = 1' and 'b = 1' then 'c' is 0 (because 'a' and 'b' are equal). These 4 combinations of 'a' and 'b' represent all possible combinations for 'a' and 'b' in binary logic. Usually the relation between possible input and output values are depicted in a matrix form called 'truth tables'. The following figure shows the truth table for the binary 'NOT EQUAL' function. The possible values of the inputs 'a' and 'b' are the coordinates for the output 'c'. The input values of 'a' and 'b' are '0' or '1'. The possible values of the output 'c' are also '0' and '1'. There are 4 possible input combinations: (0,0), (0,1), (1,0) and (1,1). Each output can assume 2 different values. So there are 2 x 2 x 2 x 2= 16 possible different output combinations and consequently also 16 different binary 'truth tables'. These describe 16 different binary logic functions. The following figure shows all 16 possible binary truth tables. For some functions (or truth tables) it does not matter if 'a' is 0 and 'b' is 1 or 'a' is 1 and 'b' is 0. Or the input state (0,1) is identical with (1,0). The truth tables are then symmetrical over their diagonal axis. These functions are called commutative. The addition of two numbers 'a' and 'b' is an example of a commutative function: a+b= b+a. If a function is not commutative it is called non-commutative. An example of a non-commutative function is a>b. If 'a' is greater than 'b' then 'b' cannot be greater than 'a'. Commutativity in a logic function is more readily demonstrated in expressing it in an assignment expression. The 'exclusive or' or 'NOT EQUAL' function can be expressed as: c → a ≠ b which is equal to: c → b ≠ a . The right arrow is used as an assignment character to distinguish from the equal character '=' which is a logic function. The switching logic that is expressed in formulas is generally known as Boolean logic, and is named after George Boole. Claude Shannon realized that Boolean expressions represented the switching performance of electric relay circuits. He presented his ideas in his Master Thesis "A symbolic analysis of relay and switching circuits" at MIT in 1936. Shannon in this thesis provides several example circuits, such as a counter, and a ripple adder. Binary signals Binary signals are designated as being '0' or '1'. This does not mean that the corresponding signals are actually 0 Volt and 1 Volt. What it means is that the signal has two distinguishable and different levels and we just name them '0' and '1'. 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: c → a ≠ b. It also shows the resulting signal 'c'. 2. Problems with logic states, values and meaning Binary logic is the recognized foundation for computers and logic circuits. It is so well entrenched in our thinking and accepted as the fundament of logic that the binary concepts that were supposed to merely explain and clarify the application of binary logic now largely dictate our understanding of logic. For instance 1 and 0 are 'known' to be equivalent to 'true' and 'false'. And the logic '1' is equivalent with the arithmetical '1', that is why computers can do calculations. This is not incorrect, but there are some qualifications to that statement: 1. electronic binary signal voltage levels are 'low' or 'high' 2. 'low' levels are called '0' and 'high' levels are called '1' 3. the truth table of the binary '≠' switch coincides with the modulo-2 addition function 4. the '≠' function is assumed to be identical with the modulo-2 addition 5. the logic '1' is assumed to be identical to the arithmetical '1' and the logical '0' is assumed to be identical to the arithmetical '0'. There is no fundamental reason why we cannot make the '1' state equivalent to the arithmetical '2'. This seems far fetched. However in digital wireless communications the logic '0' is set as equivalent to the arithmetical '-1' to calculate correlation properties. In general we consider '0' and '1' as fundamental properties of switching logic. By assigning these values to logic states we have given meaning or value to (what essentially are) meaningless logic states. This is a two-edged sword. It helps us work with binary logic, but it also limits our capability to look beyond binary logic. Mainly because concepts like 'true' and 'false' or 'on' and 'off' have no equivalent in multi-value logic. Even more serious trouble arises around concepts like inversion of states or values. In binary logic the opposite of '1' is '0'. Or the opposite of 'true' is 'false'. It is reasonable to assume that if '0' is 'false' and '1' is true that '2' as a third state has to mean something like 'perhaps'. But 'perhaps' as we understand it is no state. And we also do not have an inversion for it. States in reality are meaningless. They are just what they are: names or labels for something that is different from something else. Also there are limited ways to get from one state to another one by applying logic. To say that states are meaningless does not mean that they are useless. It just means that they do not have any inherent value or meaning. To clarify the concept of a 'meaningless' state the following figure shows the truth table for the binary '≠' function. However the binary logic states are now 'green' and 'red'. Another example is to use '3' and '5' as designated states. These truth tables have little significance beyond describing some switching mechanism. When we can look at binary logic as 2-state switching with arbitrarily named states it becomes much easier to accept 3-state switching as ternary logic without worrying what these states may signify. 3. Multi-value logic Multi-value logic is defined as a non-binary logic and involves the switching between more than 2 states. We will assume that multi-value logic devices will be limited to 2 inputs/single output functions. A ternary or 3-value logic function is one that has two inputs which can assume three states (say 0, 1 and 2) and generates one output signal that can have one of these three states. Symbolically a ternary device 'ter' looks the same as a binary one with two inputs and one output. The truth table of a ternary device looks different from a binary one as there is one more state to deal with. The following figure shows the truth table of a ternary logic function. This function is commutative (as it doesn't matter if we exchange the 'a' and 'b' inputs). It pretty much looks the same as binary logic, but there are some major differences. Binary logic has 16 different functions. Ternary logic has 3x3x3x3x3x3x3x3x3= 19,683 different functions of which 729 are commutative. For illustrative purposes the following Visual Basic program may be used. It executes a non-commutative ternary logic function. The inputs can be changed and the program will generate the correct output states. The truth table will identify the correct state. To make the distinction between value and state the input and output signals are color coded. The VB program can be downloaded in ZIP form by clicking here or on the screenshot. Ternary signals Ternary input and output signals can assume one of three levels. Consequently they have more 'information content' than binary signals. The following figure shows the ternary signal a= [2 1 0 1 1 0 2 0 2 2 1 2 0 1 0 2]. The following figure shows the ternary input signals 'a' and 'b' and the ternary output signal 'c' of a ternary logic device executing ternary logic function 'ter'. 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. The same approach can be applied to other non-binary logics, such as 4-value logic. The number of possible 4-value logic functions is around 4 billion. 4. Multi-value logic inverters It may seem that multi-value logic is similar to binary logic just with more states and functions. While this is in part true it would ignore fundamentally different properties of multi-value logic compared to binary logic. It is not the purpose of this web page to provide an in-depth analysis of multi-value logic. However one aspect that must be pointed out is the use of state (or value) inversion in multi-value logic. In binary logic each of the two states '0' and '1' has one inversion. The inversion of '0' is '1' and the inversion of '1' is '0'. Each state has the other as its inversion. This is of course not possible in non-binary logic. An arithmetical approach to inverters in an m-valued logic in the literature is provided by the formula: x = (m-1) - y In this formula y is the 'original' value and x is the 'inverted' value of y. Much of the literature uses this approach and you will see in many articles that x = [ 2 1 0] is used as the standard ternary inverter of y = [0 1 2]. There are several unsatisfactory aspects to this definition, here are three of them: a. logic states are being defined on the basis of assigned values b. not every ternary state can be 'inverted' into another ternary state c. this inverter is of limited use State based ternary inverters 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]. Another ternary inversion is where '0' is inverted to '1', '1' is inverted to '2' and '2' is inverted to '0'. The ternary signal a=[0 1 2] has then as its inversion a'=[1 2 0]. The inversion of a' is a''=[2 0 1] and the inversion of a'' is a'''=[0 1 2]. The term inversion in this context is a bit problematic. We are all familiar with inversion as a concept in arithmetic and number theory. In number theory inversion is directly connected with the zero or "null" element. Its existence is one of the axioms for a Field in an Abelian Group under addition. That means that an element 'x' has as inversion an element '-x' such that in addition: (x) + (-x) = 0 . Because we apply logic to execute arithmetical operations such as addition there is ample opportunity to mix and confuse concepts in logic and arithmetic. However in logic we can define a reversible inversion as a state transformation, with such properties that a state transformed at least 2 consecutive times by an inversion will reach its original state. Ternary logic has 6 reversible inverters (including the identity). This offers an opportunity for executing certain operations that cannot be done in binary logic, especially related to scrambling of signals and generating of non-binary sequences with some very specific properties. These and other applications are subjects of pending patents with the US Patent and Trademark Office. 5. Binary and ternary ripple adders Arithmetic and especially addition is often used as an example to demonstrate how binary logic can be "usefully" applied (ignoring the significance of the "control" capabilities of binary logic). This is where we have to provide meaning to states. Applying binary logic to adding two numbers in a base-2 counting system (or radix-2 addition) means that logic state '0' represents the number 0 and the logic state '1' represents the number 1. Adding in radix-2 now looks very much like adding in base 10, as we will apply the same rules: 1. create two numbers in base-2 notation 2. add the numbers base-2 or modulo-2 3. determine if the added numbers create a base-2 carry 4. create two numbers: the modulo-2 addition and the carry results 5. start again at item number 2 of this list and continue until no carry digits are left This means that two different binary functions are needed: the modulo-2 addition which is the same as the binary 'NOT EQUAL' function. And the 'determine if carry is 1' function, which is the binary 'AND' function. The same process can be applied to a base-3 or ternary adder. The following figure shows a screen shot of a ternary full adder applying ternary logic functions. The program also executes in parallel a binary adder, so you can compare the number of cycles to complete an addition. It also allows to compare the ripple effect of the carry in ternary and binary addition. The VB program executing the adder functions in ternary and binary form can be downloaded in zipped format by clicking here or on the figure. Please note that only input values up to 35 are correctly displayed. 6. Multi-value signals, signal processing and multi-value logic In general multi-value logic or non-binary logic is positioned as a technology that can execute arithmetical functions faster and with less interconnect than binary logic. Further more non-binary data storage would require less physical space than binary data. This is especially important as we are starting to distinguish in the future the limitations of binary logic in silicon. Even before we see the sunset of binary silicon technology we already are running into other capacity constraints, such as limitations of available bandwidth and spectrum in cable and wireless communications, data storage, processing of noisy signals, watermarking and other signal processing oriented requirements. The application of multi-value (non-binary) digital signals can provide considerable relief of capacity constraints. Applying multi-value logic to the processing of multi-value digital signals can also greatly improve the quality and the cost of multi-value digital signal processing. Strangely enough multi-value digital signal processing can be done in binary logic, by processing the multi-value symbols as binary words. This principle, well documented but not generally known, is applied in for instance line coding for digital transmission. In the 1980s we saw the appearance of 4B3T codes. In this line-coding scheme a 4 bits binary word is translated into a 3 ternary elements ternary word. Even though the transmission takes place in ternary symbols, all processing such as scrambling and descrambling currently is done in binary logic. The great disadvantage of this approach is the requirement for word synchronization, coding overhead and maintaining a Running Digital Sum. Multi-value line-coding offers an immediate increased use of bandwidth and clearly is worth the cost of processing ternary symbols as binary words. Currently, the capacity of channels is greatly enhanced by using multi-state modulated transmission signals. In these signals, a signal represents an n-state symbol. The transmission of digital HDTV signals may take place in multi-state modulated signals such as QAM-64 and QAM-256. In general one may create a QAM-n signal. QAM stands for Quadrature Amplitude Modulation. Herein, each of n states is assigned a location in a constellation that is determined by an amplitude and a phase. The following image shows a 16 point rectangular QAM-16 constellation. This image is taken from a Wikipedia site that provides further background on multi-state modulation. Other n-state modulation techniques also exist. While signals are transmitted as n-state symbols, signal processing is completely binary. 7. The gates, switches and physics 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. Recently new technology has been invented (such as SUS-LOC) that allows for direct implementation of multi-value inverters in standard CMOS silicon. SUS-LOC was invented and patented by Dan Olson as USPTO Patent 6,133,754 . Olivier Sentieys and his group at the University of Rennes have applied this technology in designing a basic ternary Digital Signal Processor. A search on the Web as well in patent databases such as the USPTO 's will provide a whole range of possible physical realizations of MVL switches. In general, an n-state switch is realized by applying a physical phenomenon wherein a level of the phenomenon determines a state. Such a magnitude based phenomenon is often an amplitude or intensity of a signal. Signal processing or switching technology for implementing an n-state switch involves some addition mechanism. For this reason, for instance two different states cannot exist at the same time at an input or output of an n-state switch. In a novel approach, non-magnitude based switches are provided, wherein a representation of one state cannot be created by merely adding representations of two other states. The background of the invention of such switches is described in U.S. Patent 7,548,092, entitled "Implementing logic functions with non-magnitude based physical phenomena." 8. The multi-valued latch Anyone who has designed a logic circuit knows that at certain times sequential circuitry is required. These usually come in the shape of flip-flops or latches. The interesting part about latches is that they work because of the applied switching functions (such as NANDS), not because of the selected switching technology. 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-state latch. It is comprised of 2 identical 4-valued switching devices 'latch4', configured in feed-back connection. The circuit has 2 inputs, In1 and In2. The output Out1 of the first device may be used as the output of the Latch. A truth table of a 4-state latch is provided in US Patent 7,397,690. This patent also provides the causal switching model that allows to determine the appropriate n-state switching functions to make a latch work. This US Patent can be downloaded by clicking here. One can easily recognize the standard binary latch in this, though its working is different. 9. What can you do with it ? Interesting stuff this MVL, but can you do something useful with it? Yes...One can for instance create multi-valued scramblers, descramblers, sequence generators and sequence detectors with the tools here provided. It is beyond the scope of this page to explain the intricacies of LFSRs. However a self-running Powerpoint presentation can be downloaded, that contains embedded VB examples applying MVL. You can download it by clicking here. If you don't have Powerpoint you can download a free viewer from here. Unfortunately the viewer does not activate the VBA macros. In order to run the actual VBA programs you will have to 'enable macros'. The following screenshot shows one of the actual programs. It shows a 4-valued Galois scrambler and the corresponding 4-valued self-synchronizing descrambler. It also shows how the LFSR is 'flushed'. The presentation is zipped. Unzip the file, and enable macros for playing the program in Slide Show Mode. Please keep in mind that scramblers and descramblers that are marked are protected by U.S. Patents. You are allowed to use the presentation with the embedded programs "as is". The presentation is provided for educational purposes only. No license for implementing and/or using the protected scramblers and/or descramblers is provided or applied. Contact Ternarylogic LLC to obtain a license. You are not allowed, nor are you licensed to use, modify, copy, implement, sell or distribute any of the protected Intellectual Property disclosed herein. 10. The strangeness factor There is a strangeness associated with MVL. It seems that binary logic is much more natural and intuitive. It is quite common to show '0's and '1's in TV commercials, or advertising related to Internet applications or computers. It appeals directly to our intuitive recognition of current and advanced technology. Binary logic (or logic for that matter) is NOT a law of nature. The reason why binary logic seems more natural is because we have been more exposed to it. The feeling of strangeness in MVL disappears once you start working with it. There is no inherent conflict with binary logic once a familiarity with the concepts has been established. There are much "stranger" and very intriguing (non-classical) logics out there. From that perspective MVL is more like an extension of binary logic and very conventional, though broader in possibilities. In fact when MVL will be applied on a larger scale we predict that the MV will be dropped from the MVL and the subject will be known as Logic. 11. An analogy To give an example of things that are possible in ternary logic but not in binary logic we will provide the following analogy: We can compare binary logic with driving in Manhattan, and are only allowed to drive straight or turn right. Under those conditions there are Targets we will not be able to reach. We will be able to reach those Targets if we are also allowed to turn left. Check the correctness of this in the following figure. 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. 12. Patents and Patent Applications Is this stuff useful, or is it merely an exercise for the brain? That is a question we often hear after explaining the concepts of MVL. But yes, it really works. How one can realize MVL circuits and what applications one may want to realize in MVL is the subject of a series of Patent Applications. These patent applications have already been published by the US Patent and Trademark Office and can be downloaded in PDF file by clicking on the title. The patent applications are of a set of over 30 inventions. Some of the inventions are pure multi-valued. Others, such as the one on convolutional codes, also deal with binary applications. Another interesting application is number 15 which explains the relation between Fibonacci and Galois LFSRs. Some relevant applications are: 1. Single and composite binary and multi-valued logic functions from gates and inverters; 2. Ternary and multi-value digital signal scramblers, descramblers and sequence generators; 3. Generation and detection of non-binary digital sequences; 4. Ternary and higher multi-value digital scramblers/descramblers; 5. Encipherment Of Digital Sequences By Reversible Transposition Methods; 6. Sequence detection by multi-valued coding; 7. Multi-valued digital information retaining elements and memory devices; 8. Multi-value digital calculating circuits, including multipliers; 9. Multi-valued scrambling and descrambling of digital data on optical disks and other storage media; 10. Sequence detection by multi-valued coding and creation of multi-valued sequences; 11. Binary digital latches not using only NAND or NOR circuits; 12. The Creation and Detection of Binary and Non-Binary Pseudo-Noise Sequences Not Using LFSR Circuits; 13. Methods And Apparatus In Finite Field Polynomial Implementations; 14. Error Correcting Decoding For Convolutional And Recursive Systematic Convolutional Encoded Sequences; 15. Binary And N-Valued LFSR And LFCSR Based Scramblers, Descramblers, Sequence Generators and Detectors In Galois Configuration. 13. White Papers A series of white papers on aspects of MVL inventions have been created and can be downloaded. Visitors to this site should be cautioned that much of the disclosures in the articles are covered by Patent Applications. Publication of the articles is for educational purposes only. No license for application of the disclosures is granted by this publication. Such a license can only be obtained in writing from Ternarylogic LLC. All rights to the Intellectual Property are reserved and owned by Ternarylogic LLC. Basic n-valued approaches 1. N-valued switches. 2. N-valued inverters. 3. Realizing n-valued logic functions. 4. Reducing n-valued logic functions with inverters. 5. Reducing z = ax +by in n-valued logic. A limited set of applications 1. A general LFSR based descrambler model. 2. A switching model for binary latches. 3. LFSR based sequence detectors. 4. PN generators, not using LFSRs. 5. Improved detection of binary sequences by multi-valued coding. 6. "DON'T CARE" functions in equivalent logic expressions. 7. Logic circuits with gates and inverters in 'chained' expressions. 8. What if one plus one is seven? 14. Sudoku rules 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. 15. Addition and Multiplication Tables in GF(2^m) Addition and multiplication in binary extension fields can be created from a Galois Field generated from a primitive polynomial of degree m of n=2. How to do that is fairly well documented. Addition and multiplication in GF(2^m) can be reduced to binary operations. This is actually a substitute for performing the actual addition and multiplication in GF(2^m). That may be the reason why it is difficult to find actual truth tables of addition and multiplication over GF(2^m). As a service truth tables for addition and multiplication over GF(8), GF(16), GF(32), GF(64) and GF(256) are provided here. You may download the files by clicking here. The truth table for addition over GF(128) can be generated by creating a table using as inputs a first word of 7 bits and a second word of 7 bits and as output the XOR-ed two words as a third word of 7 bits. As a next step one has then to substitute the decimal value for a binary word. Depending on requirements or preferences one may work with origin 0 or origin 1, keeping in mind that all additions over GF(2^m) are self-reversing. The truth tables are provided in a zipped Excel spread sheet format. The extension 0 in the file name means that indices and states in such a file are using origin 0. Extension 1 means that indices and states are using origin 1. IMPORTANT: The truth tables have not been checked extensively. One will use the tables at his or her own risk. No liability for any mistakes is accepted. Please provide feedback if any errors are identified. Please keep in mind that the order of assigned 'values' or 'states' may not coincide with the values of GF(2^m). One may generate simple tables by substituting an n-state with its binary representation. The integer order of these states may not represent the order of states in GF(2^m). Remember: states in GF(2^m) are generated by an LFSR. 16. N-state Spread Spectrum Sequences Spread-spectrum technology is at the heart of current wireless transmission. Herein in essence a logic symbol such as a '0' or a '1' is replaced by a sequence of '0's and '1's. If a sequence is not intended for a tuned receiver, such a receiver will consider a sequence as noise. By applying correlation means, a tuned receiver finds a sequence to which it is tuned. For such a receiver an intended sequence "sticks out" significantly above the noise of other sequences. Sequences that apply n-state symbols instead of binary signals differentiate themselves much better from the background noise. For instance one may generate a binary Pseudo-Noise (PN) Maximum sequence of 1023 bits. The following graph displays the auto-correlation graph of such a sequence. One may create a set of sequences from this sequence, in which each sequence is a shifted version of the original sequence. It is known that these sequences are orthogonal. For instance one may create a set of 24 of the above shifted sequences. All the sequences may be superpositioned and will create a noise signal. The cross-correlation of a sequence that is shifted, but that is not in the noise is in one calculation about -24. However, the correlation of such a sequence when it is also part of the noise is about 1000. This is a very good differentiation. The following graph shows a auto-correlation graph of a 4-state PN sequence of 1023 symbols. One can easily see that the peak of such a 4-state graph is higher than of the binary sequence. One may again create a set of 24 orthogonal sequences and superpose them into noise. In such a case a correlation factor of a sequence that is not in the noise (also called cross-correlation) is about -630. When the sequence is in the noise, the correlation is about 2180. This is a significantly better differentiation. One may apply similar calculations to larger sets of sequences with up to 1023 sequences. The 4-state sequences will demonstrate superior differentiation. The above approach requires of course strict synchronization. Somewhat less differentiating are Gold sequences. However, they also require less strict synchronization. Again, n-state sequences will demonstrate superior performance. 17. Switching Algebra While Boole is famous for Boolean algebra, he was actually best known in his time for his methods of solving differential equations. Boole reduced logic expressions to algebraic expressions by working with concepts such as "true" and "false". The Boolean algebra as applied in switching expressions (or switching algebra) is an invention by Claude Shannon and presented in his MIT Master Thesis in 1936. Shannon provides in his thesis several example circuits such as a counter, a ripple adder and a factor and prime table generator including a control circuit. Shannon mentions in his thesis developments in using more than 2 logic states. Switching algebra and Boolean algebra appear to avoid using truth tables as a form of proof. There is no reason not to rely on truth tables. Switching functions and switching expressions can generate only a finite number of states. Sometimes the number of states is very large. Clearly, in such a situation is may be beneficial to provide algebraic proofs of expressions. Proof by truth table is as good as an algebraic proof. 18. The curious case of the n-valued partial product carry Arithmetically, multiplication is the repeated addition of a multiplicand. Algorithmically, multiplication is the repeated calculation of a partial product, containing a residue and a carry. After calculating the partial products, one has to create the end product by adding all partial products. A simple example is the multiplication of a variable multiplicand consisting of 2 radix-n digits [x1 x2] with a constant multiplier consisting of 2 radix-n digits [a1 a2]. This multiplication is written out in its components below. x1 x2 a1 a2 x C(a2* x2) R(a2x2) C(a2x1) R(a2x1) C(a1x2) R(a1x2) + ....... {R(a1x2) + R(a2x1)}......... Herein R means the modulo-n residue and C means the modulo-n carry. There are several intermediate components that have to be calculated and then added. From the above, one can see that at least a sum of two residues R(a2x1) and R(a1x2) and a sum of two carries C(a2x1) and C(a1x2) have to be determined. Commonly, one may perform these tasks by first determining the first residue and the first carry (two functions) and the second residue and second carry (also two functions), which can be performed at the same time. One then adds the residues (two functions: one for the residue of the sum, and the carry) and in parallel the two carries (two functions, one residue of the sum and one carry of the sum of the carries). One is not done yet, as a carry may ripple through. So, one requires at least one additional function and step. This means that the entire operation of determining a carry and a residue of a sum of partial products may require up to 3 steps and 9 functions. Assume that the above is a radix-4 multiplication. It is clear from the above that one has first to determine R(a2x1) and R(a1x2) and then add these partial products. So, in order to work towards the product one has to perform at least three steps. In fact there may be more steps as (33) + (33) in radix-4 will generate 18 in mod-10, which is [1 0 2] in radix-4 notation. The carry ripples in this case requiring up to 3 steps to determine a partial product sum. One can see that determining a partial product sum in the radix-4 case may generate two carries and one residue. Rather than evaluating all steps individually, one may determine all digits in one step using a specific n-state switching function for determining each digit in the partial product sum. This is shown in the following illustrative diagram for determining a sum (2.x1 + 3.x2). Traditionally one would first determine residue and carry for 2.x1 and 3.x2 and then determine the sum, including a potential ripple. One may illustrate the reduction of truth tables in the following radix-4 example. The traditional modulo-4 addition truth tables R4 for the residue and C4 for the carry are provided. The following tables show the modified truth tables in accordance with the multipliers of the n-state logic functions that provide the residue Rm of the expression 2.x1 +3.x2 and the carry Cm1 of the expression 2.x1 + 3.x2. One may apply a radix-n Carry Save Add (CSA) and Carry Look Ahead (CLA) to further speed up the addition of the partial products. Please, be aware that apparatus that performs the herein described n-state machine multiplication is covered by U.S. Patent 7,562,106. No license to implement the machine multiplication is provided or implied for any user of this website. Such a license can only be provided by Ternarylogic LLC in writing. 19. N-state sequence synchronization and correlation* A sequence of symbols is a series of usually consecutive symbols. This may be a sequence of 5 binary symbols such as [1 0 0 1 0] or a sequence of 7 4-state symbols, such as [0 2 3 3 1 2 0]. In practice much longer sequences are used. A symbol in a sequence may be represented by a single signal. For instance a 1 may be a signal and a 0 may be absence of signal. Or a 1 may be a signal of 1 Volt and a 2 may be a signal of 2 Volt. A state may also be represented by a signal having an amplitude and a phase. One may also consider a series or a word (by itself a sequence) of binary symbols as a symbol. In that case, on may represent a sequence of p n-state symbols (with n>2) by a sequence of k binary symbols (with k = cp, and c being the word length). Sequences of symbols are widely known and are used in many applications. Commonly, one applies sequences of binary symbols. In general, one applies at least two sequences repeatedly in such a matter that the sequences may form a longer sequence. In such as case one usually wants to know where or at what moment a specific sequence starts (and ends). It is thus required to find where a sequence begins and which of at least two sequences one is dealing with. For instance, assume that one has two binary sequences twice: [1 0 0 1 0] and [0 1 1 0 1] which have been received as [1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0]. Detecting the correct sequence requires two steps: 1. find the symbol where a sequence begins; 2. detect which of the two sequences was present. For simplicity it is assumed that all sequences are of equal length and that no errors have occurred in any of the symbols. Correlation* A well known method for detecting a sequence is correlation, whereby all symbols of a known sequence are compared with a received sequence of symbols. In general, correlation is defined as a value created from multiplying values assigned to corresponding symbols in two sequences and adding all the products to a single correlation value. For instance, one may detect in [0 1 1 0 1] in [1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0]. Commonly, one assigns the value -1 to 0 and +1 to 1. The correlation works as follows: [1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0] [0 1 1 0 1] -1 -1 -1 -1 -1 -1= -5; [1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0] [0 1 1 0 1] +1 -1 +1 +1 -1 = 1; [1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0] [0 1 1 0 1] +1 +1 -1 +1 +1 = 3; [1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0] [0 1 1 0 1] -1 -1 -1 -1 +1 = -3; [1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0] [0 1 1 0 1] +1 -1 +1 -1 -1 = -1; [1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0] [0 1 1 0 1] +1 +1 +1 +1 +1 = +5; It is easy to see that the sequence [0 1 1 0 1] is detected when the correlation value is +5. N-state m-sequence generators There are several ways to generate "attractive" sequences which easily distinguish themselves. One set of sequences is generated by Linear Feedback Shift Registers (LFSRs) and are known as maximum-length sequence generators. The following diagram shows a binary LFSR based sequence generator with 6 register elements that can generate a maximum length binary sequence (m-sequence) of 63 bits. The "not equal" sign represents a binary XOR function. The generated sequence is: out=[111011001101010111111000001000011000101001111010001110010010110] when the initial content of the shift register is [0 1 1 0 1 0]. The correlation of the sequence out with shifted versions of itself (generally called the autocorrelation) is shown in the following graph. One may actually change the "correlation rule". For instance, one may add 1 to a sum when corresponding symbols are identical and leave a sum unchanged if two corresponding symbols are different. Such a rule will lead to the following graph. One may arbitrarily change the rule: for instance add 2 when corresponding symbols are identical and subtract 1 when symbols are different. This generates the following autocorrelation graph. The following diagram shows a 4-state LFSR based sequence generator. The LFSR has 4 4-state shift register elements. It also has two 4-state logic functions "XOR4", which are adders over GF(4). The last shift register element is connected to an input of the XOR4 function through a 4-state inverter INV4. This sequence generator generates a 511 4-state symbol m-sequence. The generated 4-state sequence is provided in the following sequence: out4 = [3 3 1 2 0 0 0 3 3 3 0 2 0 1 3 0 1 0 1 0 2 3 1 3 3 3 2 0 2 1 2 0 2 2 1 3 2 0 1 2 1 0 0 2 0 0 2 1 1 3 1 2 3 3 3 3 1 3 1 1 0 0 3 1 1 2 2 1 1 0 2 1 3 1 3 2 2 3 0 1 1 0 1 2 0 1 1 2 3 0 0 0 1 1 1 0 3 0 2 1 0 2 0 2 0 3 1 2 1 1 1 3 0 3 2 3 0 3 3 2 1 3 0 2 3 2 0 0 3 0 0 3 2 2 1 2 3 1 1 1 1 2 1 2 2 0 0 1 2 2 3 3 2 2 0 3 2 1 2 1 3 3 1 0 2 2 0 2 3 0 2 2 3 1 0 0 0 2 2 2 0 1 0 3 2 0 3 0 3 0 1 2 3 2 2 2 1 0 1 3 1 0 1 1 3 2 1 0 3 1 3 0 0 1 0 0 1 3 3 2 3 1 2 2 2 2 3 2 3 3 0 0 2 3 3 1 1 3 3 0 1 3 2 3 2 1 1 2 0 3 3 0 3 1 0]. One may generate a "classical" autocorrelation graph of the sequence by multiplying values assigned to the symbols. For instance symbols [0 1 2 3] correspond to values [0 1 2 3]. One multiplies the values of corresponding symbols and adds these values to generate a correlation value. Such a classical correlation value is shown in the following graph. One side effect of the "classical" correlation method is the occurrence of side peaks. Furthermore, generating the correlation is computationally expensive, as many multiplications have to be performed. A simpler way of generating a correlation graph is to compare corresponding symbols in sequences and, for instance, add a number (say 1) when symbols are identical, and for instance, add nothing when symbols are different. This will generate the following correlation graph. This correlation graph is cheaper to calculate and is easier to interpret. An n-state m-sequence detector To constantly determine correlation numbers between sequences may be an expensive operation. A novel way to detect an n-state m-sequence is to use a modified n-state LFSR based descrambler. For instance, the 4-state sequence as generated above may be detected with the following detector. The 4-state function may have the following truth table. The detector generates a sequence detect of all 1s or of almost all 1s on its output when out1 is provided on the input. The detector is in self-synchronizing mode. This means that if the initial state of the shift register is not identical to the initial state of the generator a series of 4 0s and 1s may be generated before the shift register is flushed and the detector starts generating all 1s. One advantage of this detector is that one does not have to run the detector for all 255 symbols in out1. One may decide that the sequence out1 is detected when for instance 25 consecutive 1s are generated. This detector is not sensitive to the phase of sequences if they are generated by the same generator but with different initial LFSR states. One should change the configuration to a non-self-synchronizing Galois configuration if sequence phase detection is important. The above methods provide very simple synchronization means for instance if only one sequence is received, such as a sequence on a magnetic or an optical disk. The above is provided for educational and informational purposes only. Aspects of the above methods and apparatus are disclosed in U.S. Patent No. 7,580,472 issued on August 25, 2009 entitled Generation and detection of non-binary digital sequences. The specification of this patent also discloses additional methods and apparatus, for instance for generating Gold or Gold-like sequences. No license to any aspect of this US Patent is provided or implied by this website. Use of the invention is strictly prohibited. Only a written approval from Ternarylogic LLC can provide a license to use the invention. 20. Contact ©2010, Peter Lablans. All rights reserved. You may use the content of this site for private use only. If you use any of this site's content you have to acknowledge it as: Source: "N-state switching " at "www.nstatelogic.com", author Peter Lablans. No further permission for private use only is required. Commercial use of all or any of the aspects of this site is strictly prohibited. For educational and commercial use please contact admin at ternarylogic dot com. Further information on Ternarylogic LLC and its portfolio can be found at www.ternarylogic.com [TOP]