Cuantización (procesamiento de señales)

Proceso de mapeo de un conjunto continuo a un conjunto contable

La forma más sencilla de cuantificar una señal es elegir el valor de amplitud digital más cercano a la amplitud analógica original. Este ejemplo muestra la señal analógica original (verde), la señal cuantificada (puntos negros), la señal reconstruida a partir de la señal cuantificada (amarillo) y la diferencia entre la señal original y la señal reconstruida (rojo). La diferencia entre la señal original y la señal reconstruida es el error de cuantificación y, en este esquema de cuantificación simple, es una función determinista de la señal de entrada.

La cuantificación , en matemáticas y procesamiento de señales digitales , es el proceso de mapear valores de entrada de un conjunto grande (a menudo un conjunto continuo) a valores de salida en un conjunto más pequeño (contable), a menudo con un número finito de elementos . El redondeo y el truncamiento son ejemplos típicos de procesos de cuantificación. La cuantificación está involucrada en algún grado en casi todo el procesamiento de señales digitales, ya que el proceso de representación de una señal en forma digital generalmente implica redondeo. La cuantificación también forma el núcleo de esencialmente todos los algoritmos de compresión con pérdida .

La diferencia entre un valor de entrada y su valor cuantificado (como el error de redondeo ) se denomina error de cuantificación . Un dispositivo o una función algorítmica que realiza la cuantificación se denomina cuantificador . Un convertidor analógico a digital es un ejemplo de cuantificador.

Ejemplo

Por ejemplo, redondear un número real al valor entero más cercano forma un tipo muy básico de cuantificador: uno uniforme . Un cuantificador uniforme típico ( de media longitud ) con un tamaño de paso de cuantificación igual a algún valor se puede expresar como ${\displaystyle x}$ ${\displaystyle \Delta }$

${\displaystyle Q(x)=\Delta \cdot \left\lfloor {\frac {x}{\Delta }}+{\frac {1}{2}}\right\rfloor }$,

donde la notación denota la función de piso . ${\displaystyle \lfloor \ \rfloor }$

Alternativamente, el mismo cuantificador puede expresarse en términos de la función de techo , como

${\displaystyle Q(x)=\Delta \cdot \left\lceil {\frac {x}{\Delta }}-{\frac {1}{2}}\right\rceil }$.

(La notación denota la función de techo). ${\displaystyle \lceil \ \rceil }$

La propiedad esencial de un cuantificador es tener un conjunto contable de posibles valores de salida menores que el conjunto de posibles valores de entrada. Los miembros del conjunto de valores de salida pueden tener valores enteros, racionales o reales. Para un redondeo simple al entero más cercano, el tamaño del paso es igual a 1. Con o con igual a cualquier otro valor entero, este cuantificador tiene entradas de valor real y salidas de valor entero. ${\displaystyle \Delta }$ ${\displaystyle \Delta =1}$ ${\displaystyle \Delta }$

Cuando el tamaño del paso de cuantificación (Δ) es pequeño en relación con la variación de la señal que se cuantifica, es relativamente sencillo demostrar que el error cuadrático medio producido por dicha operación de redondeo será aproximadamente . ^{[1] [2] [3] [4] [5] [6]} El error cuadrático medio también se denomina potencia de ruido de cuantificación . Añadir un bit al cuantificador reduce a la mitad el valor de Δ, lo que reduce la potencia de ruido por el factor ⁠ ${\displaystyle \Delta ^{2}/12}$1/4En términos de decibeles , el cambio de potencia del ruido es ${\displaystyle \scriptstyle 10\cdot \log _{10}(1/4)\ \approx \ -6\ \mathrm {dB} .}$

Debido a que el conjunto de posibles valores de salida de un cuantificador es contable, cualquier cuantificador se puede descomponer en dos etapas distintas, que se pueden denominar etapa de clasificación (o etapa de cuantificación directa ) y etapa de reconstrucción (o etapa de cuantificación inversa ), donde la etapa de clasificación asigna el valor de entrada a un índice de cuantificación entero y la etapa de reconstrucción asigna el índice al valor de reconstrucción que es la aproximación de salida del valor de entrada. Para el cuantificador uniforme de ejemplo descrito anteriormente, la etapa de cuantificación directa se puede expresar como ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle y_{k}}$

${\displaystyle k=\left\lfloor {\frac {x}{\Delta }}+{\frac {1}{2}}\right\rfloor }$,

y la etapa de reconstrucción para este cuantificador de ejemplo es simplemente

${\displaystyle y_{k}=k\cdot \Delta }$.

Esta descomposición es útil para el diseño y análisis del comportamiento de cuantificación, e ilustra cómo los datos cuantificados pueden comunicarse a través de un canal de comunicación : un codificador de origen puede realizar la etapa de cuantificación directa y enviar la información del índice a través de un canal de comunicación, y un decodificador puede realizar la etapa de reconstrucción para producir la aproximación de salida de los datos de entrada originales. En general, la etapa de cuantificación directa puede utilizar cualquier función que asigne los datos de entrada al espacio entero de los datos del índice de cuantificación, y la etapa de cuantificación inversa puede ser conceptualmente (o literalmente) una operación de búsqueda en una tabla para asignar cada índice de cuantificación a un valor de reconstrucción correspondiente. Esta descomposición en dos etapas se aplica igualmente bien a los cuantificadores vectoriales y escalares.

Propiedades matemáticas

Debido a que la cuantificación es una asignación de muchos a pocos, es un proceso inherentemente no lineal e irreversible (es decir, debido a que el mismo valor de salida es compartido por múltiples valores de entrada, es imposible, en general, recuperar el valor de entrada exacto cuando solo se da el valor de salida).

El conjunto de posibles valores de entrada puede ser infinitamente grande, y posiblemente continuo y, por lo tanto, incontable (como el conjunto de todos los números reales, o todos los números reales dentro de un rango limitado). El conjunto de posibles valores de salida puede ser finito o infinito contable . ^[6] Los conjuntos de entrada y salida involucrados en la cuantificación se pueden definir de una manera bastante general. Por ejemplo, la cuantificación vectorial es la aplicación de la cuantificación a datos de entrada multidimensionales (valorados en vectores). ^[7]

Tipos

Resolución de 2 bits con cuatro niveles de cuantificación en comparación con lo analógico. ^[8]

Resolución de 3 bits con ocho niveles.

Convertidor analógico a digital

Un convertidor analógico-digital (ADC) se puede modelar como dos procesos: muestreo y cuantificación. El muestreo convierte una señal de voltaje variable en el tiempo en una señal discreta en el tiempo , una secuencia de números reales. La cuantificación reemplaza cada número real con una aproximación de un conjunto finito de valores discretos. Lo más común es que estos valores discretos se representen como palabras de punto fijo. Aunque es posible cualquier número de niveles de cuantificación, las longitudes de palabra comunes son 8 bits (256 niveles), 16 bits (65.536 niveles) y 24 bits (16,8 millones de niveles). La cuantificación de una secuencia de números produce una secuencia de errores de cuantificación que a veces se modela como una señal aleatoria aditiva llamada ruido de cuantificación debido a su comportamiento estocástico . Cuantos más niveles utilice un cuantificador, menor será su potencia de ruido de cuantificación.

Optimización de tasa-distorsión

La cuantificación optimizada por tasa de distorsión se utiliza en la codificación de fuentes para algoritmos de compresión de datos con pérdida, donde el propósito es gestionar la distorsión dentro de los límites de la tasa de bits admitida por un canal de comunicación o medio de almacenamiento. El análisis de la cuantificación en este contexto implica estudiar la cantidad de datos (normalmente medidos en dígitos o bits o tasa de bits ) que se utilizan para representar la salida del cuantificador y estudiar la pérdida de precisión que introduce el proceso de cuantificación (a la que se hace referencia como distorsión ).

Cuantizadores uniformes de banda de rodadura y de contrahuella media

La mayoría de los cuantificadores uniformes para datos de entrada con signo se pueden clasificar como de uno de dos tipos: mid-riser y mid-tread . La terminología se basa en lo que sucede en la región alrededor del valor 0 y utiliza la analogía de ver la función de entrada-salida del cuantificador como una escalera . Los cuantificadores mid-tread tienen un nivel de reconstrucción de valor cero (que corresponde a un peldaño de una escalera), mientras que los cuantificadores mid-riser tienen un umbral de clasificación de valor cero (que corresponde a una contrahuella de una escalera). ^[9]

La cuantificación a mitad de la banda de rodadura implica redondeo. Las fórmulas para la cuantificación uniforme a mitad de la banda de rodadura se proporcionan en la sección anterior.

${\displaystyle Q(x)=\Delta \cdot \left\lfloor {\frac {x}{\Delta }}+{\frac {1}{2}}\right\rfloor }$,

La cuantificación de la parte media de la torre implica truncamiento. La fórmula de entrada-salida para un cuantificador uniforme de la parte media de la torre viene dada por:

${\displaystyle Q(x)=\Delta \cdot \left(\left\lfloor {\frac {x}{\Delta }}\right\rfloor +{\frac {1}{2}}\right)}$,

donde la regla de clasificación viene dada por

${\displaystyle k=\left\lfloor {\frac {x}{\Delta }}\right\rfloor }$

y la regla de reconstrucción es

${\displaystyle y_{k}=\Delta \cdot \left(k+{\tfrac {1}{2}}\right)}$.

Tenga en cuenta que los cuantificadores uniformes de nivel medio no tienen un valor de salida cero: su magnitud de salida mínima es la mitad del tamaño del paso. Por el contrario, los cuantificadores de nivel medio sí tienen un nivel de salida cero. Para algunas aplicaciones, tener una representación de señal de salida cero puede ser una necesidad.

En general, un cuantificador de tipo mid-riser o mid-tread puede no ser en realidad un cuantificador uniforme , es decir, el tamaño de los intervalos de clasificación del cuantificador puede no ser todos iguales, o el espaciado entre sus posibles valores de salida puede no ser todos iguales. La característica distintiva de un cuantificador de tipo mid-riser es que tiene un valor de umbral de clasificación que es exactamente cero, y la característica distintiva de un cuantificador de tipo mid-tread es que tiene un valor de reconstrucción que es exactamente cero. ^[9]

Cuantizadores de zona muerta

Un cuantificador de zona muerta es un tipo de cuantificador de banda intermedia con un comportamiento simétrico alrededor de 0. La región alrededor del valor de salida cero de un cuantificador de este tipo se conoce como zona muerta o banda muerta . La zona muerta a veces puede cumplir la misma función que una compuerta de ruido o una función de silenciamiento . Especialmente para aplicaciones de compresión, la zona muerta puede tener un ancho diferente al de los otros pasos. Para un cuantificador que por lo demás es uniforme, el ancho de la zona muerta se puede establecer en cualquier valor utilizando la regla de cuantificación directa ^{[10] [11] [12]} ${\displaystyle w}$

${\displaystyle k=\operatorname {sgn}(x)\cdot \max \left(0,\left\lfloor {\frac {\left|x\right|-w/2}{\Delta }}+1\right\rfloor \right)}$,

donde la función ( ) es la función de signo (también conocida como función signum ). La regla de reconstrucción general para un cuantificador de zona muerta de este tipo viene dada por ${\displaystyle \operatorname {sgn} }$

${\displaystyle y_{k}=\operatorname {sgn}(k)\cdot \left({\frac {w}{2}}+\Delta \cdot (|k|-1+r_{k})\right)}$,

donde es un valor de desplazamiento de reconstrucción en el rango de 0 a 1 como fracción del tamaño del paso. Por lo general, cuando se cuantifican datos de entrada con una función de densidad de probabilidad (PDF) típica que es simétrica alrededor de cero y alcanza su valor máximo en cero (como una PDF gaussiana , laplaciana o gaussiana generalizada ). Aunque puede depender de en general, y puede elegirse para cumplir la condición de optimalidad descrita a continuación, a menudo simplemente se establece en una constante, como . (Tenga en cuenta que en esta definición, debido a la definición de la función ( ) , por lo que no tiene efecto). ${\displaystyle r_{k}}$ ${\displaystyle 0\leq r_{k}\leq {\tfrac {1}{2}}}$ ${\displaystyle r_{k}}$ ${\displaystyle k}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle y_{0}=0}$ ${\displaystyle \operatorname {sgn} }$ ${\displaystyle r_{0}}$

Un caso especial muy común (por ejemplo, el esquema que se usa típicamente en contabilidad financiera y matemáticas elementales) es establecer y para todos los . En este caso, el cuantificador de zona muerta también es un cuantificador uniforme, ya que la zona muerta central de este cuantificador tiene el mismo ancho que todos sus otros pasos, y todos sus valores de reconstrucción también están espaciados de manera uniforme. ${\displaystyle w=\Delta }$ ${\displaystyle r_{k}={\tfrac {1}{2}}}$ ${\displaystyle k}$

Características de ruido y error

Modelo de ruido aditivo

Una suposición común para el análisis del error de cuantificación es que afecta a un sistema de procesamiento de señales de una manera similar a la del ruido blanco aditivo , teniendo una correlación insignificante con la señal y una densidad espectral de potencia aproximadamente plana . ^{[2] [6] [13] [14]} El modelo de ruido aditivo se utiliza comúnmente para el análisis de los efectos del error de cuantificación en sistemas de filtrado digital, y puede ser muy útil en dicho análisis. Se ha demostrado que es un modelo válido en casos de cuantificación de alta resolución (pequeña en relación con la intensidad de la señal) con PDF suaves. ^{[2] [15]} ${\displaystyle \Delta }$

El comportamiento del ruido aditivo no siempre es una suposición válida. El error de cuantificación (para los cuantificadores definidos como se describe aquí) está relacionado de manera determinista con la señal y no es completamente independiente de ella. Por lo tanto, las señales periódicas pueden crear ruido de cuantificación periódico. Y en algunos casos, incluso puede provocar la aparición de ciclos límite en los sistemas de procesamiento de señales digitales. Una forma de garantizar una independencia efectiva del error de cuantificación de la señal de origen es realizar una cuantificación dithered (a veces con modelado de ruido ), que implica agregar ruido aleatorio (o pseudoaleatorio ) a la señal antes de la cuantificación. ^{[6] [14]}

Modelos de error de cuantificación

En el caso típico, la señal original es mucho más grande que un bit menos significativo (LSB). Cuando este es el caso, el error de cuantificación no está significativamente correlacionado con la señal y tiene una distribución aproximadamente uniforme . Cuando se utiliza el redondeo para cuantificar, el error de cuantificación tiene una media de cero y el valor de la raíz cuadrada media (RMS) es la desviación estándar de esta distribución, dada por . Cuando se utiliza el truncamiento, el error tiene una media distinta de cero de y el valor RMS es . Aunque el redondeo produce un error RMS menor que el truncamiento, la diferencia solo se debe al término estático (DC) de . Los valores RMS del error AC son exactamente los mismos en ambos casos, por lo que no hay una ventaja especial del redondeo sobre el truncamiento en situaciones en las que se puede ignorar el término DC del error (como en sistemas acoplados AC). En cualquier caso, la desviación estándar, como porcentaje del rango completo de la señal, cambia en un factor de 2 por cada cambio de 1 bit en el número de bits de cuantificación. Por lo tanto, la relación señal-potencia potencial de ruido de cuantificación cambia en 4, o aproximadamente 6 dB por bit. ${\displaystyle \scriptstyle {\frac {1}{\sqrt {12}}}\mathrm {LSB} \ \approx \ 0.289\,\mathrm {LSB} }$ ${\displaystyle \scriptstyle {\frac {1}{2}}\mathrm {LSB} }$ ${\displaystyle \scriptstyle {\frac {1}{\sqrt {3}}}\mathrm {LSB} }$ ${\displaystyle \scriptstyle {\frac {1}{2}}\mathrm {LSB} }$ ${\displaystyle \scriptstyle 10\cdot \log _{10}(4)}$

En amplitudes más bajas, el error de cuantificación se vuelve dependiente de la señal de entrada, lo que produce distorsión. Esta distorsión se crea después del filtro anti-aliasing y, si estas distorsiones son superiores a la mitad de la frecuencia de muestreo, se solaparán con la banda de interés. Para que el error de cuantificación sea independiente de la señal de entrada, se realiza un dithering de la señal añadiéndole ruido. Esto reduce ligeramente la relación señal/ruido, pero puede eliminar por completo la distorsión.

Modelo de ruido de cuantificación

Comparación de la cuantificación de una sinusoide a 64 niveles (6 bits) y 256 niveles (8 bits). El ruido aditivo creado por la cuantificación de 6 bits es 12 dB mayor que el ruido creado por la cuantificación de 8 bits. Cuando la distribución espectral es plana, como en este ejemplo, la diferencia de 12 dB se manifiesta como una diferencia medible en los niveles de ruido de fondo.

El ruido de cuantificación es un modelo del error de cuantificación introducido por la cuantificación en el ADC. Es un error de redondeo entre el voltaje de entrada analógico al ADC y el valor digitalizado de salida. El ruido no es lineal y depende de la señal. Se puede modelar de varias maneras diferentes.

En un ADC ideal, donde el error de cuantificación se distribuye uniformemente entre −1/2 LSB y +1/2 LSB, y la señal tiene una distribución uniforme que cubre todos los niveles de cuantificación, la relación señal-ruido de cuantificación (SQNR) se puede calcular a partir de

${\displaystyle \mathrm {SQNR} =20\log _{10}(2^{Q})\approx 6.02\cdot Q\ \mathrm {dB} \,\!}$

donde Q es el número de bits de cuantificación.

Las señales de prueba más comunes que cumplen esto son las ondas triangulares de amplitud completa y las ondas de diente de sierra .

Por ejemplo, un ADC de 16 bits tiene una relación señal-ruido de cuantificación máxima de 6,02 × 16 = 96,3 dB.

Cuando la señal de entrada es una onda sinusoidal de amplitud completa, la distribución de la señal ya no es uniforme y la ecuación correspondiente es

${\displaystyle \mathrm {SQNR} \approx 1.761+6.02\cdot Q\ \mathrm {dB} \,\!}$

Aquí, se supone nuevamente que el ruido de cuantificación se distribuye uniformemente. Este es el caso cuando la señal de entrada tiene una amplitud alta y un espectro de frecuencia amplio. ^[16] En este caso, un ADC de 16 bits tiene una relación señal-ruido máxima de 98,09 dB. La diferencia de 1,761 en la relación señal-ruido solo se produce debido a que la señal es una onda sinusoidal de escala completa en lugar de una onda triangular o de diente de sierra.

Para señales complejas en conversores analógicos de alta resolución, este es un modelo preciso. Para conversores analógicos de baja resolución, señales de bajo nivel en conversores analógicos de alta resolución y para formas de onda simples, el ruido de cuantificación no se distribuye de manera uniforme, lo que hace que este modelo sea inexacto. ^[17] En estos casos, la distribución del ruido de cuantificación se ve fuertemente afectada por la amplitud exacta de la señal.

Los cálculos se realizan en relación con la entrada a escala completa. Para señales más pequeñas, la distorsión de cuantificación relativa puede ser muy grande. Para evitar este problema, se puede utilizar la compresión-expansión analógica, pero esto puede generar distorsión.

Diseño

Distorsión granular y distorsión por sobrecarga

A menudo, el diseño de un cuantificador implica admitir solo un rango limitado de posibles valores de salida y realizar un recorte para limitar la salida a este rango siempre que la entrada exceda el rango admitido. El error introducido por este recorte se conoce como distorsión de sobrecarga . Dentro de los límites extremos del rango admitido, la cantidad de espacio entre los valores de salida seleccionables de un cuantificador se conoce como su granularidad , y el error introducido por este espacio se conoce como distorsión granular . Es común que el diseño de un cuantificador implique determinar el equilibrio adecuado entre la distorsión granular y la distorsión de sobrecarga. Para un número dado de posibles valores de salida admitidos, reducir la distorsión granular promedio puede implicar aumentar la distorsión de sobrecarga promedio, y viceversa. Una técnica para controlar la amplitud de la señal (o, equivalentemente, el tamaño del paso de cuantificación ) para lograr el equilibrio adecuado es el uso del control automático de ganancia (AGC). Sin embargo, en algunos diseños de cuantificadores, los conceptos de error granular y error de sobrecarga pueden no aplicarse (por ejemplo, para un cuantificador con un rango limitado de datos de entrada o con un conjunto infinito contable de valores de salida seleccionables). ^[6] ${\displaystyle \Delta }$

Diseño de cuantificador de frecuencia-distorsión

Un cuantificador escalar, que realiza una operación de cuantificación, normalmente se puede descomponer en dos etapas:

Clasificación

Un proceso que clasifica el rango de la señal de entrada en intervalos no superpuestos , definiendo valores límite de decisión , tales que para , con los límites extremos definidos por y . Todas las entradas que caen en un rango de intervalo dado están asociadas con el mismo índice de cuantificación . ${\displaystyle M}$ ${\displaystyle \{I_{k}\}_{k=1}^{M}}$ ${\displaystyle M-1}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle I_{k}=[b_{k-1}~,~b_{k})}$ ${\displaystyle k=1,2,\ldots ,M}$ ${\displaystyle b_{0}=-\infty }$ ${\displaystyle b_{M}=\infty }$ ${\displaystyle x}$ ${\displaystyle I_{k}}$ ${\displaystyle k}$

Reconstrucción

Cada intervalo está representado por un valor de reconstrucción que implementa el mapeo . ${\displaystyle I_{k}}$ ${\displaystyle y_{k}}$ ${\displaystyle x\in I_{k}\Rightarrow y=y_{k}}$

Estas dos etapas juntas comprenden la operación matemática de . ${\displaystyle y=Q(x)}$

Las técnicas de codificación de entropía se pueden aplicar para comunicar los índices de cuantificación desde un codificador de origen que realiza la etapa de clasificación a un decodificador que realiza la etapa de reconstrucción. Una forma de hacerlo es asociar cada índice de cuantificación con una palabra de código binaria . Una consideración importante es el número de bits utilizados para cada palabra de código, denotado aquí por . Como resultado, el diseño de un cuantificador de nivel y un conjunto asociado de palabras de código para comunicar sus valores de índice requiere encontrar los valores de , y que satisfagan de manera óptima un conjunto seleccionado de restricciones de diseño, como la tasa de bits y la distorsión . ${\displaystyle k}$ ${\displaystyle c_{k}}$ ${\displaystyle \mathrm {length} (c_{k})}$ ${\displaystyle M}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle \{c_{k}\}_{k=1}^{M}}$ ${\displaystyle \{y_{k}\}_{k=1}^{M}}$ ${\displaystyle R}$ ${\displaystyle D}$

Suponiendo que una fuente de información produce variables aleatorias con una PDF asociada , la probabilidad de que la variable aleatoria caiga dentro de un intervalo de cuantificación particular viene dada por: ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle f(x)}$ ${\displaystyle p_{k}}$ ${\displaystyle I_{k}}$

${\displaystyle p_{k}=P[x\in I_{k}]=\int _{b_{k-1}}^{b_{k}}f(x)dx}$.

La tasa de bits resultante , en unidades de bits promedio por valor cuantificado, para este cuantificador se puede derivar de la siguiente manera: ${\displaystyle R}$

${\displaystyle R=\sum _{k=1}^{M}p_{k}\cdot \mathrm {length} (c_{k})=\sum _{k=1}^{M}\mathrm {length} (c_{k})\int _{b_{k-1}}^{b_{k}}f(x)dx}$.

Si se supone que la distorsión se mide por el error cuadrático medio, ^[a] la distorsión D , viene dada por:

${\displaystyle D=E[(x-Q(x))^{2}]=\int _{-\infty }^{\infty }(x-Q(x))^{2}f(x)dx=\sum _{k=1}^{M}\int _{b_{k-1}}^{b_{k}}(x-y_{k})^{2}f(x)dx}$.

Una observación clave es que la tasa depende de los límites de decisión y de las longitudes de las palabras de código , mientras que la distorsión depende de los límites de decisión y de los niveles de reconstrucción . ${\displaystyle R}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle \{\mathrm {length} (c_{k})\}_{k=1}^{M}}$ ${\displaystyle D}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle \{y_{k}\}_{k=1}^{M}}$

Después de definir estas dos métricas de rendimiento para el cuantificador, una formulación típica de tasa-distorsión para un problema de diseño de cuantificador se puede expresar de una de dos maneras:

1. Dada una restricción de distorsión máxima , minimice la tasa de bits ${\displaystyle D\leq D_{\max }}$ ${\displaystyle R}$
2. Dada una restricción de velocidad de bits máxima , minimice la distorsión ${\displaystyle R\leq R_{\max }}$ ${\displaystyle D}$

A menudo, la solución a estos problemas se puede expresar y resolver de manera equivalente (o aproximada) convirtiendo la formulación al problema sin restricciones, donde el multiplicador de Lagrange es una constante no negativa que establece el equilibrio apropiado entre velocidad y distorsión. Resolver el problema sin restricciones es equivalente a encontrar un punto en la envoltura convexa de la familia de soluciones para una formulación restringida equivalente del problema. Sin embargo, encontrar una solución, especialmente una solución de forma cerrada , para cualquiera de estas tres formulaciones de problemas puede ser difícil. Se han publicado soluciones que no requieren técnicas de optimización iterativa multidimensional para solo tres PDF: la distribución uniforme ^[18] , exponencial ^[12] y laplaciana ^[12] . Se pueden utilizar enfoques de optimización iterativa para encontrar soluciones en otros casos. ^{[6] [19] [20]} ${\displaystyle \min \left\{D+\lambda \cdot R\right\}}$ ${\displaystyle \lambda }$

Tenga en cuenta que los valores de reconstrucción afectan solo la distorsión (no afectan la velocidad de bits) y que cada individuo hace una contribución independiente a la distorsión total, como se muestra a continuación: ${\displaystyle \{y_{k}\}_{k=1}^{M}}$ ${\displaystyle y_{k}}$ ${\displaystyle d_{k}}$

${\displaystyle D=\sum _{k=1}^{M}d_{k}}$

dónde

${\displaystyle d_{k}=\int _{b_{k-1}}^{b_{k}}(x-y_{k})^{2}f(x)dx}$

Esta observación se puede utilizar para facilitar el análisis: dado el conjunto de valores, el valor de cada uno se puede optimizar por separado para minimizar su contribución a la distorsión . ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle y_{k}}$ ${\displaystyle D}$

Para el criterio de distorsión del error cuadrático medio, se puede demostrar fácilmente que el conjunto óptimo de valores de reconstrucción se da fijando el valor de reconstrucción dentro de cada intervalo en el valor esperado condicional (también denominado centroide ) dentro del intervalo, como se indica mediante: ${\displaystyle \{y_{k}^{*}\}_{k=1}^{M}}$ ${\displaystyle y_{k}}$ ${\displaystyle I_{k}}$

${\displaystyle y_{k}^{*}={\frac {1}{p_{k}}}\int _{b_{k-1}}^{b_{k}}xf(x)dx}$.

El uso de técnicas de codificación de entropía suficientemente bien diseñadas puede dar como resultado el uso de una tasa de bits cercana al contenido de información real de los índices , de modo que efectivamente ${\displaystyle \{k\}_{k=1}^{M}}$

${\displaystyle \mathrm {length} (c_{k})\approx -\log _{2}\left(p_{k}\right)}$

y por lo tanto

${\displaystyle R=\sum _{k=1}^{M}-p_{k}\cdot \log _{2}\left(p_{k}\right)}$.

El uso de esta aproximación puede permitir que el problema de diseño de codificación de entropía se separe del diseño del cuantificador en sí. Las técnicas de codificación de entropía modernas, como la codificación aritmética, pueden lograr velocidades de bits muy cercanas a la entropía real de una fuente, dado un conjunto de probabilidades conocidas (o estimadas de manera adaptativa) . ${\displaystyle \{p_{k}\}_{k=1}^{M}}$

En algunos diseños, en lugar de optimizar para un número particular de regiones de clasificación , el problema de diseño del cuantificador puede incluir también la optimización del valor de . Para algunos modelos de fuentes probabilísticas, el mejor rendimiento puede lograrse cuando se aproxima al infinito. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

Desconsideración de la restricción de entropía: cuantificación de Lloyd-Max

En la formulación anterior, si se ignora la restricción de la tasa de bits estableciéndola en 0, o equivalentemente, si se supone que se utilizará un código de longitud fija (FLC) para representar los datos cuantificados en lugar de un código de longitud variable (o alguna otra tecnología de codificación de entropía, como la codificación aritmética que es mejor que un FLC en el sentido de tasa-distorsión), el problema de optimización se reduce a la minimización de la distorsión únicamente. ${\displaystyle \lambda }$ ${\displaystyle D}$

Los índices producidos por un cuantificador de 2 niveles se pueden codificar utilizando un código de longitud fija que utiliza bits/símbolo. Por ejemplo, cuando hay 256 niveles, la tasa de bits de FLC es de 8 bits/símbolo. Por este motivo, a este tipo de cuantificadores se los ha denominado a veces cuantificadores de 8 bits. Sin embargo, el uso de un FLC elimina la mejora de la compresión que se puede obtener mediante el uso de una mejor codificación de entropía. ${\displaystyle M}$ ${\displaystyle R=\lceil \log _{2}M\rceil }$ ${\displaystyle M=}$ ${\displaystyle R}$

Suponiendo una FLC con niveles, el problema de minimización de la tasa de distorsión se puede reducir a la minimización de la distorsión únicamente. El problema reducido se puede plantear de la siguiente manera: dada una fuente con PDF y la restricción de que el cuantificador debe utilizar solo regiones de clasificación, encuentre los límites de decisión y los niveles de reconstrucción para minimizar la distorsión resultante. ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle f(x)}$ ${\displaystyle M}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle \{y_{k}\}_{k=1}^{M}}$

${\displaystyle D=E[(x-Q(x))^{2}]=\int _{-\infty }^{\infty }(x-Q(x))^{2}f(x)dx=\sum _{k=1}^{M}\int _{b_{k-1}}^{b_{k}}(x-y_{k})^{2}f(x)dx=\sum _{k=1}^{M}d_{k}}$.

Encontrar una solución óptima al problema anterior da como resultado un cuantificador a veces llamado solución MMSQE (error de cuantificación cuadrático medio mínimo), y el cuantificador PDF optimizado (no uniforme) resultante se conoce como cuantificador Lloyd-Max , llamado así por dos personas que desarrollaron independientemente métodos iterativos ^{[6] [21] [22]} para resolver los dos conjuntos de ecuaciones simultáneas resultantes de y , de la siguiente manera: ${\displaystyle {\partial D/\partial b_{k}}=0}$ ${\displaystyle {\partial D/\partial y_{k}}=0}$

${\displaystyle {\partial D \over \partial b_{k}}=0\Rightarrow b_{k}={y_{k}+y_{k+1} \over 2}}$,

que coloca cada umbral en el punto medio entre cada par de valores de reconstrucción, y

${\displaystyle {\partial D \over \partial y_{k}}=0\Rightarrow y_{k}={\int _{b_{k-1}}^{b_{k}}xf(x)dx \over \int _{b_{k-1}}^{b_{k}}f(x)dx}={\frac {1}{p_{k}}}\int _{b_{k-1}}^{b_{k}}xf(x)dx}$

que coloca cada valor de reconstrucción en el centroide (valor esperado condicional) de su intervalo de clasificación asociado.

El algoritmo del Método I de Lloyd , descrito originalmente en 1957, se puede generalizar de manera sencilla para su aplicación a datos vectoriales. Esta generalización da como resultado los métodos de optimización del clasificador Linde–Buzo–Gray (LBG) o k-means . Además, la técnica se puede generalizar aún más de manera sencilla para incluir también una restricción de entropía para datos vectoriales. ^[23]

Cuantización uniforme y aproximación de 6 dB/bit

El cuantificador Lloyd-Max es en realidad un cuantificador uniforme cuando la PDF de entrada se distribuye uniformemente en el rango . Sin embargo, para una fuente que no tiene una distribución uniforme, el cuantificador de distorsión mínima puede no ser un cuantificador uniforme. El análisis de un cuantificador uniforme aplicado a una fuente distribuida uniformemente se puede resumir de la siguiente manera: ${\displaystyle [y_{1}-\Delta /2,~y_{M}+\Delta /2)}$

Una fuente simétrica X se puede modelar con , para y 0 en cualquier otro lugar. El tamaño del paso y la relación señal/ruido de cuantificación (SQNR) del cuantificador es ${\displaystyle f(x)={\tfrac {1}{2X_{\max }}}}$ ${\displaystyle x\in [-X_{\max },X_{\max }]}$ ${\displaystyle \Delta ={\tfrac {2X_{\max }}{M}}}$

${\displaystyle {\rm {SQNR}}=10\log _{10}{\frac {\sigma _{x}^{2}}{\sigma _{q}^{2}}}=10\log _{10}{\frac {(M\Delta )^{2}/12}{\Delta ^{2}/12}}=10\log _{10}M^{2}=20\log _{10}M}$.

Para un código de longitud fija que utiliza bits, , lo que da como resultado , ${\displaystyle N}$ ${\displaystyle M=2^{N}}$ ${\displaystyle {\rm {SQNR}}=20\log _{10}{2^{N}}=N\cdot (20\log _{10}2)=N\cdot 6.0206\,{\rm {dB}}}$

o aproximadamente 6 dB por bit. Por ejemplo, para =8 bits, =256 niveles y SQNR = 8×6 = 48 dB; y para =16 bits, =65536 y SQNR = 16×6 = 96 dB. La propiedad de una mejora de 6 dB en SQNR por cada bit adicional utilizado en la cuantificación es una cifra de mérito bien conocida. Sin embargo, debe utilizarse con cuidado: esta derivación es solo para un cuantificador uniforme aplicado a una fuente uniforme. Para otras PDF de fuente y otros diseños de cuantificadores, el SQNR puede ser algo diferente del predicho por 6 dB/bit, dependiendo del tipo de PDF, el tipo de fuente, el tipo de cuantificador y el rango de velocidad de bits de operación. ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle M}$

Sin embargo, es común suponer que para muchas fuentes, la pendiente de una función SQNR de cuantificador puede aproximarse a 6 dB/bit cuando se opera a una tasa de bits suficientemente alta. A tasas de bits asintóticamente altas, reducir el tamaño del paso a la mitad aumenta la tasa de bits en aproximadamente 1 bit por muestra (porque se necesita 1 bit para indicar si el valor está en la mitad izquierda o derecha del intervalo anterior de tamaño doble) y reduce el error cuadrático medio en un factor de 4 (es decir, 6 dB) según la aproximación. ${\displaystyle \Delta ^{2}/12}$

A tasas de bits asintóticamente altas, la aproximación de 6 dB/bit está respaldada por un análisis teórico riguroso para muchas PDF de origen. ^{[2] [3] [5] [6]} Además, la estructura del cuantificador escalar óptimo (en el sentido de tasa-distorsión) se aproxima a la de un cuantificador uniforme en estas condiciones. ^{[5] [6]}

En otros campos

En realidad, muchas magnitudes físicas están cuantificadas por entidades físicas. Entre los campos en los que se aplica esta limitación se incluyen la electrónica (debido a los electrones ), la óptica (debido a los fotones ), la biología (debido al ADN ), la física (debido a los límites de Planck ) y la química (debido a las moléculas ).

Véase también

• Codificador beta
• Cuantización de color
• Agrupamiento de datos
• Discretización
• Error de discretización
• Posterización
• Modulación por código de pulsos
• Cuantil
• Cuantización (procesamiento de imágenes)
• Dilución de regresión : un sesgo en las estimaciones de parámetros causado por errores como la cuantificación en la variable explicativa o independiente.

Notas

1. También se pueden considerar otras medidas de distorsión, aunque el error cuadrático medio es una de las más populares.

Referencias

1. Sheppard, WF (1897). "Sobre el cálculo de los valores más probables de constantes de frecuencia para datos ordenados según la división equidistante de una escala". Actas de la London Mathematical Society . s1-29 (1). Wiley: 353–380. doi :10.1112/plms/s1-29.1.353. ISSN  0024-6115.
2. WR Bennett, "Espectros de señales cuantificadas", Bell System Technical Journal , vol. 27, págs. 446–472, julio de 1948.
3. Oliver, BM; Pierce, JR; Shannon, CE (1948). "La filosofía de PCM". Actas del IRE . 36 (11). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 1324–1331. doi :10.1109/jrproc.1948.231941. ISSN  0096-8390. S2CID  51663786.
4. Seymour Stein y J. Jay Jones, Principios de comunicación moderna , McGraw–Hill , ISBN 978-0-07-061003-3 , 1967 (pág. 196). 
5. Gish, H.; Pierce, J. (1968). "Cuantización asintóticamente eficiente". IEEE Transactions on Information Theory . 14 (5). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 676–683. doi :10.1109/tit.1968.1054193. ISSN  0018-9448.
6. Gray, RM ; Neuhoff, DL (1998). "Cuantización". IEEE Transactions on Information Theory . 44 (6). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 2325–2383. doi :10.1109/18.720541. ISSN  0018-9448. S2CID  212653679.
7. Allen Gersho ; Robert M. Gray (1991). Cuantización vectorial y compresión de señales. Springer . ISBN 978-0-7923-9181-4.
8. Hodgson, Jay (2010). Understanding Records (Entendiendo los registros), pág. 56. ISBN 978-1-4411-5607-5 . Adaptado de Franz, David (2004). Recording and Producing in the Home Studio (Grabación y producción en el estudio casero ), págs. 38-9. Berklee Press. 
9. Gersho, A. (1977). "Cuantización". Revista de la Sociedad de Comunicaciones IEEE . 15 (5). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 16–28. doi :10.1109/mcom.1977.1089500. ISSN  0148-9615. S2CID  260498692.
10. Rabbani, Majid; Joshi, Rajan L.; Jones, Paul W. (2009). "Sección 1.2.3: Cuantización, en el Capítulo 1: Sistema de codificación básica JPEG 2000 (Parte 1)". En Schelkens, Peter; Skodras, Athanassios; Ebrahimi, Touradj (eds.). La suite JPEG 2000. John Wiley & Sons . págs. 22–24. ISBN. 978-0-470-72147-6.
11. Taubman, David S.; Marcellin, Michael W. (2002). "Capítulo 3: Cuantización". JPEG2000: Fundamentos, estándares y prácticas de compresión de imágenes . Kluwer Academic Publishers . pág. 107. ISBN. 0-7923-7519-X.
12. Sullivan, GJ (1996). "Cuantización escalar eficiente de variables aleatorias exponenciales y laplacianas". IEEE Transactions on Information Theory . 42 (5). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 1365–1374. doi :10.1109/18.532878. ISSN  0018-9448.
13. Widrow, B. (1956). "Un estudio de cuantificación de amplitud aproximada mediante la teoría de muestreo de Nyquist". IRE Transactions on Circuit Theory . 3 (4). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 266–276. doi :10.1109/tct.1956.1086334. hdl : 1721.1/12139 . ISSN  0096-2007. S2CID  16777461.
14. Bernard Widrow , "Análisis estadístico de sistemas de datos muestreados cuantificados en amplitud", Trans. AIEE Pt. II: Appl. Ind. , Vol. 79, págs. 555–568, enero de 1961.
15. Marco, D.; Neuhoff, DL (2005). "La validez del modelo de ruido aditivo para cuantificadores escalares uniformes". IEEE Transactions on Information Theory . 51 (5). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 1739–1755. doi :10.1109/tit.2005.846397. ISSN  0018-9448. S2CID  14819261.
16. Pohlman, Ken C. (1989). Principios del audio digital 2.ª edición. SAMS. pág. 60. ISBN 9780071441568.
17. Watkinson, John (2001). El arte del audio digital 3.ª edición . Focal Press . ISBN 0-240-51587-0.
18. Farvardin, N. ; Modestino, J. (1984). "Rendimiento óptimo del cuantificador para una clase de fuentes sin memoria no gaussianas". IEEE Transactions on Information Theory . 30 (3). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 485–497. doi :10.1109/tit.1984.1056920. ISSN  0018-9448.(Sección VI.C y Apéndice B)
19. Berger, T. (1972). "Cuantizadores óptimos y códigos de permutación". IEEE Transactions on Information Theory . 18 (6). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 759–765. doi :10.1109/tit.1972.1054906. ISSN  0018-9448.
20. Berger, T. (1982). "Cuantizadores de entropía mínima y códigos de permutación". IEEE Transactions on Information Theory . 28 (2). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 149–157. doi :10.1109/tit.1982.1056456. ISSN  0018-9448.
21. Lloyd, S. (1982). "Cuantización de mínimos cuadrados en PCM". IEEE Transactions on Information Theory . 28 (2). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 129–137. CiteSeerX 10.1.1.131.1338 . doi :10.1109/tit.1982.1056489. ISSN  0018-9448. S2CID  10833328. (trabajo documentado en un manuscrito circulado para comentarios en los Laboratorios Bell con fecha de registro del departamento del 31 de julio de 1957 y también presentado en la reunión de 1957 del Instituto de Estadística Matemática , aunque no se publicó formalmente hasta 1982).
22. Max, J. (1960). "Cuantización para una distorsión mínima". IEEE Transactions on Information Theory . 6 (1). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 7–12. doi :10.1109/tit.1960.1057548. ISSN  0018-9448.
23. Chou, PA; Lookabaugh, T.; Gray, RM (1989). "Cuantización vectorial con restricciones de entropía". IEEE Transactions on Acoustics, Speech, and Signal Processing . 37 (1). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 31–42. doi :10.1109/29.17498. ISSN  0096-3518.

• Sawood, Khalid (2005), Introducción a la compresión de datos, tercera edición , Morgan Kaufmann, ISBN 978-0-12-620862-7
• Jayant, Nikil S.; Noll, Peter (1984), Codificación digital de formas de onda: principios y aplicaciones al habla y al vídeo , Prentice–Hall, ISBN 978-0-13-211913-9
• Gregg, W. David (1977), Comunicación analógica y digital , John Wiley, ISBN 978-0-471-32661-8
• Stein, Seymour; Jones, J. Jay (1967), Principios de comunicación moderna , McGraw–Hill , ISBN 978-0-07-061003-3

Lectura adicional

• Bernard Widrow; István Kollár (2007). Ruido de cuantificación en computación digital, procesamiento de señales y control. Cambridge University Press. ISBN 9780521886710.

Véase también

• El recuento mínimo