1. Imagine an endless incoming bit stream, divided into frames of a fixed length (for example, 128 bits) with a fixed beginning pattern (for example, 11101000). 3 consecutive appearances of this pattern (one per frame) should be found to declare in-frame.
2. Move data from one array 128x128 to another 128x128 array so that any starting offset and any length with granularity of 8 bits is allowed at the input array, while the output array is filled starting from offset 0.
3. There is a memory with read delay of 3 cycles. Its output data is saved into 2-deep FIFO. Then it is read from the FIFO:
-
Design logic for memory read enable;
-
Design logic for FIFO push;
-
What should be the FIFO depth to eliminate memory read gaps and provide 100% throughput?
4. Design FIFO control.
5. Design ASYNC FIFO control.
6. There given a memory with read delay 2. The data output is 128b wide. There is a logic which reads the memory output and generates the output of 64b. The data is sent to the entity which informs the logic about its readiness to accept the data. The data is considered accepted by it when both “vld” is asserted by the block and “ready” is asserted by the entity.
Design read enable to memory. Make the logic as effective as possible.
7. Imagine the following sequence of 24 2-bit pairs, which is received by the designed module: 00;00;00;00;00;00;01;01;01;01;01;01;10;10;10;10;10;10;11;11;11;11;11;11. The sequence constitutes the framing pattern of the respective data frame. It is needed to permanently designate the start of the sequence (the transition from 11 to 00) with the algorithm which will be single bit tolerant (one error per sequence is allowed) and will be able to find the synchronization fast.
8. Given an input of 32b data with valid. Design a circuit which will take 16msb of data on each even valid, take 16lsb of data on each odd valid, concatenate them and synchronize to clock domain with frequency 4 times faster than the source one. What is the maximum rate of the input the circuit can sustain?
9. There are 2 synchronous clocks. Design a circuit to generate out signal as in below clock diagram.
10. There is a circular wheel with a half painted white and the other half painted black. There are 2 censors located at 45 degree apart at the surface of the wheel which are asserted for black and de-asserted for white passing above them. Design a circuit to detect the wheel rotation direction in asynchronous and synchronous variants.
11. Let’s assume a DSP-like logic depicted below.
It has an input of 32b, 4 sequential stages of storage of previous value and 4 different logical functions attached to the outputs of the storages. The output of the system is the vector of these functions taken at each clock. The system is being upgraded to 64b input so that 2 consequent values of the previous system are now applied in 1 clock. Design the new system. Obviously, the output needs to be the same.
12. Design a black box that receives a signal input (pulse) and multiplies its duration by loaded value to make it suitable for synchronization to the clock which is guaranteed to be faster than extended value of the pulse.
13. Frequency divider by 3 with 50% duty cycle.
14. Imagine two blocks (receive and transmit), participating in receive and transmit data paths of a framed 8b data, while frame size is many cycles of data. A transfer of an 8b data from the pre-defined location in the frame with valid indication from Rx block to Tx block once per frame is needed. Tx block puts this 8b data once per frame in a pre-defined location in the frame. The Rx and Tx blocks work with different clock sources at the same rate. The Rx and Tx frames are of the same size. The questions are why and how to synchronize the data transfer, what other problems can occur if the clock rates slightly differ.
15. A system has 2 registers and ALU. The ALU can perform any operation on the content of these two registers and place the result in one of them. How to swap their content using only operations on these two registers?
16. To enter the office, people pass through the corridor. Once someone gets into the office the light should switch on. It goes off when the room is empty. There are two registration sensors in the corridor. Design a circuit to control the light.
17. Design a circuit with infinite 1-bit stream at the input and the same bit stream at the output delayed by 1 second. The bit rate is 1Mbit/s.
18. There is an infinite bit stream. Design the logic, which will indicate if the bits already received comprise the number, which is divided by 5. Every time least significant bit is received.
19. Similar problem to question 18 but need to detect division by 3 and with most significant bit received each time.
20. Imagine a data bus where 16 devices concur on it. There is a common “start” signal, received by all the devices and starting the distributed algorithm in all the devices to define which of them will master the bus. There is one-bit “ready” output in each device. Design algorithm to access the bus.
21. Similar problem to question 20 but without start signal with round-robin arbitration.
22. There is wine in one glass and water in the other. They take a spoon of wine from the first glass and move it to the second with the water. Second time they take a spoon from the second glass and move it to the first glass. Now what concentration is larger: the water in the wine glass or the wine in the water glass?
23. There is a closed shape, each pixel of which is defined in the memory of display. Design algorithm, which will define in or out of the closed shape the randomly chosen dot is located.
24. There is a FIFO which clocks data in at 100 MHz and clocks the same width data out at 60 MHz. At the input only 60 clocks out of each 100 ones carry data. The order of the data cycles and the idle cycles is fully random. How big should be the FIFO to avoid data overflow?
25. Imagine a system like the one shown below. The system receives data at “in” port no frequently than once every three cycles and stores it in the internal FIFO. Each FIFO entry causes a request to external entity. When reply is received, an entry from the FIFO which had caused this reply is read, a calculation based on it and reply is produced and an output is generated. The replies are in order of requests. The number of the requests asserted before first reply is received is restricted to 64. Design the system conceptually.
26. There is input stream which represents an array of 1000x1000 pixels, while each pixel is represented by 8b. The frame is divided into squares 4x4 pixels each. Output should be the average of each “square” of 4x4 pixels. Design the system.
27. There is block with write and read port of the same width (e.g. 128b). Both provide access to a single port SRAM in the block. The ports are asynchronous, i.e. there can be simultaneous writes and reads. There can be bursts of simultaneous writes and reads. Design the circuit.
28. There is a block with array storage in it of 32*32 cells, each of which stores pixel of 8b.
Each cycle one pixel, related to cell in row ‘i’, column ‘j’ in the array is driven to input and is applied as a first input to a function, which second input is the current value in the array. Then the result of the function is written back into the cell as a new value of the cell. It is also sent to the output. Each cycle one cell after another is processed in consequential manner. Design the circuit.
29. There is a block with an input of 32b data. The input data is pushed into the FIFO and the popped data is output from the block after processing. Calculate the FIFO depth, ask all the relevant questions. Resolve for two cases, when there is one input and ‘N’ inputs participating in inputs arbitration.
30. There is a module with 2 inputs and 2 outputs: a) max – output the maximum of 2 inputs b) min – output the minimum of 2 inputs. Using these modules, build a logic to sort 3 inputs.
31. Design frequency divider by 3/2, e.g convert clock 50MHz to 33.33MHz.
32. You have only 4 following assembly commands:
-
Inc R //increments the value of register
-
Dec R //decrements the value of register
-
Jnz LABEL //jump to label in case latest operation Z flag is 0 (result is not 0)
You have all the processor registers available. Implement C = A*B.
33. Design a read-ahead FIFO, the FIFO which utilizes big SRAM memory with read latency of (N+1) cycles. The read-ahead FIFO needs to provide read latency of 0 cycles. Try to provide minimal input-to-output latency. Present just the conceptual solution, there is no single “correct” answer.
34. Design conceptually recreational laser rifles system. It needs to give ability for groups of people to participate in role plays one against another, groups against groups according to different scenarios and to keep track of winners, losers and their scores.
35. There is following waveform. What logic circuit generates such a waveform for output “out”?
36. Previous question continued. What logic circuit generates such a waveform for output “out2”?
37. There is a system with N inputs. Packets of data are flowing through these inputs to a common memory 128b*1K(entry), while each packet may contain from 64B to 1KB. The width of the input is 128b. Design memory controller such that the packets of data will be put in it in order per packet. Try to provide high memory utilization.
38. A pulse is passed from one clock domain to another. The frequencies are the same, but clock sources are different. Design the synchronization scheme and define source signal constraints if needed.
39. What are good design principles related to XXes?
40. What problems may arise due to clock skew and how to solve them?
41. Provide simple implementation of rotate shifter in Verilog (or pseudo-code). RotateShifter(shift,R[N-1:0])={R[N-shift-1:0],R[N-1:N-shift]}. E.g., shift left for 3 of register R[7:0] should provide {R[4:0],R[7:5]}.
42. Provide design of strict priority encoder for N inputs. It should:
-
Provide an output which is one-hot with the single set bit, which is the ls set bit in the input.
-
Provide an output, which is the index of ls set bit in the input.
43. Design the scan chain and scan sequence to test msb of 32b counter.
44. Design half hand-shake synchronization scheme.
45. Design re-order FIFO. It should push according to write pointer into any randomly accessed location but read as normal FIFO – one entry after another.
46. Design a squeezer – the logic which squeezes all the valids from the input vector of size N with associated data vector of size N*M to lsb of the output. E.g. input valid vector {1101} should produce output {0111} and associated data vector {0x1,0x3,0xA,0xC} should produce output {0x0,0x1,0x3,0xC}.
47. Design a free list controller – the logic which allocates indexes in the scope of 0..2n-1. The indexes are consequent, but their allocation needs not be consequent. The allocated index is extracted from free list. After being used by external entity the index is returned to free list. No assumption should be made regarding any order of allocation-return.
48. Design PWM (pulse width modulation).
49. Design an LRU (least recently used) cache eviction control logic for a set containing N blocks.
50. Imagine a collection of clients who read data from common data memory. A block of data per client in memory may spread along several memory addresses. Providing round-robin access of clients to memory, i.e. client N accesses memory in cycle i, client N+1 access memory in cycle i+1, so forth is considered to be of poor performance due to overall system configuration. Of better performance is to allow for a client to continuously access the memory for duration of pre-defined number of cycles. Design such an access.
51. Design an adder of 2 digits of width N from incrementors of width N.
52. There are 2 blocks, master and slave, which interact according to defined protocol. Master sends the data to slave validated by a pulse. Slave eventually responds with acknowledge. The next cycle after acknowledge is received by the master, it can assert a new valid to the slave.
Second master is added to the system. Design the adapter which will be located between masters and slave and will retain the interface and communication protocol of both.
53. Design the logic, which will react with a signal with duration of 3 destination clocks to one pulse of source clock.
54. There is a block which receives 8b data in one clock and another 8b data in another clock. The data in both inputs is framed, i.e. it includes "marker" Byte, which indicates start of frame. It is guaranteed the relative distance between two markers is small - some cycles. The length of the frame is the same for both inputs. Design a logic which will output concatenation of these two inputs on the output clock. The output makes sense only after both data streams have meaningful data, i.e. after markers. The data of the inputs need to be mutually synchronized, i.e. the first Byte after marker in data0 together with first Byte after marker in data1, so forth. All three clocks (two inputs, one output) are the same frequency but come from different sources.
55. Design dual-port RAM out of single-port RAM.
56. We want to design a game. There are 2 players. There is a playground, which constitutes a square with a side of N cells, i.e. N*N square. Each cell is numbered from 1 to N2. The aim of the game to reach first the cell N2.
The game process: both players start in cell number 1. Each player in turn chooses the number of steps to take on the playground, while the number of possible steps is from 0 to N2. There are two type of additional elements spread over the playground – ladders and ropes.
-
Ladders – when the player reaches the cell in the bottom of the ladder he rises to the cell in its up;
-
Ropes - when the player reaches the cell in the up of the rope he slides to the cell in its bottom;
Each cell may contain only one element. The last cell isn’t connected to any element. The playground topology isn’t known to the players.
Please, implement the game with Moore FSM. It has one input “ln” through which each player in turn enters the number of steps to take. It has two outputs “out1” and “out2”, which represent the corresponding location of the players. Additionally, if player 1 wins the FSM outputs “out1=W, out2=L”, if player 2 wins the FSM outputs “out1=L, out2=W”.
The questions:
-
How many states will be in FSM without ladders and ropes?
-
How many states will be in FSM with L ladders and R ropes?
-
If added the possibility to go back, what will change in the FSM?
57. There is SPI protocol. It is serial bi-directional protocol with 3 one-bit ports (clock, data in, data out), while the data unit is 1 Byte. Design the interface. Design it with as little resources as you can.
58. A question from the world of the video processing. We have a square frame with side of N pixels, while each pixel is represented by a Byte. Each cycle a pixel of data is sent to a block which processes this frame. The ports of the block are presented in the drawing below.
-
sof – start of frame;
-
sl – start of line;
-
el – end of line;
-
eof – end of frame;
The block needs to output for each pixel a maximum between the pixels which constitute a square of 5*5 with this pixel in the center.
59. What are the principles of Design for synthesis?
60. What are the principles of Code readability?
61. Implement UART interface. The emphasis on how to sample the received data without passed clock.
62. We have 2 registers and a logic between them. Second flip-flop has Ts=3.5ns and Th=0.5ns. The signal at this flip-flop set 3ns before the rising edge and is hold for 2ns after rising edge. What are the possible problems, how may they be resolved and what are the considerations?
63. We have a send block which sends request pulses to transmit block. For each request the transmit block sends back the response. The responses are in order, but the response time is not constant. Its upper limit is 100 clocks. Design the logic to calculate the response time Tr for each request.
64. Design a FIFO based on single-port RAM.
65. Tell about bug you've solved. Tell about synthesis (timing) problem you've solved.
66. The most difficult challenge you'd encountered during any block design.
67. Two 8b wide multi-cycle data flows enter a block so that they aren't overlapped, i.e. there can't be simultaneous data valid signals for both. Valid come by two separate signals, while 8b data is shared.
The flow comprises a pre-defined message where the first data carries the size of the message and all the rest carry payload. Design the system, which will output these 2 data flows separately on two output ports together with "start of message" indication. Messages need to be output in the order of their appearance at the input (more strictly in the order of their first data (header) appearance).
68. The king of the questions: tell about block you’ve designed.
69. What are your 4 main characteristics?
70. What will your manager tell about you?
71. What will your manager tell you need to improve?
72. Why do you leave? Why do you leave now? What will your colleagues say when they know you are leaving?
73. There is a wheel with sensor which produces a periodic clock-like wave of frequency proportional to the speed of wheel rotation. Design the circuit to determine whether the speed is “slow” or “fast”.
74. Based on the previous question. There are two such wheels rotating with same speed but not in phase. Their two sensors produce two periodic waves. Design the circuit to determine what wheel is preceding and what is following.
75. Design glitch-free (glitchless) clock mux. Already answered at https://www.eetimes.com/techniques-to-make-clock-switching-glitch-free/ and https://vlsiuniverse.blogspot.com/2017/03/clock-multiplexer.html.
76. There is a processor and a memory to which it can access to read and write data. The data can be 8, 16 and 32b. ECC protection is applied to data. Design the system.
77. There are N data flows in the system, while the flow is the stream of messages pertaining to this flow. The block aggregates messages per flow for M flows. M is much less than N. The following functions are supported:
-
Add flow: when message pertaining to the flow which isn’t yet on block appears and there is enough storage space (number of already maintained flows on block is less than M), then add flow;
-
Shift flow: when message pertaining to the flow which isn’t yet on block appears and there is no storage space (number of already maintained flows on block is equal M), then perform finalizing actions for LRU (least recently used) flow, drop it and add new flow;
-
Use flow: when message pertaining to the flow which is already on block appears and the flow can be finalized (due to a certain number of messages aggregated until now), then perform finalizing actions for it and drop it;
Each command is equipped with flow ID, designating the new flow in case of add and shift and the existing flow in case of use.
Design only the mechanism for maintaining the order between flow, i.e. the mechanism to determine the LRU.
78. The advanced variant of the previous question – don’t separate add and shift flow. The interviewee needs to come up with the idea of dropping the LRU flow when flows ordering mechanism is full.
79. Propose bus encoding schemes to reduce dynamic power consumption on bus.
80. Design Linked List with 0 latency (based on FF). Provide only needed resources, no need to define the logic.