Download Sistemas Numéricos

Unidad 1
SISTEMAS NUMERICOS
Objetivos
•
•
•
•
•
•
•
•
•
Comprender el manejo de números y operaciones aritméticas desde un lenguaje de
programación de bajo nivel.
Repasar los métodos de representación numérica de los sistemas: decimal, binario,
octal y hexadecimal, para números enteros y fraccionarios.
Discutir los métodos de conversión entre los sistemas numéricos de nuestro interés,
tanto para números enteros y fraccionarios.
Comprender la representación de números binarios con signo empleando la notación
complemento a 2.
Repasar las operaciones aritméticas elementales: suma, resta, multiplicación y
división.
Establecer claramente el concepto de “overflow” y su comparación con el “carry”.
Concepto de punto fijo y flotante.
Comprender la necesidad de codificar la información.
Describir lo métodos de detección y corrección de errores: paridad, “checksum”,
códigos de redundancia cíclica y “Hamming”.
1 INTRODUCCION
Un microprocesador, como cualquier sistema digital, emplea dos estados (0 y 1) para la
representación de información. Cabe recordar que los símbolos 1 y 0 representan esos dos
estados y no tienen ningún significado numérico por sí mismos. Sin embargo, cuando estos
símbolos se utilizan para representar los dígitos del sistema numérico binario, ellos se deben
manejar de acuerdo a las reglas del sistema numérico. Por lo tanto, en esta unidad se verá el
tratamiento de los sistemas numéricos necesario para su implementación en computadoras.
Al final de la unidad veremos la necesidad de codificar la información y distintas alternativas
para la detección y corrección de errores en la transmisión de datos.
2 SISTEMA DE NUMERACIÓN
Un sistema de numeración es un conjunto de símbolos y reglas de generación que
permiten construir todos los números válidos en el sistema. Un sistema de numeración puede
representarse como N = S + R donde:
• N es el sistema de numeración considerado.
• S son los símbolos permitidos en el sistema. En el caso del sistema decimal son
{0,1...9}; en el binario son {0,1}; en el octal son {0,1...7}; en el hexadecimal son
{0,1...9,A,B,C,D,E,F}.
• R son las reglas de generación que nos indican qué números son válidos y cuáles son
no-válidos en el sistema.
Estas reglas son diferentes para cada sistema de numeración considerado, pero una regla
común a todos es que para construir números válidos en un sistema de numeración
determinado sólo se pueden utilizar los símbolos permitidos en ese sistema (para indicar el
sistema de numeración utilizado se añade como subíndice al número).
De una forma general y amplia podemos clasificar los sistemas de numeración en dos
grandes tipos:
Posicionales: El valor de los símbolos que componen el sistema depende del valor que se les
ha asignado, y de la posición que ocupan en el número (Números decimales).
No Posicionales: El valor de los símbolos que componen el sistema es fijo, y no depende de
la posición que ocupa el símbolo dentro del número (Números romanos)
3 METODOS DE REPRESENTACION NUMERICA
Un número N, en un sistema de numeración posicional, se representa como:
N = dp-1*bp-1 + dp-2*bp-2 + .....+ d0*b0 + d-1*b-1 + d-q*b-q
donde:
b : base o raíz del sistema numérico.
d´s: dígitos o símbolos del sistema numérico, que son los b dígitos permitidos.
p : número de dígitos enteros.
q : número de dígitos fraccionarios.
N se puede expresar como:
N = dp-1dp-2 ... d0.d-1d-2 ... d-q
punto base
p=0
q=0
p<>0 y q<>0
número fraccionario
número entero
número mixto
3.1 Sistema Decimal
N10 = 27,510 = 2*101 + 7*101 + 5*10-1
[1]
b (base)= 10
d (dígito)= 0,1,2,3,4,5,6,7,8,9
p=2 y q=1.
3.2 Sistema Binario
N2 = 101.012 = 1*22 + 0*21 + 1*20 + 0*2-1 + 1*2-2 = 4 + 0 + 1 + 0 + 1/4 = 5.2510
b (base) = 2
d (dígito)= 0,1
p=3 y q=2.
3.3 Sistema decimal codificado en BCD
Decimal
0
1
2
3
4
5
6
7
8
9
|
|
no
usados
|
Binario
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
El código BCD es la representación
de los 10 dígitos del sistema decimal
con 4 bits del sistema binario.
3.4 Sistema Octal
N8 = 34.18 = 3*81 + 4*80 + 1*8-1 = 24 + 4 + 1/8 = 28.12510
b (base) = 8
d (dígito) = 0,1,2,3,4,5,6,7
p=2 y q= 1.
3.5 Sistema Hexadecimal
N16 = D56.A216 = 13*162 + 5*161 + 6*160 + 10*16-1 + 2*16-2 = 3414.632810
b (base) = 16
d (símbolo) = 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
p=3 y q=2
La utilidad y conversión con el sistema binario es similar al sistema octal, con la única
diferencia que los bits se agrupan de a cuatro. Este sistema es usado como entrada/salida en
muchas aplicaciones con microprocesadores, como kits de desarrollo, interfaces, etc., ya que
provee un medio eficiente para especificar direcciones, datos e instrucciones (8 y 16 bits).
4 RANGO DE UN NUMERO
Cuando se representan números en una base b y m dígitos, hay bm números posibles en un
rango de 0....bm-1.
Sea Nb un número entero cualquiera, éste tendrá un equivalente decimal que caerá en el
rango 0...bm-1, y podrá ser representado exactamente como muestra la Fig. 1.1
Sea:
b: base
m: número de dígitos
Entonces habrá bm números en el rango [0 ..... bm–1 ]
ƒ
Números Enteros
|__________|_________|__________|
00
01
10
11
b=2
m=2
Nb = 012 =110
Figura 1.1
ƒ
Números Fraccionarios (rango [0...1] )
Cuando se trabaja con números fraccionarios hay infinitos números en el intervalo entre 0
y 1, por lo tanto, como m (número de dígitos) es finito, únicamente se pueden representar bm
fracciones (puntos), siendo el salto entre puntos:
@ = b-m
[2]
(@: Intervalo de resolución)
|____|____|____|____|____|__....__|____|____|
0
|
|
1
@
valor de fracción que puede ser representado exactamente.
Figura 1.2
ƒ
Aproximaciones:
Para representar una fracción (punto) que no corresponda a los valores de representación
exacta, será necesario aproximar. Para ello hay dos formas comunes:
-
Truncación
Redondeo
Sea Fb el valor verdadero del número tal cual se expresa a continuación:
Fb = .a-1a-2a-3...a-ma-(m+1)a-(m+2)....a-(m+p)
−1
∑a *b
−i
i
i = −(m + p)
[3]
Siendo m el número de dígitos a utilizar.
4.1 Truncación
Se dice que una fracción es truncada cuando todos los dígitos a la derecha de a-m se
desprecian.
@
|______...__________|___________.______|________.....
0
fv
Fb
fv+1
Et
Figura 1.3
fv: valor truncado
Fb: valor real
Et: error por truncación (Et < b-m)
El máximo error cometido (ver Fig 1.3) será siempre menor que el intervalo de
resolución; es decir:
Et < b-m
Ejemplo
Fb = .23749
fv = .237
m=3
donde fv es el valor truncado.
4.2 Redondeo
Se dice redondeo cuando se selecciona el valor más próximo al valor deseado, es decir que
verifica si el valor se encuentra de la mitad del intervalo de resolución a la derecha o a la
izquierda. Por supuesto, esto requiere una complejidad adicional en el hardware.
@
|______...__________|___________.______|________.....
0
fv
Fb
fv+1
Et
Figura 1.4
Er: error por redondeo (Er ≤ @/2 )
Fb = .23749
fv = .238
m=3
donde fv es el valor por redondeo.
5 CONVERSION DE SISTEMAS NUMERICOS
Las conversiones más importantes son: decimal-binario, decimal-octal y decimalhexadecimal, ya que cualquier otra conversión entre esos cuatro sistemas se puede realizar
como una combinación de los anteriores. En muchos casos, la conversión de un número
fraccionario finito, expresado en un sistema numérico de base b1, no produce un número
fraccionario finito equivalente en una base b2. El error entre ambas representaciones lo
determina el número de dígitos empleados en la representación en la base b2.
5.1 Conversión Decimal-Binario
La conversión de números enteros y fraccionarios decimales en binarios, se lleva a cabo por
sucesivas divisiones y multiplicaciones, respectivamente, por la base (2).
Números Enteros
Como resultado de la división de un número decimal por dos, se obtiene un cociente Q y un
resto R. Los restos que se obtienen de las sucesivas divisiones son los bits del número
binario. El resto R es siempre un número entero menor que el divisor (dos en este caso), por
lo tanto R puede ser 0 ó 1.
N = dp-1*2p-1 + dp-2*2p-2 + .....+ d0*20
1.
N/2 = dp-1*2p-2 + dp-2*2p-3 + .....+ d0*2-1
|____________________||______|
Q0: cociente
R0: resto
d0=R0: bit menos significativo
Q0/2 = Q1 + d1 * 2-1
d1=R1: próximo bit
.
.
.
donde Qp-1= 0
Qp-2/2 = Qp-1 + Rp-1
dp-1=Rp-1: bit más significativo.
2.
.
.
.
p.
Ejemplo:
N=13
13/2 = 6
6/2 = 3
3/2 = 1
1/2 = 0
y R0=1
y R1=0
y R2=1
y R3=1
1310 = 11012
Números Fraccionarios
En este caso se multiplica sucesivamente por dos. Los enteros resultantes son los
sucesivos dígitos a la base convertida.
N = d-1*2-1 + d-2*2-2 + ... + d-q*2q
2*N = d-1*20 + d-2*2-1 + ... + d-q*2-q+1
|_____| |_________________|
1.
I-1: entero
X-1: fracción
d-1=I-1: bit menos significativo.
2*X-1 = d-2*20 + d-3*2-1 + ... + d-q*2-q+2
|_____| |__________________|
2.
I-2: entero
.
.
q+1.
X-2: fracción
d-2=I-2: próximo bit
.
.
2*X-q+1 = d-q*20 = I-q
d-q=I-q: bit más significativo
Ejemplo
N=0.55
2*0.55 = 1.1 --->
2*0.1 = 0.2 --->
2*0.2 = 0.4 --->
2*0.4 = 0.8 --->
2*0.8 = 1.6 --->
0.5510 = 0.100012
d-1= 1
d-2= 0
d-3= 0
d-4= 0
d-5= 1
5.2 Conversión Decimal-Octal
La conversión de números enteros y fraccionarios decimales a octales se lleva a cabo por
sucesivas divisiones y multiplicaciones, respectivamente, por la base (8).
Ejemplo:
N=1310
13/8 = 1 y R0 = 5
1/8 = 0 y R1 = 1
1310 = 158
5.3 Conversión Decimal-Hexadecimal
La conversión de números enteros y fraccionarios decimales a hexadecimales se lleva a
cabo por sucesivas divisiones y multiplicaciones, respectivamente, por la base (16).
Ejemplo:
N=1310:
13/16 = 0 y R0 = 13
1310 = D16
6 NUMEROS CON SIGNO
En el sistema binario (b=2) si se disponen de m dígitos, es posible representar 2m números
en un rango de 0 hasta 2m-1. Con esta restricción, si se necesita representar números con
signo, es necesario resignar el rango de operación (2m-1-1), ya el bit más significativo
representa el signo del número.
Las premisas más importantes que debe cumplir un buen sistema de representación son:
que tenga igual cantidad de números positivos como negativos, que exista un único cero, que
se puedan realizar las operaciones aritméticas básicas (suma, resta, multiplicación y división),
etc.
6.1 Representación
Hay tres formas básicas de representar números con signo en el sistema binario.
•
•
•
Bit de Signo o "Magnitud Signada"
Complemento a dos
Complemento a uno
Debido a que en el sistema binario no se encuentran otros símbolos más que 0 y 1, es que
se utiliza el bit más significativo del número como signo del número. Donde un 0 significa
que el número positivo, y un 1, que es un número negativo.
6.1.1
Bit de Signo o “Magnitud Signada”
En esta representación, para una palabra de n bits, los n-1 bits de la derecha representan la
magnitud del número y el número positivo si comienza con cero (0) y si el mismo empieza
con uno (1) el número es negativo.
Ejemplo:
Sea N = 810 = 10002
8 = 01000
-8 = 11000
6.1.2
Complemento a Dos
El complemento (N') de un número (N) en una base b se define como:
N' = bp – N
[4]
p: número de dígitos de N
b: base
bp: módulo
El módulo toma distintas denominaciones de acuerdo con el sistema numérico que se emplee.
Por ejemplo, para el sistema decimal, se denomina complemento a 10, y para el sistema
binario, complemento a 2.
Ejemplo
N=2010 -----> N' = 100 - 20 = 80
N=10012 -----> N' = 10000 - 1001 = 0111
Es importante notar que el complemento de un número depende del módulo elegido.
Hay dos formas de hallar el complemento a dos de un número:
•
Hallar el complemento lógico del número y luego sumarle 1.
1001 -----> 0110 ------> 0110 + 1 = 0111
•
Comenzando del bit menos significativo, dejar todos los bits sin cambio hasta el
primer 1 inclusive, luego complementar los restantes.
6.1.3
Complemento a Uno
El complemento a 1 (N") de un número (N), también llamado complemento de base
disminuida, no es más que el complemento lógico del número o el complemento a dos menos
uno.
N" = bp - N - 1
si el número fuese mixto (q <> 0),
N" = bp - b-q - N
6.1.4
Complemento Como Números Negativos
Para representar números con signo en la forma de complemento, se consideran números
negativos a aquéllos cuyo bit más significativo es "1", y números positivos a aquéllos cuyo
bit más significativo es "0". La diferencia con magnitud-signada, radica en la forma de
interpretar los bits restantes.
La representación de números positivos y negativos como complemento, tiene
significativas ventajas sobre la representación bit de signo desde el punto de vista de
hardware y de software.
6.1.5
Números en Complemento a Dos
Un número entero expresado en complemento a dos tiene la siguiente expresión:
N = -d7*27 + . . . + di*2i
[5]
Un número fraccionario expresado en complemento a dos tiene la siguiente expresión:
N = -d0*20 + . . . . + d-i*2-i
[6]
La representación en una recta sería:
1001
1011
1101
1111
0001
0011
0101
0111
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1000
1010
1100
1110
0000
-8 -7 -6 -5 -4 -3 -2 -1 0
0010
1 2
0100
0110
3 4 5 6
7
Sea p el número de bits incluido el bit de signo, entonces habrá 2p números posibles siendo el
rango de variación de números:
-2p-1 <= N <= 2p-1 -1
6.1.6
Números en Complemento a Uno
La representación en una recta sería:
1001
1011
1101
0001
0011
0101
0111
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1000
1010
1100
1110 0000
0010
0100
-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5
0110
6 7
Sea p el número de bits incluido el bit de signo, entonces habrá 2p números posibles
siendo el rango de variación de números:
-(2p-1-1) <= N <= 2p-1 -1
Uno de los inconvenientes de esta representación es que tiene dos formas de representar el
cero. Esto requiere de interpretaciones adicionales de los resultados para la toma de
decisiones.
6.1.7
Elección del Sistema de Representación Numérica
Se pueden mencionar tres razones principales por las cuales la elección de la
representación en complemento a dos es la más adecuada:
1. El hardware aritmético es más simple que en bit de signo y no mucho más complejo
que en complemento a uno.
2. En complemento a uno y bit de signo existen dos formas de representar al cero
(existe un +0 y un -0). Esto causa ciertos problemas en el hardware para la toma de
decisiones, por ejemplo saltar si el resultado es negativo.
3. Hay resultados incorrectos en complemento a uno y bit de signo que se deben
corregir. Ejemplo:(-107)+(-10)= =-117
6.2 OPERACIONES ARITMETICAS
En un microprocesador la ALU (Unidad Aritmético-Lógica) es la parte del procesador
encargada de realizar las operaciones aritméticas y lógicas con los datos suministrados. Los
datos manejados por la ALU provienen y se almacenan en registros. La ALU debe además
activar indicadores (banderas o “flags”) como resultados de las operaciones realizadas. Por lo
tanto definiremos una serie de banderas que nos permitirán interpretar los resultados
obtenidos. Y para poder descifrar a las banderas, debemos observar las operaciones
aritméticas elementales.
6.2.1
Suma Binaria
La suma de M + N produce:
M+N=S
N
0 0 1 1
M
0 1 0 1
___________________________
S
0 1 1 10
transporte (“carry”)
Las funciones lógicas que implementan la operación suma con la generación de su
respectivo carry son:
S = X + Y = X XOR Y
Cy = X AND Y
El carry se produce cuando se supera la capacidad del dígito (en la base que se trabaje 1:
binaria, 9: decimal) en una columna (peso) determinada. Cuando se trabaja con computadoras
no se puede tener infinitos bits de representación de números. Es decir, que los números se
representan por n bits (generalmente 4, 8, 16, 32 bits). Por lo tanto el flag de carry indica que
tuve un desborde en el rango de representación de los números naturales (sin signo).
Si el máximo rango de representación de números con signos (positivos o negativos) se
excede, el flag de carry no nos brinda información de desborde del rango de representación.
Cuando se trabaja con números enteros (con signo), la condición de desborde se indica con
un flag denominado "overflow" (si se desbordan los números positivos) o "underflow" (si se
desbordan los números negativos).
6.2.1.1 Suma en Complemento a Dos
En complemento a dos, con (n+1) bits se pueden representar números en el rango de (2n 1) a (-2n). Por ejemplo, con 8 bits el rango es de +127 a -128. Por lo tanto, cualquier
operación que exceda dicho rango producirá "overflow".
Condiciones para la Detección de Overflow
Se analizarán cuatro casos testigos, que permiten encontrar cuáles son las condiciones en
las que se produce overflow, y así poder generalizarlo.
0110 (+6)
0110 (+6) 1001 (-7)
+
+
+
+
0011 (+3)
0001 (+1) 1101 (-3)
------ ---- ------ ---- ------ ---0 1001 -7 0 0111 +7 1 0110 +6
C=0
Cs=1
C=0
Cs=0
C=1
Cs=0
1010 (-6)
1111 (-1)
------ ---1 1001 -7
C=1
Cs=1
donde:
C : es el carry
Cs: es el carry al bit de signo (bit2
bit3)
Por lo tanto, ocurre overflow si y sólo si la suma de dos números de igual signo produce
un número de signo opuesto.
C
0
0
1
1
Cs
0
1
0
1
V
0
1
1
0
Cs XOR C = V
Otra forma de determinar el overflow (V) es: Z XOR C. Sin embargo es necesario
verificar previamente los signos de los operandos.
6.2.2
Resta Binaria
La resta binaria produce:
M
0
0
1
1
N
0
1
0
1
R
0
1
1
0
B
0
1
0
0
M-N=R
(Borrow)
R = M - N = M XOR N
B = /M AND N
donde:
M: minuendo
N: sustraendo
Si trabajamos con números naturales, el "borrow" significa que el minuendo es menor que
el sustraendo, y se debe "pedir prestado" a la próxima columna.
Una de las mayores ventajas de usar complemento, es que la resta se lleva a cabo tomando
el complemento del sustraendo y luego se realiza la suma de los mismos. Es decir, se podría
simplificar el hardware.
M - N = M + (comp N)
Ejemplo:
1100 (-4)
1100 (-4)
+
0110 (+6)
1010 (-6)
-----------0 0110 -10
1 0110 -10
6.2.2.1 Relaciones Overflow/Underflow – Carry/Borrow
Se analizarán distintos casos que permitirán establecer relaciones entre los flags
Overflow/Underflow – Carry/Borrow resultantes de operaciones de resta entre 2 números
enteros.
0100 (+4) 0100 (+4)
+
1011 (-5)
0101 (+5)
------ --------- ---1 1001 +9 0 1001 +9
0110 (+6)
------ ---0 0110 -10
1010 (-6)
------ ---1 0110 -10
B=1
Bs=0
B=0
Bs=1
C=1
Cs=0
C=0
Cs=1
1100 (-4)
-
1100 (-4)
+
donde: C : carry
Cs: carry al bit de signo (bit2 ---> bit3)
B : borrow
Bs: borrow del bit de signo (bit3 ----> bit2)
Analizando los cuatro casos del ejemplo anterior se puede deducir que el borrow es el
carry complementado y que el overflow es:
V' = /B XOR /Bs = C XOR Cs = V
donde:
V’: es el overflow (denominado underflow ) que se produce en la resta.
Por lo tanto, los circuitos que detectan el overflow en la suma también lo harán en la resta.
En general, los procesadores utilizan el mismo bit para representar el carry y el borrow.
Esto se debe a que son complementarios.
6.3 Doble Precisión
Cuando se desea mayor precisión en las operaciones aritméticas que las que provee un
microprocesador utilizando la longitud de palabra estándar, se debe recurrir a la múltiple
precisión.
6.3.1
Suma
Para realizar la suma se procede en igual forma que en simple precisión, con la única
diferencia que la parte más significativa se debe sumar agregando el carry de la operación
anterior.
1
0110
1101
1001
0110
1001
0110
+
6.3.2
Resta
Para realizar la resta se procede en igual forma que en simple precisión, con la única
diferencia que la parte más significativa se debe restar teniendo en cuenta el borrow anterior.
Una forma alternativa de implementarla sería complementar el sustraendo, y proceder como
en el caso de la suma.
1
0001
+
1110
0000
1001
(25)
+
1110
(-18)
0111
07
Con respecto a las condiciones de overflow, valen las mismas reglas que en el caso de
simple precisión.
6.4
Operaciones en BCD
El código BCD es la representación de los 10 dígitos del sistema decimal con 4 bits del
sistema binario. Esta representación genera un conjunto de 6 valores no permitidos, que
requiere que algunos resultados de operaciones aritméticas sean corregidos.
6.4.1
Suma en BCD
Los símbolos BCD son 0...9, por lo tanto, con 4 bits de representación, los símbolos A...F
no son válidos. Esto quiere decir que al realizar operaciones aritméticas será necesario hacer
algunas correcciones al resultado. Veremos los tres casos resultantes de una operación de
suma aritmética:
I. 0110 (6)
+
0010 (2)
0 1000 (8) correcto
[0] [8]
II. 0110 (6)
+
0111 (7)
0 1101 (13) incorr.
+
0110 (6)
1 0011
[1] [3] correcto
III. 1001 (9)
+
1001 (9)
1 0010 (18) incorr.
+
0110 (6)
1 1000
[1] [8] correcto
El caso I. es el único resultado correcto, por lo tanto no necesita ningún tipo de corrección.
Los casos II. y III. Dan resultados incorrectos, por lo tanto es necesario adicionarle 6 para
obtener el valor correcto. Resumiendo, hay dos casos de ajuste decimal de la suma de dos
números A y B:
•
•
si A + B ≥ 10 con carry = 0
si A + B < 10 con carry = 1
Para usar BCD con signo será necesario usar un bit adicional (en un lugar de memoria)
para llevar el signo.
6.4.2
Resta BCD
Hay dos formas posibles para realizar la resta BCD:
a. Realizar un hardware que realice la resta decimal con borrow.
b. Hallar el complemento a 10 del sustraendo en BCD y luego sumarlos.
Para hallar el complemento a 10 de un número BCD de dos dígitos se puede hacer lo
siguiente:
a. Obtener el complemento a dos de cada dígito individualmente, sin tener en cuenta el
carry.
b. Sumar al dígito menos significativo 1010, y al más significativo, 1001.
Ejemplo
0010 0110 (26)
1110 1010
+
1001 1010
0111 1010
complemento a 2 individual
7410
10010 - 2610 = 7410
6.5 Representación Punto Flotante (FP)
Hasta ahora tratamos con números enteros y/o fraccionarios en notación punto fijo. Es
decir, que los números se representan por una cantidad fija de dígitos y cuyo punto base
(decimal, binario, etc.) era fijo. Este tipo de representación limita el rango de números a
representar (por ejemplo, en complemento a 2 es: [2m-1- 1] a [-2m-1] ). La representación en
punto flotante (FP) básicamente presenta las ventajas de ajustar automáticamente la escala y
extender el rango de números que el procesador puede manejar.
Los primeros microprocesadores (4 y 8 bits) no implementaban aritmética en punto
flotante (FP) debido al reducido canal de datos y a la baja velocidad de operación. Sólo
cuando era necesario, se recurría a implementaciones por software. El advenimiento de los
microprocesadores de 16, 32 y 64 bits hicieron posible las implementaciones de aritmética en
FP.
La representación de un número en FP se la siguiente:
N * rp
donde:
N: es la mantisa
r: es la base
p: es el exponente
Dado un número fijo de bits para la representación en FP, existe un compromiso entre
rango y precisión: Cuando mayor es el rango, menor es la precisión.
Formato
Actualmente la Sociedad del IEEE propuso el estándar P754 para aritmética en FP para
números binarios. Este estándar especifica los formatos de números en FP, los resultados de
las operaciones en FP, conversión de números, etc.
Un número en FP se representa como una cadena de bits compuesta por tres componentes
básicos:
‰ Signo de la mantisa (s)
‰ Mantisa (l.f)
‰ Exponente entero con signo (e)
En algunos casos se considera un cuarto campo que corresponde al signo del exponente.
Bit:
s Exponente (e) 1 Fracción (f) .
0 1
8 9 10
31
Si s = 0 el número es positivo y si s = 1, es negativo. El exponente e es la potencia de 2
que determina el rango del número. Y la mantisa, (l.f), determina la precisión del número. La
mayor exactitud se logra cuando l = 1. De esta forma, cualquier número, distinto de cero, se
puede expresar como:
± 2e * (1.f)
Exponente
El exponente de un número binario en FP puede ser:
‰
‰
Exponente con signo en complemento a dos o en magnitud y signo.
Exponente polarizado.
En el primer caso, el exponente es un número con expresado en alguna de las formas de
expresión de números con signo.
En el segundo caso, correspondiente a la representación estándar del IEEE, al exponente
se le adiciona un número entero constante (polarización) que lo mantiene siempre positivo.
Sea N el número de bits del exponente, por lo tanto la polarización será: 2N-1-1 (es decir, la
polarización será de la forma 0111....111).
6.6 Multiplicación
El producto binario P de 2 números X (multiplicando) e Y (multiplicador) es:
X
0
0
1
1
Sea N:
Y
0
1
0
1
P
0
0
0
1
N = dp-1*2p-1 + dp-2*2p-2 + .....+ d0*20
Si multiplicamos por la base (2) será:
2 * N = dp-1*2p + dp-2*2p-1 + .....+ d0*21
Ejemplo:
N = 101
2 * N = 1010
o sea, multiplicar por dos es equivalente a desplazar un bit a la izquierda completando con
ceros en la derecha.
Ejemplo
1011
* 1101
1011
0000
1011
1011
10001111
Veamos algunos algoritmos de multiplicación:
Algoritmo de multiplicación de números naturales:
Sean X e Y dos números de p y q bits, respectivamente. Para implementar el producto será
necesario utilizar dos registros: uno de p+q lugares, para almacenar el producto parcial, y
otro, de p+q-1 lugares, a donde se llevará y rotará X. En los microprocesadores, esto se
puede realizar por hardware o software. En el primer caso, se consigue mayor velocidad, y en
el segundo, mayor flexibilidad.
Algoritmo de Booth:
Este es un algoritmo para multiplicar números con signo expresados en complemento a
dos, sin tener necesidad de testear previamente los signos.
Testear
Transiciones en el
Multiplicador
S
Iguales
N
N
Sumar
S
0
Restar
1
Desplazamiento
Aritmético
N
Último
Bit
S
Ejemplo:
Se aplicará el algoritmo de Booth para realizar el producto de dos números
negativos (-3 * -5).
-3 111101
* -5 111011(0)
15 000000
000011
000011
0000011
00000011
111101
11110111
111110111
000011
000001111
0000001111
00000001111
000000001111
\/
signo
15
6.7 División
La división de un número M/N es:
M = N*Q + R1
donde:
M: dividendo
N: divisor
R1: resto
Q: cociente
Un algoritmo que pueda realizar la división de números naturales, M/N, consiste en restar
sucesivamente R-N (donde R es inicialmente igual a M, y luego R=R-N) hasta que haya
borrow. Entonces en Q nos queda la cantidad de veces que entra el divisor en el dividendo.
7 CODIGOS
Algunos ejemplos de códigos son:
ASCII
EBCDIC
EXCESO 3
GRAY
7.1 Manejo de Información Empaquetada y Desempaquetada
Es muy importante el manejo de información en la memoria del microprocesador. Por
ejemplo, información codificada en ASCII se puede almacenar en la memoria en forma
empaquetada o desempaquetada: supongamos que se desea almacenar los caracteres
hexadecimales A, B, C y D.
Ejemplo: Código ASCII: A (41H), B (42H), C (43H), D (44H)
Empaquetada
41
42
43
44
Desempaquetada
41
42
43
44
La ventaja de utilizar la forma empaquetada, es que se emplea mejor la memoria, sin
embargo, en forma desempaquetada, la información se puede manejar más fácil y
rápidamente.
7.2 Códigos Detectores y Correctores de Errores
La capacidad para detectar posibles errores en la información manipulada por las
computadoras es esencial para poder confiar en los resultados ofrecidos.
El error es la alteración del valor correcto en uno o más bits de información producida
durante su almacenamiento, transmisión o manipulación.
Cuando se transmite información entre sistemas digitales, se puede producir pérdida de
información debido a problemas de ruido, deformación de la señal (desadaptación de
impedancias, ancho de banda, "crosstalk", etc.). Los errores en un sistema de comunicaciones
digitales se producen fundamentalmente por dos tipos de fallas:
•
•
Eventos estáticos
Eventos dinámicos
Los eventos estáticos (EE) son aquellos de comportamiento y existencia conocidos, como
podría ser: distorsión de señal, pérdida por atenuación, “crosstalk”, etc.
Los eventos dinámicos (ED) son aquellos que ocurren en forma aleatoria, como sería los
disturbios eléctricos producido por descargas atmosféricas, transitorios en líneas eléctricas de
alimentación, etc, y todo aquello que por su naturales no se pueda prever su ocurrencia.
ED
S2
S1
EE
Para ello, es necesario detectar los errores producidos. Aquellos provenientes de EE son
más fáciles de manejar, ya que sus efectos son predecibles, no sucede lo mismo con los ED,
cuya naturaleza aleatoria los hace impredecibles. Hay muchos métodos y códigos
sofisticados, siendo posible en algunos casos recuperar la información transmitida.
Para poder detectar o incluso corregir posibles errores en la información, es preciso añadir
información redundante de comprobación.
La redundancia (R) es la información agregada a los datos (D) de acuerdo con alguna
formulación matemática conocida. El proceso de detección de errores consiste en comprobar
si el conjunto datos/redundancia (D,R) cumple o no dicho formulación, entonces:
• Si la formulación se cumple, se asume que la información es correcta.
• Si la formulación no se cumple, está claro que la información contiene errores.
Si la información redundante agregada permite conocer cuáles son los bits erróneos, es
posible realizar la corrección de los mismos y reconstruir la información original.
Un concepto muy importante relativo a la corrección y detección de código de errores es
el término “distancia”. La distancia entre dos números binarios es igual a la cantidad de bits
que difieren entre sí, se decir, es la cantidad de bits diferentes entre un número y otro. Por
ejemplo entre 000 y 001, la distancia es 1 y entre 000 y 011, es 2.
Sean X e Y dos palabras de un códigos de n bits, y sea el operador ⏐w⏐ el número de 1's
del mensaje w. Luego la distancia entre X e Y se define como:
D(X,Y) = ⏐X ⊕ Y⏐
La distancia mínima se define como el número de bits que deben cambiar para pasar de
una palabra de código válida a otra palabra de código válida. Por lo tanto un código que
detecte un error simple, tendrá una distancia mínima de 2.
La regla general para la corrección de errores es: sea un código de n bits y sea k la
cantidad de errores a corregir. La combinaciones deberían elegirse de tal manera que una de
otra difieran de al menos de una distancia 2k + 1. En general si la distancia mínima entre las
combinaciones de un código es 2k, luego es posible detectar 2k-1 errores o detectar hasta k
errores y simultáneamente corregir k - 1 errores. Si la distancia mínima es 4, puede detectar
errores dobles y corregir errores simples.
Regla General:
Código
n bits
Cantidad de Errores a Corregir
k bits
Distancia Mínima
2k + 1bits
En general:
ƒ
Detecta 2k-1
Dmin = 2 k
ƒ
ƒ
Detecta k
Corrige k-1
Los códigos que vamos a estudiar son:
ƒ
ƒ
ƒ
ƒ
ƒ
Mayoría
Paridad
Checksum
Códigos de Redundancia Cíclica (CRC)
Hamming
Como se dijo anteriormente, si D es el campo de datos y R la redundancia a ser agregada,
entonces el paquete de información I a ser enviado será una función de la forma: I = [D+R].
Por lo tanto, el paquete de información I se formará por los dos campos:
Dígitos de Información (D)
Dígitos de Checheo (R)
7.2.1
Función Mayoría
El mecanismo denominado “Función Mayoría”, consiste en repetir la información un
determinado número n de veces, normalmente un número impar (n ≥ 3). Por lo tanto, el
receptor dispondría de varias copias de la información que deberían ser exactamente iguales.
Si hay errores en la información recibida, normalmente afectarán a una sola copia o a un
número pequeño de ellas. En consecuencia, el receptor seleccionará como información
correcta a la copia que se repite mayor cantidad de veces. De ahí surge la importancia de
elegir un número de copias impar.
Es posible considerar que la función mayoría se comporte como un mecanismo para
detectar y/o corregir errores.
7.2.2
Paridad
Consiste en enviar un bit extra a cada caracter enviado, para mantener un número par o
impar de unos (paridad par o impar, respectivamente).
Para calcular la redundancia para paridad par, se debe implementar la función or-exclusiva
entre los bits:
P=dn−1♁dn−2♁...♁d1♁d0
Para calcular la redundancia para paridad impar, se debe implementar la función orexclusiva negado entre los bits:
I=dn−1♁dn−2♁...♁d1♁d0
Ejemplo:
0 1010110 Paridad par
1 1010110 Paridad impar
A este método también se lo llama Chequeo de Redundancia Longitudinal ("Longitudinal
Redundancy Check" LRC).
Una forma alternativa de chequear paridad, es enviando un carácter adicional, en donde se
han calculado las paridades de los bits en columna de cada caracter:
Ejemplo:
10110011
10100011
10011110
10001110
Caracter 1
Caracter 2
Caracter 3
Caracter de Chequeo (paridad par)
Ejemplo de un código ASCII correspondiente a la secuencia CINCO:
En este caso se denomina Chequeo de Redundancia Vertical ("Vertical Redundancy
Check" VRC).
El agregado de un bit de paridad de redundancia, hace que la distancia mínima sea 2.
7.2.3
Checksum
El "Checksum" se calcula como la suma módulo 256 del total de caracteres a enviar (es
decir que no se tiene en cuenta el carry producido). Este método consiste, por lo tanto, en
enviar el resultado del cálculo como un carácter adicional.
Ejemplo:
11001001
10000110
00101101
01111100
Caracter 1
Caracter 2
Caracter 3
Checksum
Este código puede verse como una variedad de VRL.
Los métodos descriptos tienen el inconveniente de detectar únicamente un error simple,
ya que si se genera un error doble éstos no lo detectan.
7.2.4
Chequeo de Redundancia Cíclica (CRC)
Este método es mucho más efectivo que los anteriores en la detección de errores en los
sistemas de comunicaciones. No permite la corrección de errores.
En este método, en forma similar a los anteriormente descriptos, se envía uno o más
caracteres adicionales de redundancia denominados FCS ("frame check sequence") o BCC
("block check caracter"), que difieren fundamentalmente en la forma de calcularlo.
El CRC consiste en considerar a los bits a ser transmitidos como un polinomio en x (para
n bits el orden es n-1) tal que la presencia de un término significa un "1", y la ausencia, un
"0"; es decir: sean 1010101 los bits a transmitir, entonces el mensaje podrá ser considerado
como un polinomio G(x) tal que:
G(x) = x7 + x5 + x3 + 1
Un mensaje de código cíclico consiste en un número de bits de datos y el BCC. Sea n el
número total de bits y k el número de bits de datos, por lo tanto, el número de bits del BCC es
n - k. El código del mensaje (BCC) se obtiene de 2 polinomios:
ƒ
ƒ
polinomio generador P(x)
mensaje polinomial G(x) (bits de datos).
Dados:
ƒ
ƒ
P(x): polinomio generador
G(x): polinomio de mensaje de datos
Se desea hallar F(x), código del mensaje polinomial, como sigue:
ƒ
Multiplicar el mensaje G(x) por x, siendo n - k el número de bits del BCC para dar
lugar al BCC (multiplicar por x, es lo mismo que desplazar el mensaje polinomial de
datos n-k lugares completando con ceros a la derecha).
G(x) * xn-k
ƒ
G(x)
0........0
Dividir el producto resultante G(x) * xn-k por el polinomio generador P(x).
G(x) * xn-k = Q(x) P(x) + C(x)
ƒ
Despreciar el cociente y sumarle a G(x) * xn-k el resto C(x) de la división para
producir el código de mensaje polinomial F(x).
F(x) = G(x) * xn-k + C(x) ;
Mensaje Polinomial a Transmitir
Para entender las operaciones anteriores, es necesario tener en cuenta que estamos
utilizando aritmética módulo 2. Es decir que tanto la suma como la resta binaria son la
función OR exclusivo bit a bit sin acarreo.
Además es importante notar que la cantidad de bits del resto C(x) (n-k) será de un orden
menor que el del polinomio generador P(x) (n-k+1). Por lo tanto, conociendo el número de
bits de P(x), se puede determinar la cantidad de ceros que se debe agregar a G(x) para realizar
la división polinomial.
Para hallar el polinomio G(x) se considera que la mayor potencia de x corresponde al bit
más significativo, es decir: sean 101000111 los bits a transmitir, entonces G(x) será:
¾ Ejemplo de cálculo de la redundancia:
Sea la información original G(x) = 11001, patrón P(x)=101
Primero se multiplica G(x) por 22: G(x) · 2k = 1100100
El resultado anterior se divide entre P(x)=101
Entonces la trama enviada será: 1100110
¾ Ejemplo de implementación:
Sea el mensaje de datos:
101000111
entonces:
G(x) = x8 + x7 + x6 + x2 + 1
El hardware necesario para realizar la división en aritmética módulo 2 será el siguiente:
x0
x2
x4
x5
donde el polinomio generador es:
P(x) = x5 + x4 + x2 + 1
Un polinomio generador muy conocido es el CRC-16 cuyo P(x) es:
P(x) = x16 + x15 + x12 + 1
Con respecto al receptor, éste se implementa realizando la división de la información
recibida por el mismo polinomio generador que el transmisor. Si el resto de la división es 0,
entonces la información se recibió sin error, en caso contrario se asumirá que hubo un error
en la transmisión.
El efecto general que se observa en el chequeo por medio del CRC, es que cualquier bit
se refleja en varios bits por un tiempo considerable después que éste fue transmitido. Esto es
muy importante, ya que se ha comprobado que la mayoría de los problemas de errores en
comunicación de datos se producen en pequeños grupos de bits ("burst").
Características más significativas del CRC:
ƒ
ƒ
ƒ
Detecta todos los errores de 1 y 2 bits (errores simples y dobles).
Detecta todos los errores de un “Burst” menor que el grado de P(x)
Detecta el 99 % de los errores de un “Burst” mayor que el grado de P(x)
7.2.5
Código corrector de errores por paridad vertical y horizontal
Este código corrector de errores, emplea un método combinado de chequeo de errores,
paridad horizontal y vertical. Si un error simple ocurre en una palabra de código, luego
ambos chequeadores indican, en conjunto, la fila y la columna donde se halla el bit con error.
Por lo tanto, este código, es capaz de detectar y corregir un error simple.
LCR
1000
1001
0110
0100
0010
0111
VCR 1001
7.2.6
0
1
1
0
0
0
1
Códigos Hamming
El código Hamming es un código de distancia 3, capaz de detectar errores dobles y
corregir si hay un error simple. El código Hamming se forma por n bits de información (Mn,
Mn-1, ... M1) y k bits de chequeo (Ck, Ck-1, ..... C1) de paridad par o impar. El mensaje
codificado está formado por n + k bits, siendo k el menor entero que cumple que:
2k ≥ n+k+1
[7]
(por ejemplo, si n = 7, entonces k = 4).
Hamming es un código capaz de corregir un error simple por lo tanto debe identificar un
bit erróneo en una cadena de bits. Entonces la ecuación [7] nos dice que el número de
combinaciones de los bits de chequeo (2k) debe ser al menos igual al número de bits del
mensaje más los bits de redundancia más una combinación extra para identificar que no hubo
errores.
Los bits de chequeo ocupan posiciones específicas en el mensaje codificado. Esas
posiciones son potencias enteras de 2, es decir 1,2,4,8, .... 2k-1, es decir que los bits de paridad
se ubican en los posiciones que tienen un único bit a 1 en su ordinal.
Los valores de cada Ci se calculan chequeando la paridad en lugares específicos del
mensaje original M. Por ejemplo para un código de 6 bits de mensaje, el mensaje codificado
será:
M6
M5
C4
M4
M3
M2
C3
M1
C2
C1
1010
1001
1000
0111
0110
0101
0100
0011
0010
0001
C1 = M1 ⊕ M3 ⊕ M5 ⊕ M7 ⊕ M9 .......
C2 = M2 ⊕ M3 ⊕ M6 ⊕ M7 ⊕ M10 .......
C3 = M4 ⊕ M5 ⊕ M6 ⊕ M7 ............
C4 = M8 ⊕ M9 ⊕ M10 . .............
Para el cálculo de los coeficientes Ci´s, los valores de Mi´s empleados, se refieren a la
posición que ocupan los elementos en el mensaje codificado, tomando a M1 igual a cero (ya
que corresponde al valor de Ci del mensaje codificado) para el cálculo inicial. Luego se
reemplazan los valores de los Ci calculados en las posiciones del mensaje codificado.
En el receptor: se chequea la misma paridad aplicada al mensaje codificado. Es decir que
se vuelven a calcular los coeficientes de la misma manera como fueron generados. Luego se
calcula el número posicional P como:
P = pkpk-1....p2p1
Si P = 0, el resultado es correcto.
Si P ≠ 0, el número indica la posición (el bit) con error.
Ejemplo error simple:
Supongamos que se recibe un carácter ASCII “f” (1100110B) con un error simple en la
posición M4:
M7 M6 M5 C4 M4 M3 M2 C3 M1 C2 C1
1
1
0
0
“1”
1
1
0
0
1
0
C1 = 0 ⊕ 0 ⊕ 1 ⊕ “1” ⊕ 0 ⊕ 1 = 1
C2 = 1 ⊕ 0 ⊕ 1 ⊕ “1” ⊕ 1 ⊕ 1 = 1
C3 = 0 ⊕ 1 ⊕ 1 ⊕ “1” = 1
C4 = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0
Entonces la posición a corregir será: P = p4p3p2p1 = 0111 (o sea la 7).
Ejemplo error doble:
Supongamos que se recibe un carácter ASCII “f” (1100110B) con un error doble en las
posiciones M2 y M4:
M7 M6 M5 C4 M4 M3 M2 C3 M1 C2 C1
1
1
0
0
“1”
1
“0”
0
0
1
0
C1 = 0 ⊕ 0 ⊕ “0” ⊕ “1” ⊕ 0 ⊕ 1 = 0
C2 = 1 ⊕ 0 ⊕ 1 ⊕ “1” ⊕ 1 ⊕ 1 = 1
C3 = 0 ⊕ “0” ⊕ 1 ⊕ “1” = 0
C4 = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0
Si se asume que hay un único bit erróneo, se trata del que tiene el ordinal 2, es decir, C2
que era un bit correcto. Por lo tanto se realiza una corrección errónea, ya que hay un error
doble.
Para distinguir el caso de error simple del de error doble, se puede añadir un bit de paridad
transversal T, o LRC, a la cadena de bits enviados (que no se usa para calcular las paridades
de Hamming), tal que:
•
•
•
Si no hay errores, P = 0 y T: correcto.
Si hay un error simple, P ≠ 0 y T: incorrecto. Es posible corregir el bit erróneo.
Si hay un error doble, P ≠ 0 y T: correcto. No es posible corregir el error.