 On the multiplicative complexity of quasi-quadratic Boolean functionsстатья Информация о цитировании статьи получена из Scopus, Web of Science
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 9 июня 2015 г.
• Автор:
• Журнал: Moscow University Computational Mathematics and Cybernetics
• Том: 39
• Номер: 1
• Год издания: 2015
• Издательство: Allerton Press Inc.
• Местоположение издательства: United States
• Первая страница: 18
• Последняя страница: 25
• DOI: 10.3103/S0278641915010069
• Аннотация: The multiplicative complexity μ(f) of Boolean function f(x 1, …, x n ) is the smallest number of AND gates in the circuits of basis {&, ⊕, 1} such that each circuit executes function f. Boolean function f(x 1, …, x n ) is quasi-quadratic if it can be presented as φ(x 1, …, x k ) ⊕ q(x 1, …, x n ), where φ is an arbitrary function, q is a quadratic function (i.e., a function of degree), k ≤ n. This work is concerned with the multiplicative complexity of quasi-quadratic functions with k = 3 and arbitrary n. We prove that if f(x 1, …, x n ) is a quasi-quadratic Boolean function where k = 3, n ≥ k, then μ(f) ≤ ⌈(n + 1)/2⌉, where ⌈a⌉ denotes the smallest integer not less than a. In addition, we describe the family of quasi-quadratic Boolean functions f n (x 1, …, x n ), k = 3, n = 5, 6, …, for which we prove that μ(f n ) = ⌈(n + 1)/2⌉.
• Добавил в систему: Селезнева Светлана Николаевна

Работа с статьей

  Selezneva S. N. On the multiplicative complexity of quasi-quadratic boolean functions // Moscow University Computational Mathematics and Cybernetics. — 2015. — Vol. 39, no. 1. — P. 18–25. The multiplicative complexity μ(f) of Boolean function f(x 1, …, x n ) is the smallest number of AND gates in the circuits of basis {&, ⊕, 1} such that each circuit executes function f. Boolean function f(x 1, …, x n ) is quasi-quadratic if it can be presented as φ(x 1, …, x k ) ⊕ q(x 1, …, x n ), where φ is an arbitrary function, q is a quadratic function (i.e., a function of degree), k ≤ n. This work is concerned with the multiplicative complexity of quasi-quadratic functions with k = 3 and arbitrary n. We prove that if f(x 1, …, x n ) is a quasi-quadratic Boolean function where k = 3, n ≥ k, then μ(f) ≤ ⌈(n + 1)/2⌉, where ⌈a⌉ denotes the smallest integer not less than a. In addition, we describe the family of quasi-quadratic Boolean functions f n (x 1, …, x n ), k = 3, n = 5, 6, …, for which we prove that μ(f n ) = ⌈(n + 1)/2⌉. [ DOI ]