Synthesis Of Arithmetic Circuits: FPGA, ASIC, And Embedded Systems - Rilegato

Deschamps, Jean-Pierre; Bioul, Gery Jean Antoine; Sutter, Gustavo D.

Rilegato

ISBN 10: 0471687839 ISBN 13: 9780471687832

Casa editrice: Wiley-Interscience, 2006

Riassunto

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.

An Instructor Support FTP site is available from the Wiley editorial department.

Su questo libro

Informazioni sull?autore

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.

Dalla quarta di copertina

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.

Estratto. © Ristampato con autorizzazione. Tutti i diritti riservati.

Synthesis of Arithmetic Circuits

FPGA, ASIC and Embedded SystemsBy Jean-Pierre Deschamps Gery J.A. Bioul Gustavo D. Sutter

John Wiley & Sons

Copyright © 2006 Jean-Pierre Deschamps
All right reserved.
ISBN: 978-0-471-68783-2

Chapter One

INTRODUCTION

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):

12, 45, 216, 1, 107, 55, 10, 9, 34, 72, 215, 114, 13, 13, 229, 18:

The summary is computed as follows:

summary = (0, 0, 0, 0), summary = (12, 0, 0, 0), summary = (45, 12, 0, 0), summary = (216, 45, 12, 0), summary = (1, 216, 45, 12), summary = (119, 1, 216, 45), summary = (100, 119, 1, 216), summary = (226, 100, 119, 1), summary = (10, 226, 100, 119), summary = (153, 10, 226, 100), summary = (172, 153, 10, 226), summary = (185, 172, 153, 10), summary = (124, 185, 172, 153), summary = (166, 124, 185, 172), summary = (185, 166, 124, 185), summary = (158, 185, 166, 124), summary = (142, 158, 185, 166):

The final result, translated from the base-256 to the decimal representation, is

summary = 142 x [256.sup.3] + 158 x [256.sup.2] + 185 x 256 + 166 = 2392766886:

The encode function computes

encode(y) = [y.sup.x] mod m

x being some private key, and m a 32-bit number. Assume that

x = 1937757177 and m = [2.sup.32] - 1 = 4294967295.

Then the signature of the previous message is

s = [(2392766886).sup.1937757177] mod 4294967295 = 37998786:

1.7.2 Number Representation

In this example all the data are either 8-bit vectors (the characters) or 32-bit vectors (the summary, the key, and the module m). So instead of representing them in the decimal numeration system, they should be represented in the binary or, equivalently, the hexadecimal system. The message is

0C, 2D, D8, 01, 6B, 37, 0A, 09, 22 48, D7, 72, 0D, 0D, E5, 12:

The summary, the key, the module, and the signature are

summary = 8E9EB9A6, private key = 737FD3F9, m = FFFFFFFF, s = 0243D0C2.

1.7.3 Algorithms

The hash function amounts to a mod-256 addition, that is, a simple 8-bit addition without output carry. The only complex operation is the mod m exponentiation.

Assume that x, y, and m are n-bit numbers. Then

x = x(0) + 2x(1)+ ... + [2.sup.n-1]x(n - 1),

and e can be written in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The corresponding algorithm is the following (Chapter 8, Algorithm 8.14).

Algorithm 1.2 Exponentiation

e:=1; for i in 1..n loop e:=(e*e) mod m; if x(n-i)=1 then e:=(e*y) mod m; end if; end loop;

The only computation primitive is the modulo m product, which, in turn, is equivalent to a natural multiplication followed by a modulo m reduction, that is, an integer division by m. The following algorithm (Chapter 8, Algorithm 8.5) computes r = x.y mod m. It uses two procedures: multiply, which computes the product z of two natural numbers x and y, and divide, which generates q (the quotient) and r (the remainder) such that z = q.m + r with r < m.

Algorithm 1.3 Modulo m Multiplication

multiply (x, y, z); divide (z, m, q, r);

A classical method for computing the product z of two natural numbers x and y is the shift and add algorithm (Chapter 5, Algorithm 5.3). In base 2:

Algorithm 1.4 Natural Multiplication

p(0):=0; for i in 0..n-1 loop p(i+1):=(p(i)+x(i)*y)/2; end loop; z:=p(n)*(2**n);

For computing q and r such that z = q.m + r with r < m, the classical restoring division algorithm can be used (Chapter 6, Algorithms 6.1 and 6.2). Given x and y (the operands) such that x < y, and p (the desired precision), the restoring division algorithm computes q and r such that

x.[2.sup.p] = q.y + r. (1:1)

Within the exponentiation algorithm 1.2, the operands e and y are n-bit numbers. Furthermore, e is always smaller than m, so that both products z = e * e or z = e * y are 2.n-bit numbers satisfying the relation

z < m.[2.sup.n].

Thus by substituting x by z, p by n, and y by m.[2.sup.n] in (1.1), the restoring division algorithm computes q and r' such that

z.[2.sup.n] = q.(m.[2.sup.n]) + r' with r' < m.[2.sup.n],

that is,

z = q.m + r with r = r'.[2.sup.-n] < m.

The restoring algorithm is similar to the pencil and paper method. At every step the latest obtained remainder, say, r(i - 1), is multiplied by 2 and compared with the divider y. If 2.r(i - 1) is greater than or equal to y, then the new remainder is r(i) = 2.r(i - 1) - y and the corresponding quotient bit is equal to 1. In the contrary case, the new remainder is r(i) = 2.r(i - 1) and the corresponding quotient bit equal to 0. The initial remainder r(0) is the dividend.

Algorithm 1.5 Restoring Division

r(0) :=z; y: =m*(2**n); for i in 1..n loop if 2*r(i-1)-y<0 then q(i) :=0; r(i):=2*r(i-1); else q(i) :=1; r(i) :=2*r(i-1)-y; end if; end loop; r :=r(n)/(2**n);

By merging Algorithms 1.4 and 1.5, the following modular product algorithm is obtained.

Algorithm 1.6 Modular Product

p(0):=0; for i in 0..n-1 loop p(i+1) :=(p(i)+x(i)*y)/2; end loop; r(0):=p(n)*(2**n); y:=m*(2**n); for i in 1..n loop if 2*r(i-1)-y<0 then q(i):=0; r(i):=2*r(i-1); else q(i):=1; r(i):=2*r(i-1)-y; end if; end loop; r:=r(n)/(2**n);

Observe that the multiplication of p(n) and m by [2.sup.n], as well as the division of r(n) by [2.sup.n] can be deleted. Then r(0) = p(n) is a 2.n-bit fixed-point number (Chapter 3) smaller than [2.sup.n] and the divider is equal to m. The quotient q and the remainder r(n) satisfy the relation p(n).[2.sup.n] = q.m + r(n) so that r = r(n).

1.7.4 Hardware Platform

For implementing this illustrative example, a prototyping board will be used, namely, an XSA-100 board from XESS Corporation. It includes an XC2S100 FPGA (Spartan-II family of Xilinx) integrating the complete digital signature system. The design environment includes virtual components (synthesizable VHDL models, Chapter 9), among others PicoBlaze, an 8-bit microprocessor, and its program memory ([XIL2002]).

1.7.5 Hardware-Software Partitioning

As mentioned above, the only complex operation is the computation of [y.sup.x] modulo m. All the other operations can be carried out by the processor. The corresponding system architecture is shown in Figure 1.3. It works as follows:

PicoBlaze reads the character input at address 0 and the command input at address 1, where

command = 0 0 0 0 0 0 sign new_character.

It computes the 32-bit summary and writes it, under the form of four separate bytes,

summary = Y(3) Y(2) Y(1) Y(0),

into four registers whose addresses are 3, 2, 1 and 0, respectively.

A specific coprocessor receives the start signal from PicoBlaze at address 4, computes

s =[(summary).sup.737FD3F9] mod FFFFFFFF,

and generates the done flag.

1.7.6 Program Generation

The program executed by PicoBlaze is made up of three parts (assembly language code available):

reading of the new_character and sign input signals,

reading of the character input and updating of the summary,

writing of the summary and of the start command within the interface registers:

summary:=(0, 0, 0, 0); start:=0; loop -wait for command=0 while command>0 loop null; end loop; -wait for command=1 (new_character) or 2 (sign) while command=0 loop null; end loop; if command=1 then a:=(summary(0)+character) mod 256; summary(0):=summary(1); summary(1):=summary(2); summary(2):=summary(3); summary(3):=a; elsif command=2 then Y(3):=summary(3); Y(2):=summary(2); Y(1):=summary(1); Y(0):=summary(0); start:=1; summary:=(0, 0, 0, 0); start:=0; end if; end loop;

(Continues...)

Excerpted from Synthesis of Arithmetic Circuitsby Jean-Pierre Deschamps Gery J.A. Bioul Gustavo D. Sutter Copyright © 2006 by Jean-Pierre Deschamps. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Dettagli dell?edizione

• Editore: Wiley-Interscience
• Data di pubblicazione: 2006
• ISBN 10: 0471687839
• ISBN 13: 9780471687832
• Rilegatura: Copertina rigida
• Lingua: Inglese
• Numero di pagine: 556
• Contatto del produttore: non disponibile