Minimized the Complexity of Digital Circuit with GA Approach: A Review

Minimized the Complexity of Digital Circuit with GA Approach: A Review

Amit Pandey and Prof. Bhagwan Sharma Department of Computer Science & Engineering RKDF institute of science and technology,

Bhopal

Abstract

Digital Equipments are the necessity in the current scenario. Rapid growth of digital world has taken the researchers interest in order to improve the performance of circuit. As the time increases the complexity of circuit will also increase. It also seems to be that there are number of outputs will generate by the circuit. The challenge is that which one is the best or maximum. Such output can find by the various methods. This paper is a review on various methods and the genetic approach which are used in digital circuits. It also throws light on the basic steps of genetic algorithm and its application.

Keywords: Combinational Circuit, Sequential Circuit, Genetic Approach

1. Introduction

   Interconnection of certain specific components such as resistors, diodes, capacitors, transistors etc. to form a gate, flip flop or any other building block is called Circuit Design [1]. The instant growth of electronic equipments makes the condition to reduce the complexity. The purpose is able to satisfy by the genetic algorithm. Genetic algorithm is one of the best ways to solve a problem for which little is known [2]. Genetic algorithms use the principles of selection and evolution to produce several solutions to a given problem.

   There are many types of application that used genetic algorithm to solve the problem. In Digital circuits there is a possibility to find the maximum output of a digital circuit based on flip flop and can minimize time as compare to other search algorithms

   There circuits are also known as the logic circuits due to a mathematician [1]. George Boole was the mathematician who gives the idea of logic theory in his book An Investigation of the Laws of Thought" in 1854. After some time Shannon also

   conctibute in this theory and the communication take place with the digital logic gates.

   Figure 1: Digital Circuit with Gates Figure 1 is a simple architecture for the digital

   circuit having two gates. Each has its own property according to logic theory.

   This paper is divided into five sections including this one. In section two there is discussion about the digital circuit, types and advantages over analog circuit. The section third conations the genetic algorithms with its process diagram. After that we have discussed the previous work in this era in section four. Finally we conclude the paper in section five.

2. Digital Circuit

   Analog signal has the infinite range of signals[1,2]. The discrete signal is another way to convert the infinite signal into the finite signals. This finite signal gives the various outputs but binary signal gives only two outputs that is 0 and 1. On the basis of this output the digital signal has designed.

   It is a composed of basic elements like gates, flip flops and other memory elements. There are two types of digital circuits. First one is combinational circuit and another is sequential circuit.

   Combinational circuit in which there no feedback path between output and input of the circuit. That means no memory element is present in this circuit.

   Figure 2 Combinational circuit

   Sequential circuit there is feedback path present between output and input nodes. In other words a sequential circuit is composed of any Combinational circuit with memory element. This memory element is always present in the feedback path.

   Figure 3 Sequential circuit

   There are many advantages of digital circuit over analog circuit.

   1. The digital circuit is able to send the data without degradation which can occur due to noise.

   2. Speed of data processing is too higher than analog system.

   3. There are infinite numbers of signals in analog circuits which are difficult to handle. In spite of that digital signal has

      used the finite number of signal specially the binary signal.

   4. The data provided by digital circuit can be regenerated easily but in analog output it is hard to recover.

   5. In order to secure the data, digital data is most convenient for encryption but analog signal may create some problem.

3. Genetic Algorithm

   Genetic Algorithm GAs is a methodology that inspired by the procedure of organic progression. Genetic Algorithm follow human evaluation and survival of fittest to generate an optimized solution and it has been used uniform approach to solve the problems[2,3]. It contains two terms Population and individual, Individual behave like child. Population is permutation of parents gens like father, grandfather, mother, grandmother etc.

   Figure 4: Genetic Algorithm Process

   Basic Algoritham of GA

   Genetic Algorithm ()

   {

   Initialization (); Evaluation (); Selection ();

   }

   Selection()

   {

   For (all population)

   {

   If( Condition= =True)

   {

   Element Found in search space

   }

   Else

   {

   Crossover (); Mutation (); Evaluation ();

   }

   }

   A Genetic Algorithm (GA) incorporate five parts to discover resemblance between populations, individual and computational model. A starting set of individuals, P, Crossover is a procedure of encapsulating more than one parent solutions and generate a child solution from them, Mutation the solution may change entirely from the previous solution, Fitness determine the best individuals, Algorithm which applies the crossover and mutation techniques to P iteratively using the fitness function to determine the best individuals in P to keep. Genetic algorithm is simply parallelizable and has been used for classification as well as other optimization problems [3]. GA disadvantages are Difficult to understand and explain to end users, Determining fitness function is difficult, determining how to perform crossover and mutation is difficult. GAs has been used in many applications. Data mining is a significant application of GAs. GA optimized parameters for data miming algorithms or to discover knowledge by itself.

   Application of Genetic Algorithm

   Basically the genetic algorithm is a searching process. This helps to reduce the search space [2,3,4]. So it is useful to any computer generated task where searching is needed. Apart from that there are various application in digital world like Airlines Revenue Management, Artificial creativity, Audio watermark insertion/detection, Automated design (CAD) Bioinformatics Science, Digital Investigation, electronic Circuit Design, Game theory, multimedia, fuzzy logic, power Electronics Design etc.

4. Genetic Algorithm over Digital Circuit

   Genetic algorithm can apply at many places in the world of digital circuits. It seems to be that the various authors has worked on genetic algorithm over digital circuit. The genetic algorithm has used in order to find Fault Diagnosis of Mixed-signal Circuits. Genetic algorithm can also apply to design of Combinational Digital Circuits. Genetic algorithm has used with hardware evaluation environment in order to improve the time and area constraints with the arithmetic operations. Some major applications are:

   • Designing of Digital Circuit

   • Optimization of Digital Circuit

   • Fault Tolerance of Digital Circuit

   • Test Generation of Digital Circuit

   • Performance analysis of Digital circuit

5. Related Work

   There are may works has been done in this area. Some of work has presented here.

   The author explained the genetic algorithm over hardware evaluation environment [5]. They provided results with a number of benchmark arithmetic circuits evolved under different performance driven timing and area constraints.

   Genetic algorithm plays an important role to evolve the combinational circuit [6]. This algorithm uses the various techniques like liner chromosomes and dimensional crossover. In this paper the author proposed the two dimensional over two dimensional crossover and mutation techniques. By this approach the speed of GA has increased as compare to traditional approach. This whole work has done in MATLAB.

   There are some limitations in conventional fault tolerance diagnosis of mixed-signal circuit algorithm [7]. In this paper the author applied the genetic algorithm in order to diagnosis the faults in mix-signal circuit. They use some characteristics and the optimal fitness function to simulate the work. The results show that this approach can help to reduce the complexity of digital amount and special processing.

   Job Scheduling is a important task in the computer system. When it has to done in multiprocessor it will make more complex [8]. In this paper the author has used the genetic approach in order to perform job scheduling in multiprocessor environment. Here fitness function based on aggregation is used. Here Results of three methods has compared in unified condition simulation. The Genetic approach shows better results in experiments and can reduce finishing time and waiting time simultaneously.

   The author has proposed [9] A local search based genetic algorithm (GALS) in order to solve the community mining problem. The author has tested the work on both computer-generated and real-world networks, and compared with some competitive community mining algorithms. Experimental results demonstrate that GALS is highly effective as well as efficient at discovering community structure.

   Timetabling problems are a process of assigning a given set of events and resources to the limited space and time under hard constraints which are rigidly enforced and soft constraints which are satisfied as nearly as possible [10]. To solve such types of problem the author apply the genetic algorithm. It is demonstrated to be feasible for solving a real-world university course timetabling problem.

6. Conclusion

   This paper is survey on digital circuit and the genetic algorithm. This paper shows the various application of genetic algorithm. It seems to be that there are several applications has used the genetic algorithm. To avoid the complexcity in search space this approach is very efficient to apply. Digital circuit gives the large number of output so we can also apply the genetic algorithm on it.

7. Acknowledgement

   This paper would not have been possible without my guide Prof. Guide name and college name. I wish to express my thanks to all the people who helped turn the World-Wide Web into the useful and popular distributed hypertext. I also wish to express thanks the anonymous reviewers for their valuable suggestions.

8. References

1. Digital circuithttp://users.senet.com.au /~ dwsmith/beginners.htm Accessed on 23/06/2013

2. Goldberg D E., "Genetic Algorithms in Search, Optimization and Machine Learning", Reading: Addison-Wesley Publishing Company, 1989

3. Coello Coello C A, Lamont G B, Van Veldhuizen D A. 2nd ed., "Evolutionary Algorithms for Solving Multi-Objective Problems", New York: Springer, 2007

4. A. Rangel-Merino, J. L. Lopez-Bonilla, R. Linares y Miranda, Optimization Method based on Genetic Algorithms, Apeiron, Vol. 12, No. 4, October 2005.

5. Ben. I Hounsell and Tughrul Arslan "A Novel Genetic Algorithms for the Automated Design of Performance Driven Digital Circuits", IEEE 2000, pp 601-608.

6. Vijayakumari. C.K and Mythili. P "A Faster 2D Technique for the design of Combinational Digital Circuits Using Genetic Algorithm" IEEE 2012.

7. Shangcong Feng and Xiaofeng Wang,"Research on Fault Diagnosis of Mixed- signal Circuits Based on Genetic Algorithms", IEEE 2012, pp 12-15.

8. Elnaz Zafarani Moattar, Amir Masoud Rahmanil and Mohammad Reza Feizi Derakhshi "Job Scheduling in Multi Processor Architecture Using Genetic Algorithm" IEEE 2008, pp 248-251.

9. Di Jin, Dongxiao He, Dayou Liu and Carlos Baquero "Genetic Algorithm with Local Search for Community Mining in Complex Networks", IEEE 2010, pp 105-112.

10. Xinyang Deng, Yajuan Zhang, Bingyi Kang, Jiyi Wu, Xiaohong Sun and Yong Deng "An Application of Genetic Algorithm for University Course Timetabling Problem" , IEEE 2011, pp 2119-2122.