Christoph,

A table lookup would be possible, but a rather complex one.

Let's take your 4-bit example - that would be the table - and let's generate the 8-bit output. I add the number of ones and the number of numbers on that row to each row.

Row4 1 1111b,
Row3 4 0111b, 1011b, 1101b, 1110b,
Row2 6 0011b, 0101b, 0110b, 1001b, 1010b, 1100b,
Row1 4 0001b, 0010b, 0100b, 1000b,
Row0 1 0000b

Now a pseudocode:

for bits = 8 downto 0
  for i = 8 downto 0    
    if i>4 or (bits-i)>4 then shortcut to next bits *
      for j = 1 to length[row[i]]
        for k = 1 to length[row[bits-i]]
          output concatenation of row[i][j] and row[bits-i][k]
        next k
      next j
  next i
next bits

should generate the 8-bit output. IMHO it's quite easy to expand the same for more bits.

Have fun!

JW

-----
* OK I was lazy and some nicer optimisation could come here...
[added later]a good start for optimisation would be to use for i = 4 rather than 8... me stupido :-) [/added later]