Source: http://rubensm.com/modelado-de-precision-finita/
Timestamp: 2020-08-13 10:34:53+00:00

Document:
Modelado de precisión finita – Rubén Sánchez
Modelado de precisión finita
Fecha de la entrada 5 febrero 2017
No hay comentarios en Modelado de precisión finita
El modelado de precisión finita consiste en la representación de números decimales mediante una codificación que no alcanza a representar el número exacto. Antes de entrar en detalles, será mejor repasar qué formatos de codificación binaria existen.
Codificación binaria con punto fijo
En la representación en punto fijo, el valor del número representado depende de la posición de los 1’s y los 0’s. Ejemplo:
\[ (10010)_2 = 1 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0 = 18 \]
El rango dinámico de esta codificación viene determinado por el número de bits que se utilizan. Sin embargo, la suma de números representados en punto fijo es muy sencilla.
Codificación binaria con punto flotante
El valor de un número no depende de la posición de cada uno de los bits, sino que dentro de la secuencia de binaria existe 3 partes: el signo, la mantisa y el exponente.
El valor del número se calcula como:
\[ \text{Valor} = S \cdot M \cdot 2^{E-cte} \]
La codificación con punto flotante ofrece un rango dinámico más grande que con el punto fijo. Además, la resolución de la codificación puede ser variable. Sin embargo, realizar una suma de dos números en coma flotante es más complejo que en punto fijo.
Para representar números enteros, existen dos codificaciones muy utilizadas. La primera es la explicada anteriormente, en el que la posición de cada bit representa un múltiplo de potencias de 2. Sin embargo, con esta codificación no es posible representar números negativos. Para representar números negativos la codificación más utilizada es la conocida como complemento a 2.
Codificación en punto fijo de enteros
La codificación de números con N bits y sin signo tiene un rango de \(\left[0, 2^N -1 \right]\). En este caso, la resolución es de 1.
Para calcular el valor de un número:
\[ X = \sum_{i=0}^{N-1} x_i 2^i\]
Codificación en punto fijo de enteros con signo
La codificación de números con N bits y con signo se puede realizar mediante la codificación complemento a 2. En esta codificación, cada bit tiene un peso, exactamente igual que en la codificación sin signo, con la particularidad de el bit más significativo tiene signo menos y el peso como potencia de 2 que le corresponda. Es decir:
Como vemos, el MSB (most significant bit) representa el peso \(2^4\) pero además tiene signo negativo.
El complemento a 2 tiene un rango de \(\left[-2^{N-1}, 2^{N-1}-1 \right] \) y una resolución de 1.
Equivalencia entre números sin signo y complemento a 2
En la tabla vemos la representación sin signo y la representación con signo y su equivalencia al formato decimal. En este caso N = 3, ya que se utilizan 3 bits para representar todos los números. El rango de los números sin signo es [0, 7] y en el caso de con signo [-4,3].
Los valores que son menores de \(2^{N-1} = 2^{3-1} = 2^2 = 4\) tienen una equivalencia directa entre ambas codificaciones, representados con fondo azul en la tabla. Es decir, 3 se escribe en formato binario en ambos casos \((011)_2\).
Para el caso de valores sin signo mayores a \(2^{N-1}\), su lectura en complemento a 2 sería:
\[ \text{Signed} = \text{Unsigned} – 2^N \]
Por ejemplo, 6 en formato sin signo es \((110)_2\). Sin embargo, \((110)_2\) leído como un número en complemento a 2 es:
\[ \text{Signed} = 6 – 2^3 = 6 – 8 = -2 \]
\[ S = \left\{\begin{matrix}
U; & U < 2^{N-1} \\
U – 2^N ;& U \geq 2^{N-1}
Codificación de reales con punto fijo
Los números decimales también pueden ser representados mediante la codificación de punto fijo. Sin embargo, la precisión con la que se pueden representar depende del número de bits y de la posición del punto.
La posición del punto es imaginaria ya que no se especifica de ninguna manera. A partir de este punto, los números a su izquierda son potencias de 2 positivas y a la derecha potencias de dos negativas. La resolución de esta representación la da el LSB (least significant bit).
\[ X = \left(\sum_{i=0}^{N-1} x_i 2^i \right) \cdot 2^{-b} \]
La notación para describir esta codificación es \([N,b]\), donde \(N\) es el número total de bits y \(b\) es el número de bits fraccionales. Por ejemplo, \([6,3]\) significan 6 bits totales de los cuales 3 son fraccionales. En este caso, la resolución es \(2^{-3 }= 0.125\).
Codificación de reales con punto fijo en complemento a 2
Para representar números reales con signo mediante complemento a 2, el rango de estos números es \( [-2^{N-1}\cdot Q, (2^{N-1}-1)\cdot Q]\), donde N es el número total de bits y Q es la resolución, que equivale a \(Q= 2^{-b}\).
\[ X = \left(-x_{N-1} 2^{N-1} + \sum_{i=0}^{N-2} x_i 2^i \right) \cdot 2^{-b} \]
N = 6, b = 3, formato [6,3].
El rango es \(\left[2^{6-1}\cdot 2^{-3}, (2^{6-1}-1)\cdot 2^{-3} \right] = \left[-4, 3.875\right] \).
La resolución es de \(2^{-3} = 0.125\).
N = 5, b = 2, formato [5,2].
El rango es \(\left[2^{5-1}\cdot 2^{-2}, (2^{5-1}-1)\cdot 2^{-2} \right] = \left[-4, 3.75\right] \).
La resolución es de \(2^{-2} = 0.25\)
Rango dinámico de una codificación
El rango dinámico determina la cantidad de números que existen para codificar un rango de números. Es decir, en la codificación punto fijo sin signo, el rango es \([0, \left(2^{N}-1\right)\cdot Q]\) y la resolución es \(Q=2^{-b}\).
El rango dinámico es la relación entre la máxima excursión de la codificación (\(N_{max}-N_{min}\) y la resolución de la codificación.
\[ DR = \frac{N_{max}-N_{min}}{Q} = \frac{ \left(2^{N}-1\right)-0}{Q} = 2^{N}-1 \]
Para el caso de complemento a 2 donde el rango es \([-2^{N-1},2^{N-1}-1]\) y la resolución sigue siendo \(Q= 2^{-b}\) el rango dinámico es también \(2^{N}-1\).
Si se calcula en dB, definiendo el rango dinámico como \(20\log_{10}\{·\}\), obtenemos que el rango dinámico es aproximadamente, 6.02N dB. Por tanto, cada bit que se añada aumentará 6 dB el rango dinámico de la codificación.
Efectos de la precisión finita
El hecho de trabajar con precisión finita a la hora de representar los números, tiene efectos en la señal que estamos tratando. Los efectos pueden ser de dos tipos:
Disminuir el número de bits de enteros, lo cual reduce el rango de la codificación. Esto puede llevar a que la señal no pueda ser representada dentro de nuestra codificación. Es decir, un seno que tiene un rango de [0,8] no puede ser codificado con U[4,3] ya que números mayores de \(2^{4}\cdot 2^{-3} = 2\) no pueden ser representados. Esto puede tener dos tipos de consecuencias en la señal:
Wrap: la señal se desdobla y números superiores al máximo del rango se representan como valores cercanos al mínimo del rango. Ejemplo: S[4,3], rango [-1, 0.875], resolución \(2^{-3} = 0.125\). Si representa un número fuera del rango, \(1.125 = (01.001)_2 \). Solo tenemos 1 bit para representar la parte entera, por tanto el número quedará sesgado a \((1.001)_2\) que de Ca2 a decimal es \( \left(-2^{3} + 2^{0} \right) \cdot 2^{-3} = -0.875\)
Overflow: si se intentan representar números que están fuera del rango de la codificación la señal se satura en el valor máximo. Para que la señal se represente como overflow hay que añadir explícitamente electrónica que controle estos casos.
Cuantificación: al tener una precisión finita todos los valores deben ser representados mediante múltiplos de la resolución. Todo número real que se encuentre entre estos múltiplos de la resolución será mapeado directamente a uno de estos múltiplos. Por tanto, la señal quedará escalonada. Dependiendo de la técnica que se utilice para realizar este mapeada (redondeo o truncado) los efectos son distintos. Desde el punto de vista frecuencial, la cuantificación añade ruido blanco que se extiende por toda la banda de la señal (desde 0 Hz hasta la mitad de la frecuencia de muestreo \(\frac{f_s}{2}\).
Truncado: truncar significa redondear hacia abajo un valor. Esto hace que el error que se comete sea como máximo -Q y de media sea -Q/2. Sin embargo, computacionalmente es sencillo.
Redondeo: se redondea al número más cercano. Es decir, se redondea hacia arriba si supera Q/2 y hacia abajo si el valor está por debajo de Q/2.
Implementación del redondeo o del truncado
En MATLAB tenemos las funciones floor() o round() que hacen el truncado o el redondeo respectivamente de la parte entera del número. Por tanto, si queremos redondear a 2 decimales el número 12.5432 lo que hay que hacer es:
Desplazamos dos dígitos hace la izquierda el número multiplicando por 100: 12.5432 · 100 = 1254.32
Aplicamos la función de truncado o redondedo: floor(1254.32) = 1254
Desplazamos de nuevo dos dígitos hacia la derecha el resultado diviendo por 100: 1254/100 = 12.54
En binario ocurre lo mismo, con la diferencia de que en lugar de multiplicar por potencias de 10 (100 en el caso anterior) hay que hacer por potencias de 2.
Ejemplo: truncar a 3 bits fraccionales \(1.28515625 = (01.01001001)_2\)
Desplazamos hacia la izquierda 3 posiciones multiplicando por \(2^3\): \(1.28515 \cdot 2^3 = 10.2812\)
Se aplica la función floor() al resultado: floor(10.2812) = 10
Se desplaza hacia la derecha 3 posiciones multiplicando por \(2^{-3}\): \( 10 \cdot 2^{-3} = 1.25 = (01.010)_2\)
Cuantificación de números en punto fijo con MATLAB
En MATLAB existe la función quantize(q, a) que sirve para calcular cuál va a ser el número con el que se va a cuantificar en binario un número. La función quantize() tiene donde argumentos:
q: es el cuantificador que define la codificación a utilizar. Se define con la función quantize(Format, Mode, Roundmode, Overflowmode), donde:
Format: [N b]
Mode: ‘fixed’ o ‘ufixed’ para codificación de punto fijo con signo o sin signo.
Roundmode: ‘floor’ para truncado, ‘round’ para redondeo.
Overflowmode: ‘saturate’ para saturar o ‘wrap’ para que desdoble el valor.
a: número a cuantificar.
Definición de punto fijo en Simulink
En Simulink se utiliza la función fixdt(Signed, WordLength, FractionLength) para definir el formato de la codificación.
Modificación de la resolución o escalado
Ampliación de la resolución
Se da cuando pasamos a representar la parte fraccional del número con más bits de los originales. Esta operación es tan sencilla como rellenar con ceros a la derecha del número.
Reducción de la resolución
La parte fraccional del númnero se represetnará con menos bits que los originales y por tanto, la resolución disminuye.
\(A = 2.625 = (010.101)_2\)
\(A [6,3] \rightarrow A = A_e \cdot 2^{-3} =(010101)_2 ~~A_e = (010101)_2 21 \)
\(A’ [4,1] \rightarrow A’ = A’_e \cdot 2^{-2} =(0101)_2~~A’_e = (0101)_2 = 5 \)
Esta operación se puede entender intuitivamente como que la parte entera del número cambia. Es decir, en el número original \(A_e = 21\) porque se utilizan 6 bits. Si truncamos con 4 bits y reinterpretamos la parte entera (leyendo los bits como un número binario entero), la parte entera \(A’_e\) disminuye. Finalmente, si se reescala en función de la posición del punto fijo, se obtiene el nuevo número.
\(A’_e = floor\left(A_e \cdot 2^{-2}\right) = 5\)
En este caso, se multiplica por \(2^{-2}\) porque hay que pasar de escala \(2^3\) a \(2^1\). Por tanto, hay que mover el punto a la derecha 2 posiciones.
Sin pérdida de resolución
Ambos sumandos deben tener el mismo tamaño y escalado. Si no lo tienenm hay que extender el rango del número con menos bits en la parte fraccional.
El número total de bits del resultado es la suma de:
Máximo número de bits en la parte entera de los dos sumandos
Máximo número de bits en la parte fraccional de los dos sumandos
\(ceil\left[ \log_2{\left(\text{numero de sumas}\right)}\right]\). Si solo se hace una suma, el resultado es 1 bit extra.
A[6,5], B[8,2], S[12,5]
A = 0.53125, B = 3.25
\(A_e = A \cdot 2^5 = 17\), \(B_e = B \cdot 2^2 = 13\)
La suma que tenemos que realizar se puede visualizar de la siguiente manera:
Como vemos, hay que rellenar con 0’s en la parte baja de B. Si no lo hacemos, y sumamos las partes enteras directamente, estaremos sumando bits con pesos diferentes. En decimal sería equivalente a sumar decenas con centenas y centenas con millares. Obviamente, el resultado de esta operación será erroneo. Es por ello, que al añadir 0, hay que reinterpretar el número decimal que obtenemos. Es decir:
De esta manera, el LSB de B ya no tendrá un peso de \(2^0\), sino que pasará a tener un peso de \(2^3\).
Esta operación se puede realizar en decimal como multiplicar por una potencia de 2 elevado al número de desplazamientos hacia la izquierda que queramos. En este caso:
\[ B’_e = B_e \cdot 2^3 = 104 \]
De esta manera ya podemos hacer la suma de \(S_e = A_e + B’_e = 17 + 104 = 121\). Con este resultado, podemos calcular S subiendo el coma 5 posiciones multiplicando por \(2^{-s}\). Es decir, \(S = S_e \cdot 2^{-b} = 121 \cdot 2^{-5} = 3.78125\)
Con pérdida de precisión
El crecimiento natural de la operación suma es el que habíamos dicho en el apartado anterior. Sin embargo, es posible que en nuestro diseño queramos que el resultado de la operación tenga un formato menor al que marca el crecimiento natural. En este caso, tenemos que hacer la suma de la misma manera que habíamos explicado en el apartado anterior y una vez obtenido el resultado, realizar el truncado (o redondeo) del número.
Ejemplo: S = A + B
A[6,5] = 0.53125, B[8,3] = 3.125, S[9,2]
Sin perder precisión, el resultado de la suma es S = 3.65625.
\(A_e = 0.53125 \cdot 2^5 = 17 \)
\(B_e = 3.125 \cdot 2^3 = 25 \)
Primero, tenemos que alinear los pesos de \(A_e\) y \(B_e\). Para ello, hay que añadir 2 ceros a la derecha de \(B_e\), por lo que hay que desplazar hacia la izquierda dos posiciones los bits de \(B_e\).
\(B’_e = 25 \cdot 2^2 = 100 \)
Ahora, ya podemos sumar las partes enteras de A y B obteniendo:
\(S’e = A_e + B’_e = 17 + 100 = 117\)
Ahora hay que realizar el truncado (o redondeo, dependiendo de la aplicación). Al resultado de \(S’e\), debemos quitarle los tres últimos bits. Para ello, desplazamos hacia de derecha 3 posiciones, hacemos la operación floor() y finalmente calculamos S multiplicando por su escalado:
\[ S = floor\left( S’_e \cdot 2^{-3} \right) 2^{-2} = 3.5 \]
Al multiplicar dos números, el formato del resultado equivale a la suma de bits de ambos operandos. Es decir:
A[Na, a], B[Nb, b], P[Np,p]
Np = Na + Nb
A diferencia de la suma, no es necesario alinear los pesos de los operandos, sino que es suficiente con multiplicar bit a bit y realizar el escalado correspondiente al final.
Sin embargo, debido a que el crecimiento de esta operación es tan grande, normalmente se recorta la precisión de la salida.
A[6,5], B[8,2], P = A·B [12,5], P = 1.7265625
A = 0.53125, Ae = 17
B = 3.25, Be = 13
\(P = floor(A \cdot B \cdot 2^5) \cdot 2^{-5} = 1.71875 \)
Como sabemos, la representación en complemento a 2 (2’C) es asimétrica. Es decir, los números con formato [3,2] tienen un rango [-1, 0.75] y no [-1, 1]. En el caso de multiplicar 2 números con formato [3,2], existe un caso extremo que se da cuando los dos números son -1. P = (-1)·(-1) = 1, que resulta estar fuera del rango que este formato puede codificar. Para poder codificarlo, es necesario añadir un bit más en la parte real ([4,2]) cuyo rango es (-2, 1.75). Sin embargo, este bit extra solo se utilizará en el caso de que ambos operandos sean -1. Por tanto, si se conoce que en la aplicación no es posible obtener esos dos valores como operandos de la multiplicación, se puede dimensionar la salida con 1 solo bit entero.
Multiplicación por constante: P = A · K
En el caso de multiplicar por una constante, es posible conocer cuál será el crecimiento máximo del resultado. Debido a que se conoce el rango de A y el valor de K, no todos los valores del rango de P van a ser utilizados. De esta manera, es posible optimizar el formato del resultado.
A[8,4], K[5,2], P = A·K [13,6]
K = 2.25, Ke = 9
Para representar Ke solo hacen falta \(ceil(\log_2{Ke}) = 4\) bits. Este será el crecimiento que aportará K y no el que marca su formato (5). Por tanto, cualquier valor de P se podrá representar con [8+4, 4+2] = [12,6], ya que el MSB nunca se utilizará.
← Sistemas temporales discretos → Encontrar posición de un número dentro de una matriz en MATLAB

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución

 resolución

 resolución 
 resolución