cho.sh

필터링

시간 제한1초메모리 제한128 MB

문제

디지털 신호 처리(DSP)는 음악에서 흔히 들리는 "에코"나, 일부 가수의 목소리에 걸리는 특유의 변조 같은 효과를 만들어 낸다. 이런 효과는 유한 임펄스 응답(FIR, Finite Impulse Response) 필터로 구현한다.

샘플들의 입력 스트림을 생각하자. 이는 각각 0 이상 255 이하(8비트 샘플의 범위)인 정수들의 수열이며, 하나의 파형을 디지털로 표현한 것으로서 샘플이 차례대로 들어온다. FIR 믹서는 여러 스트림을 하나로 합치고, FIR 에코 필터는 하나의 입력에서 하나의 출력을 만드는 식이다.

FIR 필터는 한쪽에 입력 신호, 다른 한쪽에 출력을 두는 방정식으로 나타낸다. 예를 들어

Y = X[0] + X[-5]

는 (포스트-)에코 필터다. 즉 $Y$의 $i$번째 샘플은 같은 위치의 $X$ 값에, 다섯 샘플 앞의 $X$ 값을 더한 것이다. 일반적으로 출력 위치 $i$를 계산할 때 쓰는 참조 $X[k]$는 $X[i + k]$를 읽는다. 만약 $i + k$가 유효 범위 $0 \dots S-1$을 벗어나면 그 값은 0으로 본다.

모든 FIR 방정식은 다음 BNF(배커스-나우르 형식) 문법을 따른다.

EQUATION ::= STREAM __ "=" __ EXPR
STREAM   ::= A나 X처럼, 샘플 스트림을 나타내는 하나의 대문자
EXPR     ::= VALUE | SAMPLE | EXPR __ OPER __ EXPR | "(" __ EXPR __ ")"
VALUE    ::= 0.25, 5, -1.5 같은 부동소수점 수
SAMPLE   ::= STREAM "[" OFFSET "]"
OFFSET   ::= 0, 1, -5 처럼 스트림 안에서의 샘플 오프셋을 나타내는 정수, -100 이상 100 이하
OPER     ::= "*" | "+" | "-"

연산자는 일반적인 우선순위를 따른다(괄호가 가장 먼저, 다음이 곱셈, 그다음이 덧셈과 뺄셈, 그 외에는 왼쪽에서 오른쪽으로). 필터의 모든 계산이 끝난 뒤에야 결과를 가장 가까운 정수로 내림(버림)하고, 그다음 $0 \dots 255$ 범위로 자른다. 이렇게 잘라 낸 8비트 값이 그 필터의 출력 샘플이 된다. __ 기호는 하나 이상의 공백을 뜻하며, 공백은 문법에서 명시적으로 허용한 위치에만 올 수 있다.

예를 들어 간단한 저역 통과(low-pass) 필터는 다음과 같이 쓸 수 있다.

Z = 0.5 * Y[0] + 0.25 * Y[-1] + 0.25 * Y[1]

$Z$의 각 출력은 대응하는 $Y$ 값과 그 이웃 값들로 정해진다. 간단한 믹서는 다음처럼 쓸 수 있다.

D = C[0] + B[0]

물론 이런 필터는 값이 넘쳐 클리핑이 일어날 수 있다.

더 복잡한 효과를 위해 여러 필터를 이어 붙인다. 이때 모든 스트림은 입력 스트림(예: 원본 오디오)이거나, 하나의 FIR 필터의 출력이다. 한 스트림이 둘 이상의 필터에서 입력으로 쓰일 수도 있으며, 이렇게 필터 네트워크가 만들어진다.

FIR 필터 정의들과 초기 입력이 주어질 때, 모든 필터의 출력을 구하라. 어떤 FIR 필터도 연산자를 10개 넘게, 괄호 쌍을 10개 넘게, 또는 문자를 80자 넘게 쓰지 않는다. 각 데이터 세트에는 입력 스트림이 적어도 하나, 필터가 적어도 하나 있으며, 필터가 참조하는 모든 스트림은 같은 데이터 세트 안에 정의되어 있다. 한 데이터 세트의 모든 스트림은 샘플 개수가 같고, 네트워크에는 피드백 루프가 없다. 즉 어떤 필터도 직접적으로든 간접적으로든 자기 자신의 출력에 의존하지 않는다.

(피드백 루프도 피트 타운젠드가 쓰면 꽤 멋지게 들리긴 하지만 말이다.)

입력

첫 줄에는 데이터 세트의 개수를 나타내는 정수 $D$ ($1 \le D \le 100$)가 주어진다. 각 데이터 세트는 다음으로 이루어진다.

  • 데이터 세트에 있는 스트림의 개수를 나타내는 정수 $N$ ($2 \le N \le 26$)이 한 줄에 주어진다.
  • 모든 스트림의 샘플 개수를 나타내는 정수 $S$ ($1 \le S \le 100$)가 한 줄에 주어진다.
  • 이어서 각 스트림을 나타내는 $N$개의 줄이 온다. 한 데이터 세트 안에서 스트림 이름은 서로 다르다. 각 줄은 다음 중 하나다.
    • 입력 스트림: STREAM % sam1 sam2 sam3 … samS 형태다. 여기서 STREAM은 하나의 대문자이고, sam1 … samS는 그 샘플들이다. 샘플들과 % 기호는 공백으로 구분된다.
    • FIR 필터: 위에서 설명한 STREAM = EXPR 형태다.

출력

각 데이터 세트마다 먼저 헤더 줄 DATA SET #k를 출력한다. 여기서 $k$는 첫 번째 데이터 세트면 1, 두 번째면 2, … 이다. 그다음 그 데이터 세트에 있는 모든 FIR 필터에 대해 스트림 이름의 알파벳 순서로, 각 필터의 출력 스트림을 STREAM % sam1 sam2 sam3 … samS 형태로 한 줄씩 출력한다. 입력 스트림은 출력하지 않는다.