[VLSI설계및실험] (11주차) 16pt Fast Fourier Transform Architecture

본 게시글은 KUEE 정보공개 프로젝트에 포함된 글입니다.
https://blog.youhogeon.com/65

본 자료의 저작권은 모두 저에게 있으며
학업에 참고 자료로만 사용하시길 바랍니다.
부득이하게 인용해야 하는 경우 반드시 출처(KUEE 정보공개 프로젝트)와 링크를 남겨주시길 바랍니다.

11.pdf

0.83MB

src.zip

0.04MB

 

VLSI 설계 및 실험보고서 LAB 11 # 16pt Fast Fourier Transform Architecture 1. 개요 여덟 개의 입력에 대해 이산 푸리에 변환(Discrete Fourier Transform)은 아래와 같은 수식으로 나타낼 수 있다. 그러나 위의 수식을 회로로 구현하기 위해서는 64개의 multiplier와 56개의 adder가 필요하기 때문에 회로의 면적이 매우 커진다는 문제가 생긴다. 이러한 문제를 해결하기 위해 아래와 같이 분할 정복 알고리즘을 사용해 푸리에 변환을 단순화 시킬 수 있으며 이를 고속 푸리에 변환(Fast Fourier Transform)이라고 한다. 더불어, 위와 같은 회로를 통해 고속 푸리에 변환을 회로로 구현할 수 있는데, 이를 위해서는 두 개의 입력에 대해 합과 차를 구하는 회로(butterfly unit)와 복소수의 곱셈을 처리할 수 있는 곱셈기(complex multiplier)가 필요하다. 본 실험에서는 지난 시간에 구현한 butterfly unit과 twiddle factor multiplier(complex multiplier)를 사용해 16pt 고속 푸리에 변환 회로를 구현한다. 2. 구현 과정 위의 그림은 [1. 개요]에서의 8pt FFT architecture를 확장하여 16pt FFT architecture를 나타낸 그림이다. 위 그림처럼 회로를 구성하기 위해서는 32개의 butterfly unit과 24개의 complex multiplier 가 필요하다. 그러나 각각의 모듈들이 항상 사용되는 것이 아니라 특정 타이밍에만 연산이 이루어지기 때문에 이러한 구조는 상당히 비효율적이다. 따라서 아래와 같이 pipelining을 통해 회로를 개선시킬 수 있다. 위 회로는 pipelined 16pt FFT architecture를 나타낸 것이다. x[0] 입력은 x[8] 입력과 함께 연산이 이루어져야 하기 때문에 x[8] 입력이 들어올 때 까지 shfit register에 보관되어있다가 두 입력이 함께 butterfly unit의 입력으로 들어간다. Butterfly unit의 덧셈 출력은 곧바로 첫 번째 stage의 출력이 되며, 뺄셈 출력은 shift register의 입력으로 들어간다. 열여섯 개의 입력이 모두 들어오고 나면 새로운 입력이 다시 shift register에 저장되며, 저장되어있었던 뺄셈 출력은 twiddle factor와 곱 연산을 거친 뒤 첫 번째 stage의 출력이 된다. 두 번째 stage도 마찬가지로 첫 번째 stage의 출력을 입력으로써 사용하여 같은 방식으로 회로가 동작한다. 첫 번째 stage가 존재하지 않는다면 두 번째 ~ 네 번째 stage만으로 8pt FFT archtecture가 될 수 있다. 다시 말해 이 FFT architecture의 포인트 확장은 단순히 기존 FFT architecture의 입력단에 추가적인 shift register, butterfly unit, complex multiplier를 추가하는 것으로써 가능하다. 본 회로가 올바르게 동작하기 위해서는 회로의 각 stage의 MUX의 select bit을 적절히 선택해주어야 하고, complex multiplier의 입력으로 들어가는 twiddle factor를 올바르게 결정해야 한다. 본 실험에서 는 두 가지 인자(select bit, twiddle factor)를 결정하기 위해 counter를 사용하였으며, 16pt FFT 이기 때문에 4bit를 가지는 counter를 사용하였다. 첫 번째 입력이 들어온 시점의 counter값이 0이라고 가정하면, 각 stage에 사용될 적절한 select bit 값(sel0 ~ sel3)은 위 표와 같다. 카르노 맵 등의 기법을 사용해 적절한 논리식을 구하면 아래와 같이 select bit을 계산할 수 있다. (A는 counter의 MSB, D는 counter의 LSB이다.)                마찬가지로, 여덟 개의 twiddle factor(  ~  )을 각각   ≤  ≤ 이라고 한다면 적절한 idx값은 위의 표와 같다. 이 때              이기 때문에 첫 stage 외에 다른 stage에서의 twiddle factor도   ~  중 하나이며, 로 나타낼 수 있다. Select bit이 1인 경우에는 complex mutiplier가 사용되지 않으므로, idx값이 어떠한 값이 되어도(any value) 상관이 없다. 이러한 성질을 이용해 논리식을 간단하게 표현할 수 있다. 더불어, 마지막 stage에서는 모든 twiddle factor가    이므로 complex multiplier가 불필요하며, 따라서 idx값을 구할 필요가 없다. 위의 표를 논리식으로 나타내면 아래와 같다.                  3. Timing Diagram 구현한 16pt FFT architecture의 동작을 테스트하기 위해 테스트벤치 코드를 이용해 파형을 확인하였다. 사전에 만들어진(주어진) 총 1024개의 input vector data와 output vector data를 이용해 정상 동작 여부를 확인한 결과 모든 vector data가 구현한 FFT architecture의 출력과 파형이 일치하였다. 따라서 회로가 올바르게 동작함을 확인할 수 있었다. 더불어, pipeline을 구현하기 위해 추가한 flip-flop들, 입출력단의 flip-flop들과 shift register의 flip-flop들에 의하여 19 clock의 latency가 발생함을 확인할 수 있었다. 4. Synthesize Result & Critical Path 합성 후 16pt FFT architecture의 block diagram은 위와 같았다. 의도한 바와 같이, 입력이 각 stage의 shift register(SR), butterfly unit(BF), twiddle factor multiplier(TF)를 거쳐 모듈의 출력으로 내보냄을 확인할 수 있다. 레지스터 counter로부터 idx값을 계산해 twiddle factor의 값을 생성(Wgen1)하고, complex multiplier(TF1)의 피연산자로 입력되어 계산된 뒤 출력되는 경로가 본 회로의 critical path임을 확인할 수 있었다. 5. Timing Report 클럭 주기를 초기에 10.0ns로 설정 후 점차 낮추어가며 회로가 동작할 수 있는 가장 빠른 클럭을 찾아보았다. 각 클럭 주기에 대한 slack값과 state는 아래와 같았다. 클럭 주기(ns) Data required time(ns) Slack State 10 9.52 0.00 MET 9 8.52 0.00 MET 8 7.49 0.00 MET 6 5.52 -1.80 VIOLATED 7 6.52 -0.71 VIOLATED 7.5 7.02 -0.23 VIOLATED 7.7 7.22 -0.01 VIOLATED 7.8 7.32 -0.05 VIOLATED 7.9 7.41 0.00 MET 따라서, 본 회로가 동작할 수 있는 가장 낮은 클럭 주기는 7.9ns이고, 약 126.6MHz의 클럭에서 가장빠르게 작동할 수 있다는 것을 확인할 수 있었다. 이때의 timing report는 아래와 같았다. Timing report에 따르면 본 회로의 critical path는 [cnt_reg] -> [Wgen1] -> [TF1] -> [SR_in2] 이다. 이는 [3. Synthesize Result & Critical Path]에서 확인한 바와 같았다. 6. Area Report & Power Report 본 회로의 total cell area는 633559.56μm², total dynamic power는 17.7591mW임을 알 수 있었다. Pipelining을 통해 multiplier와 adder의 개수를 감소시켰음에도 불구하고, 여전히 많은 multiplier 와 adder가 사용되기 때문에 회로의 면적이 매우 큼을 알 수 있었다.