Error-correcting codes have been very successful in protecting against errors in data transmission. Computing on encoded data, however, has proved more difficult. In this paper we extend a framework introduced by Spielman [14] for computing on encoded data. This new formulation offers significantly more design flexibility, reduced overhead, and simplicity. It allows for a larger variety of codes to be used in computation and makes explicit conditions on codes that are compatible with computation. We also provide a lower bound on the overhead required for a single step of coded computation.

Stochastically assembled nanoscale architectures have the potential to achieve device densities 100 times greater than today's CMOS. A key challenge facing nanotechnologies is controlling parallel sets of nanowires (NWs), such as those in crossbars, using a moderate number of mesoscale wires. Three similar methods have been proposed to control NWs using a set of perpendicular mesoscale wires. The first is based on NW differentiation during manufacture, the second makes random connections between NWs and mesoscale wires, and the third, a mask-based approach, interposes high-K dielectric regions between NWs and mesoscale wires. Each of these addressing schemes involves a stochastic step in their implementation. In this paper, we analyze the mask-based approach and show that, when compared to the other two schemes, a large number of mesoscale control wires are necessary for its realization.

Methods for assembling crossbars from nanowires (NWs) have been designed and implemented. Methods for controlling individual NWs within a crossbar have also been proposed, but implementation remains a challenge. A NW decoder is a device that controls many NWs with a much smaller number of lithographically produced mesoscale wires (MWs). Unlike traditional demultiplexers, all proposed NW decoders are assembled stochastically. In a randomized-contact decoder (RCD) (Hogg et al., 2006), for example, field-effect transistors are randomly created at about half of the NW/MW junctions. In this paper, we tightly bound the number of MWs required to produce a correctly functioning RCD with high probability. We show that the number of MWs is logarithmic in the number of NWs, even when errors occur. We also analyze the overhead associated with controlling a stochastically assembled decoder. As we explain, lithographically-produced control circuitry must store information regarding which MWs control which NWs. This requires more area than the MWs themselves, but has received little attention elsewhere

We introduce radial encoding of nanowires (NWs), a new method of differentiating and controlling NWs by a small set of mesoscale wires for use in crossbar memories. We describe methods of controlling these NWs and give efficient manufacturing algorithms. These new encoding and decoding methods do not suffer from the misalignment characteristic of flow-aligned NWs. They achieve comparable effective pitch and resulting memory density with axially encoded NWs, while avoiding potential cases of address ambiguity and simplifying NW preparation. We also explore hybrid axial/radial encodings and show that they offer no net benefit over pure codes.

A key challenge facing nanotechnologies is learning to control uncertainty introduced by stochastic self-assembly. In this article, we explore architectural and manufacturing strategies to cope with this uncertainty when assembling nanoarrays, crossbars composed of two orthogonal sets of parallel nanowires (NWs) that are differentiated at their time of manufacture. NW deposition is a stochastic process and the NW encodings present in an array cannot be known in advance. We explore the reliable construction of memories from stochastically assembled arrays. This is accomplished by describing several families of NW encodings and developing strategies to map external binary addresses onto internal NW encodings using programmable circuitry. We explore a variety of different mapping strategies and develop probabilistic methods of analysis. This is the first article that makes clear the wide range of choices that are available.