Sum-Product Circuits

The previous section showed how to implement specific boolean gates as analog circuits. In this section, the same technique will be applied to circuits that implement the sum-product algorithm as described in section 4. These circuits will have to implement the following two equations for any number of variables:

$$p(x\vert\textbf{v}) = \beta \prod_{h\in n(x)\{f\}}\mu_{h\rightarrow x}(x)$$

$$\sum_{\sim\{x\}} \left ( f(x)\prod_{y\in n(f)\setminus\{x\}}\mu_{h\rightarrow x}(y) \right ).$$

as described in section 4.1.

Recall that we used a specific case of the second equation to build the boolean logic gates. The equation described the behavior of the variable $z$ in light of some apriori knowledge about the behavior the gate. That apriori knowledge was presented as an enumeration and the calculation was simple because the gate was boolean. In contrast, the function $f(x,y,z)$ in a sum-product message-passing computation may evaluate to any real number between 0 and 1. Thus, no terms may be eliminated from our equations as we no longer necessarily multiply by a 0 or a 1.

Function-to-Variable Circuits

Function-to-variable messages are the more complicated of the two types of messages required to implement the sum-product message-passing algorithm over a factor graph. These circuits must implement the type of marginalization described by equation 2 over all of their inputs. As we will see, this type of calculation becomes exponentially more complex with additional inputs. To start, we examine the implementation of a circuit with two inputs and one output. This circuit is described by equation 26, where $x$ and $y$ are inputs and $z$ is an output.

Similar to the boolean logic gates, we can enumerate the possible values of $x$, $y$, $z$, and their corresponding function $f(x,y,z)$. The only difference is that now the value of $f(x,y,z)$ is a real number between 0 and 1 that represents a probability. Equation 26 tells us that each $p(x)p(y)$ is multiplied by a corresponding $f(x,y,z)$. In function-to-variable circuits, this second level of multiplication will be accomplished by current scaling. Scaling by some fixed number can be done by scaling the sizes of the transistors in the train of a current mirror in relation to the size of its input transistor. The behavior of this scaling is given by equation 16.

The equations that result from expanding equation 26 are:

$$p(z = 0) = \ p(x = 0)p(y = 0)f(x = 0, y = 0, z = 0) +$$

$$p(x = 0)p(y = 1)f(x = 0, y = 1, z = 0) +$$

$$p(x = 1)p(y = 0)f(x = 1, y = 0, z = 0) +$$

$$p(x = 1)p(y = 1)f(x = 1, y = 1, z = 0)$$

and

$$p(z = 1) = \ p(x = 0)p(y = 0)f(x = 0, y = 0, z = 1) +$$

$$p(x = 0)p(y = 1)f(x = 0, y = 1, z = 1) +$$

$$p(x = 1)p(y = 0)f(x = 1, y = 0, z = 1) +$$

$$p(x = 1)p(y = 1)f(x = 1, y = 1, z = 1).$$

The four $p(x)p(y)$ terms are computed only once and shared between the two equations, but the $f(x,y,z)$ terms may all be different. Just as in the boolean OR gate circuit, we will make copies of the $p(x)p(y)$ terms as we need them need--two of each in this case--and then scale them according to an appropriate value, $f(x,y,z)$. The schematic for this specific case of the function-to-variable circuit is shown in figure 12 where $I_{3}$ - $I_{6}$ are the $p(x)p(y)$ terms and $I_{7}$ - $I_{14}$ are the $p(x)p(y)f(x,y,z)$ terms that are summed to generate the output.

Figure 12: Schematic for a two-input, one-output function-to-variable circuit for the sum-product algorithm.

As mentioned before, the complexity of this circuit grows exponentially with the number of inputs. A three-input function-to-variable circuit must compute all eight cases of the term $p(w)p(x)p(y)$, where $w$, $x$, and $y$ are the inputs. This is accomplished by adding a second layer of four differential pairs. Each differential pair takes as its base current, $I_{b}$, the value of $I_{1}$ or $I_{2}$ from one of the two differential pairs below it. Each of the eight $p(w)p(x)p(y)$ terms needs to be copied twice and scaled according to its corresponding $f(w,x,y,z)$. The addition of outputs only involves duplicating the existing single output. This is be accomplished by adding two current mirrors, one built from NFETs and one from PFETs such that the magnitude and direction of current flow is maintained. The train of the PFET current mirror can then generate as many duplicate outputs as needed.

Variable-to-Function Circuits

The circuits that implement the variable-to-function messages of the sum-product message-passing algorithm are simpler than the function-to-variable circuits described in the previous section. Variables in a factor graph do not store any apriori knowledge, so the calculation that they need to perform does not require multiplication by a function. The variable essentially combines the messages that are passed to it from its neighboring functions, as described by equation 3.

For a two-input, one-output circuit, as shown in figure 13, we need only perform one multiplication. This circuit is similar to the OR gate in that the unused terms must be computed because of the requirement that the two inputs to the differential pair must sum to one. Again we tie the unused branches of the differential pair to $V_{dd}$. Each additional input will add two additional differential pairs whose base current is the product of the previous inputs, so the complexity increases linearly with additional inputs. Additional outputs are generated by copying the computed value with two current mirrors, the same as with the function-to-variable circuits.

Figure 13: Schematic for a two-input, one-output variable-to-function circuit for the sum-product algorithm.