# XOR Multiplexing Technique for Nanocomputers
## 2 Error Distributions in the XOR Multiplexing System
### Error Distributions in the XOR Multiplexing Unit and the NAND Multiplexing Unit  
The XOR multiplexing unit is shown in Figure 1. Assume that (\(x\), \(y\), \(z\)) are the probabilities of two input lines and output lines being stimulated, respectively. Assuming that the error probability \(\varepsilon\) of the XOR gate is zero and the error probabilities in the two input lines are independent, then the probability of the output of the XOR gate if stimulated will be \(z=x(1-y)+y(1-x)\)[22]. If the XOR gate is not fault-free, namely, the gate has a probability \(\varepsilon(\varepsilon\) is not equal to zero) of making a von Neumann error, then the probability of its output being stimulated is  
\[z=(1-\varepsilon)[x(1-y)+y(1-x)]+\varepsilon[xy+(1-x)(1-y)] \tag{1}\]  
For the given numbers of stimulated inputs, the probability that an output is stimulated or not is actually not independent, but rather relevant to others. When \(N\) is relatively large, however, this relevance has little significant effect and can be ignored. If the \(N\) XOR gates function independently, then there is no doubt that the entire XOR multiplexing unit will constitute a Bernoulli sequence. Therefore, the distribution of the probability of stimulated outputs will be the binomial distribution. Correspondingly, the probability of exactly \(k\) outputs being stimulated is  
\[P(k)=\left( \begin{array}{c}\text{N}\\ k\end{array} \right)^{k}(1-z)^{N-k} \tag{2}\]  
When \(N\) is rather large (\(N>1000\)), the probability density of \(k\) can be obtained as [22]  
\[f(k)=\frac{1}{\sqrt{2\pi}\sqrt{Nz(1-z)}}e^{-1/2\ \left((k-Nz)/\sqrt{Nz(1-z)} \right)^{2}} \tag{3}\]  
Therefore, when \(N\) is extremely large, the probability of the number of stimulated outputs of the XOR multiplexing unit could approximately obey the normal distribution. Since the XOR multiplexing unit and the NAND multiplexing unit have the same structure, assume the XOR gates and the NAND gates have the same error probability \(\varepsilon\), therefore, the probability of exactly \(k\) outputs of the NAND multiplexing unit being stimulated is [22]  
\[P_{N}(k)=\left( \begin{array}{c}\text{N}\\ k\end{array} \right)_{2N}^{k}(1-z_{N})^{N-k} \tag{4}\]  
where \(z_{N}=(1-\varepsilon)-(1-2\varepsilon)xy\) is the probability that the output of the NAND gate is being stimulated. Similarly to the XOR multiplexing unit, the probability of the number of stimulated outputs of the NAND multiplexing unit also could be approximated to obey the normal distribution when \(N\) is extremely large. Next, the error distributions of the XOR multiplexing unit and the NAND multiplexing unit for different redundancy \(N\) and \(\varepsilon\) with certain value are considered. We take \(N=1000\) and \(N=100\). Specifying \(x=y=0.8\) and \(\varepsilon=0.01\), for von Neumann error, the probability (density) of the binomial distribution and normal distribution against the number of faulty outputs is plotted in Figure 2. As the probability of possible errors below an acceptable threshold level \(P\) (\(k\leq n\)) is an important feature to evaluate the approximation, the cumulative probability distribution \(P\) (\(k\leq n\)) for the binomial and normal distribution is plotted in Figure 3.  
As can be seen, when \(N\) is large (\(N=1000\)), the normal distribution is in good accordance with the binomial distribution. However, for modest \(N\) (\(N=100\)), the probability density of the normal distribution fits quite well with the binomial distribution, so the discrete binomial distribution is no longer appropriately described by the normal distribution in terms of the cumulative distribution, due to the declined bundle size \(N\). This simulation result is consistent with the previous conclusions. As can be seen, with the same gate error probability and same input error level, when \(N=1000\), the error rates of the XOR multiplexing unit are distributed at the scale of approximately 270-360, while thescale of the NAND multiplexing unit is approximately at 310-400.