Training digital circuits with Hamming clustering

A new algorithm, called Hamming clustering (HC), for the solution of classi fication problems with binary inputs is proposed,It builds a logical networ k containing only AND, OR, and NOT ports which, in addition to satisfying a ll the input-output pairs included in a given finite consistent training se t, is able to reconstruct the underlying Boolean function, The basic kernel of the method is the generation of clusters of input patte rns that belong to the same class and are close to each other according to the Hamming distance. A pruning phase precedes the construction of the digi tal circuit so as to reduce its complexity or to improve its robustness. A theoretical evaluation of the execution time required by HC shows that th e behavior of the computational cost is polynomial. This result is confirme d by extensive simulations on artificial and real-world benchmarks, which p oint out also the generalization ability of the logical networks trained by HC.