18.104.22.168. Shannon’s Decomposition
Shannon’s decomposition plays a role in Hyper-Optimization. Shannon’s decomposition, or Shannon’s expansion, is a way of factoring a Boolean function. You can express a function as F = x.Fx + x′Fx′ where x.Fx and x′Fx′ are the positive and negative co-factors of the function F with respect to x. You can factor a function with four inputs as, (a, b, c, x) = x.(a, b, c, 1) + x′.F(a, b, c, 0), as shown in the following diagram. In Hyper-Optimization, Shannon’s decomposition pushes the x signal to the head of the cone of input logic, making the x signal the fastest path through the cone of logic. The x signal becomes the fastest path at the expense of all other signals. Using Shannon’s decomposition also doubles the area cost of the original function.
Shannon’s decomposition can be an effective optimization technique for loops. When you perform Shannon’s decomposition on logic in a loop, the logic in the loop moves outside the loop. The Compiler can now pipeline the logic moved outside the loop.
The output of the register in the loop is 0 or 1. You can duplicate the combinational logic that feeds the register in the loop, tying one copy’s input to 0, and the other copy’s input to 1.
Performing Shannon’s decomposition on the logic in the loop reduces the amount of logic in the loop. The Compiler can now perform register retiming or Hyper-Pipelining on the logic you remove from the loop, thereby increasing the circuit performance.
Did you find the information on this page useful?