Publicado em: 18/07/2012

Dissertação de Mestrado em Microeletrônica

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE POS-GRADUAÇÃO EM COMPUTAÇÃO
———————————————————
DEFESA DE DISSERTAÇÃO DE MESTRADO

Aluno: Vinicius Callegaro
Orientador: Prof. Dr. André Inácio Reis
Coorientador: Prof. Dr. Renato Perez Ribas

Título: Read-Polarity-Once Functions
Linha de Pesquisa: Microeletrônica

Data: 23/07/2012
Hora: 10h
Local: Auditório José Mauro Volkmer de Castilho, Prédio 43424 – Instituto de Informática

Banca Examinadora:
Prof. Dr. Marcelo de Oliveira Johann (UFRGS)
Prof. Dr. Raul Fernando Weber (UFRGS)
Prof. Dr. Sergio Bampi (UFRGS)

Presidente da Banca: Prof. Dr. André Inácio Reis

Abstract:
Efficient exact factoring algorithms are limited to read-once functions, in which each variable appears once in the final Boolean equation, e.g. f=a*(b+c*(d+e)). However, these algorithms present two main constraints: (1) they do not consider incompletely specified Boolean functions; and (2) they are not suitable for binate functions. To overcome the first drawback, an algorithm that finds read-once formulas for incompletely specified Boolean functions, whenever possible, is proposed. With respect to the second limitation, a domain transformation that splits existing binate variables into two independent unate variables is proposed. Such domain transformation leads to incompletely specified Boolean functions, which can be efficiently factored by applying the proposed algorithm. The combination of both contributions gives optimal results for a novel broader class of Boolean functions called read-polarity-once functions, where each polarity (positive or negative) of a variable appears at most once in the factored form, e.g. f=(!a*d+c)*(a+b). Experimental results over ISCAS’85 benchmark circuits have shown that read-polarity-once functions are significantly more frequent than read-once functions, for which many works have been devoted.

Keywords: Boolean function, factoring, logic synthesis, incompletely specified functions, read-once function, read-polarity-once function