Multiple-level concatenated coding in embryonics: a dependability analysis

ABSTRACT

Computing machines require the highest possible dependability in order to provide accurate functionality in aggressive, critical environments. For this purpose, the Embryonics (for embryonic electronics) project explores Nature's structural redundancy mechanisms in digital electronics. It offers a hierarchically reconfigurable framework [4][5][18], whose effectiveness was assessed only for some particular cases [8]. Following the introduction of specialized memory structures [10][13], this paper proposes a more thorough reliability analysis, inspired by fault-tolerant quantum computing theory. After adopting the accuracy threshold measure as the main parameter for our qualitative evaluation, the concepts and implementation details about concatenated coding are presented. This technique, also inspired from reliable quantum computing, seems particularly well suited for the multiple-level architecture in Embryonics and allows preserving arbitrary long fault-tolerant computation.

REFERENCES

• 1: Algirdas Avizienis , Jean-Claude Laprie , Brian Randell , Carl Landwehr, Basic Concepts and Taxonomy of Dependable and Secure Computing, IEEE Transactions on Dependable and Secure Computing, v.1 n.1, p.11-33, January 2004 [doi>10.1109/TDSC.2004.2]
• 2: A. J. van de Goor, Testing semiconductor memories: theory and practice, John Wiley & Sons, Inc., New York, NY, 1991
• 3: Parag K. Lala, Fault tolerant and fault testable hardware design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 4: Mange, D. and Tomassini, M. eds. Bio-Inspired Computing Machines: Towards Novel Computational Architectures. Presses Polytechniques et Universitaires Romandes, Lausanne, Switzerland, 1998.
• 5: Mange, D., Sipper, M., Stauffer, A., Tempesti, G. Toward Robust Integrated Circuits: The Embryonics Approach. In Proc. IEEE, vol. 88, No. 4, April 2000, pp. 516--541.
• 6: Neumann, J. Von. Probabilistic Logic and the Synthesis of Reliable Organisms from Unreliable Components. In C.E. Shannon, J. McCarthy (eds.) Automata Studies, Annals of Mathematical Studies 34, Princeton University Press, 1956, 43--98.
• 7: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 8: Cesar Ortega , Andy Tyrrell, Reliability Analysis in Self-Repairing Embryonic Systems, Proceedings of the 1st NASA/DOD workshop on Evolvable Hardware, p.120, July 19-21, 1999
• 9: Preskill, J. Fault Tolerant Quantum Computation. In H.K. Lo, S. Popescu and T.P. Spiller, eds. Introduction to Quantum Computation, World Scientific Publishing Co., 1998.
• 10: Prodan, L., Udrescu, M., Vladutiu, M. Self-Repairing Embryonic Memory Arrays. Proc. IEEE NASA/DoD Conference on Evolvable Hardware, Seattle WA, 2004, 130--137.
• 11: Lucian Prodan , Gianluca Tempesti , Daniel Mange , André Stauffer, Embryonics: electronic stem cells, Proceedings of the eighth international conference on Artificial life, p.101-105, December 09-13, 2002
• 12: Lucian Prodan , Gianluca Tempesti , Daniel Mange , André Stauffer, Embryonics: Artificial Cells Driven by Artificial DNA, Proceedings of the 4th International Conference on Evolvable Systems: From Biology to Hardware, p.100-111, October 03-05, 2001
• 13: Lucian Prodan , Gianluca Tempesti , Daniel Mange , André Stauffer, Biology Meets Electronics: The Path to a Bio-inspired FPGA, Proceedings of the Third International Conference on Evolvable Systems: From Biology to Hardware, p.187-196, April 17-19, 2000
• 14: T. R. N. Rao , E. Fujiwara, Error-control coding for computer systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 15: Spector, L. Automatic Quantum Computer Programming: A Genetic Programming Approach. Kluwer Academic Publishers, Boston MA, 2004.
• 16: Mihai Udrescu , Lucian Prodan , Mircea Vlǎdutiu, Using HDLs for describing quantum circuits: a framework for efficient quantum algorithm simulation, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy [doi>10.1145/977091.977107]
• 17: Udrescu, M., Prodan, L., Vladutiu, M.. A New Perspective in Simulating Quantum Circuits. Proc. GECCO, Chicago IL, July 2003, 283--290.
• 18: Tempesti, G. A Self-Repairing Multiplexer-Based FPGA Inspired by Biological Processes. Ph.D. Thesis No. 1827, Logic Systems Laboratory, The Swiss Federal Institute of Technology, Lausanne, 1998.
• 19: Zalka, C. Threshold Estimate for Fault Tolerant Quantum Computation. arXiv:quant-ph/9612028, v2, 28 Jul. 1997.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

General Terms:
Algorithms, Reliability, Theory

Keywords:
accuracy threshold, concatenated coding, embryonics, reliability