# How many function blocks do you need to make a controller?

You have 8 binary input signals to a controller, each one for each of the digits 1 - 8. The output is four binary signals, that make up the same number as the input. If the first input signal is 1, then the four output signals should be 0 0 0 1, if the seventh input signal is 1, then the output should be 0 1 1 1. The table below shows the system (just binary representation of decimal numbers).

d   4 3 2 1
-   - - - -
- 0 0 0 0
1 - 0 0 0 1
2 - 0 0 1 0
3 - 0 0 1 1
4 - 0 1 0 0
5 - 0 1 0 1
6 - 0 1 1 0
7 - 0 1 1 1
8 - 1 0 0 0


If the first input signal is 1, the output from the controller should be a binary output 0 0 0 1 (1 in binary). If the sixth input signal is 1 the output from the controller should be 0 1 1 0 (6 in binary). If no input signal is given, the output should just be blank.

If two or more input signals are 1, then the output signal should switch back and forth. E.g. if the first and sixth signal are 1, then the output from the controller should go back and forth between 0 0 0 1 and 0 1 1 0.

The controller has the following functions blocks:

• Logical gates AND, OR, XOR, NOT, NAND, NOR, XNOR. The gates can take up to 2 signals, and unlimited outputs. (NOT can only take one input).
• A pulse generator 1 0 1 0 1 0 1 ... (both 0 and 1 have the same duration). Pulse generators have the same frequencies but you may choose the phase.

Challenge:

What's the smallest number of function blocks needed to achieve the desired behavior, and how will the controller be made up?

Examples:

1 2 3 4 5 6 7 8
- - - - - - - -
0 0 0 0 0 0 0 0   <- Input signals
0 0 0 0           <- Output

0 0 1 0 0 0 0     <- Input signals
0 0 1 1           <- Output


0 1 0 0 1 0 0 0   <- Input signals
0 0 1 0           <- Output sequence
0 1 0 1           <-
0 0 1 0           <-
0 1 0 1           <-
0 0 1 0
0 1 0 1

0 0 1 1 1 1 1 0    <- Input signals
0 0 1 1            <- Output sequence
0 1 0 0            <-
0 1 0 1            <-
0 1 1 0            <-
0 1 1 1
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1

• ISTM that the answer could easily be well above 1000, with a lot of duplication, and it would be incredibly tedious to flesh out. Am I right?  Or is there some sort of clever/insightful shortcut to a simple and elegant solution? Nov 11, 2016 at 3:22
• This is not really a puzzle - it seems to be an engineering problem that Jean faces and has trouble in solving.
– Moti
Nov 12, 2016 at 7:18
• @Moti if it was, there are way better sites he could've gone on; the puzzling SE probably isn't filled with engineers; however, the engineering SE might Nov 12, 2016 at 17:11
• Can’t decide whether this should be puzzling, electronics or code golf. Love the puzzle though, so upvoting.
– Bass
Jan 21, 2018 at 5:59
• Might want to specify whether or not the sequence needs to be displayed so that the changes are regular. I think there may be some shortcuts if some numbers can be displayed longer than others. (Not really sure about that, but it never hurts to have unambiguous requirements in optimization competitions.)
– Bass
Jan 21, 2018 at 6:23

This is probably not optimal, but might be useful as a basis for other solutions.

Instead of drawing a diagram where wires x and y enter an AND-gate and z leaves it, let's use C-like syntax and write z=x&y. Likewise: z=x|y for OR, z=~x for NOT. (We don't use XOR, NAND, NOR, XNOR.) Wires are free, so it doesn't matter how many of them we name with =. Comments start with //. For conciseness, sometimes we'll write indices as x12 instead of the traditional x[1][2].

Let g1...g8 be pulse generators with phases 0, 1/8, 2/8, ..., 7/8 of the period.

    // time -->
g1  // 1 1 1 1 0 0 0 0
g2  // 0 1 1 1 1 0 0 0
g3  // 0 0 1 1 1 1 0 0
g4  // 0 0 0 1 1 1 1 0
g5  // 0 0 0 0 1 1 1 1
g6  // 1 0 0 0 0 1 1 1
g7  // 1 1 0 0 0 0 1 1
g8  // 1 1 1 0 0 0 0 1
// cost: 8


We can know the exact time (in eights of a period modulo 8) with

              // time -->
t1 = g1 & g6  // 1 0 0 0 0 0 0 0
t2 = g2 & g7  // 0 1 0 0 0 0 0 0
t3 = g3 & g8  // 0 0 1 0 0 0 0 0
t4 = g4 & g1  // 0 0 0 1 0 0 0 0
t5 = g5 & g2  // 0 0 0 0 1 0 0 0
t6 = g6 & g3  // 0 0 0 0 0 1 0 0
t7 = g7 & g4  // 0 0 0 0 0 0 1 0
t8 = g8 & g5  // 0 0 0 0 0 0 0 1
// cost: 8


Precompute the negations of the inputs:

y1 = ~x1
y2 = ~x2
...
y8 = ~x8
// cost: 8


Now the trickiest part - let v[i] indicate if i should be the currently displayed output value.

v1 = x1&(t1|(y2&(t2|(y3&(t3|(y4&(t4|(y5&(t5|(y6&(t6|(y7&(t7|(y8&t8))))))))))))))
v2 = x2&(t2|(y3&(t3|(y4&(t4|(y5&(t5|(y6&(t6|(y7&(t7|(y8&(t8|(y1&t1))))))))))))))
...
v8 = x8&(t8|(y1&(t1|(y2&(t2|(y3&(t3|(y4&(t4|(y5&(t5|(y6&(t6|(y7&t7))))))))))))))
// cost: 120 (8 lines * 15 functions per line)


Finally, we can convert the v-s to binary digits fairly efficiently:

d1 = v1 | v3 | v5 | v7
d2 = v2 | v3 | (v6|v7)  // v6|v7 can be computed only once
d3 = v4 | v5 | (v6|v7)
d4 = v8
// cost: 8


Total cost: 8+8+8+120+8 = 152 function blocks

• not valid because for one input high the output pulses. Jan 21, 2018 at 4:01
• @Jasen Sorry, I don't get what you mean. Could you clarify please?
– ngn
Jan 21, 2018 at 4:12
• when one output is high the output should be a steady binary number not alternating number-zero-number-zero Jan 21, 2018 at 4:19
• @Jasen Oh, I see... I'll try to fix it later. Thanks for letting me know.
– ngn
Jan 21, 2018 at 4:23
• output should be stable now, I believe
– ngn
Jan 21, 2018 at 18:14

Very Partial answer, since I haven't ever designed any circuits, logical, electrical, racing, or otherwise.

However, this looks just like the job for flip-flops. (If you need to regularly alternate between one or more inputs, you are going to need to keep track of state, and a flip-flop is the simplest way to do that.)

Chaining 9 of those guys together, using the pulse generator as a clock, it's probably possible to create a circuit that switches periodically to the next active input, and keeps its state until the next clock cycle. It will probably also cook your dinner (with excessive heating) or brain (with microwaves) since the simplest idea is just to keep busylooping over the inputs if none of of them are high. (You can tell I'm really out of my depth here, can't you..)

Assuming we somehow survive the part of the mission where we convert from 0-9 simultaneous inputs to 0-1 simultaeous but periodically changing inputs, the actual display can probably be run by "poor man's OR" gates, just soldering the wires together according to the binary representation of each input. (Yeah, you'll probably need a diode or two in there somewhere too.)

In case anyone with actual knowledge of how these things are supposed to work could be bothered to lend a hand, please holler, and I'll make this into a CW.