시그마와 인덱스

핵심 질문

긴 배열의 값을 더할 때 왜 $\sum$ 기호와 번호가 필요할까?

교과서 설명

배열은 여러 값을 순서대로 적어 둔 목록이다. 컴퓨터 수학에서는 보통 첫 번째 칸을 $0$번이라고 부른다.

여기서 $N$은 배열에 들어 있는 값의 개수다. 번호 $n$은 지금 보고 있는 칸의 위치를 뜻한다.

값을 모두 더해야 할 때 매번 길게 쓰면 불편하다.

그래서 같은 뜻을 더 짧게 다음처럼 쓴다.

이 표기는 “$n=0$부터 시작해서 $N-1$까지 차례대로 넣고 모두 더하라”는 뜻이다.

시그마가 두 번 나오면 바깥 번호를 하나 고정하고, 안쪽 번호를 전부 돌며 더한 뒤, 그 일을 바깥 번호마다 반복한다.

이 식은 표의 모든 칸을 더하는 것처럼 볼 수 있다. 먼저 $i=0$번째 줄에서 모든 $j$를 더하고, 다음 줄로 넘어가는 식이다.

예를 들어 표가

라면 $\sum_i\sum_j m[i,j]$는 $2+3+5+7$을 뜻한다. 바깥 번호 $i$는 줄을 고르고, 안쪽 번호 $j$는 그 줄 안의 칸을 차례로 고른다.

합성곱에서는 두 번호 $i,j$가 함께 움직인다. $t=i+j$라고 두면, 같은 $t$를 만드는 모든 쌍을 한 칸에 모은다.

그래서 나중에 $\sum_t$가 $\sum_i\sum_j$로 바뀌어도, 뜻은 “모든 가능한 두 칸의 조합을 한 번씩 본다”는 것이다.

DFT의 식도 결국 같은 모양이다. $k$를 하나 고정해 놓고, 모든 샘플 번호 $n$에 대해 계산한 값을 더한다.

인덱스 조작과 합의 범위

시그마에서 사용하는 글자 이름은 본질이 아니다. 아래 두 식은 같은 뜻이다.

이런 글자를 더미 인덱스라고 부른다. 중요한 것은 인덱스가 도는 범위와, 그 인덱스를 식 안에서 어떻게 쓰는가다.

시그마는 덧셈이므로 분배법칙도 그대로 따른다. 같은 범위에서 더한다면

이고, 상수 $c$는 합 밖으로 뺄 수 있다.

이 성질은 뒤에서 DFT의 선형성을 증명할 때 그대로 사용된다.

합성곱처럼 $c[k]=\sum_i a[i]b[k-i]$라고 쓸 때는 숨어 있는 조건이 있다. 배열 밖의 값은 $0$으로 보겠다고 약속하면 모든 정수 $i$에 대해 쓸 수 있지만, 실제로 더해지는 항은 다음 조건을 만족하는 것뿐이다.

따라서 실제 범위는 다음처럼 정리할 수 있다.

처음에는 복잡해 보이지만, 의미는 단순하다. $a$에서 하나, $b$에서 하나를 골랐을 때 두 번호의 합이 $k$가 되는 조합만 더한다는 뜻이다. FFT 합성곱의 증명에서는 이런 인덱스 정리가 $\sum_t$를 $\sum_i\sum_j$로 바꾸는 핵심 역할을 한다.

직관 비유

반 학생들의 키를 모두 더한다고 생각하자. “1번 학생 키 + 2번 학생 키 + ...”라고 길게 말하는 대신, “모든 학생 번호를 돌며 키를 더한다”고 말할 수 있다. $\sum$은 이 반복 덧셈을 짧게 적는 약속이다.

예제

배열이 다음과 같다고 하자.

그러면 $N=4$이고, 번호는 $0,1,2,3$이다.

값을 넣으면

조금 더 복잡하게, 번호와 값을 곱해서 더할 수도 있다.

시그마는 새로운 계산법이 아니라, 반복되는 덧셈을 정리해서 쓰는 표기법이다.

손풀이 체크

1. $x=[2,5,1]$이면 $N$은?

   답 보기

   $3$

2. $\sum_{n=0}^{2}x[n]$은 어떤 덧셈을 뜻할까?

   답 보기

   $x[0]+x[1]+x[2]$

3. $x=[2,5,1]$일 때 $\sum_{n=0}^{2}x[n]$은?

   답 보기

   $2+5+1=8$

다음으로 이어지는 생각

여러 숫자를 번호로 관리하고 더할 수 있으면, 두 배열이 얼마나 같은 방향인지 재는 내적도 자연스럽게 이해할 수 있다.