## Puzzle #4 – The min-max question

June 8, 2007Here 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?

Hello,

by Ankit June 16, 2007 at 6:57 pmthese 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.

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).

by nirdahan June 16, 2007 at 8:01 pmHope this helps…

Nir

[…] 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. […]

by Puzzle #4 - Solution « Adventures in ASIC Digital Design June 24, 2007 at 9:54 pm(Fixed some typo) The number of different input sequence two verify the logical behaviour is 2.

For eg:-

by Santhosh K.R June 27, 2007 at 7:27 pmA. 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

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…

by nirdahan June 27, 2007 at 9:36 pmI 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.

by Santhosh K.R June 29, 2007 at 3:48 amThe idea is to test the MinMax4 component for all possible faults with the minimum amount of test vectors.

by nirdahan June 29, 2007 at 6:47 amI cannot find the answer to the bonus question. Can you attach the link?

by Leon Q January 13, 2010 at 8:26 pmvectors {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

by srini January 28, 2010 at 11:49 am[…] https://asicdigitaldesign.wordpress.com/2007/06/08/puzzle-4-the-min-max-question/ […]

by Interview question, testing a sorting network | Q&A System December 16, 2011 at 10:46 amone combination {3 4 2 1} will be sufficient to check any faulty MinMax2

by Samatha May 31, 2012 at 9:41 pmeither the combination {(4,3),(2,1)} or {(1,2),(3,4)} will work. (_,_) means input to one Maxmin unit

by Sanchari December 1, 2013 at 1:02 am