Based On Boolean Process Waveform Space, As Well As Segmented Insertion Sort Algorithm

With high speed and large-scale integration of electronic circuits, Boolean algebra is insufficient to describe the complicated logic behavior of digital circuits. The main reason for that is loss of timing information, which is essential for high-speed circuits. The concept of Boolean process was then introduced and first proposed by Min in 1994. It combines Boolean algebra expression with time information to describe behavior of a digital circuit. It has made substantive progress at path sensitization, power dissipation estimation, IDDT and delay fault diagnosis. Theoretically, it is necessary to establish some mathematical foundation in order to define distance, limit and continuity based on Boolean process. This thesis contributes to Boolean process in defining limit and continuity in waveform space of digital signals, and applying the concept to some practical problems. The contributions include the following.To define the space of waveforms.To define distance, limit, a delay operator, which is consistent to practical problems in waveform space.To deduce out that the waveform space is a Banach space using the Boolean operation. This is the core of the theory.It is noticed that the definitions of limit and difference of waveforms reflect path sensitization in a circuit. It is interesting to note the consistency between this theory and the reality.To deduce the properties and applications of converse operations or generalized converse operations of waveform operations in waveform space.Based on the above discussions, some theoretical foundation for testing of CMOS circuits and IDDT testing is then established.All the theoretical work is applied to 1C design and test applications with some examples.IDDT ATPG of genetic algorithm based on Boolean process. Experimental results show that more than 20% stuck-open faults inpart of IS85 and ISCAS89 circuits can produce 2.5 times IDDr variation, and then can be detected by IDDT testing. Also show that this algorithm excels previous IDDT ATPG algorithm.In addition to the theoretical work, on the way for practical applications, sorting algorithms are investigated. As well known, sorting algorithm is very important for application, especially data mining recently. This thesis presents a subsection insertion-sorting algorithm with equal probability data segmentation and multi-resource data equal probability statistical subsection insertion-sorting algorithm. Experiments show that these algorithms excel others of the same kind respectively. And quantitative evaluation for the algorithms was given.