FFT(05.20)

https://github.com/AhmedAalaaa/32-point-FFT-Verilog-design-based-DIT-butterfly-algorithm

GitHub - AhmedAalaaa/32-point-FFT-Verilog-design-based-DIT-butterfly-algorithm: This project aims to design an 32-point FFT (Fas

 

FPGA내의 자원 문제로 1024 point 에서 32 point로 변경해서 진행.

아키텍쳐적으로 하드웨어 reuse하는 방법도 있겠지만 먼저 32point로 진행해보며 감을 잡기로 하였음.

 

32개의 [15:0] real input값을 입력으로 받으며 최종적으로 output은 real, im값이 각각 [15:0]으로 출력됨.

 

이 알고리즘은

multiple clock design

을 사용해 회로 내의 여러개의 서로 다른 클락주파수를 생성하였고 파이프라인 스테이지의 개수를 고려하여 클럭을 인가함으로써 안정성을 확보함.

Time shared desgin

하나의 hw자원을 시간을 나누어 번갈아 사용하는 방식을 사용함. stage별로 사용되는 mac연산기의 갯수와 종류는 같고, 인자만 다르기 때문에 stage별로 하드웨어를 재활용한다.

 

1. data input

module m_reg_file #
(
    parameter ADDR_WIDTH = 5,
    parameter DATA_WIDTH = 16,
    parameter DEPTH      = 32
)

(
    input                       clk,
    input      [ADDR_WIDTH-1:0] addr,
    input      [DATA_WIDTH-1:0] data,
    input                       we,

    output reg [DATA_WIDTH-1:0] data00,
    output reg [DATA_WIDTH-1:0] data01,
    output reg [DATA_WIDTH-1:0] data02,
    output reg [DATA_WIDTH-1:0] data03,
    output reg [DATA_WIDTH-1:0] data04,
    output reg [DATA_WIDTH-1:0] data05,
    output reg [DATA_WIDTH-1:0] data06,
    output reg [DATA_WIDTH-1:0] data07,
    output reg [DATA_WIDTH-1:0] data08,
    output reg [DATA_WIDTH-1:0] data09,
    output reg [DATA_WIDTH-1:0] data10,
    output reg [DATA_WIDTH-1:0] data11,
    output reg [DATA_WIDTH-1:0] data12,
    output reg [DATA_WIDTH-1:0] data13,
    output reg [DATA_WIDTH-1:0] data14,
    output reg [DATA_WIDTH-1:0] data15,
    output reg [DATA_WIDTH-1:0] data16,
    output reg [DATA_WIDTH-1:0] data17,
    output reg [DATA_WIDTH-1:0] data18,
    output reg [DATA_WIDTH-1:0] data19,
    output reg [DATA_WIDTH-1:0] data20,
    output reg [DATA_WIDTH-1:0] data21,
    output reg [DATA_WIDTH-1:0] data22,
    output reg [DATA_WIDTH-1:0] data23,
    output reg [DATA_WIDTH-1:0] data24,
    output reg [DATA_WIDTH-1:0] data25,
    output reg [DATA_WIDTH-1:0] data26,
    output reg [DATA_WIDTH-1:0] data27,
    output reg [DATA_WIDTH-1:0] data28,
    output reg [DATA_WIDTH-1:0] data29,
    output reg [DATA_WIDTH-1:0] data30,
    output reg [DATA_WIDTH-1:0] data31
);

SIMO방식으로 설정됨. 

각각의 stage별로 한번의 mac연산이 이루어지기 위해서 input data/2개 만큼의 연산기를 인스턴스할 예정인데, 그러기 위해서는 한번에 모든 레지스터를 접근할 수 있어야함. 따라서 sram으로 만들기 보다는 모두 각각 F/F으로 합성함.

리소스를 많이 차지하지만 32개정도는 감당할 수 있다.

각각의 TWIDDLE FACTOR도 동일하게 설정되었다.

 

이렇게 입력된 값들은 다음 클락에서 PIPELINE REG에 저장된다. 

 

2. FFT STAGE

각각의 FFT Stage에서 하나의 연산 하드웨어를 재활용한다. 

 

3. 하드웨어 연산기

하드웨어에서 사용하는것은 고정소수점을 사용한 곱셈 연산을 구현한다.

• A와 B를 받아서 C=AxB를 계산
• A,B,C는 고정소수점 수
• sign을 고려하여 2의 보수를 이용한 연산 수행
• 곱셈후 shift를 통해 q비트만큼 스케일 다운

input  clk, rst;
input  [N-1:0] A, B;
output reg [N-1:0] C;


reg [2*N-1:0] P; // 곱셈 결과 (더 넓은 비트폭 필요)

 

이런식으로 입력, 출력은 고정된 비트폭, 내부 연산은 2배의 비트폭이 필요하다.

 

고정소수점 연산의 경우의 수

• A>0, B>0

        if(A[N-1] == 0 && B[N-1] == 0) begin
            temp1 = 0;
            temp2 = 0;
            temp3 = 0;
            P     = A * B;
            C     = P[N - 1 + Q:Q];

그냥 곱한다음에 Q비트 shift하여 정렬하면 된다.

 

• A>0, B<0

        else if(A[N-1] == 0 && B[N-1] == 1) begin
            temp1   = 0;
            temp2   = ~B + 1'b1;
            P       = A * temp2;
            temp3   = P[N - 1 + Q:Q];
            C       = ~temp3 + 1'b1;
        end

A가 음수, B가 양수일경우

먼저 A에 2의 보수를 취해 양수를 만들고, AxB를 계산한다. 마지막에 결과에 2의보수를 취해서 부호를 교정한다.

 

• A<0, B>0
• A<0, B<0

두 경우도 유사함.

 A[N-1:0]   ─┬─> [2's Complement Unit?] ─┐
            │                          │
            │                          ├─> [Multiplier] ──> [Shift Right Q bits] ─> [2's Complement Unit?] ─> C
 B[N-1:0]   ─┴─> [2's Complement Unit?] ─┘

위와같은 하드웨어 구조

2의 보수 : not게이트와 ripple carry adder

곱셈기 : a*b를 계산하는 정수 곱셈기. 고정소수점 곱셈에 경우 정수처럼 곱셈을 수행한 후 결과에 소수점 위치를 재정렬함.

shift - and - add 방식 or Booth multiplier or DSP블록이 사용됨.

 

4. 최종결과

5단계 파이프라인 결과를 진행 후 직렬로 데이터를 출력한다.