Nivel 3 · Lección 9

Una aguja en un pajar: la correlación

La idea en una imagen

Arriba, una señal con ruido en verde, con un chirrido corto escondido en algún sitio. En púrpura, la plantilla: el chirrido tal como lo conocemos, que se desliza por la señal. Abajo, en naranja, el parecido en cada posición: casi plano casi siempre, y con un pico donde la plantilla encaja.

Imagina que buscas una frase en un libro que no sabes en qué página está. Pones tu frase al principio del texto, comparas letra por letra con lo que tienes debajo, anotas cuántas coinciden, la mueves una letra a la derecha y vuelves a comparar, hasta el final. La posición con más coincidencias es donde está la frase. La correlación hace lo mismo con una señal: en cada posición multiplica la plantilla por lo que tiene debajo, punto a punto, y suma.

Con el ruido más fuerte o más débil, la curva de abajo cambia de aspecto, pero el pico sigue en su sitio mientras la plantilla sea lo bastante larga. El mando de la imagen sube el ruido hasta que el chirrido deja de verse en la señal de arriba y, aun así, la curva de abajo lo encuentra.

Paso a paso

La plantilla deslizante

En la lección 4, transformar era medir el parecido: se coloca una noria de prueba junto a la señal, se multiplican las dos punto a punto y se mira el área que queda. Aquí la plantilla no tiene por qué ser una noria. Puede ser cualquier forma que conozcas de antemano, como el chirrido corto que emite un sonar o la forma de onda de una palabra. A la forma conocida que se busca se le llama plantilla.

Se coloca la plantilla sobre el principio de la señal, se multiplican las dos punto a punto, se suman los productos y se apunta el resultado. Después se desliza un paso a la derecha y se repite, hasta llegar al final. La lista de números que sale, uno por cada posición de la plantilla, es la correlación cruzada, y el número de pasos que se ha desplazado la plantilla en cada punto de la lista es el retardo.

Donde la plantilla no se parece a lo que tiene debajo, los productos salen unas veces positivos y otras negativos, y la suma se queda cerca de cero. Donde la plantilla encaja, una cresta cae sobre una cresta y un valle sobre un valle, casi todos los productos salen positivos y la suma salta. Para poder comparar posiciones y señales de distinto volumen, se puede dividir la suma por la energía de la plantilla y por la del trozo de señal que cubre, y entonces el parecido queda entre −1 y 1.

Es casi la misma operación que la convolución de la lección 7, con una diferencia: allí el sello se daba la vuelta antes de deslizarlo, y aquí la plantilla se desliza tal como es.

Encuentra dónde está escondido el chirrido. Arrastra la plantilla púrpura por la señal y mira la curva naranja de abajo, que se va dibujando por donde pasas: cuando la plantilla caiga justo encima del chirrido, saltará el pico.

El pico es muy estrecho: al soltar, si la plantilla queda muy cerca de él, se ajusta sola. Con el teclado, pulsa la gráfica con el tabulador y usa las flechas, de muestra en muestra (con Mayús, de diez en diez).

Por qué gana al ruido

El ruido también se parece un poco a cualquier plantilla, así que la curva nunca es del todo plana. La diferencia está en cómo se suman los productos. Cada punto de la señal que coincide con la plantilla aporta un producto a favor, todos con el mismo signo, y su suma crece en proporción al número de puntos. Los productos del ruido salen unas veces a favor y otras en contra, se anulan a medias, y su suma crece solo como la raíz cuadrada de ese número.

Con cuatro veces más puntos, la señal suma cuatro veces más y el ruido, solo el doble, así que el pico sobresale el doble. Cuanto más larga es la plantilla, mayor es la ventaja, y a esa ventaja se la llama ganancia de procesado. Medida en decibelios, como en la lección 5, vale diez veces el logaritmo del número de puntos: con mil puntos son 30 dB, que es multiplicar por mil la potencia de la señal frente a la del ruido. Por eso una señal puede estar por debajo del ruido en cada instante y, aun así, encontrarse.

En la señal hay escondida una ristra de unos y menos unos, y en cada muestra la señal es unas cuatro veces más débil que el ruido, doce decibelios. Alarga la plantilla hasta que el pico de la curva naranja sobresalga al menos cinco veces por encima del resto de la curva y marque el sitio correcto.

El radar y el sonar

Si conoces la forma de lo que buscas, la mejor plantilla es esa misma forma. Cuando el ruido es blanco, es decir, igual de fuerte en todas las frecuencias, correlacionar con la forma exacta da el pico más alto sobre el ruido que puede dar un sistema lineal. Usar la correlación así se llama filtro adaptado, y la idea se atribuye a D. O. North, que la describió en un informe de los laboratorios RCA de 1943. Con ruidos de otros colores hay que blanquear antes la señal, algo de lo que se ocupa la lección 10.

El radar y el sonar lo usan así. Emiten un pulso de forma conocida y lo que vuelve es una copia retrasada y muy debilitada, enterrada en ruido. Se desliza el pulso sobre lo recibido y el retardo del pico es el tiempo que ha tardado en ir y volver. Como la onda recorre el camino dos veces, el objeto está a la mitad de lo que ha recorrido: la distancia es la velocidad por el tiempo, dividido entre dos.

A 20 °C, el sonido viaja a unos 343 metros por segundo en el aire, a unos 1.480 en agua dulce y a unos 1.540 en agua de mar. En el reto se usa el valor redondeado de 1.500. Con el móvil puedes probarlo: el experimento «Sonar» de phyphox emite chirridos de 5 ms que suben de 1 a 4 kHz, correlaciona la grabación con ellos y convierte en distancia el tiempo de cada eco.

Un sonar ha enviado un chirrido y ha recibido su eco, tan débil que se pierde entre el ruido. Toca el pico de la curva naranja para leer cuándo vuelve y calcula a cuántos metros está el objeto, con el sonido a 1.500 m/s. Escribe la distancia y pulsa «Comprobar».

Con el teclado: pulsa la gráfica con el tabulador y usa las flechas para moverte de pico en pico.

La forma de la plantilla importa

Un radar quiere dos cosas que se pelean. Un pulso largo lleva mucha energía, así que se detecta de más lejos, pero su correlación es un pico ancho y torpe que no separa dos objetos cercanos. Un pulso corto da un pico estrecho, pero lleva poca energía. La solución es codificar el pulso: sigue siendo largo, pero está compuesto por una ristra de elementos cortos, cada uno con su signo, y su correlación se concentra en un pico estrecho con unos lóbulos laterales pequeños a los lados. Es la compresión de pulsos, y permite tener a la vez energía y precisión.

El ejemplo clásico es el código de Barker de 13 elementos: más, más, más, más, más, menos, menos, más, más, menos, más, menos, más. Su correlación tiene un pico de 13 y unos lóbulos laterales que nunca pasan de 1, es decir, 22,3 dB por debajo del pico. No se conoce ningún código de Barker de más de 13 elementos, y hay indicios muy fuertes de que no existe. Un chirp, un pulso cuya frecuencia sube mientras dura, también se comprime así.

Los lóbulos laterales importan porque son falsos ecos: si son altos, un lóbulo del avión cercano se puede confundir con otro avión.

Dos aviones vuelan casi pegados y el radar recibe sus dos ecos con ruido. Elige el pulso con el que la curva naranja enseña dos picos separados y los lóbulos laterales no pasan del 10 % del pico. Los tres pulsos duran lo mismo y llevan la misma energía.

Compararse consigo misma: la autocorrelación

Si la plantilla es la propia señal, la correlación dice a qué distancias se parece la señal a sí misma, y se llama autocorrelación. Con el desplazamiento en cero el parecido es total, y es siempre lo máximo que se puede alcanzar. El ruido solo se parece a sí mismo sin moverse, así que su autocorrelación es un pico en cero y casi nada más. Un silbido se parece a sí mismo cada vez que completa una vuelta de la noria, y una vocal, cada vez que vibran las cuerdas vocales.

De ahí sale la nota de una voz. El primer pico alto después del cero marca lo que dura una vibración, y su inversa es la frecuencia fundamental de la lección 3. Es un método clásico, que Rabiner estudió a fondo en 1977 y que usa Praat con las mejoras de Boersma. En la práctica se resta la media, se multiplica el trozo por una ventana, se usan unos 40 ms, que dejan al menos tres periodos del tono más grave que se busca, y se dice «no hay nota» cuando ningún pico llega a una altura mínima, de 0,4 a 0,45: el ruido blanco da picos de unos 0,25.

Hay trampas. Los picos a dos y a tres vibraciones son casi tan altos como el primero, y quedarse con el más alto da una nota una octava por debajo de la real, el error de octava de la lección 20. Un pico pequeño antes del primero puede venir del primer formante de la vocal, y por eso se elige el primer pico que llega a una altura parecida a la del más alto, no el primero que pase de un umbral bajo.

La autocorrelación tiene además una relación íntima con Fourier. La transformada es una correlación con norias, un pico por cada noria que encaja, y el espectro de potencia es la transformada de Fourier de la autocorrelación. El ruido blanco tiene un espectro plano porque solo se parece a sí mismo sin desplazarlo, y de ahí parte la lección 10.

Esta es la autocorrelación de una «aaa» cantada, de 0 a 25 ms. Toca el pico que corresponde a una sola vibración de las cuerdas vocales y mira qué nota sale. Con los botones de abajo puedes oír la vocal y, después, un tono puro del pico que elijas, para comparar.

Con el teclado: pulsa la gráfica con el tabulador y usa las flechas para saltar de pico en pico.

Vuelta a la aguja: el GPS

Todos los satélites GPS emiten la señal civil en la misma frecuencia, 1.575,42 MHz, y todos a la vez. Lo que distingue a cada uno es su código, una ristra de 1.023 elementos, cada uno un uno o un menos uno, que se llaman chips y se repite cada milésima de segundo. Son códigos pseudoaleatorios: parecen azar, pero el satélite y el receptor los conocen. Se parecen tan poco entre sí que la correlación de un código con otro distinto solo toma los valores −65, −1 o 63, frente a los 1.023 del pico de un código consigo mismo.

La especificación oficial del GPS fija como mínimo para esta señal una potencia recibida de −158,5 dBW, que son −128,5 dBm. La cifra redonda de −130 dBm, que citan muchos textos, viene de especificaciones anteriores; con cualquiera de las dos, es del orden de 10⁻¹⁶ vatios. Cualquier receptor a temperatura ambiente capta además un ruido térmico de unos −174 dBm por hercio, y en los 2 MHz que ocupa la señal son unos −111 dBm. La señal llega, por tanto, entre 17,6 y 19 dB por debajo del ruido, entre 58 y 80 veces menos potente.

El receptor no ve la señal: la busca. Desliza el código de cada satélite sobre lo que recibe, y correlacionar un periodo completo da una ganancia de 10 veces el logaritmo de 1.023, unos 30 dB, con lo que la señal pasa de estar unos 19 dB por debajo del ruido a estar unos 11 por encima, en un receptor ideal. Cada vez que se dobla el tiempo durante el que se correlaciona, se ganan unos 3 dB, y hasta un bit de datos de navegación, que dura 20 ms, la ganancia llega a unos 43 dB.

Como el satélite se mueve, la frecuencia puede llegar desplazada por efecto Doppler hasta unos 5 kHz, y el receptor busca en dos direcciones: el retardo del código y la frecuencia. El retardo es lo que mide cuánto ha tardado la señal en llegar. Un chip dura unos 977,5 nanosegundos, tiempo en el que la luz recorre unos 293 metros, y la señal tarda unos 67 ms en bajar desde los 20.180 km de altura de un satélite que esté justo encima.

Hay uno de cuatro satélites en el aire, y su señal llega mucho más débil que el ruido y con un retraso que no conoces. Prueba el código de cada satélite con distintos tiempos de integración hasta que salga un pico claro, y descubre cuál es y con cuántos chips de retraso llega. Es un modelo sin efecto Doppler.

En tu voz

Qué grabar. Una «aaa» sostenida durante unos tres segundos, sin cambiar de nota, que es el tramo 3 de la grabación de referencia de la serie. También sirven una «iii» o un silbido, el tramo 2. Graba con el micrófono si tu navegador lo deja; si no, sube un audio grabado con el móvil, o prueba con los ejemplos sintéticos.

Qué mirar. El laboratorio busca la nota de tu voz con la autocorrelación de un trozo de 40 ms, que puedes mover tocando la grabación de arriba. Verás los picos regulares, el primero marcado como tu periodo, su frecuencia y la nota más cercana, y también los picos de dos y de tres periodos, que dan la misma nota una y dos octavas más grave. Con el botón puedes oír tu grabación y, después, un tono puro de la frecuencia que ha encontrado: si es la misma nota, se oye. Con un silbido, el laboratorio cambia solo de rango de búsqueda, porque si no encontraría una frecuencia cuatro veces más grave.

Lo que tienes que recordar

  1. La correlación desliza una plantilla por la señal y mide el parecido en cada posición: se multiplica punto a punto y se suma. Donde la plantilla encaja, la curva tiene un pico, y el retardo del pico dice dónde está lo que buscas, o a qué distancia, si es un eco.
  2. Gana al ruido porque los puntos de la señal suman a favor y los del ruido se anulan a medias: la ventaja crece con la longitud de la plantilla y se mide en decibelios, diez veces el logaritmo del número de puntos. Con ruido blanco, la mejor plantilla es la propia forma que buscas, y la forma decide lo estrecho que sale el pico y lo altos que son los lóbulos laterales.
  3. La autocorrelación compara la señal consigo misma: un ruido solo se parece a sí mismo sin moverse y una nota, cada periodo. El primer pico alto marca el periodo, y quedarse con otro pico da una nota una octava más grave.

Errores típicos

Abrir

Rincón matemático

Las fórmulas, para quien las quiera. Cada una va después de su lectura en palabras.

Correlación cruzada

La plantilla y se desliza \ell muestras sobre la señal x; en cada desplazamiento se multiplica punto a punto y se suma:

r_{xy}[\ell] = \sum_{n} x[n+\ell]\; y[n]

Parecido normalizado

Para comparar entre posiciones y señales, se divide por la energía de la plantilla y por la del trozo de señal que cubre, y el resultado queda entre −1 y 1:

\rho[\ell] = \frac{\sum_n x[n+\ell]\, y[n]}{\sqrt{\sum_n y[n]^2 \;\sum_n x[n+\ell]^2}}

Correlación y convolución

Correlacionar con una plantilla es convolucionar con la plantilla puesta del revés:

r_{xy}[\ell] = (x * \tilde{y})[\ell], \qquad \tilde{y}[n] = y[-n]

Por qué gana al ruido

Si la señal aporta A en cada uno de los N puntos y el ruido tiene desviación \sigma por punto, la señal suma NA y el ruido, \sigma\sqrt{N}, de modo que la relación en potencia mejora N veces:

\frac{(N A)^2}{N \sigma^2} = N\,\frac{A^2}{\sigma^2} \quad\Longrightarrow\quad G = 10\log_{10} N \ \text{dB}

Para el GPS, con 1.023 chips en un milisegundo y con 20 ms, que son 1,023 millones de chips por segundo partidos entre los 50 bits por segundo de los datos:

10\log_{10} 1023 \approx 30{,}1 \ \text{dB}, \qquad 10\log_{10}\frac{1{,}023\cdot 10^{6}}{50} \approx 43{,}1 \ \text{dB}

El filtro adaptado

Con ruido blanco de varianza \sigma^2 por muestra, la plantilla que da la mayor relación señal-ruido en el pico es la propia forma s, escrita como convolución, al revés. Esa relación máxima es la energía de la forma partida por la varianza del ruido:

h[n] = s[N-1-n], \qquad \mathrm{SNR}_{\max} = \frac{\sum_n s[n]^2}{\sigma^2}

Eco y distancia

La onda va y vuelve, así que la distancia es la velocidad por el tiempo del eco, dividido entre dos:

d = \frac{v\, t}{2}

Autocorrelación

La señal comparada consigo misma. En cero vale su energía y nunca se supera, y si la señal se repite cada P muestras, los picos vuelven cada P, y de ahí sale la frecuencia fundamental:

r_{xx}[\ell] = \sum_n x[n]\, x[n+\ell], \qquad |r_{xx}[\ell]| \le r_{xx}[0], \qquad f_0 = \frac{f_s}{P}

La corrección de la ventana

Al multiplicar por una ventana, la autocorrelación cae con el desplazamiento. Dividirla por la autocorrelación de la propia ventana deshace esa caída, como propone Boersma:

r_x(\tau) \approx \frac{r_a(\tau)}{r_w(\tau)}

Fourier es una correlación con norias

Cada valor del espectro es la correlación de la señal con una noria de frecuencia f:

X(f) = \sum_n x[n]\, e^{-i 2\pi f n / f_s}

El puente con el ruido

El espectro de potencia es la transformada de Fourier de la autocorrelación, y por eso el ruido blanco, con su autocorrelación en un pico en cero, tiene un espectro plano:

S_{xx}(f) = \sum_{\ell} r_{xx}[\ell]\; e^{-i 2\pi f \ell / f_s}

El presupuesto del GPS

El ruido térmico a 290 K son unos −174 dBm por hercio. La relación de la señal con el ruido de la banda que ocupa, de ancho B, es la potencia recibida C menos ese ruido, y la correlación suma después su ganancia de procesado:

\frac{C}{N}\Big|_{B} = C_{\text{dBm}} - (-174) - 10\log_{10} B, \qquad \mathrm{SNR}_{\text{tras correlar}} = \frac{C}{N}\Big|_{B} + G

Con C = -130 dBm y B = 2{,}046 MHz, la señal está unos 19 dB por debajo del ruido, y con la ganancia de 30 dB de un milisegundo de código queda unos 11 dB por encima, en un receptor ideal.

Para saber más

Términos nuevos

Examen