Lesson 1

Synthesis is the process of creating a circuit for a given Boolean function. In this section, we will practice synthesizing circuits.

The \(\operatorname{SUM}_{n} \colon \{0,1\}^{n} \to \{0,1\}^{\ell}\) function outputs the binary representation of the sum of \(n\) input bits: \(\operatorname{SUM}_{n}(x_{1}, \dotsc, x_{n}) = (w_{0}, w_{1}, \dotsc, w_{\ell - 1})\), where \(\ell = \lceil \log_{2}(n + 1) \rceil\) and \[\sum_{i = 1}^{n}x_{i} = \sum_{i = 0}^{\ell - 1}2^{i}w_{i} \ .\]

Problem. Synthesize a circuit of size 12 for \(\operatorname{SUM}_{5}\).