# XOR Multiplexing Technique for Nanocomputers
## 3 Bifurcation Analysis of the XOR Multiplexing System  
Multiplexed systems contain two types of organs. The first type is the executive organ, which performs the desired basic operations on the bundles. The second type of organ is the restoring organ, which uses the redundant information available from the input bundle to provide more reliable information on the output bundle. Any logic gates, like the NAND gate, NOR gate, AND gates and OR gates, effectively alternate critical inputs (which produce critical errors) and subcritical inputs (which produce subcritical errors), thereby performing error correction. Among them, the NAND gate restoring organ is the first two-layer restoring organ with effective error correction ability. As shown in Figure 5, the XOR multiplexing system is composed of the XOR executive unit and NAND restoring organs. In order to make the system stable, multiple restoring organs would be necessary. Note that the odd stage number is necessary to keep the XOR function. In order to derive the error threshold value for two-input XOR gates and two-input NAND gates, the circuit schematic shown in Figure 6 is involved. As can be seen, the circuit schematic is a binary tree of cascaded two-input unreliable XOR gates and NAND gates [14; 23]. Assume that the XOR gates and NAND gates have the same error probability \(\varepsilon\) of making a von Neumann error, and their input lines and output lines function reliably. Let us denote the probabilities of the two inputs of the XOR gate  
Figure 4: The output error distributions of \(n\) stages XOR multiplexing and NAND multiplexing. Figure 5: XOR multiplexing system. being stimulated by \(X\) and \(Y\). Since there are no feedback loops and fan-out in the circuit, the two inputs can be treated as independent. Then, the probability of the output of XOR gate being stimulated is  
\[Z_{1}=(1-\varepsilon)[X(1-Y)+Y(1-X)]+\varepsilon[XY+(1-X)(1-Y)] \tag{5}\]  
In the following analysis, we shall first assume that this circuit is a discrete time system. Then, further assume that all inputs to the XOR gates are independent and have the same probabilities, \(X\) and \(Y\), of being stimulated. This structure not only guarantees that the inputs to all NAND gates at an arbitrary stage \(n\) are also independent but also guarantees that they have equal probabilities of being stimulated, which we denote to them by \(Z_{n}\)[14]. Thus, for the second stage, the first stage of the NAND gates, the probability of the output being stimulated is  
\[Z_{2}=\varepsilon{Z_{1}}^{2}+(1-\varepsilon)\big{(}1-{Z_{1}}^{2}\big{)}=(1- \varepsilon)+(2\varepsilon-1){Z_{1}}^{2} \tag{6}\]  
For such a construction, Equation (6) reduces to a simple nonlinear map  
\[Z_{n+1}=(1-\varepsilon)+(2\varepsilon-1){Z_{n}}^{2} \tag{7}\]  
In order to discover the dynamic behavior of the map, bifurcation analysis is used to analyze Equation (7) [23]. For any fixed \(0\leq\varepsilon\leq 1/2\), we choose an arbitrary initial condition \(X\), \(Y\) and then iterate Equation (7) until, after a sufficient number of iterates. it converges to an attractor. Those attractors are then plotted against each \(\varepsilon\)[14; 23]. This leads to a nonlinear map called a bifurcation diagram and the diagram is shown in Figure 7 (\(\Delta\varepsilon=0.001\)). This nonlinear map contains two kinds of attractors, fixed-point solution and periodic motion. The period-doubling bifurcation occurs at bifurcation point \(\varepsilon_{*}\). When \(\varepsilon_{*}\leq\varepsilon\leq 1/2\), the system has a stable fixed-point solution; by solving the equation \(z_{0}=(1-\varepsilon)+(2\varepsilon-1){z_{0}}^{2}\), we get  
\[z_{0}=\frac{1-\sqrt{1-4(2\varepsilon-1)(1-\varepsilon)}}{2(2\varepsilon-1)} \tag{8}\]  
By stable, it means that for any arbitrary initial inputs condition \(X\) and \(Y\), the output \(Z_{n}\) will converge to \(z_{0}\) when \(n\) is large. In other words, in this region, the system no longer functions as XOR.