Limit on the Addressability of Fault-Tolerant Nanowire Decoders

Although prone to fabrication error, the nanowire crossbar is a promising candidate component for next generation nanometer-scale circuits. In the nanowire crossbar architecture, nanowires are addressed by controlling voltages on the mesowires. For area efficiency, we are interested in the maximum number of nanowires $N(m,e)$ that can be addressed by $m$ mesowires, in the face of up to $e$ fabrication errors. Asymptotically tight bounds on $N(m,e)$ are established in this paper. In particular, it is shown that $N(m,e) = \Theta(2^m / m^{e+1/2})$. Interesting observations are made on the equivalence between this problem and the problem of constructing optimal EC/AUED codes, superimposed distance codes, pooling designs, and diffbounded set systems. Results in this paper also improve upon those in the EC/AUEC codes literature.