Divide by 1.5 Counter

This is one of the favourite questions asked in interviews. One of the best answers I found was in Xilinx’s Xcell magazine by one of my favorite authors, Peter Alfke. Check out his article called “Unusual Dividers” on page 30.
http://www.xilinx.com/publications/archives/xcell/Xcell33.pdf

This blog post is devoted to him. He died yesterday. Peter’s greatest talent was not simply that he was an FPGA expert but that he could communicate very technical content in a very practical and concise way.

“He was very proud that he came from a long line of educators,” said Carter. “His ability to take complex ideas and communicate them very clearly was really quite remarkable, especially when you realize that English was his second language. He liked to share his wisdom and never did it in arrogant manner. He was a fabulous diplomat, very approachable, very welcoming…a true gentleman.”

At lunchtime at Xilinx, Peter always drew a crowd of admiring friends to his table and there was always room for more. It was not uncommon to find 10 or more people sitting at a table built for 4 listening to Peter’s advice and sharing stories about all things under the sun.

Alfke is survived by his wife, son and daughter and two grandchildren. He was 79.

Read EETimes article , blog entry and EETimes news article for more details.

The first known FIFO implemented in electronics was done by Peter Alfke in 1969 at Fairchild Semiconductors. More details
Here is link to his patent on FIFO.
First-in, first-out buffer system in an integrated circuit

The articles I read - 2: Moving data across asynchronous clock boundaries

What strategy best addresses a situation where parallel data must pass across a clock domain boundary? The traditional method is to generate a flag and to use a handshake sequence.

When the transmitter has parallel data ready for transfer,it creates a rising edge on the READY line, which in turn sets flag F telling the receiver that data is available. The receiver scans F continuously and, after finding it high, accepts the stable parallel data and then creates a rising edge of ACK, which sets flip-flop A. This resets F, which in turn resets A. This particular design makes no assumptions about any phase or frequency relationship between the transmit and receive clocks. Such generality dictates a design using a benign
controlled race condition between the two flip-flops. A reasonable loop delay can conveniently be inserted between F and the reset of A. In a less generic design, this delay might be implemented as one period of either the transmit or receive clock.

This traditional handshake requires both sides to poll the flag F. The transmitter must change parallel data only when F is low, and the receiver must accept data only when F is high. This requirement results in a safe but slow data transfer. However, speedier ways to transfer data across an asynchronous clock boundary exist.

Peter Alfke's article was originally published in Integrated System Design magazine in 2000. A pdf of this article is available here. An html version of original article is archived here.

Interview Question 16: Fibonacci number generator

Design a hardware block to generate Fibonacci numbers.
You have freedom to decide the architecture of this block.


In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence:



or, alternatively,



By definition, the first two numbers in the Fibonacci sequence are 0 and 1 (alternatively, 1 and 1), and each subsequent number is the sum of the previous two.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation


with seed values

Interview Question 15: Create a compact data structure

A tree based data structure of distribution of post offices in a county is shown above. 
- How do you store this data structure efficiently in a memory?
- Create a hardware (algorithm based) to find out whether given post office exists. For example if input to design is PO21 the module should traverse the data structure and show whether it exists or not.

Interview Question 14: Continuous Memory Read Writes

This is a high performance design question. Create a block which is an event counter as shown below. 

This module is implemented using a single port memory as it has large number (millions) of counters. Every clock a valid signal indicates an increment or decrement operation of a counter indicated by an address. This block also produces output of the selected counter after a fixed latency.

Essentially you need to design a “Read-Modify-Write” operation. Assume that the chosen memory requires 2 clocks to complete the write and 2 clocks to read the data. The command and address combination can happen in any sequence. For example you may receive increment/decrement command for the same address on 10 consecutive clock cycles.

Interview Question 13: Random Number Generation

Random numbers are needed in verification to exercise various corner cases in a test benches. Every test bench is unique. Every test scenario calls for the different kinds of random number generation. Here are two common scenarios encountered in verification. The later question helps is constrained random verification.

- Create a function (or task / module) to generate 256 “unique” random numbers.
  The generated number is unsigned 8 bit number. A simple $random call may generate repeated numbers. Your task is to create a function which guarantees unique numbers in first set of 256 numbers. The next batch may repeat the whole set.

- Design a module which generates weighted random (pseudo random) numbers. Instead of generating unique numbers this time your task is to generate a small set of numbers randomly distributed but with agreed weight-age  Out of all 100 numbers generated the distribution of numbers should be as follows.

Numbers	Distribution
0	5%
7	20%
35	25%
145	30%
244	20%
Total	100%

Interview Question 12: Design a Garage door opener

Just like the previous question this one also deals with finding out a person's problem solving approach. 

A garage door opener is a controller which responds to multiple switch/sensor inputs and produces output for a motor to pull garage door up or down or stop in the middle. 

Half the fun in solving this design problem is in understanding the functionality and creating a list of conditions/specifications.

Interview Question 11: Design a beverage dispenser machine

This is a common question in many interviews for design positions. The expected answers vary based on experience of the person. A fresh college graduate may focus on just a state machine diagram design. An experienced person's answer will be very different. State machine diagram is just a small part of it. In any case this open ended question tests how a person thinks and approaches problem solving.