Puzzle #10 – Mux Logic

Your company is pretty tight on budget this year and it happens to have only Muxes to design with.
You are required to design a circuit equivalent to the one below, using only Mux structures.

Puzzle #9 – The Snail

It’s been a while since I posted a nice puzzle and since I know they are so popular, here is a relatively simple one. It was used in job interviews btw (the last line will boost the amount of views for this post…)

A snail leaves his warm house and takes a crawl through the forest leaving behind him on the ground a trail of “0″s and “1″s. He takes a very complicated route crossing his path several times. At one point he becomes tired and disoriented and wishes to go back home. He sees his own path of “0″s and “1″s on the ground which he is about to cross (i.e. not the trail ending in his tail) and wonders whether to follow the trail towards the left or towards the right.
What is the shortest repeating code of “0″s and “1″s he should leave as he crawls in order to easily and deterministically track the way back home? What is the minimum amount of bits he needs to observe (or the sample length of the code)?

Puzzle #6 – The Spy- Solution

This puzzle created some interest, but apart from one non-complete solution which demonstrates the principle only, I didn’t receive any other feedback. Here is my own solution, which is different than the one given in the Winkler book. Naturally, I believe my solution is easier to understand, but please get the Winkler book, it is really that good and you could decide for yourself.

Now for the reason you are reading this post… the solution… oh, if you don’t remember the puzzle, please take a few moments to re-read it and understand what it is all about.

I will (try to) prove that 16 different symbols can be transmitted by flipping a single bit of the 15 which are transmitted daily.
First, for convenience reasons we define the 15-bit transmission as a 14-0 vector.
We will now define four parity functions P0,P1,P2,P3, as follows:

Why these specific functions will be clear in a moment.
Let’s try to view them in a more graphical way by marking above each bit in the vector (with the symbols P0..P3) iff this bit affects the calculation of the respective “P-function”. For example, bit 11 is included in the formula for P0 and P3 therefore we mark the column above it with P0 and P3.
So far so good, but a closer look (diagram below) on the distribution of the “P-functions” reveals why and how they were constructed.

The “P-functions” were constructed in such a way that we have 1 bit which affects only the calculation of P0, one bit which affects only P0 and P1, one which affects only P0 and P2 and so on… Try to observe the columns above each of the bits in the vector – they span all the possible combinations!

From here the end is very close.
The operators on the receiving side have to calculate the P0..P3 functions and assemble them into a 4-bit “word”.
All the spy has to do, is calculate the actual “P-functions” given by today’s random transmission and get a 4-bit “word”. The spy compares this to the 4-bit “word” she wants to transmit and discovers the difference – or in other words: the bits which need to be flipped in order to arrive from the actual “P-functions” to the desired “P-functions”. She then looks up in the diagram above and flips exactly that bit which corresponds to exactly the “P-functions” that she needs to flip. A single bit flip will also toggle the corresponding “P-function/s”.

Since the above wording may sound a big vague, here is a table with some examples:

I have to say this again, This is really one of the most beautiful and elegant puzzles I came across. It is definitely going into “the notebook”…

Puzzle #8 – Clock Frequency Driver

Take the clock frequency circuit I posted about here. As I mentioned the XOR gate at the output might cause some duty cycle distortion with some libraries, due to the fact that most XOR gates are not built to be symmetrical with respect to transition delay.
Now, assume your library has a perfectly symmetrical NAND gate. Could you modify the circuit so the XOR will be replaced by a NAND gate and still have a clock frequency at the output (You are of course allowed to add more logic on other parts of the circuit).

If not, give a short explanation why not. If yes send a circuit description/diagram.

Puzzle #7 – Transitions – Solution

This one was solved pretty quickly. Basically I was trying to trick you. The idea was to try to create the impression an infinite amount of memory is necessary to hold all the 0–>1 and 1–>0 transitions. In practice there cannot be 2 consecutive 0–>1 transitions (or vice versa) since if the input goes from 0 to 1 before the next 0–>1 transition it must change to a 0 and thus have a 1–>0 transition!
The FSM can have only three states: “exactly one more 0–>1″, “equal amount of 0–>1 and 1–>0″ or “exactly one more 1–>0″.

Puzzle #7 – Transitions

It’s time for puzzle #7.

An FSM receives an endless stream of “0″s and “1″s. The stream can not be assumed to have certain properties like randomness, transition density or the like.

Is it possible to build a state machine, which at any given moment outputs whether there were more 0–>1 or 1–>0 transitions so far?

If yes, describe briefly the FSM. If no, give a short proof.

Puzzle #5 – Binary-Gray counters – solution

The binary-Gray puzzle from last week generated some flow of comments and emails.
Basically, the important point to notice is the amount each counter toggles while going through a complete counting cycle.

For Gray coded counter, by definition only one bit changes at a time. Therefore, for an n stage counter we get 2^n toggling events for a complete counting cycle.

For binary coded n-bit counter, we have 2^(n+1)-2 toggling events for a complete counting cycle. you could verify this by

1. Taking my word for it (don’t – check it yourself)
2. Writing down manually the results for a few simple cases and convince yourself it is so
3. Calculate the general case, but you have to remember something about how to calculate the sum of a simple series (best way)

Anyways, given the above assumptions and the fact that per bit the Gray counter consumes 3 times more power (2 times more would also just work, but the difference would be a constant), the Gray counter will always consume more power.
3*2^n > 2^(n+1) – 2

Puzzle #4 – Solution

Here are the block diagrams for the solution of the MinMax problem.

Puzzle #6 – The Spy – (A real tough one…)

This one I heard a while back and saw that a version of it also appears in Peter Winkler’s excellent book Mathematical Puzzles – A Connoisseur’s Collection. Here is the version that appears in the book:

A spy in an enemy country wants to transmit information back to his home country.
The spy wants to utilize the enemy country’s daily morning radio transmission of 15-bits (which is also received in his home country). The spy is able to infiltrate the radio station 5 minutes before transmission time, analyze the transmission that is about to go on air, and can either leave as it is, or flip a single bit somewhere in the transmission (a flip of more than one bit would make the original transmission too corrupt).

how much information can the spy transmit to his operators?

remember:

• The transmission is most likely a different set of 15-bits each day but can also repeat the last day’s transmission. Best, assume it is random
• The spy is allowed to change a maximum of 1 bit in any position
• The spy has agreed on an algorithm/strategy with his operators before he was sent to the enemy country
• No other information or communication is available. the communication is strictly one way
• The spy sees for the first time the intended daily transmission 5 minutes before it goes on the air, he does not hold a list of all future transmissions
• The information on the other end should be extracted in a deterministic way

I believe this one is too tough for an interview question – it took me well over an hour to come up with a solution (well, that actually doesn’t say much…). Anyways, this is definitely one of my favorite puzzles.

Puzzle #3 – Solution

This post is written only for completeness reasons. The answer to puzzle #3 was almost immediately given in the comments. I will just repeat it here.
The important observations are that XOR (X,X) = 0 and that XOR(X,0) = X The solution is therefore:

Operation       Result
---------------------------------
X = XOR(,)     X^Y,Y
Y = XOR(,)     X^Y,X^Y^Y = X
X = XOR(,)     X^X^Y = Y,X  done!