Matrix method of parallel decomposition for minimization of symmetric Boolean functions in the form of extended polynomial

Abstract

A matrix method of parallel decomposition in order to minimize symmetric Boolean functions in orthogonal form of representation in the form of extended polynomial by modulus 2 has been developed. Symmetrical Boolean functions are characterized by the fact that they are not minimized in classical form of representation, but well – in the form of Zhegalkin polynomials. Compared to Zhegalkin polynomials, extended polynomials have better indicators of the complexity of implementing digital devices by total coefficient SL (1.49 times) and by total coefficient SAD (2.37 times) due to a slight deterioration of the total coefficient SS (deterioration of 1.293 times). The coefficient SS is less important for the development of digital devices than the coefficients SL and SAD. Another advantage of using extended polynomials consists in the use of the idea of polarization of inputs of Boolean functions. Due to this, this method can be used as a powerful component of complete matrix method of parallel decomposition for obtaining a complex minimal form of Boolean functions, which has the best indicators of the complexity of digital blocks implementation due to a slight decrease in the speed of their work. Unlike Zhegalkin polynomials having only one variant of the minimal form, an extended polynomial can have several minimal forms with the same complexity of implementation, that is essential for minimizing the systems of Boolean functions. An essential feature of implementation of the method consists in the use of ready-made expanded matrices and tables of a complete list of conjunctive sets, which significantly accelerates the process of minimization in time.

В роботі розроблено матричний метод паралельної декомпозиції для мінімізації симетричних булевих функцій в ортогональній формі представлення у вигляді розширеного полінома суми за модулем 2. Симетричні булеві функції характеризуються тим, що вони погано мінімізуються в класичній формі представлення, але добре – поліномами Жегалкіна. Результати, отримані цим методом, порівняно з результатами в поліномі Жегалкіна мають суттєве покращення показників складності реалізації цифрових пристроїв за сумарними коефіцієнтами SL (в 1,49 разу) та SAD (в 2,37 разу) за рахунок незначного погіршення сумарного коефіцієнта SS (погіршення в 1,293 разу), що не є таким значущим при розробці таких цифрових пристроїв, як коефіцієнти SL і SAD. Також за рахунок поляризації входів булевих функцій цей метод може бути використано як один із складових чинників повного матричного методу паралельної декомпозиції для отримання комплексної мінімальної форми булевих функцій, що має кращі показники складності реалізації, ніж класичні форми представлення булевих функцій. Цей метод дає можливість отримувати для булевих функцій кілька результатів з однаковими показниками складності реалізації, що є суттєвим при мінімізації систем булевих функцій. Суттєвою особливістю методу є застосування вже готових розширених матриць і таблиць повного переліку кон’юнктивних наборів, що суттєво прискорює процес мінімізації в часі.