DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

명민 당
7 years ago
Views:

1 2005 년 7 월전자공학회논문지제 42 권 SD 제 7 호 27 논문 SD-7-5 파이프라인재귀적인기술을이용한면적효율적인 Reed-Solomon 복호기의설계 (Design of an Area-Efficient Reed-Solomon Decoder using Pipelined Recursive Technique) 이한호 * (Hanho Lee ) 요 약 본논문은무선및초고속광통신등다양한통신시스템에서사용되는고속 Reed-Solomon (RS) 복호기의하드웨어면적을줄인새로운구조를소개한다. 특히 folding 기술을이용하여높은처리율 (throughput) 과적은하드웨어복잡도 (hardware complexity) 를가지고있는새로운 PrME (Pipelined recursive Modified Euclidean) 구조를제안한다. 제안된 PrME 구조는일반적으로사용되는 systolic-array 그리고완전한병렬 (fully-parallel) 구조와비교하여하드웨어복잡도를약 80% 정도줄일수있다. 제안된 RS 복호기는 1.2 V 의공급전압과 μm CMOS 기술을사용하여설계하고구현하였는데, 총 24,600 개의게이트수, 5-Gbit/s 의데이터처리율과클락주파수 625 MHz 에서동작함을보여준다. 제안된면적효율적인 PrME 구조에기반한 RS 복호기는초고속광통신뿐만아니라무선통신을위한차세대 FEC 구조등에바로적용될수있을것이다. Abstract This paper presents an area-efficient architecture to implement the high-speed Reed-Solomon(RS) decoder, which is used in a variety of communication systems such as wireless and very high-speed optical communications. We present the new pipelined-recursive Modified Euclidean(PrME) architecture to achieve high-throughput rate and reducing hardware-complexity using folding technique. The proposed pipelined recursive architecture can reduce the hardware complexity about 80% compared to the conventional systolic-array and fully-parallel architecture. The proposed RS decoder has been designed and implemented with the μm CMOS technology in a supply voltage of 1.2 V. The result show that total number of gate is 393 K and it has a data processing rate of 5 Gbits/s at clock frequency of 625 MHz. The proposed area-efficient architecture can be readily applied to the next generation FEC devices for high-speed optical communications as well as wireless communications. Keywords: error correction, area-efficient, Reed-Solomon coding, pipelined, recursive. Ⅰ. 서론 리드솔로몬 (Reed-Solomon (RS)) 코드는마그네틱, * 정회원, 인하대학교정보통신공학부 (School of Information & Communication Engineering, Inha University) 본연구는대학 IT연구센터 ( 인하 UWB-ITRC) 육성지원사업의연구결과로수행되었음. 접수일자 : 2005년3월16일, 수정완료일 : 2005년7월4일 광저장매체, 유선및위성통신등다양한응용분야에널리쓰이는 Forward Error Correction (FEC) 기술이다. 8 바이트오류정정 (error correction) RS(255,239) 코드는해저광섬유시스템을위해국제통신연합 (ITU) 에의해채택되었다. [1] 현재가장일반적으로사용되는 RS 복호기 (decoder) 구조는오류 를감지하고정정하는세개의주요한부분으로구성되어있다. 첫번째부분은 Syndrome Computation(SC) 블록이다. SC블록에서 (465)

2 28 파이프라인재귀적인기술을이용한면적효율적인 Reed-Solomon 복호기의설계이한호 는신드롬다항식 (syndrome polynomial) 를발생시키고, 수신된코드워드 (code word) 의오류패턴을표현한다. 다항식 는 RS 복호기의두번째부분인 Key-Equation Solver(KES) 블록에서사용되어진다. KES블록에서는키등식 (key equation) 을해결하기위해 Euclidean 알고리즘 (EA), modified Euclidean 알고리즘 (MEA), 또는 Berlekamp-Massey 알고리즘 (BMA) 등이오류위치다항식 (error-locator polynomial) 와오류값다항식 (error-value polynomial) 을위하여사용될수있다. [2] 와 의두다항식은 Chien Search 그리고 Forney 알고리즘을이용하여오류의위치에대응하는오류들의크기값을구하기위하여사용된다. 이블록의출력은복호기로부터읽혀져나온오류정정되어수신된코드워드이다. 추가로복호기가오류를감지하고정정하는과정을실행하는동안 FIFO 메모리가버퍼 (buffer) 로사용된다. FIFO 메모리의깊이 (depth) 는복호기의총지연성 (latency) 과관련이있다. 광통신네트워크시스템구축을위한초고속데이터전송기술은높은데이터율을얻기위한요구와맞물려초고속 FEC 구조의구현을필요로하게되었다. Dense Wavelength Division Multiplexing (DWDM) 의출현과함께광전송시스템은지난십년간급속도로발전되어왔으며 8바이트오류정정능력에기인한 RS(255,239) 코드가고속 (40-Gbits/s 이상 ) 광전송시스템에일반적으로사용되고있다. 그러나광전송시스템이급속도로발전함에따라 40-Gbits/s 이상의고속데이터전송율을필요로하게되었고, 이에따라하드웨어복잡도와전력소모가매우큰현존하는대부분의 RS복호기는시스템레벨통합의어려움을가져왔다. 본논문에서는그림 1에서보여지는바와같이하드웨어복잡도와클락주파수가상당히향상된 Pipelined recursive ME(PrME) 구조에기인한면적효율성과고속처리를위한 RS(255,239) 복호기의종합적인구조를제시한다. Ⅱ. Reed-Solomon 복호기구조 1. Syndrome Computation 블록 와 를각각코드워드다항식그리고수신된다항식이라고두자. 전송된다항식은전송도중채 그림 1. PrME구조를이용한 RS 복호기 Fig. 1. Reed-Solomon decoder using PrME architecture. 널잡음 (channel noise) 에의해손상되어질수있다. 그러므로수신된다항식은다음과같이표현되어진다. (1) 이식에서 는오류다항식이다. 복호 (decoding) 알고리즘의첫번째단계는정정가능한오류들을정정할수있는 2t syndrome, ( ) 를계산하는것이다. (t는 RS 코드에의해정정될수있는최대개수의오류 ) 만약모든 2t syndrome, ( ) 가 0이라는것은오류가발생하지않았다는것이며수신된다항식 가 로서유효한코드워드라는것을의미한다. 신드롬다항식 는다음과같이정의될수있다., (2) 여기서 는원시다항식 (primitive polynomial), t=8, 의근 (root) 이고 에서의원시원소 (primitive element) 이다. RS(255,239) 코드에서 는가능한오류위치를의미한다. 그림 2에보여진 syndrome computation(sc) 블록은잡음이있는채널을통해전송된심벌 (Symbol) 들을입력으로받아들이고, 이심벌값들을다항식계수 (coefficient) 로간주한다. 데이터블록에포함된심벌들이선택된 RS 코드의데이터블록에대하여유효한코 (466)

3 2005 년 7 월전자공학회논문지제 42 권 SD 제 7 호 29 S i-1 R n D 0 1 D S i S3 S4 S2 S5 S1 S6 S0 S7 0 전력소모를줄이기위하여 ME 구조의하드웨어복잡도를최소화하는것이다. 작은하드웨어면적을가지고있는 KES블록을설계하기위하여, folding 기술을이용 α i+1 S11 S12 S10 S13 S9 S14 S8 S15 R n S 0, S 1,...,S 14, S 15 한 PrME구조를이용하여하드웨어복잡도를줄이고클락주파수를향상시킬수있다. 제안한 PrME 구조는 Ⅲ장에서자세하게설명하고자한다. (a) (b) 그림 2. (a) 신드롬셀, (b) 신드롬연산블록 Fig. 2. (a) Syndrome cell, (b) Syndrome computation block. 드워드를형성하고있는지결정한다. 이것은 2t 신드롬값들에대한다항식을평가해서그값이 0인지아닌지감지한다. ( 즉감지된값이 0이면데이터블록이코드워드이고 0이아니면코드워드가아니다 ). 코드워드가아닌블록은채널잡음에의하여오류가발생한것이다. 그림 2(a) 에서보여지는바와같이한부분의신드롬은각사이클마다 와곱해지고수신된심벌과누적된다. 그림 2(b) 는 16개의신드롬셀 (syndrome cell) 들로구성된 SC블록을보여준다. 이블록은 n개의심벌구간안에서신드롬들이계산되어질수있도록한다. 신드롬심벌들 는직렬로 KES 블록으로 3. Chien Search, Forney 알고리즘및오류정정블록 ME알고리즘이수행된후, 오류위치다항식과오류값다항식이 double buffered 직렬-병렬 (serial-to-parallel) converter로전송된다. 이값들은 Chien Search 알고리즘블록에전달되고, 여기서오류위치다항식의근이계산된다. Forney 알고리즘블록과 Chien Search 알고리즘은병렬로동작하고각각의오류위치에대응하는오류들의크기를계산한다. 복호과정의마지막단계는오류들을정정하기위하여이진 XOR 연산을통해 FIFO buffered 입력코드워드에오류값들을합하는것이다. 에대한 degree t차오류위치다항식이,, 에의하여정의된다. 그러면이런다항 출력된다. 2. Key Equation Solver 블록신드롬다항식 는 KES블록에서키등식 를계산하기위하여사용된다. 이등식을풀기위해서오류위치다항식 와오류값다항식 를계산 한다. RS 복호에서의 KES 블록은 EA, ME 또는 BM 알고리즘들을이용하여구현할수있으며, division-free ME 그리고고속 ME 구조들이각각제안되었다. [3][5] 일반적인 ME 구조는 2t ( 정정가능한최대오류의 2 배수 ) 의 Processing Elements(PEs) 로구성되어있고 systolic-array 구조로연결되어있다. 일반적인 systolic-array ME구조의하드웨어크기는총 RS 복호기크기의약 60% 를차지한다. [3][5] 그러므로 RS 복호기설계에있어서중요한도전은 critical path delay와총 그림 3. (a) Chien search 셀, (b) Chien search 블록, (c) Forney 알고리즘및에러정정블록 Fig. 3. (a) Chien search cell, (b) Chien search block, (c) Forney algorithm and error correction block. (467)

4 30 파이프라인재귀적인기술을이용한면적효율적인 Reed-Solomon 복호기의설계이한호 식의근을구하는것은 RS 복호기의광범위한연산에의하여이루어진다. Chien Search 알고리즘은 상의 t차오류위치다항식 (t는정정가능한최대오류의 2배수 ) 의근을구하는데사용될수있다. 그러나 Chien Search 알고리즘은각각계수 와 의거듭제곱과의 곱셈연산을필요로한다 ( 는더이상약분될수없는 상의 t차다항식의근 ). 오류위치와오류값을계산하기위한 Chien Search 알고리즘과 Forney 알고리즘에대한설명은논문 [5] 에잘설명되어있다. 그림 3(b) 는 8개의 Chien Search 셀로구성된 Chien Search 블록의블록도를보여주고있다. Finite-field 덧셈기 (adder) 는그림 3(b) 에서보여지는바와같이두개의 Chien Search 셀의합의결과를다음번덧셈기로보낸다. 그림 3(c) 는 Forney 알고리즘과오류정정블록을보여주고있고여기서오류값을구한뒤심벌들을정정한다. Galois-field의나눗셈에대해서는제수 (divisor) 의역원 (inverse element) 이유도된후파이프라인 fully-parallel 곱셈기에의하여피제수 (dividend) 의원소와곱해진다. 에서의 non-zero 원소의역계산을위한직접적인방법은 field 원소들의역수를저장할수있는 8비트의 255워드들로이루어진간단한 look-up 테이블을사용하는것이다. 결과적으로 look-up 테이블은 static ROM에의하여실현되고, 파이프라인된곱셈기보다도더적은 path delay를가지고있다. 4. FIFO 메모리 Buffer 및 Control Logic 각각의오류값들이계산될때, 이에대응되는수신된심벌이 FIFO메모리로부터호출되며, FIFO 메모리는복호과정동안의완충역할을한다. 각각의오류값은정정된심벌을만들기위해단순히수신된심벌에합해진다. 오류가발생하지않은위치에서오류값들은 0이되므로합해져도이위치에서수신된다항식은바뀌지않는다. RS 복호기로수신된데이터들은연속적으로들어오므로제어기 (controller) 는각복호과정을위한제어신호를발생시키는것이필요하다. 제어기시스템의설계는주제어기 (master controller) 로전달되기위한특수한신호변경규약을갖는각각의부제어기 (local slave controller) 를구현함으로써이루어진다. 그림 4. Systolic-array ME 구조를사용한 RS 복호기의 타이밍도 Fig4. 4. Timing chart of RS decoder usign the systolic-array ME architecture. III. Pipelined Recursive Modified Euclidean 구조 이번장에서는면적효율성및고속처리 KES블록의구현을위한 folding 방법을이용한 pipelined recursive modified Euclidean(PrME) 구조가소개된다. 기존의 systolic-array ME 구조는 2t의처리요소들 (PEs) 로구성되어있고 systolic-array 구조로연결되어있다. [3]-[5] 이와같은 2t PEs의 systolic-array 구조는오류위치다항식과오류값다항식을계산하고, ME 알고리즘을연속적으로실행한다. ME알고리즘의 systolic-array 구조는 2t 주기의지연성을가지고있다. 그림 4는 systolic-array ME 구조를가지고있는 RS 복호기의타이밍도 (timing chart) 를보여주고있다. 그러나이방법은고속연산에서매우큰하드웨어비용을요구하므로향후공간비용 (space cost) 을대신한시간주기 (time cycle) 를이용한면적효율성구조를제안한다. systolic-array ME 구조에서한개의 PE를규칙적으로 16번사용하면이상적으로중첩된키등식을해결할수있는데이구조는단지 1/16의하드웨어비용만을필요로한다. 1. Modified Euclidean Algorithm ME 알고리즘은키등식 을계산함으로써오류위치다항식 와오류값다항식 을구하기위하여사용된다. 알고리즘을요약하면다음과같다. Input: S(x), x2t Initialization: (468)

5 2005 년 7 월전자공학회논문지제 42 권 SD 제 7 호 31 그림 5. 파이프라인재귀적인 modified Euclidean (PrME) architecture. Fig. 5. Pipelined recursive modified Euclidean (PrME) architecture. R 0 (x) = x 2t, Q 0 (x) = S(x), L 0 (x) = 0, U 0 (x) = 1; deg(r 0 (x)) = 2t, deg(q 0 (x)) = 2t 1 l 0 = deg(r 0 (x)) - deg(q 0 (x)); Index 'i' is initialized to 0; Index 'Step' is initialized to 1; Start Algorithm: while (Step 2t) do begin Step Step + 1 i i + 1; a i-1 leading coefficient of R i-1 (x) b i-1 leading coefficient of Q i-1 (x) if (deg(r i (x)) < t) begin R i (x) = R i (x); Q i (x) = Q i (x); L i (x) = L i (x); U i (x) = U i (x); Skip the following statements & stop the algorithm. end if (l i-1 0) begin R i (x) = [b i-1 R i-1 (x)] x li-1 [a i-1 Q i-1 (x)]; (1a) Q i (x) = Q i-1 (x); (2a) L i (x) = [b i-1 L i-1 (x)] x li-1 [a i-1 U i-1 (x)]; (3a) U i (x) = U i-1 (x); (4a) end else begin R i (x) = [a i-1 Q i-1 (x)] x li-1 [b i-1 R i-1 (x)]; (1b) Q i (x) = R i-1 (x); (2b) L i (x) = [a i-1 U i-1 (x)] x li-1 [b i-1 L i-1 (x)]; (3b) U i (x) = L i-1 (x); (4b) end l i-1 deg(r i-1 (x)) deg(q i-1 (x)); (5) end Output: (x), (x) (469)

6 32 파이프라인재귀적인기술을이용한면적효율적인 Reed-Solomon 복호기의설계이한호 i 번째반복에서 과 는 와 의각각의계수가되고, 알고리즘은, ( 은다항식의차수 ) 일때멈추게된다. 2. Pipelined Recursive Modified Euclidean 구조 Finite-field 원소의곱셈연산은 RS 복호기의 VLSI구현에서매우중요한역할을한다. 칩의복잡도와연산시간은 finite-field 곱셈기를어떻게구현하는가에많이의존한다. PrME 구조의구현에쓰이는 상의파이프라인 fully-parallel 곱셈기에대한설명은논문 [5] 에잘설명되어있으며, 이곱셈기구조는 critical path delay의상당한감소를제공한다. ME 알고리즘에서하나의신드롬다항식이하나의코드워드만큼의시간차를가지고계산되며, 그결과상당한부분의 systolic-array가유휴상태에있게된다. 이러한사실은데이터처리율의감소없이좀더효율적인설계가가능하다는것을의미한다. 그림 5는제안된 PrME 구조의블록도를보여주고있으며, pipelined Degree Computation (DC) unit, Polynomial Arithmetic (PA) unit, Parallel Degree Dection (PDD) unit 그리고 Shift-Registers(SRs) 들이재귀적인반복 (recursive loop) 으로연결되어있다. 이러한 PrME구조는오류위치다항식과오류값다항식을계산한다. 가. Degree Computation DC unit은다음의두가지주요기능을수행한다. 첫번째는 5비트비교기 (comparator) 를이용하여 두다항식의차수를비교하는것이다. 여기서등식 1(a,b) 와 2(a,b) 에서의 와, 그리고등식3(a,b) 와 4(a,b) 에서의 와 의다항식들이교환될필요가있는지를결정한다. 그래서제어회로 (control circuit) 는등식 (5) 에서처럼 를계산한다. 만약 이면신호 sw" 는 1 (high) 이되고, 그렇지않으면 0 (low) 가된다. DC unit에서의두번째기능은다음번 ME 연산을위해다항식 와 의차수를계산하는것이다. 이다항식차수값은각반복단계의마지막에등록되고다음반복단계까지 shift-register에상수로저장된다. PrME 구조에서높게파이프라인된한개의 PE가재귀적으로사용되기때문에두개의연 속적인반복사이의의존성을피하기위해서이러한 shift-register의사용은매우중요하다. 나. Polynomial Arithmetic PA unit은 의 finite-field 연산을수행하고각다항식의계수를연속으로 (serial) 생성하고 PA unit에보내진순서대로피드백 (feed-back) 되어입력된다. 첫번째반복에서병렬 -직렬(parallel-serial) converter는신드롬블록과 PrME 구조사이에서신드롬다항식을직렬화하기위해서사용된다. PA unit에서 start" 신호는다항식들의시작을알리기위해서사용된다. 다시말하면, "start" 신호는항상다항식 와 의 leading 계수 와 를정렬한다. ME알고리즘의첫번째단계에서 "start" 신호에의해각다항식의 leading 계수들이적절히유도되는것과같은방법으로, 뿐만아니라 "start" 신호도한 time unit 만큼지연된다. 신호 는 DC unit에서다항식 의유도된계수가 0인지아닌지를나타내기위해서발생된다. PA unit은 finite-field 곱셈과덧셈을처리한다. 하나의 PA unit은등식 (1)-(4) 를계산하기위해서 4 개의파이프라인 Galois-field 곱셈기와두개의 Galois-field 덧셈기그리고 6개의 MUX를가지고있다. ME알고리즘에서첫반복단계에서 는각각 로 는각각 0과 1로초기화된다. PA unit은파이프라인 fully-parallel 곱셈기를사용하고, 클락주파수의두드러진향상을제공하기위해 5 단의파이프라이닝단계 (pipelining stage) 를가지고있다. 각각의재귀적인반복단계를위하여 11단의 shiftregister 가각반복단계의출력된값을저장하기위해사용된다. 그러므로 PrME구조는총 16단의파이프라이닝레지스터 (register) 를 PA unit안에가지고있다. 다. Parallel Degree Detection DC unit에서다항식 또는 의차수는제어신호 에따라각반복단계마다 1씩감소한다. 그래서알고리즘을멈추기위한조건 또는 을만족하는지를감지하기위해각반복단 (470)

7 2005 년 7 월전자공학회논문지제 42 권 SD 제 7 호 33 계마다 stop-flag generation unit은 의현재차수값들을요구한다. PrME구조의각반복단계에서계산되는각다항식차수가다항식의실제차수와분명히다를수있다. 그러므로수신된코드워드의오류의수가 t보다작다면멈추기위한조건이감지되기전까지많은반복단계의초과계산을초래할수있다. 이러한상태는각반복단계에서다항식 또 는 의차수가적어도한번은감소하였다는가정하에 systolic-array ME구조로부터이어받은것이다. 그러나수신된코드워드에서오류의개수가 t보다작다면오류값과오류위치다항식은적은반복단계를거쳐서계산될수있을것이다. Systolic-array ME구조에는 2t PE unit이사용되고있기때문에알고리즘을완료하는데 2t의주기가필요하다. 그러나재귀적으로사용하는단일 PE unit을갖는 PrME 구조인경우에는알고리즘을완료하는데 n주기가걸린다. PrME구조에서전력소모를최소화하기위하여 stop 조건이만족될때알고리즘을멈추고불필요한신호들의 toggle을즉시중지시킴으로써저전력상태로블록을유지시키는것이중요하다. 그러므로현재상태에서두다항식 의차수를확인하기위해병렬로비교해보는것이필요하다. 이런방법을이용하면, 각반복단계의끝에서두다항식중하나의차수가 t이하로떨어지는지즉조건 또는 를만족하는지감지할수있다. 제안된 PDD구조는 stop" 신호를발생시키기위해두다항식 와 의차수를병렬로비교하고감지한다. PDD unit에는중요한네부분이있다. 첫부분에서는 shift-register를이용하여두다항식이직렬에서병렬로전환된다. 각반복단계의끝에서 다항식의차수를계산한 5비트값이 MUX의선택을위한값으로지정된다. 이 MUX들은두다항식 의계수를정렬하는데사용한다. 와 다항식의차수값 5 비트중에서하위 4 비트가 와 다항식의 MUX를지정하기위한값으로사용된다. 일단정렬이되면상위 8개의계수들이 0이아닌값에대하여감지되고이값들은서로비교된다. 만약두다항식의상위 8개의계수들이 0이라면하위8개의계수들이비교되고 stop" 신호가발생한다. stop" 신호는두번째단계를위한 PrME구조의모든레지스터의동기리셋 (reset) 신호로사용되고, 저전력상태의 PA와 DC unit에입력 표 1. KES블록에서의 Critical path delay와 latency의비교 Table 1. Comparison of critcial path delay and latency for KES blocks. Architecture Critical path delay Latenc y Proposed PrME 3T or2 +T xnor2 +T mux +T ff 2n+12 Systolic ME [5] 3T or2 +T xnor2 +T mux +T ff 10t Parallel ME [8] T mult +T add +T ff 2t+2 EA [6] T rom+t and2+2t mult+t add+2t mux2+t ff 2t RiBM [7] T mult+t add+t ff 2t 된다. 다항식 또는 의 차수가 t이하이면 인지조건을검사하고비교한다. 즉 이경우에는오류위치다항식 는 가되고, 오류값다항식 는 가된다. 다시말하면 이면 는, 그리고 는 가된다. 좀더신중한설계는 PDD unit안의 shift-register를중복사용하는대신에 PrME 구조안에이미저장되어있는 shift-register 로부터의값들을사용하여구현하는것이다. 그러므로 PDD unit 를이용하여저전력상태로유지시켜줌으로써저전력소비에있어서더많은이득을얻을수있다. PrME구조에서 critical path는 DC unit내의 5비트비교기에있으므로 로 critical path delay를정의할수있다. 이같은설계는일반적인 systolic-array 구조 [3]-[5] 와병렬 ME구조 [8] 와비교하여훨씬감소된하드웨어복잡도과높은클락주파수의이득을얻을수있다. Ⅳ. 결과및비교 본논문에서제안된 PrME구조를이용한면적효율성및고속처리 RS복호기는 Verilog-HDL로설계하였고, CADENCE NC-Verilog 시뮬레이터 (simulator) 로검증하였다. Verilog-HDL로설계한 RS 복호기의결과는 C 언어로설계한모델과정확히일치하였다. 이런검증단계후에는 SYNOPSYS Design Compiler(DC) 를이용하여적절한 time 및 area constraint와 1.2 V의공급전 (471)

8 34 파이프라인재귀적인기술을이용한면적효율적인 Reed-Solomon 복호기의설계이한호 표 2. KES블록에서의하드웨어복잡도비교 Table 2. Comparison of hardware complexity for KES blocks. Architecture Multipliers Adders D-FFs MUXes Proposed PrME Systolic ME [5] 8t 8t 78t+4 40t+2 Parallel ME [8] 6t+2 3t+1 6t+4 N/A EA [6] 3t+1 4t+1 14t+6 11t+4 RiBM [7] 6t+2 3t+1 6t+2 3t+1 그림 6. PrME 구조를사용한 RS 복호기의타이밍도 Fig. 6. Timing chart of RS decoder using the PrME architecture. 표 3. RS(255,239) 복호기의구현결과 Table 3. Implementation result of RS(255,239) decoders. Design Proosed Systolic Parallel PrME ME [5] ME [8] EA [6] Syndrome 3,000 3,000 10,000 3,000 KES 17, ,500 84,000 44,700 Chien, Forney, Error Total # of Gates Clock Rate(MHz) Latency (Clock cycle) 4,600 4,600 24,000 4,600 24, , ,000 55, (n+(2t) 2 +12) (0.83 μs ) 355 (n+12t+20) (0.57 μs ) 271 (n+16) (1.5 μs ) 287 (n+32) (0.96 μs ) Throughput (Gbit/s) Efficiency Tech.( μm ) 압과 0.13-μm CMOS 기술을이용하여합성 (synthesize) 하고구현하였다. 표 1에서는다양한 KES블록의 critical path delay와지연성 (latency) 를비교한결과를보여주고있다. 제안된 PrME구조는이전의 systolic-array ME구조와비교하여서는거의비슷한 critical path delay를보여주고있고, Euclidean 과 BM구조보다는훨씬감소한 critical path delay를보여주고있다. 표 2에서는다양한 KES블록의하드웨어복잡도를보여주고있다. 일반적으로사용되는 KES블록들과비교한결과본논문에서제안한 PrME구조는단지 4개의 finite-field 곱셈기와 2개의 finite-field 덧셈기, 170 개의 D-FF만이필요하다는것을보여주고있다. 결론 적으로일반적인 ME구조 [5][8], Euclidean [6] 그리고 BM 구조보다는현저히감소한하드웨어복잡도를보여주고있다. 표 3은몇종류의 RS 복호기의게이트수, clock rate, latency, throughput들을비교한결과들을보여주고있다. RS 복호기에서 FIFO 메모리를제외한하드웨어복잡도를비교한결과본논문에서제안한 RS 복호기는이전의 systolic-array ME [5] 및 Euclidean [6] 구조와비교하여각각 20%, 44% 의게이트수만필요로한다는것을보여주고있다. 또한 parallel ME [8] 구조와비교하면제안된 RS 복호기는 20% 의게이트수를필요로한다. 본논문에서제안된 RS 복호기는 625 MHz에서동작하고 0.83 μs의 latency, 5-GBits/s 의처리속도를갖는다. 이비교표들로부터본논문에서제안된 RS 복호기가최근발표된복호기들보다면저과속도를고려한효율성면에서 4-5배정도우수하다것을볼수있다. 그림 6은 PrME구조를이용한 RS 복호기의타이밍도를보여주고있다. Syndrome Computation(SC) 블록은신드롬다항식을계산하기위하여 n클락주기만큼의처리지연후 2t 신드롬들을출력한다. PrME구조는각반복단계마다신드롬들을받아들이고, 출력을피드백 (feed-back) 한다. n주기후에, PrME구조는다항식 와 을출력하고 Chien Search 블록으로병렬로입력된다. 본논문에서제안된 RS 복호기는코드블록을연속적으로생성하는데, 고정된지연 2n+12 클락주기를가지고적절히연산하고결과를출력한다. (472)

9 2005 년 7 월전자공학회논문지제 42 권 SD 제 7 호 35 Ⅴ. 결론본논문에서는면적효율성및고속처리를위하여 folding 방법을이용한면적효율성 PrME구조를제안하고 RS 복호기설계에적용하였다. 파이프라인재귀적인 (pipelined recursive) 구조는단하나의처리요소 (processing element) 를가짐으로써면적효율적인 PrME 구조의구현을가능하게하였다. 제안된 PrME구조는일반적인 systolic-array 및 fully-parallel 구조와비교하여약 80% 정도하드웨어복잡도를줄일수있다. 제안된 RS 복호기는총 24,600개의게이트수, 5-Gbit/s의데이터처리율과클락주파수 625 MHz에서동작하는결과를보여주고있다. 결론으로써본논문에서제안한 RS 복호기는현재까지발표된복호기중가장높은면적효율성을가지고있는것중에하나이며, 초고속광통신뿐아니라무선통신장비를위한차세대 FEC 장치등에바로적용할수있다. Trans. on VLSI Systems, Vol 9, No.5, pp , Oct [8] L. Song, M-L. Yu and M. S. Shaffer, 10 and 40-Gb/s Forward Error Correction Devices for Optical Communications, IEEE Journal of Solid-State Circuits, Vol. 37, No. 11, pp , Nov 참고문헌 [1] Forward Error Correction for Submarine System Telecommunication Standardization Section, International Telecom. Union, ITU-T Recommendation G.975, Oct [2] S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall, [3] H. M. Shao, T. K. Truong, L. J. Deutsch, J. H. Yuen and I. S. Reed, A VLSI Design of Pipeline Reed-Solomon Decoder, IEEE Trans. on Computers, Vol. C-34, No.5, pp , May [4] W. Wilhelm, A New Scalable VLSI Architecture for Reed-Solomon Decoders IEEE Jour. of Solid-state Circuits, Vol34, No.3, Mar [5] H. Lee, High-Speed VLSI Architecture for Parallel Reed-Solomon Decoder, IEEE Trans. on VLSI Systems, Vol. 11, No. 2, pp , April [6] H. Lee, An Area-Efficient Euclidean Algorithm Block for Reed-Solomon Decoder, IEEE computer society Annual Symposium on VLSI, pp , Feb [7] D.V.Sarwate and N. R. Shanbhag, High-Speed Architecture for Reed-Solomon Decoders, IEEE (473)

36 파이프라인재귀적인기술을이용한면적효율적인 Reed-Solomon 복호기의설계이한호 저자소개 이한호 ( 정회원 ) 1993 년충북대학교전자공학과학사졸업. 1996 년 Univ.

10 36 파이프라인재귀적인기술을이용한면적효율적인 Reed-Solomon 복호기의설계이한호 저자소개 이한호 ( 정회원 ) 1993 년충북대학교전자공학과학사졸업 년 Univ. of Minnesota 전기컴퓨터공학석사졸업 년 Univ. of Minnesota 전기컴퓨터공학박사졸업. < 주관심분야 : 통신용 VLSI 설계, SoC 설계 > (474)

<333520B0ADBCBAC1F82D46534DC0BB20C0CCBFEBC7D120BCF6C1A4B5C820C0AFC5ACB8AEB5E520BECBB0EDB8AEC1F220BCB3B0E82E687770>

<333520B0ADBCBAC1F82D46534DC0BB20C0CCBFEBC7D120BCF6C1A4B5C820C0AFC5ACB8AEB5E520BECBB0EDB8AEC1F220BCB3B0E82E687770> 한국산학기술학회논문지 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.