Exploiting K-Distance Signature
for Boolean Matching and G-Symmetry Detection?
Kuo-Hua Wang
Dept.of Computer Science and Information Engineering
Fu Jen Catholic University
Hsinchuang City,Taipei County24205,Taiwan,R.O.C.
khwang@https://www.doczj.com/doc/6411210302.html,.tw
ABSTRACT
In this paper,we present the concept of k-distance signature which is a general case of many existing signatures.By exploiting k-distance signature,we propose an Algorithm for Input Di?erentiation(AID)which is very powerful to distinguish inputs of Boolean functions.Moreover,based on AID,we propose a heuristic method to detect G-symmetry of Boolean functions and a Boolean matching algorithm.The experimental results show that our methods are not only e?ective but also very e?cient for Boolean matching and G-symmetry detection.
Categories and Subject Descriptors:B.6.3[Hardware] Logic Design:Design Aids-Automatic Synthesis.
General Terms:Algorithms,Design,Veri?cation.
1.INTRODUCTION
Boolean matching is a technique to check if two functions are equivalent under input permutation and input/output phase assignments(so called NPN-Class).It can be ap-plied in technology mapping and logic veri?cation.In the early90’s,the work in the article[1]opened the door of re-search on Boolean matching for technology mapping.Over the past decade,many studies had been devoted to Boolean matching and various Boolean matching methods were pro-posed[1]-[6].Among these methods,exploiting signatures and computing canonical forms of Boolean functions are the most successful approaches to deal with Boolean matching. The idea behind using signatures for Boolean matching is very simple.Various signatures can be de?ned to char-acterize the input variables of Boolean functions,where the variables with di?erent signatures can be distinguished with each other and many infeasible permutations and phase as-signments can be pruned quickly.The major issue of sig-nature based approach is the aliasing problem,i.e.two or more input variables have the same signature and therefore can’t be distinguished.In such a case,an exhaustive search ?This work was supported by the National Science Council of Taiwan under Grants NSC94-2215-E-030-006. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro?t or commercial advantage and that copies bear this notice and the full citation on the?rst page.To copy otherwise,to republish,to post on servers or to redistribute to lists,requires prior speci?c permission and/or a fee.
DAC2006,July24–28,2006,San Francisco,California,USA. Copyright2006ACM1-59593-381-6/06/0007...$5.00.is still required to?nd the input mapping.The paper[8]
had shown signatures have the inherent limitations to dis-
tinguish all input variables for those Boolean functions with G-symmetry.To the best of our knowledge,there were few research devoted to detect G-symmetry of Boolean functions
[9][10].
Yet,another group of research was based on computing
canonical forms of Boolean functions[5][6].Using this ap-proach,each NPN-class of functions will be represented as a unique canonical function.If two functions can be transformed to the same canonical function,then they are matched.In a recent paper[6],a new approach combin-ing signature and canonical form of Boolean functions was proposed.Their method was based on generalized signa-tures(signatures of one or more variables)and canonicity-producing(CP)transformation for Boolean matching under input permutation and input phase assignment.
In this paper,we consider permutation independent
Boolean matching problem.A new k-distance signature will
be presented and correlated with many previously proposed signatures.Based on k-distance signature,we will propose a very e?ective Algorithm for Input Di?erentiation(AID) to distinguish inputs of Boolean functions.With respect to (w.r.t.)the aliasing problem of signatures,we also present a heuristic method to detect G-symmetry of Boolean https://www.doczj.com/doc/6411210302.html,bining AID,G-symmetry detection,and trans-formation of Ordered Binary Decision Diagrams(OBDD’s), we also propose a Boolean matching algorithm to match two Boolean functions.
The remainder of this paper is organized as follows.Sec-
tion2brie?y reviews Boolean matching and some previ-
ously proposed signatures.Then we introduce k-distance signature and propose a heuristic to detect G-symmetry of Boolean functions in Section3and Section4,respectively. Our AID and Boolean matching algorithms will be described in Section5.Finally,the experimental results and conclu-sion will be given in Section6and Section7,respectively.
2.PRELIMINARIES
2.1Boolean Matching and Symmetry
Boolean matching is to check the equivalence of two func-tions under input permutation and input/output phase as-signment.Let B n denote the multi-dimensional space spanned by n binary-valued Boolean variables.A minterm is a point in the Boolean space B n.A literal is a vari-able x i(positive literal)or its complement formˉx i(negative literal).The weight of a minterm m,denoted as W(m),
32.2
is the number of positive literals x i ’s involved in m .The
cofactor of f (x 1,···,x i ,···,x n )w.r.t.the literal x i (ˉx
i )is f x i =f (x 1,···,1,···,x n )(f ˉx i =f (x 1,···,0,···,x n )).The satisfy count of f ,denoted as |f |,is the number of minterms for which the function value is 1.
Given two inputs x i and x j of a function f ,(x i ,x j )is a symmetric pair of f if and only if f is invariant under the swapping of x i and x j ,i.e.f ˉx i x j =f x i ˉx j .Let X s be an input subset of a Boolean function f (X ).X s is a maximal symmetric set of f if and only if f is not symmetric w.r.t.X s ∪{x i }for any input x i ∈X ?X s [8].f (X )is a totally symmetric function if and only if X is a maximal symmetric set of f .In other words,f evaluates to 1w.r.t.all the minterms with weight i ∈A ,where A ?{0,1,···,n }and
n is the number of input variables.It is denoted as S n
A and
can be shortened as S n
k if A ={k }.
2.2Review of Some Signatures
Consider a Boolean function f (X )and an input variable x i ∈X .The signature of f w.r.t.x i is a description of the input x i that is independent of the permutation of the inputs of Boolean function f .Four types of previously proposed signatures are rede?ned as below.
Definition 2.1.The cofactor-satisfy-count signature of f w.r.t.x i is the integer |f x i |.
Definition 2.2.The partner signature [3]of f w.r.t.x i is an integer vector [p 0,p 1,p 2,p 3],where p 0,p 1,p 2,and p 3are |ˉf ˉx i ·ˉf x i |,|ˉf ˉx i ·f x i |,|f ˉx i ·ˉf x i |,and |f ˉx i ·f x i |,respectively.Definition 2.3.The cofactor-breakup signature [4]of f w.r.t.x i is an integer vector [b 1,···,b i ,···,b n ],where b i is the number of minterms with weight i in the domain x i =1,i.e.|f x i |=P n i =1b i .Definition 2.4.The cross signature [7]of f w.r.t.x i is an integer vector [|f x i |,|f x i ˉx 1|,···,|f x i ˉx n |].Definition 2.5.Let s 1and s 2be two di?erent signature types.We say that s 1dominates s 2if two inputs x i ,x j ∈X of any Boolean function f (X )can be distinguished by s 2,then they can be distinguished by s 1as well.
Theorem 2.1.The partner and cofactor-breakup signa-tures dominate the cofactor-satisfy-count signature .
Theorem 2.2.The cross signature dominates the cofactor-satisfy-count signature .
2.3G -Symmetry
Let G ?P n ,where P n involves all input permutations
w.r.t.an input variable set X .A Boolean function f (X )is G -symmetric if and only if f is invariant under any input permutation ψ∈G .There are three types of G -symmetry dis-cussed in the paper [8]:group symmetry (g-symmetry ),hier-archical symmetry (h-symmetry ),and rotational symmetry (r-symmetry ).
Definition 2.6.Consider a Boolean function f (X ).Let X i =[x i 1,x i 2,···,x i k ]and X j =[x j 1,x j 2,···,x j k ]be two
disjoint ordered subsets of X with k ≥1.f is group sym-metric (g-symmetric )w.r.t.to X i and X j if and only if f is invariant under the swapping of x i m and x j m for m =1,2,···,k .We call (X i ,X j )is a g-symmetric pair of f .Example 2.1.Let f =x 1(x 2+ˉx 3)+x 4(x 5+ˉx 6).It is obvious that f is g-symmetric w.r.t.ordered sets [x 1,x 2,x 3]and [x 4,x 5,x 6].
By Def.2.6,the traditional symmetric pair can be viewed as a special case of g-symmetry pair with k = 1.It is easy to prove that g-symmetric pair is an equivalence re-lation.That is,a larger g-symmetric sets can be derived from g-symmetric pairs directly.In addition,h-symmetry is a special case of g-symmetry,i.e.all swapping groups are maximal symmetric sets.
Definition 2.7.Let X i and X j be two maximal sym-metric sets of f (X ).f is h-symmetric w.r.t.X i and X j if and only if f is g-symmetric w.r.t.X i and X j .
Example 2.2.Consider the function f =x 1x 2x 3+x 4x 5x 6+x 7x 8x 9.There are three maximal symmetric sets X 1={x 1,x 2,x 3},X 2={x 4,x 5,x 6},and X 3={x 7,x 8,x 9}.It is clear that f is h-symmetric w.r.t.the permutation of X 1,X 2,and X 3.
Definition 2.8.Consider a function f (X )and an or-dered subset X i of X .Without loose of generality,let X i =[x 1,x 2,···,x k ]which is not a symmetric set of f for k ≥3.f is rotational symmetric (r-symmetric )w.r.t.X i if and only if f is invariant under the permutations ψ=(x m ,x m +1,···,x k ,x 1,···,x m ?1)for m =1,2,···,k .Example 2.3.Let f =x 1x 2+x 2x 3+x 3x 4+x 4x 5+x 5x 1.f is invariant under rotating the variables of f w.r.t.the ordered set [x 2,x 3,x 4,x 5,x 1].
3.K-DISTANCE SIGNATURES
3.1Five types of K-Distance Signature
Let p =(m a ,m b )be a pair of minterms w.r.t.the same input set.The mark of p ,denoted as Mark (p ),is the product by anding the literals involved in m a which are di?erent from the literals involved in m b .For example,consider the minterm pair p =(m a ,m b )w.r.t.the in-put set X ={x 1,x 2,x 3,x 4,x 5},where m a =01100and m b =10000.Then Mark (p )=ˉx 1x 2x 3.
Given two functions f and g w.r.t.the same input set,consider any minterm pair p =(m a ,m b )with mark M i ,where m a and m b are from f and g ,respectively.Assume the number of literals in the mark M i is k ,denoted as |M i |.
Let S k M i and |S k
M i
|=w i denote the set involving all minterm pairs with mark M i and the number of minterm pairs in S k M i
,respectively.Then the tuple (w i ,M i )can characterize a relation between f and g .If we further classify (w i ,M i )’s in terms of the number of literals involved in M i ,then each group can be viewed as a signature showing the k-disjoint situations between f and g .In the following,we de?ne the k-distance signature and give a simple example.
Definition 3.1.Consider two functions f (X )and g (X ).Given an integer k >0,the k-distance signature of f w.r.t.to g ,denoted as ksig (f,g,k ),can be formally de?ned as
ksig (f,g,k )={(w i ,M i )||S k
M i
|=w i ,|M i |=k }(1)
,where S k
M i
={p =(m a ,m b )|Mark (p )=M i ,?m a ∈f,?m b ∈g }.
Example 3.1.Consider two functions f =x 1ˉx 2x 3=P m (5)and g =(ˉx 1+x 2)x 3=
P
m (1,3,7).There are two minterm pairs (m 5,m 1)and (m 5,m 7)with mark x 1and ˉx
2,respectively.So ksig (f,g,1)={(1,x 1),(1,ˉx 2)}.For k =2,ksig (f,g,k =2)={(1,x 1ˉx 2)}because of one minterm pair (m 5,m 3)with mark x 1ˉx 2.Instead of computing Equation (1)directly,given an input x i ,ksig (f,g,k )can be computed in a recursive way as be-low.
ksig (f,g,k )=ksig (f ˉx i ,g ˉx i ,k )S
ksig (f x i ,g x i ,k )S ˉx i ·ksig (f ˉx i ,g x i ,k ?1)S x i ·ksig (f x i ,g ˉx i ,k ?1)
(2)
By Def.3.1,ksig (f,g,k )can be viewed as a 2k
×C n k
integer matrix M with rows and columns corresponding to di?erent input phase assignments and input combinations of k inputs from X ,respectively.
Example 3.2.Consider f (x 1,x 2,x 3,x 4)=P
(0,1,3,6,8,
13,14,15).ksig (f,f,k =1)is a 2×C 4
1integer matrix shown below:
x 1x 2x 3x 401
?20222022
–W.r.t.k =2,it is a 22×C 4
2integer matrix shown below:
x 1x 2x 1x 3x 1x 4x 2x 3x 2x 4x 3x
400011011264201211000001000001201211
375The following de?nition shows how to extract the signa-ture from ksig (f,g,k )w.r.t.an input x i ∈X .
Definition 3.2.Consider a target function f (X )and an anchor function g (X ).Let x i be an input of X .Given an integer k >0,the k-distance signature of f w.r.t.x i and g is
an integer vector [v 1,···,v j ,···,v s ]with s =2k ?1×C n ?1
k ?1,
where v j =|f x i m a |and m a ∈B
k ?1
which is expanded by any (k ?1)-input subset of X without involving x i .Example 3.3.Consider the same function f (X )shown in Example 3.2and an input x 1∈X .Given k =2,the k-distance signature of f w.r.t.x 1and anchor function f is a six-integer vector shown below:
[|f x 1ˉx 2|,f x 1ˉx 3|,f x 1ˉx 4|,|f x 1x 2|,f x 1x 3|,f x 1x 4|]=[0,0,0,2,0,1]
According to Equation (2),the time complexity of comput-ing k-distance signature is O (p k +1×q k +1),where p and q are the sizes of OBDD’s representing f and g ,respec-tively.It is time consuming to compute k-distance signa-ture w.r.t.a large number k .Therefore,we propose ?ve k-distance signatures w.r.t.k =1and use ksig (f,g )to de-note ksig (f,g,k =1)for short.It is clear that ksig (f,g )is a 2n -integer vector,where each tuple corresponds to the number of pairs of minterms which only involve one di?erent literal x i or ˉx i .
?Type 0:g =1In fact,type-0k-distance signature is equivalent to the cofactor satisfy-count signature.However,it can com-pute the cofactor-satisfy-count signatures w.r.t.all in-puts simultaneously.
?Type 1:g 1=f and g 2=ˉf
?Type 2:g =S n
i for i =0,1,···,n
S n
i is a totally symmetric function involving all minterms with weight i .
?Type 3:g =x i for i =1,···,n
01111000x 1x 2
x 3x 4
(a) Karnaugh Map
(b) BDD
x 2
1x 3x 4
x 1
00011110
01111
000000
1110
B A A
B
A
1
01
1
10
Figure 1:Karnaugh map and BDD of f =x 1x 2+x 3x 4.Below,we will describe a new type of k-distance signa-ture based on communication complexity.Suppose that X b
is the set of inputs (or referred as bounded set )which had been distinguished by some signatures.The communication complexity of f w.r.t.X b is de?ned as the number of dis-tinct cofactors of f w.r.t.m i ,where m i is a minterm in the Boolean space spanned by X b .For example,consider f =x 1x 2+x 3x 4and bound set X b ={x 1,x 2}.Fig.1(a)and 1(b)show the Karnaugh map of f w.r.t.the partition X b /X ?X b and OBDD of f with order x 1 Given a Boolean function f (X )and a bounded set X b including all distinguished inputs,let m be the communica-tion complexity of f w.r.t.X b .Then f can be decomposed as f =P m i =1b i (X b )·u i (X ?X b ),where f m j =u i for each minterm m j ∈b i .Type 4k-distance signature is thus de-?ned as below. ?Type 4:g =b i for i =1,···,m Theorem 3.1.Type 0k-distance signature is equivalent to the cofactor-satisfy-count signature . i =1l i ,where l i is x i or ˉx i .For each literal l i ∈m a ,since g is a tautology,it is clear that there exists a minterm m b ∈g ,where Mark (m a ,m b )=l i .So the tuple on l i in type 0k-distance signature will increase accordingly.After checking all minterms in f in such a way,then each tuple is equivalent to the cofactor-satisfy-count signature w.r.t.literal x i or ˉx i .It is proved. Theorem 3.2.Type 1k-distance signature is equivalent to the partner signature. .The tuples in ksig (f,ˉf )corresponding to x i and ˉx i are equal to p 1and p 2,respec-tively.Moreover,p 0can be computed as 2n ?1?(p 1+p 2+p 3).It is proved. Theorem 3.3.Type 2k-distance signature is equivalent to the cofactor-breakup signature. weight j .Consider g =S n j ?1.Consider the domain x i =1.For each minterm m a ∈f with weight j ,there must exist a minterm m b ∈g and Mark (m a ,m b )=x i .So b j can in-crease 1because of this minterm pair.W.r.t.di?erent S n j ’s,all b j ’s can be computed in the same way.It is proved.Theorem 3.4.Type 3k-distance signature is equivalent to the cross signature. Let us consider a Boolean function f (X )with symmet-ric inputs ?rst.Without loose of generality,let MSS ={x 1,x 2,···,x m }be a maximal symmetric set of f .In our AID algorithm,x 1will be used to represent MSS .While computing the distinct factor of f w.r.t.any signature type,the remaining m ?1inputs can be viewed as the distin-guished inputs of f . Example 3.4.Let f =x 1x 2+x 3x 4+x 5.Type 0k-distance signature s 0of f is shown below: x 1 x 2x 3x 4x 501?10101010713 13 13 13 16 –It is clear that {x 1,x 2}and {x 3,x 4}are symmetric sets of f .Consequently,x 2and x 4are included in the distinguished input set DI .x 5is also added into DI because of |f x 5|=16=13.So d f (f,s 0)=3/5=0.6. 4.DETECTION OF G -SYMMETRY 4.1Check of Group Symmetry There are two phases in our heuristic to detect g-symmetry of Boolean functions. Phase 1:Search of Candidate Swapping Pairs Suppose f is g-symmetric to X 1=[x 11,x 12,···,x 1k ]and X 2=[x 21,x 22,···,x 2k ].Let A =[a 1,a 2,···,a i ,···,a k ]and B =[b 1,b 2,···,b i ,···,b k ]be constructed by the fol-lowing rule:if a i =x 1i (or x 2i ),then b i =x 2i (or x 1i ).It is easy to prove that f is also g-symmetric w.r.t.A and B .Therefore,it doesn’t matter to ?nd any speci?c ordered sets A and B .We only need to search the candidate pairs of variables for swapping.In our method,we consider the swapping of two indistinguishable inputs x i and x j and use type 4k-distance signature to ?nd their mutual dependency which can help search the other candidate swapping pairs.Consider the function f =x 1(x 2+ˉx 3)+x 4(x 5+ˉx 6).It has three indistinguishable input groups X 1={x 1,x 4},X 2={x 2,x 5},and X 3={x 3,x 6}.The following matrix shows the positive phase of type 4signatures w.r.t.all in-put variables.Each entry corresponds to the cofactor count of f x i x j . X 1X 2X 3z }|{x 1x 4z }|{x 2x 5z }|{x 3x 6X 1:x 1 x 4 X 2:x 2 x 5 X 3:x 3 x 6 2666664 0141614101314014161310161401211101416120101110131113071310 1011 710 37 77775 x 1x 2x 3x 4x 5 x 1x 2x 3x 4x 5 2 66 64087788087778087778088778 37775(a )M 1x 1x 2x 4x 5x 3x 1x 2x 4x 5x 3 266640878780778770888780778870 37775(b )M 2 Figure 2:Type 4Signatures with Di?erent Input Orders. Consider the input group X 1w.r.t.the above matrix.If we swap the inputs x 1and x 4,two pairs (x 2,x 5)and (x 3,x 6)must be also swapped to make this matrix invariant.The same situation can happen to swapping the inputs in X 2and X 3.With such an observation,we can obtain three swapping candidate pairs.Then f can be checked if it is invariant under the swapping of these candidate pairs.Our heuristic chooses the inputs from the smallest group as the initial swapping candidate pair. Phase 2:Check of Group Symmetry with Transpo-sitional Operator Consider a function f (X )and two k -input ordered subsets X 1and X 2of X .In the article [9],the authors proposed a straightforward method using 22k ?1?2k ?1cofactors’equiv-alence checking which is not feasible for large number k .Instead,we check G -symmetry of f w.r.t.X 1and X 2by transpositional operator which can swap two inputs of f with ITE operator [11].The time complexity of transpo-sitional operator is O (p 2),where p is the size of OBDD representing f .Let f k be the function obtained from f by applying k transpositional operators to f .If f k =f ,then f is G -symmetric w.r.t.X 1and X 2.Let f 0=f and f i be the function after applying the i ’th transpositional operator.The time complexity of computing f k from f is O (P k ?1i =0p i 2),where p i is the size of OBDD representing f i . 4.2Check of Rotational Symmetry Consider the function f =x 1x 2+x 2x 3+x 3x 4+x 4x 5+x 5x 1which is invariant under rotating the variables of f with the ordered set [x 5,x 1,x 2,x 3,x 4].Fig.2(a)and (b)show the matrices of type 4k-distance signature of f with input orders [x 1,x 2,x 3,x 4,x 5]and [x 1,x 2,x 4,x 5,x 3],respectively.In the ?rst matrix,each left-to-right diagonal has the same value,while the second matrix doesn’t own this property.According to this important observation,given an initial type 4k-distance signature matrix,we have developed a prune-and-search algorithm to ?nd all reordered matrices with all diagonals having the same value.If there exists such a matrix,we can further check if f is r-symmetric w.r.t.this input order.The detail is however omitted because of space limitation. We have implemented the matrix reordering algorithm mentioned above and performed an experiment to check r-symmetry of f =x 1x 2+x 2x 3+···+x n ?1x n +x n x 1.The experimental result is shown in Table 1.The rows la-beled n ,|BDD |,and CPU Time show the input size,the OBDD size,and the run time in second,respectively.It shows our matrix reordering algorithm is very promising to check r-symmetry of Boolean functions. Table 1:Results of Detecting R-Symmetry n 58163264128256|BDD |1020521162445001012CPU Time 0.00 0.00 0.01 0.04 0.33 2.44 21.02 Algorithm AID (f,X ) Input:A Boolean function f w.r.t.the input set X ;Output:Ψis an ordered set of distinguished inputs;Begin MSS =Maximal -Symmetric -Set (f,X );Generate the initial Ψbased on MSS ;if Ψ=X return Ψ; Type-0signature ksig (f,1)is used to update Ψ;if Ψ=X return Ψ; Type-1signature ksig (f,f )is used to update Ψ;if Ψ=X return Ψ;for i =0to n do /*optional */ Type-2signature ksig (f,S n i )is used to update Ψ;if Ψ=X return Ψ;endfor Type-3signature ksig (f,x i )is used to update Ψ;if Ψ=X return Ψ; Generate the bounded set X b by MSS and Ψ; Reorder the OBDD of f with transpositional operator so the order of inputs in X b is before the inputs in X ?X b ;Let f =P m i =1(b i (X b )·u i (X ?X b ))by Type-4signature;for i =1to m do Ψ=Ψ+AID (u i ,X ?X b );if Ψ=X return Ψ;endfor return (Ψ);End Figure 3:The AID Algorithm. 5. ALGORITHM FOR INPUT DIFFERENTIATION (AID) 5.1AID Our AID algorithm starts by detecting all maximal sym-metric sets MSS of f (X )using the algorithm we proposed in [12].Then we classify the MSS in terms of set size.For each maximal symmetric set P i ∈MSS ,if P i is unique in size |P i |,then we throw the inputs of P i into the ini-tial ordered set Ψ;otherwise,we take an input x i of P i to represent P i and throw the remaining inputs into Ψ.Take f =x 1x 2x 3+x 4x 5+x 6x 7for example.It is clear P 1={x 1,x 2,x 3},P 2={x 4,x 5}and P 3={x 6,x 7}are maximal symmetric sets.The inputs of P 1are added into Ψdue to P 1is unique on set size 3.Since P 2and P 3have the same set size,x 4and x 6are used to represent P 1and P 2,respectively.Consequently,x 5and x 7are thrown into Ψ.After generating the initial Ψ,we apply type 0,1,2,and 3signatures in turn to add more inputs into Ψ.Once all inputs are distinguished,the algorithm returns Ψimmediately.If there still exist some inputs that can’t be distinguished,the bounded set X b is constructed based on Ψand MSS .One thing we need to address is that the bounded set is not al-ways equal to Ψ.Take the function f =x 1x 2x 3+x 4x 5+x 6x 7for example.After applying all k-distance signatures except for type 4,we get Ψ=[x 1,x 2,x 3,x 5,x 7]and two indis-tinguishable inputs x 4,x 6.So,x 5and x 7must be removed from Ψto generate the bounded set X b ={x 1,x 2,x 3}.Then w.r.t.X b ,we reorder the OBDD of f using transpositional operator [11]and decompose f as P m i =1(b i (X b )·u i (X ?X b ))based on type 4k-distance signature.Then AID procedure is recursively applied to subfunctions u i ’s to further distin-guish the inputs in X ?X b .By the above description,the AID algorithm is shown in Fig 3. 5.2Boolean Matching Algorithm Our Boolean matching method is mainly based on AID ,G -symmetry detection,and structural transformation of OBDD’s.To check if two functions f (X )and g (Y )are Algorithm Boolean-Matching (f (X ),g (Y ))Input:f (X )and g (Y ) Output:πis a feasible assignment;Begin if |f |=|g |return (?); Ψ1=AID (f,X ); Ψ2=AID (g,Y );if Ψ1=Ψ2return (?); G 1=G -Symmetry of f (X )utilizing Ψ1;G 2=G -Symmetry of g (Y )utilizing Ψ2; Let ψbe an assignment w.r.t.(Ψ1,G 1)and (Ψ2,G 2);Reorder f w.r.t.ψ;if f ≡g return (ψ);/*≡:structural equivalent */return (?);End Figure 4:The Boolean Matching Algorithm.equivalent under input permutation,our algorithm starts by applying AID algorithm to f and g to ?nd their distin-guishable inputs as many as possible.If all the inputs of f and g can be distinguished and have the same signature for each ordered input pair,then the OBDD representing f can be reordered to check if the transformed OBDD is struc-tural equivalent [11]to the OBDD representing g .For the situation that some inputs can’t be distinguished by AID ,we may apply our G -symmetry detection method to ?nd G -symmetry of f and g ,https://www.doczj.com/doc/6411210302.html,bining the result by AID and detected G -symmetry,an assignment ψmap-ping X to Y can be identi?https://www.doczj.com/doc/6411210302.html,stly,the same reordering and structural equivalence checking scheme can be applied to check whether f and g are matched or not.The above Boolean matching algorithm is shown in Fig.4. 6.EXPERIMENTAL RESULTS The proposed AID algorithm and G -symmetry detection method have been implemented in C language on SUN-Blade 1000station.128circuits from MCNC and ISCAS benchmarking sets have been tested.For each circuit,each output is tested individually.Overall,there are 17,28,63,71,and 78out of 128circuits with all inputs that can be distinguished by type 0,1,2,3k-distance signatures,and AID ,respectively.The ratios are 13%,22%,49%,55%,and 61%,respectively. Table 2shows the partial experimental results.The columns labeled #in ,#out ,and |BDD |are the numbers of inputs,the number of outputs,and the size of OBDD,respectively.The columns with labels 0,1,2,3and AID show the average distinct factors of type 0,1,2,3k-distance signatures,and our AID algorithm,respectively.The CPU Time column shows the running time in second.The rows with labels average and ratio show the average distinct factor and runtime normalization,respectively.The average distinct factors of type 0,1,2,3,and AID are 0.60,0.67,0.78,0.76,and 0.81,respectively.It shows that AID is the most e?ective signature for being used in Boolean matching.Table 2also shows the result of testing our G -symmetry de-tection method.The column #O show the number of out-puts with indistinguishable inputs after running AID .The +GSD column shows the result of G -symmetry detection.The columns labeled #HS and #GS show the number of outputs with h-symmetry and with g-symmetry ,respec-tively.The result of r-symmetry is skipped since no r-symmetry exists for all circuits.The experimental result shows that the G -symmetry of all tested circuits except for C1355can be detected by our heuristic with little run time overhead (7%).In summary,our heuristic is very e?ective and e?cient to check G -symmetry of Boolean functions. Table2:Benchmarking Results for K-Distance Signatures and AID circuit#in#out|BDD| K-Distance Signature(k=1)+GSD CPU Time(sec.) 0123AID#O#HS#GS0123AID+GSD BM alu41486370.180.420.900.900.901010.000.000.000.000.000.010.02 apex354508540.730.790.920.990.991100.080.12 2.130.590.580.63 1.20 apex51178811210.880.930.930.940.958800.100.120.200.110.130.180.37 apex6135995690.800.880.890.980.995050.010.020.070.040.050.050.10 clma41511513040.890.930.980.980.993030.050.070.520.290.210.270.50 cm150a211330.050.050.140.140.141010.000.000.010.010.010.010.02 cm151a122170.080.080.250.250.252020.000.000.000.010.000.000.01 cordic232630.830.830.830.830.832200.000.000.010.000.000.010.02 dalu75168040.350.390.570.630.72130130.180.21 2.64 1.10 1.15 1.47 3.01 des25624529220.720.810.970.95 1.00---0.200.230.620.570.60- 1.17 dsip45242124600.730.820.91 1.00 1.00---0.110.110.600.180.18-0.35 ecc12713022760.910.920.990.990.992020.190.270.360.300.170.180.34 frg21431399750.790.800.840.840.87330330.030.040.200.210.200.300.58 gcd788512000.920.940.970.990.99111100.070.110.610.370.160.190.41 i10257224303750.940.960.980.980.981688 4.237.0916.707.2217.5617.7138.59 mm9a393611130.420.540.660.660.66160160.040.090.140.120.130.160.30 pair173********.700.920.970.970.979810.130.310.780.400.330.410.89 rot135********.860.910.970.980.9811290.130.28 1.870.600.390.58 1.23 s1423917918230.580.730.910.890.94272610.100.17 1.630.800.620.65 1.32 s38584.114641730145390.830.930.970.970.9820817137 2.07 2.6824.81 5.5724.7626.4654.10 s4863153120564830.560.580.640.630.8547146 1.50 3.42 3.93 4.39 2.96 4.228.81 s6669322294218030.720.860.870.870.87472450.37 1.01 3.18 2.85 2.79 4.238.15 seq413512020.940.970.990.99 1.00---0.120.100.170.110.08-0.15 t481161210.000.000.000.000.001010.000.000.000.010.000.010.03 term13410810.610.640.700.650.708530.010.010.030.020.020.030.06 x3135995620.800.880.890.980.995050.020.030.070.040.040.050.11 C1355*4132258740.020.050.070.050.0732000.55 1.4543.0232.5247.2347.50130.24 C1908332564610.180.300.970.40 1.00---0.170.527.28 5.57 2.71- 5.40 C267023314019370.800.810.870.860.88320320.140.3412.38 3.5827.2633.5070.06 C35405022241290.640.860.930.950.98111 2.22 4.1223.42 5.36 5.76 6.3513.10 C43236712260.060.060.060.060.067070.050.11 1.050.980.13 1.00 2.10 C531517812320640.430.480.950.760.968080.170.43 3.537.57 3.48 3.717.96 C755220710822990.640.680.990.790.994400.510.7118.3812.8818.0118.5038.28 C880602646260.990.990.990.990.993300.170.450.740.480.210.240.50 average0.600.670.780.760.810.410.72 5.03 2.79 4.72 5.0611.42 ratio 1.000.450.500.080.15 1.070.59 1.00 1.07 2.42 Table3:Boolean Matching with Cell Libraries circuit#in#out|BDD| CPU Time(ms.) total avg. 33-498772200.23 43-512396900800.20 44-31662515881500.24 44-616350385568000.23 We also conduct an experiment to test our Boolean match-ing algorithm.For each benchmarking circuit,we match it with a new circuit generated by randomly permuting its in-puts variables.In Table2,the column with label BM shows the running time for Boolean matching.The experimental result demonstrates our algorithm is very e?cient to solve Boolean matching problem.Moreover,we test several large cell libraries with the same experimental?ow.The result is summarized in Table3.In this table,the columns#in and#out show the input number of the largest cell and the number of cells in the library,respectively.The columns total and avg.show the matching time of all cells and the average matching time for each cell in millisecond(ms.).The experimental result shows the average matching time is less than0.25ms.It is very promising to encourage us to apply our Boolean matching technique for technology mapping. 7.CONCLUSION In this paper,we had de?ned the k-distance signature which is a general form of many existing signatures.Based on k-distance signature,an AID algorithm which can dis-tinguish almost all inputs of Boolean functions without G-symmetry was also proposed.Moreover,we addressed the issue of detecting G-symmetry and shown a heuristic to solve this problem.The experimental results on a set of bench-marks show that our AID algorithm and G-symmetry de-tection method are not only e?ective but also e?cient for being applied in Boolean matching for logic veri?cation and technology mapping. 8.REFERENCES [1] F.Mailhot and G.De Micheli,“Technology mapping using Boolean matching and don’t care sets,”in Proc.European Design Automation Conf.,pp.212-216,1990. [2]U.Hinsberger and R.Kolla,“Boolean matching for large libraries,”in Proc.Design Automation Conf.,pp.206-211, 1998. [3] D.I.Cheng and M.Marek Sadowska,“Verifying equivalence of functions with unknown input correspondence,”in Proc. European Design Automation Conf.,pp.81-85,Feb.1993. [4]J.Mohnke and S.Malik,“Permutation and phase independent Boolean comparison,”INTEGRATION-the VLSI Journal, Vol.16,no.2,pp.109-129,1993. [5]J.Ciric and C.Sechen,“E?cient canonical form for Boolean mathcing of complex functions in large library,”IEEE Trans. Computer-Aided Design,Vol.22,No.5,pp.535-544,May 2003. [6] A.Abdollahi and M.Pedram,“A new canonical form for fast Boolean matching in logic synthesis and veri?cation,”in Proc. Design Automation Conf.,pp.379-384,June2005. [7]J.Schlichtmann, F.Brglez,and P.Schneider,“E?cient Boolean matching based on unique variable ordering,”in Proc. Int.Workshop on Logic Synthesis,May1993. [8]J.Mohnke,P.Molitor,and S.Malik,“Limits of using signatures for permutation independent Boolean comparison,” in Proc.ASP Design Automation Conf.,pp.459-464,1995. [9]I.Pomeranz and S.M.Reddy,“On determining symmetries in inputs of logic circuits,”IEEE https://www.doczj.com/doc/6411210302.html,puter-Aided Design,Vol.13,No.11,pp.1428-1434,Nov.1994. [10]V.N.Kravets and K.A.Sakallah,“Generalized symmetries in Boolean functions,”in Proc.Int.Conf.on Computer-Aided Design,pp.526-532,Nov.2000. [11]K.H.Wang,T.Hwang,and C.Chen,“Restructuring Binary Decision Diagrams Based on Functional Equivalence,”in Proc. European Design Automation Conf.,pp.261-265,1993. [12]K.H.Wang and J.H.Chen,“K-disjointness paradiagm with application to symmetry detection of incompletely speci?ed functions,”in Proc.ASP Design Automation Conf.,pp. 994-997,Jan.2005. 宁波工程学院 《文献检索与科技论文写作》课程 检索题 检索题目大空隙沥青混合料 中文：_____大空隙沥青混合料_______________________ 英文：__asphalt mix for open-graded friction course_____________ 姓名：_______章茂廷___ 学号：___________ 学院：____建工____ 专业：__土木工程_____________ 2014年12 月25 日 一、课题分析： 1) 学科领域：_土木工程_____________ 中图分类号：______________TU5 2) 研究内容（包括要解决的关键性问题）： 名词解释 性能，用途 3) 中英文关键词（注意同义词、上位词及下位词等）：（A1、A2、A3…，B1、B2….，C1…..）asphalt mix for open-graded friction course 大空隙沥青混合料 4) 中英文逻辑检索表达式：如：（A1 OR A2 OR A3）AND（B1 OR B2）AND C1 (注：A1、A2、A3同义关键词，B1、B2同义关键词，C1 ) 混凝土，高性能，大空隙，沥青 二、选择数据库并检索；记录、整理检索结果 1）数据库选择： 2 a)、知网全文数据库，检索结果 10篇 检索过程：初级检索：检索词篇名（检索字段：篇名/关键词/摘要），检得11 篇；二次检索：检索词关键词（检索字段：），检得 7 篇；二次检索：检索词摘要（），检得 7 篇。 b)、万方全文数据库，检索结果 143 篇 检索过程：初级检索：检索词学术论文 （文献类型：期刊/学位/会议/ ），检得 140篇；二次检索：检索词篇名（篇名/ ），检得 11 篇；二次检索：检索词（篇名/ ），检得篇。 3）文献分析： a)、在所检索文献中，下列文献为综述性文献： （1）、题名：大空隙沥青混合料的耐久性研究 作者：黄学文 刊物名：中外公路 摘要：通过设计3种不同级配的大空隙沥青混合料,对其进行不同程度的老化处理,然后再进行肯塔堡飞散试验、浸水肯塔堡飞散试验和冻融循环劈裂试验,采用飞散损失、浸水飞散损失和冻融劈裂强度比等指标表征大空隙沥青混合料的耐久性,研究级配、浸水和老化对大空隙沥青混合料的耐久性的影响。结果表明:级配、水和老化都会对大空隙沥青混合料的耐久性产生影响,增大9.5mm的通过率可提高大空隙沥青混合料的耐久性,老化和浸水却会降低其耐久性。更多还原 出自数据库：知网 b)、在所检文献中，下列文献为相关度较高的文献： （1）、题名：大空隙沥青混合料配合比设计研究 作者：刘红瑛 刊物名：石油沥青 一、研究生必备四本 俗话说好记性不如烂笔头，所以一定要首先养成做笔记的好习惯！作为研究生下面这几个本子是必不可少的。 1，实验记录本（包括试验准备本），这当然首当其冲必不可少，我就不多说了； 2，Idea记录本，每次看文献对自己有用的东西先记下，由此产生的idea更不能放过，这可是做研究的本钱，好记性不如烂笔头，以后翻翻会更有想法的； 3，专业概念以及理论进展记录本，每个人不可能对自己领域的概念都了如指掌，初入门者更是如此，这时候小小一个本子的作用就大了； 4，讲座记录本，这本本子可能有些零杂，记录听到的内容，更要记录瞬间的灵感，以及不懂的地方，不可小视！ 这四本是你必不可少的，不过作为我们这些非英语专业的研究生来说，还有一个应该具备的本子就是英语好句记录本。 二、论文写作要点 1、选题要小，开掘要深；不要题目很大，内容却很单薄。 2、写作前要读好书、翻阅大量资料、注意学术积累，在这个过程中，还要注重利用网络，特别是一些专业数据库 3、“选题新、方法新、资料新”的三新原则（老板教导的） 4、“新题新做”和“小题大做 总之，一点之见即成文。 三、如何撰写实验研究论文（唐朝枢） 论文发表意识：基础研究成果的表达方式；是否急于发表（创新与严谨的关系）；发表的论文与学位论文的区别（反映科学事实而不是反映作者水平） 论文格式：原著 original research paper, full length paper、review综述论文，快报、简报、摘要。不同于教科书、讲义，更不同于工作总结。 撰写前的准备工作：复习和准备好相关文献;再次审定实验目的(学术思想,Idea);实验资料完整并再次审核 1.Introduction:引言 问题的提出；研究的现状及背景；以前工作基础；本工作的目的；思路（可提假说）；对象；方法；结果。在…模型上，观察…指标，以探讨…（目的） 摘要 伴随着经济的不断发展,必然带动交通业和旅游业务的不断扩大, 特别是航空售票和订票的信息管理日异复杂, 传统的售票方式已经难以满足快节奏, 高效率的现代生活需求,这就要求航空公司要有一套好的售票数据库系统。 一个正常营运的航空公司需要管理所拥有的飞机、航线的设置、客户的信息等，但更重要的还要提供票务管理。面对各种不同种类的信息，需要合理的数据库结构来保存数据信息以及有效的程序结构支持各种数据操作的执行。对数据的添加、修改、删除及查询等方面的操作应简单易行，并且能够具有较好的稳定性。航空售票管理系统主要采用Delphi 7.0做为开发工具，进行开发与设计的。本系统的使用界面具有十分人性化的特征，具有方便的查询功能，对售票、网上订票等方面的操作应简单易行，并且能够具有较好的稳定性。 关键词: 航空；售票；网上订票；管理系统；数据库；SQL语言。 目录 1.开发一个航空售票管理系统的背景和意义 (1) 1.1.传统售票方式的回顾和特点分析 (1) 1.2.航空售票管理系统的应用现状和前景展望 (1) 2.用计算机开发一个航空售票管理系统的可行性分析 (1) 2.1.技术可行性 (1) 2.2.经济可行性 (2) 2.3.法律可行性 (2) 3.开发环境的选择 (3) 3.1.Delphi 7.0简介 (3) 3.2.开发工具的选择 (3) 4.航空售票管理系统的需求分析 (3) 4.1.系统分析 (4) 4.2.系统功能模块设计 (4) 4.3.功能子模块分析 (5) 4.3.1.网上订票模块 (5) 4.3.2.用户查询模块 (5) 4.3.3.用户订票模 (5) 4.4.后台管理系统 (6) 4.4.1.后台管理系统子模块 (6) 4.5. 民航售票管理系统的顶级数据流程图 (8) 4.6. 民航售票管理系统一级数据流图 (9) 4.7. 数据字典定义 (10) 4.7.1.数据项定义 (10) 4.8.E/R模型 (13) 5.详细设计 (14) 5.1.系统的总体流程图 (14) 5.2.系统各模块的实现 (15) 5.2.1.系统登录窗口 (15) 5.2.2.主界面窗口 (16) 5.2.3.信息操作模块 (17) 5.2.4.送票员模块 (22) 5.2.5.员工管理模块 (23) 5.2.6.系统模块 (24) 5.2.7.售票员模块 (25) 5.2.8.前台订票模块 (26) 文摘要求 对于科技期刊的文章，论文的 abstract 主要由三部分组成，即：研究的问题、过程和方法、结果。 文摘只有写得正确，写的好，才能起到帮助读者了解原文的作用。因此必须对文献进行认真的主题分析， 找出文献的主题概念， 正确地组织好这些主题内容， 简明准确完整地写出文摘来。 文摘长度一般不超过 150 words 。少数情况下允许例外，视原始文献而定。在不遗漏主题概念的前提下，文摘应尽量简洁。 （一）.缩短文摘方法: 1.取消不必要的字句：如 ”t is reported here ”、 “new ”、 “ mainly ” 也尽量不要。 2. 对物理单位及一些通用词可以适当进行简化; 3. 取消或减少背景信息（ Background Information ）; 4. 不说无用的话，如“本文所谈的有关研究工作是对过去老工艺的一个极大的改进” ， “本工作首次实现了 …” “经检索尚未发现与本文类似的文献”等词句切不可进入文摘; 5. 作者在文献中谈及的未来计划不纳入文摘； 6. 文摘第一句应避免与题目（Title ）重复。 7. 尽量简化一些措辞和重复的单元，如： （二）.文体风格 1. 文摘叙述要完整，清楚，简明； 2. 尽量用短句子并避免句形单调； 3. 用过去时态叙述作者工作，用现在时态叙述作者结论； 如 “The structure of dislocation cores in GaP was investigated by weak-beam electron microscopy. The dislocations are dissociated into two Shokley partials with separations of 80 edge and screw cases respectively. The results show that... __________________________________ ” 可直接用名词或名词短语作定语的情况下，要少用 of 句型。 例如： 用 Thick ness of plastic sheets was measured. 不用 Measurement of thickness of plastic sheet was made. 注意冠词用法，不要误用，滥用或随便省略冠词。 避免使用一长串形容词或名词来修饰名词，可以将这些词分成几个前置短语，用连字符连接名词 组，作为单位形容词（一个形容词） 。 如应用 The chlorine-containing propylene-based polymer of high meld index. 代替 The chlorine containing high melt index propylene based polymer. 尽量用主动语态代替被动语态； 尽量用简短、词义清楚并为人熟知的词; 10?慎用行话和俗语; " Exte nsive in vestigati ons show that 'The author discusses ” This paper concerned with …”；一些不必要的修饰词，如“ in detail ”、“ briefly ±10 and 40 ±10 A in the pure 能用名词做定语不要用动名词做定 语， 例如：用 measurement accuracy 用 experimental results 能用形容词做定语就不要用名词做定语。 不用 measuri ng accuracy 不用 experime nt results 例女口 用 measurement accuracy 不用 accuracy of measureme nt 用 camera curtain shutter 不用 curta in shutter of camera 用 equipment structure 不用 structure of equipme nt 5. 可用动词的情况尽量避免用动词的名词形式; 6 . 8. 9. titlesec&titletoc中文文档 张海军编译 makeday1984@https://www.doczj.com/doc/6411210302.html, 2009年10月 目录 1简介,1 2titlesec基本功能,2 2.1.格式,2.—2.2.间隔, 3.—2.3.工具,3. 3titlesec用法进阶,3 3.1.标题格式,3.—3.2.标题间距, 4.—3.3.与间隔相关的工具, 5.—3.4.标题 填充,5.—3.5.页面类型,6.—3.6.断行,6. 4titletoc部分,6 4.1.titletoc快速上手,6. 1简介 The titlesec and titletoc宏包是用来改变L A T E X中默认标题和目录样式的，可以提供当前L A T E X中没有的功能。Piet van Oostrum写的fancyhdr宏包、Rowland McDonnell的sectsty宏包以及Peter Wilson的tocloft宏包用法更容易些；如果希望用法简单的朋友，可以考虑使用它们。 要想正确使用titlesec宏包，首先要明白L A T E X中标题的构成，一个完整的标题是由标签+间隔+标题内容构成的。比如： 1.这是一个标题，此标题中 1.就是这个标题的标签，这是一个标签是此标题的内容，它们之间的间距就是间隔了。 1 2titlesec基本功能 改变标题样式最容易的方法就是用几向个命令和一系列选项。如果你感觉用这种方法已经能满足你的需求，就不要读除本节之外的其它章节了1。 2.1格式 格式里用三组选项来控制字体的簇、大小以及对齐方法。没有必要设置每一个选项，因为有些选项已经有默认值了。 rm s f t t md b f up i t s l s c 用来控制字体的族和形状2，默认是bf,详情见表1。 项目意义备注（相当于） rm roman字体\textrm{...} sf sans serif字体\textsf{...} tt typewriter字体\texttt{...} md mdseries(中等粗体)\textmd{...} bf bfseries(粗体)\textbf{...} up直立字体\textup{...} it italic字体\textit{...} sl slanted字体\textsl{...} sc小号大写字母\textsc{...} 表1:字体族、形状选项 bf和md属于控制字体形状，其余均是切换字体族的。 b i g medium s m a l l t i n y（大、中、小、很小） 用来标题字体的大小，默认是big。 1这句话是宏包作者说的，不过我感觉大多情况下，是不能满足需要的，特别是中文排版，英文 可能会好些！ 2L A T E X中的字体有5种属性：编码、族、形状、系列和尺寸。 2 Writing: Abstract WHAT IS AN ABSTRACT 1. The Definition of an Abstract 1 ) the objectives and scope of investigation; 2) the methods used; 3) the most important results; 4) conclusion or recommendation. 2. Features of Abstracts Brevity Accuracy Specificity Objectivity Informativeness Independency CLASSIFICATION OF ABSTRACTS 1.Indicative Abstracts https://www.doczj.com/doc/6411210302.html,rmative Abstracts https://www.doczj.com/doc/6411210302.html,rmative-indicative Abstracts 4.Other Types of Abstracts 1) Critical Abstracts 2) Mini-abstracts FUNCTIONS OF ABSTRACTS A Screening Device of Documents: An abstract gives readers the idea of what the article is about. A Self-contained Text: We’ll know the information it contains, without seeing the article . A Helpful Preview: It "frames" the article and prepares the reader for the main points to come. To Facilitate Indexing: It will improve the chances of having it read by the right people. STYLISTIC FEATURES OF ABSTRACTS 1. The Length of Abstracts 1) In general, there is a 100-300 word limit to the number of words in an abstract. 2) Do not confuse an abstract with a review. There should be no comment or evaluation. 3) Give information only once. 4) Do not repeat the information given in the title. 5) Do not include any facts or ideas that are not in the text. 6) For informative abstracts, include enough data to support the conclusions. 7) If reference to procedure is essential, try to restrict it to identification of method or process. 8) State results, conclusions, or findings in clear concise fashion. 9) Organize the information in the way that is most useful to the reader. (a thesis-first abstract) 2. Verbs and Tenses Used in Abstracts 1) Active verbs: use active verbs rather than passive verbs. 2) Present tense: background information, existing facts, what is in the paper and conclusion. 3) Past tense /present perfect tense: completed research, methodology or major activities results. 3. Words Used in Abstracts 1) Avoid use of highly specialized words or abbreviations. Define unfamiliar words. 2) Synthesize or rephrase the information into clear, concise statements. 3) Avoid using jargon. 4. Sentence Structures of Abstracts 1) Use third person sentences. 2) Use short sentences, but vary sentence structure. 3) Use complete sentences. 4) The first sentence should present the subject and scope of the report. The thesis or the writer's focus should be presented in the second sentence. The balance of the article is a summary of the important points of each section, including methods, procedures, results and conclusions. 5) Good abstracts are sure to include a variety of pat phrases: a. Background Information (Research has shown... It has been proposed... Another proposed property... The search is on for... One of the promising new...) b. Statement of the Problem (The objective of the research is to prove / verify... The experiment was designed to determine...) e. Statement of Procedure (To investigate this .... A group of 10 specimens / subjects ... Measurements 火车票网上订票系统系统 摘要 本文针对火车站的订票实际情况，按照软件工程的结构化设计思想，经过项目的可行性研究和需求分析、总体设计、详细设计，以及编码实现和调试等步骤设计开发了火车站网上订票系统。并运用数据流图和数据字典、E-R图和数据库逻辑结构、层次图、系统流程图、以及程序流程图，对该系统的数据需求、数据库、系统软件结构、系统流程、以及处理过程等进行了分析和设计。 工具软件利用JAVA 开发工具和SQL Server 2000数据库来开发这个火车站网上订票系统。该系统要解决的是火车站网上订票工作所要解决的问题，可以满足火车站网上订票的基本要求，包括查询、订票、退票等三个方面的功能。该系统能运用到火车站订票的工作中，根据用户的需求，设置其权限，并快捷方便的为用户提供服务。 关键词：信息管理，火车售票，JAVA，SQL Server2000 目录 第一章引言 (1) 第二章需求分析 (2) 第三章总体设计 (3) 第四章详细设计与实现 (6) 第五章系统测试 (12) 结论 (13) 参考文献 (14) 第一章引言 信息化的时代，我们除了在跟上时代的节拍外，更多的时候是一种理念的提升与升华。存在既有存在的道理，就像为什么之前我们有了电视，但是现在还需要有电脑一样。现在绝大多数公司都会借助电脑去工作，为什么，因为借助它让我们提高我们的办事效率，让我们的管理模式变得更简易更方便。CRM的产生也是同样的道理，我们在自己打好客户关系外，总是需要借助一个工具来帮我们管理的，如果是找人管理的话，那么多的数据不见得都能够记下来，而且也存在一些矛盾让你后期不便于管理，但是借助软件工具我们就可以省事省时省力了。随着信息技术的飞速发展和客户驱动市场的形成，制造业面临的竞争越来越激烈，许多企业通过ERP 、SCM等管理信息化系统强化了财务、生产、物流、产品管理后，发现自己的营销与服务能力的不足，特别是那些快速发展的企业，在全国各地建立了营销与服务网络，人员越来越庞大，营销费用增长迅速，但业绩提升缓慢，而且客户的满意度下降，竞争对手比自己跑得越来越快，各层次沟通不畅信息衰减严重。打造一个富有战斗力的营销服务体系，成本突破管理与发展瓶颈的明智选择，CRM强调建立以客户为中心的现代企业，以客户价值来判定市场需求，对于正在转变战略从“产品中心”向“客户中心”过渡的企业无疑是一拍即合，正是基于此，各大公司才决定制作CRM系统。 影院网上订票系统网站需求说明书 计算机科学与技术2班 2012年9月29日 1.项目背景 电影，又称映画，是由活动照相术和幻灯放映术结合发展起来的一种现代艺术，有着复杂繁多的科系。 目前一般大众可以经由网际网络进行许多商业活动，例如购书、订花、购物、游戏等，其中也包含订票（例如机票、火车票、音乐剧入场券等）。其中，在电影院方面也有业者推动相关服务，如：华纳威秀、环球影城、国宾戏院等，已开始使用网际网络提供观众放映影片相关资讯，如场次时间表、影片预告及简介、电影院资讯等。 从网际网络到电子商务的蓬勃发展来看，类似于淘宝网上商城那种从开网店，在网上摆放商品，客人挑选物品再下订单，店主发货等一系列流程已经很成熟了。相对于淘宝网上商城而言，目前电影院的网络服务似乎仍有不足之处。对于使用者而言，影片的相关讯息介绍、预告片都是上百度、谷歌等网上引擎搜索得知，某个城市的特定影城往往不能提供全方位的详细信息，特别是不能满足观众对影片场次时间的查询。 社会生活节奏的加快，许多社会人士忙于工作等繁琐事务，每次想去影城观看电影都要经过现场查询最近热映的影片，每部影片的放映场次等信息，然后才能开始订票，而往往排队等候很长时间以后才发现自己要观看的那场影片的票已经售完，或是没有合适的观看座位。 电影业的蓬勃发展，必然引发的一个问题是群众对电影票需求的增大。特别是一些关注度很高的大片上映的时候，很多观众都反应电影票实在是很难购买，有些人就只能选择观看午夜场。在一些大城市规模很好的影城售票厅内，甚至出现要一大早起来排队去抢票的现象。还有些观众反应等那么长的队伍能买到票，但是都没有自由选择座位的权利。 这样的情况已经普遍的存在了，很多人纷纷提出影城应该提供最近热映的的影片讯息、快要上映的影片相关预告、每场电影的场次安排，以及每场次电影票的网上预订模式。 对基于WEB的电影院订票系统的研究，对于观众而言可以增强他们对各部影片的了解，对最新的影片上映动态的掌握，让他们对影片更加期待，尤其能在网上订票模式下使观众享受到不需要等待排队买票与自由选择座位的权利。通过网络轻松订票，从而减少许多因现场购票失败的客户，促使我国电影事业更好更快的发展。 2.项目范围 系统的开发和维护，提供配套的数据库。 一：对语言学本身性质的阐述分析 并且从不同角度来分析语言学 1《认知语言学的最新应用及展望》述介 【作者】卢植； 【机构】暨南大学外国语学院； 【摘要】Gitte Kristiansen,Michel Achard,Ren啨Dirven&Francisco J.Ruiz de MendozaIb偄 nez(eds.).2006.Cognitive Linguistics:Current Applications and Future Per-spectives.Berlin:Mouton de Gruyter.ix+499pp.1.前言《认知语言学的最新应用及展望》是德国Moutonde Gruyter出版社“认知语言学的应用”系列丛书的第一卷。编者在导言中指出,在过去二三十年间,认知语言学逐渐发展成为一个成熟和创新的学科,并不断演化和拓展。一更多还原 【关键词】认知语言学；最新应用；认知基础；概念隐喻理论；语言学模型；展望；认知科学；计算语言学； 2以认知为基础的英汉对比研究——关于对比认知语言学的一些构想 【作者】文旭； 【机构】西南大学； 【摘要】英汉对比研究是我国语言学界研究的一个主要领域,其研究方法和视角都相当丰富。认知语言学是语言学中的一种新范式。将两者结合起来,建立一门新的学科,即对比认知语言学,必将对认知语言学和对比语言学大有裨益。本文探讨了对比认知语言学的理论基础、对比的原则和方法、对比的范围和内容。可以说,语言系统的任何方面,都可以从认知的角度进行对比研究。更多还原 【Abstract】English-Chinese contrastive study is a major field done in Chinese linguistics,which has a number of research approaches and perspectives. Cognitive linguistics is a new linguistic paradigm. Therefore, it is significant to integrate them into a new discipline called cognitive contrastive linguistics. This paper has explored its theoretical foundations, principles, approaches, scope and content. We can say that any aspect of language system can be studied contrastively from the perspective of cog... 更多 还原 3认知社会语言学 实验十三数据库管理系统综合应用 -------民航订票管理系统 一、实验目的： 通过完成从用户需求分析、数据库设计到上机编程、调试和应用等全过程，进一步了解和掌握所讲解的内容。 二、实验简述： 民航订票系统主要分为机场、航空公司和客户三方的服务。航空公司提供航线和飞机的资料，机场则对本机场起飞和降落的航班和机票进行管理，而客户能得到的服务应该有航班线路和剩余票数的查询，以及网上订票等功能。客户又可以分为两类，一类是普通客户，对于普通客户只有普通的查询功能和订票功能，没有相应的机票优惠，另一种是经常旅客，需要办理注册手续，但增加了里程积分功能和积分优惠政策。机场还要紧急应对措施，在航班出现延误时，要发送相应的信息。 三、实验要求： 完成该系统的数据库设计； 用SQL实现数据库的设计，并在SQL Server上调试通过。 四、参考答案： 1、需求分析 （1）航空公司 航空公司的操作流程如图C.1所示。 图C.1 航空公司操作分类表 （2）客户 客户的操作流程如图C.2所示。 图C.2 客户操作分类表 （3）机场 机场的任务是根据航空公司提供的航线和飞机，安排航班，以及航班的机票。如果出现晚点等情况，要记录并发送信息，对特殊客户记录其消费信息，并相应提供优惠。 （4）客户订票 客户订票涉及到多个因素：由客户提出订票申请；由机场管理航班机票；对于特殊客户，除给予票价优惠以外，还要累计里程；订票后需判断是否超员。这些因素涉及到客户资料、航班资料以及由航空公司提供的航线（里程）和飞机（座位数）资料中所提供的相关数据。 客户订票的操作流程如图C.3所示。 2、概念模型设计 数据库需要表述的信息有以下几种： （1）航空公司信息 （2）客户信息 （3）飞机信息 （4）航线信息 （5）航班信息 （6）订票信息 （7）特殊客户积分 How to Write an Abstract for a Research Paper WANG Yan School of International Studies UIBE Issues to address: 1What is an abstract? 2Functions of an abstract 3Structure of an abstract 4Principles of abstract writing 1. What is an abstract? ?An abstract is a condensed version of a longer piece of writing that highlights the major points covered, concisely describes the purpose and scope of the writing, and reviews the writing's contents in abbreviated form. ?It is a concise and clear summary of a complete research paper. ?It tells the reader What you set out to do, and Why you did it,How you did it, What you found (recommendations). 2. Functions of an abstract ?An abstract is used to communicate specific information from the article.?It is aimed at introducing the subject to readers, who may then read the article to find out the author's results, conclusions, or recommendations. 2. Functions of an abstract ?The practice of using key words in an abstract is vital because of today's electronic information retrieval systems. ?Titles and abstracts are filed electronically, and key words are put in electronic storage. ?When people search for information, they enter key words related to the subject, and the computer prints out the titles of all the articles containing those key words. ?An abstract must contain key words about what is essential in an article so that someone else can retrieve information from it. 3. Structure of an abstract ?The components of an abstract ①Background Information ②Subject Matter/Problem Statement ③Purpose ④Method (and Data) ⑤Results / Findings ⑥Conclusion / Implications ctex宏包说明 https://www.doczj.com/doc/6411210302.html,? 版本号：v1.02c修改日期：2011/03/11 摘要 ctex宏包提供了一个统一的中文L A T E X文档框架，底层支持CCT、CJK和xeCJK 三种中文L A T E X系统。ctex宏包提供了编写中文L A T E X文档常用的一些宏定义和命令。 ctex宏包需要CCT系统或者CJK宏包或者xeCJK宏包的支持。主要文件包括ctexart.cls、ctexrep.cls、ctexbook.cls和ctex.sty、ctexcap.sty。 ctex宏包由https://www.doczj.com/doc/6411210302.html,制作并负责维护。 目录 1简介2 2使用帮助3 2.1使用CJK或xeCJK (3) 2.2使用CCT (3) 2.3选项 (4) 2.3.1只能用于文档类的选项 (4) 2.3.2只能用于文档类和ctexcap.sty的选项 (4) 2.3.3中文编码选项 (4) 2.3.4中文字库选项 (5) 2.3.5CCT引擎选项 (5) 2.3.6排版风格选项 (5) 2.3.7宏包兼容选项 (6) 2.3.8缺省选项 (6) 2.4基本命令 (6) 2.4.1字体设置 (6) 2.4.2字号、字距、字宽和缩进 (7) ?https://www.doczj.com/doc/6411210302.html, 1 1简介2 2.4.3中文数字转换 (7) 2.5高级设置 (8) 2.5.1章节标题设置 (9) 2.5.2部分修改标题格式 (12) 2.5.3附录标题设置 (12) 2.5.4其他标题设置 (13) 2.5.5其他设置 (13) 2.6配置文件 (14) 3版本更新15 4开发人员17 1简介 这个宏包的部分原始代码来自于由王磊编写cjkbook.cls文档类，还有一小部分原始代码来自于吴凌云编写的GB.cap文件。原来的这些工作都是零零碎碎编写的，没有认真、系统的设计，也没有用户文档，非常不利于维护和改进。2003年，吴凌云用doc和docstrip工具重新编写了整个文档，并增加了许多新的功能。2007年，oseen和王越在ctex宏包基础上增加了对UTF-8编码的支持，开发出了ctexutf8宏包。2009年5月，我们在Google Code建立了ctex-kit项目1，对ctex宏包及相关宏包和脚本进行了整合，并加入了对XeT E X的支持。该项目由https://www.doczj.com/doc/6411210302.html,社区的开发者共同维护，新版本号为v0.9。在开发新版本时，考虑到合作开发和调试的方便，我们不再使用doc和docstrip工具，改为直接编写宏包文件。 最初Knuth设计开发T E X的时候没有考虑到支持多国语言，特别是多字节的中日韩语言。这使得T E X以至后来的L A T E X对中文的支持一直不是很好。即使在CJK解决了中文字符处理的问题以后，中文用户使用L A T E X仍然要面对许多困难。最常见的就是中文化的标题。由于中文习惯和西方语言的不同，使得很难直接使用原有的标题结构来表示中文标题。因此需要对标准L A T E X宏包做较大的修改。此外，还有诸如中文字号的对应关系等等。ctex宏包正是尝试着解决这些问题。中间很多地方用到了在https://www.doczj.com/doc/6411210302.html,论坛上的讨论结果，在此对参与讨论的朋友们表示感谢。 ctex宏包由五个主要文件构成：ctexart.cls、ctexrep.cls、ctexbook.cls和ctex.sty、ctexcap.sty。ctex.sty主要是提供整合的中文环境，可以配合大多数文档类使用。而ctexcap.sty则是在ctex.sty的基础上对L A T E X的三个标准文档类的格式进行修改以符合中文习惯，该宏包只能配合这三个标准文档类使用。ctexart.cls、ctexrep.cls、ctexbook.cls则是ctex.sty、ctexcap.sty分别和三个标准文档类结合产生的新文档类，除了包含ctex.sty、ctexcap.sty的所有功能，还加入了一些修改文档类缺省设置的内容（如使用五号字体为缺省字体）。 1https://www.doczj.com/doc/6411210302.html,/p/ctex-kit/ Questions on the Abstract ?What is the subject matter/area the research paper is dealing with? ?What background information is provided by the author(s)? ?What is the purpose of the present study? ?How is the research to be done? ?What are some of the important findings? ?What are some of the implications of the study? Elements of structure in an Abstract ?We can see that by asking a number of questions we can discover the structure of the Abstract. ?We can refer to each section as an "element of stmcture"? Tlie six elements of structure can then be refeiTed to as ?Topic Specification (TS), ?Background Information (BI), ?Purpose Statement (PS), ?Methodology and Data (MD), ?Results/Findings (RF), and ?Implications/Conclusions (IC). ?An important issue here is the time for the writing of the Abstract??Usually it is written after the study/research is completed but this is not always the case as, for example, people send abstracts of unfinished C#课程设计报告——网上机票预订系统 专业：软件工程 班级： 学号： 姓名： 小组成员：无 、课程设计题目 网上机票预订系统 二、需求分析 2.1系统开发背景 当今世界，以信息技术为主要标志的科技进步日新月异，高科技成果向现实生产力的转化越来越快。纵观全球经济发展，信息技术和信息产业已经成为经济增长的主要推动力之一，正在改变着传统的生产和经营方式以至生活方式，发达国家经过产业结构的升级和经济结构的转型已进入信息经济阶段。信息资源已经成为国民经济和社会发展的战略资源，信息化水平也已成为现代水平和综合国力的重要标志。今年是“十五”计划开局之年，中共十五届五中全会通过的国民经济和社会发展第十个五年计划建议中已明确指出：“信息化是当今世界经济和社会发展的大趋势，也是我国产业优化升级和实现工业化、现代化的关键环节。”“大力推进国民经济和社会信息化，是覆盖现代化建设全局的战略举措。”，可见，党和国家已将国民经济和社会信息化放在优先发展位置，体现了先进生产力的客观要求，是一项重要的战略决策。这是民航加快发展的机遇，更是民航信息化的难得机遇。 随着知识经济的到来，人类已经逐步进入信息化社会，信息增长的速度越来越快，人们希望利用先进的管理理论方法手段来得到并处理越来越多的信息，以提高工作效率和管理水平。由于信息资源对人们生活的重要性，不断提高信息的收集，传输，加以利用等活动，日益成为人们社会生活的重要组成部分。网上机票预订管理系统的产生和发展正好满足人们的这种需求。现在将详细介绍我的课程设计——网上机票预订管理系统。 2.2软件主要组成及功能 要完成功能主要有： ●新用户注册，新用户可以注册，注册时输入用户名可以查询用户可不可用，可用就 可以注册，注册时可以判断用户输入的密码和验证密码是否相同，相同才给以注册， 如果满意可以点注册，注册成功后用户可以选择不用在回到登陆界面，可以直接 陆到用户主界面，以后就可以用这个用户登录了，如果不满意，点取消，所有信息 清空，重新输入。 ●验证登陆名密码，正确进入主菜单，根据登录时所选的登录方式（客户、管理员） 的不同分别对用户设定不同的访问权限（如果是输入的客户用户名和密码正确，选 择以客户方式登陆则主界面里面的管理员界面不能用，如果输入的是管理员的相应 用户密码正确，以管理员的方式登陆则管理员界面可用）不正确则清空登录框，最 多可以输入三次，三次不正确系统会自动关闭。 ●主窗体的用户信息界面，用户点击个人查询按钮，可以把自己的个人信息显示到界 面上，还可以对自己的信息进行相应的修改（用户编号和用户名不能修改），还可 以点击我的机票查询，查询该用户的订票记录。 ●主窗体的订票界面，你可以点击你想查询的有关机票的信息的按钮（舱位信息查询， 客机信息查询，航线查询，客户类型信息查询）获得相关信息的表，根据表的内容， 你可以在下面的下拉框中选择你要定的票信息，点确定后在下面会显示你的机票的文献检索与科技论文写作期末训练题
学术论文写作的要点范文
航空售票管理系统
论文的Abstract写法
titlesec宏包使用手册
Abstract Writing (论文摘要写作精简版)
(强烈推荐)火车票网上订票系统系统毕业论文设计
影院网上订票系统需求说明书
研究方法与论文写作
民航订票管理系统
论文写作abstract
ctex 宏包说明 ctex
教你学术论文毕业论文的写作教程anabstract
网上机票预订系统
相关主题
文本预览