October 2015
<<September October November>>
There are straightforward ways to implement a counter that yields nine functions, such as:
abcde03303003300303303003033003303003
fghij03303003300303303003033003303003
nnnpk01121223011212230112122301121223
abcde00010111011111120111111211121222
fghij00010111011111120111111211121222
stuvq01122330122330012330011230011223
stuvq00000001000001110001111101111111
zwxlr01122330011223300112233001100112
zwxlr00000001111111122222222333300000
29 30 27 28
If you compute the sum of 11 bits modulo 4 and modulo 3, you can use the Chinese Remainder Theorem (http://mathworld.wolfram.com/ChineseRemainderTheorem.html) to compute the sum in eight functions:
abcde01121223122323301223233023303001
fghij01121223122323301223233023303001
mnopk01122330122330012330011230011223
abcde01121220122020011220200120010112
fghij01121220122020011220200120010112
stuvk011220..122001..200112..011220..
qrwxl001122..220011..112200..011223..
qrwxl010101..121212..232323..303030..
25 26 27 28
There are more ways, but the best we know of uses only six functions:
abcde01121223122323301223233023303001
fghin01121223122323301223233023303001
ppjkl01121223122323300112122312232330
qmabc00020222111111111113133322222222
tofgh00020222111111111113133322222222
pqrsu01120112011201121223011201120112
23 24 22 18
Thanks to an anonymous solver who implemented 11 bits counter with only 5 functions:
abcde13303002300202213002022102212113
fghil23313110311010023110100210020223
jkmno20133102123003211230032131022013
deilo00101011221032112210321122323233
mnqrs22222222212102022211002202210221
21 20 17 16
Leo Broukhis answered the question what a good FPGA compiler would do (as Teraptor tweeted https://twitter.com/teraptor/status/650359650668314624?refsrc=email&s=11): FPGA compilers (e.g. Synplicity by Synopsys) fare badly. As interconnected groups of 5-to-2 functions strain the FPGA connectivity fabric by (almost) fully utilizing all inputs and outputs of logic blocks, tools do not attempt to pack tightly into such functions to avoid placement and routing issues.
Leo also supplied a natural language explanation of a 6 function solution:
First, observe that the 3-bit sum of 5 bits 4*f+2*t+o (after "four", "two", and "one") cannot be equal to 6 or 7, which means that (t=1) =>(f=0). Also, f can be derived from t, o, and any two inputs x,y,
making a 4-input function: if t=1 then f=0 else if o=0 then f=(x|y) else f=(x&y).
For convenience, intermediate values will be denoted by fN, tN, oN, the final results - with capital O,T,F,E (for eight).
First, sum two groups of 5 inputs:
{t1,o1} = (a+b+c+d+e) mod 4
{t2,o2} = (f+g+h+i+j) mod 4
Then produce the ones bit:
{t3,O} = (o1+o2+k+l) mod 4
Left to add are t1, t2, t3, "f1", "f2", "f3".{f4,t4} = 2*f1 + t1 + t3, where f1 is a function of t1, o1, a, b As f1 and t1 cannot be equal to 1 at the same time, there is no carry.
Similarly,
{f5, T} = 2*f2 + t2 + t4, where f2 is a function of t2, o2, f, g
The value of f3 comes from the sum of 4 bits, therefore it depends on t3, O and only one bit of input; therefore
{E, F} = f3 + f4 + f5, where f3 is a function of t3, O, o1.