Basic Combinational Building Blocks

The circuits in the project requirements are described in a structural way, but the the code will be written as behavioral.

Exercise 80

The circuit must be in structural form before the FPGA can be configured, but the circuit is mostly described in behavioral manner. How is the process called in which behavioral description is converted to structural?

Solution to Exercise 80

Logic synthesis

Learning Goals

• Understand the design and use of multiplexers, decoders, encoders, shifters

Background

Multiplexers

Source

The word comes from multi and plex. Multi means many and plex means weaved or twined. A multiplexer takes many (multi) inputs and combines them (plex) into a single signal.

In our context the multiplexer does not necessarily combines all inputs all the time similar to a serializer, but selects one of them dependent on the select inputs. It can work like a serializer though if we would select the input signals one after another.

Multiplexers are also called:

• mux

• data selector

Exercise 81

1. What does a multiplexer in the context of digital electronics do?

2. Which interface signals does a multiplexer have?

Solution to Exercise 81

1. A multiplexer routes one of the many input signals to its output.

2. It has many inputs, select inputs for selecting one of the input signals for routing to the output, and an output.

Exercise 82

Why does a multiplexer have \(\log_2 N\) select input signals where \(N\) is the number of input signals?

Solution to Exercise 82

To address \(N\) signals in binary we need at least \(\lceil \log_2 \rceil\) bits. For each bit we have one signal.

Exercise 83

What does a 16:1 mux mean?

Solution to Exercise 83

16 input to 1 output multiplexer.

Exercise 84

We introduced K-maps with entered variables before. How are these useful for describing the behavior of multiplexers?

Solution to Exercise 84

Imagine that you are describing a multiplexer with four inputs and two select inputs. Then the truth table would have six input signals which is not easy to describe (and minimize) using standard K-maps. Using entered variables we can describe them much easier as each combination of the select inputs signals corresponds to the forwarding of one input signal.

For an example, look at the tables in digital multiplexers – Wikipedia

Warning

The author writes

An N-input mux is a simple SOP circuit constructed from N AND gates each with log2N+1 …

It is actually \(\log_2 N +1\)

Exercise 85

Which and how many gates do we need for a multiplexer with 16 inputs and 4 select inputs?

Solution to Exercise 85

In SOP form we have a product for each input. Each product consists of the select inputs and an input signal. So we have

• 16 product terms with 4 select input variables and one output. Total: 16 AND gates with five inputs each

• 1 OR with 16 inputs.

Exercise 86

Assume that you have only 4:1 muxes. How many of these would you need to multiplex eight signals which are four bytes each?

Solution to Exercise 86

1. Using a 4:1 mux we can only multiplex 1 bit signals. To multiplex four byte = 32 bit signals, we need 32 of them.

2. We can now select between four signals. We need two sets of above to select between eight signals.

3. We need additional gates to control the select inputs, e.g., a binary decoder.

Total: 64

Exercise 87

What is an application of multiplexers in computers?

Solution to Exercise 87

1. A multiplexer can be used to select a byte from an byte array. For example, imagine a random-access memory with 128 bytes. We can select a byte using 7 select input signals.

2. Different components of a computer are typically connected to each other using a bus. A multiplexer can be used to give access to a single component only.

Binary Decoders, Demultiplexers

Binary Decoders

Exercise 88

What does a binary decoder do? Give an example.

Solution to Exercise 88

A binary decoder takes a binary encoded signal with \(n\) bits and decodes it to \(2^n\) bit signals.

For example a 3:8 (3 inputs to 8 outputs) binary decoder with three inputs could output an eight bit signal where the one of the output bits is set dependent on the decoded number: 000 to 0000_0001, 001 to 0000_0010, etc.

If only one of the bits is 1 in a group of bits, then this group is called one-hot

Exercise 89

Where can decoders be used in computing?

Solution to Exercise 89

We can select an item from an array, e.g., a byte or a component as we described in Exercise 87 using an address.

Exercise 90

How can we describe a decoder using a K-map?

Solution to Exercise 90

Similar to Exercise 84. Instead of forwarding a single input signal in multiplexer we forward a specific data word. Each word for each input combination would be entered into the corresponding cell.

Demultiplexers

Exercise 91

1. What does a demultiplexer in the context of digital electronics do?

2. Which interface signals does a demultiplexer have?

Solution to Exercise 91

A demultiplexer does the opposite of a multiplexer (Exercise 81). It has one signal output, many select inputs and many signal outputs. It forwards the input signal to one of the outputs.

Exercise 92

How can we build a demultiplexer using a binary decoder?

Solution to Exercise 92

If we take a binary decoder with enable, then the enable signal acts like a one bit input. If the enable is active, then typically 1 will be forwarded to one of the outputs and if not active, then each output will be 0.

Priority Encoders

Exercise 93

1. What is an encoder in the context of digital electronics?

2. What is the difference between an encoder and priority encoder?

3. Which interface signals does a priority encoder have?

Solution to Exercise 93

1. An encoder maps a one-hot input data to a binary encoded word. In other words an encoder compresses a wide input to a narrow output.

2. In an encoder the input must be one-hot, but a priority encoder also permits multiple 1s in the input bits by prioritizing inputs. For example, if second and fourth input bits of an eight bit priority encoder are set, then the decoder may output 001 (signal for the second bit) instead of 003 (signal for the fourth bit).

3. \(n\) input signals, \(\log_2 n\) output signals, an optional enable signal.

Exercise 94

Why does a priority encoder exist but not a priority decoder?

Solution to Exercise 94

A decoder maps \(n\) inputs to \(2^n\) outputs. This function is injective, but cannot be surjective. Consequently we will get definitely a designated output from every combination of inputs.

An encoder maps \(2^n\) inputs to \(n\) outputs, so the function cannot be injective. We must also consider the cases when multiple bits are set in the input (unmapped inputs). A priority encoder solves this by prioritizing.

Exercise 95

How can we describe a priority decoder using a K-map?

Solution to Exercise 95

If the input bit with the highest priority is 1, then the other inputs are don't care and the output is the binary encoded value. If the input with the second highest priority is 1, then the bit with the highest priority must be 0 and others must be don't care etc.

Shifters

Exercise 96

1. What does a shifter in the context of digital electronics do?

2. Which interface signals does a shifter have?

Solution to Exercise 96

1. A shifter shifts the bits in a group of bits to left or to the right. The vacated bits can be filled with 0, 1 or with the most- or least-significant bits in case of rotation.

2. Inputs that encode shift count (i.e., how many bits to shift), the data input/output, a direction signal, rotation enable bit, a fill bit (if rotation not enabled).

Exercise 97

How does a truth table for a four input shifter with enable and without a fill bit look like?

Solution to Exercise 97

Exercise 98

Where are shifters used?

Solution to Exercise 98

1. For binary multiplication and division

2. To move bits to a new location on the data bus. For example, if a 32 bit data bus is narrowed down to a 16 bit data bus.

Tutorial: Multiplexer, Shifter, Encoder, Decoder

Exercise 99

How can we describe a 4:1 multiplexer in Systemverilog?

Solution to Exercise 99

Array select signals are useful:

multiplexer_4to1.sv

module multiplexer_4to1 (
    input [3:0] i,
    input [1:0] sel,
    output o
);
assign o = i[sel];
endmodule;

Exercise 100

1. Describe a shifter with:

   • eight bit input

   • direction select

   • two bit shift count.

2. Add a fill bit input to the shifter above.

Solution to Exercise 100

shifter.sv

module shifter (
    input byte i, [1:0] shift_count,
    input dir,
    output byte o
);
assign
o = dir ? 
    i<<shift_count :
    i>>shift_count;
// Vivado seems to parse above statement as a procedural statement and error
// out. Procedural statements must typically be in an always block as follows:
// always_comb
//   o = dir ? ...
endmodule;

shifter_with_fill_bit.sv

module shifter_with_fill_bit (
    input byte i, [1:0] shift_count,
    input dir, fill_bit,
    output byte o
);
// We cannot replicate a bit dynamically like {n{fill_bit}} as follows:
// {(i<<shift_count)[7:shift_count], {shift_count{fill_bit}}}
// So we have to describe our logic procedurally.
always_comb begin
    byte shifted_tmp = i;
    for (int j=0; j<shift_count; ++j) begin
        shifted_tmp = dir ?
            {shifted_tmp[6:0], fill_bit} :
            {fill_bit, shifted_tmp[7:1]};
    end
    o = shifted_tmp;
end
endmodule;

Requirements

1. Multiplexer

Warning

You must also simulate the circuit.

In next weeks the circuits will become more complex and debugging your circuit using simulation can

1. save you the time for synthesis

2. give you a better insight to the internal signals

So getting to grips with simulation right now can be beneficial.

2. Decoder

3. Encoder

A priority encoder is required. A priority decoder can be implemented with if ... else statements that check the conditions in sequence and thus prioritize the first conditions when deciding what to output.

Can it also be implemented using a case statement? Does case check the conditions in sequence or in parallel? Instead of doing an internet search we can look to the standard document for Verilog which acts like the law book for the syntax and resulting semantics. It is also called language reference manual.

IEEE Standard for SystemVerilog–Unified Hardware Design, Specification, and Verification Language

The standard is not free, but you can very likely download it using the subscription of your university or company.

case statement is explained in chapter 12.5:

… The case_item_expressions shall be evaluated and then compared in the exact order in which they appear. … During the linear search, if one of the case_item_expressions matches the case_expression, then the statement associated with that case_item shall be executed, and the linear search shall terminate. …

We can read that the case statement should behave like an if ... else and thus like a priority encoder.

What if we wanted to check in parallel? For example if we want to implement a multiplexer? For that the Verilog supplies unique case`:

… unique-case … assert(s) that there are no overlapping case_items and hence that it is safe for the case_items to be evaluated in parallel. …

… The case_item_expressions may be evaluated in any order and compared in any order …

… By specifying unique or priority, it is not necessary to code a default case to trap unexpected case values. …

So if we want to be more explicit, then we would use unique case statement for a multiplexer.

4. Shifter