6
$\begingroup$

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    
$\endgroup$
  • $\begingroup$ What is the desired behavior? $\endgroup$ – Beastly Gerbil Nov 10 '16 at 20:01
  • 2
    $\begingroup$ 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? $\endgroup$ – Peregrine Rook Nov 11 '16 at 3:22
  • 2
    $\begingroup$ This is not really a puzzle - it seems to be an engineering problem that Jean faces and has trouble in solving. $\endgroup$ – Moti Nov 12 '16 at 7:18
  • 1
    $\begingroup$ @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 $\endgroup$ – Areeb Nov 12 '16 at 17:11
  • 1
    $\begingroup$ 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.) $\endgroup$ – Bass Jan 21 '18 at 6:23
2
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.