mapping - How many 5-input LUT functions are mappable to two cascaded 4-input LUTs? -

the questions can made more precise: out of 2²⁵ = 0x100000000 different functions realizable in 5-input lut, 0x3c1d3c82 functions realizable 2 cascaded 4-input luts?

background

one of standard building blocks in fpgas 4-input look-up table. 1 such table can realize 2²⁴ functions. standard method construct arbitrary 5-input lut use 3 4-input luts, 2 levels of logic, , use second level lut 2-to-1 multiplexer. arbitrary function f5(i4,i3,i2,i1,i0) may represented ff5(i4,g4(i3,i2,i1,i0),h4(i3,i2,i1,i0)), illustrated below.

       ___                ___           i3 ---|i3 |           ---|i3 |          i2 ---|i2 |        i4 ---|i2 |--- ff5   i1 ---|i1 |------- h4 ---|i1 |          i0 ---|i0_|   +--- g4 ---|i0_|                 ___    |  i3 ---|i3 |   | i2 ---|i2 |---+ i1 ---|i1 | i0 ---|i0_| 

more compact representation

however, many 5-input functions can represented 2 cascaded 4-input luts, gg(hh4(j4,j3,j2,j1),j2,j1,j0) j_n's permutation of i_n (n 0 4). graphically, can shown as:

       lut1        ___            lut2                        j4 ---|i3 |           ___              j3 ---|i2 |----hh----|i3 |            j2 ---|i1 |    j2 ---|i2 |-- gg j1 ---|i0_|    j1 ---|i1 |                j0 ---|i0_| 

result, verified

i have written brute force program find how many true 5-input functions can represented above construction, results are:

0 input lut...... :        0x2   0.0000% (constant 0 , constant 1) 1 input lut...... :        0xa   0.0000% (buffered signal , inverted signal) 2 input lut...... :       0x64   0.0000% 3 input lut...... :      0x884   0.0001% 4 input lut...... :    0x4ed9a   0.0075% chained luts..... : 0x3c1d3c82  23.4821% uncovered         : 0xc3ddccf0  76.5103% total             :0x100000000 100% 

5-input functions super-set of 4-input functions, not count 5-input functions can represented in single lut (or no lut @ all, functions 0x00000000 , 0xffffffff, , arguably 0xffff0000, 0xff00ff00, 0xf0f0f0f0, 0xcccccccc, 0xaaaaaaaa).

i wonder if else have conducted same exercise, , obtained same results?

this not answer question directly, answer looking @ first 3-lut example, when implemented using 'modern' fpga device (xilinx spartan 3, altera cyclone v, lattice ecp2 or newer), 'multiplexer' not use lut, rather there dedicated multiplexer resource purpose of creating wider logic functions.

these multiplexers avoid routing delay incurred using third lut multiplexer, or using chained lut in second example, resulting wide lut should operate @ higher frequency chained-lut approach. 'for free', in can used logic associated neighboring luts in same alm/slice.

i if chained-lut approach used less logic resource, still favor code written plainly while using more luts, code directly instantiated luts in way, associated totally unreadable lut initialisation values.