[논문]Common Sub-expression Sharing을 사용한 저면적 FFT 프로세서 구조

장영범; 이동훈

doi:10.5762/kais.2011.12.4.1867

Common Sub-expression Sharing을 사용한 저면적 FFT 프로세서 구조
Low-area FFT Processor Structure using Common Sub-expression Sharing 원문보기

한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society, v.12 no.4, 2011년, pp.1867 - 1875

장영범 (상명대학교 정보통신공학과) , 이동훈 (상명대학교 정보통신공학과)

초록
AI-Helper

이 논문에서는 저면적 256-point FFT 구조를 제안한다. 저면적 구현을 위하여 CSD(Canonic Signed Digit) 곱셈기 방식을 채택하여 구현하였다. CSD 곱셈기 방식을 효율적으로 적용하기 위해서는 곱셈연산의 가지 수가 적어야 하는데, 여러 알고리즘을 조사한 결과 Radix-$4^2$ 알고리즘이 곱셈연산의 가지 수가 적음을 발견하였다. 따라서 제안 구조는 Radix-$4^2$ DIF 알고리즘과 CSD 곱셈기 방식을 사용하였다. 즉 Radix-$4^2$ 알고리즘을 사용하여 4개의 스테이지에서 사용되는 곱셈연산의 가지 수를 최소화한 후에 각각의 곱셈연산 블록은 CSD 곱셈기를 사용하여 구현하였다. CSD 곱셈기 구현에서 공통패턴을 공유하여 덧셈기의 수를 줄일 수 있는 CSS(Common Sub-expression Sharing) 기술을 사용하여 구현면적을 더욱 감소시켰다. 제안된 FFT 구조를 Verilog-HDL 코딩 후 합성하여 구현한 결과, Radix-4를 사용한 구조와 비교하여 복소 곱셈기 부분의 29.9%의 cell area 감소를 보였고 전체적인 256-point FFT 구조에 대한 비교에서는 12.54% cell area 감소를 보였다.

Abstract ▼ AI-Helper

In this paper, a low-area 256-point FFT structure is proposed. For low-area implementation CSD(Canonic Signed Digit) multiplier method is chosen. Because multiplication type should be less for efficient CSD multiplier application to the FFT structure, the Radix-$4^2$ algorithm is chosen for those purposes. After, in the proposed structure, the number of multiplication type is minimized in each multiplication block, the CSD multipliers are applied for implementation of multiplication. Furthermore, in CSD multiplier implementation, cell-area is more reduced through common sub-expression sharing(CSS). The Verilog-HDL coding result shows 29.9% cell area reduction in the complex multiplication part and 12.54% cell area reduction in overall 256-point FFT structure comparison with those of the conventional structure.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

그림 5의 덧셈 블록은 식 (12)의 덧셈연산을 수행한다. 그림 5의 곱셈 연산 블록은 많은 종류의 곱셈을 수행하므로 구현면적을 줄여야 하는 것이 이 논문의 핵심 목표이다. 두 번째 스테이지에서는 256개의 Twiddle Factor 중에서 그림 6과 같이 1/8에 해당하는 32개의 Twiddle Factor 만을 고려하면 된다.
이 논문에서 OFDM 시스템에서 큰 면적을 차지하고 있는 FFT 블록에 대하여 CSD 곱셈기 방식의 새로운 FFT 구조를 제안하였다. 덧셈기 만을 사용하여 구현하기 위해서는 곱셈연산의 가지 수가 가장 적은 Radix-4² 알고리즘을 선택함으로써 곱셈연산의 가지 수를 14.
이 논문에서는 CSD 곱셈기 방식의 새로운 고속/저면적 FFT 구조를 제안한다. 고속 FFT 구현을 위하여 Radix-4 계열을 선택하였으며 저면적 구현을 위하여 CSD 곱셈기 방식을 선택하였다.
모든 스테이지에서 사용되는 Delay Commutator는 MDC(Multi-path Delay Commutator) 방식을 사용하였다. 이 논문에서는 각 스테이지에서 사용되는 곱셈연산을 저면적으로 구현하는 CSD 방식을 제안한다. 마지막 스테이지에서는 곱셈연산이 사용되지 않으므로 앞의 3개의 스테이지에 대한 곱셈연산 구조를 다음 절에서 제안한다.
이 절에서는 제안된 FFT 프로세서의 효율성을 기존 구조와 비교하여 살펴보기로 한다. 먼저 제안구조의 알고리즘을 통하여 이론적으로 곱셈연산과 덧셈연산의 수가 얼마나 감소 할 수 있는지를 알아보고 다음으로 합성을 통하여 면적이 실제 얼마나 감소하였는지 실험을 통하여 알아보기로 한다.

제안 방법

Verilog HDL로 설계한 FFT 프로세서를 Chartered 0.18μm CMOS 셀 라이브러리를 이용하여 합성하였고 두 구조 모두 동일한 constraints를 적용하였다.
즉 CSD형 계수를 그대로 사용할 때보다 61개를 줄일 수 있었다. 그림 7과 그림 8에서 보듯이 초기 입력 값을 사용하여 공통 패턴을 만들고 이 공통패턴 x₂ , x₃ , x₄ , x₅과 초기입력 값을 이용하여 쉬프트와 덧셈기를 통해 63개의 출력이 나오도록 설계하였다.
두 번째 스테이지의 DC2도 MDC 방식을 사용하여 설계하였다. 이제 두 번째 스테이지의 버터플라이 블록을 설계해보기로 한다.
이 절에서는 제안된 FFT 프로세서의 효율성을 기존 구조와 비교하여 살펴보기로 한다. 먼저 제안구조의 알고리즘을 통하여 이론적으로 곱셈연산과 덧셈연산의 수가 얼마나 감소 할 수 있는지를 알아보고 다음으로 합성을 통하여 면적이 실제 얼마나 감소하였는지 실험을 통하여 알아보기로 한다.
이 절에서는 CSD 곱셈기를 사용한 새로운 고속/저면적 256-point FFT의 구조를 제안한다. 즉 곱셈연산을 위하여 덧셈기와 쉬프트 연산만을 사용하는 CSD 곱셈기 FFT 구조를 제안한다.
이제 덧셈 연산의 수를 더욱 줄이기 위해 CSS 방식을 실수부에 적용하기로 한다. 공통 패턴은 표 2에서 2중 실선으로 표현하였다.
이후 Xilinx ISE 7.1i로 Verilog-HDL 코딩을 하고 Modelsim을 이용하여 나온 출력 값을 테스트벡터와 비교하여 HDL 코딩을 검증하였다.
제안한 FFT 프로세서의 구현면적 감소에 관한 효율성을 시뮬레이션 하기 위해 그림 1과 같은 파이프라인 256-point Radix-4² MDC 구조를 구현하였다. 제안구조의 효율성을 비교하기 위해 256-point Radix-4 MDC 구조를 구현하여 비교하였다.
이 절에서는 CSD 곱셈기를 사용한 새로운 고속/저면적 256-point FFT의 구조를 제안한다. 즉 곱셈연산을 위하여 덧셈기와 쉬프트 연산만을 사용하는 CSD 곱셈기 FFT 구조를 제안한다. 우리가 선택한 Radix-4²의 알고리즘을 사용한 256-point FFT의 전체 구조의 블록 도는 그림 1과 같이 4개의 스테이지로 구성된다.

대상 데이터

MDC 구조의 function을 검증하였다. 즉 각각의 스테이지 출력과 최종 256개 출력이 정확한지 검증하였다. 여기에서 만들어진 각 스테이지 출력 값은 Verilog-HDL 코딩의 검증을 위한 테스트벡터로 사용하였다.
표 7에서 보듯이 기존의 구조는 2.746mm²로 합성되었으며 제안구조는 2.402mm²로 합성되었다. 제안된 구조가 기존 구조와 비교하여 면적이 12.

데이터처리

Matlab을 사용하여 제안된 256-point Radix-4² MDC 구조의 function을 검증하였다. 즉 각각의 스테이지 출력과 최종 256개 출력이 정확한지 검증하였다.
MDC 구조를 구현하였다. 제안구조의 효율성을 비교하기 위해 256-point Radix-4 MDC 구조를 구현하여 비교하였다.

이론/모형

Radix-4² 알고리즘을 사용하여 두 스테이지를 설계하였으므로 이제 16-point FFT가 남았다. 이에 대하여 다시 Radix-4² 알고리즘을 적용하기로 한다.
이 논문에서는 CSD 곱셈기 방식의 새로운 고속/저면적 FFT 구조를 제안한다. 고속 FFT 구현을 위하여 Radix-4 계열을 선택하였으며 저면적 구현을 위하여 CSD 곱셈기 방식을 선택하였다. CSD 곱셈기 방식을 사용하여 저면적으로 구현하기 위하서는 복소 곱셈연산의가지 수가 적어야만 한다.
곱셈기를 사용하지 않는 256-point FFT 구조를 만들기 위해서 알고리즘을 먼저 선택해야 한다. 고속 연산을 위하여 Radix-4 계열의 알고리즘을 선택하였고, 그 중에서도 곱셈연산의 수가 적은 Radix-4² 알고리즘을 사용하여 저 전력 구조를 설계하기로 한다. 먼저 Radix-4² 알고리즘에 대하여 간단히 소개한다.
오직 3개의 곱셈만 사용되므로 덧셈기와 쉬프트를 사용하여 구현하였다. 곱셈용 계수는 CSD형의 계수를 사용하였다.
오직 3개의 곱셈만 사용되므로 덧셈기와 쉬프트를 사용하여 구현하였다. 곱셈용 계수는 덧셈 연산의 수를 줄이기 위하여 CSD(Canonic Signed Digit)형의 계수를 사용하였다. 계수들의 2진수 표현에서 1의 수가 곧 덧셈의 수가 되므로 1의 빈도가 구현 비용과 비례한다.
덧셈기를 사용한 효율적인 FFT 구조를 설계하기 위하여 곱셈연산의 가지 수가 적어야하므로 우리는 Radix-4² 알고리즘을 선택하였다. 256-point FFT에 대한 곱셈 연산의 가지 수 비교는 표 4와 같다.
또한 덧셈 연산의 효율적인 구현을 위하여 CSD 방식과 CSS 방식을 사용하여 구현하였다. HDL 코딩과 Chartered 0.
256-point FFT는 Radix-4² 알고리즘을 사용하면 4x4x16으로 분해되므로 마지막 16-point FFT는 다시 Radix-4² 알고리즘을 적용한다. 모든 스테이지에서 사용되는 Delay Commutator는 MDC(Multi-path Delay Commutator) 방식을 사용하였다. 이 논문에서는 각 스테이지에서 사용되는 곱셈연산을 저면적으로 구현하는 CSD 방식을 제안한다.
N-point Radix 알고리즘에서 point의 값이 증가할수록 이를 저장하는 ROM의 크기가 커지게 되고, 복소 곱셈 연산의 수도 증가하게 되어 전력 소모 및 면적이 증가하게 된다. 이를 해결하기 위해 두 번째 스테이지에서는 CSD형의 계수와 CSS(Common Sub- expression Sharing) 방식을 사용하여 구현하였다. CSS 방식은 곱셈 연산을 덧셈연산과 쉬프트를 이용하여 구현하는 방법으로서 공통패턴을 정의하여 서로 공유하는 방식이다.
알고리즘을 사용하여 두 스테이지를 설계하였으므로 이제 16-point FFT가 남았다. 이에 대하여 다시 Radix-4² 알고리즘을 적용하기로 한다.
제안구조의 첫 번째와 세 번째 스테이지는 각각 3가지의 계수를 필요로 하며 두 번째 스테이지는 63가지 계수가 필요하여 총 69가지 계수를 필요로 한다. 이와 비교하여 Radix-4의 256-point FFT는 81가지의 계수를 필요하므로 이 논문에서 Radix-4² 알고리즘을 선택하였다.
첫 번째 스테이지의 DC1은 MDC 방식을 사용하여 설계하였다. 이제 첫 번째 스테이지의 버터플라이 블록을 설계해보기로 한다.

성능/효과

또한 덧셈 연산의 효율적인 구현을 위하여 CSD 방식과 CSS 방식을 사용하여 구현하였다. HDL 코딩과 Chartered 0.18μm 공정으로 논리합성하여 cell area를 비교한 결과 12.54%의 면적 감소 효과를 입증하였다.
이 논문에서 OFDM 시스템에서 큰 면적을 차지하고 있는 FFT 블록에 대하여 CSD 곱셈기 방식의 새로운 FFT 구조를 제안하였다. 덧셈기 만을 사용하여 구현하기 위해서는 곱셈연산의 가지 수가 가장 적은 Radix-4² 알고리즘을 선택함으로써 곱셈연산의 가지 수를 14.81% 줄일 수 있었다.
CSD 곱셈기 방식을 사용하여 저면적으로 구현하기 위하서는 복소 곱셈연산의가지 수가 적어야만 한다. 이 논문에서 Radix-4² 알고리즘을 사용하여 복소 곱셈연산의 가지 수를 최소화시킴으로써 저면적 구현을 달성할 수 있었다. 이 논문에서 제안한 CSD 곱셈기 방식에서는 CSS 기술을 사용하는데 이 CSS(Common Sub-expression Sharing) 기술은 각 스테이지의 CSD형 계수를 공통패턴을 찾아 공유함으로써 덧셈 기를 줄여 기존 CSD 알고리즘만을 사용하여 구현한 방식보다 더욱 구현 면적을 줄일 수 있음을 보인다.
이 논문에서 Radix-4² 알고리즘을 사용하여 복소 곱셈연산의 가지 수를 최소화시킴으로써 저면적 구현을 달성할 수 있었다. 이 논문에서 제안한 CSD 곱셈기 방식에서는 CSS 기술을 사용하는데 이 CSS(Common Sub-expression Sharing) 기술은 각 스테이지의 CSD형 계수를 공통패턴을 찾아 공유함으로써 덧셈 기를 줄여 기존 CSD 알고리즘만을 사용하여 구현한 방식보다 더욱 구현 면적을 줄일 수 있음을 보인다. 이 논문의 2장에서는 Radix-4²알고리즘에 대하여 알아보고 3장에서는 저면적 FFT 구조를 제안한다.
667mm² 로 합성되었다. 제안된 곱셈연산 블록의 구현 면적은 기존 블록과 비교하여 약 29.9% 감소됨을 알 수 있다.
402mm²로 합성되었다. 제안된 구조가 기존 구조와 비교하여 면적이 12.54% 감소된 것을 확인 할 수 있다.
그림 7의 실수부 곱셈기에서 사용되는 덧셈기는 85이다. 즉 CSD형 계수를 그대로 사용할 때보다 57개를 줄일 수 있었다.
그림 8의 허수부 곱셈기에서 사용되는 덧셈기는 74이다. 즉 CSD형 계수를 그대로 사용할 때보다 61개를 줄일 수 있었다. 그림 7과 그림 8에서 보듯이 초기 입력 값을 사용하여 공통 패턴을 만들고 이 공통패턴 x₂ , x₃ , x₄ , x₅과 초기입력 값을 이용하여 쉬프트와 덧셈기를 통해 63개의 출력이 나오도록 설계하였다.
표 5에서 보듯이 덧셈기를 사용하여 곱셈연산을 효율적으로 구현하기 위해서 CSS 방식을 사용한 결과 175개의 덧셈기를 사용하여 구현할 수 있었다. 즉 CSD형 계수를 사용하는 구조보다 132개의 덧셈기를 감소시킬 수 있었다.
표 5에서 보듯이 덧셈기를 사용하여 곱셈연산을 효율적으로 구현하기 위해서 CSS 방식을 사용한 결과 175개의 덧셈기를 사용하여 구현할 수 있었다. 즉 CSD형 계수를 사용하는 구조보다 132개의 덧셈기를 감소시킬 수 있었다.
표 6에서 보듯이 기존 256-point Radix-4 구조의 곱셈 연산 블록은 0.952mm²로 합성되었으며 제안된 256-point Radix-4² 구조의 곱셈연산 블록은 0.667mm² 로 합성되었다. 제안된 곱셈연산 블록의 구현 면적은 기존 블록과 비교하여 약 29.

질의응답

핵심어	질문	논문에서 추출한 답변
	FFT의 구현에 무엇이 사용되는가?	FFT의 구현에는 파이프라인 방식이 주로 사용되며, 파이프라인 방식에서는 복소 곱셈연산의 구현이 가장 중요하다. 복소 곱셈연산을 구현하는 방법으로는 Modified Booth 곱셈기를 사용하는 방법이 가장 일반적이며, CORDIC(COordinate Rotation DIgital Computer) 곱셈기를 사용하는 방식도 사용되고 있다.
	파이프라인 방식에 가장 중요한 것은 무엇인가?	FFT의 구현에는 파이프라인 방식이 주로 사용되며, 파이프라인 방식에서는 복소 곱셈연산의 구현이 가장 중요하다. 복소 곱셈연산을 구현하는 방법으로는 Modified Booth 곱셈기를 사용하는 방법이 가장 일반적이며, CORDIC(COordinate Rotation DIgital Computer) 곱셈기를 사용하는 방식도 사용되고 있다.
	FFT의 구현에 중요한 복소 곱셈연산을 구현하는 방법은 무엇인가?	FFT의 구현에는 파이프라인 방식이 주로 사용되며, 파이프라인 방식에서는 복소 곱셈연산의 구현이 가장 중요하다. 복소 곱셈연산을 구현하는 방법으로는 Modified Booth 곱셈기를 사용하는 방법이 가장 일반적이며, CORDIC(COordinate Rotation DIgital Computer) 곱셈기를 사용하는 방식도 사용되고 있다.[1][2] 이와 더불어 CSD(Canonic Signed Digit) 곱셈기를 쓰는 방식도 연구되었다[3].

참고문헌 (8)

R. Sarmiento, V. D. Armas, J. F. Lopez, J. A. Montiel-Nelson, and A. Nunez, "A CORDIC processor for FFT computation and its implementation using gallium arsenide technology", IEEE Trans. on VLSI Systems, vol. 6, No. 1, pp. 18-30, Mar. 1998.

상세보기
M. Bekooij, J. Huisken, and K. Nowak, "Numerical accuracy of Fast Fourier Transforms with CORDIC arithmetic", Journal of VLSI Signal Processing 25, pp. 187-193, 2000.

상세보기
S. M Kim, J. G. Chung, and K. K. Parhi, "Low error Fixed-width CSD Multiplier with Efficient Sign Extension", IEEE Trans. Circuits and Systems-II, vol. 50, No. 12, Dec. 2003.
R. I. Hartley, "Sub-expression sharing in filters using canonic signed digit multipliers", IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Processing, vol. 43, No.10, pp. 677-688, Oct. 1996.

상세보기
Y. Jang, and S. Yang, "Low-power CSD linear phase FIR filter structure using vertical common sub-expression" IEE Electronics Letters, vol. 38, No. 15, pp. 777-779, Jul. 2002.

상세보기
J. Lee and H. Lee, "High-Speed 2-Parallel Radix-24 FFT/IFFT Processor for MB-OFDM UWB Systems", IEICE Trans. on Fundamentals of Electronics, communications, and Computer Science, vol. E91-A, No. 4, pp. 1206-1211, April, 2008.

상세보기
J. Y. Oh, J. S. Cha, S. K. Kim, and M. S. Lim, "Implementation of Orthogonal Frequency Division Multiplexing using radix-N Pipeline Fast Fourier Transform(FFT) Processor", Jpn. J. Appl. Phys., vol. 42, No. 4B, pp. 1-6, April, 2003.

상세보기
최동규, 장영범, "Common sub-expression sharing과 CORDIC을 이용한 OFDM 시스템의 저면적 파이프라인 FFT 구조", 전자공학회논문지, 제46권, SP편 제 4호, pp. 157-164, 2009.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증