24-01-2013, 11:20 AM
A Parameterisable Fast Walsh-Hadamard Transform
1A Parameterisable.pdf (Size: 620.18 KB / Downloads: 44)
ABSTRACT
The aim of this thesis was to create a parameterisable Fast Walsh-Hadamard
Transform in the form of a robust intellectual property core. This paper provides
background information on the Walsh-Hadamard Transform (WHT), reprogrammable
hardware and the current state of the intellectual property (IP) industry. The
functionality of the IP core that was produced is explained, and further areas for study
are explored. Customisable features of the transform include the number of points, the
input word length, and the ordering. It is noted that the parameterisable FWHT core is
consistent with IP principles, in that it is technology independent, customisable, and
synthesizable.
Introduction
The level of abstraction in electronic design has risen during this century from
components such as the resistor and transistor, to logic gates, all the way up to
hardware description languages. Accompanying this development is Moore’s Law,
which states that the number of logic gates semiconductor companies can fit on a chip
doubles every two years. These two phenomena are dramatically reducing design
times, and increasing design complexity.
One of the most valuable assets of a semiconductor manufacturer is its intellectual
property (IP). An IP core is a description of a certain piece of hardware, written in a
hardware description language such as VHDL or Verilog. Today, rather than
developing a design in-house from scratch, many companies are finding it to be more
productive to purchase their design from an IP vendor.
Increased emphasis is now being placed on designing reusable IPs. A well-designed
reusable core is valuable, as it can be implemented by anyone with an application that
demands it. Combined with reprogrammable hardware such as FPGAs, they allow
very rapid prototyping and low time-to-market.
PROBLEM DEFINITION
The aim of this project is to create a parameterisable Fast Walsh Hadamard Transform
(FWHT) IP core. The FWHT is to be described in synthesizable VHDL code, with a
comprehensive testbench for simulation. A graphical user interface will enable a user
to generate the required code by selecting the appropriate parameters.
METHODOLOGY
The development of this project can be divided into a number of stages. Firstly the
FWHT algorithm had to be developed. An understanding of the important issues in
the intellectual property field enabled the creation of a VHDL description consistent
with IP principles. A number of tools were required in this process. Active HDL was
used for writing, debugging, compiling and simulating the VHDL code. Mentor
Graphics was used to simulate and synthesise the design. Visual Basic provided a
simple platform to create a user interface to automatically generate customised VHDL
code.
OUTLINE
Chapter 2 of this paper reviews the literature relevant to this experiment. Certain IP
cores are investigated, along with trends in the IP market. Additionally, FPGAs and
reconfigurable computing are discussed. Walsh Hadamard Transforms and their
applications are also covered. Chapter 3 explains the theory behind the Walsh
Hadamard Transform and provides an efficient algorithm to compute the FWHT. A
description of an FPGAs architecture and functionality is provided. Chapter 4
describes the final design, and is presented in a typical IP datasheet format. Chapter 5
addresses the future and chapter 6 concludes.
REPROGRAMMABLE SYSTEMS
Reconfigurable Computing has been described as hardware going soft. A computing
platform based on this principle has an architecture that can be modified by the
software to suit the application at hand10. An algorithm will always run fastest when
directly hardwired (DSP, ASIC). Dramatic performance gains can therefore be
obtained by implementing an algorithm in the reconfigurable portion of such a
system.
Custom computing has gathered momentum over the past few years.13 A custom
computing machine (CCM) consists of a host processor such as a microprocessor
connected to programmable hardware that implements the computationally complex
part of a program. The concept arose from the fact that in microprocessor
implementations, most computationally complex applications spent 90% of their
execution time on 10% of their code.14 Because hardware always outperforms
software, CCM implementations offer superior performance to microprocessor
implementations.
The FPGA is the natural platform for CCMs due to its reprogrammability.
Architectures such as the XC6200 and Virtex series from Xilinx are dynamically
reprogrammable during operation. Virtual Computing Corporation already offers a
PCI-interfaced, FPGA-based custom computing board complete with development
software.
This board has been used to develop a highly efficient XC6200 implementation of a
two dimensional discrete cosine transform (2D DCT) circuit that performs the
equivalent of 2 billion operations per second.9 The design exploits the algorithm’s
inherent parallelism and uses pipelining and a distributed-arithmetic organisation. It
achieves a performance speedup of four times that of a 233-MHz Pentium II with 64
Mbytes of RAM performing the computation using the fast Lee DCT algorithm. This
allows the processing of VGA colour images (640 x 480 pixels) at 25 frames per
second.