Zhang Junbin,Cai Jinyan,Meng Yafeng

Department of Electronic and Optical Engineering,Mechanical Engineering College,Shijiazhuang 050003,China

Optimal design of RTCs in digital circuit fault self-repair based on global signal optimization

Zhang Junbin,Cai Jinyan*,Meng Yafeng

Department of Electronic and Optical Engineering,Mechanical Engineering College,Shijiazhuang 050003,China

Since digital circuits have been widely and thoroughly applied in various fields,electronic systems are increasingly more complicated and require greater reliability.Faults may occur in electronic systems in complicated environments.If immediate field repairs are not made on the faults,electronic systems will not run normally,and this will lead to serious losses.The traditional method for improving system reliability based on redundant fault-tolerant technique has been unable to meet the requirements.Therefore,on the basis of(evolvable hardware)-based and(reparation balance technology)-based electronic circuit fault self-repair strategy proposed in our preliminary work,the optimal design of rectification circuits(RTCs)in electronic circuit fault self-repair based on global signal optimization is deeply researched in this paper.First of all,the basic theory of RTC optimal design based on global signal optimization is proposed.Secondly,relevant considerations and suitable ranges are analyzed.Then,the basic flow of RTC optimal design is researched.Eventually,a typical circuit is selected for simulation verification,and detailed simulated analysis is made on five circumstances that occur during RTC evolution.The simulation results prove that compared with the conventional design method based RTC,the global signal optimization design method based RTC is lower in hardware cost,faster in circuit evolution,higher in convergent precision,and higher in circuit evolution success rate.Therefore,the global signal optimization based RTC optimal design method applied in the electronic circuit fault self-repair technology is proven to be feasible,effective,and advantageous.

1.Introduction

With the continual development of electronics,digital circuits have been widely and thoroughly applied in various fields.Faults will be apt to occur in electronic systems under complicated environments(e.g.,powerful electromagnetic interference,high temperature difference,deep space,deep sea).1–3If real-time field faults repairs are not achieved,electronic systems will lose parts offunctions,not work properly,and even cause great losses.2,4,5

With regard to traditional electronic circuits,their reliability is mainly improved based on redundant fault-tolerant technology.6–8Although its theory is simple,redundant backup technology cannot be achieved on all components or chips.Therefore,its scope of application is limited,which leads to slight improvement of system reliability.9–12In order to solve these problems,a novel electronic circuit fault self-repair strategy based on evolvable hardware(EHW)and reparation balancetechnology(RBT)wasproposedin ourprevious research,which improved the reliability and self-repair capacity of electronic systems.13

Based on our previous work,the optimal design theory of a rectification circuit(RTC)applied in electronic circuit fault self-repair based on global signal optimization is proposed.13When all node signals’logics of an electrical system are statistically analyzed and time sequences are consistent,the input signals of an RTC under design are replaced.This will reduce hardware resource consumption,improve circuit evolution convergence precision and convergence speed,and enhance the success rate of circuit evolution.The basic theory of RTC optimal design based on global signal optimization is researched in detail.The conditions and application range of the RTC optimal design method are analyzed.The basic design process of the RTC optimal design method is studied.Eventually,the feasibility and effectiveness of the proposed RTC optimal design method based on global signal optimization are proven by a simulation example.

2.Basic theory of electronic circuit fault self-repair based on EHW and RBT

Before the search of the RTC optimal design method in electronic circuit fault self-repair based on global signal optimization,the EHW theory needs to be introduced,and the electronic circuit fault self-repair strategy based on EHW and RBT is also introduced,so that the significance of RTC optimal design can be understood.14–16

Using EHW,a tool with evolutionary algorithm(EA)as combinational optimization and global search,circuits and system structures with intended functions can be obtained by means of simulated evolution. Its formula is EAs+PLDs=EHW.13,17–20The evolution process of EHW is expressed in Fig.1.

Firstly,during circuit evolution,the circuit structure shall be coded as 010110011011101111011 according to a rule so as to obtain a structural bit-string(also called as chromosome code),and the corresponding circuit is shown in Fig.1(a).Secondly,according to constraint conditions and fitness judgment function,genetic operations(replication,selection,crossover,and mutation)are made on the chromosome codes,so as to get a new chromosome code of 010110011011101110010,as shown in Fig.1(b).13Finally,the new chromosome code is decoded,and the circuit structure can be obtained.It can be seen from circuit evolution that the EA is able to find a structural bit-string code conforming to the target circuit from a disordered structural bit-string code according to a rule.In addition,such advantages of EHW as self-organization and self-repair are completely applied and reflected during circuit evolution.16,19–22

Since EHW features sound robustness,it is independent of prior knowledge and manual intervention.23EHW has been widely applied to functional evolution offield programmable gate array(FPGA)and digital circuit function,24–26reconfigurable chip structure and dynamic reconfiguration,27–29robotics,industry,military affairs,18etc.1,15,30–32

The electronic circuit fault self-repair strategy based on EHW and RBT mainly uses EHW technology and RBT technology.13An RTC can be evolved and designed according to the input signal based on the analysis of the output signal of a fault circuit.XOR operation is made on the output signals between the RTC and the original fault module,and then the correct output signals can be obtained.The circuit can work normally,and faults are repaired.Fig.2 shows the universal model offault self-repair based on EHW and RBT.Only signal states are repaired during fault self-repair,and there is no need to orientate fault position.13

In Fig.2,the universal model mainly includes an upper computer,a lower computer,UUTs(units under test),MUXs(multiplexers),FPGA,serial port communication,etc.An FPGA chip for fault self-repair is embedded into the fault self-repair electronic system,and all UUTs are brought in via MUXs to repair faults of UUTs.

As can be seen from the above theories,the core of the proposed fault self-repair strategy is RTC design.Whether the RTC is an optimal circuit,or whether there are less hardware resources consumptions,these problems need to be researched in detail in the following section.

Fig.1 Basic theory scheme of evolvable hardware.

Fig.2 Universal model of a fault self-repair circuit system based on EHW and RBT.

3.Theory of RTC optimal design based on global signal optimization

3.1.Basic theory of RTC optimal design

The traditional RTC design method which was used in Ref.13can be named conventional method.During the design of an RTC with the conventional method,all input signals of the RTC are selected from UUT circuits in which output fault signals occur.However,the hardware resource consumption of the designed RTC through EA cannot be easily reduced.

In the process offault self-repair based on EHW and RBT,when RTC optimal design is used,a simple structure should be obtained.It should have some advantages,for example,the least hardware resource consumption and fast circuit evolution speed.

Consequently,the optimal design theory of an RTC based on global signal optimization is proposed in this paper.Specifically,according to the fault UUT in an electronic system,the selected node signals in the electronic system can become the input signals of the RTC.The time sequences of the selected node signal and the original signal must be consistent.Finally,the designed RTC shall consume the least hardware resources,and it has the fastest evolutional speed and highest evolutional success rate.

Assume that the input ports set of a UUT is expressed as SUUTand that SUUTis formed by two subsets including S1and S2,so it can be namely SUUT={S1，S2}.There are also some other node signals in the electronic system,and such signals constitute another set, and it is expressed as Sother={S3，S4，...，Sk},in which k is a constant.Assume that SRTCis expressed as the input signals of the RTC.

During the design of the RTC based on global signal optimization,the input signals of the RTC under design shall conform to the following requirements.

(1)All input signals of the RTC can be the input signals of the UUT,and this is also the conventional RTC design method.At this time,SRTC=SUUT.

(2)When the selected node signals of the designed RTC include some input signals of the UUT(assumed as S1),they include a signal set of S3which does not belong to SUUT,so the input signal set of the RTC is SRTC={S1，S3}.Whether such node signals are periodic signals,one-to-one mapping or many-to-one mapping of the signal combinations between SRTCand SUUTshall be ensured.

(3)Based on the second requirement,several sets of SRTCcan be selected,or none is selected.When there are several SRTC,an EA is used to evolve the target circuit.According to the principle with the least hardware resource consumptions,fastest evolutional convergence speed,and highest evolutional success rate,the best SRTCcan be selected.Then the corresponding RTC is designed,and fault self-repair is realized.

(4)In the new optimum SRTC,one-to-many mapping shall not occur absolutely between the input and output signals of the RTC.In other words,the same input combination only has the same output signal.Otherwise the replacement of node signals will fail,so that the RTC with expected functions cannot be evolved directly.

In order to better describe the proposed optimal design theory of an RTC,a simple circuit system is illustrated as follows.The circuit system is constituted by two sub-circuits,and the corresponding truth tables of the two sub-circuits are shown in Tables 1 and 2,respectively.

The logical relations of these signals are shown in Fig.3,where CLK is the clock signal.When the input signal of Circuit 1 is 000,the corresponding signal of Circuit 2 is 100.Whenthe input signal of Circuit 1 is 100,the corresponding signal of Circuit 2 is 000.At other times,Circuit 1 and Circuit 2 have the same input signals synchronously.

Table 1 Truth table of Circuit 1.

Table 2 Truth table of Circuit 2.

Fig.3 Logic relation of the example circuit system nodes.

Assuming that the input signals of{X1,X2,X3}are{000,101},the output ports of Circuit 1 are inconsistent with the expected output signals.In other words,faults exist in Circuit 1.The designed RTC diagrams of the example circuit before and after global signal optimization are shown in Fig.4.

If the conventional method is used to design an RTC to achieve reparation balance repair offaults,the corresponding RTC is shown in Fig.4(a).The designed RTC based on global signal optimization is shown in Fig.4(b).It can be seen from Fig.4 that the former uses eight basic gate units,but the latter only uses two basic gate units.Compared with the conventional method for designing RTC,the RTC designed based on globalsignaloptimization consumeslesshardware resources.The former implements circuit evolution based on three input ports including X1,X2,and X3,but the latter implements circuit evolution based on such three input ports as X2,X3,and X4.X1 of the former is replaced by X4 of the latter.

It can be seen from RTC design during fault repair on the example circuit that the RTC based on global signal optimization can reach the optimal hardware resource consumption,evolutional convergence speed,etc.Furthermore,according to the changes of UUT faults,SRTCcan be changed adaptively by EA,and the self-adaptive design of the RTC can be realized,so that the fault self-repair of the electronic circuit can be achieved.

Fig.4 RTC diagrams of example circuit before and after global signal optimization.

3.2.Matters needing attention and application scopes of RTC optimal design

Two main important concepts including valid replacement and invalid replacement shall be analyzed in the RTC optimal design theory as described in Section 3.1.

Valid replacement shall mean,based on the conventional RTC design method,the corresponding input combination changes when the RTC outputs ‘1” after the input signals are replaced by other node signals.In the example of Section 3.1,when the output combinations of the RTC designed with the conventional method are{000,101},the corresponding output signals are ‘1”.If X4 of Circuit 2 replaces X1 of Circuit 1,the corresponding input combinations change when the RTC outputs ‘1”.This is a valid replacement.

On the contrary,invalid replacement shall mean that the corresponding input combination keeps unchanged when the RTC outputs ‘1”after the input signals are replaced by other node signals.In the example of Section 3.1,if X1 of Circuit 1 is replaced by X3 of Circuit 2,the corresponding input combinations keep unchanged when the RTC outputs ‘1”.This is an invalid replacement.

When the input signals of the RTC are replaced by global node signals,invalid replacements need to be completely eradicated.The important reason is that invalid replacements cannot change the designed RTC structure,and only valid replacements are capable of changing the RTC structure.

Meanwhile,the optimal design theory of RTC in electronic circuit fault self-repair based on global signal optimization shall make statistical analysis on the global node signals.A large-scale circuit system shall be divided into several small sub-systems,and signals transmitted among sub-systems shall be brought into the range of the global node signals.In this way,not all the component signals of the entire circuit system are counted,so as to save hardware cost.

In addition,RTC optimal design is achieved on the basis of the following condition.Based on Fig.2,all the node signals of the circuit system can transmit through the MUX,and an access between switches and the FPGA can be formed,so that the global node signals can be utilized by the RTC.

Eventually,the following rules shall be observed during RTC optimal design.The node signals selected for replacing the original input signals of the RTC shall not be the nextstage circuit of the existing faults UUT circuit.In other words,if a fault signal inputs into a sub-system,the output signals of these sub-systems cannot be brought into the range of the global node signals.The sub-circuit node signals that are directly or indirectly related to the output signals of the fault UUT circuit cannot be brought into the range of the global node signals.

3.3.Basic flow of RTC optimal design based on global signal optimization

Concerning a specific circuit system,the flow is required to achieve RTC optimaldesign based on globalsignal optimization.

The state number of the source signals of the circuit system is assumed as the maximum state number of the entire circuit system.The logical relation table of all the node signals of the circuit system shall be built from low to high according to the maximum state number of the circuit system.Assuming that a circuit system has five source signals,it has totally 25=32 states,and such states are ordered from 00000 to 11111.However,if the five source signals do not have 32 states in an actual working circuit,the logic relation table of the node signals shall be built according to the real state number.The optimal design flow of an RTC based on global signal optimization is shown as follows.

Step 1.The dynamic states of all the node signals of the electronic system are comprehensively analyzed,and the logic relations among all the signals are clarified.

Step 2.BIT detects the node signals of the entire electronic system.When faults occurred in a UUT,according to the faults information,SUUTneeds to be calculated,and the corresponding RTC output signals of the repaired faults are calculated.

Step 3.Node signals that can replace SUUTare analyzed according to the fault information(mapping relations are ensured and node signals of sub-circuits which are directly or indirectly related to UUT output signals are removed).

Step 4.Signal combinations that can replace SUUTare calculated according to the selected global node signals.Invalidly replaced node signalsare deleted,so thatall replacements are valid.

Step 5.The RTC is evolved with an EA according to combinations which can make valid replacements,and evaluation is made according to hardware resource consumption,fitness changes,evolution success rate,evolution convergence speed,etc.

There are only two cases in the process of RTC optimal design,i.e.,the global signal optimization technology can be applied or not.If no valid replacement exists,only the conventional RTC design method can be applied.Otherwise,the global signal optimization technology can be used.The detailed analyses are shown in Fig.5.

As clearly seen from Fig.5,in Situation 4,the global signal optimization technology can be used.In Situation 5,the global signal optimization technology cannot be used.Situation 4 concludes two situations:general situation and special situation.Situation 1,Situation 2,and Situation 3 are contained by the special situation of Situation 4.

The detailed analyses of the five situations are summarized as follows.

Situation 1.Whether a node signal is consistent with the output signal of the RTC or not.If yes,it can be directly used.It is concluded in the special situation of Situation 4.

Situation 2.Whether a node signal after NOT operations is consistent with the output signal of the RTC or not.If yes,it can be directly used after NOT operation.It is concluded in the special situation of Situation 4.

Situation 3.Whether several node signals after simple AND,OR,and NOT operations can be consistent with the output signals of the RTC.If yes,such signals can be directly used after the above simple operations.It is concluded in the special situation of Situation 4.

Situation 4.After the signals in SUUTare replaced by one or more node signals,whether the redesigned circuit can constitute the output signals of the RTC,it concludes the common situation and the special situation.

Situation 5.The signals in SUUTcan only be used as the input signals of the RTC,and only the conventional RTC design method can be used.

An EA is used in the process of RTC optimal design after a valid replacement exists.The best replacement scheme can be found by the EA.In the best replacement scheme,the hardware resources consumption can be reduced,the evolutionary speed can be improved,and the convergent precision and the circuit evolution success rate can be increased.There is a possibility that the performance of all the valid replacements is not as good as that of the conventional RTC design method.At this time,the performance of the EA will also be reflected.

4.Example simulation analyses

4.1.Selection of EA

Simulation experiment and analysis of a circuit are made on an AMD Athlon X2 250 dual-core,2 GB,ATI Radeon 3000 computer.

Genetic algorithm discrete particle swarm optimization(GADPSO)is used during EA33–37,and ternary code design is used with the coding rule shown in Table 3.38Since this paper does not focus on EA,GADPSO is not analyzed in detail.

a in Table 3 is an input port.The following equation is mainly used for evolution:

where FRlBTis the output value of the evolved circuit calculated according to the truth table.FRlBTis the lth value offRBT.M is the number of the input ports.N is the number of the output ports.H is the number of rows of the chromosome code matrix.l∈ [1，L],i∈ [1，H],j∈ [1，M],and L=2M.F is assumed as the output matrix of the truth table,with a scale of L×N.FRBTand F are vectors,and their lengths are L.C is the chromosome code matrix,with a scale of H×M.T is the input combined matrix of the truth table,with a scale of L×M.

Fig.5 All situations of RTC optimal design.

Table 3 Rules of ternary code.

In GADPSO,the crossover rate is pc=0.95,the mutation rate is pd=0.05,the number of the initialized particle swarms is 40,the number of cross points is 2,and the number of mutation points is 2.The code length of every chromosome is determined according to the number of the initial input ports of RTC evolution,and it can be named by 5×M.

The inertia weight of w in GADPSO is as follows:

where t is the current number of iteration steps and tmaxis the maximum number of evolution iterations.

4.2.Selection of a classic circuit system

For the purpose of verifying the feasibility and effectiveness of the optimal design theory of RTC based on global signal optimization proposed in this paper,a classic circuit system is used for simulation verification,which is shown in Fig.6.Although the selected circuit is small,the feasibility and effectiveness of the optimal design theory can be proven.

The selected circuit system mainly includes six parts,and each part is a sub-circuit,which includes a code circuit(U1),a NOT gate(U2),C17(U3),a binary gray code generating circuit(U4),a two-bit adder(U5),and an OR gate(U6).The node signals of the circuit system are expressed as follows:module No.+output port name.For example,Y1 output node of U1 module is expressed as ‘U1-Y1”,and the output port of U6 is expressed with ‘U6-out”.

The circuit system has 64 input ports,with a serial number from U1-X1 to U1-X64.It has eight output ports,with the serial numbers of U3-C17_Y1,U3-C17_Y2,U4-GC_Y1,U4-GC_Y2,U4-GC_Y3,U4-GC_Y4,U5-Adder_C1,and U5-Adder_C2.The code circuit in the circuit system is achieved with six pieces of commonly used 8–3 encoders(74LS148),and its output ports from U1-Y6 to U1-Y1 can output signals from 000000 to 111111.

In order to analyze RTC optimal design easily,the node signals brought in the simulation experiment only include connection node signals among the six modules of the circuit system,and the internal nodes of every module are not brought in.For example,U3 is constituted by several NAND gates and the connection signals between each NAND gate are not brought in the statistical scope of node signals.

Finally,the logical table of the node signals of the entire circuit system is obtained as shown in Table 4,where all modules are sequenced from left to right and from the high bit to the low bit.

As shown in Table 4,the input signals of the entire circuit system are from U1-X1 to U1-X64,which are directly input into encoders,and subsequent U2,U3,U4,U5,and U6 are directly or indirectly controlled by the encoders.In other words,when the input signals of U1 are fixed,its output signals are fixed,and the input and output signals of correspondingly subsequent U2,U3,U4,U5,and U6 are also fixed;namely,every row of signals in Table 4 occurs simultaneously.At this time,Y1-Y6 of U1 presents one-to-one mapping with those of U3,and U1 presents one-to-one mapping with U4.As a matter offact,the output result of U4 is only related to Y1-Y4 output ports of U1.However,the logic value of Y5 of U1 in Table 4 has no influence on the output values of U4 and U5.Therefore,the states from the first to 16th of U4 and U5 in Table 4 overlap with the states from 17th to 32nd.

Simulated analysis is made on fault self-repair of RTC optimal design under five circumstances in Section 3.1,and only one node signal existing fault is assumed.When multiple node signals appear faults,they have the same principle.

4.3.Simulation analysis of circuit evolution

4.3.1.Corresponding example analysis to Situation 1

Fig.6 Circuit system for simulation.

Table 4 Logical table of the node signals of the circuit system.

It is assumed that faults occur in the 5th–8th and 13th–16th states of Y2 output port of U4(U4-GC_Y2),and the output signal of the RTC shall be 0000111100001111.It can be found after looking up Table 4 that the previous 16 states of Y3 node signal of U1(U1-Y3)are consistent with the output signals of the RTC,U1-Y3 starts circulating the previous states from 17th to 32nd,and U4-Y2 also starts circulating from the 17th state.Therefore,the output signals of the RTC can be replaced by U1-Y3 node signals directly.According to the fault selfrepair theory combining EHW with RBT,XOR can be directly made between U1-Y3 and U4-Y2 node signals in which faults occur,so that without any fault,the signal of U4-Y2 can be obtained.

According to the faults in Situation 1,a conventional RTC evolutionary method is used and the same GADPSO parameters are set to make six circuit evolutions,the maximum number of evolution iterations is 6000.The related corresponding circuit simulation data are shown in Table 5.

It can be seen from Table 5 that in the six repeated circuit evolutions with conventional RTC evolutionary methods,the foremost numbers of evolvable iteration evolution are different.However,the evolved circuits conform to RTC functions,and six repeated circuit evolutions can be successfully evolved within the regulated maximum evolutionary times.In the second circuit evolution,no hardware resource is consumed,which is greatly different from the hardware resource consumptions in the other five circuit evolution experiments.The data are correct.After detailed study on the finally evolved circuit code,the obtained RTC only includes one U1-Y3 input port,and the signals of U1-Y3 are consistent with those of the RTC output port,coinciding with the result in Situation 1.

Some conclusions are shown as follows.When faults occur in Situation 1,the logic relations among all the node signals in the database are compared firstly,and the node signals that are consistent with the RTC output signals are found so as to rapidly achieve fault rectifiable repair,and it consumes the least hardware resources.Although the RTC can be evolved successfully on circuit modules with faults,the evolved circuits may not be the simplest circuits(least hardware resources consumption).In addition,the time for circuit evolution is far more than the time for comparison of the similarity between two sets of data under normal conditions.

4.3.2.Corresponding example analysis to Situation 2

It is assumed that faults occur in the 1st,2nd,9th–12th,16th-18th,25th-28th,and 32nd states of C1 of U5(U5-Adder_C1),and the output signal of the RTC shall be 1100000011110001 1100000011110001.It can be discovered through looking up the logic relation table of all node signals of the circuit system that U3-C17_Y1 node signal presents an opposite logic relation with RTC output signals.Although U3-C17_Y1 node signal does not belong to the input signal of U3,the 17th–32nd states of U3-C17_Y1 and U5-Adder_C1 are consistent withthe 1st–16th states.Consequently,the negation of U3-C17_Y1 node signal can be directly used as the output signal of the RTC.In other words,after the NOT operation on U3-C17_Y1 node signal,XOR is made with U5-Adder_C1 fault signal to get without faults signal of U5-Adder_C1.

Table 5 Related data of the corresponding conventional RTC evolution to Situation 1.

According to the faults in Situation 2,a conventional RTC evolutionary method is used,and the same GADPSO parameters are set to make six circuit evolutions,the maximum number of evolution iterations is 6000.The related simulation data of the corresponding circuit are shown in Table 6.

It can be seen from Table 6 that the conventional RTC evolutionary method successfully evolves the RTC in six evolution experiments.If the negation of U3-C17_Y1 node signal is used as the output signal of the RTC,the number of hardware resources will be ‘1”.However,the conventional method is used to design the RTC,the third evolutionary experiment consumes least hardware resources,and the number of hardware resources is ‘10”.RTCs designed with the two methods are shown in Fig.7.

It can be clearly seen from Fig.7 that the conventional method uses the original input port of a circuit module with faults as the input port,namely,U4-GC_Y1,U4-GC_Y2,U4-GC_Y3,U4-GC_Y4,and U6-out.It is known from Fig.6 that U6-out is only related to U1-Y3 and U1-Y4.Therefore,the RTC evolved with a conventional method can be optimized.

In Situation 2,U3-C17_Y1 node signal is not the input signal of U5,but the node signal selected from the entire circuit system preferentially.In the RTC optimal design method based on global signal optimization,the overall fault selfrepair is just a process for data comparison if a node signal is opposite to the output signal of the RTC.Compared with the conventional RTC evolution,the former is characterized with less time and less hardware resources consumption.Therefore,it has distinct advantages.

4.3.3.Corresponding example analysis to Situation 3

Assuming that faults occur in the 8th,9th,11th,14th,16th,22nd,24th,25th,27th,30th,and 32nd states of Y1 output port of U3(U3-Y1),it is discovered after detailed analysis that the states from the 1st to 16th of U3-Y1 node signal repeat the states from the 17th to 32nd states,i.e.,one circulation.Therefore,faults occurred in the previous 16 states can be repaired on the premise that the output signals of the RTC shall circulate once from the 1st state to the 32nd state.With respect to faults occurred in U3-Y1 node,the output signal of the RTC shall be 0000000110100101.At this time,it is found after looking up Table 4 that the output signals after the AND operation between U5-Adder_C1 and U6-out are consistent with the output signals of the RTC through the EA,and its period is also consistent with the node signals of U3-Y1.Consequently,one AND gate is made between U5-Adder_C1 and U6-out in order to get the required RTC signal,and the number of hardware resources consumption is ‘1”.

According to the faults in Situation 3,a conventional evolutionary method is used to design an RTC and the same GADPSO parameters are set to make six circuit evolutions,the maximum number of evolution iterations is 6000.The related simulation data of the corresponding circuit are shown in Table 7.

It can be seen from Table 7 that the six conventional RTC evolutionary methods evolve the RTC in six evolution experiments successfully.According to the 2nd,3rd,5th,and 6th circuit evolutionary experiments,the same circuit structures are obtained,and they have the same hardware resourcesconsumption apparently.RTCs designed with the two methods in Situation 3 are shown in Fig.8.

Table 6 Related data of the corresponding conventional RTC evolution to Situation 2.

Fig.7 RTCs designed with different methods in Situation 2.

It can been seen from Fig.8(b)that the RTC designed with the conventional method only has four input ports,including U1-Y1,U1-Y2,U1-Y3,and U1-Y4,all of which are the original input signals of U3.The first column of all circuit codes in Table 7 is ‘2”,which represents that the corresponding highest-bit U1-Y5 signals are unrelated to the output signals of the RTC.RTC signals are only determined by U1-Y1,U1-Y2,U1-Y3,and U1-Y4 node signals.

Like RTC design in Situation 1 and Situation 2,the conventional RTC method features longer evolution time and greater hardware resources consumption.In the RTC design method based on global signal optimization,the selected U5-Adder_C1 and U6-out node signals are from the entire circuit system other than the input signals of U3.However,the output signals of the RTC can be obtained through U5-Adder_C1 and U6-out signals,so that faults can be repaired.Both of U5-Adder_C1 and U6-out signals are not the input signals of U3.It is more effective and valuable to select node signals from the entire circuit system in the process of RTC design.

4.3.4.Corresponding example analysis to Situation 4

Assume that faults occur in the 2nd,4th,18th,and 20th states of C2 of U5(U5-C2),and the corresponding output signal of the RTC shall be 01010000100100000101000010010000.If a conventional method is used to design the RTC,the corresponding input signals of the RTC are the input signals of U5,including U6-out,U4-Y4,U4-Y3,U4-Y2,and U4-Y1.Valid replacement is made according to the principle.The original input signals are replaced,and the mapping relations between signal combinations before and after replacement are not affected.

When U1-Y4,U1-Y3,U2-out,and U3-Y2 replace any signal of U5 input ports,it will cause one-to-many mapping or further lead to a contradiction,and they are invalid replacements.Finally,U1-Y1,U1-Y2,and U3-Y1 signals may replace some signals of U5 input port.U1-Y1 can be replaced by U4-Y1 and U4-Y2.U1-Y2 can be replaced by U4-Y3,U4-Y4,and U6-out.U3-Y1 can be replaced by U4-Y3,U4-Y4,and U6-out.With the addition of the conventional RTC design method,it has nine schemes.

The same GADPSO parameters are set to make 10 circuit evolutions,the maximum number of evolution iterations is 20000.The changes of hardware resources consumption and fitness are statistically analyzed,as separately shown in Figs.9 and 10.

Fig.9 includes average hardware resources consumption of RTC evolutions with nine schemes.As a whole,the average hardware resources consumption of the RTC in every schemeis rapidly reduced before 1500th time.After 1500th time,the hardware resources consumption is reduced slowly.RTC evolution with the method of replacing U4-Y1 with U1-Y1 consumes the least average hardware resources,and RTC evolution with the method of replacing U6-out with U1-Y2 consumes the most average hardware resources.The required hardware resources consumption for a conventional method to design the RTC is between the two parties.In other words,the RTC design method based on global signal optimization may consume less or more hardware resources than that with the conventional method.As for RTC design in the experiment,during RTC evolutions with U1-Y1 replacing U4-Y1,U1-Y1 replacing U4-Y2,U3-Y1 replacing U4-Y3,and U3-Y1 replacing U6-out,the average hardware resources consumption is less than that of the conventional RTC design method.DuringRTC evolutionswithU1-Y2 replacing U4-Y3 and U1-Y2 replacing U4-Y4,the hardware resources consumptions are almost the same.However,during RTC evolutions with U1-Y2 replacing U6-out and U3-Y1 replacing U4-Y4,theformerconsumesmorehardwareresources compared with that of the conventional RTC design method.Therefore,the scheme with U1-Y1 replacing U4-Y1 consumes the leasthardware resources based on globalsignal optimization.

Table 7 Related data of the corresponding conventional RTC evolution to Situation 3.

Fig.8 RTCs designed with different methods in Situation 3.

Fig.10 shows the average fitness change curves of RTC evolutions under nine schemes.Since the number of data points of every curve reaches 20000,the average fitness curves change slightly after the number of evolutionary iterations is more than 500.Therefore,the data in the previous 500 points are selected for explanation.

The change of average fitness significantly reflects the circuit evolutionary convergence speed.It can be seen from Fig.10 that the average fitness of every scheme rises rapidly in the previous 180 times.Such three schemes as replacing U4-Y1 with U1-Y1,replacing U4-Y2 with U1-Y1,and replacing U4-Y4 with U1-Y2 have achieved the best fitness of 1.Between 180th time and 500th time,the average fitness of the rest schemes increases slowly.In 500th circuit evolution,the best fitness is reached for all schemes except the scheme of replacing U6-out with U1-Y2.As a whole,the convergence speeds of the rest seven schemes are quicker than that of the conventional RTC design method.

Fig.9 Average hardware resources consumption of EA with nine schemes.

Fig.10 Average fitness change curves of EA with nine schemes.

Fig.11 Comparison of the previous six circuit evolutions data of the optimal scheme and the conventional RTC design method.

Fig.12 Circuit evolution success rates of the two schemes in different evolutionary times.

After balancing the average hardware resources consumption and average fitness change curves(convergence speed),the scheme with U1-Y1 replacing U4-Y1 is the optimal scheme based on global signal optimization.The performance of the optimal scheme(U1-Y1 replacing U4-Y1)is separately compared with the conventional RTC design method,and the maximum number of iteration times of EA is set as 20000.The related data are shown in Table 8.

It can be seen from Table 8 that both of the two schemes can successfully evolve the RTC within the maximum evolutionary times.The performances of the two schemes are weighed by three important indicators,i.e.,the time for first RTC evolution,the number of evolutionary iterations for first evolution,and the hardware resources consumption for the maximum evolutionary times.The three indicators in Table 8 are contrasted obviously.The optimal scheme(U1-Y1 replacing U4-Y1)first successfully evolves the RTC in 0.23266 s on average,but the conventional method spends 0.27330 s on average.The average number of evolutionary iteration times for the optimal scheme to first evolve the RTC is 87,but for the conventional RTC design method it is 193.The final average number of hardware resources consumed by the optimal scheme is 10,but that consumed by the conventional RTC design method is 14.The effectiveness and superiority of the optimal scheme are verified by the above data.

Table 9 Related data of the corresponding conventional RTC evolution to Situation 5.

Figs.9 and 10 only show the average data of the 10 simulation experiments,and any single simulation experiment is not analyzed.In order to effectively and dynamically compare the advantages and disadvantages of the two schemes,only the previous six circuit evolutions data of the simulation experiments are shown in Fig.11.

It can be clearly seen from Fig.11 that,in the six simulation experiments,the reduction speed of the hardware resources consumption of the optimal scheme(U1-Y1 replacing U4-Y1)is significantly faster than that of the conventional RTC design method,and the hardware resources consumption for the conventional RTC design method is located at 14 for a long time and seldom decreases with the increase in the number of circuit evolution.Fig.11 compares the two schemes in terms of hardware resources consumption and Fig.12 compares the two schemes in terms of evolutionary success rate.

The histogram in Fig.12 clearly shows data comparison of the two schemes.Data are statistically recorded when 50 times are increased every time from 10th evolutionary iterations on,totaling 10 groups of data.It can be clearly known from Fig.12 that the evolutionary success rate in 10th time is 10%,and the evolutionary success rate in 110th time reaches 70%,but such a rate of the conventional RTC design method in 110th time is only 20%.In 210th time,the RTC evolutionary success rate of the optimal scheme reaches 100%,but that of the conventional RTC design method is only 60%and doesn’t reach 100%until 460th time.Compared with the conventional RTC design method,the optimal scheme features a higher circuit evolutionary success rate and a faster convergence speed as demonstrated comprehensively in Fig.12.

U1-Y1 is not the direct input port of U5,but it is the global node signal of the entire circuit system.To sum up,the scheme with U1-Y1 replacing U4-Y1 is characterized with less hardware resources consumption,faster circuit evolutionary speed,and higher evolutionary success rate based on global signal optimization.Therefore,it is the optimal scheme.

4.3.5.Corresponding example analysis to Situation 5

It is assumed that faults occur in the 5th,19th,and 30th states of Y2 of U3(U3-Y2),and the output signal of the RTC shall be 00001000000000000010000000000100.The five input signals of the conventional RTC design method in Situation 5 are U1-Y1,U1-Y2,U1-Y3,U1-Y4,and U1-Y5.Based on global signal optimization,the RTC cannot be successfully evolved no matter which node signal replaces the input signal of the conventional RTC design method,so the conventional RTC design method is the only choice.

According to the faults in Situation 5,a conventional method is used to design the RTC and the same GADPSO parameters are set to make eight circuit evolutions,the maximum number of evolution iterations is 20000.The related simulation data of the corresponding circuit are shown in Table 9.

It can be seen from Table 9 that,with respect to the faults in Situation 5,the conventional RTC design method features a low circuit evolutionary success rate within the maximum regulated evolutionary times of 20,000.However,the population’s global fitness reaches 0.9688 at the maximum evolutionary iteration times,approaching the optimal fitness of ‘1”.If the maximum number of evolutionary iteration times is increased,the circuit evolutionary success rate will increase.However,the time for circuit evolution will also increase.

It can be found from the above five situations that the RTC design method based on global signal optimization will consume the least hardware resources,shorten the successful evolutionary time,and improve the evolutionary success rate.On faults in Situation 1,Situation 2,Situation 3,and Situation 4,the RTC designed method based on global signal optimization is distinctly superior to those designed with the conventional methods.Although only a conventional RTC design method can be used for the fault in Situation 5,it does not affect the feasibility and effectiveness of RTC optimal design based on global signal optimization.Signals are replaced according to the rules as mentioned in Section 3.1,so that the output signals of the designed RTC cannot be changed.

5.Conclusions

The optimal design of RTC applied in electronic circuit fault self-repair based on global signal optimization is put forward in this paper based on the previously proposed EHW-based and RBT-based electronic circuit fault self-repair strategy.After analysis of all global node signals and on the condition that signal sequence is consistent,the input ports of an RTC designed by means of conventional methods are selectively replaced to achieve optimal design of the RTC.

The design theory of RTC based on global signal optimization is deeply researched,application conditions and matters needing attention of RTC optimal design based on global signal optimization are analyzed,and the optimal design flow of RTC is researched.Eventually,classic circuit systems are selected to verify the feasibility and effectiveness of the proposed RTC optimaldesign based on globalsignal optimization.

Compared with the conventional RTC design method,the RTC design method based on global signal optimization is capable of reducing circuit evolution iteration times,improving circuit evolution precision,accelerating circuit evolution convergence,decreasing hardware resource consumption,and improving the success rate of RTC evolution.Therefore,the RTC optimal design method based on global signal optimization is superior to the conventional RTC design method and has a significant engineering application value.

Acknowledgments

This study was supported by the National Natural Science Foundation of China(Nos.61271153,61372039).

1.Adrian S,Alex F,Ken H,Carlos SL.Evolvable hardware for space applications.Lect Notes Comput Sci 1998;1478(1):1–8.

2.Bloom G,Narahari B,Simha R,Zambreno J.Providing secure execution environments with a last line of defense against trojan circuit attacks.Comput Secur 2009;28(7):660–9.

3.Seung WL,Hwa KL.Reliability prediction system based on the failure rate model for electronic components.J Mech Sci Technol 2008;22(5):957–64.

4.Wu S,Jiao ZX,Yan L,Yu JT,Chen CY.A fault-tolerant tripleredundant voice coil motor for direct drive valves:design,optimization,and experiment.Chin J Aeronaut 2013;26(4):1071–9.

5.Gan L,Xu JP,Bernard TH.A computer-integrated FMEA for dynamic supply chains in a flexible-based environment.Int J Adv Manuf Technol 2012;59(5):697–717.

6.Gao GJ,Wang YR,Yao R.Research on redundancy and tolerance of system with different structures.Transducer Micro-Syst Technol 2007;26(10):25–8[Chinese].

7.Cui G,Li B,Wang DS,Wang TZ,Yang XZ.Synchronization mechanisms based on TMR fault tolerant computer system.J Harbin Inst Technol 1997;29(3):68–71.

8.Kima KJ,Cho SB.Automated synthesis of multiple analog circuits using evolutionary computation for redundancy-based fault-tolerance.Appl Soft Comput 2012;12(4):1309–21.

9.Kristian G,Snorre A.Improving yield and defect tolerance in subthreshold CMOS through output-wired redundancy.J Electron Test 2008;1(24):157–63.

10.Yun WY,Song YM,Kim HG.Multiple multi-level redundancy allocation in seriessystems.ReliabEng SystSaf2007;92(3):308–13.

11.Zhang XM,Hoang P,Carolyn RJ.Reliability models for systems with internal and external redundancy.Int J Syst Assur Eng Manage 2010;1(4):362–9.

12.Oussama T,Mohamed S.Using dynamic task level redundancy for openMP fault tolerance.Lect Notes Comput Sci 2012;7179(1):25–36.

13.Zhang JB,Cai JY,Meng YF,Meng TZ.Fault self-repair strategy based on evolvable hardware and reparation balance technology.Chin J Aeronaut 2014;27(5):1211–22.

14.Moritoshi Y,Jung HK,Ikou Y.Evolvable reasoning hardware:Its prototyping and performance evaluation.Genet Program Evolvable Mach 2001;2(3):211–30.

15.Zebulum RS,Stoica A,Keymeulen D,Sekanina L,Ramesham R,Guo X.Evolvable hardware system at extreme low temperatures.Lect Notes Comput Sci 2005;3637(1):1–37.

16.Hu CY,Yao H,Yan XS.Multiple particle swarms coevolutionary algorithm for dynamic multi-objective optimization problems and itsapplication.J ComputResDevelop 2013;50(6):1313–23[Chinese].

17.Zhang JB,Wan RX,Cai JY,Meng YF,Meng TZ.Survey of electronic and circuit fault self-repair based on EHW.Appl Res Comput 2013;30(12):3521–4[Chinese].

18.Yao R,Chen QQ,Li ZW,Sun YM.Multi-objective evolutionary design of selective triple modular redundancy systems against SEUs.Chin J Aeronaut 2015;28(3):804–13.

19.Yao R,Wang YR,Yu SL,Chen ZW.Design and experiments of enhanced fault-tolerant triple-module redundancy systems capable of online self-repairing.Acta Electron Sin 2010;38(1):177–83[Chinese].

20.Pawar SN,Bichkar RS.Genetic algorithm with variable length chromosome for network intrusion detection.Int J Autom Comput 2015;12(3):337–42.

21.Keymeulen D,Zebulum RS,Jin YL,Stoica A.Fault tolerant evolvable hardware using field-programmable transistor arrays.IEEE Trans Reliab 2000;49(3):305–16.

22.Jongbin I,Jungsun P.Stochastic structural optimization using particle swarm optimization,surrogate models and bayesian statistics.Chin J Aeronaut 2013;26(1):112–21.

23.Garvie M,Adrian T.Evolution of self-diagnosing hardware.Lect Notes Comput Sci 2003;26(6):238–48.

24.Gong MG,Cai Q,Chen XW,Ma LJ.Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition.IEEE Trans Evol Comput 2014;18(1):114–30.

25.Oreifej Rashad S,DeMara Ronald F.Intrinsic evolvable hardware platform for digital circuit design and repair using genetic algorithms.Appl Soft Comput 2012;12(8):2470–80.

26.Muhammad I,Will NB,Zhang MJ.Reusing building blocks of extracted knowledge to solve complex,large-scale boolean problems.IEEE Trans Evol Comput 2014;18(4):465–80.

27.Hao GF,Wang YR,Zhang Z,Yuan P,Kong DM.In-chip fault localization and self-repairing method for reconfigurable hardware.Acta Electron Sin 2012;40(2):384–8[Chinese].

28.Mateusz M,Jurgen T,Ali A,Christophe B.The Erlangen slot machine:a dynamically reconfigurable FPGA-based computer.J VLSI Sig Process 2007;47(1):15–31.

29.Ali B,Almaini AEA,Kalganova T.Evolutionary algorithms and their use in the design of sequential logic circuits.Genet Program Evolvable Mach 2004;5(1):11–29.

30.Wang FL,Tan KC.Evolvable hardware in evolutionary robotics.Auton Robots 2004;16(1):5–21.

31.Kyrre Glette JT,Yasunaga M.An online EHW pattern recognition system applied to face image recognition.Lect Notes Comput Sci 2007;4448(1):271–80.

32.Vedeshenkov VA.Local self-diagnosis offailed components in digital systems.Autom Remote Contr 2004;65(5):800–13.

33.Niu B,Zhu YL,He XX,Wu H.MCPSO:A multi-swarm cooperativeparticleswarm optimizer.ApplMath Comput 2007;185(2):1050–62.

34.Jiang Y,Hu TS,Huang CC,Wu XN.An improved particle swarm optimization algorithm.Appl Math Comput 2007;193(1):231–9.

35.Poli R,Kennedy J,Blackwell T.Particle swarm optimization.Swarm Intell 2007;1(1):33–57.

36.Wang XF,Qiu J,Liu GJ.Discrete particle swarm optimization algorithm for gearbox fault symptom selection.J Aerospace Power 2005;20(6):969–72.

37.Tao XM,Xu J,Yang LB,Liu Y.Improved cluster algorithm based on k-means and particle swarm optimization.J Electron Inform Technol 2010;32(1):92–7[Chinese].

38.Zhang JB,Cai JY,Li DY,Pan G.Ternary code implemented in Hardware Evolution research.Microelectron Comput 2013;30(3):1–4[Chinese].

Zhang Junbin is a Ph.D.student in the Department of Electronic and Optical Engineering at Mechanical Engineering College.He received his B.S.degree from University of Electronic Science and Technology of China,and his M.S.degree from Mechanical Engineering College.His research interest is evolvable hardware and fault self-repair of electronic systems.

Cai Jinyan is a professor and Ph.D.advisor at Mechanical Engineering College.She received her B.S.degree from Nanjing University of Science and Technology,her M.S.degree from Tsinghua University,and her Ph.D.degree from Nanjing University of Science and Technology.Her area of research includes electronic system fault diagnosis,electronic system reliability,fault self-repair,and evolvable hardware.

Meng Yafeng is an associate professor and Master’s advisor at Mechanical Engineering College,where he received his B.S.,M.S.,and Ph.D.degrees.His area of research includes electronic system fault diagnosis and electronic system reliability.

28 February 2016;revised 1 April 2016;accepted 3 May 2016

Available online 22 October 2016

Evolutionary algorithm;

Evolvable hardware;

Fault self-repair;

Optimal design;

Reparation balance technology

Ⓒ2016 Production and hosting by Elsevier Ltd.on behalf of Chinese Society of Aeronautics and Astronautics.This is an open access article under the CC BY-NC-ND license(http://creativecommons.org/licenses/by-nc-nd/4.0/).

*Corresponding author.Tel.:+86 311 87994289.

E-mail address:cjyrad@163.com(J.Cai).

Peer review under responsibility of Editorial Committee of CJA.

Production and hosting by Elsevier

http://dx.doi.org/10.1016/j.cja.2016.09.013

1000-9361Ⓒ2016 Production and hosting by Elsevier Ltd.on behalf of Chinese Society of Aeronautics and Astronautics.This is an open access article under the CC BY-NC-ND license(http://creativecommons.org/licenses/by-nc-nd/4.0/).