적응적 시간 분할 양자화

Nathan O. Davis는 통합 시스템학과에 재학 중인 학생이다. 오늘 그는 수업에서 디지털 양자화를 배웠다. 양자화란 아날로그 데이터(예: 전압)를 유한한 개수의 이산값 또는 정수로 근사하는 과정이다.

그는 전압계로 각 시간 단계마다 측정한 전압을 나타내는 실수 수열을 양자화하는 프로그램을 작성하는 과제를 받았다. 평범한 양자화기를 구현하는 것은 재미없었기 때문에, 그는 적응적 시간 분할 양자화(Adaptive Time Slicing Quantization)라는 새로운 양자화 방법을 고안했다. 이 양자화는 다음 단계로 이루어진다.

1. 주어진 실수 수열을 임의의 M개의 연속한 부분 수열로 나눈다. 이 부분 수열을 프레임이라고 부른다. 프레임의 크기는 모두 같을 필요는 없지만, 각 프레임은 적어도 두 개의 원소를 포함해야 한다. 이후 단계는 각 프레임에 대해 독립적으로 수행된다.

2. 프레임의 최댓값 Vmax와 최솟값 Vmin을 찾는다.

3. 양자화 값의 집합을 정의한다. 이 집합은 구간 [Vmin, Vmax]를 양 끝점을 포함하여 균등하게 나눈 2L개의 값을 포함한다. 여기서 L은 양자화 레벨이라고 불리는 주어진 매개변수이다. 즉, i번째 양자화 값 qi (1 ≤ i ≤ 2L)는 다음과 같다.

   qi = Vmin + (i - 1){(Vmax - Vmin)/(2L - 1)}.

4. 프레임의 각 원소 값을 가장 가까운 양자화 값으로 반올림한다.

이 방법의 핵심은 1단계에서 더 적절한 프레임 집합을 선택할수록 더 좋은 결과를 얻을 수 있다는 것이다. 양자화의 품질은 수열의 모든 원소에 대한 양자화 오차의 제곱합으로 측정하며, 작을수록 좋다. 각 원소의 양자화 오차는 원래 값과 양자화된 값의 절댓값 차이이다.

안타깝게도 Nathan은 프로그램을 작성하기 전에 심한 감기에 걸려 아직도 침대에 누워 있다. 그래서 그는 당신의 도움이 필요하다. 대신 당신이 적응적 시간 분할 양자화를 구현해야 한다. 프로그램에서 양자화는 최상의 품질로, 즉 양자화 오차의 제곱합이 최소가 되도록 수행되어야 한다.

입력은 여러 데이터셋으로 이루어진다. 각 데이터셋은 두 줄로 구성된다. 첫째 줄에는 수열의 원소 수 N (2 ≤ N ≤ 256), 프레임의 수 M (1 ≤ M ≤ N/2), 양자화 레벨 L (1 ≤ L ≤ 8)을 나타내는 세 정수가 주어진다. 둘째 줄에는 [0, 1] 범위의 실수 N개가 주어진다. 입력은 N = M = L = 0인 데이터셋으로 끝나며, 이 데이터셋은 처리하지 않는다.

각 데이터셋마다 양자화 오차의 제곱합의 최솟값을 한 줄에 출력한다. 절대 오차가 10-6 이하이면 정답으로 인정된다.