공학석사학위청구논문 광통신용 40Gb/s Forward Error Correction 아키텍처 40Gb/s Forward Error Correction Architecture for Optical Communications 2008 년 2 월 인하대학교대학원 정보통신공학과 이승범
지도교수이한호 이논문을석사학위논문으로제출함
이논문을이승범의석사학위논문으로인정함 2008 년 2 월 주심 부심 위원
국문요약 본논문은 ME 알고리즘의차수연산블록대신에다항식의차수의편차를이용하여제어신호를생성하는 pdcme 알고리즘블록과새로운 16 채널 RS FEC 구조들을제시한다. pdcme 알고리즘블록은차수연산블록을제거하여기존의 ME 알고리즘블록에비해 17% 의하드웨어복잡도를줄일수있다. 기존의직렬 FEC 구조는 4개의신드롬계산블록이 1개의 KES 블록과연결되는 4채널 FEC구조 2개로구성되어있지만새로운 16채널직렬 FEC 구조는 8개의신드롬계산블록이하나의 KES 블록과연결되는 8채널 FEC 구조 2개로구성된다. 4개의 KES 블록을 2개로줄임으로서새로운직렬 FEC 구조는기존의 FEC 구조에비해하드웨어복잡도를약 30% 줄일수있다. 제안된직렬 FEC 구조는 3.3V의공급전압과 0.18-μm CMOS 기술을사용하여구현하였고총 223K개의게이트수와 400MHz의클럭주파수에서 51Gb/s의데이터처리율을가지고동작함을보여준다. 기존의 2-병렬 FEC 구조는 RS(255,239) 에서 255개의코드워드는 2로나눌수없기때문에더미제로심벌이추가되어대역손실을가진다. 제안된 2-병렬 FEC 구조는더미제로심벌이필요없는신드롬계산블록과 Chien Search 블록및 Forney 알고리즘블록을제시한다. 2-병렬 FEC 구조는 Xilinx Virtex4 FPGA에서 180MHz의클럭주파수와 46Gb/s의데이터처리율을가진다. 제안된 FEC 구조들은초고속광통신뿐만아니라무선통신을위한차세대 FEC 구조등에바로적용될수있을것이다. I
Abstract This paper presents pdcme algorithm block, which is generating it s control signal using degree difference of polynomials instead of degree computation block and novel 16 channel FEC architectures. pdcme algorithm block can reduce the hardware complexity about 17% compared to the ME algorithm block by removing degree computation block. The conventional 16-Ch. serial FEC architecture consists of four 4-Ch. serial FEC architectures and each 4-Ch. serial FEC architecture has four syndrome computation blocks and a shared 1 KES block. But the proposed 16-Ch. serial FEC architecture consists of two 8-Ch. serial FEC architecture and each 8-Ch. serial FEC architecture has 8 syndrome computation block and a shared 1 KES block. The novel serial FEC architecture can reduce the hardware complexity about 30% compared to the conventional FEC architecture by using 2 KES block not 4 KES block. The proposed FEC architecture has been designed and implemented with 0.18-μm CMOS technology in a supply voltage of 3.3V. The result shows that the total number of gate is 223K and it has a data processing rate of 51Gb/s at clock frequency of 400MHz. The conventional 2-parallel FEC has bandloss by adding dummy zero symbol because codeword of 255 symbols can t divide by 2. The 16-Ch. 2-parallel FEC architecture presents syndrome computation block, Chien search block and Forney algorithm block without dummy zero symbol. The 16-Ch. 2-parallel FEC architecture has a data processing rate of 46Gb/s at clock frequency of 180MHz in Xilinx Virtex4 FPGA. The proposed architectures can be readily applied to the next generation FEC devices for high-speed optical communications as well as wireless communications. II
목 차 국문요약 I Abstract II 목 차 III 그림목차 V 표목차 VI 1. 서론 1 2. 리드 - 솔로몬코드 3 2.1. 리드 - 솔로몬부호화 4 2.2. 리드 - 솔로몬복호화 5 3. 하드웨어설계 11 3.1. 신드롬계산블록 11 3.2. Chien Search 블록, Forney 알고리즘블록및오류정정블록 13 3.3. Key Equation Solver (KES) 블록 16 4. 정정불가능한블록의감지 27 5. 40Gb/s 급직렬리드 - 솔로몬 FEC 구조 28 5.1 기존의 40Gb/s 급리드 - 솔로몬 FEC 구조 28 5.2. 제안하는 40Gb/s 급리드 - 솔로몬 FEC 구조 28 6. 40Gb/s 급병렬리드 - 솔로몬 FEC 구조 33 6.1. 40Gb/s 급 3- 병렬 FEC 구조 34 6.2. 40Gb/s 급 2- 병렬 FEC 구조 36 7. 결과및비교 41 III
8. 기능검증 43 8.1. 시험환경 43 8.2. 시험절차 44 8.3. 검증 45 9. 결론 47 10. 참고문헌 48 IV
그림목차 그림 1. (a) 신드롬셀, (b) 신드롬다항식을구하는신드롬계산블록. 12 그림 2. (a) 기본셀, (b) Chien Search 블록, (c) Forney 알고리즘및 오류정정블록. 15 그림 3. 차수연산이포함된 (a) Processing Element 블록, (b) KES 블록. 18 그림 4. 제안하는 pdcme 알고리즘을이용한 KES 블록. 20 그림 5. (a) 다항식연산에따른 PE의구조, (b) 지연연산에따른 PE의구조 21 그림 6. (a) 수식 (51), (b) 수식 (52), (c) 수식 (53), (d) 수식 (54) 에대한 서로다른 PE의연산. 25 그림 7. (a) 제어신호생성에대한, (b) stop 신호생성에대한 Finite State Machine (FSM). 25 그림 8. 기존의 40Gb/s 급 RS기반 FEC 구조. 29 그림 9. 8 채널직렬 RS기반 FEC 구조. 30 그림 10. 8채널 RS기반 FEC 구조의타이밍도. 31 그림 11. 8채널 RS기반 FEC칩의다이포토그래프. 31 그림 12. 16채널직렬 RS기반 FEC 구조. 32 그림 13. 4채널 3-병렬 RS기반 FEC 구조. 34 그림 14. (a) 신드롬셀, (b) 신드롬계산블록. 35 그림 15. (a) 오류정정셀, (b) Chien Search 블록, (c) Forney 알고리즘블록 및오류정정블록. 35 그림 17. (a) 신드롬셀, (b) 신드롬계산블록. 37 그림 19. (a) 오류정정셀, (b) Chien Search 블록, (c) Forney 알고리즘블록 및오류정정블록. 39 그림 20. 제안하는 2-병렬오류정정셀의멀티플렉서신호의타이밍차트. 40 그림 21. FPGA 보드테스트환경. 43 그림 22. 시험절차. 44 그림 23. FPGA design flow. 44 그림 24. ModelSim을이용한 8 채널직렬 RS 복호기의시뮬레이션도. 45 그림 25. ChipScope Pro를이용한 8-채널직렬 RS 복호기의시뮬레이션도. 46 V
표목차 표 1. KES 블록비교. 26 표 2. 더미없는신드롬계산블록의입력패턴. 37 표 3. 16 채널 RS 복호기기반 FEC 의구현결과. 42 VI
1. 서론 리드-솔로몬 (Reed-Solomon: RS) 코드는마그네틱, 광저장매체, 유선및위성통신등다양한응용분야에널리쓰이는 Forward Error Correction (FEC) 기술이다. 8 바이트오류정정 (error correction) RS(255,239) 코드는해저광섬유시스템을위해국제통신연합 (ITU) 에의해채택되었다 [1]. 현재가장일반적으로사용되는 RS 복호기 (decoder) 구조는오류를감지하고정정하는세개의주요한부분으로구성되어있다. 첫번째부분은신드롬계산 (Syndrome Computation: SC) 블록이다. 신드롬계산블록에서는신드롬다항식 (Syndrome polynomial) 를발생시키고, 수신된코드워드 (Codeword) 의오류패턴을표현한다. 신드롬다항식 는 RS 복호기의두번째부분인 Key-Equation Solver (KES) 블록에서입력으로사용되어진다. KES 블록에서는키등식 (Key equation) 을해결하기위해유클리디안알고리즘 (Euclidean Algorithm (EA)), 수정유클리디안알고리즘 (modified Euclidean Algorithm (MEA)), 또는벌리캄프-마시알고리즘 (Berlecamp- Massay Algorithm (BMA)) 등이오류위치다항식 (error-locator polynomial) 와오류추정다항식 (error-evaluator polynomial) 을구하기위하여사용될수있다 [2]. 와 의두다항식은 Chien Search 블록과 Forney 알고리즘블록에서오류의위치와오류값을구하기위하여사용된다. 복호기가오류를감지하고정정하는과정을실행하는동안 FIFO 메모리가버퍼 (buffer) 로사용된다. FIFO 메모리의깊이 (depth) 는복호기의총지연성 (latency) 과관련이있고 FIFO 메모리의출력과 Forney 알고리즘블록의출력이 XOR 연산을거쳐오류정정된코드워드가출력이된다. 광통신네트워크시스템구축을위한초고속데이터전송기술은높은데이터율을얻기위한요구와맞물려초고속 FEC 구조의구현을필요로하게되었다. Dense Wavelength Division Multiplexing (DWDM) 의출현과함께광전송시스템은지난십년간급속도로발전되어왔으며 8 바이트오류정정능력에기인한 RS(255,239) 코드가고속 (10Gb/s 이상 ) 광전송시스템에일반적으로사용되고있다. 그러나광전송시스템이급속도로발전함에따라 40Gb/s 이상의고속 - 1 -
데이터전송률을필요로하게되었고, 이에따라하드웨어복잡도와전력소모가매우큰현존하는대부분의 RS 복호기는시스템레벨통합의어려움을가져왔다. 본논문에서는차수의직접적인연산을제거하고다항식의차수의편차를이용하여제어신호를생성하는 pdcme 알고리즘블록과 16 채널직렬 FEC 구조를제시한다. 차수연산블록이제거되어기존의 ME 알고리즘블록에비해하드웨어복잡도가줄어들었고 8개의채널의신드롬계산블록이하나의 KES 블록과연결되는 8 채널 FEC 구조를병렬로연결하여 16 채널직렬 FEC 구조를구현하였다. 또한 2-병렬또는 3-병렬 FEC 구조를살펴보고기존의 2-병렬구조에포함되는더미제로심벌을제거하여대역손실없는 2-병렬 FEC 구조를제안한다. 직렬 FEC 구조, 2-병렬 FEC 구조그리고 3-병렬 FEC 구조의장단점을알아보고시스템의요구사항에따라선택적으로사용할수있는방향을제시한다. - 2 -
2. 리드 - 솔로몬코드 리드-솔로몬부호 (Code) 는 이 2보다큰양의정수일때, 비트열로만든심벌 (Symbol) 로이루어진비2진순환부호 (nonbinary cyclic code) 이다. 비트심벌에대한 RS 부호는다음조건을만족시키는모든 과 값에존재한다 [10]. (1) 여기서 는부호화될데이터심벌의수이고, 은부호화된블록에있는부호심벌의수이다. 대부분의기존 RS 부호는다음과같다. (2) 여기서 는부호의심벌오류정정능력이고, 는패리티심벌의수이다. RS 부호는동일한부호기입력및출력길이를가진어느선형부호보다최소거리가가능한최대가되는부호이다. 비2진부호에서, 두부호어사이의거리는 ( 해밍거리 (Hamming distance) 와마찬가지로 ) 부호어열에서서로다른심벌의수로정의한다. RS 부호의최소거리는다음과같이주어진다. (3) 부호는어느 개나그이하의오류를정정할수있는데, 는다음과같이표현 할수있다. (4) 여기서 는 보다크지않은가장큰정수를뜻한다. 수식 (4) 에의하면 RS 부호의경우, 개의심벌오류를정정하는데 개의패리티심벌만있으면충분하다. 수식 (4) 에의해다음과같은직관적인논리가가능하다. 복호 (decoding) 에는 쓸수있는 개의여유분심벌이있는데그것은정정가능한오류수의두배이다. 각오류에대해하나의여유분심벌은오류의위치를찾는데사용되고, 나머지여유분심벌은그오류의올바른값을찾는데사용된 - 3 -
다고말할수있다. 부호의소거 (erasure) 정정능력은다음과같다. (5) 동시에오류와소거를정정할수있는능력은다음과같은요구조건으로표시할수있다. (6) 여기서 는정정할수있는심벌오류패턴의수이고, 는정정할수있는심벌소거패턴의수이다. RS 부호와같은비2진부호의장점은다음과같은비교를통해알수있다. 2진 부호를보자. 전체 튜플 (Tuple) 공간에는 개의 튜플이있고, 그중 개 ( 즉 튜플의 1/16) 가부호어다. 다음에각심벌이 비트로이루어진비2진 부호를보자. n튜플공간에는모두 개의 튜플이있고, 그중 개 ( 즉, 튜플의1/4096) 가부호어이다. 개의비트로만든비2진심벌을다룰때는, 가능한 튜플중에서아주작은비율 ( 즉 중 ) 만이부호어이다. 이비율은 이증가할수록더욱감소한다. 여기서중요한점은 튜플공간의아주작은비율만이부호어로사용되면, 더큰 이가능하다는것이다 [10]. 어떤선형부호도만약 개의소거심벌이모두패리티심벌의위치에발생한다면 심벌소거패턴을정정할수있다. 그러나 RS 부호는블록내의어떤위치에있는 개의심벌소거집합도정정할수있는획기적인특성을가지고있다. RS 부호는여유분의수에관계없이설계할수있으며, 가장바람직한 RS 부호는높은부호율 ( 적은여유분 ) 을가진다. 2.1. 리드 - 솔로몬부호화 수식 (7) 은파라미터,, 와임의의양의정수 으로 RS 부호를나타 낸가장전형적인형태이다. 여기에반복하면다음과같다. - 4 -
(7) 여기서 는패리티심벌의수이고, 는부호의심벌오류정정능력이 다. RS 부호의생성다항식은다음의형태를취한다. (8) 생성다항식의차수는패리티심벌의수와같다. 생성다항식의차수가 이므로, 다항식의근은정확히 개의연속적인 의거듭제곱이어야한다 [10]. ITU-T G.975에서는 의값을 부터 으로권장하고있고다음과같은형태가된다 [1]. (9) RS 부호는순환부호이므로조직적인 (systematic) 형태의부호화는메시지다항식 에 를곱하고패리티다항식 를더하는형태가된다. 는 를 로나눈나머지이다. (10) (11) 부호화된다항식 는다음과같다. (12) 수식 (10) 의 를 수식 (12) 에 대입하면 부호화된 다항식 는 가되고이는부호화된다항식에 의근을대입하면 0이됨을의미 한다. 2.2. 리드 - 솔로몬복호화 부호화를통해얻은부호어다항식은전송하는동안잡음에의해오염되어 심벌의오류로수신되었다고가정하면오류패턴은다음과같이다항식으로나 - 5 -
타낼수있다. (13) 그러면오염되어수신된부호어다항식 는다음과같이송신부호어다항 식과오류패턴다항식의합으로나타낼수있다. (14) 2.2.1. 신드롬계산 신드롬계산은수신된다항식 가오류에오염되었는지아닌지를판단하고오류에의해오염되었을때오류패턴을찾을수있는값이된다. 신드롬계산은수신된다항식 에 의모든근을대입하는형태로이루어진다. 가합법적인부호어라면 는 가되고 에 로나누어지므로신드롬계산의결과는 0이된다. 신드롬의계산결과가 0이아니면수신된다항식이오류로부터오염되었음을나타낸다. 신드롬 는 개의심벌 로구성되었고신드롬심벌의계산은다음과같이표현할수있다. (15) 에대한신드롬심벌의계산결과는 0 이므로신드롬심벌은다음의형태로 표현할수있다. (16) 채널에서 개의오류가발생하였고 는오류의위치를나타내고 는오류의값을나타낸다고가정하면 는다음과같이표현할수있다. (17) - 6 -
수식 (17) 에서, 이라고하면 는다음과같이표현할수있다. (18) 이때 은오류의위치를나타내고 은오류의값이된다. 2.2.2. 유클리디안알고리즘 신드롬계산을통해구한신드롬다항식을이용하여오류의위치를나타내는오류위치다항식을구하기위해유클리디안알고리즘이이용된다. 유클리디안알고리즘을정리하면다음과같다. [ 정리 1] 상의두다항식 와 가주어졌을때이들의최대공약수 (GCD) 는다음과같은나눗셈을반복적으로수행하여구할수있다. 즉 인관계를만족할때 (19) 으로나머지가 0 일때 는 이다 [9]. [ 증명 ], 라고할때수식 (19) 는 로 표현될수있다. 마지막식에서 는 와 를모두나눌수있고 는 와 항의합으로이루어져있으므로 로나누어진다. 그러므로 는 이되고 가된다. - 7 -
[ 정리 2] 이다. 여기서 와 는 상의다항식이다. [ 증명 ] 정리 1에서 이므로수식 (19) 로부터 라할수있다. 한편 로부터 가되고 가된다. 따라서앞의식들을이용하여 와 를차례로제거해가면 가된다. 정리 1과정리 2를이용하여유클리디안알고리즘은다음과같이요약될수있다. 임의의다항식, 의 GCD를 라하면정리 2에의해다음의관계식을만족한다. (20) 라할때 와 는,, (21) 을초기조건으로하여,, (22) (23) (24) (25) 에서 일때까지반복계산을수행한후그때의 와 가된다. 여기서 는 를 로나눌때의몫이며,, 와의관계는다음을만족한다. (26) - 8 -
이알고리즘의반복계산횟수는모든 에대해 이므로유한하다 [9]. 앞에서기술한유클리디안알고리즘을이용하여신드롬다항식으로부터오류위치다항식 를구하는방법은아래와같다. RS 부호의신드롬값 로부터다음과같은신드롬다항식을정의하자. (27) 수식 (27) 에수식 (18) 을대입하면다음과같다. (28) 오류위치다항식 는오류위치의역수값을근으로가지는다항식이라고정의하면다음과같이표현할수있다. (29) 또한 라고정의하면 (30) 수식 (20) 에 를취하면 가되고, 여기서, 라하고, 라하면수식 (20) 는수 식 (30) 이된다. 가 이고 가 이므로유클리디안알고리 - 9 -
즘에적용하여오류위치다항식을구할수있다. 2.2.3. 오류위치및오류의값검출 유클리디안알고리즘을이용하여오류위치다항식을구하였고오류위치다항식은정의에따라오류위치의역수를근으로가진다. 이근을알면오류위치도알게된다. 그러므로 의유한체 (Galois Field) 모든원소들로검사함으로써그근을구할수있다. RS 부호의첫심벌은 위치에해당하고이위치에서오류가발생했는지확인하기위해 의역수 을 의근으로대입하고,,, 순으로검사한다. 오류의값은오류추정다항식과오류위치다항식의미분다항식으로얻을수있다. 오류위치다항식 의미분다항식 는다음과같이표현할수있다. (31) 와 를이용하여오류값 을구할수있다. (32) - 10 -
3. 하드웨어설계 3.1. 신드롬계산블록 신드롬계산블록은신드롬값 를구하고이를다항식 의형태로출력으로내보내는역할을한다. 수신된코드워드 의계수값들이 1 클럭사이클마다하나씩입력되므로수식 (15) 을수식 (33) 의반복적인형태로변형하고이를이용하여신드롬계산블록을구현할수있다. (33) 16개의신드롬값은수신된다항식 에대입되는입력 의차수만다르기때문에신드롬값을구하는그림 1(a) 의신드롬셀블록은같은구조가된다. 먼저수신된다항식 의최고차항의계수 는레지스터 (1) 과레지스터 (2) 의값에관계없이레지스터에저장이되어야하므로멀티플렉서 (3) 의셀렉트 (Select) 신호 은 1이되고레지스터 (1) 에는 가저장이된다. 이후 부터 까지의계수값은클럭사이클마다차례로신드롬블록의입력이되고레지스터 (1) 에저장된값에 를곱한것과입력계수를더하고다시레지스터 (1) 에저장하는반복적인연산이수행된다. 이때 신호는 0이되어야누적된값이레지스터 (1) 에저장이된다. 255 클럭동안연산을수행하면 16개의신드롬셀의레지스터 (1) 에는 가저장이되고멀티플렉서 (4) 의셀렉트신호 에의해서레지스터 (2) 로보내진다. 블록의첫데이터가입력으로들어오는시기와 255클럭동안의연산으로구해진 가레지스터 (2) 로전달되는시기가같기때문에멀티플렉서 (3) 과멀티플렉서 (4) 는같은셀렉트신호를사용한다. 신드롬계산블록은신드롬다항식의최고차항을계수부터순차적으로출력으로내보내기때문에 16개의신드롬셀은그림 1(b) 와같이연결된다. 신드롬셀의레지스터 (2) 는쉬프트레지스터의역할을하며멀티플렉서 (5) 의셀렉트신호 에의해서쉬프트를할지현재값을유지할지를결정한다. 신호가 1이되면신드롬다항식이신드롬계산블록의출력으로나오게된다. - 11 -
(a) 그림 1. (a) 신드롬셀, (b) 신드롬다항식을구하는신드롬계산블록. (b) - 12 -
3.2. Chien Search 블록, Forney 알고리즘블록및오류정정블록 수신된다항식의계수값이 부터입력이된것과마찬가지로오류가정정된후의오류정정된다항식 도높은차수의계수부터출력되어야한다. 에해당하는위치는 로표현되었고오류위치다항식은오류위치의역수를근으로가지기때문에 에오류가발생했는지여부를확인하기위해오류위치다항식의근으로 을대입하여야한다. 그러므로오류위치다항식에는 부터 이차례로대입된다. 오류위치에해당하는오류값을구하기위해수식 (32) 에서보는바와같이오류추정다항식 와오류위치다항식의미분다항식 에도 부터 을차례로대입하여야한다. 오류위치다항식 와오류위치다항식의미분다항식 는각각다음과같이표현될수있다. (34) 에서의연산에서 이므로오류위치다항식의짝수차수의 항은미분후모두 0 이된다. 그러므로오류위치다항식의미분다항식 를다시표현하면다음과같다 (35) 수식 (35) 을이용하여수식 (34) 을다시표현하면다음과같게되고 는 오류값을구할때도사용된다. (36) 오류위치다항식의근은 부터 까지클럭사이클마다 배커지는형 태로대입된다. 항을보면근이 일때 가되고근이 일때 가된다. 즉, 매클럭사이클마다 에 이곱해지는구조가된다. - 13 -
그림 2(a) 의기본셀은오류위치다항식의각항을구하는블록이고각항의차수에따라곱해지는 값만달라진다. 기본셀을차수별로적용하여수식 (36) 을구현한것은그림 2(b) 에나타나있고오류위치의값을구하는 Chien Search 블록이다. Forney 알고리즘블록은오류추정다항식 를 나누는연산을수행하는데 는 Chien Search 블록으로부터입력받고 를구하는블록은오류위치다항식과마찬가지로기본셀을이용하여구현할수있다. Forney 알고리즘블록은나누기연산이포함되어있지만 의역수를구하면나누기를곱하기로구현할수있으므로그림 2(c) 와같이역수를구하는 ROM과곱셈기를이용하였다. 오류위치다항식에서해당위치의오류가발생했는지아닌지여부를그값이 0인지아닌지로판단하고 0이면추정한오류값과 FIFO를거쳐서나온오류가포함된심벌을 XOR연산을통해서오류를정정하고최종출력을얻을수있다. - 14 -
(a) (b) 그림 2. (a) 기본셀, (b) Chien Search 블록, (c) Forney 알고리즘및오류 (c) 정정블록. - 15 -
3.3. Key Equation Solver (KES) 블록 신드롬다항식과유클리디안알고리즘을이용하여오류위치다항식과오류추정다항식을구할수있다. KES 블록은유클리디안알고리즘, 수정유클리디안알고리즘또는벌리캄프-마시알고리즘들을이용하여구현할수있으며, division-free 유클리디안알고리즘과그리고고속유클리디안구조들이각각제안되었다 [3]-[5]. 유클리디안알고리즘은몫 를계산하기위해많은나눗셈이필요하므로나눗셈을구현하기위해 ROM을사용하여야한다. 반면에수정유클리디안알고리즘은두다항식의최고차항의계수를교대로곱함으로써차수를줄여나가는방식이며기존의유클리디안알고리즘에서필요로한나눗셈을제거한형태이다. 3.3.1. 기존의수정유클리디안알고리즘블록 수정유클리디안알고리즘은최고차항을소거하여반복적으로차수를줄이 는방식으로오류위치및오류값다항식을구하기위해수식 (37) 과같이초 기값을정한다. 는앞서언급한신드롬다항식이다.,,, (37) (38) (39) (40) (41) 수식 (38)~(41) 은반복적으로 번수행될,,, 에대해 - 16 -
나타낸것이다. 와 는각각 와 의최고차항의계수이고다항식,,, 의값은다항식, 의차수에따라값이결정된다. 와 는각각다항식, 의차수를나타낸다. 가되면반복연산을멈추게되고그때의 와 가각각오류값다항식과오류위치다항식이된다. (42) (43) 그림 3(a) 는기존의 ME 알고리즘구현한 Processing Element(PE) 블록이며그림 3(b) 와같이 개의 PE 블록들이시스톨릭어레이 (Systolic Array) 방식으로연결되어 번째 PE블록의연산으로오류위치다항식과오류추정다항식을구할수있다. PE의입력,,, 는각다항식의최고차항의계수부터클럭사이클마다차례로들어가고각다항식의최고차항의계수가 PE의입력으로동시에들어갔다면그다항식들의차수는같다고판단한다. 그러므로다항식의차수를같게하기위해서낮은차수의다항식에 를곱하는것은높은차수의다항식을지연 (delay) 시키는방식으로구현할수있다. 수식 (38) 의 를곱하는것도높은차수의다항식을 번반복적으로지연시켜구현한것이다. 수정유클리디안알고리즘은위의수식 (38)~(41) 까지반복적으로연산을하는것이고기존의방식은수식 (42) 의두다항식 와 의차수를계산하고 을구하여수식 (38)~(41) 이바르게연산될수있도록제어신호를만들어주었다. 제어신호는반복연산의종료조건인 에따른정지 ( ) 신호도포함하고있다. 즉, 기존의 ME 알고리즘블록은차수계산에따라제어신호를생성하고제어신호에따라연산을수행하는것이다. - 17 -
(a) 그림 3. 차수연산이포함된 (a) Processing Element 블록, (b) KES 블록. (b) - 18 -
3.3.2. 제안하는 Pipelined Degree Computationless Modified Euclidean (pdcme) 알고리즘블록 수식 (38) 은 의값이정해지면수식 (44) 또는 (45) 의형태가된다. (44) (45) 와 의값을서로바꾸면 과 의값이함께바뀌기때문에수식 (45) 은다시수식 (44) 의형태로표현할수있다. 같은방법으로수식 (39)~(41) 을바꾸면 ME 알고리즘은다음과같이표현될수있다. (46) (47) (48) (49) (50) 수식 (47) 와 (49) 에나타나있는 는기존의 PE와마찬가지로높은차수의다항식을 번반복적으로지연시켜구현한다. 수식 (46)~(50) 를구현한 PE 블록은그림 4에나타나있다. 수식 (47)~(50) 의,,, 를구하는다항식연산은그림 5(a) 에나타나있다. 입력단 C에 를대입하고입력단 D에 를대입하고첫번째클럭사이클에만 신호가 1이면레지스터 (1) 에는 이저장되고레지스터 (2) 에는 이저장된다. 에 를곱한것과 에 를곱한것을더하여 를얻을수있고출력단 C를통해 - 19 -
그림 4. 제안하는 pdcme 알고리즘을이용한 KES 블록. - 20 -
서출력된다. 같은방법으로 를구할수있다. 두다항식의차수를같게하는지연연산은그림 5(b) 과같은구조로구현할수있다. 입력단 C와 E에 를곱할다항식을넣고입력단 D와 F에지연시킬다항식을넣으면입력단 C 의다항식과 1이곱해지고입력단 D의다항식과 0이곱해지므로입력단 C이다항식은그대로출력으로나오지만입력단 D의다항식은 1 클럭사이클만큼지연되므로입력단 C의다항식에 를곱한결과를얻을수있다. 같은방법으로입력단 E의다항식또한 를곱한결과를얻을수있다. (a) 그림 5. (a) 다항식연산에따른 PE 의구조, (b) 지연연산에따른 PE 의구조. (b) - 21 -
pdcme 알고리즘블록은 와 의차수를계산하고비교하는연산없이수정유클리디안알고리즘의연산을수행할수있도록구현한것이다. 하지만 PE 블록에서필요로하는 ` ', ` ', ` ' 제어신호는다항식의차수를기준으로생성된다. pdcme 알고리즘은초기입력이정해져있고입력다항식을알때연산결과의범위를어느정도유추할수있다. 그러므로수식 (42) 의직접적인차수비교연산대신에입력패턴과그결과에따른상대적인차수가감을통해차수비교를할수있다. 즉, 차수의비교연산없이앞서언급한세개의제어신호를생성할수있다. 각 PE의입력은다음의네가지패턴을벗어나지않는다. (51) (52) (53) (54) 의차수는항상 이고 의차수는 이하이므로두입력다항식의차수를같게하는지연연산을줄이기위해 에 를곱한다항식이 와함께 PE1의입력이된다. 의차수가 이하이므로 의차수는 이하가된다. 의차수가 미만일때다항식연산을하기전에지연연산을수행해야하므로 PE1의입력단 C에는 가들어가고입력단 D에는 가들어간다. PE1의스타트 (Start) 신호와동기하여들어오는 C와 D입력의값이 0인지아닌지를관찰하면초기입력다항식과관계하여두입력 - 22 -
다항식 와 의차수가같은지아닌지여부를알수있다. 수식 (51) 의패턴은 는 이고 는 이며 은 0이아니라고가정하고있다. 이경우 PE1의스타트신호와동기하여들어온두입력 C와 D는 0이아니므로 와 의차수를 16( ) 이라고판단할수있고 PE1은그림 6(a) 와같이스왑연산과다항식연산이수행된다. PE1의 D 출력은 1 클럭만큼데이터를지연시키므로 PE1의 D 출력단 ( ) 의다항식의차수는 15가되고 PE1이다항식연산을수행하였으므로 C 출력단 ( ) 의다항식의차수는 15가된다. PE2에서 와 의차수가 15로같으므로스타트신호와동기하여들어온 C와 D의입력값이둘다 0이아니다. PE2는두입력다항식이같은차수이기때문에다항식연산을수행한다. PE2의 D 출력단 ( ) 은 1 클럭만큼지연되지만이경우 의차수가감소되지않고 C 출력단 ( ) 에 를곱하는효과를가진다. 따라서 PE2의 C와 D 출력다항식의차수는 15가된다. 입력패턴에따라 D 출력단의지연은 C 출력단에 를곱하거나 D출력단을 로나누는역할을한다. PE3의두입력다항식의차수는 15 로같지만 에 가곱해진것을알고있기때문에실제 의차수가 보다작다. 그러므로스왑연산이 PE3의다항식연산전에이루어진다. 수식 (52) 의경우에스타트신호와동기하여들어오는 C와 D의입력값중 C의값이 0이므로 의차수가 15이하임을알게된다. 그러므로 PE1은지연연산을수행하여다항식연산이가능한형태로만들어야한다. 그림 6(b) 와같이 PE1은지연연산을수행하기위해 D 출력단을 1 클럭만큼지연시키고이것은 에 를곱하는것과같다. PE1의 C 출력단의다항식의차수는 16 이하이고 PE2의스타트신호와동기하여 C와 D의입력다항식이모두 0이아니라면 C 입력다항식의차수가 16이되고다항식연산을위해스왑연산을먼저수행한다. 수식 (53) 의경우에는 PE1은수식 (51) 와같이동작하지만 C 출력다항식의차수가 14이하가되기때문에 PE2가그림 6(b) PE1과같은연산을수행하여그림 6(c) 와같이된다. 수식 (54) 에서 과 의값이 1인경우의 PE의연산이그림 6(d) 에나타나있 - 23 -
다. 의차수가 16이아니므로 PE1은수식 (52) 의 PE1과같은연산을수행하지만 PE2의출력다항식의차수가같지않으므로 PE3은지연연산을수행하여두다항식의차수를같게한다. 위의네가지패턴에따른 PE의연산은스타트신호와동기하여들어오는 C 와 D의입력값에의존하여선택적으로수행하였다. 그림 7(a) 는 C와 D의입력값이동시에들어오는지아닌지를나타내는 SI (Simultaneously Input) 신호를입력으로하고세가지의 PE 연산을결정하는두개의제어신호 Sw(Swap) 과 Sht(Shift) 를출력으로하는 FSM(Finite State Machine) 을나타낸다. S0 상태 (State) 는초기상태이며 S16 상태는 의최고차항의계수부터연속적으로 8 개의계수가 0일때도달하는상태이므로채널에서오류가발생하지않았음을나타내는상태이다. 오류가 개발생한경우 개의 PE 블록을거친후에오류위치다항식과오류값다항식을얻을수있다. 하지만발생한오류의개수가 개이면 개의 PE 블록의연산후에오류위치다항식과오류값다항식을구하게되고남은 PE 블록은 ME 알고리즘연산을중단하고오류위치다항식과오류값다항식을 PE16의출력으로나오도록쉬프트연산을수행한다. 앞서언급한바와같이 ME 알고리즘의연산수행중에 의차수가 이하이거나 의차수보다작을때연산의종료조건은만족시킨다. 즉, PE의 C보다 E의입력이먼저 0이아닌값이들어오는지여부를관찰하여종료조건을만족하는지아닌지를 신호를통해알수있다. 그림 7(b) 는 신호에대한 FSM이며 신호에의해상태가초기화된다. 초기의상태는 S0 상태이고 ME 알고리즘의연산종료조건이만족되면 S2 상태가된다. 종료조건이만족되면그림 4의 stop 신호가 1이되고 PE의입력은각각 4 클럭만큼의지연후 PE의출력으로나온다. 하지만종료조건이 PE16 이전에만족된경우 C와 E의입력은 2개의 PE 동안 8 클럭이아닌 7 클럭만큼지연되어야 PE16에서의결과값이 Chien Search 블록과 Forney 알고리즘블록으로전달되기때문에, 그림 4에서짝수 PE의레지스터 (2) 는제거된다. 기존의 KES 블록과제안하는 pdcme 알고리즘을비교한것은표 1에나타나있다. 기존의블록과클럭주기는비슷하지만면적이약 17% 줄어든것을볼수있다. - 24 -
(a) (b) (c) 그림 6. (a) 수식 (51), (b) 수식 (52), (c) 수식 (53), (d) 수식 (54) 에대한서로 (d) 다른 PE 의연산. (a) (b) 그림 7. (a) 제어신호생성에대한, (b) stop 신호생성에대한 Finite State Machine (FSM). - 25 -
표 1. KES 블록비교 Design MEA [5] Proposed pdcme (5 stage) Multipliers 8t 8t Adders 8t 4t D-FFs 78t+4 54t Mux 40t+2 20t # of Gates 55,500 46,200 Clock Rat (MHz) 625 660 Critical Path T ff +3T or2 +T xnor2 +T mux2 T ff +T inv +T and2 +3T mux2-26 -
4. 정정불가능한블록의감지 RS(255,239) 복호기는 8개의심벌오류를정정할수있다. 즉, 9개이상의오류가발생한경우복호기는코드워드의오류를정정할수없을뿐만아니라정정과정에서오류가추가되기도한다. 그러므로오류정정이불가능할경우이를알려주는신호가필요하다. 블록의오류의정정가능여부를확인하기위해두가지방법을이용할수있다. 하나는신드롬계산블록을복호기의출력단에추가하여신드롬값이 0인지아닌지를확인하는것이다. 다른하나는 KES 블록의출력인오류위치다항식을관찰하는것이다. 오류가 9개이상일때와 8개일때의 KES 블록의출력으로나오는오류위치다항식의차수는둘다 8이므로실제오류가 8개가발생했는지아닌지를확인하기위해실제근을대입한다. 오류가 8개인경우그근이 8개가나오고그렇지않은경우오류위치다항식의근이 8개미만이거나초과하여나오게된다. 그러므로오류위치다항식에근을대입함으로써정정가능한근의개수와정정가능여부를알수있게된다. 전자의방법은신드롬계산블록을추가하여야하므로면적이증가하는단점이있고정정가능한블록일때정정한오류의수를나타내는블록을추가하여야한다. 후자의방법은오류위치다항식의차수를확인하고오류위치다항식의근의개수를카운트 (count) 하면되므로후자의방법이면적적인측면에서효율을가진다. - 27 -
5. 40Gb/s 급직렬리드 - 솔로몬 FEC 구조 5.1 기존의 40Gb/s 급리드 - 솔로몬 FEC 구조 8 바이트오류정정 (error correction) RS(255,239) 부호는해저광섬유시스템을위해국제통신연합 (ITU) 에의해채택되었다 [1]. 여기서 RS 부호는 의 BER에서대략 5.5dB 네트코딩게인 (net coding gain) 을제공한다. 이는 의입력 BER에대해 의출력 BER를가지는것을의미한다. 특히 RS 부호는연집오류 (burst errors) 를수정할수있으며, 하나의 RS(255, 239) 부호는최대 64비트의오류를정정할수있다. 이것은 16개의채널이인터리빙 (Interleaving) 되는 RS 부호에서는더긴길이의연집오류를정정할수있다는것을보여준다. 16개의채널에서각각의채널이코드워드를생성하고각코드워드의심벌이순차적으로한개씩전송되면 16 채널 RS 부호는최대 1024비트의오류를정정할수있게된다. ITU-T G.975에서이와같이 1024비트의오류를정정할수있는 16 채널 RS 부호를권장하고있다. 1채널 RS 복호기는신드롬계산블록, KES 블록, Chien Search 블록과 Forney 알고리즘블록이연결되어있고 16채널 RS 복호기는 1채널 RS 복호기 16개를병렬로연결하는형태가된다. 하지만 RS 복호기에서 KES 블록이차지하는면적은전체 RS 복호기의약 80% 이므로기존의 40Gb/s 급 RS기반 FEC구조는 4개의신드롬계산블록과 1 개의 KES 블록을연결하고이를다시 4개의 Chien Search 블록, Forney 알고리즘블록과연결하는형태로구현되었다. 그림 8은기존의 40Gb/s 급 RS기반 FEC구조를나타낸다. 5.2. 제안하는 40Gb/s 급리드 - 솔로몬 FEC 구조 제안하는 40Gb/s 급 RS기반 FEC 구조또한기존의것과마찬가지로 16채널로구성되어있지만각채널은 1 클럭사이클에 1개의심벌을처리하는직렬구조로되어있다. 제안하는 FEC 구조에사용된 KES 블록은앞서언급한 pdcme 알고리즘블록으로구성되며 16개의신드롬값을순차적으로받아서 - 28 -
그림 8. 기존의 40Gb/s 급 RS 기반 FEC 구조. 처리하는시스톨릭어레이형태로구성되어있다. 즉, 16개의신드롬계산값이순차적으로 PE1의입력이되고이값이 PE2와 PE3로거쳐가는구조이다. 이구조의장점은출력이다시입력이되는궤한 (Recursive) 구조가아니기때문에중간에플립플롭을추가하여쉽게클럭주파수를높일수있다. 그러나 KES 블록의깊이가 16개의신드롬값보다크기때문에 KES 블록을구성하는 16개의 PE 중동시에입력에대한처리를하는 PE는 4개정도이고나머지는아무런동작을하지않게된다. 수신된다항식 의계수값은차례로신드롬계산블록의입력이되고 RS(255,239) 에서의신드롬계산블록은 255 클럭동안 255 개의계수값을연산하여출력으로 16개의신드롬다항식의값을차례로내보낸다. 즉, KES 블록의 PE들은 16 클럭의연산을위해 255 클럭을기다리는형태가된다. 기존의구조와마찬가지로파이프라인형태의 KES 블록은서로다른입력들을처리하는것이가능하고하나의 PE 블록에서서로다른입력이 2 클럭이상의간격을가지면데이터의충돌없이연산을수행할수있다. 즉, 본논문의 KES 블록은 18 클럭사이클마다새로운신드롬계산블록의입력을처리하며, 하나의 KES 블록이여러개의신드롬계산블록의출력을처리하면 - 29 -
그림 9. 8 채널직렬 RS 기반 FEC 구조. PE가연산을수행하기위해입력을기다리는대기시간을줄일수있다. KES 블록은 18 클럭사이클에하나의신드롬계산블록을처리하므로신드롬계산블록이새출력값을생성하기까지 14개의신드롬계산블록의출력을처리할수있다. 본논문에서그림 9는한개의 KES 블록이 8개의신드롬계산블록의출력을처리하는형태를가진 8채널 RS 복호기를나타낸것이다. 그림 9와같이 8개의신드롬계산블록이한개의 KES 블록을공유함으로써, 기존의 4개의신드롬계산블록이 1개의 KES 블록과연결되는구조와비교하여 17% 의지연성이늘어나는데반해 30% 의면적을줄일수있다. 그림 10에제안하는 8채널 FEC구조의타이밍도가나타나있다. 각각의채널에서신드롬계산블록은동시에연산이이루어지고그결과값은버퍼에저장되었다가차례로 KES 블록의입력으로들어간다. 각채널의신드롬값은 2 클럭사이클이상의간격을가지면서로독립적으로 KES 블록에서연산되므로여러채널의신드롬값이동시에 KES 블록에서처리되며먼저계산된 KES 블록의결과는버퍼에다시저장이되고 8번째채널의 KES 블록의결과가출력이되면동시에 Chien Search 블록과 Forney 알고리즘블록에서연산이되고오류가정정된코드워드가동시에채널로나오게된다. 그림 11은제안한 8채널 RS기반 FEC구조를 0.18-μm CMOS 기술을이용하여합성 (Synthesize) 하고구현한 FEC칩의다이포토그래프이다. 3.3V의공급전압을가지고칩코어사이즈는 1.4 1.4 μm 2 이다. 그림 12 는 8채널 FEC 구조두개를병렬로연결한 16채널 FEC 구조를나타낸다. - 30 -
그림 10. 8 채널 RS 기반 FEC 구조의타이밍도. 그림 11. 8 채널 RS 기반 FEC 칩의다이포토그래프. - 31 -
그림 12. 16 채널직렬 RS 기반 FEC 구조. - 32 -
6. 40Gb/s 급병렬리드 - 솔로몬 FEC 구조 앞서살펴본바와같이직렬 RS기반 FEC 구조는하나의신드롬계산블록이매클럭사이클마다하나의심벌 (1바이트) 를처리하는구조이고 255 클럭이지나면 16개의신드롬값을얻게된다. 반면에병렬구조는하나의신드롬계산블록이매클럭사이클마다처리하는심벌의수가여러개인형태이다. 직렬구조에서크리티컬패스는 KES 블록에존재하고병렬구조로바뀌더라도 KES 블록은변화가없으므로병렬 FEC 구조도 KES 블록이크리티컬패스를가지게된다. N-병렬 FEC 구조는직렬 FEC구조와클럭주기가같다면클럭사이클마다처리하는심벌의수가 N배가되므로전체 FEC의처리율을비약적으로증가시킬수있다. 시스템의요구사항에따라병렬 FEC 구조또한선택적으로사용할수있다. 제안한 8개의신드롬계산블록과 1개의 KES 블록을연결하는직렬 FEC 구조는 KES 블록이신드롬값을처리하고새로운신드롬값을처리하기위해최소 144 클럭사이클의대기시간이필요하다. 왜냐하면하나의신드롬계산블록의결과는 16개의심벌이고서로다른채널의신드롬값은최소 2 클럭사이클의거리를가져야하기때문이다. 그러므로병렬 FEC 구조는 8개의신드롬계산블록과 1개의 KES 블록을연결하는구조를사용할수없다. 데이터처리율이늘어났기때문에신드롬값을구하는데걸리는클럭사이클이줄어들기때문이다. 2-병렬 FEC 구조에서신드롬값을구하는데 128 클럭이소요되고 3-병렬 FEC 구조에서신드롬값을구하는데 85 클럭이소요된다. 2-병렬과 3- 병렬 FEC 구조에서 pdcme 방식의 KES 블록과연결되는신드롬계산블록은각각최대 7개와 4개가되므로따라서 4-병렬이상의 FEC 구조는여러개의신드롬계산블록과 1개의 KES 블록을연결하는것이힘들게된다. 즉, 2-병렬 FEC 구조와 3-병렬 FEC 구조는 4개의신드롬계산블록과 1개의 KES 블록이연결된구조를가진다. 그림 13은 3-병렬 FEC 구조를나타낸다. - 33 -
그림 13. 4 채널 3- 병렬 RS 기반 FEC 구조. 6.1. 40Gb/s 급 3- 병렬 FEC 구조 RS(255,239) 의블록단위가 255이고 255는 3으로나누어지므로 3-병렬구조는대역폭의손실없이구현할수있다. 아래의그림 14은 3-병렬신드롬계산블록이다.,, 를 1 클럭사이클에처리하고,, 를다음클럭사이클에처리하기때문에 85 클럭사이클에하나의블록 (255개의심벌 ) 에대한신드롬다항식을출력으로내보낼수있다. 마찬가지로 Chien Search 블록과 Forney 알고리즘블록도 1 클럭사이클에근의위치,, 에대해연산한다. 그림 14은 3-병렬 FEC 구조에서의신드롬계산블록을나타내고그림 15는 3-병렬 Chien Search 블록과 Forney 알고리즘블록을나타낸다. (a) - 34 -
(b) 그림 14. (a) 신드롬셀, (b) 신드롬계산블록. (a) (b) (c) 그림 15. (a) 오류정정셀, (b) Chien Search 블록, (c) Forney 알고리즘블록 및오류정정블록. - 35 -
(a) (b) 그림 16. 더미제로심벌이포함된 2- 병렬 (a) 신드롬셀, (b) 오류정정셀. 6.2. 40Gb/s 급 2- 병렬 FEC 구조 6.2.1 기존의 2- 병렬 FEC 구조 기존의 2-병렬 FEC 구조는 255 블록단위를처리하기위해더미제로 (dummy zero) 심벌을추가하였다. 255가 2로나누어지지않기때문이다. 그림 16은더미제로심벌이추가된신드롬계산블록과오류정정셀을나타낸다. Chien Search 블록에서는오류위치다항식의근으로 ~ 을차례로대입하는것이외에임의의심벌을근으로대입하는데이값은출력에서무시된다. - 36 -
6.2.2. 제안하는 2- 병렬 FEC 구조 제안하는 2-병렬 FEC 구조는표 2와같은입력패턴을처리한다. 더미제로심불을없애기위해 128 클럭사이클에두개의서로다른블록의심벌이동시에신드롬계산블록으로들어가고 2개의블록을 255 클럭사이클에처리하게된다. 그림 17은제안하는 2-병렬신드롬계산블록이고그림 18은신드롬계산블록의멀티플렉서의제어신호를나타낸다. 표 2. 더미없는신드롬계산블록의입력패턴. clock 1 st 2 nd... 128 th 129 th... 255 th 1 st inputa r 254 r 252... r 0 r 253... r 1 r 254 inputb r 253 r 251... r 254 r 252... r 0 r 253 (a) (b) 그림 17. (a) 신드롬셀, (b) 신드롬계산블록. - 37 -
그림 18. 제안하는 2- 병렬신드롬셀의멀티플렉서신호의타이밍차트. 첫번째클럭사이클에멀티플렉서 (2) 의셀렉트신호가 1이되면서동시에들어오는두입력 는레지스터 (5) 에저장이되고 은레지스터 (4) 에저장이된다. 두번째클럭사이클에레지스터 (4) 에저장된 과 는멀티플렉서 (1) 을지나 와함께 의형태로더해진다. 연산을반복하면 128번째클럭사이클에첫블록에대한신드롬값을얻게되고이때새로운브록의 는레지스터 (4) 에저장이된다. 129번째클럭사이클에멀티플렉서 (3) 의제어신호가 1이되면서레지스터 (4) 에저장된 는 과곱해지고멀티플렉서 (1) 의제어신호가 1이기때문에 는 와더해진다. 연산을반복하면 255번째클럭사이클에두번째블록에대한신드롬값을얻게된다. 신드롬값을얻을때마다멀티플렉서 (7) 의제어신호가 1이되고신드롬값은레지스터 (8) 에저장이되며멀티플렉서 (6) 의제어신호가 1이되면신드롬계산블록의출력으로신드롬값이차례로나가게된다. 그림 19는제안하는 2-병렬 Chien Search 블록, Forney 알고리즘블록과오류정정블록이다. 그림 20은 Chien Search 블록, Forney 알고리즘블록과오류정정블록에들어가는오류정정셀의멀티플렉서제어신호를나타낸것이다. - 38 -
(a) (b) (c) 그림 19. (a) 오류정정셀, (b) Chien Search 블록, (c) Forney 알고리즘블록 및오류정정블록. - 39 -
그림 20. 제안하는 2- 병렬오류정정셀의멀티플렉서신호의타이밍차트. 제안한 2-병렬신드롬계산블록은더미제로심벌없이연산을수행하기위해더미제로심벌을포함하는신드롬계산블록에비해하드웨어복잡도가높아진반면제안한 2-병렬오류정정셀은더미제로심벌을포함하는오류정정셀에비해단지멀티플렉서두개가추가되었다. 첫번째클럭사이클에레지스터에 와 에 과 를근으로대입하여얻은값이저장이된다. 128번째클럭사이클에 과 을근으로대입하여얻은값이레지스터에 저장이되는데멀티플렉서 (3) 의제어신호가 1 이되므로새로얻은 와 에, 즉 을근으로대입하여새로운블록의첫번째심벌에대한오류값을얻게된다. 129번째클럭사이클에멀티플렉서 (2) 의제어신호가 1이므로 129번째클럭사이클부터 255번째클럭사이클까지새로운블록에대한오류값을얻게된다. - 40 -
7. 결과및비교 본논문에서제안된 16채널 40Gb/s 급 RS 복호기와 RS기반 FEC 구조들은 Verilog-HDL로설계하였고 Mentor Model Sim으로검증하였다. Verilog-HDL 로설계한 RS 복호기의결과는 C언어로설계한모델과정확히일치하였다. 이런검증단계후에는 SYNOPSYS Design Compiler(DC) 를이용하여적절한 time 및 area constraint를이용하여합성 (synthesize) 하고구현하였다. 표 3은몇종류의 40Gb/s 급 FEC 구조의게이트수, clock rate, latency, throughput들을비교한결과들을보여주고있다. RS 복호기에서 FIFO 메모리를제외한하드웨어복잡도를비교한결과본논문에서제안한직렬 FEC 구조는병렬복호기보다낮은하드웨어복잡도를가지는것을볼수있다. 본논문에서제안된 RS 복호기들은 4 stage 파이프라인 pdcme 알고리즘블록을사용하였고합성 (Synthesis) 후에 Pre-Simulation을수행하면 400MHz의클럭속도를얻을수있다. 3-병렬구조의 Area efficient ME구조와입력을처리하는방식이다르기때문에직렬구조의신드롬계산블록이 3-병렬구조보다면적을좀더많이차지하지만 3-병렬구조도 pdcme 알고리즘블록을채택하면 3-병렬구조의신드롬계산블록이직렬구조보다높은하드웨어복잡도를가지게된다. 즉 40Gb/s 급 FEC 구조에서제안한직렬 FEC 구조는쉽게 40Gb/s의처리율을가질수있고가장낮은하드웨어복잡도를가진다. 반면에 3-병렬구조가 pdcme 알고리즘블록을채택하면가장높은처리율을가지게된다. 타겟보드 (Target Board) 로 FPGA를사용하는경우 Xilinx Virtex4 FPGA를기준으로 pdcme 알고리즘블록이 300MHz에못미치는클럭속도를가지게되므로병렬구조의 FEC가 40Gb/s 급 FEC로사용된다. 제안한 2-병렬구조는더미제로심벌을처리하기위해하드웨어복잡도가증가하여 3-병렬구조에비해하드웨어복잡도가높아지지만시스템이요구하는입력이 2-병렬구조일때더미심벌의추가없이사용될수있다. - 41 -
표 3. 16채널 RS기반 FEC의구현결과 Design 제안하는직렬 FEC 구조 제안하는 2-병렬 FEC 구조 3-병렬 FEC 구조 [8] Syndrome 48,800 100,800 40,000 KES 80,200 156,000 84,000 (pdcme 4stage) (pdcme 4stage) Chien+EC 100,700 178,000 240,000 Total # of Gates 229,700 434,800 364,000 Clock Rate 400 400 180 112 (MHz) Latency 473 260 260 168 (Clocks) Throughput 51 102 46 43 (Gb/s) Technology 0.18 μm CMOS 0.18 μm CMOS Xilinx Virtex4 FPGA 0.13 μm CMOS - 42 -
8. 기능검증 8.1. 시험환경 구조의기능검증을위하여필요한시험환경인 CAD 툴및시험장비등은다음과같다. - RTL code simulation: Mentor Graphics ModelSim simulator - Synthesys, Place & Route: Xilinx ISE 9.2 - FPGA 보드테스트 : ChipScope Pro - Xilinx Virtex-4 LX100 FPGA evaluation board 그림 21은 Xilinx Virtex-4 LX100 FPGA evaluation board를이용한테스트환경을보여준다. 그림 21. FPGA 보드테스트환경. - 43 -
8.2. 시험절차 그림 22 와같이 RS 부호기와복호기를 C-language로구현하고각각의입출력을텍스트파일로저장한다. 그후 Verilog-HDL로 RS 부호기와복호기를설계하고 ModelSim 시뮬레이터를통해출력을확인하고그출력을텍스트파일로저장한다. C-language로얻은텍스트파일과 ModelSim을통해얻은텍스트파일을비교하여동일한지검증하고, FPGA 구현을위해 Xilinx ISE9.2 툴을이용하여그림 23과같이 Verilog 파일을합성하고비트파일을만든다. C language C language Message RS Encoder Channel Modeling RS Decoder Comparison RS Encoder Comparison RS Decoder Verilog Verilog 그림 22. 시험절차. 그림 23. FPGA design flow. - 44 -
8.3. 검증 8.3.1. ModelSim 을이용한기능검증 16채널 RS 복호기는 8채널복호기 2개를병렬로배열한것이므로그림 24는 8 채널에대한시뮬레이션파형을보여준다. 그림 24는직렬 RS 복호기입출력의일부분을나타낸파형이다. 사각형의값이오류를가진값이고아래의파형에서오류가정정되었다. 그림 24. ModelSim 을이용한 8 채널직렬 RS 복호기의시뮬레이션도. - 45 -
8.3.2. ChipScope Pro 를이용한기능검증 FEC구조들을 Xilinx Virtex4 LX100 테스트보드에구현한후그림 24의시뮬레이션의입력다항식을똑같이적용하여 ChipScope Pro. 를이용하여검증하였다. 그림 25에서 RCode는복호기로수신된다항식을의미하며 CCode는오류정정된다항식을나타낸다. 그림 25. ChipScope Pro 를이용한 8- 채널직렬 RS 복호기의시뮬레이션도. - 46 -
9. 결론 본논문은새로운 16채널 RS기반의 FEC 구조들을제안하였다. 차수연산블록을제거한 pdcme 알고리즘블록은기존의 KES 블록에비해약 17% 정도면적을줄였다. 신드롬계산블록, KES 블록, Chien Search 및오류정정블록에서 KES 블록이차지하는면적이 80% 정도이므로다채널 RS 복호기는여러개의신드롬계산블록이 1 개의 KES 블록을공유하는구조를가졌다. 16 채널 FEC 구조로 40Gb/s 이상의처리율을가지기위해각채널은 312MHz이상의클럭주파수를가져야한다. 즉전체시스템의크리티컬패스를포함하고있는 KES 블록이 312MHz 이상에서동작하여야한다. 기존의 4개의신드롬이 1개의 KES를공유하는 FEC 구조 [5] 는 KES 블록를 5 단계로파이프라인하여 625MHz의클럭주파수를만족하였다. 그러나 KES 블록의하드웨어복잡도는상대적으로커지게되었다. 신드롬계산블록이한번에 3개의심벌을처리하는 16채널, 3-병렬구조는 KES 블록의클럭주파수 112MHz만만족하면 40Gb/s 이상을처리율을가진다 [8]. 그러나이구조는신드롬계산블록과오류정정블록의하드웨어복잡도가커진다. 직렬구조를유지함으로써신드롬계산블록과오류정정블록의하드웨어복잡도는유지시키고 pdcme 알고리즘을이용한저면적 KES 블록, 8개신드롬계산블록과 1개의 KES 블록이공유하는제안된구조는앞서언급한두구조와비교하여면적과데이터처리율의종합적인측면에서좋은성능을보이고있다. 또한제한한 2-병렬 FEC 구조는하드웨어복잡도는증가하지만더미제로심벌을제거함으로써대역폭의손실없이 2-병렬 FEC를이용할수있게된다. 제안된 RS 기반 FEC 구조들은향후초고속광통신뿐만아니라무선통신장비를위한차세대 FEC 장치등에바로적용될수있다. - 47 -
10. 참고문헌 [1] Forward Error Correction for Submarine System Telecommunication Standardization Section, International Telecom. Union, ITU-T Recommendation G.975, Oct. 2000. [2] S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall, 1995. [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.393-403, May.1985. [4] W. Wilhelm, A New Scalable VLSI Architecture for Reed-Solomon Decoders IEEE Jour. of Solid-state Circuits, Vol34, No.3, Mar. 1999. [5] H. Lee, High-Speed VLSI Architecture for Parallel Reed-Solomon Decoder, IEEE Trans. on VLSI Systems, Vol. 11, No. 2, pp. 288-294, April. 2003. [6] H. Lee, An Area-Efficient Euclidean Algorithm Block for Reed-Solomon Decoder, IEEE computer society Annual Symposium on VLSI, pp. 209-210, Feb. 2003. [7] D. V. Sarwate and N. R. Shanbhag, High-Speed Architecture for Reed-Solomon Decoders, IEEE Trans. on VLSI Systems, Vol 9, No.5, pp.641-655, Oct. 2001. [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. 1565-1573, Nov. 2002. [9] 이만영, 부호이론, 희중당, pp. 152-154, 1984. [10] Bernard Sklar, 디지털통신공학 : 기본과응용, 박상규외역, 교보문고, pp. 516-544, 2003. [11] T. K. Matsushima, T. Matsushima, S.Hirasawa, Parallel Encoder and Decoder Architecture for Cyclic Codes, IEICE Trans. on Fundamentals of - 48 -
Electronics, Communications and Computer Sciences, Vol.E79-A, no.9 pp.1313-1323, Sept. 1996. [12] S. Lee, Hanho Lee, J. Shin, J-S. Ko, "A High-Speed Pipelined Degree-Computationless Modified Euclidean Algorithm Architecture for Reed-Solomon Decoders," IEEE International Symposium on Circuits and Systems (ISCAS 2007), pp. 901-904, May 2007. - 49 -