____________________________________________________________________________

CSEE E6861						      Handout #23b
Prof. Steven Nowick					      March 7, 2013

____________________________________________________________________________
____________________________________________________________________________


		       MIDTERM CAD MINI-PROJECT:  


PART #2:  UNATE RECURSIVE PARADIGM -- FUNCTION "SIMILARITY" EVALUATION TOOL
		     
____________________________________________________________________________
____________________________________________________________________________

OVERVIEW:

In this problem, you are to use your experience with unate recursive
algorithms to design a new algorithm, and to create a supporting CAD tool: 
TO EVALUATE THE "SIMILARITY" OF 2 BOOLEAN FUNCTIONS, f AND g. 

BACKGROUND:

Given two single-output Boolean functions f and g, it is sometimes useful
to determine how "similar" the functions are.  For example, suppose a 
combinational function block was implemented for function f, 
and a designer made some incremental modifications to the block, where the new 
combinational function is g.  We define the SIMILARITY s(f,g) OF FUNCTIONS f AND g as
the percentage of minterms where the two functions have the same values.
From a designer viewpoint, the similarity metric, s(f,g), indicates the percentage 
of input vectors under which the two combinational blocks will produce the same 
output results.


DISCUSSION:

In tautology-checking, complementation, and prime generation, each algorithm 
begins with a cover F of a function f.  A divide-and-conquer approach is then used, 
based on Shannon decomposition, where the cover is split recursively using splitting 
variables in some order.  The recursion terminates when certain termination conditions
are satisfied, where these termination conditions are different for
each of the above algorithms.  The results are then combined together into a solution.  

Several handouts have covered these basic algorithms:  tautology checking (#11),
complementation (#16), prime generation (#18), and illustrative examples (#12, #19).
In addition, in HW#3 problem #6, you developed a new algorithm for function 
"density" evaluation.  Note that all of the above algorithms operate on a 
single cover F.

In this problem, your goal is to follow some of the recursive strategies you
have learned, as well as modify or extend them, to handle this new CAD problem.
In particular, unlike the previous algorithms, 
your starting point will now be TWO COVERS, $F$ and $G$, not one cover. 
In addition, you will be returning a result which is a SIMILARITY PERCENTAGE, 
rather than a cover.


ASSUMPTIONS:

Assume that both f and g are fully-specified single-output functions 
(i.e. have no don't cares -- DC-set is empty).  Also, assume both
functions have identical "support"  (i.e. both are functions of precisely the 
same input variables).

WHAT TO DO:

Your algorithm will take covers F and G, and eventually return 
the similarity result, s(f,g), which is the final percentage
of all minterms where f and g have identical function values.
You are to clearly and precisely outline your new algorithm, and
implement in a software CAD tool.

In particular, the following are guidelines to address in both your algorithm/tool
design, and in your writeup.

  (i) How does algorithm handle two covers, instead of one?  (how is
      splitting performed, how are results assembled?)  What form of
      Shannon decomposition equation do you use?  How is splitting perforrmed?

 (ii) What termination conditions do you propose? (these can 
      be simple, but must still allow early termination). 
      For each termination condition, what result is returned?
      You should try to find a varied and powerful set of termination conditions,
      including simple basic ones, as well as more sophisticated ones.
      However, in each case, the rule must be simple and fast to apply,
      not complex and slow. 

(iii) What unateness and other properties, if any, can you exploit,
      in (a) forming termination rules, or in (b) directing and simplifying 
      the search?  

 (iv) How is the similarity percentage formed and returned at each step
      of the recursion?

  (v) What criteria do you propose to select a good splitting variable,
      given that the algorithm handles two covers instead of one?
      In addition, think over and justify your proposed criteria:
      give reasons, trade-offs and/or hypotheses, to explain why you
      propose them.

NOTE: As a general guideline, your approach, rules and conditions should 
be easy to apply, and should improve the search rather than making it more 
complicated or slower.  Your soultion should follow the general divide-and-conquer 
strategies of the existing algorithms, and be based on a form of Shannon decomposition.  
However, you should customize your solution to address this new problem.

Remember the goals of such an algorithm:  if you provide termination rules or 
recursive strategies that require complex and expensive calculation, the runtime
of the algorithm will be poor and points will be deducted.  The goal is to find
techniques that are simple, relatively fast, and effective.

____________________________________________________________________________
____________________________________________________________________________

DETAILS:

Due Date:  at start of class, Thursday, March 28

Languages allowed:  C/C++ or Java.  For others, you need to ask permission
  	    	   	 of the instructor and TA.

Report Writeup:  along with your source code, you will also be producing 
       a short report on your tool (2-3 pages).  Details will be announced 
       shortly.

Demo:  You will need to set up a demo to present your tool to Weiwei.
       The demo will be run both on examples provided to you in advance,	
       as well as new examples.
       
Group Work:  You may work solo or in a group of 2, for this problem.
       Both students in a group will receive the same grade.
       I encourage you to work in a group-of-2.

Grading:  The entire combined 'midterm homework and CAD project' is 
       worth 20% of your final grade.  It includes 3 parts:  homework 
       (written problems and SIS CAD tool problem), and CAD 
       programming problems part #1 and part #2.	       

       The current part (CAD tool part #2) is worth 5% of your final 
       course grade.

Input/Output Format: You are NOT allowed to create your own input format for 
       what to read in.  

       ==> Details on required format will be provided soon. <==

Commenting:  Your program should have clear comments.  We will be looking
       at your source code.	     

How to Submit:  Details will be announced shortly.

____________________________________________________________________________
____________________________________________________________________________