On the minimal implementation of the Boolean tuple matching operator

N. P. Red'kin

Lomonosov Moscow State University

Abstract: We investigate the complexity of implementing the matching operator $R_n(\tilde x,\tilde y)$ of two Boolean $n$-tuples $\tilde x=(x_1,\dots,x_n)$ and $\tilde y=(y_1,\dots,y_n)$, which converts to one if and only if $\tilde x=\tilde y$. We establish that the minimum Boolean circuit for $R_n(\tilde x,\tilde y)$ in the basis $\{x\&y,\overline x\}$ contains $8n-1$ gates.

Keywords: Boolean function, circuit, minimal circuit.

UDC: 519.714.7

Received: 03.07.2024

DOI: 10.4213/dm1847