3

Assume that I have a multi-output Boolean function $f(x_1,x_2,x_3,x_4) = (y_1,y_2,y_3,y_4)$.

Is there a direct way of computing the inverse, that is, $g$ such that $g(y_1,y_2,y_3,y_4) = (x_1,x_2,x_3,x_4)$?

Naturally, I could construct function $g$ from scratch, but in this case function $f$ is fairly optimized w.r.t number of gates. Thus, it is of interest to directly reversing it.

George V. Williams
  • 5,213
kostaspap
  • 131
  • 1
  • 4

1 Answers1

1

To actually have an inverse function, the function f() has to be bijective. Such a bijection maps each of the $2^n$ different input patterns one-to-one to a unique output pattern.

Putting it the other way round:
If two or more input patterns would lead to the same output pattern, one could not tell from the output what input pattern is present.

Assuming that f() is a bijection, it must have the same number of inputs and outputs. Otherwise, the number of possible input patterns would not match the number of possible output patterns.

I am not aware of any method to directly construct such an inverse function or mapping. But for only four inputs, it is just a truth table with 16 rows. It should be a quick task using tools like Logic Friday 1 or Berkeley Octtools to compile such a table into a decent circuit.

Axel Kemper
  • 4,943