Diseño de Operadores Aritméticos Dr. Andrés David García García Departamento de Mecatrónica ITESM-CEM

Algoritmos de procesamiento digital de señales • Los algoritmos de DSP basan su funcionamiento en operadores aritméticos y unidades de almacenamiento temporal. • Filtros Digitales • Transformadas Discretas Coseno/Fourier • Convolución

• Operadores MAC(Multiply And ACcumulate) M 1

y (n)   h(k )x(n  k ) k 0

2

Algoritmos de DSP • Diseño de Operadores Aritméticos: crítico en el diseño VLSI de arquitecturas de DSP • Arquitecturas eficientes de operadores aritméticos funamentales (sumas, restas, multiplidadores y divisores) para aplicaciones VLSI • Objetivo: Diseñar y Construir arqutiecturas con un mínimo tiempo de propagación (mejorar velocidad de respuesta), y con el menor requerimiento de superficie de silicio (optimizar la densidad y el nivel de integración).

ADGG / LFGP

3

Representación de Números en Binario • Números positivos en binario: Magnitud:

N 1

X   Bi  2 i 0

i

i 15

3 1

2 1

1 1

0 1

14 : 2 1 0

1 : 0 0 0

1 : 0 0 0

1 : 1 0 0

0 : 0 1 0 4

Representación de Números Negativos • Varios métodos • Característica común: MSB representa el bit de signo • 0  número positivo • 1  número negative

• Métodos principales • Signo y magnitud • Complemento a 2 • Complemento a 1

5

Representación de Números Negativos • Signo y magnitud poco adaptado al diseño de circuitos digitales: • Se requiere de N bits para la magnitud y de un bit extra para el signo. • Las arquitecturas aritméticas son más complejas.

• Complemento a 2 y complemento a 1 permiten un fácil diseño de circuitos aritméticos digitales: • Objetivo: representar números positivos y negativos usando el mísmo número de bits.

6

Numeración en Complemento a 1 • Número positivo, N, 0 XX…XXX Donde XX…XXX representa la magnitud del número

• Número negativo, -N, /N = (2n – 1) – N Ejemplo: Si n = 4, -N = 15 – N, -3 = 15 – 3 = 11 = 11002

• Regla: Complementar todos los bits de la palabra.

7

Numeración en Complemento a 2 • Número positivo, N, 0 XX…XXX Donde XX…XXX representa la magnitud del número

• Número negativo, -N, N* = 2n – N Donde n es el tamaño de la palabra o número Ejemplo: Si n = 4, -N = 16 – N, -3 = 16 – 3 = 13 = 11012

• Regla: Avanzar de derecha a izquierda. Cuando se localice el primer 1, complementar los siguientes bits. 8

Complemento a 1 y Complemento a 2 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7

0

1

7

2+4=6 2

6

2 - 4 = 6 (-2)

3

5

4 9

Complemento a 2 VS Complemento a 1 • N* = 2n – N = 2n – 1 – N + 1 = /N + 1 • Obtención de N a partir de sus complementos • N = 2n – N* • N = (2n – 1) – /N

• Complemento a 2: posibilidad de representar un número negativo más que un número positivo. Ejemplo: Para n = 4 podemos representar los valores [7 .. –8]

10

Representación de Números Negativos Enteros Positivos (Todos los sistemas)

N

Enteros Negativos -N

Signo y magnitud

Complemen to a 2

Complemen to a 1

+0

0000

-0

1000

----

1111

+1

0001

-1

1001

1111

1110

+2

0010

-2

1010

1110

1101

+3

0011

-3

1011

1101

1100

+4

0100

-4

1100

1100

1011

+5

0101

-5

1101

1011

1010

+6

0110

-6

1110

1010

1001

+7

0111

-7

1111

1001

1000

-8

----

1000

----

11

La Suma en Complemento a 2 • La suma de números con signo de n bits es directa cuando se emplea el sistema en complemento a 2. • Cualquier carry de la posición de signo se ignora • La suma siempre será correcta excepto cuando ocurre overflow • Se dice que ha ocurrido overflow cuando la representación de la suma (incluyendo el bit de signo) requiere más de n bits

12

La Suma en Complemento a 1 • Similar a la suma en complemento a 2 • Diferencia: El carry no se ignora y se suma al resultado de la suma • También puede ocurrir overflow, lo que indica que la suma necesita más bits para representarse correctamente

13

Ejemplos • Complemento a 2 • • • • • •

(+3)+(+4) (+5)+(+6) (+5)+(-6) (-5)+(+6) (-3)+(-4) (-5)+(-6)

=> +7 (0111) => +11 (1011) => -1 (1111) => +1 (0001) => -7 (1001) => -11 (0101)

14

Ejemplos • Complemento a 1 • • • • • •

(+3)+(+4) (+5)+(+6) (+5)+(-6) (-5)+(+6) (-3)+(-4) (-5)+(-6)

=> +7 (0111) => +11 (1011) => -1 (1110) => +1 (0000) ???? => -7 (0111) ???? => -11 (0011) ????

Igual que el complemento a 2

15

Overflow • Con el propósito de obtener una respuesta correcta de un sumador/restador, se debe asegurar que el resultado tiene el número suficiente de bits para representar el resultado • Si dos números de b-bits se suman y la suma requiere de n+1 bits para ser representada, ocurre un overflow • El “overflow” es un problema cuando el número de bits para representar el resultado es fijo • Una Solución: extender el resultado a n+1 bits  desperdicio de recursos 16

Overflow • Otra solución es detectar cuando ocurre el “overflow” • Dos casos • Números sin signo • Números con signo

17

Overflow en números sin signo • En la suma de 2 números sin signo, el “overflow” se detecta a partir del Carry-Out del MSB. • En la resta de números sin signo, la magnitud del resultado es siempre igual o menor que el operando de mayor longitud, por lo que no hay posibilidad de “overflow”.

18

Overflow en números con signo • En 2’complemento, el MSB indica el signo • Cuando 2 números con signo se suman, el bit de signo se manipula separadamente del número y un Carry-Out de los MSB en ‘1’ no es necesariamente un “overflow” • En números con signo, un “overflow” no puede ocurrir durante la suma si uno de los operandos es positivo y el otro negativo

19

Overflow en números con signo • Un “overflow” puede ocurrir si los 2 números a sumar son positivos o negativos • Ejemplo: suma de 2 números de 8-bits

 70

0 1 0 0 0 1 1 0

 80 0 1 0 1 0 0 0 0  150 0 1 0 0 1 0 1 1 0

 70

1 0 1 1 1 0 1 0

 80 1 0 1 1 0 0 0 0  150 1 0 1 1 0 1 0 1 0

20

Overflow en números con signo • Rango de valores sobre 8-bits: [-128, 127] • El resultado (150) excede la capacidad de representación • El resultado que debería ser positivo tiene un signo negativo y el resultado que debiera ser negativo tiene un signo positivo

 70

0 1 0 0 0 1 1 0

 80 0 1 0 1 0 0 0 0  150 0 1 0 0 1 0 1 1 0

 70

1 0 1 1 1 0 1 0

 80 1 0 1 1 0 0 0 0  150 1 0 1 1 0 1 0 1 0

21

Overflow en números con signo • El “overflow” se detecta al observar el Carry dentro del bit de signo y el carry-out del bit de signo • Si ambos no son iguales, un “overflow” ha ocurrido (XOR)

Carry : 0 1 0 0 0 0 0 0  70 0 1 0 0 0 1 1 0

Carry : 1 0 1 1 0 0 0 0  70 1 0 1 1 1 0 1 0

 80  150

 80  150

0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0

1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 1 0

22

Sumadores Binarios • Operación aritmética básica en el diseño de circuitos digitales más complejos • Clasificación Tipo de Suma • Sumador Completo (Full Adder) • Sumador Medio (Half Adder)

Implementación de Sumas con

n bits

• Ripple Carry Adder • Carry Lookahead Adder

23

Sumador Medio (Half Adder) • Circuito aritmético que genera la suma de dos bits (no toma en cuenta el bit carry)

A

Entradas

Salidas

A

B

Cout

S

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

0

S  AB  AB  A  B C  AB

B

Cout S A B

HA

S Cout 24

Sumador Completo (Full Adder) • Circuito aritmético que genera la suma de tres bits (entradas A y B, y el bit carry)

A

B

Cout (Hacia el siguiente FA)

FA

Cin (Del FA anterior)

S 25

Sumador Completo (Full Adder)

Entradas

Salidas

S  ABCin  ABCin  ABCin  ABCin

A

B

Cin

Cout

S

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

Cout  AB  ACin  BCin

0

1

1

1

0

1

0

0

0

1

Cout  AB  Cin( AB  AB )

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

S  A  B  Cin

Cout  AB  Cin( A  B )

26

Sumador Completo (Full Adder)

Half Adder A B

Half Adder S

Cout Cin 27

Sumadores de n bits • Arquitecturas capaces de realizar la suma de dos números de n bits • Dos tipos de intereses: Velocidad Tamaño

• Dos tipos de arqutiecturas Arquitecturas en Serie

Tamaño Velocidad Arquitecturas en Paralelo

Velocidad Tamaño 28

Sumador en Serie • Implementación de un sumador eficiente en tamaño

A = An-1, An-2, …,A0 B = Bn-1, Bn-2, …,B0

Ai Bi

Si

FA

Cout

Cin

Condición: entradas sincronizadas por medio de la señal CLK

Q

D

CLK 29

Sumador Paralelo • Arquitecturas para realizar sumas de n bits donde la velocidad es el principal criterio de diseño • Utilización de n FA´s. Todos los bits se aplican simultáneamente a los FA´s para producir la suma • Clasificación de acuerdo a la forma de generar el bit de carry : • • • • •

Ripple Carry Adder Carry Lookahead Adder Manchester Carry Chain Carry Select Adder Carry Skip Adder 30

Ripple Carry Adder An-1

Cn

Bn-1

FA Sn-1

A2

Cn-1

B2

FA s2

A1

c2

B1

FA s1

A0

c1

B0

FA

c0

s0

Cin 0 1 1 0 A 1011 B 0011 S 1110 Cout 0 0 1 1

31

Ripple Carry Adder • Aplicación simultánea de las entradas A, B • Cada FA genera S y Cout simultáneamente después de Tp segundos (Tp : tiempo de propagación) • Inestabilidad inicial debido a Tp • Después de nTp segundos, el sumador produce la suma total • Desventaja: Tiempo de propagación muy largo (nTp)

32

Ripple Carry Adder • Todas las células propagan: • Sn requiere de Cn-1 • El tiempo de propagación será igual a 3(TpropFA) A0 B0

C0

FA

S0

A1 B1

C1

FA

S1

A2 B2

C2

FA

S2

A3 B3

C3

FA

S3

C4

S4 33

Ripple Carry Adder • Si al menos una de las células FA no propaga Carry: • Sn no requerirá de Cn-1 • El tiempo de propagación será igual a 2(TpropFA A0 B0

C0

FAp

S0

A1 B1

C1

FAI

S1

A2 B2

C2

FAp

S2

A3 B3

C3

FAI

S3

C4

S4 34

Ripple Carry Adder • Análisis de la suma de 3 bits: Ai Bi Ci

Ci+1

0 0 0 0 0 1

0 0

Ai = Bi  Generación Ci+1 = Gi = Ai AND Bi

0 0 1 1

0 1 0 1

0 1 0 1

Ai  Bi  Propagación Ci+1 = Ci  Pi = Ai XOR Bi Pi = ‘1’  Propagación de carry Pi = ‘0’  Generación de carry

1 1 0 1 1 1

1 1

Ai = Bi  Generación Ci+1 = Gi = Ai AND Bi

1 1 0 0

35

Ripple Carry Adder • Análisis de la suma de 3 bits: • A la entrada del sumador completo (3 bits) los bits A, B y Cin llegan al mismo tiempo. • Si sabemos desde ese momento que A = B o que A  B, entonces podemos determinar, en base a la tabla anterior, si el Cout debe ser calculado en base a A, B, Cin (generación) o si el Cout = Cin (propagación).

36

Optimización de la suma de 3 bits • Con el fin de anticipar (predecir) si el Carry de salida debe ser calculado o no, se ha modificado la célula del FA: ai bi (t0)

• • • •

Célula P Célula G Multiplexor Célula S

T1

Ci +1

P

G

M U

(tci+1)

T1

Ci (tci)

X

T2

S

Si (tsi)

T3

37

Optimización del sumador ai bi

(t0)

• Célula: P

T1

G

T1

Propagación Generación

Ci +1

M U

(tci+1)

Ci (tci)

X

T2

S

T3

Cálculo de la suma Si (tsi) 38

Manchester Carry Chain Adder • Se forma a base de células de suma de 3 bits optimizadas (P y G).

• El objetivo es tratar de predecir, desde el momento en que llegan los bits, si una o varias células van a propagar el carry de entrada correspondiente. • En el mejor de los casos todas las células generan el carry de salida: Tsuma = T0

39

Manchester Carry Chain Adder • Célula en modo de propagación:

P

Ci+1

G

M U X

Ci

S

Si

40

Manchester Carry Chain Adder • Célula en modo generación:

P

G

M

Ci+1

U X

Ci

S

Si

41

Manchester Carry Chain Adder • Caso intermedio: Al menos una célula genera: 11

01

10

00

10

10

01

11

• En este caso las células de los bits cero, cuatro y cinco generaron Carry de salida. • Las demás células propagaron. • El tiempo de la suma de 8 bits es 5t (la cadena más larga). 42

Manchester Carry Chain Adder • Peor caso: todas las células propagan: La suma de los bits n, requieren del carry del nivel n-1. 10

01

10

01

10

10

01

10

• El tiempo de la suma de 8 bits es 8t.

43

Manchester Carry Chain Adder • Las compuertas que forman al FA tienen distintos tiempos de propagación (T1, T2, T3). • Se supone que los módulos P y G T1 tienen el mismo tiempo de propagación T1. • Los operandos ai, bi están disponibles Ci +1 en t0. (tci+1) • El carry de entrada Ci esta disponible en el tiempo tci.

ai bi

(t0)

P

G

T1

M U

Ci (tci)

X

T2

S

Si (tsi)

T3

44

Manchester Carry Chain Adder ai bi

• Propagación ó Generación:

• Suma:

T1

(t0)

P

G

T1

tCi1  f (tCi , T1, T 2, T 3) Ci +1

M U

(tci+1)

tSi  f (tCi , T1, T 2, T 3)

Ci (tci)

X

T2

S

Si (tsi)

T3

45

Manchester Carry Chain Adder • Si:

ai bi

tCi  t0

(t0)

• Propagación:

tCi1  T1  T 2 • Generación:

• Suma:

T1

Ci +1

tCi1  T1  T 2

P

G

M U

(tci+1)

T1

Ci (tci)

X

T2

S

T3

t Si  T1  T 3 Si (tsi)

46

Manchester Carry Chain Adder 10

01

10

01

10

10

01

10

1

tC7

tC6

tC6

De cada Cout:

tC5

tC4

tC3

tC2

tC0

tC1

tCn  T1  T 2 47

Ejemplo 1: Cálculo del camino crítico en un sumador MCC • EL camino crítico se determina usando el peor escenario ( todos los FAs propagan el acarreo) • Calcular tcN y tsN de la siguiente figura:

t0 N-1

i

2

1

0

tC0

tci  T1  iT 2 tSN  T1  ( N  1)T 2  T 3

tc1  T1  T 2

tc 2  T1  2T 2 tc3  T1  3T 2

tcN  T1  N  T 2 48

Ejemplo 1: Cálculo del camino crítico en un sumador MCC tc1  T1  T 2

• El primer FA genera: • Para los demás FAs:

tc 2  max tc1 , T 1  T 2  tc1  T 2  T 1  2T 2

tc 3  max tc 2 , T 1  T 2  tc 2  T 2  T 1  3T 2 

tci  max tci 1 , T 1  T 2  tci 1  T 2  T 1  iT 2 

tcN  max tcN 1 , T 1  T 2  tcN 1  T 2  T 1  N  T 2

t SN  max tcN 1 , T 1  T 3  tcN 1  T 2  T 1  ( N  1)T 2  T 3 49

Cálculo de los Ci independientes • Se basa en el principio de que todos los operandos Ai y Bi llegan al mismo tiempo. • También consideraremos que el Cin para A0 y B0 es cero. • Volveremos a utilizar las ecuaciones correspondientes a la generación y a la propagación: • P = AXORB • G = AANDB

50

Cálculo de los Ci independientes • Las ecuaciones de forma independiente para cara carry son:

• C0 = 0 • C1 = G0 + P0•C0 • C2 = G1 + P1•C1 = G1 + P1•(G0 + P0•C0) • C3 = G2 + P2•C2 = G2 + P2•(G1 + P1•C1) • C3 = G2 + P2•(G1 + P1•(G0 + P0•C0))

51

Cálculo de los Ci independientes • En función de las ecuaciones de Generación y Propagación: • • • •

C0 = 0 C1 = G0 + P0•C0 C2 = G1 + P1•G0 + P0•P1•C0 C3 = G2 + P2•G1 + P1•P2•G0 + P0•P1•P2•C0

52

Aceleración de la propagación de los Ci

A0, B0

A1, B1

A2, B2

A3, B3

P0, G0

P1, G1

P2, G2

P3, G3

C0

C1

C2

C3

S0

S1

S2

S3 53

Carry LookAhead Adder • Principio: acelerar la propagación del carry mediante el conocimiento previo del mismo. • Se considera que todos los operandos llegan al mismo tiempo. • El objetivo es construir un bloque independiente a la suma que permita conocer, desde el momento t0, en que nivel se va a generar y en que nivel se va a propagar el carry.

54

Carry LookAhead Adder C0

P1

G1

P2

G2

P3

G3

P4

G4

•4 bits de suma: C1

C2

C3

C4

55

Carry Lookahead vs Ripple Carry Ripple Carry Adder Si  X i  Yi  Ci Ci 1  X iYi  X i Ci  Yi Ci Ci 1  XY  Ci ( X i  Yi )

Para un sumador de n-bits

ADGG / LFGP

Critical path

Total delay: 2n+1 56

Carry Lookahead vs Ripple Carry Carry Lookahead Si  X i  Yi  Ci C1  G0  P0C0 C2  G1  P1G0  P1 P0C0

Para un sumador de n-bit

ADGG / LFGP

Total delay: 4 gate delays 57

Sumador/Restador • Recordando: El complemento ‘2 permite representar números positivos y negativos usando el mismo número de bits, también permite tener un único código para el cero. • La resta se obtiene de la siguiente forma: • Se obtiene el complemento ‘2 del número afectado por el signo negativo. • Se realiza una suma directa bit a bit. • Si el Overflow es ‘1’, el resultado de la suma es la magnitud positiva (resultado positivo). • Si el Overflow es ‘0’, el resultado de la suma es la magnitud en complemento a dos (resultado negativo).

58

Sumador/Restador • Ejemplo:

1010 (10) - 0010 (2) (8) ‘2: 0010 1101 + 1 1110 (14)

1010 (10) + 1110 (14) 1 1000 (8) En este caso, como el OV = ‘1’ el resultado es un número positivo y la magnitud del mismo se obtiene directamente 59

Sumador/Restador • Ejemplo:

1010 (10) - 1100 (12) (-2) ‘2: 1100 0011 + 1 0100 (8)

1010 (10) + 0100 (8) 0 1110 (14) 0001 + 1 0010 En este caso, OV = ‘0’ el resultado es un número negativo y la magnitud del mismo se obtiene con el ‘2 60

Sumador/Restador • Diseño del circuito: A0

A1 /B0

‘1’

A2 /B1

A3 /B2

An /B3

/Bn

FA

FA

FA

FA

FA

S0

S1

S2

S3

Sn

OV

61

Sumador/Restador • Diseño del circuito: A0

A1 B0 /B0

B1 /B1

‘0’ ‘1’

A2

B2 /B2

A3

B3 /B3

An

Bn /Bn

OV

Sumador de n bits

S0

S1

S2

S3

Sn

62

Sumador/Restador • Diseño del circuito: R/S

A0 B0

A1 B1

A2 B2

A3 B3

An Bn

OV

Sumador de n bits

S0

S1

S2

S3

Sn 63

Formato BCD • BCD : Binary Coded Decimal • Cada dígito en digital se codifica usando 4 bits • Las combinaciones: 1010 (10), 1011 (11), 1100 (12), 1101 (13), 1110 (14) y 1111 (15) no son utilizadas • Ejemplos: • 9710  1001 0111BCD  1100001b • 4510  0100 0101BCD  101101b

64

BCD a 7-Segment Display

BCD input

• Cada dígito codificado en 4 bits se codifica nuevamente en una representación de 7 bits conforme al display de 7 segmentos:

LSB

LSB

A

a

B

C

BCD to 7-segment Display decoder

b c d e f

D

g

0 1 2 3 4 5 6 65

Suma en BCD • Muy similar a la suma convencional, solo requiere un ajuste cuando la suma excede 9. • Ejemplo: Suma de 2 dígitos en BCD • • • •

Sea X= x3x2x1x0 y Y= y3y2y1y0 números en BCD Sea Z= z3z2z1z0 los bits de suma deseados Si X + Y ≤ 9 la suma no sufre ninguna corrección Si X + Y ≥ 9, el resultado necesita ser representado por 2 palabras de 4 bits (2 dígitos BCD). Los bits que se obtienen de la suma son incorrectos

66

Suma en BCD •

Dos posibles casos cuando: X+Y ≥ 9 1.

La suma no excede 15 (no carry out)

8  4 1 2

1 0 0 0  0 1 0 0 1 1 0 0  1 1 0 1 0 0 1 0

9  5 1 4

1 0 0 1  0 1 0 1 1 1 1 0  1 1 0 1 0 1 0 0

La suma de 4 bits da un resultado en módulo 16. La suma en decimal es módulo 10. La corrección de un decimal de peso superior se obtiene al sumar 6 cuando el resultado excede de 9. 67

Suma en BCD •

Dos posibles casos cuando: X+Y ≥ 9 2.

La suma excede de 15 (carry out)

8  8 1 6

1 0 0 0  1 0 0 0 1 0 0 0 0  1 1 0 1 0 1 1 0

9  9 1 8

1 0 0 1  1 0 0 1 1 0 0 1 0  1 1 0 1 1 0 0 0

9  6 1 5

1 0 0 1  0 1 1 0 0 1 1 1 1  1 1 0 1 0 1 0 1

La suma de 4 bits da un resultado en módulo 16. La suma en decimal es módulo 10. La corrección de un decimal de peso superior se obtiene al sumar 6 cuando el resultado excede de 9. 68

Sumador en BCD de un dígito: Arquitectura X

• Primer aproximación de la implementación en Hardware

Y

Adder

Sum > 9 ?

Z 6

Correction

0

MUX

Cout

Adder

Sum

69

Suma en BCD de dos dígitos • Mas allá de una suma con un dígito: • El Carry-Out de la suma de correcciónentra como Carry-In de la suma de 4 bits del dígito BCD siguiente

Resultado mayor a “1001”? SI + “0110” 38  97 135

0  1 1 0 1 0

Carry-Out de la suma de corrección entra a la segunda suma como Carry-In 0 0 1 1 0

1 0 0 1 1

1 1 1 1 0 1

1 0 1 0 0

0 1 1 1 1

0 1 1 1 0

0 1 1 0 1

Resultado mayor a “1001”? SI + “0110” 70

Suma en BCD de dos dígitos Resultado mayor a “1001”? SI + “0110” 87 

62 149

1  0 1 0 1 0

0 1 1 1 1

0 1 1 1 0

0 0 0 0 0

0 0 1 0 1

1 0 0 0 0

1 1 0 0 0

1 0 1 0 1

Resultado mayor a “1001”? NO No sumar “0110”

71

Suma en BCD de dos dígitos: Arquitectura X1

Z 6

Sum > 9 ?

MUX

Cout

Z 6

0

Correction

Cout

Y0

Adder

Adder

Sum > 9 ?

Sum2

X0

Carry- out

Carry- out

Correction

Y1

0

MUX

Adder

Adder

Sum1

Sum0

72

Optimización del circuito • Caso: cuando la suma + “0110” es requerida • Suma mayor a “1001” • • • • • • •

(10) 1010 (11) 1011 (12) 1100 (13) 1101 (14) 1110 (15) 1111 Carry-out = 1 (suma mayor a 15)

Combinaciones de bits en común: If Z3=1 and (Z2=1 or Z1=1) Or carry-out = 1

Corrección = Carry-Out OR (Z3=1 AND (Z2=1 OR Z1=1) 73

Hardware Architecture X

Y

Cin

Binary Adder

z3

z2

z1

z0

Binary Adder

Cout (S4)

S3

S2

S1

S0

74

Suma en BCD de dos dígitos X1

Y1

X0

Y0

Cin

Binary Adder

z3

z2

z1

z0

Cout

z3

Binary Adder

Cout

S2

S3

S2

S1

S1

Cin

Binary Adder

z2

z1

z0

Binary Adder

S0

S3

S2

S1

S0

S0 75

Multiplicador • Existen varios métodos básicos para el cálculo de la multiplicación de dos números (A, B) de N bits: • Almacenamiento de los 22*N resultados posibles en una memoria ROM y utilizar los 2*N bits para el direccionamiento. • Calcular los 2N funciones lógicas y realizar la suma correspondiente. • En base a la codificación anterior optimizar teniendo en cuenta una relación de dependencia entre los números A y B y el resultado M. 76

Multiplicador • La multiplicación consiste en una serie de operaciones AND entre los distintos bits y una serie de sumas. • Se requieren de 2N compuertas AND. • Se requiere de N sumadores de N bits • Problema: Extensión del signo. • Problema: Tratamiento del signo del operando B.

77

Multiplicación

X

A3 A2 A1 A0

A

B3 B2 B1 B0

B

B

A/0 A/1

A codificado A

(+/-)(A/N)2 i

+

A*B

A/2 A/3 R=  Bi A 2 i 78

Codificación de los productos parciales a3

a2

a1

a0

a3 b0 a2 b0 a1 b0 a0 b0 b0

a3 b1 a2 b1 a1 b1 a0 b1

b1

a3 b2 a2 b2 a1 b2 a0 b2

b2

a3 b3 a2 b3 a1 b3 a0 b3 M7 M 6

M5

M4

M3

b3 M2

M1

M0

Arreglo de compuertas AND ADGG / LFGP

79

Multiplicación A3

A2

A1

A0 B0

A3/0

A2/0

A1/0

A0/0

B1 A3/1

A2/1

A1/1

A0/1

B2 A3/2

A2/2

A1/2

A0/2

B3 A3/3

A2/3

A1/3

A0/3

Matriz de sumas

M7

M6

M5

M4

M3

M2

M1

M0

80

Multiplicación A3/1

A2/1

HA A3/2

A3/3

FA

M7

M6

A2/3

FA

M5

A1/2

FA A1/3

FA

M4

A1/1

FA

A2/2

FA

A3/0

FA

A2/0

FA

A0/1

A1/0

A0/0

HA

A0/2

HA

A0/3

HA

M3

M2

M1

M0

81

Multiplicación • Si suponemos que todos los productos intermedios se calculan en un tiempo T, y que cada sumador realiza su operación en un tiempo ts, el resultado para una multiplicación de dos números de N bits será igual al número de operadores de suma que compone el camino crítico: • Total de células sumadoras: 12 (8 FA, y 4 HA) • CAMINO CRÍTICO: 10 (8 FA, 2 HA)

82

Multiplicación A3/1

A2/1

HA A3/2

A3/3

FA

M7

M6

A2/3

FA

M5

A1/2

FA A1/3

FA

M4

A1/1

FA

A2/2

FA

A3/0

FA

A2/0

FA

A0/1

A1/0

A0/0

HA

A0/2

HA

A0/3

HA

M3

M2

M1

M0

83

Multiplicación • Descripción de la multiplicación sin signo en dos bloques: A3 A2 A1 A0

Codificador A/N

B0 B1 B2 B3

Sumatoria de A/N M7 M6 M5 M4 M3 M2 M1 M0 84

Multiplicación de números con signo • Multiplicación de números negativos: • Representación en complemento a 2.

• Si B es negativo, entonces el último producto parcial se obtiene con el complemento a 2 de A: • B3*23*(/A+1) = 23*(B3*/A+B3) • En este caso si B3=‘1’ se realiza el complemento a 2 y el ajuste. • Si B3=‘0’ el producto parcial es cero y no hay ajuste.

85

Extensión de signo (Si B es negativo) A3

A2

A1

A0 B0

A3/0

A2/0

A1/0

A0/0

B1 A3/1

A2/1

A1/1

A0/1

B2 A3/2

A2/2

A1/2

A0/2

B3 A3/3

A2/3

A1/3

A0/3

Matriz de sumas

M7

M6

M5

M4

M3

M2

M1

M0

86

Multiplicación de números con signo • Multiplicación de números negativos: • Si A y B son negativos, se representan en ‘2 y se expande el resultado de cada producto intermedio copiando el MSb. También se aplica el ajuste anterior (B negativo) • Si sólo A es negativo solamente se expande el resultado de cada producto intermedio copiando el MSb.

87

Multiplicación • Realice los siguientes ejercicios: 0 1 0 1 (5) X 0 1 1 0 (6)

1 1 0 1 (-3) X 0 1 0 1 (5)

1 0 1 1 (-5) X 1 0 1 0 (-6)

88

Multiplicación de números con signo • Solución de los ejercicios: Extensión de signo 0 1 0 1 (5) X 0 1 1 0 (6) 0000 01010101-0000---

1 1 0 1 (-3) X 0 1 0 1 (5) 1111101 000000 11101 - 0000- - -

0011110

1 1 1 0 0 0 1 (-15) 0 0 1 1 1 1 0 (30)

(30)

Complemento a 2

1 0 1 1 (-5) X 1 0 1 0 (-6) 0000000 111011 00000 - 0101 - - -

89

Multiplicación de números con signo • Efectuar el corrimiento hacia la izquierda y extensión de signo. • El último operando se representa en complemento a 2 de A si B es negativo (MSB = ‘1’), en otro caso, el último operando es cero:

 A  bN 1 2 N 1  A  1  2 N 1 bN 1 A  bN 1  • Físicamente, la implementación consiste complementar el operando A y sumar el término:

en

bN 1 2 N 1 90

Multiplicación de números con signo

-a3 b3

a3

a2

a1

a0

-a3 b0

a2 b0

a1 b0

a0 b 0

-a3 b1

a2 b1

a1 b1

a0 b1

-a3 b2

a2 b 2

a1 b2

a0 b2

a2 b3

a1 b 3

a0 b3

b0

b1 b2

b3

b3 M7

M6

M5

M4

M3

M2

M1

M0 91

Multiplicación de números con signo A3

A2

A1

A0 B0

A3/0

A3/0

A2/0

A1/0

A0/0

B1 A3/1

A3/1

A2/1

A1/1

A0/1

B2 A3/2

A3/2

A2/2

A1/2

A0/2

B3 A3/3

A2/3

A1/3

A0/3

23B3

Matriz de sumas

M7

M6

M5

M4

M3

M2

M1

M0

92

Multiplicación de números con signo • La codificación de los productos parciales se realiza en paralelo. N 1 b 2 • La suma del término: N 1 se realizará en el arreglo sumador. • El camino crítico se compone de una AND y una compuerta NOT. • La velocidad del multiplicador dependerá en gran medida del bloque de sumas

93

Multiplicación • Para acelerar el resultado de la multiplicación se debe optimizar el camino crítico, es decir, el camino mas largo que deben recorrer las entradas A y B para generar el resultado M. • En este caso, todos los productos intermedios estarán calculados al mismo tiempo por lo que no representan parte del camino crítico. • El camino crítico estará definido por la suma de productos intermedios mas grande.

94

Multiplicación • Con el fin de acelerar la suma de multi-operandos, es mas conveniente optimizar desde el punto de vista de la palabra (y no del bit). • El incremento de velocidad de cálculo usando este método no implica necesariamente aumentar la complejidad material debido a que el número de FA es fijo. • Solo si se requiere optimizar velocidad, la dimensión de bit (columna) será considerada.

95

Multiplicación • Estructura de sumas de 3 bits: • Estrictamente hablando, un FA realiza una suma de 3 bits ( A, B, Cin) y nos arroja un resultado sobre 2 bits ( S, Cout).

• Al analizar la estructura del multiplicador podemos darnos cuenta de que un operador de suma de 3 bits podría reducir la complejidad material (CSA). • Ejemplo: suma de A2/0, A1/1, A0/2

96

Carry Save Adders (CSA) • En un CSA, el carry no es usado en la suma que le corresponde sino que se sumará en el renglón siguiente. • El CSA puede ser aplicado en todos los renglones excepto en el último, en donde se requiere de un sumador rápido que procese el carry final mediante un sumador rápido o de vector resultante. • Ventajas: • Las sumas para posiciones de bit distintas dentro del mismo renglón son independientes entre ellas y generan un carry en paralelo. • Al optimizar el desempeño de la suma se optimiza de forma directa el desempeño del multiplicador.

97

Carry Save Adder • Se tiene el siguiente esquema: A3 B3 C3 A3 B3 C3 A3 B3 C3 A3 B3 C3

S3

FA

Co3

S3

FA

Co3 S3

FA

Co3

N

A

N

Co

N

B

C.S.A N

N

S

C

S3

FA

Co3

A+B+C=S+2 CY

98

Carry Save Adder • Si el Ripple Carry Adder  • CY0 = C1; CY1 = C2; CY2 = C3

• El CSA realiza la suma de 3 operandos (A, B y C) y entrega 2 resultados: • Una palabra de suma, S, del mismo orden 2i • Una palabra de carry, CY, de orden 2i+1

A+B+C=S+2 CY 99

Carry Save Adder • Lógica redundante (suma de 3 palabras de N bits): X+Y+Z

X+Y+Z X= 0 0 1 0 1 0 1 0 1 Y= 0 1 0 1 0 1 1 1 0

X= 0 0 1 0 1 0 1 0 1

Y= 0 1 0 1 0 1 1 1 0 Z= 0 0 1 0 0 0 1 0 1

r=100000011 Z= 0 0 1 0 0 0 1 0 1 R= 1 0 1 0 0 1 0 0 0

Suma

S=

010111110

C= 0 0 1 0 0 0 1 0 1

carry

R= 0 1 0 1 0 0 1 0 0 0 100

Carry Save Adder Multiplicación usando un CSA: 0 1 0 0 1 A=9 x 1 1 1 0 1 B=-3 0 1 0 0 1 A1=A 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1

A2=0 A3=A A4=A A5=-A

0 1 0 0 1 A1 A2 + 0 0 0 0 0 A3 + 0 1 0 0 1 + 0 + 0

0 + 0 0 + 1 0

0 1 0 1 1 0 1 S1 0 0 0 0 0 0 CY1 A4 1 0 0 1 1 1 0 0 1 0 1 S2 CY2 0 0 1 A5 1 1 1

1 0 0 0 0 0 1 0 1 S3 CY3 + 0 1 1 1 1 1 1 1 0 0 1 0 1 R=-27 101

Principio del CSA:

0 0 0 0 0 0 0 0

• Diseño de una estructura basada en un FA que cuenta el número de ‘1’s de una palabra de 8 bits. • Solución: Controlar los corrimientos hacia la izquierda (potencias de 2) generados durante la suma multi-operandos. 0 0 HA 0 0 0 0 1 FA 0 1 FA 1 1 1 1 FA HA 1 0 2 FA 1 2 2 HA 3 102

CSA • Utilización de CSA para una suma de N operandos: • Suma en serie:

A1 A2 A3

CSA

CSA

A4

CSA

A5

CSA

A6

CSA

SUMADOR RÁPIDO

A7

103

CSA • Utilización de CSA para una suma de N operandos: • Suma en paralelo:

A1 A2 A3

A4 A5 A6

A7 A8 A9

CSA

CSA

CSA

CSA

SUMADOR RÁPIDO

CSA

CSA CSA 104

Sumador Rápido • El sumador rápido o de vector resultante puede ser implementado con un carry Save Adder o on un Ripple Carry Adder de forma indistinta. • Ejemplo de un Carry Save VMA (Vector Merging Adder):

A3 A2 A1 A0

HA

HA

HA

HA

HA

HA

HA

HA

HA HA 105

Sumador Rápido • VMA implementado con un Ripple Carry Adder:

FA

FA

FA

HA

A3

A2

A1

A0

106

Sumador Rápido • Mezcla de las 2 arquitecturas:

FA

HA

HA

HA

A3

A2

FA

A1

HA

A0 107

Multiplicación con CSA • En la suma CSA, la propagación se realiza solo en la dimensión de la palabra (renglón) • Propagación en el sentido de las columnas se realiza al final usando el vector resultante.

108

Multiplicación con CSA • La velocidad (considerando un arreglo en árbol): • Tp (árbol) + Tp (sumador rápido)  log(1.5N) + Tp(sumador rápido)

• Tamaño (considerando estructura en árbol): • Se requere (N-2) CSA.

• La técnica usando CSA ofrece el mejor compromiso de Velocidad/Tamaño para la suma multioperandos.

109

Multiplicador Serie-Paralelo • La Multiplicación puede ser re-estructurada en base a operaciones simples a realizarse de forma sucesiva o iterativa. • Esto permite reducir drásticamente la complejidad material del circuito. • Arquitectura Serie-Paralelo: • • • •

Multiplicar el operando “A” con cada bit del operando “B” Recorrer hacia la izquierda cada producto parcial Acumular los productos parciales conforme se generan Utilizar un circuito síncrono para controlar el proceso

110

Multiplicador Serie-Paralelo

0 1 1 0

x 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0

0 0 0 0 0 1 0 1 0

Operando “A” Operando “B”

“A” x B0 “A” x B1 “A” x B2 “A” x B3

Shift a la Izquierda según la potencia de n2 que corresponda a cada bit de “B”

1 0 1 1 1 0 0 (-36)

El resultado es producto de una suma de todos los productos parciales 111

Multiplicador Serie-Paralelo 0

1

1

0

1

0

1

0

0

0

0

0

Shift

0

0

0

0

Add

0

1

1

0

0

1

1

0

0

0

0

0

0

0

1

1

1

0

1

0

1

0

1

1

x

0 1 1 0

x 1 0 1 0 0 0 0 0 0 0 0

+

0 0 0 1 1 0

0 0 0 0 0

+

1 0 1 0 1 0 1 1 1 0 0 (-36)

+

Shift 0

Add Shift

0

0

Add Shift

1

0

0

ADD 112

Multiplicador Serie-Paralelo 0

1

1

0

1

0

1

0

0

0

0

0

Shift

0

0

0

0

Add

0

1

1

0

0

1

1

0

0

0

0

0

0

0

1

1

1

0

1

0

1

0

1

1

x

Producto parcial = 0 +

Producto parcial = A +

Producto parcial = 0 Producto parcial = A

+

Shift 0

Add Shift

0

0

Add Shift

1

0

0

ADD 113

Arquitectura del circuito 0

B (serial)

A

MUX

Fast Adder

Shift / Accumulation Register

114

Arquitectura del circuito • El multiplicador Serie-Paralelo es un circuito secuencial • La arquitectura consiste de: • Un multiplexor: • Producto Parcia = 0, si Bn = ‘0’ • Producto Parcial = A, si Bn = ‘1’

• Sumador: suma la salida del multiplexor (A ó 0) que corresponde al producto parcial Bn con el contenido del registro (Producto Parcial previamente acumulado correspondiente a Bn-1) • Shift / accumulation register: Almacena el resultado en el acumulador y realiza el corrimiento (shift)

• En lugar de hacer corrimientos hacia la izquierda (como se haría en la multiplicación normal) se hace un corrimiento a la derecha del contenido del acumulador

115

Diseño del circuito • Requerimientos para un multiplicador de n-bits • Un registro de n-bits para el multiplicando • Un registro de n-bits para el multiplicador • Un registro de corrimiento para el producto de 2n-bits

• El registro del producto también se usa como registro acumulador para almacenar las sumas de los productos parciales conforme son generados • IDEA: al usar una arquitectura iterativa de este tipo, el corrimiento dentro del registro de 2n-bits es hacia la derecha. • ¿explique porqué?

116

Arquitectura del circuito Ad : Add enable signal Sh : Shift enable signal C : Carry out signal M: Multiplier bit

Shift sense Accumulator

CLK

Multiplier (B)

M C

Adder

Ad Control (FSM)

Start CLK

Sh Multiplicand (A) 117

Arquitectura del circuito: Ejemplo • Multiplicar 13x11 = 143 (“1101” x “1011”= “10001111”) Contenido inicial del registro

0 0 0 0 0 1

( " A" en M  1)

1 1 0 1 1

Shift

0 0 1 1 1 1

Despúes de sumar

1

Shift

0 1

M

0 1

Después de sumar ( " A" en M  1)

0 1 1

0 1 1

0 1 1

0 1 1

0 1

M

0 1

0 0 1 1 1 1

0 1

0 0 1 1 1 1

0

M

0 0 1 1 1 1

M

(Salto de suma en M  0) Shift

0 0 1

( " A" en M  1)

1 1

Después de sumar

1

Shift (Resultado final)

0 1

0 1

0 0 0 1 1 1 1 1

Línea divisoria entre el producto y el multiplicador

0 0 0 1 1 1 1 118

Arquitectura del circuito • Pseudo-código

• Máquina de Estados

A, B son los operandos (n bits) P es el registro en donde se almacenará el producto final P = 0; // inicialización for i=0 to n-1 do if bi = 1 then P = P + A; end if; left-shift A; end for;

119

Desempeño: • El cálculo de la multiplicación a través de un arreglo serie-paralelo es más pequeño que un multiplicador paralelo tradicional • Serie-paralelo: una multiplicación en B ciclos de reloj • Paralelo: una multiplicación por ciclo de reloj

• Sin embargo, el camino crítico es mas pequeño en el arreglo serie-paralelo  El circuito puede operar a frecuencias de reloj superiores

120

División • La división, como todos sabemos, es una serie de divisiones sucesivas. • El objetivo es ver, para A/B cuantas veces cabe el número B en A. O en otras palabras por qué número tengo que multiplicar B para obtener A. • Se obtiene un cociente y un residuo.

121

Principio del algoritmo: 0 0 0 0 1 1 1 1

1 5 9 1 4 0

Divisor

9 5 0 4 5 5

Pseudo-código Residuo = 0; for i=0 to n-1 do Left-shift (Residuo & Dividendo); if Residuo ≥ Divisor then Cociente(i) = 1; Residuo = Residuo - Divisor; else Cociente(i) = 0; end if; end for;

1001 1 0 0 0 1 1 0 0

Cociente Dividendo

1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 1

1 0 1

Residuo

122

Architectura • La división es vista como una serie de restas y corrimientos • En lugar de recorrer hacia la derecha el divisor después de una resta, se recorre a la izquierda • En lugar de usar un registro separado para almacenar el cociente, éste será generado bit a bit e introducido por la orilla derecha del registro del dividendo en cada corrimiento a la izquierda

123

División • Ejemplo:

101 110 100010 -110 101 -000 1010 -110 100

Cociente Resta

Compara Resta

Residuo

124

Divisor • Circuito: Dividend register

Sub

Sh

La señal “C” indica si el divisor es mayor al conjunto de bits del dividendo con los que fue restado, y va conformando bit a bit el cociente Start

Subtractor and Comparator

C

control

rst

C = 0, no resta C = 1, resta

clk

0 Divisor register

Ov (optional)

125

Ejemplo de la operación:

Contenido inicial del registro del dividendo

Dividir: 10001100/1001 Q= 1111 R=101

(Saltar resta en C  0) Shift

t 0

0 1 0 0 0 1 1 0 0

1 0 0 1 C0 1 0 0 0 1 1 0 0 0 t 1

(- divisor en C  1) Después de la resta

1 0 0 1 0 1 0 0 0 1 0 0 0

Shift (- divisor en C  1)

1 0 0 0 1 0 0 0 1 1 0 0 1

Después de la resta

0 1 0 0 0 0 0 0 1

Shift (- divisor en C  1)

1 0 0 0 0 0 0 1 1 1 0 0 1

Después de la resta Shift

0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1

(- divisor en C  1) Después de la resta

1 0 0 1 C 1 0 0 1 0 1 0 1 1 1

Shift

0 1 0 1 0 1 1 1 1

Residuo

C 1 t2 C 1 t 3 C 1 t4

t 5

Cociente

126