Post on 16-Feb-2015
transcript
Tema 2: Representación de la información
1. Sistemas numéricos• Sistemas de numeración y cambio de base• Aritmética binaria• Sistemas de codificación y representación de los
números
2. Codificación binaria• Representación binaria de datos e instrucciones• Características de los espacios de representación• Aspectos de los sistemas de representación
3. Sistemas alfanuméricos• Características de los códigos• Principales sistemas d codificación
4. Códigos redundantes• Características de los códigos• Códigos detectores• Códigos correctores
Contenido
v 3.0
Sistemas de numeración y cambio de base
Un sistema de numeración en base b utiliza para representar los números un alfabeto compuesto por b símbolos o cifras
Ejemplos:
b = 10 (decimal) {0,1,2,3,4,5,6,7,8,9}
b = 16 (hexadecimal) {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
b = 2 (binario) {0,1}
El número se expresa mediante una secuencia de cifras:
N ... n4 n3 n2 n1 n0 n-1 n-2 n-3 ...
El valor de cada cifra depende de la cifra en sí y de la posición que ocupa en la secuencia
1. Sistemas numéricos 1/24
El valor del número se calcula mediante el polinomio:
N ...+ n3·b3 + n2·b
2 + n1·b1 +n0· b
0 +n-1·b-1 ...
i
ii b·nN
Ejemplos:
3278,5210 = 3 · 103 + 2 · 102 + 7 · 101 +
+ 8 · 100 + 5 · 10-1 + 2 · 10-2
175,3728 = 1· 82 + 7 · 81 + 5 · 80 + 3 · 8-1 +
+ 7 · 8-2 + 2 · 8-3 = 125,488281210
Sistemas de numeración y cambio de base
1. Sistemas numéricos 2/242/4
Conversión decimal - base b
Método de divisiones sucesivas entre la base b
Para números fraccionarios se realizan multiplicaciones sucesivas por la base b.
Consideración de restos mayores que 9 y Error de truncamiento
Ejemplos:
2610 = 110102
0,187510 = 0,00112
26,187510 = 11010,00112
1. Sistemas numéricos 3/24Sistemas de numeración y cambio de base 3/4
b = 2 (binario)
{0,1}
1101002 = (1· 25) + (1· 24) + (1 · 22) =
= 25 + 24 + 22 = 32 + 16 + 4 = 5210
0,101002 = 2-1 + 2-3 = (1/2) + (1/8) = 0,62510
10100,0012 = 24 + 22 + 2-3 = 16 + 4 +(1/8)
= 20,12510
Ejemplos:
0 0001 0012 010
3 0114 100
5 101
6 1107 111
Decimal Binario
Números binarios del 0 al 7
Rango de representación: Conjunto de valores representable. Con n cifras en la base b podemos formar bn combinaciones distintas. [0..bn-1]
Sistema de numeración en base dos o binario
1. Sistemas numéricos 4/24Sistemas de numeración y cambio de base 4/4
Operaciones básicas
A B A+B
0 0 0
0 1 1
1 0 1
1 1 0 (1)
A B A*B
0 0 0
0 1 0
1 0 0
1 1 1
A B A – B
0 0 0
0 1 1 (1)
1 0 1
1 1 0
A B A/B
0 0 --
0 1 0
1 0 --
1 1 1
1. Sistemas numéricos 5/24
Aritmética binaria
Ejemplos
Sumas y restas
Multiplicaciones
División
1. Sistemas numéricos 6/24Aritmética binaria 2/2
Octal
b = 8 (octal) {0,1,2,3,4,5,6,7}
Correspondencia con el binario
8 = 23 Una cifra en octal
corresponde a 3 binarias
10001101100.110102 = 2154.648
Ejemplos
537.248 = 101011111.0101002
Conversión Decimal - Octal
760.3310 1370.25078
1. Sistemas numéricos 7/24
Sistemas de codificación y representación de números
Hexadecimalb = 16 (hexadecimal)
{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,}
Correspondencia con el binario
16 = 24 Una cifra en hexadecimal
corresponde a 4 binarias
Hexadecimal Decimal Binario
0 0 0000
1 1 0001
2 2 0010
3 3 0011
4 4 0100
5 5 0101
6 6 0110
7 7 0111
8 8 1000
9 9 1001
A 10 1010
B 11 1011
C 12 1100
D 13 1101
E 14 1110
F 15 1111
1. Sistemas numéricos 8/24Sistemas de representación y codificación de números 2/18
Ejemplos
10010111011111.10111012 = 25DF.BAH
4373.7910 1115.CA3D16
Conversión Decimal - Hexadecimal
273
553
1174373
17113 16
16
1
16
1 1
1. Sistemas numéricos 9/24Sistemas de representación y codificación de números 3/18
Código no ponderado, contínuo y cíclico
Basado en un sistema binario
Dos números sucesivos sólo varían en un bit
0 0 0 0 0 0 0 0 0 00 1 0 0 1 0 0 0 1 11 1 0 1 1 0 0 1 1 21 0 0 1 0 0 0 1 0 3
1 1 0 0 1 1 0 4 1 1 1 0 1 1 1 5 1 0 1 0 1 0 1 6 1 0 0 0 1 0 0 7
1 1 0 0 81 1 0 1 91 1 1 1 101 1 1 0 111 0 1 0 121 0 1 1 131 0 0 1 141 0 0 0 15
2 bits 3 bits 4 bits Decimal
1. Sistemas numéricos 10/24Sistemas de representación y codificación de números 4/18
Código Gray
Conversión Binario - Gray
A partir del primer bit sumamos el bit binario que queremos obtener con el de su izquierda
1 1 0 1 1
+ + + +
1 0 0 1 0
1 0 1 1 0 Binario1
1 + 0 1 1 0 1 11 0 + 1 1 0
1 1 11 0 1 + 1 0
1 1 1 01 0 1 1 + 0
1 1 1 0 1 Gray
Conversión Gray - Binario
1. Sistemas numéricos 11/24Sistemas de representación y codificación de números 5/18
Código BCD - Binary Coded Decimal
Dígitos decimales codificados en binario
Ejemplo
9 8 3 2 510 = 1001 1000 0011 0010 0101BCD-natural
Decimal BCD natural BCD exceso 3 BCD Aiken BCD 5421
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 3 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 1 4 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 0 5 0 1 0 1 1 0 0 0 1 0 1 1 1 0 0 0 6 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 7 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 8 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 1 9 1 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0
BCD natural tiene pesos 8421
BCD Aiken tiene pesos 2421
9 8 3 2 510 = 1111 1110 0011 0010 1011BCD-Aiken
1. Sistemas numéricos 12/24Sistemas de representación y codificación de números 6/18
Representación de números enteros
Es necesario la representación del signo
Se utiliza una cantidad determinada de bits (n)
Signo y magnitud (SM)
El signo se representa en el bit más a la izquierda del dato. Bit (n-1)
En el resto de los bits se representa el valor del número en binario natural. Bits (n-2)..0
Doble representación del 0.n = 6
1010 = 001010SM -410 = 100100SM
n = 4
-710 = 1111SM -1410 = no representable
010 = 000000SM 010 = 100000SM
1. Sistemas numéricos 13/24Sistemas de representación y codificación de números 7/18
Complemento a la base menos uno
Los valores positivos se representan en SM.
Los valores negativos se obtienen restando la magnitud del número a la base menos uno.
Convierte las restas en sumas.
Doble representación del 0.
Ejemplos Base 10
-6310 = 936C9 936 = 999 - 63
-1610 = 983C9 983 = 999 - 16
-1610 = 9983C9 9983 = 9999 - 16
n = 3
n = 4
Operación: 77 - 63
14
77-63
+936C9
077C9
014C9
(1)013+ 1
1. Sistemas numéricos 14/24Sistemas de representación y codificación de números 8/18
Base 2
C1 de -100102 = 101101C1
C1 de -1001112 = no representable
C1 de 0 = {000000C1 , 111111C1}
n = 6
Operación: 10001112 - 100102
Se intercambian ceros por unos y unos por ceros
Rango : [-2n-1 + 1, 2n-1 - 1]
Ejemplos:111111
- 010010
101101
Restando en binario natural
Sumando en C1 (n=8)c
10001112
- 00100102
01101012
01000111C1
(1)00110100
11101101C1
+
1+
00110101C1
1. Sistemas numéricos 15/24Sistemas de representación y codificación de números 9/18
Complemento a la base
Los valores positivos se representan en SM.
Los valores negativos se obtienen restando la magnitud del número a la base menos uno y posteriormente sumar uno a la dicha cantidad
Convierte las restas en sumas.
Ejemplos Base 10
-6310 = 937C10 937 = (999 - 63) + 1
-1610 = 984C10 984 = (999 - 16) + 1
-1610 = 9984C10 9984 = (9999 - 16) + 1
n = 3
n = 4
Operación: 77 - 63
El acarreo, si existe, no se considera
+937077
(1)014
1. Sistemas numéricos 16/24Sistemas de representación y codificación de números 10/18
Base 2
C2 de -100102 = 101110C2n = 6
Operación: 110012 - 100102 = 1112
Se intercambian los ceros y los unos y se suma uno
Rango : [-2n-1, 2n-1 - 1]
Ejemplos:
C2 de -11100102 = no representable
El acarreo no se considera
111111- 010010
101101C1
+ 1101101
101110C2
011001C2
101110C2
(1)000111C2
+Operando en C2
(n=6)
1. Sistemas numéricos 17/24Sistemas de representación y codificación de números 11/18
Representación sesgada
La representación se obtiene sumando un sesgo o cantidad al valor del número
El sesgo suele ser: 2n-1
Rango : [-2n-1, 2n-1 - 1]
Ejemplos Base 2
n = 8 Sesgo = 28-1 = 12810 = 1000 00002
110102 = 10011010S
- 110102 = 01100110S
02 = 1000 0000S
n = 4 Sesgo = 24-1 = 810 = 10002
12 = 1001S
-12 = 0111
1. Sistemas numéricos 18/24Sistemas de representación y codificación de números 12/18
Estándar IEEE 754
B = 2
Representación s e m
n = ns + ne + nm
Ejemplos:
Representación de los números reales
Representación en coma fija
Representación en coma flotante
N = (-1)s M · BE
N Valor numérico M Mantisa s signo
B Base E Exponente
1.234535 · 103 = 1234.535 · 100 = 0.1234535 · 104 = 123453.5 · 10-2 = 0.0001234535 · 107
ns : cantidad de bits para el signo
ne : cantidad de bits para el exponente
nm: cantidad de bits para la mantisa
1. Sistemas numéricos 19/24Sistemas de representación y codificación de números 13/18
Estándar IEEE 754
Campo de signo 0 +
1 -
• Representación sesgada
• Sesgo S = 2ne-1-1
• Ejemplos:
ne = 8 S = 2ne-1-1 = 127 = 0111 1111
Campo del exponente
1. Sistemas numéricos 20/24Sistemas de representación y codificación de números 14/18
Estándar IEEE 754
Campo de mantisa
• Normalización 1 M < 2
• M = [1.m] donde m es el valor que se almacena
• Ejemplos de normalizaciónN1 = 1001.1100110 · 2-5
1.0011100110 · 2-2
N2 = 0.000001101101 · 234 1.101101 · 228
Ejercicio n = 16 bits
ne = 8 bitsN = 1001 1111 0001 1101
s = 1 N<0
e = 0011 1110 E = -65
m = 001 1101 M = 1.00111012
N = -1.2265625 · 2-65 = -3,32440346980633 · 10-20
1. Sistemas numéricos 21/24Sistemas de representación y codificación de números 15/18
Situaciones especiales
• e = 0 mantisa denormalizada
Sesgo = 2ne-1-2
E = e - S = -2ne-1 + 2
• (e = 0) (m = 0) N = 0
• (e = 11...1) (m = 0) N =
• (e = 11...1) (m 0) N = NaN
Redondeo
• Exceso, defecto, más cercano, al par
1. Sistemas numéricos 22/24Sistemas de representación y codificación de números 16/18
• Ejemplo redondeo al par
Valores límite
• Números normalizados
|b| = Mmax2Emax Mmax = 2 - 2-nm
Emax = 2ne-1-1
|a| = Mmin2Emin Mmin = 1
Emin = -(2ne-1-2)
• Números denormalizados
|a’| = M’min2E’min M’min = 2-nm
E’min = -(2ne-1-2)
1. Sistemas numéricos 23/24Sistemas de representación y codificación de números 17/18
Valores límite• Si |N| > |b| desbordamiento a infinito
OVERFLOW
• Si |N| < |a’| desbordamiento a cero UNDERFLOW
Precisión
• Simple precisión
n = 32 bits, ne = 8 bits, nm = 23 bits
• Doble precisión
n = 64 bits, ne = 11 bits, nm = 52 bits
• Doble precisión extendida
n = 80 bits, ne = 15 bits, nm = 64 bits
Consideraciones
• Números excesivamente pequeños
• Números excesivamente grandes
• Comparación de números
1. Sistemas numéricos 24/24Sistemas de representación y codificación de números 18/18
Representación binaria de datos e instrucciones
2. Codificación binaria 1/10
MagnitudesAnalógicas: toma valores continuosDigitales: toma un conjunto de valores discreto
Ventajas sistemas digitales frente sistemas analógicos
Más sencillos y económicosMás seguridad y precisiónFácil almacenamiento de la informaciónMás resistentes al ruido e interferenciasPosibilidad de tratar información no numérica
Inconvenientes sistemas digitales frente sistemas analógicos
La mayoría de las magnitudes físicas son de tipo analógicoNecesidad de etapas CAD/CDA
Representación binaria de datos e instrucciones
2. Codificación binaria 2/102/2
Sistema digital binario
Representación de las magnitudes en base 2
Estados de un interruptor [ENCENDIDO, APAGADO]
Los dígitos {0, 1} corresponden con niveles de tensión eléctrica.
Nivel alto
Nivel bajo
Niveles lógicos de la familia tecnológica TTL
0 V0,8 V
2,4 V
5 V
Características de los espacios de representación
2. Codificación binaria 3/10
Elementos que lo componen
Condicionantes
Cantidad de estados representables
Cantidad de elementos representables
Tamaños predefinidos en las unidades del computador
Tamaños predefinidos en la comunicación entre unidades del computador
BIT Byte = 8 bits Palabra
1 KiloByte (KB) = 210 Bytes = 1024 Bytes
1 MegaByte (MB) = 220 Bytes = 1024 KB
1 GigaByte (GB) = 230 Bytes = 1024 MB
1 TeraByte (TB) = 240 Bytes = 1024 GB
1 PetaByte (PB) = 250 Bytes = 1024 TB
Unidades de codificación
Aspectos de los sistemas de codificación2. Codificación binaria 4/10
Coste de traducción
Coste de almacenamiento
Coste de procesamiento
Robustez y tolerancia a fallos
Características de los códigos3. Sistemas alfanuméricos 5/10
Compuesta por caracteres
Cantidad de bits dedicados a representar cada carácter
Codificación de cada carácter
Separación de cadenas
Cadenas de longitud fija
Cadenas de longitud variable
Principales sistemas de codificación3. Sistemas alfanuméricos 6/10
Código ASCII
Principales sistemas de codificación
3. Sistemas alfanuméricos 7/10
Código ASCII
2/5
Principales sistemas de codificación
3. Sistemas alfanuméricos 8/10
Código EBCDIC
3/5
Principales sistemas de codificación
3. Sistemas alfanuméricos 9/10
Código EBCDIC
4/5
Consideración de los distintos alfabetos: griego, latín árabe, ...
Estándar Unicode: emplea 2 bytes por carácter. Abarca los alfabetos de los idiomas escritos de América, Europa, Oriente Medio, África, India, Asia y el Pacífico
Página de códigos especial
Ejemplos:
• 862 hebreo
• 1251 cirílio
Principales sistemas de codificación
3. Sistemas alfanuméricos 10/105/5
Características de los códigos
4. Códigos redundantes 1/7
Objetivo: salvaguardar la información ante posibles errores
Se añade una información adicional a cada dato
Tipos:
Códigos detectores
Códigos correctores
4. Códigos redundantes 2/7
Códigos detectores
Código de paridad
Añade a cada dato un bit de paridad
Permite detectar un error en un bit
Paridad par, paridad impar
‘H’ 01001000 0
‘O’ 01001111 1
‘L’ 01001100 1
‘A’ 01000001 0
Bit de paridad
4. Códigos redundantes 3/7
Códigos correctores
Permiten detectar errores en más de un bit
El código debe ser capaz de indicar los bits erróneos
Ejemplos:
Códigos de paridad múltiple
Código Hamming
Códigos polinomiales (CRC)
4. Códigos redundantes 4/7Códigos correctores
Código Hamming
Distancia Hamming entre dos vectores: es el número de bits en el que toman valores diferentes.
Ej. Distancia Hamming 2
c1=0101 y c2 = 1100
Distancia de un código es la mínima distancia Hamming entre todas las posibles combinaciones distintas del código.
Teorema: Si la distancia de un código es d, entonces podemos detectar errores que afecten a d-1 bit.
Teorema: Si la distancia de un código es d, entonces es posible detectar y corregir los errores que afecten a t bits según la siguiente expresión:
d = 2·t+1
1/4
Números naturales 0..15 codificados en binario con 4 bit.
4. Códigos redundantes 5/7Códigos correctores
Ejemplos:
Distancia del código: 1
No es posible detectar ni corregir ningún error en los bit.
0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 1
1 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1
01234567
89
101112131415
2/4
4. Códigos redundantes 6/7Códigos correctores
Ejemplos:
Números naturales 0..15 codificados en binario con 4 bit con bit de paridad par.
Distancia del código: 2
Es posible detectar errores en un bit.
No es posible corregir ningún error.
0 0 0 0 00 0 0 1 10 0 1 0 10 0 1 1 00 1 0 0 10 1 0 1 00 1 1 0 00 1 1 1 1
1 0 0 0 11 0 0 1 01 0 1 0 01 0 1 1 11 1 0 0 01 1 0 1 11 1 1 0 11 1 1 1 0
01234567
89
101112131415
3/4
0 0 0 0 0 0 00 0 0 0 1 1 10 0 1 1 0 0 10 0 1 1 1 1 00 1 0 1 0 1 00 1 0 1 1 0 10 1 1 0 0 1 10 1 1 0 1 0 0
1 0 0 1 0 1 11 0 0 1 1 0 01 0 1 0 0 1 01 0 1 0 1 0 11 1 0 0 0 0 11 1 0 0 1 1 01 1 1 1 0 0 01 1 1 1 1 1 1
4. Códigos redundantes 7/7Códigos correctores
Código Hamming de los 15 primeros números naturales
Ejemplos:
p1p2p3p4p5p6p7
01234567
89
101112131415
p1: paridad par de p3, p5 y p7
p2: paridad par de p3, p6 y p7
p4: paridad par de p5, p6 y p7
Distancia del código: 3
Es posible detectar errores en dos bit.
Es posible corregir errores en un bit.
4/4