ARSO TEMA 2 PDF

Preview

Summary

Download ARSO TEMA 2 PDF

Description

Arquitectura de Computadores y Sistema Operativos Tema 2: Representación de la información Gregorio Fernández Fernández Tema 2: Representación de la información

1

©

DIT-UPM, 2015. Algunos derechos reservados. Este material se distribuye bajo licencia Creative Commons disponible en: http://creativecommons.org/licenses/by-sa/3.0/deed.es

Tema 2: Representación de la información

2

Contenido Conceptos previos Representación de textos Representación de datos numéricos Representación de sonidos e imágenes Compresión Detección y corrección de errores Tipos de ficheros Formatos de ficheros Material de estudio y trabajo: Documento «Representación y procesamiento en el nivel de máquina convencional» en el Moodle Bibliografía citada en ese documento Ejercicios y prácticas de laboratorio propuestos

Tema 2: Representación de la información

Representación de la información Conceptos previos Datos, información y conocimiento Extremistas Representación de textos Representación de datos numéricos Representación de sonidos e imágenes Compresión Detección y corrección de errores Tipos de ficheros Formatos de ficheros

3

Datos, información y conocimiento sensores perceptos (datos) información conocimiento

entorno

razonamiento

agente

acciones efectores

Información: Datos con significado (datos interpretados por el agente) Conocimiento: Información asimilada Tema 2: Representación de la información

4

Extremismo (Endianess) En almacenamiento: Si un dato codificado en k bytes se ha de almacenar en una sucesión de k direcciones de una RAM (d, d + 1...d + k − 1), ¿en qué orden se hace? ◮

◮

Convenio extremista menor (little-endian): el byte menos significativo en d, el siguiente en d + 1... Convenio extremista mayor (big-endian): el byte más significativo en d, el siguiente en d + 1... dir.

7

0 b m s

d b

d+1 M

dir. 15

0

b M s

b m s

d

7

0

b M s

d+1

s

extremista menor

b m s

15

0

b M s

b m s

extremista mayor

En transmisión (network byte order): El convenio en la mayoría de los protocolos de red es extremista mayor: se envía primero el byte más significativo. Tema 2: Representación de la información

5

Extremistas mayores y menores: ejemplo Petición a la dirección IP 138.4.2.61, que se codifica en 32 bits: 61 2 4 138 61 2 4 138 z}|{ z}|{ z}|{ z}|{ z }| { z }| { z }| { z }| { 0x 8A 04 02 3D = 10001010 00000100 00000010 00111101 Red (big endian)

Procesador Intel (little endian)

Procesador Motorola (big endian)

8A...04...02...3D

138.4.2.61 d d+1

0x8A04023D

d+2 d+3

t

3D 02 04 8A

61.2.4.138 3D 02 04 8A

d d+1 d+2 d+3

0x3D02048A

Solución por software: función (host to network long), que reordena los bytes del orden del procesador al orden de la red: 138.4.2.61 d

0x8A04023D

d+1 d+2 d+3

3D 02 04 8A

3D...02...04...8A

t

htonl(8A04023D)

138.4.2.61 d d+1 d+2 d+3

8A 04 02 3D

0x8A04023D

Tema 2: Representación de la información

Representación de la información Conceptos previos Representación de textos Codificación en binario: acuerdos y desacuerdos ASCII e ISO Unicode, UTF-8 Hipertexto y XML Representación de datos numéricos Representación de sonidos e imágenes Compresión Detección y corrección de errores Tipos de ficheros Formatos de ficheros

6

Codificación de caracteres en binario 01100001 01101100 01101111 01001000 0x61 0x6C 0x6F 0x48 ("a") ("l") ("o") ("H")

Hola

(ASCII) ¿Qué tal?

10111111 01010001 01110101 11101001 00100000 01110100 01100001 01101100 00111111 0xBF 0x51 0x75 0xE9 0x20 0x74 0x61 0x6C 0x3F ("¿") ("Q") ("u") ("é") (" ") ("t") ("a") ("l") ("?")

(ISO−8859−1) 11000010 10111111 01010001 01110101 11000011 10101001 00100000 01110100 01100001 01101100 00111111 0xC2

0xBF ("¿")

0x51

0x75

("Q")

("u")

0xC3

0xA9 ("é")

0x20

0x74

(" ")

("t")

0x61

0x6C

("a")

0x3F

("l")

("?")

(Unicode/UTF−8) 11000010 10111111 01010001 01110101 11000011 10101001 00100000 01110100 01100001 01101100 00111111 0xC2 Â

0xBF ¿

0x51

0x75

0xC3

Q

u

Ã

0xA9 ©

0x20

0x74 t

0x61 a

0x6C

0x3F

l

?

(Interpretado como ISO−8859−1) Tema 2: Representación de la información

7

Desacuerdo en un mensaje de correo Un mensaje codificado en UTF-8 que se ve así...

Tema 2: Representación de la información

8

Desacuerdo en un mensaje de correo ... porque el cliente de correo está configurado para ISO-8859-1:

Tema 2: Representación de la información

9

Acuerdo en un mensaje de correo Configurando el cliente...

Tema 2: Representación de la información

10

Acuerdo en un mensaje de correo ... los ponemos de acuerdo:

Tema 2: Representación de la información

11

Desacuerdo entre una página web y un navegador

Tema 2: Representación de la información

12

Desacuerdo entre una página web y un navegador Resultado en un navegador configurado para ISO-8859-15:

Tema 2: Representación de la información

13

Acuerdo entre una página web y un navegador Para verla bien (independientemente de lo que tenga por defecto el navegador), el fichero HTML debe contener esto:

Tema 2: Representación de la información

14

Otro desacuerdo Si el contenido de la página HTML está codificado en ISO-8859-15, y no lo dice, y el navegador está configurado por defecto para UTF-8 resulta esto:

Tema 2: Representación de la información

15

Otro desacuerdo Para verla así:

la cabecera debe informar del tipo de contenido:

Tema 2: Representación de la información

16

En el principio era el ASCII... «American Standard Code for Information Interchange», ≈ 1960 Estándares ISO/IEC 646 y Ecma-6 Código de 7 bits (27 = 128 codificaciones) 0000000 a 0011111 (0x00 a 0x1F): 32 caracteres de control («Conjunto C0», estándar ISO/IEC 6429): 0x00. NUL: carácter nulo (fin de cadena) 0x0A, LF (line feed): nueva línea 0x0D, CR (carriage return): retorno 0x1B, ESC (escape) ...

0100000 a 1111110 (0x20 a 0x7E): 95 caracteres imprimibles (incluido el espacio, 0x20):

1111111 (0x7F): DEL (delete): borrar Tema 2: Representación de la información

17

Codificaciones ASCII de caracteres imprimibles

Hex. Dec. 20 032 21 033 22 034 23 035 24 036 25 037 26 038 27 039 28 040 29 041 2A 042 2B 043 2C 044 2D 045 2E 046 2F 047

Hex. Dec. Hex. Dec. 30 048 40 064 31 049 41 065 32 050 42 066 33 051 43 067 34 052 44 068 35 053 45 069 36 054 46 070 37 055 47 071 38 056 48 072 39 057 49 073 3A 058 4A 074 3B 059 4B 075 3C 060 < 4C 076 3D 061 4D 077 3E 062 > 4E 078 3F 063 4F 079

Hex. Dec. 50 080 51 081 52 082 53 083 54 084 55 085 56 086 57 087 58 088 59 089 5A 090 5B 091 5C 092 5D 093 5E 094 5F 095

Tema 2: Representación de la información

Hex. Dec. 60 096 61 097 62 098 63 099 64 100 65 101 66 102 67 103 68 104 69 105 6A 106 6B 107 6C 108 6D 109 6E 110 6F 111

Hex. Dec. 70 112 71 113 72 114 73 115 74 116 75 117 76 118 77 119 78 120 79 121 7A 122 7B 123 7C 124 7D 125 7E 126 7F 127

18

...después vinieron muchos... La mayoría, extensiones a 8 bits: Windows-1252 («occidental»), Windows-1251 («cirílico»)... MacOS Roman, MacOS Arabic... IBM CP 850, CP 858... EBCDIC, incompatible con ASCII. Utilizado en «mainframes». GSM 03.38: código de 7 bits para el SMS de telefonía móvil ... Estándar ISO/IEC 8859 (1985-2001): 16 «partes» (códigos) que comparten las codificaciones ASCII ◮

ISO 8859-1 (o «Latin-1»), para europa occidental

◮

...

◮

ISO 8859-15 (o «Latin-9»), revisión de 8859-1: introduce e y otros caracteres Tema 2: Representación de la información

19

...ISO 8859-15... 0x00 a 0x7F ≡ ASCII 0x80 a 0x9F: caracteres de control («Conjunto C1») Hex. Dec. Hex. Dec. Hex. Dec. Hex. Dec. Hex. Dec. Hex. Dec. A0 160 NBSP B0 176 ° C0 192 À D0 208 Ð E0 224 à F0 240 ð A1 161 ¡ B1 177 ± C1 193 Á D1 209 Ñ E1 225 á F1 241 ñ A2 162 ¢ B2 178 ² C2 194  D2 210 Ò E2 226 â F2 242 ò A3 163 £ B3 179 ³ C3 195 à D3 211 Ó E3 227 ã F3 243 ó A4 164 e B4 180 Ž C4 196 Ä D4 212 Ô E4 228 ä F4 244 ô A5 165 ¥ B5 181 µ C5 197 Å D5 213 Õ E5 229 å F5 245 õ A6 166 Š B6 182 ¶ C6 198 Æ D6 214 Ö E6 230 æ F6 246 ö A7 167 § B7 183 · C7 199 Ç D7 215 × E7 231 ç F7 247 ÷ A8 168 š B8 184 ž C8 200 È D8 216 Ø E8 232 è F8 248 ø A9 169 © B9 185 ¹ C9 201 É D9 217 Ù E9 233 é F9 249 ù AA 170 a BA 186 o CA 202 Ê DA 218 Ú EA 234 ê FA 250 ú AB 171 « BB 187 » CB 203 Ë DB 219 Û EB 235 ë FB 251 û BC 188 Œ CC 204 Ì DC 220 Ü EC 236 ì FC 252 ü AC 172 ¬ AD 173 BD 189 œ CD 205 Í DD 221 Ý ED 237 í FD 253 ý AE 174 ® BE 190 Ÿ CE 206 Î DE 222 Þ EE 238 î FE 254 þ – AF 175 BF 191 ¿ CF 207 Ï DF 223 ß EF 239 ï FF 255 ÿ

Tema 2: Representación de la información

20

...pero Unicode llegó para quedarse Código universal para todas las lenguas. ISO/IEC 10646 Importante para la internacionalización del software (i18n) Define puntos de código: números naturales que se asocian a los distintos caracteres. Unicode 1.1 (1991): 216 = 65.536 puntos de código (U+0000 a U+FFFF) = plano básico multilingüe (BMP) Unicode 6.2 (2012): 17 planos { 17 × 216 = 1.114.112 (110.182 caracteres definidos) Se puede materializar mediante varias formas de codificación: UCS-2 (dos bytes, sólo el BMP) y UTF-16 (dos o cuatro bytes). UCS-4: Codifica todos los puntos de código en cuatro bytes. UTF-8: Actualmente, la forma más usada. Tema 2: Representación de la información

21

UTF-8 A diferencia de otras formas, es compatible con ASCII: los primeros 128 puntos de código se codifican en un solo byte. Código de longitud variable: los puntos del BMP mayores que U+007F se codifican con dos o tres bytes. Los otros planos requieren hasta seis bytes. Ejemplos:

Carácter E

Punto de código U+0045

ñ

U+00F1

e

U+20AC

Pts

U+20A7

Tema 2: Representación de la información

Codificación UTF-8 0x45 (un byte) 0xC3 0xB1 (dos bytes) 0xE2 0x82 0xAC (tres bytes) 0xE2 0x82 0xA7 (tres bytes) 22

Hipertexto y XML

Hipertexto: documento de texto plano con anotaciones, o marcas, que indican propiedades para la presentación (tamaño, color, etc.), o enlaces que remiten a otras partes del documento o a otros documentos (textos, imágenes, sonidos, vídeos...) «hipertexto» { «hipermedia» XML: orientado a intercambio de datos entre máquinas, no a presentación para personas y a navegación

Tema 2: Representación de la información

23

HTML (Hypertext Markup Language) Las marcas, o etiquetas, comienzan con « » y terminan con « ». Elementos ◮

◮

Con contenido: tienen una marca de apertura y otra de cierre. Ejemplo: Sin contenido. Ejemplo:

Las marcas de apertura pueden contener atributos con valores: , ... El documento debe tener un elemento raíz, , conteniendo dos elementos: ◮ ◮

, que contiene elementos con metadatos, y , que contiene elementos con datos.

Tema 2: Representación de la información

24

Ejemplo de documento HTML

En rojo: marcado semántico; en azul: marcado de presentación. (Mejor, en un documento CSS aparte)

Tema 2: Representación de la información

25

XML (eXtensible Markup Language) Como HTML, es un lenguaje de marcas y tiene una sintaxis parecida, pero... XML está concebido para el almacenamiento, el transporte y el intercambio de datos entre aplicaciones, no para su presentación. Las marcas (etiquetas) en XML no tienen un significado predefinido. Es un metalenguaje: con documentos adicionales (DTD o XMLSchema) se definen lenguajes específicos. Ejemplo:

Éste es un documento XML correcto. Nosotros entendemos lo que significan las marcas, pero un procesador no, a menos que lo acompañemos de otro documento en el que se definen los significados. Tema 2: Representación de la información

26

Representación de la información Conceptos previos Representación de textos Representación de datos numéricos Números enteros Operaciones de procesamiento Números reales Representación de sonidos e imágenes Compresión Detección y corrección de errores Tipos de ficheros Formatos de ficheros

Representación de números en binario Precisión arbitraria: los bits que sean necesarios { operaciones aritméticas con grandes números («bignum arithmetic»). Precisión limitada: formatos con un número fijo de bits { representación de enteros y racionales, con una precisión (número de bits) y un rango (números máximo y mínimo) fijos: n−1

bMs, o MSB

0

bms, o LSB

Los formatos más utilizados son los de «coma fija» y «coma flotante» Tema 2: Representación de la información

27

Representación de números enteros Se suele utilizar un formato de coma fija (la «coma» se supone situada inmediatamente a la derecha del bms) Números sin signo (enteros no negativos) Máximo representable: 1111...11 = rep(2n − 1) Números con signo:

◮

◮

n−1

0

S

b m s

En este caso, al bMs le llamamos S, porque se reserva para indicar el signo (S = 0: positivo, S = 1: negativo) Máximo representable: 0111...11 = rep(2n−1 − 1) ¿Y el mínimo? Depende del convenio para los números negativos. Tema 2: Representación de la información

28

Convenios para representar enteros negativos Signo y magnitud Complemento a 1: La representación de −N, rep(−N), es tal que: rep (N) + rep (−N) = 2n − 1 A efectos prácticos, basta cambiar los 0 por 1 y 1 por 0 en rep(N) Mínimo representable: 100...0 = rep(−2n−1 + 1) Dos representaciones para «cero»: +0 (0...0) y −0 (1...1) Complemento a 2 (más frecuente): La representación de −N, rep(−N), es tal que: rep (N) + rep (−N) = 2n A efectos prácticos, basta cambiar los 0 por 1 y 1 por 0 en rep(N) y luego sumar una unidad. Mínimo representable: 100...0 = rep(−2n−1 ) Un solo «cero» y un negativo más. Tema 2: Representación de la información

29

Operaciones de procesamiento básicas Suma sin signo trivial (1 + 1 = 10) Si acarreo del bMs { desbordamiento Suma con signo igual. Si los dos positivos o los dos negativos y cambia el bit de signo { desbordamiento Para restar (usando c. a 2): rep (N1 − N2) = rep (N1) + rep (−N2) ignorando acarreo de los bits de signo.

Indicadores (flags) : biestables en los circuitos del procesador: V: desbordamiento (overflow) C: acarreo (carry) N: negativo (= bMs) Z: cero Tema 2: Representación de la información

30

Operaciones lógicas op1 0 0 1 1

op2 0 1 0 1

NOT(op1) 1 1 0 0

AND 0 0 0 1

OR 0 1 1 1

EOR 0 1 1 0

NAND 1 1 1 0

NOR 1 0 0 0

Ejemplo: de un registro de 32 bits que contiene las codificaciones ASCII de «1234», extraer el «4» y pasarlo a binario: AND

0x(31 32 33 34) 0x(00 00 00 FF)

= =

0b(00110001 00110010 00110011 00110100) 0b(00000000 00000000 00000000 11111111) («máscara») 0b(00000000 00000000 00000000 00110100)

0b00110100 = 0x34 es la codificación de «4». Restándole 0x30 (codificación de «0») obtenemos el resultado: 00110100 + 11010000 (c. a 2 de 0x30) (1) 00000100 (resultado: 4) Tema 2: Representación de la información

31

Desplazamientos y rotaciones A LA IZQUIERDA

A LA DERECHA

0

C

0

C

LSR (a) desplazamientos logicos

C

LSL

C

ROL ROR (b) desplazamientos circulares, o rotaciones

C

C ROLC RORC (c) desplazamientos circulares con acarreo V C

S

Ejercicios:

ASR

C

S

0

ASL (d) desplazamientos aritmeticos

1

Multiplicar un número por 10 mediante tres desplazamientos y una suma.

2

Pasar de una cadena de dígitos decimales codificados en ASCII a la representación del número en binario mediante rotaciones, máscaras y multiplicaciones por 10. Tema 2: Representación de la información

32

Desplazamientos y rotaciones: ejercicio 1

Multiplicar N (representado en binario, coma fija) por 10: 1

Desplazar N dos veces a la izquierda { 4 × N

2

Sumar N al resultado { 5 × N

3

Desplazar a la izquierda el resultado anterior { 10 × N

Este algoritmo se puede codificar como un programa que recibe un dato, N, y devuelve el resultado 10 × N . Otro programa puede llamar a éste para que realice esa función

Tema 2: Representación de la información

33

Desplazamientos y rotaciones: ejercicio 2 (a)

Obtener la representación en 16 bits de la cadena ASCII «1234» (0x31 32 33 34: 32 bits) (o cualquier otra de cuatro dígitos) interpretada como número entero decimal (1.234): «ROL8(operando)» significa «8 rotaciones a la izquierda del operando» «MUL10(operando)» significa «multiplicar por 10 el operando» 1 2 3 4 5 6 7 8 9 10 11 12

ROL8(0x31 32 33 34) { 0x(32 33 34 31) (0x32 33 34 31) AND (0x00 00 00 FF) { 0x31 0x31 - 0x30 = 0x1; MUL10(0x1) = 0xA ROL8(0x32 33 34 31) { 0x(33 34 31 32) (0x33 34 31 32) AND (0x00 00 00 FF) { 0x32 0x32 - 0x30 = 0x2; MUL10(0x2 + 0xA) = 0x78 ROL8(0x33 34 31 32) { 0x(34 31 32 33) (0x34 31 32 33) AND (0x00 00 00 FF) { 0x33 0x33 - 0x30 = 0x3; MUL10(0x3 + 0x78) = 0x4CE ROL8(0x34 31 32 33) { 0x(31 32 33 34) (0x31 32 33 34) AND (0x00 00 00 FF) { 0x34 0x34 - 0x30 = 0x4; 0x4 + 0x4CE = 0x4D2

Resultado (en 16 bits): 0x04D2 = 0000 0100 1101 0010 Tema 2: Representación de la información

34

Desplazamientos y rotaciones: ejercicio 2 (b) Ahora bien, si la cadena estaba almacenada en memoria en cuatro bytes, lo anterior supone que el procesador (de 32 bits) es extremista mayor :

MP d d+1 d+2 d+3

0x31 0x32 0x33 0x34

registro del procesador 0x31

0x32

0x33

0x34

Algoritmo 0x04D2 = 1.234

Porque si fuese extremista menor el resultado sería erróneo:

MP d d+1 d+2 d+3

0x31 0x32 0x33 0x34

registro del procesador 0x34

0x33

0x32

0x31

Algoritmo 0x10E1 = 4.321 Tema 2: Representación de la información

35

Desplazamientos y rotaciones: ejercicio 2 (c) Algoritmo para el caso extremista menor: LSR8(operando) significa «8 desplazamientos lógicos a la derecha del...