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!

Puzzle #5 - Binary-Gray

Assuming you have an n-bit binary counter, made of n identical cascaded cells, which hold the corresponding bit value. Each of the binary cells dissipates a power of P units only when it toggles.
You also have an n-bit Gray counter made of n cascaded cells, which dissipates 3P units of power per cell when it toggles.

You now let the counters run through an entire cycle (2^n different values) until they return to their starting position. Which counter burns more power?

Puzzle #4 - The min-max question

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?

Puzzle #3

OK, you seem to like them so here is another puzzle/interview question.

In the diagram below both X and Y are n-bit wide registers. With each clock cycle you could select a bit-wise basic operation between X and Y and load it to either X or Y, while the other register keeps its value.
The problem is to exchange the contents of X and Y. Describe the values of the “select logic op” and “load XnotY” signals for each clock cycle.

Puzzle #2 - Solution

4 full-adder units are necessary to count the amount of “1″s in a 7-bit vector.

The most important thing to notice is that a full-adder “counts” the amount of “1″s of it’s inputs. If you are not convinced , then a brief look in the component’s truth table will prove this to you. The output is a binary represented 2-bit number.

The next picture shows how to connect the four full-adders in the desired way. The first stage generates two 2-bit numbers, each represents the amount of “1″s among its respected three input bits. The second stage adds those two binary numbers together and uses the carry_in of one full-adder for the 7th bit.

As I mentioned when I posted the puzzle, I used this in an actual design. In clock and data recovery circuits (CDRs) it is necessary to integrate the amount of “ups” and “downs” a phase detector outputs (if this tells you nothing, please hold on till the CDR post I am planning). Basically, you receive two vectors of a given length, one represents “ups” the other “downs”. You have to sum up the amount of “1″s in each vector and subtract one from the other. Summing up the amount of “1″s is done using this full-adder arrangement. Another way would be using a LUT (posts on LUTs are planned as well…).

Puzzle #1 - Solution

The key observation to the solution of this puzzle is to note that the outputs of components can be connected together given than only one drives a non high-Z value. If you realized that 90% of the way to solving this puzzle is behind you.

The second step is to realize a “NOT” gate using both the “X” and “Y” components. When you know how to do that an “OR” and an “AND” gate realization are quite simple.
The figure below sums up the construction of “NOT”, “OR” and “AND gates from various instances of “X” and “Y”.

The next step is quite straightforward. We combine the gates we constructed and make an “XOR” gate as follows:

This is by no means the most efficient solution in terms of minimum “X” and “Y” components.