Scalable FFT Processor Based on Twice Perfect Shuffle Network for Radar Applications

레이다 응용을 위한 이중 완전 셔플 네트워크 기반 Scalable FFT 프로세서

Scalable FFT Processor Based on Twice Perfect Shuffle Network for Radar Applications

김 건 호 · 허 진 무 · 정 용 철 · 정 윤 호 ^*

한국항공대학교 항공전자정보공학부

Geonho Kim · Jinmoo Heo · Yongchul Jung · Yunho Jung

^*

School of Electronics and Information Engineering, Korea Aerospace University, Gyeonggi-do, 10540, Korea

[요 약]

레이다 시스템의 경우, 타겟의 거리와 속도를 추출하기 위해 FFT (fast Fourier transform) 연산이 필수적으로 요구되며, 실시간 구현을 위해 고속으로 동작하는 FFT 프로세서의 설계가 필요하다. 고속 FFT 프로세서를 위한 하드웨어 구조로 완전 셔플 네트워크 (perfect shuffle network) 구조가 적합하며, 특히 초고속 연산을 위해 radix-4 기반의 이중 완전 셔플 네트워크 (twice perfect shuffle network) 구조가 가장 적절하고 볼 수 있다. 더불어, 다양한 속도 해상도를 요구하는 레이다 응용을 고려할 때, FFT 프로세서는 가변길 이 FFT 연산을 지원할 필요가 있다. 이에 본 논문에서는 8~1024 포인트의 가변 길이 연산을 지원하는 이중 완전 셔플 네트워크 기반의 FFT 알고리즘을 제안하였으며, 이의 하드웨어 구조 설계 및 구현 결과를 제시한다. 제안된 FFT 프로세서는 HDL (hardware description language)을 활용하여 RTL (register transfer level) 설계가 수행되었으며, 0.65μm CMOS 공정을 활용하여 논리 합성한 결과, 총 3,293K 개의 논리 게이트로 구현 가능함을 확인 할 수 있었다.

[Abstract]

In radar systems, FFT (fast Fourier transform) operation is necessary to obtain the range and velocity of target, and the design of an FFT processor which operates at high speed is required for real-time implementation. The perfect shuffle network is suitable for high-speed FFT processor. In particular, twice perfect shuffle network based on radix-4 is preferred for very high-speed FFT processor. Moreover, radar systems that requires various velocity resolution should support scalable FFT points. In this paper, we propose a 8~1024-point scalable FFT processor based on twice perfect shuffle network algorithm and present hardware design and implementation results. The proposed FFT processor was designed using hardware description language (HDL) and synthesized to gate-level circuits using 0.65μm CMOS process. It is confirmed that the proposed processor includes logic gates of 3,293K.

Key word :

Fast Fourier transform, Perfect shuffle network, Radar system, Radix-4.

https://doi.org/10.12673/jant.2018.22.5.429

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-CommercialLicense(http://creativecommon s.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Received 8 October 2018; Revised 11 October 2018 Accepted (Publication) 24 October 2018 (30 October 2018)

*Corresponding Author; Yunho Jung Tel: +82-2-300-0133

E-mail: [email protected]

Ⅰ. 서 론

최근 운전자와 보행자의 안전을 고려한 지능형 자동차에 대 한 관심이 증대되고 있다. 지능형 자동차는 운전자의 신체 상해 를 최소화하는 수동적인 기술의 기존 개념을 넘어서, 사고의 위 험에 대한 정보를 사전에 감지해 운전자에게 전달하거나 차량 을 조작하는 기술로 발전하고 있다 [1]. 이를 위해, 차량에 영상 기반의 센서, 레이다 (radar)와 라이다 (lidar)등의 센서를 장착 해 사고 위험을 감지한다 [2]. 영상 기반의 센서는 주변 밝기 환 경에 민감해 모든 환경에서 신뢰할 수 있는 시스템을 설계하는 데 어려움이 따르지만, 레이다 센서의 경우 영상 기반의 센서에 비해 밝기 환경이나 주변 환경에 민감하지 않기 때문에, 최근 레이다 시스템을 이용한 지능형 자동차가 활발히 연구되고 있 다 [3-4].

레이다 시스템의 경우, 타겟의 거리와 속도를 추출하기 위해 서는 FFT (fast Fourier transform) 프로세서가 필수적이며, 높은 데이터 처리량과 계산량이 요구되므로 효율적인 FFT 프로세서 설계가 요구된다 [5-7]. 특히, 레이다 시스템의 경우 실시간 구 현을 위해 타겟의 도플러 천이 (Doppler shift)에 따른 위상 변화 를 측정하는 FFT 프로세서가 고속으로 동작해야 한다. 따라서, 레이다 시스템을 위한 고속 FFT 프로세서를 설계하기 위해서 완전 셔플 네트워크 (perfect shuffle network)와 시스토릭 어레 이 (systolic array) 기반의 병렬구조를 고려할 수 있으나, 면적과 수행시간의 교환 관계 (trade-off) 및 레이다 시스템의 메모리 구 조를 고려할 때, 완전 셔플 네트워크 기반의 병렬 구조가 레이 다 시스템의 고속 FFT 프로세서의 하드웨어 구조로 가장 적합 하다 [8-10]. 특히, 셔플 네트워크 FFT 프로세서의 속도 증대를 위해서는 radix-4 기반의 완전 셔플 네트워크인 이중 완전 셔플 네트워크 (twice perfect shuffle network)가 가장 적절하고 볼 수 있다 [11].

레이다 시스템에서 속도 해상도 (∆V)는 식 (1)과 같이 정의 된다.

  (1)

여기서, T는 PD 레이다의 경우 PRI (pulse repetition interval), FMCW 레이다의 경우 변조 주기 (sweep time)으로 정의하며, N 은 레이다 시스템에서 타겟의 도플러 천이 (Doppler shift)에 따 른 위상 변화를 측정하는 FFT 포인트 수이다. 즉, 다양한 속도 해상도를 요구하는 레이다 응용 (application)을 고려할 때, 가변 FFT 포인트의 지원이 필요하며, 이에 본 논문에서는 8~1024 포 인트의 가변 길이를 지원하는 이중 완전 셔플 네트워크 기반의

FFT 프로세서를 제안하고 설계 및 검증 결과를 제시한다. 본 논 문의 구성은 다음과 같다. Ⅱ 장에서 이중 완전 셔플 네트워크 알고리즘에 대해 설명하고, Ⅲ 장에서는 제안하는 이중 완전 셔 플 네트워크의 하드웨어 구조 설계결과를 제시한다. Ⅳ 장에서 는 제안된 하드웨어 구조에 대한 구현 결과를 제시하며, 끝으로

Ⅴ 장에서 본 논문의 결론을 맺는다.

Ⅱ. 제안된 FFT 프로세서의 알고리즘

2-1 Radix-4 기반의 이중 완전 셔플 네트워크 알고리즘

Radix-4 기반의 이중 완전 셔플 네트워크의 연결도는 그림 1 과 같다. 양 쪽 노드가 0부터 N−1까지 구성 된다고 했을 때, 이 중 완전 셔플 네트워크는 radix-4 기반의 알고리즘이므로



그림

Radix-4.

그림 1의 이중 완전 셔플 네트워크 연결 원리를 정리하면 수식 (2)와 같다.

 







 

  ≤  ≤ 

 

    

≤  ≤ 

 

    

≤  ≤ 



 

  _{  }





≤  ≤ 

_ _{ }_{ }⋯ __ (3)

여기서, 상위 두 비트 α _n−1α _n−2를 조건으로 이중 완전 셔플 네 트워크의 연결 원리를 나타내면 다음과 같다.

 









 _{ }_{ } 

    _{ }_{ } 

    _{ }_{ } 

    _{ }_{ } 

(4)

예를 들어, N = 16 일 때, i = 0010(2)이면 P(2)는 8번 노드에 연결 되고, i = 1011₍₂₎이면

P(11)는 14번 노드에 연결된다. 이와 같이,

그림

Fig. 2. SFG of the conventional radix-4 FFT (16-point).

그림

network (16-point).

이중 완전 셔플 네트워크에서는 상위 두 비트인 α_n−1α_n−2를 이 용해 완전 셔플 네트워크의 연결을 정의한다 [11].

기존의 radix-4 FFT의 SFG (signal flow graph)는 그림 2와 같 이 매 스테이지마다 버터플라이 연산기에 들어가는 입력 순서 가 다르기 때문에 스테이지마다 입력 순서를 조정하는 모듈이 필요하다. 하지만, 이중 완전 셔플 네트워크 기반 FFT 알고리즘 의 SFG는 그림 3과 같이 모든 스테이지에서 버터플라이 연산

그림

shuffle network (16-point).

기에 들어가는 입력 순서가 동일하기 때문에 스테이지마다 입 력 순서를 조정하는 모듈이 필요하지 않아 하드웨어 면적을 줄 일 수 있다.

그림 4는 16-point 이중 완전 셔플 네트워크 기반의 FFT 연산 중 하나의 스테이지 (stage)에 대한 연결도이다. 연결도의 구조 는 16개의 데이터가 완전 셔플 네트워크의 연결 원리를 이용해 radix-4 버터플라이 (butterfly) 연산기에 입력되면, 버터플라이 연산기마다 4개의 데이터가 출력되며, 다음 스테이지에서 다시 완전 셔플 네트워크의 연결 원리를 이용해 radix-4 버터플라이 연산기에 입력되는 형태이다. 본 논문에서 제안하는 FFT 프로 세서는 이러한 원리를 통해 1024-point로 확장하여 적용하였다.

2-2 가변 길이 FFT 연산

이중 완전 셔플 네트워크로 FFT 알고리즘을 연결하면 네트 워크 연결이 고정된다. 고정된 네트워크에서 가변 길이 FFT 알 고리즘을 설계하기 위해서는 입력 노드를 조정할 필요가 있다.

예를 들어, 전체 노드의 개수가 16개이며 이중 완전 셔플 네트 워크로 연결됐을 때, 그림 5처럼 0, 1, 2, 3, 8, 9, 10과 11 노드에 8개의 데이터를 입력하고, 나머지 노드에는 0을 입력해 8-point FFT 연산을 수행 할 수 있다. 또한, 기존의 이중 완전 셔플 네트 워크는 radix-4 기반이기 때문에 FFT 길이가 4의 지수 승에 해 당하는 길이만 연산 가능하지만, 본 논문에서는 radix-4 버터플 라이 연산기를 이용하여 radix-2 버터플라이 연산까지 수행할 수 있게 설계함으로써 radix-4와 radix-2를 같이 사용한 mixed radix 알고리즘을 구현했다. 따라서, 본 논문에서는 1024-point 뿐 아니라 8/16/32/64/128/256/512-point 까지 지원 가능한 이중 완전 셔플 네트워크 기반 가변 FFT 알고리즘을 설계하였다.

그림

연산 SFG 예시

Fig. 5. Example of 8-point SFG in the 16-point FFT based

on twice perfect shuffle network.

Ⅲ. 제안된 FFT 프로세서 하드웨어 구조

본 장에서는 고속 레이다 시스템을 위한 가변길이 이중 완전 셔플 네트워크 FFT 프로세서의 하드웨어 구조를 설명한다. 아 래의 그림 6은 제안하는 FFT 프로세서의 구조를 도시하고 있 다. 제안된 FFT 프로세서의 하드웨어 구조는 크게 Input Data Mapper 모듈, Output Data Mapper 모듈과 Perfect Shuffle 모듈 로 구성된다. Perfect Shuffle 모듈의 세부 모듈은 Radix-4 버터 플라이 모듈과 복소 승산기 (complex multiplier)들로 구성된다.

메모리로부터 Input Data Mapper 모듈에 하나의 데이터 세 트 (data set)가 입력되면, 첫 번째 스테이지일 때 FFT 길이에 맞 게 입력 순서가 조정된다. 이때 Input Data Mapper에서 두 번째 스테이지부터는 입력된 순서대로 출력한다. Input Data Mapper 모듈을 거친 데이터는 Perfect Shuffle 모듈에 입력되어 한 스테 이지에 해당하는 FFT 연산이 수행된다. 연산된 데이터는 Output Data Mapper 모듈로 이동하는데 현재 스테이지가 FFT 연산의 마지막 스테이지라면 출력 순서가 조정되고 그렇지 않 다면 Output Data Mapper 모듈에 입력된 순서대로 출력한다.

Input Data Mapper 모듈과 Output Data Mapper 모듈은 그림 7과 같이 멀티플렉서와 레지스터로 구성된다. Input Data Mapper 모듈은 가변길이를 지원하기 위해 필요하며, 2장에서 언급했듯이 전체 1024 포인트의 이중 완전 셔플 네트워크를 이 용하여 8/16/32/64/128/512-point를 지원하기 위해서는 입력 순 서를 조정해야 한다. 이때, 지원하는 FFT 길이가 8~1024-point 까지 총 8개이므로 Input Data Mapper 모듈을 구성하는 멀티 플렉서의 최대 입력 개수는 8개이다.

Output Data Mapper 모듈은 FFT 연산을 완료하기 위해 필요 하다. 이중 완전 셔플 네트워크뿐 아니라 모든 FFT 알고리즘은 첫 번째 스테이지 혹은 마지막 스테이지에서 데이터의 순서를 조정해야 한다. 본 논문에서 제안하는 FFT 프로세서는 마지막

그림

processor.

그림

Fig. 7. Block diagram of the data mapper.

스테이지에서 데이터의 순서를 조정하였다. 이때, radix-4 기반 의 FFT 알고리즘은 출력 순서를 digit reverse order로 조정해야 하는데, 16, 64, 256와 1024-point는 4의 지수이므로 출력 순서 를 알고리즘대로 digit reverse order로 조정한다. 반면에 8, 32, 128와 512-point는 4의 지수가 아니므로 표 1에 정리된 규칙에 따라 출력 순서를 조정한다. 표 1에 정리된 것은 비트의 순서를 나타내고 있다. 예를 들어, 8-point에서 4번째 출력 데이터는 α₂ α₁α₀= 100이고 α₀α₂α₁

= 010으로 조정되므로 2번째 출력이 된

그림 8은 제안하는 하드웨어 구조의 타이밍도를 나타낸다.

한 스테이지를 연산하는데 7 클록 사이클이 소요되는 것을 확

표

Table 1. Output Reordering pattern of 8/32/128/512-point.

Point Output Order Reordering Pattern

8 ___ ___

32 _____ _____ 128 _______ _______ 512 ________ _________

인 할 수 있으며, 16-point FFT 연산을 한다면 FFT 연산 결과가 나오기까지 두 스테이지가 필요하므로 14 클록 사이클이 FFT 연산에 필요하다.

Ⅳ. 제안된 FFT 프로세서 설계 및 구현

본 장에선 제안된 FFT 프로세서의 설계 및 구현 결과를 설명 한다. 제안된 구조의 FFT 프로세서는 Matlab을 이용하여 알고 리즘 검증 및 고정 소수점 분석을 통한 최적의 데이터 비트수 결정이 수행되었다. 표 2는 데이터 비트 수에 따른 SQNR (signal to quantization noise ratio) 분석 결과를 보여준다. SQNR 분석 결과를 통해 하드웨어 복잡도와 성능간의 교환 관계를 고 려했을 때, 8 bit가 가장 적합하다는 결론을 내렸다.

Matlab을 이용한 알고리즘 검증과 최적의 비트수를 결정한 이후에는 Verilog-HDL을 이용하여 RTL 설계를 수행하였다.

표 3은 제안된 이중 완전 셔플 네트워크 기반 가변길이 FFT 프 로세서의 0.65μm CMOS 공정 기반 논리 합성 결과를 보여준다.

논리 합성 결과 총 게이트 수는 3,293K개이며, Perfect shuffle 모듈이 병렬 복소 승산기로 인해 가장 큰 면적을 차지한다. 클 록 주파수는 150MHz에서 동작하도록 설계하였고, 1024-point 기준으로 FFT 연산하는데 걸리는 시간은 약 220ns로 본 논문에 서 제안한 FFT 프로세서가 고속 레이다 시스템에 적합한 처리 속도를 얻을 수 있음을 확인하였다.

0 0

0

0 0 1 (16-point)

1

TW_Factor

Stage 1 2 1

TW_Factor1 TW_Factor2 TW_Factor1

oDATA0 oDATA0

iDATA1

oDATA1

TW_Factor2 2 WrEn

oDATA oDone

ㆍㆍㆍ

1023

iDATA1022 iDATA1023 iDATA1023

oDATA1022 oDATA1023 oDATA1023

TW_Factor1

1 2

TW_Factor2 1022

iCLK iStart iPoint RdEn

Addr 0

iDATA iDATA0 iDATA0 iDATA1

그림

Fig. 8. Timing diagram of the proposed FFT processor.

표

number of data bits and FFT points

Point 8 9 10

8 50.11 50.87 51.14

16 46.90 51.75 51.85

32 47.77 50.34 51.23

64 48.36 48.56 48.81

128 43.21 47.85 50.46

256 45.35 48.28 49.47

512 37.44 43.22 47.86

1024 40.26 45.39 48.63

표

150MHz)

Table 3. Logic synthesis results of the proposed FFT

processor (Clock frequency : 150MHz).

Module Gate Count Proportion (%)

Input Data Mapper 204,522 6.21

Output Data Mapper 275,666 8.37

Perfect Shuffle 2,812,924 85.42

Total 3,293,112 100

Ⅴ. 결 론

본 논문에서는 고속 레이다 시스템을 위한 가변길이 Radix-4 완전 셔플 FFT 프로세서를 제안하고, 이의 설계 및 구현 결과를 제시하였다. 제안된 FFT 프로세서에는 이중 완전 셔플 알고리 즘을 적용하여 스테이지마다 입력의 순서를 변경하지 않아 기 존의 FFT 프로세서보다 더 고속으로 연산할 수 있음을 확인하 였다. 또한, 가변길이를 지원하기 위해 radix-4와 radix-2 알고리 즘을 혼합한 mixed radix 알고리즘을 적용하였으며, 하드웨어 면적을 줄이기 위해 radix-4 버터플라이 연산기를 이용하여 radix-2 버터플라이 연산까지 수행할 수 있도록 설계하였다. 따 라서, 제안된 FFT 프로세서는 8, 16, 32, 64, 128, 256, 512, 1024 point를 모두 지원 가능하며, 이로 인해 다양한 속도 해상도를 요구하는 레이다 응용에 적합할 것으로 기대된다.

Acknowledgments

본 논문은 산업통상자원부 및 한국산업기술평가관리원 산 업핵심기술개발사업 (10080619)의 일환으로 수행되었음.

References

[1] M. Abe, “Trends of Intelligent Vehicle Dynamics Controls and Their Future,” New Technology Network Technical

Review, No. 81, pp. 2 -

[2] T. Hanke, N. Hirsenkorn, B. Dehlink, A. Rauch, R.

Rasshofer, and E. Biebl, “Generic architecture for simulation of ADAS sensors,” in Proceeding of the 16th International

Radar Symposium (IRS), Dresden: Germany, pp. 125 -

[3] E. Richter, R. Schubert, and G. Wanielik, “Radar and vision based data fusion—Advanced filtering techniques for a multi object vehicle tracking system,” in Proceedings of the IEEE

Intelligent Vehicles Symposium, Eindhoven: Netherlands,

-

[4] U. Kadow, G. Schneider, and A. Vukotich, “Radar-vision based vehicle recognition with evolutionary optimized and boosted features,” in Proceedings of the IEEE Intelligent

Vehicles Symposium, Istanbul: Turkey, pp. 749 -

2007.

[5] S. Jardak, S. Ahmed, and M.S. Alouini, “Low complexity moving target parameter estimation for MIMO radar using 2D-FFT,” IEEE Transaction on Signal Processing, Vol. 65, No. 18, pp. 4745

-

[6] A. Boughambouz, A. Bellabas, B. Magaz, T. Menni, and M.

Abdelaziz, “Improvement of radar signal phase extraction using All Phase FFT spectrum analysis,” in Detection

Systems Architectures and Technologies Seminar, Algiers:

Algeria, Feb. 2017.

[7] S. Saponara and B. Neri, “Radar sensor signal acquisition and multidimensional FFT processing for surveillance applications in transport systems,” IEEE Transactions on

Instrumentation and Measurement, Vol. 66, No. 4, pp.

604

-

[8] H. Stone, “Parallel processing with the perfect shuffle,”

IEEE Transaction on Computers, Vol. C-20, No.2, pp.

156-161, Feb. 1971.

[9] V. Boriakoff, “FFT computation with Systolic arrays, a new architecture,” IEEE Transaction on Circuit and Systems,

Analog and Digital Signal Processing, Vol. 41, No. 4, pp.

278-284, April. 1994.

[10] A. Suleiman, A. Hussein, K. Bataineh, and D. Akopian,

“Scalable FFT architecture vs. multiple pipeline FFT architectures–hardware implementation and cost,” in

Proceeding of the IEEE International Conference on Systems, Man and Cybernetics, San Antonio: TX, pp.

3792-3796, Oct. 2009.

[11] M. H. Hwang and H, J. Hwang, “Design of radix-4 FFT processor using twice perfect shuffle,” Journal of the

Institute of Electronics and Information Engineers, Vol. 27,

김 건 호 (Geonho Kim)

2012년 3월 ~ 현재 : 한국항공대학교 항공전자정보공학부

※관심분야 : 레이다 신호처리 시스템, 레이다 SoC

허 진 무 (Jinmoo Heo)

2013년 3월 ~ 현재 : 한국항공대학교 항공전자정보공학부

※관심분야 : 레이다 신호처리 시스템, 레이다 SoC

정 용 철 (YongChul Jung)

2015년 8월 : 한국항공대학교 전자 및 항공전자공학과 (공학사) 2017년 2월 : 한국항공대학교 항공전자정보공학부 (공학석사) 2017년 3월 ~ 현재 : 한국항공대학교 항공전자정보공학부 박사과정

※관심분야 : 레이다 신호처리 시스템, 레이다 SoC

정 윤 호 (Yunho Jung)

1998년 2월 : 연세대학교 전자공학과 (공학사) 2000년 2월 : 연세대학교 전기전자공학과 (공학석사) 2005년 2월 : 연세대학교 전기전자공학과 (공학박사) 2005년～2007년 : 삼성전자 책임연구원

2007년～2008년 : 연세대학교 연구교수 2008년～현재 : 한국항공대학교 교수

※관심분야 : 무선 통신 시스템, 항공통신 시스템, 레이다 신호처리 시스템, 모뎀 SoC, 레이다 SoC