Centro Asociado Palma de Mallorca

 

Arquitectura  de  Ordenadores  Tutor: Antonio Rivero Cuesta

  Unidad  Didáctica 1 

  Representación de  la Inf ormación y  Funciones Lógicas 

   

Tema  2 

  Aritmética y  Codificación 

   

Aritmética Binaria 

Suma Binaria 

Acarreo  Se define como el desbordamiento que se alcanza al sumar al dígito de mayor valor (el 1) un valor distinto de cero (0). Lo que conlleva al desplazamiento de una unidad en el resultado de la suma. No se puede realizar con sólo el dígito inicialmente existente.

Realice la suma de dos números binarios, de valor decimal 7 y 12.

11

Acarreo 111

+

1100 10011

Realice la suma de dos números binarios, de valor decimal 5,5 y 6,75.

111 1 1 0 1, 1 +

1 1 0, 1 1 1 1 0 0, 0 1

Acarreo

Resta Binaria 

Aparece el concepto de préstamo. El préstamo se define como el valor necesario que se cedería al dígito anterior, de forma que éste pueda restar un dígito que de otra forma sería suficiente.

Realice la resta de dos números binarios, 1100 y 111. 1 1 1 Préstamo 01 01 10 0 −

1 1 1 0 1 0 1

Realice la resta de dos números binarios, 10000 y 1. 1 1 1 1 Préstamo 01 10 10 10 0 −

1 0 1 1 1 1

  Formatos de los  Números y su  Representación 

Representación de Números en  Coma Fija sin Signo  Un número se representa mediante dos partes separadas mediante una coma, que ocupa una posición fija dentro de los dígitos que componen el número. A la izquierda de la coma se encuentra la parte entera, mientras que a su derecha está la parte fraccionaria. Que la parte entera y fraccionaria tenga un número fijo de bits, es el que obliga a que la coma se encuentre en una posición fija, de ahí la denominación de coma fija.

Representación de Números  Naturales en Binario Puro  El sistema de representación en binario puro se realiza mediante coma fija sin signo Es un sistema polinomial de base b = 2 y sin parte fraccionaria. Este sistema permite representar, con palabras de n n bits, todos los enteros positivos desde 0 hasta 2 −1. n

Por tanto su rango es de [0, 2 −1] y su resolución es la unidad.

Representación de Números en  Coma Fija con Signo  Los sistemas digitales deben ser capaces de procesar tanto con números positivos como con negativos, es decir, información numérica con signo. En la representación habitual de números se añade un signo a su izquierda, + en los números positivos y – en los números negativos.

La solución adoptada para evitar la inclusión de un nuevo nivel para el signo, es añadir un dígito más que indique el signo del número. Este bit denominado dígito de signo, se encuentra situado en el extremo izquierdo de la representación del número. Toma el valor: 

0 cuando se trate de números positivos.



1 para los negativos.

Los formatos más habituales de representación de los números con signo son: 

Signo-magnitud.



Complemento a la base.



Complemento a la base menos uno.

Formato de Números Binarios  en Signo‐Magnitud  Este tipo de representación utiliza uno de los dígitos, el situado más a la izquierda del número, para indicar su signo. Recibe el nombre de signo-magnitud, porque un dígito se dedica al signo y los demás a la magnitud.

Con n bits, el valor decimal que se puede representar estará comprendido en el rango simétrico:

[± (2

n–1

–1)]

Un inconveniente, es la necesidad de utilizar circuitos diferentes para realizar las operaciones de suma y de resta.

Complementos  Para evitar el inconveniente del sistema de representación en signo-magnitud se utilizan los complementos. Son transformaciones en la representación de números utilizados por las máquinas digitales para convertir restas en sumas.

Los complementos pueden ser de dos clases: 

Complemento a la base b.



Complemento a la base menos uno.

Complemento a la Base  Dado un número positivo N, de n dígitos enteros y representado en base b, se define su complemento a la base, como el número Cb(N) que cumple: N + Cb(N) = bn Para N = 0 su complemento vale Cb(N) = 0.

En el sistema decimal recibe el nombre de complemento a diez En el sistema binario se denomina complemento a dos.

Calcular el complemento a la base de los números: 2

C10 (72) = 10 − 72 = 100 − 72 = 28(10 C2 (110,01) = 23 − 110,01 = 1000 − 110,01 = 001,11

Complemento a la Base Menos  Uno  Dado un número positivo N en base b, compuesto por n dígitos en la parte entera y m dígitos en la parte fraccionaria, se define su complemento a la base menos uno, como el número Cb −1(N) que cumple: n

N + Cb–1(N) = b − b

−m

–m

0

Cuando la parte fraccionaria es cero, b = b = 1, siendo en este caso el complemento a la base menos uno igual a: Cb–1(N) = bn –1 –N n

Se debe observar que b – 1 es el valor máximo que se puede representar en la base b con n dígitos enteros.

Para N > 0, el valor de su complemento a la base menos uno es igual a: Cb(N) = bn – 1 – N. Para N = 0 su complemento vale: n

n

Cb-1(N) = b – 1 – N = b – 1,

Calcular el complemento a la base menos uno: 2

C9 (72) = 10 − 1 − 72 = 99 − 72 = 27(10 C2 (110,01) = 23 – 2–2 − 110,01 = 111,11 − 111,01 = 001,10

Convenio del Complemento a  dos en Números Binarios 

En el convenio del complemento a dos con formato de n bits, incluido el signo, se pueden representar sólo números comprendidos en el rango asimétrico: n–1

n–1

[–2 , 2 –1]

Convenio del Complemento a  Uno en Números Binarios 

En el convenio del complemento a uno con formato de n bits, incluido el signo, se pueden representar números comprendidos en el rango simétrico:

[–(2

n–1

n–1

–1), 2

–1]

Comparación entre  las Representaciones  Diferentes de  Números Binarios  con Signo 

Representación de los Números  Reales en Binario  Todos los números reales binarios, que se han representado anteriormente, tienen un formato de coma fija. Con este formato un número real se representa mediante dos partes separadas mediante una coma.

Modificar la posición de la coma tiene un efecto de multiplicación por un factor que es potencia de dos: −n



Negativa 2 .



Positiva 2m.

Según se desplace n posiciones a la izquierda o m posiciones a la derecha respectivamente.

Representar el número 12,25(10 en binario con formato de coma fija. Desplazar, en la representación binaria, la coma una posición a derecha e izquierda y calcular los nuevos valores que toma en cada caso el número binario modificado. 12,25(10 = 1100,01(2 11000,1(2 = 24,5(10 110,001(2 = 6,125(10

Coma Flotante  El tamaño de los números binarios o palabras de memoria, con el que operan los sistemas digitales, suele ser demasiado pequeño para representar números reales en coma fija, ya que limita considerablemente su rango de representación.

En la notación en coma flotante, un número tiene tres componentes: 

Una mantisa M.



Un exponente E.



Una base b.

Generalizando, un número N en coma flotante tiene la siguiente composición: N = S M(b)E S: es el signo del número. M: es el valor absoluto de la mantisa. E: es el valor del exponente. b: es la base del sistema de numeración utilizado.

La precisión de los cálculos depende directamente del número de dígitos que tenga la mantisa. El rango de representación, o valores extremos que el sistema digital es capaz de manejar, lo determina el número de dígitos que tiene el exponente. La representación de un número en coma flotante no es única, pues tiene tantas variaciones como lugares pueda ocupar la coma.

Para evitar representaciones múltiples del mismo número, se adopta el convenio de situar la coma en un lugar fijo de la mantisa. Para mantener el mayor número de dígitos significativos en la mantisa y con ello disponer de la mayor precisión posible, los números en coma flotante se normalizan. Al proceso que transforma cualquier mantisa, en una mantisa normalizada se denomina normalización. Implica el ajuste del exponente para que el valor del número no quede alterado.

Un formato de coma flotante muy extendido en los sistemas digitales es el estándar IEEE 754: 

Un bit de signo S, que es el signo de la mantisa.



El campo del exponente E de 8 bits (incluido implícitamente el signo del exponente).



El campo de la mantisa m de 23 bits.

S

N = (−1) · 2

E−127

· (1,m)

El estándar IEEE 754 también establece un formato de 64 bits, 11 bits en el campo del exponente y 52 bits en el campo de la mantisa, cumpliéndose la expresión: N = (−1)S · 2E−1023 · (1,m)

Representar el número −6,125(10 según el estándar IEEE 754 con formato de 32 bits. El número −6,125(10 se representa, su valor positivo en binario, como 110,001. Según el estándar IEEE 754, el número propuesto, debe cumplir la expresión:

S

N = (−1) · 2 1

N = (−1) ·

E−127

· (1,m) =

129−127 (2 (10)

· (1,10001(2) =

N = (–1) · (4(10) · (1,53125(10) = –6,125 Su almacenamiento, según el estándar IEEE 754 para números de 32 bits en coma flotante, es: 31

23

0

11000000110001000000000000000000

Casos especiales de representación mediante el estándar IEEE 754: El cero se representa mediante una secuencia de 32 ceros. Los números en los que el exponente E = 255 representan valores infinitos o expresiones de la forma 0/0. El último caso trata de cubrir el hueco dejado por la representación en coma flotante con mantisa normalizada, y conseguir una representación cercana al cero que tenga una distribución de errores uniforme.

Para ello este estándar emplea la representación no normalizada para E = 0 y M ≠ 0, cumpliendo el número N representado la siguiente expresión. N = (−1)S · 2−126 · (0,m)

Determinar el valor decimal del número siguiente expresado en el formato binario de coma flotante de 32 bits, según el estándar IEEE 754: 0000 0000 0001 1101 0100 0000 0000 0000 El número representado en coma flotante es un caso especial de los representados en la Tabla 3.6, donde el exponente E = 0 y la mantisa M ≠ 0.

Aplicando la expresión correspondiente a este caso especial, se obtiene: N = (−1)0 · 2–126(0,001110101(2) = N = 1,175494 · 10−38 · 0,228515 = N = 2,686188 · 10

−39

  Definiciones y  Codificación de la  Inf ormación 

Propiedades de Interés de los  Códigos  UNIFORMIDAD: Un código es uniforme si a cada símbolo fuente le corresponde una palabra código. A los códigos que cumplen esta propiedad también se les denomina código bloque. NO SINGULARIDAD: Un código uniforme es no singular si a cada símbolo fuente le corresponde palabras de código distintas.

DECODIFICACIÓN UNÍVOCA: Un código es unívocamente decodificable si, y sólo si, su extensión de orden n es no singular para cualquier valor finito n. DECODIFICACIÓN INSTANTÁNEA: Se denomina instantáneo, a un código unívocamente decodificable, cuando éste permite decodificar sin ambigüedad las palabras contenidas en una secuencia de símbolos del alfabeto código, sin necesitar el conocimiento de los símbolos que les suceden.

    Códigos Binarios 

PONDERADOS: Son aquellos códigos que a cada dígito binario se le asigna un peso y a cada palabra código la suma de los pesos de los dígitos binarios con valor uno, siendo el resultado igual al número decimal al que representan. La distancia entre dos palabras de código, se define como el número de dígitos que deben ser invertidos en una de ellas para obtener la otra. DISTANCIA DEL CÓDIGO BINARIO: se define como la menor de las distancias entre dos cualesquiera de sus palabras código.

Dos palabras de código son adyacentes si su distancia es uno, es decir, sólo difieren en un bit. CONTINUOS: Son aquellos códigos cuyas palabras consecutivas son adyacentes; es decir, si dos cualesquiera de sus palabras de código consecutivas sólo difieren en un bit. CÍCLICOS: Son aquellos códigos que además de ser continuos, la primera y última palabra de código también son adyacentes. DENSO: Se define a un código como denso si teniendo una longitud de palabra de n bits está n formado por 2 palabras de código.

AUTOCOMPLEMENTARIOS AL NÚMERO N: Son aquellos códigos, cuya palabra de código y su complementada suman N. Los códigos con esta propiedad posibilitan efectuar más fácilmente las operaciones de resta mediante el complemento a N.

   

Tipos 

  Códigos  Numéricos 

Código Binario Natural  Este código representa los valores decimales en el sistema de base dos. En la Tabla 3.15 se representa, a modo de ejemplo, el código binario natural, para el caso de longitud de palabra de cuatro bits.

Códigos BCD  En aplicaciones de introducción de información digital en forma decimal y en su visualización, como son por ejemplo los displays, resulta aconsejable, para simplificar los circuitos digitales, el empleo de códigos que representen por separado cada uno de los dígitos del número decimal. Este tipo de códigos se denomina decimales codificados en binario (Binary Coded Decimal, códigos BCD en lo sucesivo).

El número de dígitos binarios necesarios para la codificación es cuatro. Pueden ser códigos: 

Ponderados.



No ponderados.

Dentro de los códigos ponderados se pueden destacar el BCD Natural o BCD 8421.

La conversión de un número decimal a código BCD se realiza expresando cada dígito decimal mediante la combinación binaria correspondiente del código BCD elegido. La conversión del código BCD a un número decimal se realiza dividiendo el número, a partir de la coma, en grupos de cuatro bits, expresando en cada grupo su valor decimal correspondiente del código BCD elegido.

La representación del número decimal 37,6 en el código BCD natural es: 3

7

,

6

0 0 1 1 0 1 1 1 , 0 1 1 0

El valor decimal 1001010011,011 es:

del

código

BCD

natural:

1 0 0 1 0 1 0 0 1 1 , 0 1 1 0 2

5

3

,

6

Representar el número decimal 127,25 en los códigos BCD natural, Aiken 2421, exceso 3 y en binario natural.

Determinar el número decimal del código: 0100 0101 1000,0011 cuando está expresado en: BCD natural, Aiken 2421, exceso 3 y en binario natural.

La ventaja que presentan los códigos BCD, como ya se ha indicado anteriormente, es que al efectuarse codificaciones independientes para cada dígito, se facilita la conversión decimal-binario. La desventaja que presentan es que se necesitan más bits para ser representados.

Códigos Continuos y Cíclicos  Los códigos cíclicos por definición son continuos. Garantizan que entre dos palabras de código adyacentes solamente cambiará un bit. Se evita la aparición de palabras transitorias de código debidas a la imposibilidad de conmutación de dos o más dígitos. Una de las aplicaciones importantes de estos códigos está en los sistemas de conversión de digital a analógico y de analógico a digital.

Código Gray  El código Gray es uno de los códigos cíclicos más usados. También recibe el nombre de código reflejado, debido al reflejo que se debe realizar en las palabras código al construirlo.

TABLA 3.25 Construcción del código Gray o código reflejado

TABLA 3.26 Código Gray de cuatro bits

TABLA 3.27 Propiedades del código Gray

Conversión de Binario a Gray  101011, en código binario natural, a código Gray.

Conversión de Gray a Binario  111110, en código Gray, a código binario natural.

Código Johnson  El código Johnson es continuo y cíclico. Este código recibe también el nombre de código progresivo, debido a que el número de unos aumenta y disminuye progresivamente de una combinación a la siguiente. Presenta la desventaja de tener una capacidad de codificación para n bits de tan sólo 2 · n símbolos fuentes distintos, por lo que no es denso.

TABLA 3.28 Código Johnson

TABLA 3.29 Propiedades del código Johnson

TABLA 3.30 Propiedades de los códigos

Códigos Alfanuméricos  Se caracterizan porque permiten representar tanto números como caracteres alfabéticos. Incluyen caracteres especiales y de control, necesarios, estos últimos, para la transferencia de información. Podemos destacar: 

EBCDIC



ASCII

Código ASCII 

Códigos Detectores de Error  Cuando se transmite información digital por un medio físico, tal como cable, radio, fibra óptica, etc., se pueden producir errores, debido a la presencia de ruido, interferencias electromagnéticas, fallo de componentes, falsos contactos, etc. En un código denso no es posible la detección de un error. Es necesario que las palabras código no presenten todas las posibles combinaciones. Esta condición es necesaria, pero no suficiente.

La condición necesaria y suficiente para que un código binario permita detectar errores en un bit es que su distancia sea superior a la unidad. Para ello, se añade información redundante (bits de chequeo) a la palabra a transmitir aumentando su distancia.

Códigos de Paridad  Se define la paridad de una combinación o palabra de código binario, como el número de unos que contiene. Si el número de unos: 

Es par, la configuración tendrá paridad par.



En caso contrario, tendrá paridad impar.

Los códigos de paridad se forman partiendo de cualquier código cuya distancia mínima sea uno.

A cada combinación del código base se le añade un bit llamado bit de paridad. El bit de paridad toma un valor tal que hace que el número total de unos en el grupo sea siempre par o impar. Si se desea obtener un código de paridad par, dicho bit será tal que el número de unos en cada palabra del nuevo código sea par. Por el contrario, para obtener un código de paridad impar, dicho bit será tal que el número de unos en cada palabra del nuevo código sea impar.

TABLA 3.32 Código de paridad correspondiente al código base BCD natural

La detección de errores requiere que el transmisor genere el código de paridad, a partir del código base, añadiendo el bit de paridad (par o impar) y enviando esta información por el medio de transmisión. El receptor, en el otro extremo del medio de transmisión, debe comprobar si la paridad se mantiene igual a la prefijada en el transmisor (par o impar), detectando el error cuando ésta no se cumpla.

Códigos de Peso Fijo  Cabe destacar el código 2 entre 5 y el código biquinario. Este último es ponderado y consta de dos partes, una de dos bits y otra de cinco bits, de ahí su nombre. Los dos códigos indicados se caracterizan por tener una distancia de código igual a dos (lo que permite la detección de un bit de error) y todas sus palabras código tienen exactamente dos unos (paridad par).

TABLA 3.33

Códigos Correctores de Error  Además de detectar la presencia de un error, proporcionan información, indicando los bits en los que se ha producido el error. Una vez identificados los bits erróneos basta con invertir su valor y así obtener el valor correcto de los datos. Estos códigos, se utilizan principalmente en la transmisión de información, y en especial en aquellos casos donde la transmisión se realiza una sola vez, existiendo la imposibilidad de volver a repetirla cuando se detecta que se ha producido el error.

Tal es el caso de los sistemas que trabajan en tiempo real, en los que la información que se transmite es utilizada por el sistema receptor en el mismo instante en el que se recibe. La condición necesaria y suficiente para que un código permita corregir errores en un bit es que la distancia mínima debe ser superior a dos.

Código Hamming  Para detectar F bit erróneos la distancia mínima ha de ser: 2·F+1 A una palabra de n bits habrá que añadir k bits de paridad tal que: k

2 ≥n+k Se dice que es óptimo cuando cumple la igualdad: 2k = n + k + 1

Procedimiento: Numerar de derecha a izquierda los bits con 1,2,3,4... Los bits de paridad ocuparán las posiciones: 0

1

2

3

2 , 2 , 2 , 2 ,...

1,2,4,8,...

Los bits del test Ti deben de cumplir que el conjunto evaluado tenga paridad par.

TABLA 3.34 Palabra de test de paridad, en función de la posición del error, para el código Hamming

Generador Hamming 

Corrector Hamming 

El valor señalado por los bits de test, representa la posición (T3 T2 T1) = (011). El bit de la posición tercera del mensaje recibido (0110111) se debe invertir. Obteniéndose el mensaje correcto 0110011 del dígito decimal 6.

Tabla Hamming  Determinar si el dato 1010101 recibido en código Hamming, es correcto o bien corregirlo si es necesario.

Posición Pi Mensaje P7 ⨁ P5 ⨁ P3 ⨁ P1 P7 ⨁ P6 ⨁ P3 ⨁ P2 P7 ⨁ P6 ⨁ P5 ⨁ P4

B4 B3 B2 C3 B1 C2 C1 P7 P6 P5 P4 P3 P2 P1

1 1 1 1

0 0 0

1 1 1

0 0

1 1 1

0 0

Ti

1 1 T1 = 0 T2 = 0 T3 = 0

Tabla Hamming  Determinar si el dato 1000010 recibido en código Hamming, es correcto o bien corregirlo si es necesario.

Posición Pi Mensaje P7 ⨁ P5 ⨁ P3 ⨁ P1 P7 ⨁ P6 ⨁ P3 ⨁ P2 P7 ⨁ P6 ⨁ P5 ⨁ P4

B4 B3 B2 C3 B1 C2 C1 P7 P6 P5 P4 P3 P2 P1

1 1 1 1

0 0 0

0 0 0

0 0

0 0 0

1 1

Ti

0 0 T1 = 1 T2 = 0 T3 = 1

El valor señalado por los bits de test, representa la posición (T3 T2 T1) = (101). El bit de la posición 5 del mensaje recibido se debe invertir.

1010010