한국산학기술학회논문지 Vol., No. 6 pp. 222-226, 2 강성진 * 한국기술교육대학교정보기술공학부 A esign of Modified Euclidean Algorithm using Finite State Machine Sung-Jin Kang * School of Info. Tech. Engineering, Korea University of Tech. and Educ. 요약본논문에서는 FSM(finite-state machine) 을이용하여차수계산 (degree computation) 을하지않고수정된유클리드알고리즘 (modified Euclidean algorithm) 을구현할수있는구조를제안한다. 제안된구조는차수계산이필요없기때문에 RS(Reed-Solomon) 복호기의하드웨어복잡도를줄일수있고, 고속의복호기설계가가능하게된다. 제안된구조를이용하는 RS(255,239) 복호기를 Verilog HL로구현하였고, 기존의복호기에비해게이트수를약 3% 정도줄일수있다. Abstract In this paper, an architecture for modified Euclidean(ME) algorithm is proposed, which is using finite-state machine(fsm) instead of degree computation. Since the proposed architecture does not have degree computation circuits, it is possible to reduce the hardware complexity of RS(Reed-Solomon) decoder, so that a very high-speed RS decoder can be implemented. RS(255,239) decoder with the proposed architecture is implemented using Verilog-HL and requires about 3% fewer gate counts than conventional one. Key Words : Reed-Solomon, Modified Euclidean, RS decoder, FSM. 서론 RS 부호는연집오류에대하여우수한오류정정능력을가지고있어서, 광 / 자기저장매체, 유무선통신, 방송, 위성통신등많은통신시스템에서널리사용되고있다. 또한, 최근에는 NAN 플래시메모리분야에서도오류정정을하기위한연구가활발히진행되고있다. 일반적인 RS(n,k,t) 부호에서 n은전체부호어 (codeword) 의길이 ( 심볼개수 ), k는정보심볼의개수를의미하며, 는 RS 부호의오류정정능력을나타낸다 [,6]. RS부호에대한복호기는그림 과같이신드롬연산 (syndrome computation), 키방정식연산 (Key Equation Solver, KES), Chien 탐색, Forney 알고리즘, 오류정정블록및 FIFO(First Input First Output) 로구성된다 [2-5]. 여기에서 KES 블록이오류위치다항식 (error locator polynomial, ) 과오류값다항식 (error value polynomial, ) 을찾기위해가장많은연산을필요로하며, 하드웨어복잡도가가장높다. Received Codeword Syndrome Computation S σ Key Equation Solver ω FIFO Chien Search And Forney Algorithm [ 그림 ] RS 복호기의블록도 i ω( α ) i i Corrected α σ '( α ) Error Codeword Correction RS 복호기에관한연구는대부분 KES 알고리즘에관한것이며, 많은복호알고리즘과복호기구조가연구되어왔다 [-8]. 이중에서수정된유클리드 (Modified Euclidean, ME) 알고리즘은하드웨어의규칙성이우수하여쉽게구현이가능한장점을지니고있다 [4]. ME 알고리즘 [2] 은차수계산과다항식연산을수행하는 processing element(pe) 블록을 개사용하여구현할수있 * 교신저자 : 강성진 (sjkang@kut.ac.kr) 접수일 년 3 월 29 일수정일 년 4 월 26 일게재확정일 년 6 월 8 일 222
으며, 이러한구조는하드웨어규칙성및경로지연 (critical path) 이작아서고속으로동작하는 RS 복호기를구현할수있다 [4,5]. [6] 에서는차수계산이필요치않는 CME(degree computationless ME) 를제안하였지만, 각기본셀 (basic cell) 내의 feedback되는부분과모든셀에입력되는 leading coefficient, 가 feedback되므로상대적으로고속구현이어렵게된다. [7] 에서는 CME 알고리즘의지연시간과 basic cell을개선하여 E-CME 알고리즘을제안하였다. [5] 에서는 [4] 의구조를개선하여 CME 알고리즘구조를제안하였다. [8] 에서는 [4] 의 PE 구조를개선하여마지막 PE 블록의출력신호에서차수비교및 MUX(multiplexer) 가필요없는구조를제안하였다. 본논문에서는 [8] 에서제안된 PE 구조의차수계산회로를 FSM(finite-state machine) 로대치하여하드웨어복잡도를줄일수있는구조를제안한다. 본논문의구성은 2장에서제안된 PE 구조를설명하고, 3 장에서는제안된 PE 구조를이용한 RS(255,239,8) 복호기설계에대하여설명한다. 4장에서는성능평가결과를제시하고 5장에서결론을맺는다. 2. 제안된 PE 구조 [8] 에서는맨마지막 PE 블록의출력 와 의차수를비교하여오류위치다항식 과오류값다항식 을결정하게된다. 이러한이유는 PE 블록에입력된 와 의차수를비교하여다항식스위칭여부를결정한후에다항식연산이이루어지기때문에 PE 블록외부에서출력다항식의차수의변화를알수없기때문이다. [4] 에서는각 PE 블록의출력에서항상 이성립하도록, PE 블록의출력다항식에대하여다항식스위치가이루어지는구조를제안하였으며, 이를통해마지막 PE 블록의출력으로에서바로, 를얻을수있다. [4,8] 의 PE 구조에서다항식차수를계산하는블록은스위치 () 와 신호를발생하기위해서필요하다. PE 블록에서, 차수가같고, 의 leading coefficient가 이아닌경우에, 다항식연산에서 의최고차항계수가제거되어차수가 감소하였으므로, 가되어다항식스위치가일어나게된다. 신호는 PE 블록의출력다항식, 의차수가오류정정능력 보다작을때발생하여, 이후의 PE 블록이동작하지않도록한다. PE 블록에서 신호를발생하기위해서는 의차수와 의차수가같은지를판단할수있다면, 차수계산을하지않아도됨을알수있다. 따라서, 를관찰함으로써차수계산을하지않고 신호를발생시킬수있으며, 식 () 과같은상태변수를정의할수있다. () 여기에서, 이다. 즉, 와 의차수차이는 을초과할수없다. [8] 의 PE는 의차수또는 의차수가 씩감소하는구조이므로, 그림 2와같은상태도로표현이가능하다. 따라서, PE 블록은그림 2와같은상태도를갖는 FSM을사용하여차수계산없이 신호를발생할수있다. 그림 2에서, 는 의 leading coefficient가 일때 이고, 그렇치않으면 인신호이다. Legend : zq/ / / / / λ λ λ t / / / [ 그림 2] 의상태도 [8] 의 PE는 가성립하므로, 의차수가 보다작으면 신호를발생한다. 식 () 에정의된 로부터 와 의차수의차이를알수있지만, 의차수가 보다작은지를알수가없다. 따라서, 각 PE에서 의변화를관찰하고있어야한다. 의차수가감소하는경우는 의 leading coefficient가 인경우와다항식연산후에 가되어다항식스위치가일어나는경우이다. 따라서 의차수가감소하는횟수를카운트하는상태변수를식 (2) 와같이정의할수있다. 만약, 라면 의차수가 2번감소함을의미한다. (2) 여기에서, 이다. 왜냐하면, 번째 PE블록에서 이고 이면, 223
한국산학기술학회논문지제 권제 6 호, 2 가되어야하지만, 이경우는 의차수가 에서 만큼줄어 의차수가 이되었음을의미하기때문에, 신호가발생하여 번째이후의 PE 블록은동작할필요가없으므로, 를증가시킬필요가없기때문이다. 따라서, 이면, 이다. 이로부터식 (3) 과같이 신호가발생됨을알수있다. 신호는 일때식 (3) 과같이계산되며, 이면 이다. 그림 3은본논문에서제안하는 PE 블록의구조이다. 그림 3에서 FSM은그림 2의상태도를가지며, Y 표시의박스는식 (2) 와식 (3) 을통해 와 신호를발생하는회로이다. 그림 3의 X 표시의박스는제어신호,, 를생성하는조합회로이며, leadr, 는각각, 의 leading coefficient를나타낸다. 제어신호 zq는 일때 이된다. 그리고, 와 는각각식 (4), (5) 와같이계산된다. (3) (4) (5) i- i µ i- zq FSM µ i stop i- R i- Q i- L i- U i- starti- zq leadr leadr X Y zq [ 그림 3] 제안된 PE 블록구조 stop i R i Q i L i U i starti 3. RS(255,239,8) 복호기설계 RS(255,239,8) 부호의발생다항식 는식 (6) 과같다. RS 부호기는 239byte의정보심볼을입력받아서, 발생다항식 를이용하여 RS 패리티 6byte를구한후에, 정보심볼 239byte와패리티 6byte를합하여총 255byte의부호어를발생시킨다. RS(n,k,t) 부호의송신된부호어 (codeword) 다항식을, 수신된부호어다항식을, 에러다항식을 라하면, 는식 (7) 과같다. (6) (7) RS 복호기는수신된부호어로부터식 (8) 와같이신드롬 (Syndrome) 를계산한다. (8) KES 블록은신드롬 로부터식 (9) 의키방정식연산을통해오류위치다항식 와오류값다항식 을계산한다 [-4]. (9) 여기에서, 의차수는 이고, 의차수는 이다. RS(255,239,8) 복호기를위한 KES 블록은 2장에서제안된 PE 블록을 개연결하여구현할수있다. µ stop R xq L xu start PE ω PE2 PE5 PE6 σ [ 그림 4] 제안된 PE 블록을이용한 KES 블록도 224
여기에서, 는 ME 알고리즘에서, 이므로, 이다. 그리고,, 이며, 는 [2] 에서와같이발생된다. 즉, 의최고차항을나타내는시간동안에만 이고, 나머지시간에는 이다., 이다. KES블록의출력인오류위치다항식 와오류값다항식 는각각식 (), 식 () 과같다. () () KES 블록에서 와 가계산되면, Chien 탐색과 Forney 알고리즘을이용하여식 (2) 과같이오류정정이가능하다 [3]. (2) 여기에서, 이고, 는오류가정정된 번째부호어심볼이다. Chien 탐색과 Forney 알고리즘은 [4] 에서와같이간단하게구현될수있다. 본논문에서는제안된 PE 구조를이용하는 RS(255,239,8) 복호기를 Verilog HL 를사용하여구현하였으며, 삼성 65nm library로합성하였다. 표 은본논문에서제안된구조의구현결과를비교한것이며, 그림 의 RS 복호기중에서 KES 블록만을비교하였고, 다른블록은 [4,5] 와동일하다. [7] 에서제안된 CME 구조는 latency와 gate count 측면에서가장우수하지만, 고속복호에는적합지않음을알수있다. 제안된 PE 구조와유사한구조를갖는 [4,5] 의구현결과와비교하면, 유사한동작주파수를가지면서본논문에서제안된구조가 [4] 에비해약 3% 정도 gate count가줄어드는것을알수있고, latency도 [4,5] 에비해현저하게줄어드는것을알수있다. [ 표 ] RS(255,239,8) 복호기구현결과 Architecture proposed pcme[5] ME[4] CME[7] Technology 65nm.3um.3um.8um KES (gate count) 4,6 46,2 55,5 8, Clock rate(mhz) 66 66 625 2 Latency (clock) 32 8 8 6 4. 성능평가 제안된 ME알고리즘구조의다양한오류패턴에대한유효성을검증하기위해 RS(255,239,8) 부호의복호기를 C프로그램을작성하여시뮬레이션을수행하였다. 그림 5는 AWGN(Additive White Gaussian Noise) 채널에서 BPSK(Binary Phase Shift Keying) 변조를사용했을때, RS(255,239) 부호의 BER성능곡선이다. RS(255,239) 부호는비트오류확률 에서약 2.5dB의부호이득을가진다. 5. 결론 본논문에서는차수계산을하지않고 FSM을이용하여 ME 알고리즘을구현할수있는 PE 구조를제안하였다. 제안된구조는차수계산회로대신 FSM을이용하기때문에, 고속복호기구현이가능할뿐만아니라하드웨어복잡도를줄일수있다. 제안된구조를이용하는 KES 블록은 66MHz의고속 clock에서동작하며, [5] 에비해약 3% 정도 gate count가줄어듬을확인하였다. 참고문헌 [ 그림 5] RS(255,239) 부호의 BER 성능 [] S. B. Wicker, Error Control Systems for igital Communication and Storage, Englewood Cliffs, NJ, Prentice-Hall, 995. [2] H. Shao, T. Truong, L. eutsch, J. Yuen, I. Reed, "A VLSI design of a Pipeline Reed-Solomon ecoder," IEEE Trans. on Computers, Vol.c-34, No.5, pp.393-43, May 985. [3] L. Song, M. Yu, M. Shaffer, "- and 4-Gb/s 225
한국산학기술학회논문지제 권제 6 호, 2 Forward Error Correction evices for Optical Communications," IEEE Journal of Soild-State Circuits, Vol.37, No., pp.565-573, Nov. 22. [4] Hanho Lee, "High-Speed VLSI Architecture for Parallel Reed-Solomon ecoder," IEEE Trans. on VLSI Systems, Vol., No.2, pp.288-294, April 23. [5] S. Lee, H. Lee, J. Shin, J. Ko, "A High-Speed Pipelined egree-computationless Modified Euclidean Algorithm Architecture for Reed-Solomon ecoders," ISCAS, pp. 9-94, May, 27. [6] J. H. Baek and M. H. SunWoo, "New degree computationless modified Euclid's algorithm and architecture for Reed-Solomon decoder", IEEE Trans. Very Large Integr. (VLSI) Syst., vol. 4, no. 8, pp 95-92, Aug. 26. [7] J. H. Baek and M. H. SunWoo, "Enhanced degree computationless modified Euclid's algorithm for Reed-Solomon decoders," Electronics Letters, vol. 43, no. 3, pp. 75-76, Feb., 27. [8] 강성진, "RS(23,7) 리드-솔로몬복호기설계," 한국해양정보통신학회논문지, Vol.2, No.2, pp.2286-2292, ec., 28. 강성진 (Sung-Jin Kang) [ 정회원 ] 994년 8월 : 연세대학교대학원전자공학과 ( 공학석사 ) 998년 8월 : 연세대학교대학원전자공학과 ( 공학박사 ) 22년 9월 ~ 27년 2월 : 전자부품연구원책임연구원 27년 3월 ~ 현재 : 한국기술교육대학교정보기술공학부조교수 < 관심분야 > WPAN/WLAN, MOEM SoC 226