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)
2
)()()(1
0
knxkhnyM
k
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:
4
1
0
2N
i
iBiX
i 3 2 1 0
15 1 1 1 1
14 1 1 1 0
: : : : :
2 0 0 1 0
1 0 0 0 1
0 0 0 0 0
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
9
0-1-2-3-4-5-6-7 7654321
0
1
2
3
4
5
6
7
2 + 4 = 6
2 - 4 = 6 (-2)
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 negativomás que un número positivo. Ejemplo: Para n = 4 podemosrepresentar los valores [7 .. –8]
10
Representación de Números Negativos
11
N
Enteros
Positivos
(Todos los
sistemas)
-N
Enteros Negativos
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 ----
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) => +7 (0111)
• (+5)+(+6) => +11 (1011)
• (+5)+(-6) => -1 (1111)
• (-5)+(+6) => +1 (0001)
• (-3)+(-4) => -7 (1001)
• (-5)+(-6) => -11 (0101)
14
Ejemplos
• Complemento a 1
• (+3)+(+4) => +7 (0111)
• (+5)+(+6) => +11 (1011)
• (+5)+(-6) => -1 (1110)
• (-5)+(+6) => +1 (0000) ????
• (-3)+(-4) => -7 (0111) ????
• (-5)+(-6) => -11 (0011) ????
15
Igual que el complemento a 2
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
011010010150
0000101080
0110001070
20
• Un “overflow” puede ocurrir si los 2 números a sumar son positivos o negativos
• Ejemplo: suma de 2 números de 8-bits
010101101150
0000110180
0101110170
Overflow en números con signo
011010010150
0000101080
0110001070
21
• 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
010101101150
0000110180
0101110170
Overflow en números con signo
011010010150
0000101080
0110001070
00000010:Carry
22
• 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)
010101101150
0000110180
0101110170
00001101:Carry
Sumadores Binarios
• Operación aritmética básica en el diseño de circuitos digitales máscomplejos
• ClasificaciónTipo 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)
24
Entradas SalidasA B Cout S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
ABC
BABABAS
A
BS
Cout
HA
BA
S
Cout
Sumador Completo (Full Adder)
• Circuito aritmético que genera la suma de tres bits (entradas A y B, y el bit carry)
25
Cin(Del FA anterior)
Cout(Hacia el
siguiente FA)
S
BA
FA
Sumador Completo (Full Adder)
26
Entradas Salidas
A B Cin Cout S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
)(
)(
BACinABCout
BABACinABCout
BCinACinABCout
CinBAS
ABCinCinBACinBACinBAS
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 arqutiecturasArquitecturas en Serie
Tamaño
VelocidadArquitecturas en Paralelo
Velocidad
Tamaño
28
Sumador en Serie
• Implementación de un sumador eficiente en tamaño
29
DQ
CLK
AiBi
Si
Cin CoutFAA = An-1, An-2, …,A0
B = Bn-1, Bn-2, …,B0
Condición: entradas sincronizadas
por medio de la señal CLK
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
31
B0A0
c0
s0
B1A1
c1
s1
B2A2
c2
s2
Bn-1An-1
Cn-1
Sn-1
FAFAFAFACn
Cin 0 1 1 0
A 1 0 1 1
B 0 0 1 1
S 1 1 1 0
Cout 0 0 1 1
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 sumatotal
•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)
33
FA FA FAFA
S0 S1 S2 S3 S4
A3 B3A2 B2A1 B1A0 B0
C0 C1 C2 C3 C4
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
34
FAI FAp FAIFAp
S3S2S1S0 S4
A0 B0 A1 B1 A2 B2 A3 B3
C0 C2 C4C3C1
Ripple Carry Adder
•Análisis de la suma de 3 bits:
35
Ai Bi Ci Ci+1
0 0 0
0 0 1
0
0
Ai = Bi Generación
Ci+1 = Gi = Ai AND Bi
0 1 0
0 1 1
1 0 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
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:
• Célula P
• Célula G
• Multiplexor
• Célula S
37
P G
S
M
U
X
ai bi (t0)
T1T1
Ci (tci)
T3
Si (tsi)
T2
Ci +1
(tci+1)
Optimización del sumador
• Célula:
38
P G
S
M
U
X
ai bi (t0)
T1T1
Ci (tci)
T3
Si (tsi)
T2
Ci +1
(tci+1)
Propagación
Generación
Cálculo de la suma
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
•Caso intermedio: Al menos una célula genera:
• 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
11 01 10 00 10 10 01 11
Manchester Carry Chain Adder
•Peor caso: todas las células propagan: La suma de los bits n, requieren del carry del nivel n-1.
• El tiempo de la suma de 8 bits es 8t.
43
10 01 10 01 10 10 01 10
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 tienen el mismo tiempo de propagación T1.
• Los operandos ai, bi están disponibles en t0.
• El carry de entrada Ci esta disponible en el tiempo tci.
44
P G
S
M
U
X
ai bi (t0)
T1T1
Ci (tci)
T3
Si (tsi)
T2
Ci +1
(tci+1)
Manchester Carry Chain Adder
• Propagación ó Generación:
• Suma:
45
P G
S
M
U
X
ai bi (t0)
T1T1
Ci (tci)
T3
Si (tsi)
T2
Ci +1
(tci+1)
)3,2,1,(1 TTTtft CiCi
)3,2,1,( TTTtft CiSi
Manchester Carry Chain Adder
• Si:
• Propagación:
• Generación:
• Suma:
46
P G
S
M
U
X
ai bi (t0)
T1T1
Ci (tci)
T3
Si (tsi)
T2
Ci +1
(tci+1)
0ttCi
211 TTtCi
211 TTtCi
31 TTtSi
Manchester Carry Chain Adder
47
1
10 01 10 01 10 10 01 10
tC1tC2tC3tC4tC5tC6tC6tC7
tC0
21 TTtCn De cada Cout:
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:
48
tC0
0t
211 TTtc
2212 TTtc
2313 TTtc
012iN-1
21 iTTtci
32)1(1 TTNTtSN
21 TNTtcN
Ejemplo 1: Cálculo del camino crítico en un sumador MCC
•El primer FA genera:
•Para los demás FAs:
49
211 TTtc
32)1(1231,max
21221,max
21221,max
231221,max
221221,max
11
11
11
223
112
TTNTTtTTtt
TNTTtTTtt
iTTTtTTtt
TTTtTTtt
TTTtTTtt
cNcNSN
cNcNcN
cicici
ccc
ccc
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
53
A0, B0
P0, G0
C0
S0
A1, B1
P1, G1
C1
S1
A2, B2
P2, G2
C2
S2
A3, B3
P3, G3
C3
S3
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 vs Ripple Carry
)(1
1
iiii
iiiiiii
iiii
YXCXYC
CYCXYXC
CYXS
ADGG / LFGP 56
Para un sumador de n-bits
Total delay: 2n+1
Ripple Carry Adder
Critical path
Carry Lookahead vs Ripple Carry
0010112
0001
CPPGPGC
CPGC
CYXS iiii
ADGG / LFGP 57
Carry Lookahead
Para un sumador de n-bit
Total delay: 4 gate delays
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:
59
1010
0010-
(10)
(2)
(8)
‘2: 0010
1101
+ 1
1110
1010
1110+
(10)
(14)
(8)
(14)
1 1000
En este caso, como el OV = ‘1’ el
resultado es un número positivo y la
magnitud del mismo se obtiene
directamente
Sumador/Restador
• Ejemplo:
60
1010
1100-
(10)
(12)
(-2)
‘2: 1100
0011
+ 1
0100
1010
0100+
(10)
(8)
(14)
(8)
0 1110
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
Sumador/Restador
• Diseño del circuito:
61
FA FA FA FA FA
A0 A1 A2 A3 An
/B0 /B1 /B2 /B3 /Bn
‘1’
S0 S1 S2 S3 Sn
OV
Sumador/Restador
• Diseño del circuito:
62
A0 A1 A2 A3 AnB0
/B0
B1
/B1
B2
/B2
B3
/B3
Bn
/Bn
‘0’
‘1’
S0 S1 S2 S3 Sn
OVSumador de n bits
Sumador/Restador
• Diseño del circuito:
63
A0 A1 A2 A3 An
S0 S1 S2 S3 Sn
OVSumador de n bits
B0 B1 B2 B3 BnR/S
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
to 7-segment
Display
decoder
A
B
C
D
a
b
d
e
f
g
c
LSB LSB
65
• Cada dígito codificado en 4 bits se codifica nuevamente en una representación de 7 bits conforme al display de 7 segmentos:
BC
D i
np
ut
0123456
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
01001
011
0011
0010
0001
21
4
8
67
• Dos posibles casos cuando: X+Y ≥ 91. La suma no excede 15 (no carry out)
00101
011
0111
1010
1001
41
5
9
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.
Suma en BCD
01101
011
00001
0001
0001
61
8
8
68
• Dos posibles casos cuando: X+Y ≥ 92. La suma excede de 15 (carry out)
10101
011
11110
0110
1001
51
6
9
00011
011
01001
1001
1001
81
9
9
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.
Sumador en BCD de un dígito: Arquitectura
Adder
Adder
MUX
Sum > 9 ?
X Y
Z
Sum
Correction
6 0
Cout
69
•Primer aproximación de la implementación en Hardware
Suma en BCD de dos dígitos
135
97
38
70
• 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
101011001
01100110
11111011
11101001
00011100
1
Resultado mayor a “1001”?
SI
+ “0110”
Carry-Out de la suma de corrección entra a
la segunda suma como Carry-In
Resultado mayor a
“1001”? SI
+ “0110”
Suma en BCD de dos dígitos
149
62
87
71
100100101
00000110
10010111
01000110
11100001
Resultado mayor a “1001”?
NO
No sumar “0110”
Resultado mayor a
“1001”? SI
+ “0110”
Suma en BCD de dos dígitos: Arquitectura
Adder
Adder
MUX
Sum > 9 ?
X0 Y0
Z
Sum0
Correction
6 0
Cout
Adder
Adder
MUX
Sum > 9 ?
X1 Y1
Z
Sum1
Correction
6 0
Cout
Sum2
Carry- outCarry- out
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)
73
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)
Suma en BCD de dos dígitos
Binary Adder
Binary Adder
X0 Y0
z3 z2 z1 z0
S0S1S2S3
Cout
CinBinary Adder
Binary Adder
X1 Y1
z3 z2 z1 z0
S0S1S2S3Cout
Cin
S0S1
S2
75
Multiplicador
•Existen varios métodos básicos para el cálculo de lamultiplicación de dos números (A, B) de N bits:
• Almacenamiento de los 22*N resultados posibles en unamemoria ROM y utilizar los 2*N bits para el direccionamiento.
• Calcular los 2N funciones lógicas y realizar la sumacorrespondiente.
• En base a la codificación anterior optimizar teniendo en cuentauna relación de dependencia entre los números A y B y elresultado M.
76
Multiplicador
• La multiplicación consiste en una serie deoperaciones AND entre los distintos bits y una seriede 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
78
AA*B
B
A codificado
(+/-)(A/N)2 i+
X
A
B
A3 A2 A1 A0
B3 B2 B1 B0
A/0
A/1
A/2
A/3
R= Bi A 2 i
Codificación de los productos parciales
ADGG / LFGP 79
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 b3
M7 M6 M5 M4 M3 M2 M1 M0
Arreglo de compuertas AND
Multiplicación
80
A3 A2 A1 A0
B0
B1
B2
B3
A0/0A1/0A2/0A3/0
A0/1A1/1A2/1A3/1
A0/2A1/2A2/2A3/2
A0/3A1/3A2/3A3/3
Matriz de sumas
M7 M6 M5 M4 M3 M2 M1 M0
Multiplicación
81
HA
A1/0A0/1 A0/0
FA
A1/1 A2/0
A0/2
A1/3
A1/2
A2/1 A3/0A3/1
A2/2
A0/3A2/3
A3/2
A3/3
M7 M6 M5 M4 M3 M2 M1 M0
FAHA
HAFAFAFA
HAFAFAFA
Multiplicación
• Si suponemos que todos los productos intermedios se calculan en untiempo 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 caminocrítico:
• Total de células sumadoras: 12 (8 FA, y 4 HA)
• CAMINO CRÍTICO: 10 (8 FA, 2 HA)
82
Multiplicación
83
HA
A1/0A0/1 A0/0
FA
A1/1 A2/0
A0/2
A1/3
A1/2
A2/1 A3/0A3/1
A2/2
A0/3A2/3
A3/2
A3/3
M7 M6 M5 M4 M3 M2 M1 M0
FAHA
HAFAFAFA
HAFAFAFA
Multiplicación
•Descripción de la multiplicación sin signo en dos bloques:
84
Codificador A/N
A3 A2 A1 A0
B0
B1
B2
B3
Sumatoria de A/N
M7 M6 M5 M4 M3 M2 M1 M0
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 seobtiene 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)
86
A3 A2 A1 A0
B0
B1
B2
B3
A0/0A1/0A2/0A3/0
A0/1A1/1A2/1A3/1
A0/2A1/2A2/2A3/2
A0/3A1/3A2/3A3/3
Matriz de sumas
M7 M6 M5 M4 M3 M2 M1 M0
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 cadaproducto intermedio copiando el MSb. También se aplica el ajuste anterior (Bnegativo)
• Si sólo A es negativo solamente se expande el resultado de cada productointermedio copiando el MSb.
87
Multiplicación
•Realice los siguientes ejercicios:
88
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)
Multiplicación de números con signo
•Solución de los ejercicios:
89
1 1 0 1 (-3)
X 0 1 0 1 (5)
1 0 1 1 (-5)
X 1 0 1 0 (-6)
0 0 0 0
0 1 0 1 -
0 1 0 1 - -
0 0 0 0 0 0 -
1 1 1 1 1 0 1
1 1 1 0 1 - -
0 0 0 0 - - -
1 1 1 0 0 0 1 (-15)
0 1 0 1 (5)
X 0 1 1 0 (6)
0 0 0 0 - - -
0 0 1 1 1 1 0 (30)
0 0 0 0 0 0 0
1 1 1 0 1 1 -
0 0 0 0 0 - -
0 1 0 1 - - -
0 0 1 1 1 1 0 (30)
Complemento a 2
Extensión de signo
Multiplicación de números con signo
•Efectuar el corrimiento hacia la izquierda y extensiónde signo.
•El último operando se representa en complemento a 2de A si B es negativo (MSB = ‘1’), en otro caso, elúltimo operando es cero:
•Físicamente, la implementación consiste encomplementar el operando A y sumar el término:
90
11
11
1 212
NN
NN
N bAbAbA
1
12
N
Nb
Multiplicación de números con signo
91
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 b3
b3
M7 M6 M5 M4 M3 M2 M1 M0
Multiplicación de números con signo
92
A3 A2 A1 A0
B0
B1
B2
B3
A0/0A1/0A2/0A3/0
A0/1A1/1A2/1A3/1
A0/2A1/2A2/2A3/2
A0/3A1/3A2/3A3/3
Matriz de sumas
M7 M6 M5 M4 M3 M2 M1 M0
A3/0
A3/1
A3/2
23B3
Multiplicación de números con signo
• La codificación de los productos parciales se realizaen paralelo.
• La suma del término: se realizará en elarreglo sumador.
•El camino crítico se compone de una AND y unacompuerta NOT.
• La velocidad del multiplicador dependerá en granmedida del bloque de sumas
93
1
12
N
Nb
Multiplicación
•Para acelerar el resultado de la multiplicación sedebe optimizar el camino crítico, es decir, el caminomas largo que deben recorrer las entradas A y Bpara generar el resultado M.
•En este caso, todos los productos intermediosestarán calculados al mismo tiempo por lo que norepresentan parte del camino crítico.
•El camino crítico estará definido por la suma deproductos intermedios mas grande.
94
Multiplicación
•Con el fin de acelerar la suma de multi-operandos,es mas conveniente optimizar desde el punto devista de la palabra (y no del bit).
•El incremento de velocidad de cálculo usando estemétodo no implica necesariamente aumentar lacomplejidad material debido a que el número de FAes fijo.
•Solo si se requiere optimizar velocidad, ladimensió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 podemosdarnos cuenta de que un operador de suma de 3 bitspodrí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 quese 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 finalmediante 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 eldesempeño del multiplicador.
97
Carry Save Adder
•Se tiene el siguiente esquema:
98
A3
B3
S3
C3
Co3FA
A3
B3
S3
C3
Co3FA
A3
B3
S3
C3
Co3FA
A3
B3
S3
C3
Co3FA
N
N
N
N
NC.S.A
A
B
C
Co
S
A+B+C=S+2 CY
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
99
A+B+C=S+2 CY
Carry Save Adder
• Lógica redundante (suma de 3 palabras de N bits):
100
X + Y + Z
r = 1 0 0 0 0 0 0 1 1
Z= 0 0 1 0 0 0 1 0 1
X= 0 0 1 0 1 0 1 0 1
Y= 0 1 0 1 0 1 1 1 0
R= 1 0 1 0 0 1 0 0 0
X + Y + Z
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
S= 0 1 0 1 1 1 1 1 0
C= 0 0 1 0 0 0 1 0 1
R= 0 1 0 1 0 0 1 0 0 0
Suma
carry
Carry Save Adder
101
Multiplicación usando un CSA:
0 1 0 0 1
x 1 1 1 0 1
0 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 1
1 0 1 1 1
A=9
B=-3
A1=A
A2=0
A3=A
A4=A
A5=-A
0 1 0 0 1
+ 0 0 0 0 0
+ 0 1 0 0 1
0 1 0 1 1 0 1
+ 0 0 0 0 0 0 0
+ 0 1 0 0 1
0 1 1 0 0 1 0 1
+ 0 0 0 0 1
+ 1 0 1 1 1
1 0 0 0 0 0 1 0 1
+ 0 1 1 1
1 1 1 1 0 0 1 0 1
A1
A2
A3
S1
CY1
A4
S2
CY2
A5
S3
CY3
R=-27
Principio del CSA:
• 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.
102
FA
FA
FA
FA
HA
HA
HA
000
000
0
0
000
0
0
0
1
0
1
11
1 1
1
2
2
0
1
2
3
CSA
•Utilización de CSA para una suma de N operandos:• Suma en serie:
103
CSA CSA CSA CSA SUMADOR
RÁPIDO
A1
A2
A3
CSA
A4 A5 A6 A7
CSA
•Utilización de CSA para una suma de N operandos:• Suma en paralelo:
104
CSA CSA CSA CSA SUMADOR
RÁPIDO
CSA
CSA
CSA
A1A2A3
A4A5A6
A7A8A9
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):
105
HA
HA
HA
HA
HA
HA
HA
HA
HA
HA
A0
A1
A2
A3
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 multi-operandos.
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
111
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)
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”
El resultado es producto de una suma de todos los productos parciales
Multiplicador Serie-Paralelo
112
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)
0 1 1 0
x 1 0 1 0
0 0 0 0 Shift
0 0 0 0 Add
+ 0 1 1 0 Shift
0 1 1 0 0 Add
+ 0 0 0 0 Shift
0 0 1 1 0 0 Add
+ 1 0 1 0 Shift
1 0 1 1 1 0 0 ADD
Multiplicador Serie-Paralelo
113
0 1 1 0
x 1 0 1 0
0 0 0 0 Shift
0 0 0 0 Add
+ 0 1 1 0 Shift
0 1 1 0 0 Add
+ 0 0 0 0 Shift
0 0 1 1 0 0 Add
+ 1 0 1 0 Shift
1 0 1 1 1 0 0 ADD
Producto parcial = 0
Producto parcial = A
Producto parcial = 0
Producto parcial = A
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
Adder Control
(FSM)
Multiplicand (A)
Multiplier (B)Accumulator
Shift sense
CLK
CLK
Ad
M
Sh
C Start
117
Ad : Add enable signalSh : Shift enable signalC : Carry out signalM: Multiplier bit
Arquitectura del circuito: Ejemplo
• Multiplicar 13x11 = 143 (“1101” x “1011”= “10001111”)
118111100010final) (ResultadoShift
111110001sumar de Después
10111)Men A"" (
M111100100Shift
0)Men suma de (Salto
M011110010Shift
101111001sumar de Despúes
10111)Men A"" (
M101101100Shift
110110110sumar de Después
10111)Men A"" (
M110100000registro del inicial Contenido
Línea divisoria entre el producto y el multiplicador
Arquitectura del circuito
• Pseudo-código
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;
• Máquina de Estados
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:
122
Cociente
001100011001
11110000
1001
1001
10001
1001
00001
1001
0111
101
Divisor Dividendo
Residuo
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;
5
54
05
9
0419
51
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:
124
1 1 0 1 0 0 0 1 01 1 0-
1 0 10 0 0-1 0 1 0
1 1 0-
1 0 0
1 0 1
Compara
Residuo
Resta
Cociente
Resta
Divisor
•Circuito:
125
Subtractor and
Comparator
Dividend register
Divisor register
0
control
Start
clk
rst
ShSub
C
Ov (optional)
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
C = 0, no resta
C = 1, resta
Ejemplo de la operación:
5111101010Shift
111010100resta la de Después
110011)Cen divisor (-
4111001110Shift
110011100resta la de Después
1C10011)Cen divisor (-
3110000001Shift
100000010resta la de Después
1C10011)Cen divisor (-
2100010001Shift
000100010resta la de Después
1C10011) Cen divisor (-
1000110001Shift
0C10010)Cen resta(Saltar
0001100010dividendo del registro del inicial Contenido
t
C
t
t
t
t
t
126
Dividir:
10001100/1001
Q= 1111 R=101
CocienteResiduo