Cuantificación (procesamiento de señales) - Quantization (signal processing)

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 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 la cuantificación se denomina cuantificador . Un convertidor de 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 de piso . ${\ Displaystyle \ lfloor \ \ rfloor}$

La propiedad esencial de un cuantificador es tener un conjunto contable de posibles miembros de valores de salida más pequeño que el conjunto de posibles valores de entrada. Los miembros del conjunto de valores de salida pueden tener valores enteros, racionales o reales. Para redondeo simple al número 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 en la señal que se cuantifica, es relativamente sencillo mostrar que el error cuadrático medio producido por tal operación de redondeo será aproximadamente . 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 de ruido en el factor ¼. En términos de decibelios , el cambio de potencia de ruido es${\ Displaystyle \ Delta ^ {2} / 12}$${\ 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 mapea el valor de entrada a un índice de cuantificación entero y la etapa de reconstrucción mapea 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 se pueden comunicar los datos cuantificados 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 usar 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 conceptual (o literalmente) una operación de búsqueda de tablas 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 cuantificadores vectoriales y escalares.

Propiedades matematicas

Debido a que la cuantificación es un mapeo 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 solo el valor de salida).

El conjunto de posibles valores de entrada puede ser infinitamente grande, y posiblemente puede ser 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 numerable . 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).

Tipos

Resolución de 2 bits con cuatro niveles de cuantificación en comparación con la analógica.

Resolución de 3 bits con ocho niveles.

Conversor analógico a digital

Un convertidor de 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. Por lo general, estos valores discretos se representan 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 denominada 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 la distorsión de la frecuencia

La cuantificación optimizada de la distorsión de velocidad se encuentra en la codificación de origen 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 cuantificación en este contexto implica estudiar la cantidad de datos (normalmente medidos en dígitos o bits o tasa 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 la distorsión ).

Cuantificadores uniformes de media y media banda de rodadura

La mayoría de los cuantificadores uniformes para datos de entrada firmados pueden clasificarse en 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 de medio escalón tienen un nivel de reconstrucción de valor cero (correspondiente a un escalón de una escalera), mientras que los cuantificadores de medio escalón tienen un umbral de clasificación de valor cero (correspondiente a un escalón de una escalera).

La cuantificación de 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 cuantificación de media altura implica truncamiento. La fórmula de entrada-salida para un cuantificador uniforme de media altura 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 media altura no tienen un valor de salida cero; su magnitud de salida mínima es la mitad del tamaño de paso. Por el contrario, los cuantificadores de banda intermedia 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 media altura o 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 que no sean todos iguales, o el espacio entre sus posibles valores de salida puede que no sean todos iguales. . La característica distintiva de un cuantificador de media altura es que tiene un valor de umbral de clasificación que es exactamente cero, y la característica distintiva de un cuantificador de media banda es que tiene un valor de reconstrucción que es exactamente cero.

Cuantificadores de zona muerta

Un cuantificador de zona muerta es un tipo de cuantificador de medio paso con comportamiento simétrico alrededor de 0. La región alrededor del valor de salida cero de dicho cuantificador se denomina 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, la zona muerta puede tener un ancho diferente al de los otros pasos. Para un cuantificador uniforme, el ancho de la zona muerta se puede establecer en cualquier valor mediante la regla de cuantificación directa. ${\ 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 conocido como el signum función). La regla de reconstrucción general para tal 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, al cuantificar 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 que se describe a continuación, a menudo se establece simplemente en una constante, como . (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 de uso muy común (por ejemplo, el esquema que se usa típicamente en contabilidad financiera y matemáticas elementales) es establecer y para todos . En este caso, el cuantificador de zona muerta es también 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 están igualmente espaciados también. ${\ 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 a la del ruido blanco aditivo , teniendo una correlación insignificante con la señal y una densidad espectral de potencia aproximadamente plana . El modelo de ruido aditivo se utiliza habitualmente 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 fuerza de la señal) con PDF suaves. ${\ 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 determinísticamente 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ódica. 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 asegurar la independencia efectiva del error de cuantificación de la señal fuente es realizar una cuantificación difusa (a veces con modelado de ruido ), que implica agregar ruido aleatorio (o pseudoaleatorio ) a la señal antes de la cuantificación.

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 se correlaciona significativamente 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 . 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 de señal a 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 10 \ cdot \ log _ {10} (4)}$

A amplitudes más bajas, el error de cuantificación se vuelve dependiente de la señal de entrada, lo que resulta en 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 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 difumina añadiendo ruido a la señal. Esto reduce ligeramente la relación señal / ruido, pero puede eliminar por completo la distorsión.

Modelo de cuantificación de ruido

Ruido de cuantificación para un ADC de 2 bits que funciona a una frecuencia de muestreo infinita . La diferencia entre las señales azul y roja en el gráfico superior es el error de cuantificación, que se "suma" a la señal cuantificada y es la fuente de ruido.

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 pisos de ruido.

El ruido de cuantificación es un modelo de error de cuantificación introducido por cuantificación en el ADC. Es un error de redondeo entre el voltaje de entrada analógica al ADC y el valor digitalizado de salida. El ruido no es lineal y depende de la señal. Se puede modelar de varias formas 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}) \ aproximadamente 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 con esto son las ondas triangulares de amplitud completa y las ondas en diente de sierra .

Por ejemplo, un ADC de 16 bits tiene una relación máxima de señal a ruido de cuantificación 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} \ aproximadamente 1.761 + 6.02 \ cdot Q \ \ mathrm {dB} \, \!}$

Aquí, es una vez más el ruido de cuantificación supone para ser distribuida de manera uniforme. Cuando la señal de entrada tiene una gran amplitud y un amplio espectro de frecuencias, este es el caso. 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 ocurre debido a que la señal es una onda sinusoidal a gran escala en lugar de un triángulo o diente de sierra.

Para señales complejas en ADC de alta resolución, este es un modelo preciso. Para ADC de baja resolución, señales de bajo nivel en ADC de alta resolución y para formas de onda simples, el ruido de cuantificación no se distribuye uniformemente, lo que hace que este modelo sea inexacto. 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 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 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 posibles valores de salida 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 denomina distorsión por sobrecarga . Dentro de los límites extremos del rango admitido, la cantidad de espacio entre los valores de salida seleccionables de un cuantificador se denomina granularidad , y el error introducido por este espacio se denomina distorsión granular . Es común que el diseño de un cuantificador implique la determinación del equilibrio adecuado entre la distorsión granular y la distorsión por sobrecarga. Para un número admitido dado de posibles valores de salida, 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 infinito numerable de valores de salida seleccionables). ${\ Displaystyle \ Delta}$

Diseño de cuantificador de distorsión de frecuencia

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 señal de entrada en que no se superponen los intervalos , mediante la definición de frontera de decisión valores , 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)}$

Se pueden aplicar técnicas de codificación de entropía 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 la cantidad de bits utilizados para cada palabra de código, indicada aquí por . Como resultado, el diseño de un cuantificador -level y un conjunto asociado de palabras de código para comunicar sus valores índice requiere la búsqueda de los valores de , y que satisfacer de manera óptima un conjunto seleccionado de las restricciones de diseño tales como la tasa de bits y la distorsión . ${\ Displaystyle k}$${\ Displaystyle c_ {k}}$${\ Displaystyle \ mathrm {longitud} (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 un PDF asociado , la probabilidad de que la variable aleatoria se encuentre 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 {longitud} (c_ {k}) = \ sum _ {k = 1} ^ {M} \ mathrm { longitud} (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, la distorsión D viene dada por:

${\ Displaystyle D = E [(xQ (x)) ^ {2}] = \ int _ {- \ infty} ^ {\ infty} (xQ (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 las longitudes de las palabras de código , 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 {longitud} (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 distorsión de velocidad para un problema de diseño de cuantificador se puede expresar de dos formas:

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 puede expresarse y resolverse de manera equivalente (o aproximadamente) convirtiendo la formulación al problema no restringido 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 es equivalente a encontrar un punto en el casco convexo de la familia de soluciones a una formulación restringida equivalente del problema. Sin embargo, puede resultar difícil encontrar una solución, especialmente una solución de forma cerrada , a cualquiera de estas tres formulaciones de problemas. Las soluciones que no requieren técnicas de optimización iterativa multidimensional se han publicado solo para tres PDF: las distribuciones uniforme, exponencial y laplaciana . Los enfoques de optimización iterativa se pueden utilizar para encontrar soluciones en otros casos. ${\ Displaystyle \ min \ left \ {D + \ lambda \ cdot R \ right \}}$ ${\ Displaystyle \ lambda}$

Tenga en cuenta que los valores de reconstrucción afectan solo a la distorsión (no afectan la tasa 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 mostrar fácilmente que el conjunto óptimo de valores de reconstrucción se da estableciendo el valor de reconstrucción dentro de cada intervalo al valor esperado condicional (también denominado 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 de entropía suficientemente bien diseñadas puede resultar en el uso de una tasa de bits cercana al contenido de información real de los índices , de manera que efectivamente ${\ Displaystyle \ {k \} _ {k = 1} ^ {M}}$

${\ Displaystyle \ mathrm {longitud} (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 del diseño de la codificación de entropía se separe del diseño del cuantificador en sí. Las técnicas modernas de codificación de 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 del diseño del cuantificador también puede incluir la optimización del valor de . Para algunos modelos fuente probabilísticos, el mejor rendimiento se puede lograr cuando se acerca al infinito. ${\ Displaystyle M}$${\ Displaystyle M}$${\ Displaystyle M}$

Ignorar 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 al establecer un valor igual a 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 la distorsión de la velocidad), el problema de optimización se reduce a la minimización de la distorsión solamente. ${\ 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 tasa de bits de FLC es de 8 bits / símbolo. Por esta razón, este cuantificador a veces se ha denominado 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 de entropía. ${\ 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 a la minimización de la distorsión solamente. 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 [(xQ (x)) ^ {2}] = \ int _ {- \ infty} ^ {\ infty} (xQ (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 que a veces se denomina solución MMSQE (error de cuantificación cuadrático medio mínimo), y el cuantificador optimizado para PDF (no uniforme) resultante se denomina cuantificador Lloyd-Max , que lleva el nombre de dos personas que desarrollaron de forma independiente métodos iterativos para resolver los dos conjuntos de ecuaciones simultáneas resultantes de y , de la siguiente manera: ${\ Displaystyle {\ parcial D / \ parcial b_ {k}} = 0}$${\ Displaystyle {\ parcial D / \ parcial y_ {k}} = 0}$

${\ Displaystyle {\ D \ parcial sobre \ parcial b_ {k}} = 0 \ Flecha derecha 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 {\ parcial D \ sobre \ parcial y_ {k}} = 0 \ Flecha derecha y_ {k} = {\ int _ {b_ {k-1}} ^ {b_ {k}} xf (x) dx \ sobre \ 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-means . Además, la técnica se puede generalizar aún más de una manera sencilla para incluir también una restricción de entropía para datos vectoriales.

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

El cuantificador de Lloyd-Max es en realidad un cuantificador uniforme cuando el 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 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 usa 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 solo para un cuantificador uniforme aplicado a una fuente uniforme. Para otros PDF de origen y otros diseños de cuantificador, el SQNR puede ser algo diferente del predicho en 6 dB / bit, según el tipo de PDF, el tipo de fuente, el tipo de cuantificador y el rango de operación de la velocidad de bits. ${\ 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 del cuantificador se puede aproximar a 6 dB / bit cuando funciona a una velocidad de bits suficientemente alta. A velocidades de bits asintóticamente altas, cortar 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 tamaño doble anterior) y reduce el error cuadrático medio por un factor de 4 (es decir, 6 dB) basado en 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 PDF de origen mediante un análisis teórico riguroso. Además, la estructura del cuantificador escalar óptimo (en el sentido de velocidad-distorsión) se aproxima a la de un cuantificador uniforme en estas condiciones.

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
• Binning de datos
• Discretización
• Error de discretización
• Posterización
• Modulación de código de impulsos
• Cuantil
• Cuantización (procesamiento de imágenes)
• Dilución de regresión : un sesgo en las estimaciones de los parámetros causado por errores como la cuantificación en la variable explicativa o independiente.

Notas

Referencias

Otras lecturas

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