Logic Arrays

Like memory (bits cells organized into an 2-D array to store data), gates can be organized into regular arrays. If the connections are made programmable, the logic arrays can be configured to perform any function without the use having to connect wires in specific ways. Most logic arrays are also reconfigurable, allowing designs to be modified without replacing the hardware. Reconfigurability is valuable during development and is also useful in the field, because a system can be upgraded by simply downloading the new configuration.

This sections introduces two types of logic arrays:

1. Programmable logic arrays (PLAs): the older technology, perform only combinational logic functions.

2. Field programmable logic arrays (FPGAs): perform both combinational and sequential logic.

Programmable Logic Array

Programmble logic arrays (PLAs) implement two-level combinational logic in sum-of-products (SOP) form. PLAs are built from and AND array followed by an OR array, as shown in Figure 5.54.

The inputs (in true and complementary form) drive an AND array, which produces implicants, which in turn are ORed together to form the outputs. An MxNxP-bit PLA has M inputs, N implicants, and P outputs.

Figure 5.55 shows the dot notation for a 3x3x2-bit PLA performing functions $X=\bar A\bar BC+A\bar B\bar C$ and $Y=A\bar B$. Each row in the AND array forms an implicant. Dots in each row of the AND array indicate which literals comprise the implicant. The AND array in Figure 5.55 forms three implicants: $\bar A\bar BC,A\bar B\bar C$, and $A\bar B$. Dots in the OR array indicate which implicants are part of the output function.

Figure 5.56 shows how PLAs can be built using two-level logic. An alternative implementation is given later.

Simple programmable logic devices (SPLDs) are souped-up PLAs that add registers and various other features to the basic AND/OR planes. However, SPLDs and PLAs have largely been displaced by FPGAs, which are more felxible and efficient for building large systems.

Field Programmable Gate Array

A field programmable gate array (FPGA) is an array of reconfigurable gates. FPGAs are built as an array of configurable logic elements (LEs), also referred to as configurable logic blocks (CLBs). Each LE can be configured to perform combinational or sequential functions. Figure 5.57 shows a general block diagram of an FPGA.

The LEs are surrounded by input/output elements (IOEs) for interfacing with the outside world. The IOEs connected LE inputs and outputs to pins on the chip package. LEs can connect to other LEs and IOEs through programmable routing channels.

Two of the leading FPGA manufacturers are Intel (formerly Altera Corp.) and Xilinx, Inc. Figure 5.60 shows a single LE from Intel’s Cyclone IV FPGA, introduced in 2009. The key elements of the LE are a 4-input lookup table (LUT) and a 1-bit register. The LE also contains configurable multiplexers to route signals through the LE. The FPGA is configured by specifying the contents of the LUTs and the select signals for the multiplexers.

The underlying "technique" behind LUT is nothing but a multiplexer. The part has been illustrated in the memory part in DDCA as well.

Figure 5.60 Cyclone IV Logic Element (LE)

Each Cyclone IV LE has one 4-input LUT and one flip-flop. By loading the appropriate values into the LUT, it can be configured to perform any function of up to four variables. Configuring the FPGA also involves choosing the select signals that determine how the multiplexers route data through the LE and to neighboring LEs and IOEs. Altera groups 16 LEs together to create a logic array block (LAB) and provides local connections between LEs within the LAB.

In summary, each Cyclone IV LE can perform one combinational and/or registered function, which can involve up to four variables. Other brands of FPGAs are organized somewhat differently, but the same general principles apply. For example, Xilinx’s 7-series FPGAs use 6-input LUTs instead of 4-input LUTs.

For example, for a Cyclone IV LE, which has 4 inputs and 1 to select the mux for using the flip-flop or not, the total number of configurations available is $2^4+1=16+1=17$. (The flip-flop mux select bit is separate from the 4 input bits)

The designer configures an FPGA by first creating a schematic or HDL description of the design. The design is then synthesized onto the FPGA. The synthesis tool determines how the LUTs, multiplexers, and routing channels should be configured to perform the specified functions. This configuration information is then downloaded to the FPGA.

Example 5.8: Functions built using LEs

Explain how to configure one or more Cyclone IV LEs to perform the following functions: (a) $X=\bar A \bar BC+AB\bar C$ and $Y=A\bar B$ (b) Y = JKLMPQR. You may show interconnection between LEs as needed.

---

Sol: (a) Configure two LEs. One LUT computes X and the other LUT computes Y, as shown in Figure 5.61.

Figure 5.61 LE configuration for two functions of up to four inputs each

For the first LE, inputs data 1, data 2, and data 3 are A, B, and C, respectively (these connections are set by the routing channels). data 4 is a don’t care but must be tied to something, so it is tied to 0. For the second LE, inputs data 1 and data 2 are A and B, respectively; the other LUT inputs are don’t cares and are tied to 0. Configure the final multiplexers to select the combinational outputs from the LUTs to produce X and Y (not shown in Figure 5.61). In general, a single LE can compute any function of up to four input variables in this fashion.

(b) Configure the LUT of the first LE to compute X = JKLM and the LUT on the second LE to compute Y = XPQR. Configure the final multiplexers to select the combinational outputs X and Y from each LE. This configuration is shown in Figure 5.62.

Figure 5.62 LE configuration for one function of more than four inputs

Routing channels between LEs, indicated by the dashed blue lines, connect the output of LE 1 to the input of LE 2. In general, a group of LEs can compute functions of N input variables in this manner.

Example 5.9: More Logic Element Examples

How many Cyclone IV LEs are required to build each of the following circuits?

1. 4-input AND

2. 7-input XOR

3. Y = A(B + C + D + E) + $\bar A$(BCDE)

4. 12-bit shift register

5. 32-bit 2:1 multiplexer

6. 16-bit counter

---

Sol: The key is to remember that one LE has one LUT which can deal with any function up to 4 variables and a flip-flop.

1. 1: The LUT can perform any function of up to 4 inputs.

2. 2: The first LUT can compute a 4-input XOR. The second LUT can XOR that output with three more inputs.

3. 3: One LUT computes B + C + D + E, a function of 4 inputs. A second LUT computes BCDE, a different function of 4 inputs. A third LUT uses 3 inputs (these two outputs and A) to compute Y.

4. 12: A shift register contains one flip-flop per bit.

5. 32: A 2:1 multiplexer is a function of three inputs: S, D0, and D1, so it requires one LUT per bit.

Example 5.10 LE Delay

Alyssa P. Hacker is building a finite state machine that must run at 200MHz. She uses a Cyclone IV FPGA with the following specifications: tLE = 381 ps per LE, tsetup = 76 ps, and tpcq = 199 ps for all flip-flops. The wiring delay between LEs is 246 ps. Assume that the hold time for the flip-flops is 0. What is the maximum number of levels of LEs that her design can use between two registers?

---

Sol: Alyssa uses the Equation we have learn before to solve for the maximum propagation delay of the logic: $t_{pd}\le T_c-(t_{pcq}+t_{setup})$.

Thus, t_pd = 5 ns − (0.199 ns + 0.076 ns), so t_pd 4.725 ns. The delay of each LE plus wiring delay between LEs, t_LE+wire, is 381 ps + 246 ps = 627 ps. The maximum number of LEs, N, is N t_LE+wire ≤ 4.725 ns. Thus, N = 7.

The Big Picture

We have learned the digital design flow in both CG3207 and EE4218, now we can try to apply that on FPGA but with more details!

This flow transforms human-readable HDL code into the binary configuration that physically arranges the FPGA's Logic Elements (LEs) and routing.

1

Logic Synthesis

• Input: HDL Code (Verilog/SystemVerilog/VHDL).

• Action: Compiles code into a Gate-Level Netlist.

• Output: A generic circuit representation using ideal boolean gates (AND, OR, NOT) and registers. It is technology independent (does not yet know about LUTs or CLBs).

After that, technology mapping is done (in the convention of CG3207 and EE4218, technology mapping is part of Logic Synthesis)

• Action: Translates generic gates into the specific resources available on the target FPGA (e.g., Xilinx Artix-7 or Intel Cyclone IV).

• Details:

  • LUT Packing: Groups combinational logic (e.g., $A \cdot B + C$) into a single N-input LUT.

  • Register Packing: Pairs logic with Flip-Flops inside the same LE/CLB where possible.

• Output: A Mapped Netlist made of LEs, DSP slices, and RAM blocks, not generic gates.

2

Physical Design

1. Placement

   • Action: Determines the physical location of each logic block on the FPGA die.

   • Goal: Assigns specific (Row, Column) coordinates to every LE from the mapped netlist.

   • Optimization: Places connected LEs close together to minimize signal delay and meet timing constraints.

2. Routing

   • Action: Configures the programmable interconnects (wires) to connect the placed LEs.

   • Mechanism: Selects paths through Switch Matrices (programmable intersections) to create electrical connections between inputs and outputs.

   • Output: A fully routed design. This is often the most time-consuming step due to congestion management.

3

Bitstream Generation

• Action: Converts the final placement and routing configuration into a binary stream.

• Output: A .bit or .sof file. This file is loaded into the FPGA's SRAM configuration memory at startup, physically setting the LUT values and routing switch states.