Basic Combinational Building Blocks
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.
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?
Understand the design and use of multiplexers, decoders, encoders, shifters
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:
What does a multiplexer in the context of digital electronics do?
Which interface signals does a multiplexer have?
Solution to Exercise 81
A multiplexer routes one of the many input signals to its output.
It has many inputs, select inputs for selecting one of the input signals for routing to the output, and an output.
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.
What does a 16:1 mux mean?
Solution to Exercise 83
16 input to 1 output multiplexer.
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
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\)
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
ANDgates with five inputs each
ORwith 16 inputs.
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
Using a 4:1 mux we can only multiplex 1 bit signals. To multiplex four byte = 32 bit signals, we need 32 of them.
We can now select between four signals. We need two sets of above to select between eight signals.
We need additional gates to control the select inputs, e.g., a binary decoder.
What is an application of multiplexers in computers?
Solution to Exercise 87
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.
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#
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
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.
How can we describe a decoder using a K-map?
What does a demultiplexer in the context of digital electronics do?
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.
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
What is an encoder in the context of digital electronics?
What is the difference between an encoder and priority encoder?
Which interface signals does a priority encoder have?
Solution to Exercise 93
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.
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).
\(n\) input signals, \(\log_2 n\) output signals, an optional enable signal.
Why does a priority encoder exist but not a priority decoder?
Solution to Exercise 94
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.
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.
What does a shifter in the context of digital electronics do?
Which interface signals does a shifter have?
Solution to Exercise 96
A shifter shifts the bits in a group of bits to left or to the right. The vacated bits can be filled with
1or with the most- or least-significant bits in case of rotation.
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).
How does a truth table for a four input shifter with enable and without a fill bit look like?
Solution to Exercise 97
Where are shifters used?
Solution to Exercise 98
For binary multiplication and division
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#
You must also simulate the circuit.
In next weeks the circuits will become more complex and debugging your circuit using simulation can
save you the time for synthesis
give you a better insight to the internal signals
So getting to grips with simulation right now can be beneficial.
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.
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:
case_item_expressionsshall be evaluated and then compared in the exact order in which they appear. … During the linear search, if one of the
case_item_expressionsmatches the case_expression, then the statement associated with that
case_itemshall 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… 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.