[VLSI설계및실험] (10주차) Fast Fourier Transform, Butterfly Unit, Twiddle Factor Multiplier (Complex Multiplier), Twiddle Factor MUX

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

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

10.pdf

0.55MB

src.zip

0.04MB

 

VLSI 설계 및 실험보고서 LAB 10 # Fast Fourier Transform 1. 개요 여덟 개의 입력에 대해 이산 푸리에 변환(Discrete Fourier Transform)은 아래와 같은 수식으로 나타낼 수 있다. 그러나 위의 수식을 회로로 구현하기 위해서는 64개의 multiplier와 56개의 adder가 필요하기 때문에 회로의 면적이 매우 커진다는 문제가 생긴다. 이러한 문제를 해결하기 위해 아래와 같이 분할 정복 알고리즘을 사용해 푸리에 변환을 단순화 시킬 수 있으며 이를 고속 푸리에 변환(Fast Fourier Transform)이라고 한다. 더불어, 위와 같은 회로를 통해 고속 푸리에 변환을 회로로 구현할 수 있는데, 이를 위해서는 두 개의 입력에 대해 합과 차를 구하는 회로(butterfly unit)와 복소수의 곱셈을 처리할 수 있는 곱셈기(complex multiplier)가 필요하다. 본 실험에서는 butterfly unit, twiddle factor multiplier(complex multiplier), twiddle factor MUX를 구현한다. 또, 다음주 실험에서 이번주에 구현한 세 회로를 사용해 고속 푸리에 변환 회로를 구현한다. # Butterfly Unit 1. 개요 Butterfly unit은 위와 같이 두 개의 입력을 받아 두 입력의 합과 차를 각각 출력시키는 회로이다. 구현하고자 하는 FFT 회로가 복소수의 입력을 받아야 하고 twiddle factor(coefficient)도 복소수로 이루어져있기 때문에, butterfly unit 역시 복소수 계산을 고려하여 설계해야 한다. 입력은 실수부 허수부가 각각 12bit씩 입력되기 때문에 출력은 실수부 허수부가 각각 13bit가 나오게 된다. 하지만 butterfly unit에 의해 출력의 bit수가 늘어나게 되면 FFT의 stage가 지남에 따라 출력의 bit수가 점점 커지는 문제가 생기기 때문에, 약간의(무시할 수 있는) loss를 감수하고 출력의 bit를 12bit 로 유지(truncate)시켰다. 2. Timing Diagram 구현한 butterfly unit의 동작을 테스트하기 위해 테스트벤치 코드를 이용해 파형을 확인하였다. 사전에 만들어진(주어진) 총 1024개의 input vector data와 output vector data를 이용해 정상 동작 여부를 확인한 결과 모든 vector data가 구현한 butterfly unit의 출력과 파형이 일치하였다. 따라서 회로가 올바르게 동작함을 확인할 수 있었다. (err = 0) 입력(A, B)의 MSB 12bit이 실수부, LSB 12bit이 허수부이기 때문에 각각의 값을 나누어 합과 곱을 계산하였고 LSB 1bit를 truncate 시킨 뒤 실수부와 허수부를 합쳐(concatenation) 출력하였다. 3. Synthesize result 합성 후 butterfly unit의 block diagram은 위와 같았다. 의도한 바와 같이, 두 입력(A, B)의 비트를 반으로 나누어 adder와 subtracter의 입력으로 각각 사용하고, adder와 subtracter의 출력을 합쳐서 모듈의 출력으로 내보냄을 확인할 수 있다. A의 실수부(MSB 11bits)로부터 adder를 거쳐 합의 실수부를 계산하는 path가 본 회로의 critical path임을 확인할 수 있었다. 4. Area Report 본 회로의 total cell area는 8941.36μm²임을 알 수 있었다. 클럭을 사용하지 않는 non-combinational circit이기 때문에 모든 area가 combinational area로 이루어져 있음을 확인할 수 있었다. # Twiddle Factor Multiplier (Complex Multiplier) 1. 개요 Twiddle factor multiplier는 butterfly unit의 출력(복소수)에 twiddle factor(복소수)를 곱해주는 회로이다. 두 복소수의 곱을 연산하기 위해서는 네 번의 곱연산과 두 번의 합연산을 해야하기 때문에 실수 multiplier에 비해 더 많은 area가 필요하다. Twiddle factor multiplier의 입력은 실수부 허수부가 각각 12bit씩( (12,10) ) 입력되기 때문에 곱셈기의 출력은 24bit가( (24, 20) ) 나오게 되고 덧셈기의 출력은 출력은 실수부 허수부가 각각 25bit씩 나오게 된다. Butterfly unit과 마찬가지로 출력의 bit수가 늘어나게 되면 FFT의 stage가 지남에 따라 출력의 bit수가 점점 커지는 문제가 생기기 때문에, loss를 감수하고 출력의 bit를 12bit로 유지(truncate) 시켰다. 2. Timing Diagram 구현한 twiddle factor multiplier의 동작을 테스트하기 위해 테스트벤치 코드를 이용해 파형을 확인하였다. 사전에 만들어진(주어진) 총 1024개의 input vector data와 output vector data를 이용해 정상 동작 여부를 확인한 결과 모든 vector data가 구현한 twiddle factor multiplier 출력과 파형이 일치하였다. 따라서 회로가 올바르게 동작함을 확인할 수 있었다. (err = 0) 입력(C, T)의 MSB 12bit이 실수부, LSB 12bit이 허수부이기 때문에 각각의 값을 나누어 곱과 합을 계산하였고 LSB 1bit를 truncate 시킨 뒤 실수부와 허수부를 합쳐(concatenation) 출력하였다. 3. Synthesize result 합성 후 twiddle factor multiplier의 block diagram은 위와 같았다. 의도한 바와 같이, 두 입력(C, T)의 비트를 반으로 나누어 각각을 실수부와 허수부로써 multiplier의 입력으로 사용하고, 그 출력을 닷adder(subtracter)를 통해 더한 뒤 truncate를 거쳐 모듈의 출력으로 내보냄을 확인할 수 있다. T의 실수부(MSB 11bits)로부터 multiplier와 subtracter를 거쳐 곱의 실수부를 계산하는 path가 본 회로의 critical path임을 확인할 수 있었다. 4. Area Report 본 회로의 total cell area는 104866.10μm²임을 알 수 있었다. 클럭을 사용하지 않는 non-combinational circit이기 때문에 모든 area가 combinational area로 이루어져 있음을 확인할 수 있었다. 또한 면적이 큰 multiplier를 네 개나 사용하기 때문에 butterfly unit에 비해 훨씬 큰 면적을 차지하였다. # Twiddle Factor MUX 1. 개요 다음 실험에서 구현하고자 하는 16pt FFT의 architecture는 위와 같다. 위 회로를 구현하기 위해서는 14개의 twiddle factor(  ~  ,  ~  ,  ~  )가 필요하다. 그러나        이기 때문에,              이다. 따라서 첫 stage 외에 다른 stage에서의 twiddle factor( ~  ,  ~  )도   ~  로 나타낼 수 있다. 본 실험에서는 16pt FFT를 구현하기 위해 사용할 twiddle factor MUX를 구현한다. Twiddle factor MUX는 8개의 selection bit(0~7)을 입력으로 받고 twiddle factor(  )를 출력으로 내보낸다. 더불어, behavior level로 구현한 아주 간단한 모듈이기 때문에 별도로 simulation은 진행하지 않았으며, synthesize만 진행하였다. 2. Synthesize result 합성 후 twiddle factor MUX의 block diagram은 위와 같았다. 출력이 여덟 개의 상수이기 때문에, 기본적인 gates(AND, OR, ...) 들로 MUX가 합성되었음을 알 수 있었다. (카르노 맵 등의 기법을 이용해 출력의 각 비트들을 selection bits를 입력으로 받는 여러개의 gates로 표현할 수 있다.)