응용: 이진 코드와 정합 필터

레이다는 두 반사파의 도착 시각 차이가 수신기 출력의 펄스 폭보다 작으면 피크가 겹쳐 서로 다른 거리의 표적을 구별하기 어렵다. 코드를 싣지 않은 펄스는 송신 폭을 줄이면 출력도 좁아지지만, 짧은 펄스에는 에너지를 많이 싣기 어렵다. 긴 펄스를 폭 $T_c$인 작은 조각으로 나누어 조각마다 $+1$이나 $-1$을 곱해 보내고, 수신기에서 그 코드에 맞춘 필터를 지나게 하면 출력이 칩 하나 폭 정도의 날카로운 피크로 모인다. 이 필터의 출력이 컨볼루션이고, 피크 옆에 남는 작은 값의 크기는 어떤 코드를 골랐는지에 달려 있다.

코드를 실은 파형과 정합 필터

코드 $c[0],c[1],\dots,c[N-1]$의 각 값은 $+1$ 또는 $-1$이다. 2장의 GPS 신호처럼 한 자리를 칩(chip)이라 부르고, 칩 하나를 폭 $T_c$인 사각 펄스 $p(t)$로 보낸다.

수신기는 $x(t)$를 시간축에서 뒤집은 것을 임펄스 응답으로 쓴다. 이 필터를 정합 필터(matched filter)라고 한다.

실수 파형 $x$의 에너지(제곱의 적분)를 $E_x=\int_{-\infty}^{\infty}x^2(\tau)\,d\tau$라고 하자. 같은 에너지 $\int h^2(\tau)\,d\tau=E_x$를 갖는 필터끼리 비교해 보자. 두 함수 곱의 적분은 두 에너지 곱의 제곱근을 넘지 못하므로(코시–슈바르츠 부등식) $|y(t)|=\bigl|\int x(\tau)h(t-\tau)\,d\tau\bigr|\le\sqrt{E_x\int h^2(\tau)\,d\tau}=E_x$이다. $h(t)=x(-t)$이면 $h(-\tau)=x(\tau)$라서 $y(0)=\int x^2(\tau)\,d\tau=E_x$로 이 상한에 닿는다. 그래서 시간축을 뒤집은 파형을 쓴다. 적분은 모두 전체 시간에 걸친다.

출력은 컨볼루션이다. $h(t-\tau)=x(-(t-\tau))$이고 이것은 $x(\tau-t)$와 같으므로, $h$를 한 번 더 뒤집어 옮긴 것은 $x$를 $t$만큼 옮긴 것과 같다.

마지막 적분은 $x$에 $t$만큼 옮긴 자기 자신을 곱해 적분한 값이고, 이것을 $x$의 자기상관(autocorrelation)이라고 한다. 정합 필터의 출력은 입력 파형의 자기상관이다.

칩이 사각 펄스이므로 계산은 칩 시각에서 간단해진다. $t=kT_c$이면 옮긴 칩이 원래 칩과 정확히 겹쳐, 겹친 칩마다 $c[n]c[n+k]\cdot T_c$가 더해진다.

합은 $c[n]$과 $c[n+k]$가 모두 있는 $n$에 대해서만 한다. $c[n]c[n+k]$는 두 칩의 부호가 같으면 $+1$, 다르면 $-1$이므로 $r[k]$는 (같은 칩 수) − (다른 칩 수)이다. $k=0$에서는 모든 칩이 자기 자신과 겹쳐 가장 큰 값 $y(0)=NT_c$가 나온다. 이것이 피크(peak)이다. 칩 시각 사이에서 $y(t)$는 이웃한 두 칩 시각의 값을 직선으로 잇는다(문제 2). 폭 $T_c$인 사각 펄스끼리의 상호상관이 $t=0$을 가운데로 밑변이 $2T_c$인 삼각형이기 때문이다. '컨볼루션 적분 읽기'의 두 사각 펄스의 컨볼루션도 같은 모양의 삼각형이다. 다만 컨볼루션이라 가운데가 $t=0$이 아니라 펄스 폭만큼 옮겨진 자리에 있다.

$k\ne0$의 $r[k]$는 피크 옆에 남는 값이고 사이드로브라고 부른다. 레이다에서는 큰 표적의 사이드로브가 가까운 거리의 작은 표적을 가리고, 통신에서는 수신기가 피크가 아닌 곳에서 동기를 잘못 잡을 수 있다. 코드의 좋고 나쁨은 가장 큰 사이드로브와 피크의 비로 잰다. 이 비를 dB로 나타낸 것이 PSL(peak sidelobe level)이다.

$h(t-\tau)$가 $x(\tau)$ 위를 지나가는 동안 곱의 면적을 이으면 출력 곡선 $y(t)$가 된다. 이 곡선의 피크 높이와 가장 큰 사이드로브(점선)의 높이를 비교한 것이 PSL이다.

바커 13 코드를 한 번 보낸 상태이고, 위의 줄은 $x(\tau)$, 옮긴 정합 필터 $h(t-\tau)=x(\tau-t)$, 둘의 곱이다. 곱의 면적이 아래 출력 $y(t)$의 현재 점이 되고, 칩 시각에서는 겹친 칩 가운데 부호가 같은 것과 다른 것의 수가 함께 나오며, '무작위 13칩'은 아래 표의 무작위 코드이다.

한 번 보낼 때와 되풀이해 보낼 때

코드를 한 번만 보내는 펄스 레이다에서는 옮긴 복사본이 원래 코드에서 벗어난 부분은 0과 겹친다. 그래서 $|k|$가 커질수록 겹치는 칩이 줄어든다. 위의 $r[k]$가 이 경우이고, 비주기 상관(aperiodic correlation)이라고 한다.

GPS C/A 코드(1023칩, 1.023 Mchip/s이므로 1 ms마다 되풀이)나 쉬지 않고 신호를 보내는 코드 분할 다중 접속(code division multiple access, CDMA)처럼 같은 코드를 끊지 않고 되풀이해 보내면, 한 주기의 정합 필터는 언제나 $N$개의 칩과 겹친다. 원래 코드에서 벗어난 부분에는 다음 주기의 앞부분이 들어온다. 이때의 출력은 주기 상관(periodic correlation)이다.

두 상관은 같은 코드에서도 다르다. 어떤 코드가 좋은지는 코드를 보내는 방식에 따라 달라진다.

• 바커 코드(Barker code)는 비주기 사이드로브가 모두 $|r[k]|\le1$인 코드이다. 길이 34까지 모든 코드를 컴퓨터로 확인하면 길이 2, 3, 4, 5, 7, 11, 13에만 있고, 바커 13의 PSL은 $20\log_{10}(1/13)=-22.3$ dB이다.
• m-시퀀스(maximal-length sequence)는 $m$단 선형 귀환 시프트 레지스터(linear feedback shift register, LFSR)로 만드는 수열이다. 귀환 다항식이 원시 다항식(primitive polynomial)이면 주기가 가장 긴 $N=2^m-1$이 된다. 레지스터의 상태는 $2^m$가지인데 모두 0인 상태에서는 계속 0만 나오므로, 나머지 상태를 한 번씩 지나는 $2^m-1$이 최장 주기이다. 여기서 $x^3+x+1$은 귀환 $a[n+3]=a[n+1]\oplus a[n]$($\oplus$는 XOR)을 뜻한다. $0,0,1$에서 시작하면 $0010111$을 되풀이한다. 그림의 15, 31은 같은 방법으로 $x^4+x+1$, $x^5+x^2+1$에서 만들었다. m-시퀀스의 주기 상관은 피크 밖에서 모두 $-1$이다. m-시퀀스와 그것을 0이 아닌 칩 수만큼 돌린 수열을 XOR하면 다시 같은 m-시퀀스를 돌린 것이 되고, 한 주기에는 1이 0보다 하나 많다. 그래서 두 수열의 칩은 다른 곳이 같은 곳보다 하나 많다(이동·XOR 성질과 0·1 개수 성질의 증명은 생략한다; Goldsmith, Wireless Communications, 13장). 따라서 되풀이해 보내면 PSL이 $20\log_{10}(1/N)$으로, 31칩에서 −29.8 dB, 1023칩이면 −60.2 dB이다. 한 번만 보내면 사이드로브가 모두 $-1$이 되지는 않는다. 그림의 31칩에서는 가장 큰 사이드로브의 크기가 5($r[14]=-5$, −15.8 dB)이고, 한 주기를 어디서 끊느냐(31가지)에 따라 4에서 6 사이로 달라진다. 바커 7도 m-시퀀스 7을 돌려 부호를 바꾼 것 가운데 하나이다. 같은 수열이라도 끊는 곳을 잘 고르면 비주기 사이드로브가 작아진다.
• GPS C/A 코드는 위성마다 다르고, 길이 1023인 m-시퀀스 두 개를 칩마다 XOR해 만든 골드 코드(Gold code)이다. 위성의 코드는 의사 잡음(pseudorandom noise, PRN) 번호로 구분한다. PRN 1 코드를 만들어 계산해 보면 주기 상관이 피크 1023 밖에서 −65, −1, 63 세 값만 갖는다.

아래 표는 그림의 코드들을 두 방식으로 보냈을 때 가장 큰 사이드로브의 크기 $|r|$와 PSL이다.

perfect sequence와 almost perfect sequence

주기 상관의 사이드로브가 모두 0인 수열을 perfect sequence라고 한다. $[+1,+1,+1,-1]$은 $r_{\mathrm p}[1]=r_{\mathrm p}[2]=r_{\mathrm p}[3]=0$이다. 이 수열은 길이 4의 바커 코드이기도 하다.

이진 수열의 주기 상관은 0이 되기 어렵다. $N$개의 곱 $c[n]c[(n+k)\bmod N]$을 모두 곱하면 각 $c[n]$이 두 번씩 들어가 1이 된다. 따라서 $-1$인 곱의 개수 $d$는 짝수이다. 나머지 $N-d$개의 곱은 $+1$이므로 $r_{\mathrm p}[k]=(N-d)-d=N-2d$이고, 이를 4로 나눈 나머지는 $N$을 4로 나눈 나머지와 같다. $r_{\mathrm p}[k]=0$이려면 $N$이 4의 배수여야 한다. 길이 20까지 모든 수열을 확인하면 perfect sequence는 길이 4에만 있다.

그래서 하나를 양보한 수열을 쓴다. 주기 상관이 $k=0$ 말고 한 곳에서만 0이 아닌 수열을 almost perfect sequence(almost perfect autocorrelation sequence)라고 한다. 실수 수열은 $r_{\mathrm p}[k]=r_{\mathrm p}[N-k]$이므로 0이 아닌 한 곳은 반 주기 $k=N/2$일 수밖에 없다. 길이 3에서 20까지 모두 찾아보면 almost perfect sequence는 4, 8, 12, 16, 20에서 나온다. 길이 24, 28, 32도 모두 찾아보면 24와 28에는 있고 32에는 없다. 길이가 4의 배수여야 한다는 것은 앞의 논증에서 나오지만, 4의 배수라고 늘 있는 것은 아니다. 그림의 예는 길이 12인 $[+,+,+,+,+,-,+,-,+,+,-,-]$로, 주기 상관이 $k=6$에서 4이고 나머지 이동에서 모두 0이다. 반 주기에 남은 사이드로브 4 때문에 PSL은 −9.5 dB이지만, 피크와 반 주기 사이는 모두 0이다.

almost perfect sequence는 J. Wolfmann이 이진 수열에 대해 다룬 개념이다("Almost perfect autocorrelation sequences," IEEE Trans. Inf. Theory 38(4), 1412–1418, 1992). 이 절의 길이와 예는 모든 수열을 계산해 찾은 것이다.

문제 1: 길이 7 m-시퀀스의 상관

$x^3+x+1$로 만든 m-시퀀스 $0010111$을 $0\to+1$, $1\to-1$로 바꾼 코드 $c=[+1,+1,-1,+1,-1,-1,-1]$을 쓴다.

직접 유도해 보기. 비주기 상관 $r[k]$($k=0,\dots,6$)와 PSL을 구하라. 같은 코드를 되풀이해 보낼 때의 $r_{\mathrm p}[k]$도 구하라.

문제 2: 칩 시각 사이의 출력

직접 유도해 보기. 칩이 폭 $T_c$인 사각 펄스일 때 $y(kT_c)=T_c\,r[k]$임을 보여라. 또 $kT_c<t<(k+1)T_c$에서 $y(t)$가 $T_c\,r[k]$와 $T_c\,r[k+1]$을 잇는 직선임을 보여라.

문제 3: 되풀이해 보내는 코드를 주기 상관으로 보는 이유

직접 유도해 보기. 코드를 끊지 않고 되풀이해 보낼 때, 한 주기의 정합 필터 출력이 칩 시각 $kT_c$($0<k<N$)에서 $T_c\,r_{\mathrm p}[k]$임을 보여라. 이 경우 비주기 사이드로브가 작은 코드보다 주기 사이드로브가 작은 코드가 나은 이유를 설명하라.