Informatics and Applications
December 2013, Volume 7, Issue 4, pp 140-147
PROBABILISTIC METHODS FOR SELF-CORRECTING HARDWARE DESIGN
- S. Dolev
- S. Frenkel
- D. E. Tamir
Abstract
This paper presents several ways for extending the scope of program self-correction methods, based on
the “randomself-reducibility” property, to hardware design issues. The concept can be utilized for both analog and
digital hardware-design. The extension is based on sampling, polynomial-interpolation, and error-correcting codes.
In particular, the authors suggest using the well-known reconstruction of real-numerical functions for correcting
faults remaining in analog and digital hardware, e. g., arithmetic logic units (ALU), after manufacturing testing.
The present approach can complement the state-of-the-art technique of program self-correction by uniformly
testing samples of operations and verifying the results of these samples.
[+] References (16)
- Bil‚en, S., and A. Price. 2007. Modulation classification
for radio interoperability via SDR. SDR 07 Technical
Conference and Product Exposition Proceedings.
http://www.slideshare.net/kirill443/12-4-5647963 (accessed
November 7, 2013).
- Lala, P. 2000. Self-checking and fault-tolerant digital design.
Morgan Kaufmann Publs. 400 p.
- Sigal, A., R. Lipton, R. Rubinfeld, and M. Sudan. 1990.
Reconstructing algebraic functions frommixed data. 33rd
Annual Symposium on Foundations of Computer Science.
503–12.
- Gemmell, P., R. Lipton, R. Rubinfeld, M. Sudan, and
A. Wigderson. 1991. Self-testing/correcting for polynomials
and for approximate functions. 23rd Annual ACM
Symposium on Theory of Computing Proceedings. 32–34.
- Lee, D.U., R. Cheung, W. Luk, and J. Villasenor. 2008.
Hardware implementation trade-offs of polynomial approximations
and interpolations. IEEE Trans. Comput.
57(5):686–701.
- Dolev, Sh., and S. Frenkel. 2009. Extending the scope
of self-correcting. 13th Conference (International) on Applied
Stochastic Models and Data Analysis (ASMDA2009)
Proceedings. 458–62.
- Nicely, T.R. Some results of computational research
in prime numbers (Computational number theory).
http://www.trnicely.net/pentbug/pentbug.html (last retrieved
December 2010).
- Rubinfeld, R. 1992. Batch checking with applications to
linear functions. Inform. Process. Lett. 42:77–80.
- Spielman, D. 1996. Highly fault-tolerant parallel computation.
37th IEEE Annual Symposium on Foundations of
Computer Science Proceeding. 154–63.
- Oppenheim, A. V., R.W. Schafer, and J.R. Buck. 1999.
Discrete-time signal processing. Upper Saddle River, NJ:
Prentice-Hall. 871 p.
- Berlekamp, E., and L. Welch. 1986. Error correction of
algebraic block codes. U.S. Patent No. 4,633,470.
- Tertinek, S., and C. Vogel. 2008. Reconstruction of
nonuniformly sampled bandlimited signals using a
differentiator-multiplier cascade. IEEE Trans. Circuits
Syst. 55(8):2273—86.
- Pang, Y., and K. Radecka. 2008. Optimizing imprecise
fixed-point arithmetic circuits specified by Taylor series
through arithmetic transform. Design Automation Conference
DAC’08 Proceedings. 397–402.
- Yekhanin, S. 2011. Locally decodable codes. Foundations
Trends Theoretical Computer Sci. 7(1):1–117.
- Rahardja, S., and B. J. Falkowski. 2001. Efficient algorithm
to calculate Reed–Muller expansions over
GF(4). IEE Proceedings — Circuits, Devices and Systems.
148(6):289, 297.
- Leroux, C., G. LeMestre, C. Jego, P. Adde, and M. Jezequel.
2008. A 5-Gbps FPGA prototype of a (31,29)2
Reed–Solomon turbo decoder. 5th Symposium (International)
on Turbo Codes and Related Topics Proceedings.
67–72.
[+] About this article
Title
PROBABILISTIC METHODS FOR SELF-CORRECTING HARDWARE DESIGN
Journal
Informatics and Applications
December 2013, Volume 7, Issue 4, pp 140-147
Cover Date
2013-12-31
DOI
10.14357/19922264130413
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
self-correcting; real function computation; data analysis; interpolation
Authors
S. Dolev  , S. Frenkel  , and D. E. Tamir 
Author Affiliations
Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel
Institute of Informatics Problems, Russian Academy of Sciences,Moscow, Russia
Department of Computer Science, Texas State University, SanMarcos, Texas, USA
|