Multi-input Multi-output Orthogonal Frequency Division Multiplexing (MIMO OFDM) is widely used in wireless communication systems. In Ultra Wideband (UWB) mainly applied in the Wireless Personal Area Network (WPAN) 802.15 3c standard, MIMO OFDM is an important way in modulation. And in MIMO OFDM, Fast Fourier Transform (FFT) is a key element, since the computational complexity of FFT processor is very high in the whole system. In this thesis, the three integer multiplication based complex constant multiplier is applied in the four path pipelined 128 point FFT to reduce the computational complexity and the area, an important Intellectual Property (IP) in VLSI design. Since the number of the multipliers decreased from 4 to 3 in a complex multiplication, the computation is compensated by the increase of adders from two to three and extra multiplexers. Though the result is not as much as 25% as expected, the area reduced by 19% and 8% respectively in 4-path pipelined 128 point FFT compared to two previous architectures, the pool-based and the path-based architectures, with Multiple Radix Multipath Delay Feedback (MRMDF).
본 석사학위논문에서는 다중경로 128 포인트 FFT를 위한 3개의 정수 곱셈 기반 복소수 상수 곱셈기를 구현하였다. 광대역 무선통신에서 가장 중요한 역할을 하는 FFT/IFFT는 계산이 복잡하고 구현하기 어려우며 포인트 수가 커질수록 복잡도가 더 높아진다. FFT/IFFT 구현 중에서 제일 중요한 부분은 복소수 곱셈이다. DFT의 O(N^2)의 곱셈 계산을 줄이기 위해 응용되는 FFT는 곱셈 계산을 줄여 계산의 복잡도를 줄인다.
UWB는 높은 전송속도를 요구로 한다. 128 포인트 FFT를 사용할 때 최저 528Msamples/s의 ADC 샘플링 속도를 요구한다. 다중경로가 아닌 SISO (Single Input and Single Output)이라면 clock의 주파수가 528MHz보다 높아야 한다. 이는 CMOS 구현에서 실현하기 어렵다. 하지만 MIMO (Multiple Input and Multiple Output)를 사용한다면 경로의 개수만큼 요구하는 clock의 주파수를 줄일 수 있기 때문에 구현하기 쉽다. 따라서 본 연구에서는 132MHz 이상의 주파수를 요구하는 네 개의 다중경로의 128 포인트 FFT를 구현하였다.
본 논문에서는 Radix-2/Radix-2^3/ Radix-2^3 MRMDF 128-point FFT)의 두 번째 stage의 세 번째 단계의 twiddle factor인 W_64^p에 의한 복소수 곱셈기를 기존의 방법보다 개선된 3개의 정수 곱셈기 기반 복소수 상수 곱셈기로 구현하였다. 3개의 정수 곱셈 기반 복소수 상수 곱셈기는 기존의 네 개의 곱셈기와 두 개의 덧셈기를 사용하는 상수 곱셈기와 달리 아래와 같이 세 개의 곱셈기와 세 개의 덧셈기를 사용한다.
$X=\(x_r+jx_i\)\times\(cos\theta-jsin\theta\)=\(x_rcos\theta+x_isin\theta)+j(x_icos\theta-x_rsin\theta)$
$X_r=x_rcos\theta+x_isin\theta=\(x_r+x_i\)cos\theta-x_i\(cos\theta-sin\theta\)$
$X_i=x_icos\theta-x_rsin\theta=\(x_r+x_i\)cos\theta-x_r\(cos\theta+sin\theta\)$
$Comm =\begin{cases}\(x_r+x_i\)cos\theta, & if Region\in\{A,C,E,F\}\\\(x_r+x_i\)sin\theta, & if Region\in\{B,D,F,H\}\end{cases}$
$Diff=x_i\(cos\theta-sin\theta\)$
$Sum=x_r\(cos\theta+sin\theta\)$
각각의 곱셈기는 twiddle factor인 삼각함수의 값으로부터 계산된 10-bit의 상수값을 미리 ROM에 저장하였다가 multiplex를 통하여 읽어서 데이터를 shifter로 right-shift시키고 그 결과를 덧셈기로 더해 최종 정수 곱셈 값을 구한다. 최종 복소수 곱셈은 실수부 및 허수수의 덧셈(또는 뺄셈) 연산을 통하여 구한다. 구현상의 추가적인 면적감소를 위하여 shifter의 개수를 최소화하여 상대적으로 큰 면적을 차지하는 덧셈기의 개수의 감소를 추구하였다. 구체적으로 상기 Diff 파트와 Comm 파트는 네 개의 경로에서 각각 4개의 shifter와 3개의 덧셈 연산을 하되 하나의 ‘joker’ shifter를 추가적으로 두어 각 timeslot에서 추가적인 shifter가 필요한 경로에 동적으로 할당함으로써 전체 shifter와 덧셈기의 개수를 감소하였다. Sum 파트에서는 네 개의 경로에서 각각 4개의 shifter와 3개의 덧셈 연산을 한다.
본 논문에서는 복소수 상수 곱셈기의 네 개의 정수곱셈을 식변형을 통하여 세 개의 정소곱셈연산으로 줄여서 곱셈기 감소효과만 감안한 목표인25%의 복잡도 감소를 추구하였다. 0.13μm TSMC를 통하여 구현한 결과 UWB의 요구를 상회하는 572Msamples/s의 데이터 전송속도를 얻었으며 면적은 기존의 pool-based 및 path-based 복소수 상수 곱셈 방법에 비하여 각각 19%와 8%를 감소되는 결과를 얻었다. 면적감소 추구 목표와의 차이는 데이터 실수 및 허수의 사전 덧셈에 의한 복잡도 증가와 정수곱셈에 필요한 상수 ROM저장을 위해 필요한twiddle factor의 실수 및 허수의 덧셈 또는 뺄셈의 정밀도 및 범위 증가에 의한 복잡도 증가에 의한 오버헤드 회로 증가에 기인된다.
