h1

Puzzle #4 – The min-max question

June 8, 2007

Here is a question you are bound to stumble upon in one of your logic design job interviews, why? I don’t know, I personally think it is pretty obvious, but what do I know…

MinMax2 is a component with 2 inputs – A and B, and 2 outputs – Max and Min. You guessed it, you connect the 2 n-bit numbers at the inputs and the component drives the Max output with the bigger of the two and the Min output with the smaller of the two.

Your job is to design a component – MinMax4, with 4 inputs and 4 outputs which sorts the 4 numbers using only MinMax2 components. Try to use as little as possible MinMax2 components.

If you made it so far, try making a MinMax6 component from MinMax2 and MinMax4 components.

For bonus points – how many different input sequences are needed to verify the logical behavior of MinMax4?

Advertisements

12 comments

  1. Hello,
    these type of min-max architecture are used in sorting networks. but I didn’t understand the bonus question as to what approach should be taken.


  2. Ok, maybe I was not clear enough there. Imagine the sequence 1,3,4,2 the outputs should be 1,2,3,4 after the sorting process. Now imagine that you get instead 1,3,2,4 at the output, this means one of MinMax2 components that makes the MinMax4 is faulty. The question is how many different sequences would you need to detect all possible logical faults? By a logical fault I mean a fault where min and max are reversed regardless of their value (e.g 1,3 giving Min = 3, Max = 1 and 4,5 giving Min = 5, Max = 4 is the very same fault – the Min, Max outputs are transposed).
    Hope this helps…
    Nir


  3. […] Adventures in ASIC Digital Design Tricks and Tips for ASIC Digital Designers « Puzzle #6 – The Spy – (A real tough one…) Puzzle #4 – Solution June 24th, 2007 Here are the block diagrams for the solution of the MinMax problem. […]


  4. (Fixed some typo) The number of different input sequence two verify the logical behaviour is 2.

    For eg:-
    A. MinMax2 has 2 inputs. The possible test vectors is 2.
    B. MinMax4 has 2 set of MinMax2.
    i. 1st set of vectors can be anything for eg(1,3,4,2) i.e 1,3 are feeded to 1st MinMax2 and 4,2 are feeded to 2nd MinMax2.
    ii. 2nd set of vectors can be 3,1 and 2,4.
    So possible test vectors are 1,3,4,2 and 3,1,2,4


  5. The answer is not correct, sorry.
    Look at your 2 test vectors the second number for example is always smaller than the 3rd – in both vectors. let’s say there is a problem with the device that compares those two numbers in the MinMax4 circuit. With these test vectors you would never detect that fault.

    Try to think of all pair combinations…


  6. I presume the idea here is to test the faulty systems with min set of vectors.
    Take an example.
    Vector 1
    ———
    (1,3) is feeded to A-MinMax2
    (4,2) is feeded to B-MinMax2

    Vector 2
    ———
    (3,1) is feeded to A-MinMax2
    (2,4) is feeded to B-MinMax2

    If there is a fault in either of MinMax2 then final outputs will be not in sorted order.


  7. The idea is to test the MinMax4 component for all possible faults with the minimum amount of test vectors.


  8. I cannot find the answer to the bonus question. Can you attach the link?


  9. vectors {1,2,3,4} {1,3,2,4} {4,2,3,1} {4,3,2,1} represent all possible cases of inputs…they are sufficient


  10. one combination {3 4 2 1} will be sufficient to check any faulty MinMax2


  11. either the combination {(4,3),(2,1)} or {(1,2),(3,4)} will work. (_,_) means input to one Maxmin unit



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: