Implication Logic

3.2 Implication Logic

Figure 3.2.:

Circuit topology of the TiO $2$ memristive implication logic gate.

Recently, it has been shown that a fundamental Boolean logic operation called material implication (IMP) is naturally realized in a simple circuit (Fig. 3.2) combining a conventional resistor and two TiO $2$ memristive switches [75, 76]. This provides stateful logic where non-volatile memory devices are used as the computing elements.

Material implication (IMP) is a fundamental two-input (e.g. $s$ and $t$ ) Boolean logic operation ( $s → t$ ), which reads ‘ $s$ implies $t$ ’ or ‘if $s$ , then $t$ ’, and is equivalent to ‘(NOT $s$ ) OR $t$ ’ ( $s-+ t$ ) as shown in Table 3.1. The symbols $s$ and $t$ are chosen as they represent the logic states of a source (S) and a target (T) memory element in the stateful logic gate. The operations IMP and NIMP (negated IMP) form a computationally complete logic basis in combination with any operation from the sets C and $C′$ , respectively, for which $C = {NOT, FALSE, XOR, NIMP }$ and $C ′ = {NOT,$ $TRUE, XNOR, IMP }$ and are therefore able to compute arbitrary Boolean functions.

Besides the AND, OR, and NOT operations, the IMP operation has been classified by Whitehead and Russell as one of the four basic logic operations in 1910 [160]. However, by modeling Boolean logic with circuits built with relays and switches, Shannon founded modern digital electronics [161] only based on AND, OR, and NOT operations due to their straightforward implementation. Since then, the IMP operation has been ignored in digital electronics. Only recently, it was demonstrated that memristive switches intrinsically enable the IMP operation in a crossbar array [75].

Table 3.1.:

Truth tables of the basic implication operations, IMP and NIMP (negated IMP).


State	s t	s $→$ t	$------ t → s$

1	0 0	1	0

2	0 1	1	1

3	1 0	0	0

4	1 1	1	0

Table 3.2.:

Realized conditional switching behavior is equivalent to the operation IMP or NIMP depending on the definitions for the high and low resistance states (HRS and LRS) as logical ‘0’ and ‘1’.


	Implication operation		HRS $≡$ 0, LRS $≡$ 1		HRS $≡$ 1, LRS $≡$ 0

	(conditional switching)		t $′$ $= s → t$		t $′$ $------ = t → s$

State	s t	s $′$ t $′$	s t	t $′$	s t	t $′$

1	HRS HRS	HRS LRS	0 0	1	1 1	0

2	HRS LRS	HRS LRS	0 1	1	1 0	0

3	LRS HRS	LRS HRS	1 0	0	0 1	1

4	LRS LRS	LRS LRS	1 1	1	0 0	0

Fig. 3.2 shows the circuit topology of the TiO $2$ memristive implication logic gate [75] combining two TiO $2$ memristors, $S$ and $T$ , with a conventional resistor $RG$ . The initial resistance states of the source ( $S$ ) and target ( $T$ ) memristors (denoted by the logic variable $s$ and $t$ , respectively) are the logic inputs of the gate. The final resistance state of $T$ after performing the logic operation ( $′ t$ ) is the logic output of the gate. Performing the logic operation ( $t′ = s → t$ ) involves simultaneous application of two negative voltage pulses, $VSET$ and $VCOND$ , to the non-common terminals of $S$ and $T$ . $V COND$ is a negative voltage with smaller amplitude than $V SET$ ( $|V | > |V | SET COND$ ). Therefore, the voltage drop on $S$ is smaller than $VON$ (the voltage level required for memristor high-to-low resistance switching) and it remains unchanged after the operation for any input patterns. However, depending on the resistance state of $S$ , the voltage $VCOND$ changes the voltage level on the common terminal of $S$ and $T$ ( $V G$ ) and modulates the voltage drop on the target memristor $T$ . This provides a conditional switching behavior in $T$ , which is shown in Table 3.2. In fact, the negative voltage pulse $V SET$ enforces a high-to-low resistance switching of $T$ only, when both memristors are initially in the high resistance state (State 1). The voltage $V SET$ has a higher amplitude compared to $V ON$ as it must compensate the voltage drop on $RG$ .

According to Table 3.2, depending on the logical definitions for the memristor low (LRS) and high (HRS) resistance states, LRS $≡$ logic ‘1’ and HRS $≡$ logic ‘0’ or vice-versa, the realized conditional switching behavior is corresponding to the IMP or NIMP (negated IMP) operation (Table 3.1). In accordance with the convention of Shannon, if we define HRS $≡$ 1 and LRS $≡$ 0, the logic output of the implication gate corresponds to the NIMP operation as

{t^′ = t NIMP s}≡t → s ≡{t^′ = t.s = t AND ss},

(3.1)

where $′ t$ is the final state of the variable $t$ after the operation. In combination with the low-to-high resistance switching, which corresponds to the TRUE operation (writing logic ‘1’) according to the above definition, the NIMP operation forms a complete logic basis to compute any Boolean function. Therefore, it enables stateful logic operations by memristive devices used simultaneously as non-volatile memory and logic gates [75]. For instance, stateful universal NOR and NAND operations can be performed in three and five sequential steps as Eq. 3.2 and Eq. 3.3, respectively.

Step 1 (TRUE) :	a = 1
Step 2 (NIMP) :	a → b ≡{a^′ = a.b = b}
Step 3 (NIMP) :	a → c ≡{a^′ = a.c = b.c = b + c = b NOR c}	(3.2)

Step 1 (TRUE) :	a =1
Step 2 (NIMP) :	a → b ≡{a^′ = a.b = b}
Step 3 (NIMP) :	c → a ≡{c^′ = c.a = c.b}
Step 4 (TRUE) :	a =1
Step 5 (NIMP) :	a → c ≡{a^′ = a.c = c.b = b NAND c}	(3.3)

Here, $a$ ( $a ′$ ) represents the initial (final) logic variable equivalent to the resistance state of a third memristor storing the logic result of intermediary logic steps and the final result of stateful NAND and NOR operations. It should be noted that each logic variable (e.g. $a$ ) used as an input in Step $i$ is equal to the final logic value ( $′ a$ ) from the previous step (Step $i - 1$ ) since it has been directly stored in a non-volatile memory element (A).

[next] [prev] [prev-tail] [front] [up]