Über die Autorin bzw. den Autor

JEAN-PIERRE DESCHAMPS, PhD, is Professor, University Rovira, Tarragona, Spain. He is the author of six books and over 100 research papers. His research interests include FPGA and ASIC design, digital arithmetic, and cryptography.

GERY Jean Antoine BIOUL, MSc, is Professor, National University of the Center of the Province of Buenos Aires, Argentina. His research interests include logic design and computer arithmetic algorithms, and implementations.

GUSTAVO D. SUTTER, PhD, is Professor, University Autonoma of Madrid, Spain. His research interests include FPGA and ASIC design, digital arithmetic, and development of embedded systems.

Von der hinteren Coverseite

A new approach to the study of arithmetic circuits

In Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems, the authors take a novel approach of presenting methods and examples for the synthesis of arithmetic circuits that better reflects the needs of today's computer system designers and engineers. Unlike other publications that limit discussion to arithmetic units for general-purpose computers, this text features a practical focus on embedded systems.

Following an introductory chapter, the publication is divided into two parts. The first part, Mathematical Aspects and Algorithms, includes mathematical background, number representation, addition and subtraction, multiplication, division, other arithmetic operations, and operations in finite fields. The second part, Synthesis of Arithmetic Circuits, includes hardware platforms, general principles of synthesis, adders and subtractors, multipliers, dividers, and other arithmetic primitives. In addition, the publication distinguishes itself with:

• A separate treatment of algorithms and circuits―a more useful presentation for both software and hardware implementations
• Complete executable and synthesizable VHDL models available on the book's companion Web site, allowing readers to generate synthesizable descriptions
• Proposed FPGA implementation examples, namely synthesizable low-level VHDL models for the Spartan II and Virtex families
• Two chapters dedicated to finite field operations

This publication is a must-have resource for students in computer science and embedded system designers, engineers, and researchers in the field of hardware and software computer system design and development.

Aus dem Klappentext

A new approach to the study of arithmetic circuits

In Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems, the authors take a novel approach of presenting methods and examples for the synthesis of arithmetic circuits that better reflects the needs of today's computer system designers and engineers. Unlike other publications that limit discussion to arithmetic units for general-purpose computers, this text features a practical focus on embedded systems.

Following an introductory chapter, the publication is divided into two parts. The first part, Mathematical Aspects and Algorithms, includes mathematical background, number representation, addition and subtraction, multiplication, division, other arithmetic operations, and operations in finite fields. The second part, Synthesis of Arithmetic Circuits, includes hardware platforms, general principles of synthesis, adders and subtractors, multipliers, dividers, and other arithmetic primitives. In addition, the publication distinguishes itself with:

• A separate treatment of algorithms and circuits—a more useful presentation for both software and hardware implementations
• Complete executable and synthesizable VHDL models available on the book's companion Web site, allowing readers to generate synthesizable descriptions
• Proposed FPGA implementation examples, namely synthesizable low-level VHDL models for the Spartan II and Virtex families
• Two chapters dedicated to finite field operations

This publication is a must-have resource for students in computer science and embedded system designers, engineers, and researchers in the field of hardware and software computer system design and development.

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Synthesis of Arithmetic Circuits

John Wiley & Sons

Chapter One

The design of embedded systems, that is, circuits designed for specific applications, is based on a series of decisions as well as on the use of several types of development techniques. For example:

Selection of the data representation

Generation or selection of algorithms

Selection of hardware platforms

Hardware-software partitioning

Program generation

New hardware synthesis

Cosimulation, coemulation, and prototyping

Some of these activities have a close relationship with the study of arithmetic algorithms and circuits, especially in the case of systems including a great amount of data processing (e.g., ciphering and deciphering, image processing, digital signature, biometry).

1.1 NUMBER REPRESENTATION

When using general-purpose equipment, the designer has few possible choices concerning the internal representation of data. He must conform to some fixed and predefined data types such as integer, floating-point, double precision, and character. On the contrary, if a specific system is under development, the designer can choose, for each data, the most convenient type of representation. It is no longer necessary to choose some standard fixed-point or floating-point numeration system. Nonstandard specific formats can be used. In Chapter 3 the main number representation methods will be defined.

1.2 ALGORITHMS

Every complex data processing operation must be decomposed into simpler operations-the computation primitives-executable either by the main processor or by some specific coprocessor. The way the computation primitives are used in order to perform the complex operation is what is meant by algorithm. Obviously, knowledge of algorithms is of fundamental importance for developing arithmetic procedures (software) and circuits (hardware). It is the topic of Chapters 4-8.

1.3 HARDWARE PLATFORMS

The selection of a hardware platform is based on the answer to the following question. How do we get the desired behavior at the lowest cost, while fulfilling some additional constraints? As a matter of fact, the concept of cost must be carefully defined in each particular case. It can cover several aspects: for example, the unit production cost, the nonrecurring engineering costs, and the implicit cost for a late introduction of the product to the market. Some examples of additional technical constraints are the size of the system, its power consumption, and its reliability and maintainability.

For systems requiring little data processing capability, microcontrollers and low-range microprocessors can be the best choice. If the computation needs are greater, more powerful microprocessors, or even digital signal processors (DSPs), should be considered. This type of solution (microprocessors and DSPs) is very flexible as the development work mainly consists in generating programs.

For getting higher performances, it may be necessary to develop specific circuits. A first option is to use a programmable device, for example, a field-programmable gate array (FPGA). It could be an interesting option for prototypes and small series. For greater series, an application-specific integrated circuit (ASIC) should be developed. ASIC vendors offer several types of products: for example, gate arrays, with relatively small prototyping costs, or standard cell libraries, integrating a complete system-on-chip (SOC) including processors, program memories, data memories, logic, macrocells, and analog interfaces.

A brief presentation of the most common hardware platforms is given in Chapter 9.

1.4 HARDWARE-SOFTWARE PARTITIONING

The hardware-software partitioning consists of deciding which operations will be executed by the central processing unit (the software) and which ones by specific coprocessors (the hardware). As a matter of fact, the platform selection and the hardware-software partitioning are tightly related operations. For systems requiring little data processing capability, the whole system is implemented in software. If higher performances are necessary, the noncritical operations, as well as control of the operation sequence, are executed by the central processing unit, while the critical ones are implemented within specific coprocessors.

1.5 SOFTWARE GENERATION

The operations belonging to the software block of the chosen partition must be programmed. In Chapters 4-8 the algorithms are presented in an Ada-like language that can easily be translated to C or even to the assembly language of the chosen microprocessor.

1.6 SYNTHESIS

Once the hardware-software partition has been defined, all the tasks assigned to the specific hardware (FPGA, ASIC) must be translated into circuit descriptions. Some important synthesis principles and methods are described in Chapter 10. The synthesis of arithmetic circuits, based on the algorithms of Chapters 4-8, is the topic of Chapters 11-15, and an additional chapter is dedicated to the implementation of floating-point arithmetic.

1.7 A FIRST EXAMPLE

Common examples of application fields resorting to embedded solutions are cryptography, access control, smart cards, automotive, avionics, space, entertainment, and electronic sales outlets. In order to illustrate the main steps of the design process, a small digital signature system will now be developed (complete assembly language and VHDL code available).

1.7.1 Specification

The system under development (Figure 1.1) has three inputs,

character is an 8-bit vector.

new_character is a signal used for synchronizing the input of successive characters.

sign is a control signal ordering the computation of a digital signature. and two outputs,

done is a status variable indicating that the signature computation has been completed,

signature is a 32-bit vector, namely, the signature of the message.

The working of the system is shown in Figure 1.2: a sequence [c.sub.1], [c.sub.2], ..., [c.sub.n] of any number n of characters (the message), synchronized by the signal new_character, is inputted. When the sign control signal goes high, the done flag is lowered and the signature of the message is computed. The done flag will be raised as soon as the signature s is available.

In order to sign the message two functions must be defined:

a hash function associating a 32-bit vector (the summary) to every message, whatever its length;

an encode function computing the signature corresponding to the summary.

The following (naive) hash function is used:

Algorithm 1.1 Hash Function

summary:=0; while not(end_of_message) loop get(character); a:=(summary(7 downto 0)+character) mod 256; summary(23 downto 16):=summary(31 downto 24); summary(15 downto 8):=summary(23 downto 16); summary(7 downto 0):=summary(15 downto 8); summary(31 downto 24):=a; end loop;

As an example, assume that the message is the following (every character can be equivalently considered as an 8-bit vector or a natural number smaller than 256, i.e. a base-256 digit; see Chapter 3):

...