Problems





Problems

1.

A one-ho multiplexor requires that the signals at its select lines be one-hot. If a selection is not one-hot, the output depends on the specific implementation of the multiplexor. In this exercise, let's assume that if a selection is not one-hot, the input corresponding to the most significant nonzero select bit becomes the output. For instance, in a 4:1 multiplexor, inputs are labeled as 1, 2, 3, and 4. If selection is 0100, then input 2 is connected to the output. If selection is 0101, input 2 is also the output, as a result of this implementation. Consider the circuit in Figure. Suppose the select signal S of the shaded multiplexor is not one-hot as a result of a design error. For example, to select input 3, S has value 0011, a binary number, instead of 0100.

  1. Define error detection latency (EDL) to be the number of cycles that must have passed before an error is observed during verification. When is the minimum EDL for this error seen at the output? What is the maximum EDL?

  2. How can you improve the EDL of this error by adding an assertion so that both the minimum and the maximum EDLs are equal to zero?

27. Bug detection latency in a one-hot multiplexor circuit


2.

In this problem, let's consider a grayscale JPEG image processor. First, an image is partitioned into blocks of 8 x 8 pixels. Then each block is transformed and quantized separately. Finally, the code of the blocks is encoded and compressed to produce JPEG code. A JPEG processing system consists of three major components: a discrete cosine transform (DCT), a quantizer, and an encoder (FigureA). The DCT components take an 8 x 8 patch of image and compute its two-dimensional DCT. The result, a vector of 64 real coefficients, is then quantized to the bit capacity of the processor. The code from the blocks is then encoded and compressed in the zigzag diagonal order shown in FigureB. For example, a 1280 x 1024 image has 160 x 128 (or 20,480) blocks, each of which is a vector of 64 numbers, for a total of 1,310,720 numbers. During the encoding and compression stage, consecutive zeros are encoded with run length encoding (for example, seven consecutive zeros is written as 07). The rest is encoded with Hoffman coding, which assigns the shortest codes to the most occurring patterns subject to the so-called prefix constraint. Of the three components, only the quantizer is lossy, meaning output information content is reduced. Assume that we want to verify this JPEG processor hierarchically. Determine which of the specifications belong to the JPEG system or its components.

  1. The total picture quality must achieve at least 99.5% fidelity.

  2. The average file size of a 1280 x 1024 image is 1MB.

  3. Processing time for a 1280 x 1024 image is less than 10 msec.

28. (A) JPEG processing components (B) JPEG encoding order of blocks


3.

Using the state space approach, derive a test case in category 3, S S|, for the previous JPEG system. Then derive a test case that verifies an instance in each of the following categories: error handling (category 2), power-on test (category 5), and normal operation (category 4).

4.

Write a test plan for the previous JPEG system. Use the test cases from problem 3.

5.

To verify the JPEG processor, one can feed it random pixel values, compute the expected JPEG file contents, and compare the computed contents with those produced by the processor. For simplicity, let's apply this methodology to verifying the DCT component. We first generate random pixel values, perform DCT on the values, and compare the resulting coefficients with those from the DCT design. This is called self-checking, and all these computations are done in a C/C++ routine that is run concurrently with the simulation of the DCT design and communicate via a PLI interface.

  1. Write a C/C++ program that automatically generate blocks of 8x8 random values between 0 and 1024. For each block of the pixels, compute the DCT coefficients as shown here:


    where Ki is equals to if x equals 0, and Ki equal 1 if x > 0. P(x,y) is the value of the pixel at (x,y).

  2. Design an RTL module that computes DCT.

  3. Using PLIs, compare the DCT coefficients from (a) with those from (b) at the end of every block. Whenever a block is done, the next block of pixel values are retrieved from the program in (a).

6.

Write a Verilog assertion that the input signal to an encoder is one-hot whenever the encoder is enabled. The input signal can take on any value if the encoder is not active.

7.

Write a Verilog assertion that ensures the data written to a memory contain no unknown values.

8.

Write an assertion that at most one driver is driving the bus at any time.

9.

The Hamming distance between two vectors is the number of bits that differ. Write a Verilog assertion that enforces a Hamming distance of 2 between all states in a finite-state machine.

10.

Write a Verilog assertion that issues a warning when the time a device possesses a bus exceeds eight cycles.

11.

Write a Verilog assertion that a signal must change within a time window specified by two events, assuming the delimiting events do not align with the signal transitions.

12.

Write an assertion on a FIFO that issues a warning when it is full, and a push command is issued.

13.

Write an assertion that ensures the data written to a memory are not corrupted. That is, data read are identical to data written.

14.

Based on Figure, find a SystemVerilog sequence such that

  1. Waveform A satisfies

  2. Waveform B satisfies

  3. Both waveforms satisfy

29. Waveforms for SystemVerilog sequences


15.

In a PCI bus, a deasserted IRDY# means the bus is idle and an asserted GNT# means it has bus acquisition. If GNT# is asserted, the master asserts FRAME#, which is active low, to start the transaction immediately. Coincident with the FRAME# assertion, the initiator drives the starting address onto the address bus. One cycle later, IRDY#, which is active low, is asserted. Write a concurrent assertion to ensure that the temporal relationship among IRDY#, FRAME#, and GNT# is correct.

16.

For the waveforms shown in Figure, determine which of the following sequences are satisfied. If satisfied, specify the times when they are satisfied. Assume the current time is time 1.

  1. S1 = ##1 x2 ##[1:3] (x1 + ) ##2

  2. S2 = ##1 (x1x2)[*1:2] ##1 (x3) ##1 () ##1

  3. S3 = x4 ##[0,3] x3 ##1

  4. Can we have (S1 intersect S2)? Why?

  5. When is the finish time of first_match (S2) ?

  6. S3 |-> S1, excluding vacuously true case when S3 is false

  7. (x1 ##1 ) within S1

  8. S2 ended ##2 (x2 + x4)

30. Waveforms for evaluating sequences


17.

Write a SystemVerilog assertion for the property that vector S is always even parity and the Hamming distance among its feasible values is 2.

18.

Determine the statement, block, and path coverage of the following code after it is simulated for three clock ticks:

initial begin
   x = 0;
   y = 8'b101111;
   p = 8'b01111101;
   count = 1;
   shift = 1;
   mask = 8'b1111001;
end

always @(clock) begin
   x = y & p;
   repeat (5) begin
      if (x > 8) begin
         count = count + 1;
         x = shift >> 1;
      end
      else begin
         count = count - 2;
         x = x + 2;
      end
   end
   if ( x < 7 )
      step = count & mask;
   else
      step = count ^ mask ;
   @(clock)
   x = x + 2;
   @(clock)
       if (x < 8) begin
       y = x + 2;
       p = mask & y;
       step = count + 3;
   end
end

19.

Compute the expression coverage for the following expression in a run that has encountered these values for a,b, and c: (1,1,0), (0,0,1), (1,0,1), and (0,1,0).

((a ?  :c) ^ (a b +  ))

20.

In this exercise, let's consider a Huffman encoder. The Huffman algorithm uses variable-length code to encode and compress. It assigns code with lengths that are inversely proportional to the frequencies of the symbols (for example, the shortest code to the symbol with the highest occurring frequency). To code the sentence "finding all bugs is ideal," the frequencies of the letters are first determined, and they are space (4), i(4), l(3), n(2), d(2), g(2), a(2), s(2), f(1), b(1), and e(1). Then the two symbols with lowest frequencies are merged to form a new symbol with a frequency that is the sum of the two. Once merged, the two symbols are removed from the set and the new symbol takes their place. This process is repeated until only one symbol is left. Figure depicts the process on the example sentence. The numbers on the edges in the first two graphs denote the order in which the nodes are combined. In the last graph, the left edges are assigned 1s and the right edges are assigned 0s. Now the code for the letters are read off the paths from the root to the letters. For example, letter i is encoded as 110, f as 01110.

  1. Define the parameters for parameter coverage of a Huffman encoder. A good parameter affects the algorithm and hence affects its output. Give an example of a good and a bad parameter.

  2. Define the operational features for functional coverage of a Huffman encoder. An operational feature or functional feature is a property that must or must not hold if the algorithm operates correctly. (Hint: Consider relationships between sentence characteristics and coding properties, such as letter frequency and code length.)

31. Huffman encoding process



     Python   SQL   Java   php   Perl 
     game development   web development   internet   *nix   graphics   hardware 
     telecommunications   C++ 
     Flash   Active Directory   Windows