Introducing flexibility in digital circuit evolution: exploiting undefined values in binary truth tables
Pages 25 - 36
Abstract
Evolutionary algorithms can be used to evolve novel digital circuit solutions. This paper proposes the use of flexible target truth tables, allowing evolution more freedom where values are undefined. This concept is applied to three test circuits with different distributions of "don't care" values. Two strategies are introduced for utilising the undefined output values within the evolutionary algorithm. The use of flexible desired truth tables is shown to significantly improve the success of the algorithm in evolving circuits to perform this function. In addition, we show that this flexibility allows evolution to develop more hardware efficient solutions than using a fully-defined truth table.
References
[1]
Miller, J.F., Job, D., Vassilev, V.K.: Principles in the Evolutionary Design of Digital Circuits - Part I. Journal of Genetic Programming and Evolvable Machines 1, 8-35 (2000).
[2]
Perez, E.I., Coello, C.C.: Extracting and re-using design patterns from genetic algorithms using case-based reasoning. Engineering Optimization 35(2), 121-141 (2003).
[3]
Miller, J.F., Thomson, P., Fogarty, T.: Designing Electronic Circuits Using Evolutionary Algorithms. In: Quagliarella, D., Periaux, J., Poloni, C., Winter, G. (eds.) Arithmetic Circuits: A Case Study, Genetic Algorithms and Evolution Strategies in Engineering and Computer Science, pp. 105-131. Wiley, Chichester (1997).
[4]
Miller, J.F., Thomson, P.: Cartesian Genetic Programming. In: Poli, R., Banzhaf, W., Langdon, W.B., Miller, J., Nordin, P., Fogarty, T.C. (eds.) EuroGP 2000. LNCS, vol. 1802, pp. 121-132. Springer, Heidelberg (2000).
[5]
Perkowski, M., Foote, D., Chen, Q., Al-Rabadi, A., Jozwiak, L.: Learning hardware using multiple-valued logic-Part 1: introduction and approach. IEEE Mirco 22(3), 41-51 (2002).
[6]
Poli, R.: Sub-machine-code GP: New results and extensions. In: Langdon, W.B., Fogarty, T.C., Nordin, P., Poli, R. (eds.) EuroGP 1999. LNCS, vol. 1598, pp. 65-82. Springer, Heidelberg (1999).
[7]
Bäck, T., Hoffmeister, F., Schwefel, H.P.: A survey of evolution strategies. In: Belew, R., Booker, L. (eds.) Proceedings of the 4th International Conference on Genetic Algorithms, pp. 2-9. Morgan Kaufmann, San Francisco (1991).
[8]
Miller, J.F., Smith, S.L.: Redundancy and Computational Efficiency in Cartesian Genetic Programming. IEEE Trans. on Evolutionary Computation 10, 167-174 (2006).
[9]
Shaw, R.F.: Arithmetic Operations in a Binary Computer. The Review of Scientific Instruments 21(8) (1950).
[10]
Oberman, S.F.: Floating Point Division and Square Root Algorithms and Implementation in the AMD-K7 Microprocessor. In: Proc. IEEE Symposium on Computer Arithmetic, pp. 106-115 (1999).
[11]
Yang, S.: Logic synthesis and optimisation benchmark user guide version 3. MCNC (1991).
[12]
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992).
[13]
Holder, M.E.: A modified Karnaugh map technique. IEEE Transactions on Education 48(1), 206-207 (2005).
[14]
Sekanina, L.: Evolutionary Design of Digital Circuits: Where Are Current Limits? In: Proceedings of the First NASA/ESA Conference on Adaptive Hardware and Systems (AHS 2006), pp. 171-178. IEEE CS, Los Alamitos (2006).
[15]
Stomeo, E., Kalganova, T., Lambert, C.: Generalized Disjunction Decomposition for Evolvable Hardware. IEEE Trans. Syst., Man, and Cyb. Part B 36(5), 1024-1043 (2006).
- Introducing flexibility in digital circuit evolution: exploiting undefined values in binary truth tables
Recommendations
The Automatic Acquisition, Evolution and Reuse of Modules in Cartesian Genetic Programming
This paper presents a generalization of the graph- based genetic programming (GP) technique known as Cartesian genetic programming (CGP). We have extended CGP by utilizing automatic module acquisition, evolution, and reuse. To benchmark the new ...
Intrinsic evolution of digital circuits using evolutionary algorithms
GEC '09: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary ComputationCurrently, the auto-design of electronic and analog circuits is an intensively studied topic in the field of evolvable hardware. In order to improve evolutionary design of logic circuits in efficiency, capability of optimization and safety of on-line ...
Applying Genetic Parallel Programming to Synthesize Combinational Logic Circuits
Experimental results show that parallel programs can be evolved more easily than sequential programs in genetic parallel programming (GPP). GPP is a novel genetic programming paradigm which evolves parallel program solutions. With the rapid development ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 06 September 2010
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024