Optimized circuit to correct function approximation outliers

Abstract

Correction of outliers in a data set includes receiving a first set of inputs of an input dataset requiring positive correction; and receiving a second set of inputs of the input dataset requiring negative correction. Conjunctive clauses with a predetermined number of terms that make all members in the second set of inputs false are identified to form a set of identified conjunctive clauses. Members from the first set of inputs that evaluate to true are collected for each conjunctive clause in the set of identified clauses. The set of identified conjunctive clauses are iterated through until all of the first set of inputs evaluates to true, and the conjunctive clauses are disjuncted to form a disjuncted expression. A correction circuit for the input dataset is generated based on the disjuncted expression.

What is claimed is: 
     
         1 . A method for correction of outliers for a function, the method comprising:
 receiving a set of potential adjustments to one or more output values of a function, each of the one or more output values having a corresponding input value, each input value and corresponding output value comprising an input/output pair;   receiving, for each of a plurality of inputs to the function, a set of acceptable output values for the function;   identifying, as outlier values, the input/output pairs for which a given output is not in the set of acceptable values for the given input;   determining, for the potential adjustments in the set of adjustments, a logical predicate which is true for a subset of the plurality of input values such that:
 a. at most one logical predicate is true for each input value, 
 b. at least one logical predicate must be true for each input value associated with an outlier value, and 
 c. when the corresponding potential adjustment is applied to the output value of the function evaluated at an input value for which the predicate produces a true value, the resulting adjusted output value is in the set of acceptable values. 
   
     
     
         2 . The method of  claim 1 , further comprising determining a hardware circuit to realize the logical predicate. 
     
     
         3 . The method of  claim 1 , further comprising determining one or more software functions to realize the logical predicate. 
     
     
         4 . The method of  claim 1 , wherein the input values and the output values are one or more of sets of binary representations from a set of integer values, floating-point values, vectors of integer values, or vectors of floating-point values. 
     
     
         5 . The method of  claim 1 , wherein the function is an approximation of a mathematical function, and the set of acceptable values are determined based upon one of a maximum tolerated absolute approximation error, a maximum tolerated positive approximation error, or a maximum tolerated negative approximation error. 
     
     
         6 . The method of  claim 1 , wherein the logical predicate comprises a disjunction of a conjunction. 
     
     
         7 . The method of  claim 1 , wherein the logical predicate is determined based on a greedy algorithm. 
     
     
         8 . The method of  claim 1 , wherein the logical predicate is determined based on a bit minimization algorithm. 
     
     
         9 . The method of  claim 1 , wherein the potential adjustments include correction for positive outliers, correction for negative outliers, correction for both positive or negative outliers, correction for single unit in last place outliers or multiple unit in last place outliers. 
     
     
         10 . A method for correction of outliers in a dataset, the method comprising:
 receiving a first set of inputs of an input dataset requiring positive correction;   receiving a second set of inputs of the input dataset requiring negative correction;   identifying conjunctive clauses with a predetermined number of terms that make all members in the second set of inputs false to form a set of identified conjunctive clauses;   collecting, for each conjunctive clause in the set of identified clauses, members from the first set of inputs that evaluate to true;   iterating through the set of identified conjunctive clauses until all of the first set of inputs evaluates to true;   disjuncting the conjunctive clauses to form a disjuncted expression; and   generating a correction circuit for the input dataset based on the disjuncted expression.   
     
     
         11 . The method of  claim 10 , wherein the input dataset is associated with an approximation function. 
     
     
         12 . The method of  claim 10 , wherein disjuncting the conjunctive clauses includes performing OR operations on all AND results. 
     
     
         13 . The method of  claim 10 , wherein the first set of inputs includes a two most negative unit in last place errors of the input dataset. 
     
     
         14 . The method of  claim 10 , wherein the second set of inputs includes a two most positive unit in last place errors of the input dataset. 
     
     
         15 . The method of  claim 10 , wherein the disjuncted expression comprises a disjunctive normal form (DNF) expression. 
     
     
         16 . The method of  claim 10 , wherein the conjunctive clauses are associated with AND gates of the correction circuit. 
     
     
         17 . An apparatus for correction of outliers in a dataset, the apparatus comprising:
 a processor; a computer memory operatively coupled to the processor; and   logic configured to cause the apparatus to:
 receive a first set of inputs of an input dataset requiring positive correction; 
 receive a second set of inputs of the input dataset requiring negative correction; 
 identify conjunctive clauses with a predetermined number of terms that make all members in the second set of inputs false to form a set of identified conjunctive clauses; 
 collect, for each conjunctive clause in the set of identified clauses, members from the first set of inputs that evaluate to true; 
 iterate through the set of identified conjunctive clauses until all of the first set of inputs evaluates to true; 
 disjunct the conjunctive clauses to form a disjuncted expression; and 
 generate a correction circuit for the input dataset based on the disjuncted expression. 
   
     
     
         18 . The apparatus of  claim 17 , wherein the input dataset is associated with an approximation function. 
     
     
         19 . The apparatus of  claim 17 , wherein disjuncting the conjunctive clauses includes performing OR operations on all AND results. 
     
     
         20 . The apparatus of  claim 17 , wherein the first set of inputs includes a two most negative unit in last place errors of the input dataset.