No Access

FAULT-TOLERANT NANOCOMPUTERS BASED ON ASYNCHRONOUS CELLULAR AUTOMATA

Division of Computer Engineering, Himeji Institute of Technology, University of Hyogo, 2167 Shosha, Himeji, Hyogo, 671-2201, Japan

Search for more papers by this author

FUKUTARO ABO

Division of Computer Engineering, Himeji Institute of Technology, University of Hyogo, 2167 Shosha, Himeji, Hyogo, 671-2201, Japan

Search for more papers by this author

FERDINAND PEPER

Nanotechnology Group, National Institute of Information and Communications Technology, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe, 651-2492, Japan

Division of Computer Engineering, Himeji Institute of Technology, University of Hyogo, 2167 Shosha, Himeji, Hyogo, 671-2201, Japan

Search for more papers by this author

SUSUMU ADACHI

Nanotechnology Group, National Institute of Information and Communications Technology, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe, 651-2492, Japan

Search for more papers by this author

JIA LEE

Nanotechnology Group, National Institute of Information and Communications Technology, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe, 651-2492, Japan

Search for more papers by this author

NOBUYUKI MATSUI

Division of Computer Engineering, Himeji Institute of Technology, University of Hyogo, 2167 Shosha, Himeji, Hyogo, 671-2201, Japan

Search for more papers by this author

, and

SHINRO MASHIKO

Nanotechnology Group, National Institute of Information and Communications Technology, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe, 651-2492, Japan

Search for more papers by this author

https://doi.org/10.1142/S0129183104006327Cited by:9 (Source: Crossref)

Abstract

Cellular Automata (CA) are a promising architecture for computers with nanometer-scale sized components, because their regular structure potentially allows chemical manufacturing techniques based on self-organization. With the increase in integration density, however, comes a decrease in the reliability of the components from which such computers will be built. This paper employs BCH error-correcting codes to construct CA with improved reliability. We construct an asynchronous CA of which a quarter of the (ternary) bits storing a cell's state information may be corrupted without affecting the CA's operations, provided errors are evenly distributed over a cell's bits (no burst errors allowed). Under the same condition, the corruption of half of a cell's bits can be detected.

Keywords:

You currently do not have access to the full text article.
Recommend the journal to your library today!

References

A. Bachtoldet al., Science 294, 1317 (2001). Crossref, Web of Science, ADS, Google Scholar
C. P. Collieret al., Science 285, 391 (1999). Crossref, Web of Science, Google Scholar
Y. Cui and C. Lieber, Science 291, 851 (2001). Crossref, Web of Science, ADS, Google Scholar
Y. Huanget al., Science 294, 1313 (2001). Crossref, Web of Science, ADS, Google Scholar
H. W. C. Postmaet al., Science 293, 76 (2001). Crossref, Web of Science, ADS, Google Scholar
M. A. Reedet al., Appl. Phys. Lett. 78, 3735 (2001). Crossref, Web of Science, ADS, Google Scholar
T. Rueckeset al., Science 289, 94 (2000). Crossref, Web of Science, ADS, Google Scholar
W. Porod , Nanoelectronic Circuit Architectures ( Chemical Rubber Company Press , Boca Raton, FL , 2002 ) . Crossref, Google Scholar
P. Beckett and A. Jennings, Proc. 7th Asia-Pacific Computer Systems Architecture Conf., ACSAC'2002 (Conf. on Research and Practice in Information Technology), eds. F. Lai and J. Morris (2002), Vol. 6 . Google Scholar
M. Biafore, Physica D 70, 415 (1995). Crossref, Web of Science, ADS, Google Scholar
J. Lyke , G. Donohoe and S. Karna , Technical report ( Air Force Research Laboratory , 2001 ) . Google Scholar
L. J. K. Durbeck and N. J. Macias, Nanotechnology 12, 217 (2001). Crossref, Web of Science, ADS, Google Scholar
F. Peperet al., Nanotechnology 14, 469 (2003). Crossref, Web of Science, ADS, Google Scholar
S. Hauck, Proc. IEEE (1995), pp. 69–93 . Google Scholar
P. Gács , Technical report ( Computer Science Department, Boston University , 1997 ) . Google Scholar
K. Nakamura, Systems, Computers, Controls 5, 58 (1974). Google Scholar
T. Toffoli, Proc. Fifth Colloquium on Automata, Languages, and Programming (ICALP), eds. G. Ausiello and C. Böhm (Springer, 1978) pp. 457–463. Crossref, Google Scholar
J. Leeet al., Physica D 194, 369 (2004). Crossref, Web of Science, ADS, Google Scholar
F. Peperet al., Future Generation Computer Systems 18, 893 (2002). Crossref, Web of Science, Google Scholar
L. Priese, J. Comput. Syst. Sci. 17, 237 (1978). Crossref, Web of Science, Google Scholar
U. Golze and L. Priese, Information and Control 53, 121 (1982). Crossref, Google Scholar
S. Adachi, F. Peper and J. Lee, J. Stat. Phys. 114, 261 (2004). Crossref, Web of Science, ADS, Google Scholar
J. Leeet al., Fundamenta Informaticae 58, 295 (2003). Web of Science, Google Scholar
L. Priese and D. Rödding, J. Cybernetics 4, 7 (1974). Crossref, Web of Science, Google Scholar
J. Leeet al., 3rd Int. Conf. Unconventional Models of Computation 2002, eds. C. S. Calude, M. J. Dinneen and F. Peper (Springer, 2002) pp. 220–229. Crossref, Google Scholar
L. Priese, J. Cybernetics 5, 103 (1975). Web of Science, Google Scholar
L. Priese, Progress in Cybernetics and Systems Research 159 (1979). Google Scholar
J. R. Heathet al., Science 280, 1716 (1996). Crossref, Web of Science, Google Scholar
J. von Neumann, Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components (Princeton University Press, 1956) pp. 43–98. Crossref, Google Scholar
R. L. Dobrushin and S. I. Ortyukov, Problems of Information Transmission 13, 203 (1977). Google Scholar
N. Pippenger, 26th IEEE Symp. Foundations of Computer Science (1985), pp. 30–38 . Google Scholar
N. Pippenger, J. Association for Comput. Machinery 36, 531 (1989). Crossref, Web of Science, Google Scholar
K. Nikolić, A. Sadek and M. Forshaw, Nanotechnology 13, 357 (2002). Crossref, Web of Science, ADS, Google Scholar
P. G. Depledge, IEE Proc. (1981), pp. 257–272 . Google Scholar
S. Spagocci and T. Fountain, Electrochem. Soc. Proc. (1999), pp. 354–368 . Google Scholar
J. Han and P. Jonker, Nanotechnology 14, 224 (2003). Crossref, Web of Science, ADS, Google Scholar
H. Nishio and Y. Kobuchi, J. Comput. Syst. Sci. 11, 150 (1975). Crossref, Web of Science, Google Scholar
M. Harao and S. Noguchi, J. Comput. Syst. Sci. 11, 171 (1975). Crossref, Web of Science, Google Scholar
P. Gács, J. Stat. Phys. 103, 45 (2001); P. Gács, IEEE Symp. Foundations of Computer Science (1997), pp. 90–99 . Google Scholar
P. Gács, J. Comput. Syst. Sci. 32, 15 (1986). Crossref, Web of Science, Google Scholar
P. Gács, Advances in Computing Research (A Scientific Annual), ed. S. Micali (JAI Press, 1989) pp. 223–326. Google Scholar
P. Gács and J. Reif, J. Comput. Syst. Sci. 36, 125 (1988). Crossref, Web of Science, Google Scholar
W.Wang, Ph.D. thesis, Boston University, Boston, MA 02215 (1990); W. Wang, Proc. 32nd IEEE Symp. Foundations of Computer (IEEE Press, 1991), pp. 278–285 . Google Scholar
C. E. Shannon , The Mathematical Theory of Communication ( University of Illinois Press , 1949 ) . Google Scholar
F. J. MacWilliams and N. J. Sloane , The Theory of Error-Correcting Code ( North-Holland , 1978 ) . Google Scholar
V. Akella, N. H. Vaidya and G. R. Redinbo, Symp. Fault-Tolerant Computing (1996), pp. 208–217 . Google Scholar
F.-C. Cheng and S.-L. Ho, Int. Conf. Computer Design (ICCD'01) (IEEE Computer Society Press, 2001) pp. 24–29. Google Scholar
D. A. Spielman, Procs. 37th Annual IEEE Conf. Foundations of Computer Science (1996), pp. 154–163 . Google Scholar
F. Peperet al., IEEE Trans. Nanotechnology 3, 187 (2004). Crossref, Web of Science, ADS, Google Scholar
M. Capcarrere, Ph.D. thesis, Swiss Federal Institute of Technology, Lausanne, Switzerland (2002) . Google Scholar
F. Peper, T. Isokawa, F. Abo, J. Lee, S. Adachi, N. Matsui and S. Mashiko, Proc. 9th Int. Symp. Artificial Life and Robotics (AROB'04) (2004), pp. 61–66 . Google Scholar
K. Morita, Lecture Notes in Computer Science 2055, 102 (2003). Crossref, Google Scholar
A. Hocquenghem, Chiffres 2, 147 (1959). Google Scholar
R. C. Bose and D. K. Ray-Chaudhuri, Inf. Control 3, 68 (1960). Crossref, Google Scholar
R. C. Bose and D. K. Ray-Chaudhuri, Inf. Control 3, 279 (1960). Crossref, Google Scholar