논문 05-30-3C-02 한국통신학회논문지 '05-3 Vol.30 No.3C VHDL로구현된직렬승산리드솔로몬부호화기의복잡도분석 학생회원백승훈 *, 종신회원송익호 **, 배진수 * Complexity Analysis of a VHDL Implementation of the Bit-Serial Reed-Solomon Encoder Seung hun Back* Student Member Iick ho Song**, Jin soo Bae* Regular Members 요 약 리드솔로몬부호화기를구현하기위해서제안된구조는널리알려진대로일반적인구조와직렬승산기를쓰는구조가있다. 일반적구조의부호화기는구조가복잡한대신처리속도가빠르고, 반면에직렬승산기를쓰는부호화기는구조는단순하지만처리속도는그다지빠르지않은것으로알려져있다. 이논문에서는, 이널리알려진사실이 VHDL로구현할때는사실이아닐수도있다는것을보인다. 이는, 직렬승산기에필요한쌍대기저변환테이블을구현하는데에는많은게이트가필요한경우가있기때문인것으로해석된다. 한편두가지구조를써서 VHDL로구현한부호화의처리속도는모두같다. Key Words:Reed-Solomon code, VHDL, bit-serial, Berlekamp. ABSTRACT Reed-Solomon code is one of the most versatile channel codes. The encoder can be implemented with two famous structures: ordinary and bit-serial. The ordinary encoder is generally known to be complex and fast, while the bit-serial encoder is simple and not so fast. However, it may not be true for a longer codeword length at least in VHDL implementation. In this letter, it is shown that, when the encoder is implemented with VHDL, the number of logic gates of the bit-serial encoder might be larger than that of the ordinary encoder if the dual basis conversion table has to be used. It is also shown that the encoding speeds of the two VHDL implemented encoders are exactly same. Ⅰ. 서론리드솔로몬 (RS) 부호는통신및저장시스템에널리사용된다 [1]. RS 인코딩동작중에서심벌곱셈은가장복잡하고시간이많이드는과정이다 [2]. 쌍대기저변환을응용한곱셈알고리즘을채용한직렬승산 RS 부호화기는벌리캠프에의해제안되었다 [3]. 이논문에서 RS 부호화기를 VHDL로구현하여성능과복잡도분석을수행하기위한성능지표로서각각부호어하나를부호화하는데필요한클럭수와 VHDL로부호화기를구현하는데필요한논리게이트수를사용한다. 일반적으로알려져있기로는, 직렬승산부호화기는일반적인부호화기에견주어볼때, 구조가간단하기때문에일반적인부호화기보다 * 세종대학교정보통신공학과신호처리연구실 (baej@sejong.ac.kr), ** 한국과학기술원전자전산학과전기및전자공학전공 (isong@sejong.kaist.ac.kr) 논문번호 : KICS2005-02-071, 접수일자 :2005 년 2 월 18 일 본연구는한국과학재단특정기초연구 R01-2004-000-10019-0 지원으로수행되었음. 64
논문 /VHDL 로구현된직렬승산리드솔로몬부호화기의복잡도분석 더적은수의논리게이트로구현할수있는반면, 데이터를직렬로처리하기때문에부호화시간이길다고한다. 그러나이두종류의부호화기를 VHDL 로구현할때필요한논리게이트수를견주어보면어떤경우에는직렬승산부호화기가더복잡할수도있다는것을밝힐수있다. 따라서복잡도가중요한요소가되는응용분야에서 RS 부호화기를 VHDL 로구현하고자할때더욱특별한주의를기울여야한다. Ⅱ. 직렬승산부호화알고리즘 : 쌍대기저곱셈일반적인부호화기의구성은잘알려져있으므로이논문에서따로설명하지는않는다 [1,4,6-8]. 대신직렬승산부호화기에쓰이는쌍대기저곱셈알고리즘을간단히소개한다. 갈루아체 GF( m p ) 의기저는서로선형독립인 m 개의 GF( m p ) 의원소들로이루어진집합을일컫는다. 갈루아체 GF( m p ) 의기저는 m 개의선형독립인원소들로이루어져있는데, 기저는유일하게존재하는것은아니어서하나의갈루아체는복수개의기저를가질수있다. 또, 하나의기저에대해서언제나쌍대기저를구할수있다. α가 GF( m p ) 의원시다항식의한근일때, { α 0,α 1,, α m -1 } 를표준기저라하고다음식을만족하는 { λ 0,λ 1, λ m -1 } 을그표준기저의쌍대기저라한다. Tr ( α j λ k )= { 1, j = k (1) 0, j k 여기서대각합 Tr( ) 은다음식과같다. Tr(β) = β+ β p + +β p m-1 (2) m = -1 β p k GF( m p ) 의모든원소는표준기저의선형조합으로도, 쌍대기저의선형조합으로도나타낼수있으며, 서로변환도가능하다. 쌍대기저곱셈의이점가운데하나는덧셈기만을이용해서곱셈기를구성할수있다는것이다. 일반적으로덧셈기보다곱셈기가훨씬더복잡하므로, 쌍대기저곱셈을이용하면, 상대적으로간단하게곱셈기를구성할수있게된다. 따라서쌍대기저곱셈에바탕을둔직렬승산 RS 부호화기는덧셈기만으로구성할수있다 [3]. 이절에서는쌍대기저곱셈을먼저설명하고, 일반적인부호화기가주어졌을때그로부터직렬승산부호화기의내부계수들을얻는방법을설명한다. GF( m p ) 의두원소인 β와 γ의곱을 σ라고하자. β와 γ는다음식과같이각각표준기저와쌍대기저의선형조합으로나타낼수있다. β = m -1 b α i i, γ = m -1 c λ (3) k k i =0 곱 σ는쌍대기저 { λ k } 의선형조합으로써표현할수있으므로, 다음식에서선형조합의계수 s k 만구하면 σ를얻을수있다. σ = β γ = m -1 i =0 m -1 b ic k α i λ k m = -1 s λ (4) k k 곱셈계수 s k 는대각합 Tr( ) 을이용해서얻을수있다 [6]. s k =Tr ( σ α k )=Tr ( β γ α k ) =Tr ( β (γ α k )). (5) 이를이용해서, (n,k) = (31,27) 인일반적인 RS 부호화기로부터 RS 직렬승산부호화기를얻어보기로하자. 같은방법으로어떤 (n,k) 의값을갖는직렬승산 RS 부호화기도얻을수있다. 그림 1, 2는각각일반적인부호화기와직렬승산부호화기의블록도이다. 그림 1의계수 g i 는문헌에서어렵지않게 찾아볼수있다. (31,27) 의경우에는 g 0 = α 10, g 1 = α, 29 g 2 = α 19, g 3 = α 24 이다 [7,8]. 직렬승산부호화기의 s i 는다음과같이 z i 의선형조합으로써얻을수있다. s 0 = Tr (Z g 0 )=Tr (Z α 10 ) = z 0 +z 4 (6) s 1 = Tr (Z g 1 )=Tr (Z α 29 ) = z 0 +z 3 (7) s 2 = Tr (Z g 2 )=Tr (Z α 19 ) = z 1 +z 2 (8) s 3 = Tr (Z g 3 )=Tr (Z α 24 ) = z 1 +z 2 +z 3 +z 4 (9) 65
한국통신학회논문지 '05-3 Vol.30 No.3C 표 1. 선택된부호들의원시다항식과부호율 m ( n, k) t 원시다항식 k/n 4 (15,13) 1 X 4 +X+1 0.867 5 (31,27) 2 X 5 +X 2 +1 0.871 6 (63,55) 4 X 6 +X+1 0.873 그림 1. (32,27) RS 일반적인부호화기의블록다이어그램 7 (127,111) 8 X 7 +X 3 +1 0.874 8 (255,223) 16 X 8 +X 4 +X 3 +X 2 +1 0.875 그림 3. (31,27) RS 부호화기의 VHDL 블록도 그림 2. (32,27) RS 직렬승산부호화기의블록다이어그램 그림 2에서 Z 는이동레지스터에저장된심벌수열이다. 그림 1의곱셈기가비트단위곱셈기라면, 그림 2의덧셈기는심벌단위덧셈기이다. 곧, 직렬승산부호화기는비트단위곱셈기대신심벌단위덧셈기만을요구하므로구조가매우간단하다고할수있다. Ⅲ. 구현과분석 이절에서는 VHDL로구현된두개의부호화기들에소요된논리게이트수와하나의부호어를부호화하기위해필요한클럭수의변화를부호어길이 n 에따라비교한다. 부호어의길이는 15, 31, 63, 55, 127, 255의경우를생각하고공정한비교를위해모든선택된부호들이유사한부호율 k / n 를갖도록메시지심벌의길이 k 를결정한다. 대체로같은부호율을갖는부호들은비슷한오류정정능력갖는것으로추정된다. 즉, k/ n 는일정하게유지하면서 n 을변화시켜가며논리게이트수와클럭수를비교한다. 표 1은선택된부호각각의부호율, 원시다항식등을보여준다. 여기서 t 는오류정정능력이다. VHDL로구현된 RS 부호화기의블럭도는그림 3 에나와있다. makedata 와 encoding 두개의함수블럭으로구성되어있다. makedata 블럭은블럭으로임의의심벌수열을입력으로제공하고 encoding 블럭은그에맞는패리티심벌수열을생성한다. encoding 블럭은직렬승산부호화기의경우에는 ( 심벌레벨 ) 덧셈기로, 일반적인부호화기의경우에는 ( 비트레벨 ) 곱셈기로이루어져있다. 주목할만한것은기저변환이직렬승산부호화기에서는꼭필요하므로기저변환을위해서는미리저장된변환테이블이항상필요하다는것이다. 직렬승산부호화기에서곱셈은다음과같이수행된다 : 표준기저로표현된입력심벌수열은쌍대기저의선형조합의꼴로변환된다. 이때심벌레벨덧셈기에서곱셈이수행된다. 마지막으로출력은쌍대기저형태이므로표준기저형태로변환해야만한다. 변환된출력은이동레지스터에저장되고이과정을반복하면패리티심벌수열이생성된다. 부호화기는 VHDL을이용하여알테라 FPGA에서구현하였다. 그림 4 는변환테이블을위한논리게이트의숫자가 n 이커질수록급속도로증가하여 n 이커질수록직렬승산부호화기가일반적인부호화기보다더많은논리게이트를필요로하는것을보여준다.( 여기서, 변환테이블을사용하지않은부호화기의논리게이트수는추정치임.) 주목할만한점은변환테이블을제외한직렬승산부호화기의논리게이트수는 n 에상관없이일반적인부호화기보다훨씬적다는것이다. 다시말해, VHDL로구현한직렬승산부호화기는일반적인부호화기보다더많은논리게이트를필요로한다. 이것은일견직렬승산부호화기가덧셈기들로만구성되어더단순할것이라는사실에모순이있는것처럼보인다. 하지만이모순의원인은 n 66
논문 /VHDL 로구현된직렬승산리드솔로몬부호화기의복잡도분석 표 2. 클럭사이클비교 클럭사이클 ( n, k) (15,13) (31,27) (63,55) (127,111) (255,223) Ordinary 15 31 63 127 255 Bitserial 15 31 63 127 255 Ⅳ. 맺음말 그림 4. 일반적인 RS 부호화기와직렬승산 RS 부호화기의게이트수비교 이증가할수록변환테이블의크기가매우급격히증가하고, 결과적으로변환테이블로인한논리게이트수의증가가간단한알고리즘에의한게이트수의감소의효과를넘어서기때문인것이다. 쌍대기저곱셈알고리즘자체가단순한알고리즘임을부정하는것은아닌것이다. 이는단지 VHDL로구현할때에는복잡도문제가변환테이블에의해생길수도있다는것을의미할뿐이다. 그림 5, 6을보면하나의부호어를부호화하기위해걸린시간이두부호화기모두같다는것을알수있다. 표 2는하나의부호어를부호화하기위해요구되는클럭수가 n 이라는것을보여주는데, 이는부호화기들이리얼타임부호화에쓰일수있다는것을의미한다. 이논문에서는쌍대기저변환테이블이 VHDL로구현된 RS 직렬승산부호화기의논리게이트수에미치는영향을정량적으로분석하였다. 변환테이블에필요한논리게이트수는부호어의길이 n 이커질수록매우급격하게증가하기때문에 VHDL에서구현되는직렬승산부호화기는 n 이매우커질때일반적인부호화기보다훨씬복잡해진다. 이는직렬승산부호화기가간단하다고알려져있는일반적인사실과일치하지않는다. 쌍대기저곱셈이매우간단한알고리즘임에는틀림이없지만, 쌍대기저의변환이필수적이라는사실에주목할필요가있고, 이쌍대기저변환이 VHDL 구현에서는상당히많은자원을필요로한다는사실을기억할필요가있다. 단, 변환테이블을참조할필요가없는기저변환을사용한다면직렬승산부호화기가부호어길이 n 에상관없이일반적인부호화기보다항상더적은수의논리게이트로구현될수있다. 따라서, 변환테이블없는기저변환은연구해볼만하며여지껏연구결과가발표되지않은분야이다. 한편, 두부호화기들의부호화속도는같다는것을보였다. 참고문헌 그림 5. 일반적인 (7,3) RS 부호화기의구현결과 그림 6. 직렬승산 (7,3) RS 부호화기의구현결과 [1] I.S. Reed and G. Solomon, "Polynomial codes over certain finite field", J. Soc. Ind. Applied Math., Vol.8, pp. 300-304, 1960. [2] I.S. Hus, T.K. Truong, L.J. Deutsch, and I.S. Reed, "A comparison of VLSI architecture of finite field multipliers using dual, normal, or standard bases", IEEE Trans. Comput., vol. 37, no. 6, pp. 735-739, Jun. 1988. [3] E. Berlekamp, "Bit-serial Reed-Solomon encoders", IEEE Trans. Inf. Theory, vol. 28, no. 6, pp. 869-874, Nov. 1982. [4] 이만영, BCH 부호와 Reed-Solomon 부호, 민 67
한국통신학회논문지 '05-3 Vol.30 No.3C 음사, 1990. [5] R. Lidl, Finite Field, Addison Wesley, 1983. [6] R.E. Blahut, Algebraic Codes for Data Transmission, Cambridge University Press, 2003. [7] S. Bernard, Digital Communications, Prentice- Hall, 2001. [8] S. Lin and D.J. Costello, Error Control Coding, 2nd Ed., Prentice-Hall, 2002. 백승훈 (Seung hun Back) 학생회원 2001년 9월 세종대학교입학 2001년 9월 ~ 현재 세종대학교정 보통신공학과 (2005년 8월졸 업예정 ) < 관심분야 > 디지털신호처리, 채 널코딩, 신호검파이론 배진수 (Jin soo Bae) 종신회원 1990년 2월경기과학고등학교조기졸업 ( 우등 ) 1993년 2월한국과학기술원전기및전자공학과공학사 ( 조기졸업, 최우등 ) 1995년 2월한국과학기술원전기및전자공학과공학석사 1998년 2월한국과학기술원전기및전자공학과공학박사 1997년 1월~1997년 12월동경대학객원연구원 1998년 1월~1998년 10월엑센츄어컨설턴트 1998년 11월~1999년 12월일본모토로라연구원 2000년 3월~ 현재 : 세종대학교정보통신공학과전임강사 / 조교수, 한국통신학회종신회원 ; IEEE 준석학회원 < 관심분야 > 신호처리이론, 신호검파이론 송익호 (Iick ho Song) 종신회원 1982년 2월 서울대학교전자공학과공학사 ( 준최우 등 ) 1984년 2월 서울대학교전자공학과공학석사 1985년 8월 펜실베니아대학교전기공학과공학석사 1987년 3월 ~1998년 2월 벨통신연구소연구원 1988년 3월 ~ 현재 한국과학기술원전자전산학과조 교수, 부교수, 교수 1995년 1월 ~ 현재 한국통신학회논문지편집위원 1991년 11월, 1996년 11월 한국통신학회학술상받음 1993년 11월 한국음향학회우수연구상받음 1998년 11월 한국통신학회 LG학술상받음 1999년 11월 대한전자공학회해동논문상받음 2000년 3월 젊은과학자상받음 2000년 11월 한국통신학회모토롤라학술상받음대 한전자공학회, 한국음향학회, 한국통신학회종신회 원 ; IEE 석학회원 ; IEEE 준석학회원 < 관심분야 > 통계학적신호처리와통신이론, 신호검파 와추정, 이동통신 68