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 cuantizació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 hasta cierto punto en casi todo el procesamiento de señales digitales, ya que el proceso de representar una señal en forma digital normalmente 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 función algorítmica que realiza una cuantificación se llama 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 de cuantificador muy básico: uno uniforme . Un cuantificador uniforme típico ( en la mitad de la banda de rodadura ) 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 suelo . ${\displaystyle \lfloor \ \rfloor }$

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

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

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

La propiedad esencial de un cuantificador es tener un conjunto contable de posibles valores de salida miembros más pequeños 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 igual a cualquier otro valor entero, este cuantificador tiene entradas con valores reales y salidas con valores enteros. ${\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 en la señal que se está cuantificando, 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 . Agregar un bit al cuantificador reduce a la mitad el valor de Δ, lo que reduce la potencia del ruido en el factor ${\displaystyle \Delta ^{2}/12}$1/4. En términos de decibelios , 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, a las que se puede hacer referencia como 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 ejemplo de cuantificador uniforme 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 se pueden comunicar 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 mapee 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 de tabla para mapear cada índice de cuantificación a un valor de reconstrucción correspondiente. Esta descomposición en dos etapas se aplica igualmente bien a 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 dado sólo 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 contablemente infinito . ^[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 (con valores vectoriales). ^[7]

Tipos

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

Resolución de 3 bits con ocho niveles.

Conversor analógico a digital

Un convertidor analógico a 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 de tiempo discreto , 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 habitual 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 palabras 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 velocidad-distorsión

La cuantificación optimizada para la distorsión de la velocidad se encuentra en la codificación fuente 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 velocidad 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 velocidad de bits ) que se utiliza para representar la salida del cuantificador y estudiar la pérdida de precisión que introduce el proceso de cuantificación (que se conoce como distorsión ).

Cuantizadores uniformes de media contrahuella y media banda de rodadura

La mayoría de los cuantificadores uniformes para datos de entrada con signo se pueden clasificar en uno de dos tipos: de media altura y de media banda de rodadura . 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 de mitad de escalón tienen un nivel de reconstrucción de valor cero (correspondiente a un escalón de una escalera), mientras que los cuantificadores de mitad de contrahuella tienen un umbral de clasificación de valor cero (correspondiente a un contrahuella de una escalera). ^[9]

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

La cuantización de media altura implica truncamiento. La fórmula de entrada-salida para un cuantificador uniforme de columna media 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 está 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 media altura 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 media banda de rodadura tienen un nivel de salida cero. Para algunas aplicaciones, puede ser necesario tener una representación de señal de salida cero.

En general, un cuantificador de media altura o de media banda de rodadura 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 espacio entre sus posibles valores de salida puede no ser todos iguales. . La característica distintiva de un cuantificador de banda media es que tiene un valor de umbral de clasificación que es exactamente cero, y la característica distintiva de un cuantificador de banda media 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 mitad de banda con comportamiento simétrico alrededor de 0. La región alrededor del valor de salida cero de dicho cuantificador se conoce como zona muerta o banda muerta . La zona muerta a veces puede tener el mismo propósito que una puerta de ruido o una función de silenciamiento . Especialmente para aplicaciones de compresión, a la zona muerta se le puede dar un ancho diferente al de los otros pasos. Para un cuantificador 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 signo (también conocida como función signum ). La regla general de reconstrucción para dicho cuantificador de zona muerta 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 compensación de reconstrucción en el rango de 0 a 1 como una fracción del tamaño del paso. Normalmente, 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 optimización que se describe a continuación, a menudo simplemente se establece en una constante, como por ejemplo . (Tenga en cuenta que en esta definición, debido a la definición de la función () , no tiene ningún 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únmente utilizado (por ejemplo, el esquema típicamente utilizado en contabilidad financiera y matemáticas elementales) es establecer y para todos . 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 igualmente espaciados. ${\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 manera similar al ruido blanco aditivo : tiene 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 usa comúnmente para el análisis de los efectos del error de cuantificación en sistemas de filtrado digital y puede resultar 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 fluidos. ^{[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 tanto, las señales periódicas pueden crear ruido de cuantificación periódico. Y en algunos casos incluso puede provocar que aparezcan 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 fuente es realizar una cuantificación difuminada (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 mayor 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 cuadrático medio (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 y el valor RMS es . Aunque el redondeo produce menos error RMS que el truncamiento, la diferencia se debe únicamente al término estático (DC) de . Los valores RMS del error de CA son exactamente los mismos en ambos casos, por lo que no existe ninguna ventaja especial de redondear sobre el truncamiento en situaciones en las que el término de CC del error puede ignorarse (como en los sistemas acoplados a CA). 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 potencial de potencia señal-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 depende 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 están por encima de la mitad de la frecuencia de muestreo, volverán a formar un alias en la banda de interés. Para que el error de cuantificación sea independiente de la señal de entrada, la señal se trama agregando ruido a la señal. 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 mensurable en los niveles de ruido.

El ruido de cuantificación es un modelo de 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) puede ser calculado 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 en dientes 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, en cambio, la ecuación correspondiente es

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

Aquí se supone una vez más que el ruido de cuantificación está distribuido 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 entre señal y ruido sólo se produce debido a que la señal es una onda sinusoidal de escala completa en lugar de un triángulo o un diente de sierra.

Para señales complejas en ADC de alta resolución, este es un modelo preciso. Para los ADC de baja resolución, las señales de bajo nivel en los ADC de alta resolución y las formas de onda simples, el ruido de cuantificación no se distribuye uniformemente, 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 son relativos a los datos de entrada a gran escala. 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 analógica, pero esto puede introducir 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 valores de salida posibles y realizar recortes 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 por sobrecarga . Dentro de los límites extremos del rango admitido, la cantidad de espaciado entre los valores de salida seleccionables de un cuantificador se denomina granularidad , y el error introducido por este espaciado se denomina distorsión granular . Es común que el diseño de un cuantificador implique determinar el equilibrio adecuado entre distorsión granular y distorsión de sobrecarga. Para un número determinado de valores de salida posibles, 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, de manera equivalente, el tamaño del paso de cuantificación ) para lograr el equilibrio apropiado 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 contablemente infinito de valores de salida seleccionables). ^[6] ${\displaystyle \Delta }$

Diseño de cuantificador de velocidad-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 que no se superponen , definiendo valores de límite de decisión , tales como para , con los límites extremos definidos por y . Todas las entradas que caen en un rango de intervalo determinado 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)}$

Se pueden aplicar técnicas de codificación de entropía para comunicar los índices de cuantificación desde un codificador fuente 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 binario . Una consideración importante es el número de bits utilizados para cada palabra de código, indicado 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 velocidad 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 está 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 velocidad 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 clave , mientras que la distorsión depende de los límites de decisión y 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 de distorsión para un problema de diseño de cuantificador se puede expresar de dos maneras:

1. Dada una restricción de distorsión máxima , minimice la velocidad 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 aproximadamente) convirtiendo la formulación al problema sin restricciones donde el multiplicador de Lagrange es una constante no negativa que establece el equilibrio apropiado entre tasa y distorsión. Resolver el problema no restringido equivale a encontrar un punto en el casco convexo de la familia de soluciones para una formulación restringida equivalente del problema. Sin embargo, encontrar una solución (especialmente una solución cerrada ) a cualquiera de estas tres formulaciones de problemas puede resultar difícil. Se han publicado soluciones que no requieren técnicas de optimización iterativa multidimensional para solo tres PDF: las distribuciones uniforme, ^[18] exponencial , ^[12] y laplaciana ^{[12] .} Se pueden utilizar enfoques de optimización iterativos 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 sólo la distorsión (no afectan la velocidad de bits) y que cada individuo hace una contribución separada 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 obtiene estableciendo el valor de reconstrucción dentro de cada intervalo en el valor esperado condicional (también conocido como centroide ) dentro del intervalo, como se indica por: ${\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 entrópica suficientemente bien diseñadas puede dar como resultado el uso de una velocidad de bits cercana al verdadero contenido de información 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 separar el problema de diseño de codificación entrópica del diseño del cuantificador en sí. Las técnicas modernas de codificación por entropía, 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 forma 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 también puede incluir la optimización del valor de . Para algunos modelos de fuentes probabilísticas, el mejor rendimiento se puede lograr cuando se aproxima al infinito. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

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

En la formulación anterior, si se ignora la restricción de velocidad de bits al establecerla en 0, o de manera equivalente, 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 distorsión de velocidad), 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 nivel se pueden codificar usando un código de longitud fija usando bits/símbolo. Por ejemplo, cuando hay 256 niveles, la velocidad de bits del FLC es de 8 bits/símbolo. Por esta razón, a este tipo de cuantificador se le ha denominado en ocasiones cuantificador 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 entrópica. ${\displaystyle M}$ ${\displaystyle R=\lceil \log _{2}M\rceil }$ ${\displaystyle M=}$ ${\displaystyle R}$

Suponiendo un FLC con niveles, el problema de minimización de la distorsión de la velocidad se puede reducir únicamente a la minimización de la distorsión. El problema reducido se puede plantear de la siguiente manera: dada una fuente con PDF y la restricción de que el cuantificador debe usar 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 denominado solución MMSQE (error de cuantificación cuadrático medio mínimo), y el cuantificador PDF optimizado (no uniforme) resultante se denomina cuantificador Lloyd -Max , que lleva el nombre de dos personas que desarrollaron de forma independiente 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 forma 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-medias . Además, la técnica se puede generalizar aún más de forma sencilla para incluir también una restricción de entropía para los 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 en lo siguiente: ${\displaystyle [y_{1}-\Delta /2,~y_{M}+\Delta /2)}$

Una fuente simétrica X se puede modelar con , para y 0 en otros lugares. El tamaño del paso y la relación señal/ruido de cuantificación (SQNR) del cuantificador son ${\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 figura de mérito bien conocida. Sin embargo, debe usarse con cuidado: esta derivación es sólo para un cuantificador uniforme aplicado a una fuente uniforme. Para otros PDF de origen y otros diseños de cuantificadores, el SQNR puede ser algo diferente del previsto 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 la función SQNR de un cuantificador se puede aproximar a 6 dB/bit cuando se opera a una velocidad de bits suficientemente alta. A velocidades de bits asintóticamente altas, reducir el tamaño del paso a la mitad aumenta la velocidad 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 de doble tamaño anterior) y reduce el error cuadrático medio por un factor de 4 (es decir, 6 dB) según la aproximación. ${\displaystyle \Delta ^{2}/12}$

A velocidades de bits asintóticamente altas, la aproximación de 6 dB/bit es compatible con muchos archivos PDF de origen mediante análisis teóricos rigurosos. ^{[2] [3] [5] [6]} Además, la estructura del cuantificador escalar óptimo (en el sentido de distorsión de velocidad) se aproxima a la de un cuantificador uniforme en estas condiciones. ^{[5] [6]}

En otros campos

En realidad, muchas cantidades físicas están cuantificadas por entidades físicas. Ejemplos de campos donde se aplica esta limitación 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 ).

Ver también

• Codificador beta
• Cuantización de color
• Agrupación de datos
• Discretización
• Error de discretización
• Posterización
• Modulación de código de pulso
• 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 división equidistante de una escala". Actas de la Sociedad Matemática de Londres . Wiley. T1-29 (1): 353–380. doi :10.1112/plms/s1-29.1.353. ISSN  0024-6115.
2. WR Bennett, "Espectros de señales cuantificadas", Revista técnica de Bell System , vol. 27, págs. 446–472, julio de 1948.
3. Oliver, BM; Pierce, JR; Shannon, CE (1948). "La Filosofía del PCM". Actas del IRE . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 36 (11): 1324-1331. doi :10.1109/jrproc.1948.231941. ISSN  0096-8390. S2CID  51663786.
4. Seymour Stein y J. Jay Jones, Principios de comunicación modernos , McGraw-Hill , ISBN 978-0-07-061003-3 , 1967 (p. 196). 
5. , H.; Pierce, J. (1968). "Cuantización asintóticamente eficiente". Transacciones IEEE sobre teoría de la información . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 14 (5): 676–683. doi :10.1109/tit.1968.1054193. ISSN  0018-9448.
6. Gray, RM ; Neuhoff, DL (1998). "Cuantización". Transacciones IEEE sobre teoría de la información . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 44 (6): 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. Saltador . ISBN 978-0-7923-9181-4.
8. Hodgson, Jay (2010). Comprensión de los registros , p.56. ISBN 978-1-4411-5607-5 . Adaptado de Franz, David (2004). Grabar y producir en el Home Studio , p.38-9. Prensa Berklee. 
9. Gersho, A. (1977). "Cuantización". Revista de la Sociedad de Comunicaciones IEEE . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 15 (5): 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 central JPEG 2000 (Parte 1)". En Schelkens, Peter; Skodras, Atanasio; Ebrahimi, Touradj (eds.). La suite JPEG 2000 . John Wiley e hijos . págs. 22-24. ISBN 978-0-470-72147-6.
11. Taubman, David S.; Marcelino, Michael W. (2002). "Capítulo 3: Cuantización". JPEG2000: Fundamentos, estándares y práctica de la compresión de imágenes . Editores académicos de Kluwer . pag. 107.ISBN​ 0-7923-7519-X.
12. Sullivan, GJ (1996). "Cuantización escalar eficiente de variables aleatorias exponenciales y laplacianas". Transacciones IEEE sobre teoría de la información . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 42 (5): 1365-1374. doi : 10.1109/18.532878. ISSN  0018-9448.
13. Viuda, B. (1956). "Un estudio de cuantificación aproximada de amplitud mediante la teoría del muestreo de Nyquist". Transacciones IRE sobre teoría de circuitos . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 3 (4): 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: Aplica. Indiana , 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". Transacciones IEEE sobre teoría de la información . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 51 (5): 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. pag. 60.ISBN​ 9780071441568.
17. Watkinson, John (2001). El arte del audio digital 3ª edición . Prensa Focal . ISBN 0-240-51587-0.
18. Farvardin, N .; Modestino, J. (1984). "Rendimiento óptimo del cuantificador para una clase de fuentes sin memoria no gaussianas". Transacciones IEEE sobre teoría de la información . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 30 (3): 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". Transacciones IEEE sobre teoría de la información . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 18 (6): 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". Transacciones IEEE sobre teoría de la información . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 28 (2): 149-157. doi :10.1109/tit.1982.1056456. ISSN  0018-9448.
21. Lloyd, S. (1982). "Cuantización de mínimos cuadrados en PCM". Transacciones IEEE sobre teoría de la información . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 28 (2): 129-137. CiteSeerX 10.1.1.131.1338 . doi :10.1109/tit.1982.1056489. ISSN  0018-9448. S2CID  10833328. (trabajo documentado en un manuscrito distribuido para comentarios en Bell Laboratories 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". Transacciones IEEE sobre teoría de la información . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 6 (1): 7–12. doi :10.1109/tit.1960.1057548. ISSN  0018-9448.
23. Chou, Pensilvania; Lookabaugh, T.; Gris, RM (1989). "Cuantización de vectores restringida por entropía". Transacciones IEEE sobre acústica, voz y procesamiento de señales . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 37 (1): 31–42. doi :10.1109/29.17498. ISSN  0096-3518.

• Sayood, 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 la comunicación moderna , McGraw-Hill , ISBN 978-0-07-061003-3

Otras lecturas

• Bernardo viuda; István Kollár (2007). Ruido de cuantificación en Computación Digital, Procesamiento de Señales y Control. Prensa de la Universidad de Cambridge. ISBN 9780521886710.

Ver también

• Menos recuento