Ponder This Challenge - October 2015 - Counting 12 bits using 5-to-2 functions

Ponder This Challenge:

Counting the number of 1s in a 12-bit input is a function from 12 to 4 bits.
Our challenge this month is to implement it with a minimal number of 5-to-2 functions (a function that receives 5 bits input and emits 2 bits output).
The format we request is several lines. Each line consists of <5 letters> followed by <32 base-4 digits>,
followed by the last line with 4 space separated numbers.
The 5 letters are the input to the function (the first letter is the msb) and the 32 digits are the output (the msb is the first output). The last line states which bits are used as the output.
To explain the format, here is an implementation that compares 2 numbers that are 2-bit, using 2 functions of 3-to-2
acd02113302
bef21133123
7 8
The input is a,b,c,d; the first line defines e,f as a function of the 3 bits a,c,d; and the second line applies a different 3-to-2 function on b,e,f, yielding a 2-bit output (g,h).
The last line states that the output of the computation is 7,8, where 7(=g) is the msb and 8(=h) is the lsb.
In the real problem, the output contains 4 bits. In our example, the output has 2 bits.

If a=0, c=0, d=0 then e=0 and f=0
If a=0, c=0, d=1 then e=1 and f=0
If a=0, c=1, d=0 then e=0 and f=1
If a=0, c=1, d=1 then e=0 and f=1
If a=1, c=0, d=0 then e=1 and f=1
If a=1, c=0, d=1 then e=1 and f=1
If a=1, c=1, d=0 then e=0 and f=0
If a=1, c=1, d=1 then e=1 and f=0
The output (g,h) is 0,1 if, and only if, 2*a+b < 2*c+d
The output (g,h) is 1,0 if, and only if, 2*a+b = 2*c+d
The output (g,h) is 1,1 if, and only if, 2*a+b > 2*c+d

Solution

• Click here to view the solution

  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.

Solvers

• ***Michael Brand (30/09/2015 04:00 AM IDT)
• ***Uoti Urpala (30/09/2015 06:47 PM IDT)
• Sean Egan (30/09/2015 09:13 PM IDT)
• **luke hsieh (01/10/2015 06:11 AM IDT)
• ***James Dow Allen (01/10/2015 06:53 AM IDT)
• Eitan Levine (01/10/2015 09:32 AM IDT)
• *Joseph DeVincentis (01/10/2015 08:12 PM IDT)
• *Edwin Karat (01/10/2015 08:34 PM IDT)
• *Daniel Bitin (02/10/2015 01:35 PM IDT)
• **Alexandre Gilotte (03/10/2015 06:36 PM IDT)
• Shisen Luo (05/10/2015 01:37 AM IDT)
• **Lorenz Reichel (06/10/2015 02:12 PM IDT)
• **Shirish Chinchalkar (07/10/2015 03:19 AM IDT)
• **Jesse Rearick (07/10/2015 06:40 AM IDT)
• *Kang Jin Cho (07/10/2015 10:14 AM IDT)
• *Francis Golding (07/10/2015 02:02 PM IDT)
• *Frank Samm (10/10/2015 08:56 AM IDT)
• *Andreas Puccio (10/10/2015 05:59 PM IDT)
• ***Liubing Yu (11/10/2015 04:19 AM PM IDT)
• **Keith Reckdahl & Gary Gerken (11/10/2015 07:22 AM PM IDT)
• *Dieter Beckerle (11/10/2015 08:55 AM PM IDT)
• *Graham Hemsley (11/10/2015 09:27 AM PM IDT)
• **Dan Dima (12/10/2015 12:47 AM PM IDT)
• *Sergey Koposov (13/10/2015 10:38 PM PM IDT)
• Isabella Cattinelli (14/10/2015 12:16 PM IDT)
• *Don Dodson & David Dodson (14/10/2015 02:55 PM IDT)
• *Peter Gerritson (14/10/2015 06:38 PM IDT)
• ***Radu-Alexandru Todor (14/10/2015 09:41 PM IDT)
• *Leo Broukhis (14/10/2015 11:19 PM IDT)
• *Hao Wu (15/10/2015 09:32 AM IDT)
• Aviv Nisgav (15/10/2015 12:08 PM IDT)
• ***Dmitry Teytelman (16/10/2015 03:18 AM IDT)
• *Harald Bögeholz (16/10/2015 10:56 AM IDT)
• *Armin Krauss (16/10/2015 02:50 PM IDT)
• *Clive Tong (16/10/2015 05:43 PM IDT)
• ***Luke Hsieh (16/10/2015 08:27 PM IDT)
• *Chris Hibbert (18/10/2015 12:23 AM IDT)
• *Di Luo (18/10/2015 08:48 AM IDT)
• **Motty Porat (18/10/2015 09:15 PM IDT)
• **Hongcheng Zhu (19/10/2015 01:59 AM IDT)
• **Matthew Rips (19/10/2015 07:44 AM IDT)
• ***Hendrik Nigul (19/10/2015 08:13 AM IDT)
• *Etienne Leloup (19/10/2015 09:32 PM IDT)
• Ganor Tamir & Shouky Dan (20/10/2015 11:23 AM IDT)
• ***Leo Broukhis (21/10/2015 03:10 AM IDT)
• **Raymond Lo (21/10/2015 12:01 PM IDT)
• Stéphane Higueret (22/10/2015 03:00 PM IDT)
• ***Tom Harley (22/10/2015 04:07 PM IDT)
• *Varun Ahluwalia (23/10/2015 03:28 AM IDT)
• *Gregory Giecold (24/10/2015 05:06 AM IDT)
• *Nyles Heise (24/10/2015 07:51 AM IDT)
• ***Motty Porat (25/10/2015 11:53 PM IDT)
• *Ali Can Keserel (27/10/2015 01:25 PM IDT)
• *Aviv Nisgav (28/10/2015 07:26 AM IDT)
• **Benjamin Lui (31/10/2015 01:29 PM IDT)
• **Arthur Nascimento (31/10/2015 05:35 PM IDT)
• *David Greer (01/11/2015 12:02 PM IDT)
• **David Dunkley (01/11/2015 02:52 PM IDT)