Design and Implementation of a Microelectronic System

 

 

String Comparator

 

 

 

Mohammad Ahsanul Adeeb & Mohammad Moshiur Rahman

 

  

ECE551 FINAL PROJECT REPORT

December 1, 2004

 

 

 

 

 

 

Electrical and Computer Engineering

The University of Tennessee

Knoxville, TN 37996

 

Contents

  1. Abstract
  2. Introduction
  3. String Comparator
  4. Algorithm for Edit Distance
  5. System Requirements
  6. ASIC Requirements
  7. Block Diagrams
  8. Flow Charts
  9. Pre-Synthesis Simulation Results
  10. Placement and Routing Post-Synthesis Simulation Results
  11. Implementation in the Altera Tools
  12. System Performance
  13. Conclusion
  14. References
 
List of Figures
  1. Design Flow for a Microelectronic System
  2. System-level Block Diagram
  3. ASIC Modules and I/O requirements
  4. Block Diagram of the Test Bench
  5. Block Diagram of the Main Module
  6. Block Diagram of theEdit Module
  7. Zooming in to the Block Diagram of the Edit Module
  8. Flow Chart of the Search Module
  9. Zooming in to the Search Module Flow Chart
  10. Test Bench Simulation
  11. Edit Module Simulation
  12. Search Module Simulation
  13. Floor Plan for Altera FLEX 10K20
  14. Layout in Xilinx XCV1000E
  15. Zooming in to the Virtex Layout
  16. Test Bench Simulation
  17. Edit Module Simulation
  18. Search Module Simulation
  19. Test Bench Simulation in Virtex
  20. Post-Synthesis Coverage for Virtex
  21. Altera Logic Floorplan

 

Abstract

This project involves the design, simulation, realization and demonstration of a STRING COMPARATOR system using multiple (Altera and Xilinx) Field-Programmable Gate Arrays (FPGA). The behavior of the system was described in a hardware description language (VHDL), which was then synthesized into a hardware-independent structural description and then combined with other components. After verification of the design using computer simulation, the design was physically placed and routed using technology-dependent tools, namely Altera & Xilinx tools.

 

Introduction

The design of the microelectronic system for this project was done to meet the requirements for a specific application. The system consists of input/output devices coupled with digital logic circuitry, to be implemented in a single application-specific integrated circuit (ASIC). The design is specified, as shown in Figure 1, at various levels of abstraction including the system, behavioral, structural, and physical levels. The design process involves mapping the requirements of the application into lower-level specifications that describe not only the internal functions, but also the interactions among the components and the external world.

For this project, a hardware description language, VHDL, was used to specify portions of the design. This representation was then synthesized and mapped into a chosen technology. The resulting structural (logic) description then was combined with other components using a schematic editor. After that the design was simulated for functionality. Once verified, the structural representation was translated into a physical representation that was placed and routed automatically. The design was then re-simulated to verify proper operation and timing.

Using this synthesis-based approach, the core of the design was made to be technology-independent. Then it could be implemented on multiple devices; namely the Altera FLEX10K20 and Xilinx XCV1000E devices. Very little redesign would be required for transferring the design from one platform to another. This platform-independence facilitates cost-effectiveness and turnaround time for real-world designs that may be targeted to a variety of devices. In addition, various devices can be compared on the basis of speed, cost, size, and availability while maintaining the exact same functionality.

This report has been organized along the lines of the design flow shown in Figure 1. First, the system requirements and then the detailed specifications are given. Next, the behavioral and structural representations are discussed. The actual physical layouts were implemented after successful design synthesis and verification by simulation for the specific technology mentioned.

Figure 1: Design Flow for a Microelectronic System

 

String Comparator

 

A string comparator is basically a system that compares two strings and tries to measure the similarity between two based on some mathematical calculations. In many applications it is necessary to determine the similarity of two strings. A widely used notion of measuring string similarity is the Levenshtein Distance or the edit distance. The edit distance of two strings, which we refer to as the source string (s) and the target string (t), is defined as the minimum number of point mutations required changing s into t, where a point mutation is one of the following:

1.      Changing a letter,

2.      Inserting a letter or

3.      Deleting a letter

For example,

The greater the Levenshtein distance, the more different the strings are. Levenshtein distance is named after the Russian scientist Vladimir Levenshtein, who devised the algorithm in 1965.

 

More Examples:

 

1)

 

 

                                    Edit Distance = 0

 

2)

 

 

 

 

 

Distance without shifting:  5 (for deleting five characters) + 5 (for inserting five characters) = 10

 

Distance after shifting:  2 (for deleting two characters) + 2 (for inserting two characters) = 4

 

                                    Edit Distance = 4

 

 

Our designed string comparator calculates the edit distance between two strings according to the definitions described above, and it also incorporates the additional feature of a substring search. For the search option, a small string is looked for inside a bigger string for a possible match. If match occurs, the system reports that as well as the position in the bigger string where the match occurs. Detailed descriptions of the features have been provided later in this report.

 

Algorithm for Edit Distance Calculation

Steps

Step

Description

1

Set n to be the length of s.
Set m to be the length of t.
If n = 0, return m and exit.
If m = 0, return n and exit.
Construct a matrix containing 0..m rows and 0..n columns.

2

Initialize the first row to 0..n.
Initialize the first column to 0..m.

3

Examine each character of s (i from 1 to n).

4

Examine each character of t (j from 1 to m).

5

If s[i] equals t[j], the cost is 0.
If s[i] doesn't equal t[j], the cost is 1.

6

Set cell d[i,j] of the matrix equal to the minimum of:
a. The cell immediately above plus 1: d[i-1,j] + 1.
b. The cell immediately to the left plus 1: d[i,j-1] + 1.
c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.

7

After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].

 

 

 

 

System Requirements

The designed microelectronic system for this project consisted of a string comparison system. Two inputs (maximum of 5 characters each) can be compared for either edit distance calculation or substring search depending on the mode selection by the user, where one input is considered as the reference string and the other is the comparing input string. Four different options are available in the system which are described below:

 

Option 1: Clear  (DIP = “00000000”)

 

The system turns of both of the seven-segment displays.

 

Option 2: BIST  (DIP = “00000001”)

 

All segments of the two seven-segment displays are lighted up.

 

Option 3: Edit Distance  (DIP = “00000010”)

 

The system compares the two input strings to calculate the edit distance between them and displays the result measured in one of the seven-segment displays (LED1).

 

Option 4: Substring Search  (DIP = “00000100”)

 

A three-character substring is searched inside the bigger reference string for a match. If match occurs, LED2 displays “1” and LED1 displays the position (character number, counting from the left) in the reference string where the substring is found. If the string is not found, both LED1 and LED2 show “0”.

 

The designed system basically will have four modes of operation, and the system requirements for those are as follows:

 

 

 

 

Figure 2: System-level Block Diagram

 

ASIC Requirements

The design consists of several functional blocks, each performing a particular task. Figure 3 shows the internal components and the I/O requirements of the ASIC.

 

 

Figure 3: ASIC Modules and I/O requirements

 

 

The basic design consists of the above modules shown. The input module takes the input character one by one with the help of a PB. It takes first eight characters as reference string and next eight characters as comparing string. For the next input characters this module works in the same way. An external clock provides synchronization for the state machine execution. The clock division module divides the clock to a lower frequency if required.

 

The main module shown at the center of the diagram comprises state machine and the arithmetic & logic module. This state machine collects the input characters and based on the mode selected it sends the input data to the arithmetic and logic module. In fact, the state machine generates control bits that control the operation of all the other modules in the design. The arithmetic & logic module performs the necessary mathematical and logical operations on the data.

 

After the result of the selected function is calculated, the main module sends signals to the output module (two 7-segment display controller). The 7-segment controller/decoder module translates these signals and light up the 7-segments to display the numerical result.

 

The BIST (Built-In Self-Test) module lights up each of the LED’s and 7-segement displays to verify their operation.

 

A one-pulse module was needed in the actual implementation to remove the debounce effect of the two push buttons.

 

Block Diagrams

Figure 4: Block Diagram of the Test Bench

 

 

Figure 5: Block Diagram of the Main Module

Figure 6: Block Diagram of theEdit Module

Figure 7: Zooming in to the Block Diagram of the Edit Module

 

Flow Charts

 

Figure 8: Flow Chart of the Search Module

Figure 9: Zooming in to the Search Module Flow Chart

 

Pre-Synthesis Simulation Results

Figure 10: Test Bench Simulation

 

Figure 11: Edit Module Simulation

Figure 12: Search Module Simulation

Placement and Routing

Figure 13: Floor Plan for Altera FLEX 10K20

Figure 14: Layout in Xilinx XCV1000E

 

Figure 15: Zooming in to the Virtex Layout

 

Post-Synthesis Simulations

 

Figure 16: Test Bench Simulation

 

Figure 17: Edit Module Simulation

Figure 18: Search Module Simulation

 

Figure 19: Test Bench Simulation in Virtex

Figure 20: Post-Synthesis Coverage for Virtex

 

 

 

 Implementation in the Altera Tools

Since the function blocks were developed previously using technology-independent VHDL, they were resynthesized into a technology-dependent structural description using the Altera library. The system was coded in IEEE-compliant VHDL and compiled and simulated using the Altera MAX2PLUSWIN Suite. This provided an opportunity to detect and correct errors early in the design process. It also allowed each module to be individually simulated to verify correct operation before the entire system was tested.

The project file was downloaded to an Altera evaluation board containing a FLEX10K20RC240-4. This is a 240-pin FPGA, which had barely sufficient room to store the logic functions for this project. Several pins on the chip were hardwired to specific components on the evaluation board, such as seven-segments, LEDs, dip switches, etc. The eight Flex switches were used for entering the code corresponding to the input characters and the two Flex push buttons were used for mode control. The pin numbers for each device were available in the documentation for the board, and were manually assigned in the Altera software prior to downloading.  Also, an external clock signal was used, and applied to another pin on the chip, which was then manually selected in the Altera software. The logic floor plan for the designed system has been shown here once again for convenience.

 

Figure 21: Altera logic floorplan

 

 

 

Before downloading to the Altera evaluation board we performed simulation for theoretically expected results using a test vector file. The simulation results were found satisfactory.  

 

 

 

System performance

After successfully downloading the project to the evaluation board, a series of tests were performed using the physical inputs (switches and push buttons) and physical outputs (seven-segment displays) on the board. Edit distance calculation, substring search and other options were performed and correctly verified for many sets of data. The seven-segment LEDs functioned correctly for all the possible values.

The physical results corresponded exactly to the results predicted by manual analysis and software simulations. This confirms that the design process was complete and the implementation of the design was accurate.

 

Conclusion

The ‘String Comparator’ we designed and developed was successfully tested using an Altera FPGA device. General system functions were broken down into modules, which were designed and coded using VHDL.  All the design objectives were met and hardware implementation worked perfectly. However, we could have allowed more characters per string and made the system work with strings of variable length. We also developed some codes and did some successful pre-synthesis simulation in order for supporting these enhanced features. However, when we tried to synthesize and place and route those functions, we found the Altera FLEX 10K20 device exceeding the maximum gate limit. We also had some problems implementing WHILE loops and WAIT statements. Therefore, we had to be a little defensive on coding and synthesizing attempts due to the hardware limitations. Otherwise, everything worked just fine. Of course, there is sufficient scope for enhancing the system and adding more features to it, especially with a larger capability FPGA device. It is also possible to implement our design in other technologies, such as Xilinx, because the design core is technology independent.

As a final point, it is worth mentioning some features of the string comparator and edit distance measurements. The Levenshtein distance algorithm has been successfully used in:

As a whole, the lessons learned from working on this project were great and it provided us some insight in to FPGA design with real-life hands on experience. 

References

[1] http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

[2] http://www.merriampark.com/ld.htm