리드-솔로몬 복호기를 위한 저전력 및 저면적 VLSI 구조
Low-Power and Small-Area VLSI Architecture for Reed-Solomon Decoders
- 주제(키워드) Forward Error Correction (FEC) , Reed-Solomon , 리드-솔로몬 복호기
- 발행기관 아주대학교 일반대학원
- 지도교수 선우명훈
- 발행년도 2008
- 학위수여년월 2008. 2
- 학위명 박사
- 학과 및 전공 일반대학원 전자공학과
- 본문언어 영어
초록/요약
This thesis proposes a new RS decoder based on a new simplified Euclid’s algorithm that can satisfy low power and small area. Since the key equation solver block requires the highest hardware complexity among various blocks for the RS decoder, various key equation solver algorithms have been proposed to satisfy low power and complexity. Even though the existing modified Euclid’s (ME) algorithm removes the inversions, that is, computations of inverse elements to find the greatest common divisor, and achieves the regularity, it requires higher hardware complexity compared with the inverse-free Berlekamp-Massey (iBM) algorithm. Therefore, the thesis will propose the new simplified Euclid’s (SE) algorithm for solving the key equation, and thus, the SE algorithm can acheive the lowest hardware complexity among existing key equation solver blocks. The new SE algorithm has two major advantages. The proposed SE algorithm uses new initial conditions, and thus, the highest degree of the new initial conditions becomes 2t ? 1 instead of 2t in the existing ME algorithm. Since the key equation solver block requires the number of basic cells as the highest degree of the initial conditions, the proposed SE algorithm can naturally reduce the number of coefficients, and thus, it requires one less basic cell compared with the existing ME algorithm. The thesis will verify that the new initial conditions and the existing initial conditions mathematically are the same. In addition, the new SE algorithm proposes the new computation method for solving the key equation. Since the existing computation method is performed according to the results of the degree computations and comparisons, it should proceed complex flow. Since the new SE algorithm uses the leading coefficient of the error evaluator polynomial and control signals for solving the key equation instead of the degree comparisons and computations, the thesis reformulates the existing computation method. The new method requires simpler equations than the existing computation method. In addition, the proposed SE algorithm can perform the polynomial computations and the update of the control signal at the same time such as the RiBM algorithm. The new SE algorithm has been verified by C++ simulations. The simulations have been performed for various (n, k, t) RS codes, such as (7, 5, 1), (37, 33, 2), (41, 21, 10), (255, 235, 10), (255, 239, 8), (255, 251, 2), etc. The new SE architecture for the (255, 239, 8) RS code has been modeled by VHDL and it has about 20,166 gates. The implemented RS decoder excluding the FIFO memory consists of 40,136 gates. The total latency for RS decoding is 288 clock cycles. The maximum delay is about 2.67ns, and thus, the maximum operating frequency even with the 0.18μm technology is about 370MHz. Therefore, the implemented RS decoder has the lowest hardware complexity and the shortest latency.
more초록/요약
본 논문은 새로운 단순화된 유클리드 알고리즘 기반 고성능 및 저면적을 만족하는 새로운 리드-솔로몬 복호기를 제한한다. 리드-솔로몬 복호기를 구성하는 다양한 하드웨어 블록 중 키 방정식 연산 블록의 하드웨어 복잡도가 가장 높기 때문에 다양한 키 방정식 연산기에 대한 연구가 진행되어왔다. 키 방정식 연산에 사용되는 여러 알고리즘 가운데 수정 유클리드 알고리즘은 기존 유클리드 알고리즘의 역수 연산을 제거하였으며 규칙적은 하드웨어 구조를 만족시키는 반면 베르캠프-메세이 알고리즘에 비해 높은 하드웨어 복잡도를 갖는다. 따라서 본 논문은 키 방정식 연산을 위한 새로운 단순화된 유클리드 알고리즘을 제안한다. 제안하는 단순화된 유클리드 알고리즘은 기존 키 방정식 알고리즘들에 비해 낮은 하드웨어 복잡도를 달성할 수 있다. 새로운 단순화된 유클리드 알고리즘은 두 가지 큰 장점을 갖는다. 새로운 단순화된 유클리드 알고리즘은 새로운 초기 조건을 사용한다. 새로운 초기 조건의 최고 차수는 2t - 1로서 기존 수정 유클리드 알고리즘 초기 조건의 최고 차수인 2t에 비해 낮다. 따라서 제안하는 단순화된 유클리드 알고리즘의 초기 조건을 구성하는 다항식 계수의 개수는 기존 수정 유클리드 알고리즘에 비해 작고, 그 결과 적은 하드웨어를 사용하여 키 방정식 연산이 가능하다. 새로운 초기 조건과 기존 초기 조건이 동일한 연산 결과를 갖는다는 것은 수식적으로 증명할 수 있다. 또한, 새로운 단순화된 유클리드 알고리즘은 키 방정식 연산을 위해서 새로운 다항식 연산 방식을 사용한다. 기존 수정 유클리드 알고리즘은 다항식의 차수 비교 및 차수 연산 결과를 사용하여 다항식 연산을 수행하였다. 따라서 수정 유클리드 알고리즘의 다항식 연산은 복잡한 수식으로 기술된다. 그러나 새로운 단순화된 유클리드 알고리즘은 다항식 차수 비교 및 차수 연산대신 오류 크기 다항식의 최고차항 계수와 제어 신호를 사용하여 다항식 연산을 수행하는 방식으로 기존 다항식 연산 방식에 비해 단순한 수식으로 기술할 수 있다. 결과적으로 새로운 단순화된 유클리드 알고리즘은 기존 베르캠프-메세이 알고리즘 기반의 RIBM 알고리즘과 같이 다항식 연산 및 제어 신호의 갱신을 동시에 수행하는 구조로서 고속의 키 방정식 연산이 가능하다. 새로운 단순화된 유클리드 알고리즘은 C++ 시뮬레이션을 통해서 검증하였다. (255, 239, 8) RS 코드를 위해 VHDL 언어 및 삼성 0.18um 라이브러리를 사용하여 구현한 제한하는 단순화된 유클리드 구조는 약 20,166 게이트로 구성된다. 또한 구현한 리드-솔로몬 복호기는 FIFO 메모리를 제외하고 약 40,136 게이트로 구성되며, RS 복호를 위해 288 클록을 필요로 한다. 구현한 리드-솔로몬 복호기의 임계 경로는 약 2.67ns 이다. 따라서 구현한 리드-솔로몬 복호기는 낮은 하드웨어 복잡도를 갖는 것은 물론 고속으로 리드-솔로몬 코드의 복호가 가능하다.
more목차
I. Introduction = 1
A. Introduction = 1
B. Key Equation Algorithms = 2
C. Summary of Contributions = 5
D. Outline of Thesis = 7
II. Existing Algorithm for Solving the Key Equation = 8
A. RS Codes = 8
B. RS Decoding Flow = 14
C. Existing Algorithms = 20
1. ME Algorithm = 20
2. RiBM Algorithm = 28
III. New Simplified Euclid's Algorithm = 33
A. My Previous Works = 33
1. DCME Algorithm = 33
2. Enhanced DCME Algorithm = 49
B. New Simplified Euclid's (SE) Algorithm = 55
III. Implementation of RS Decoder Using the New SE Algorithm = 64
A. Implementation of RS Decoder = 64
1. Syndrome Block = 64
2. New SE Architecture = 65
3. Chien Search and Forney's Blocks = 69
B. Performance Comparisons = 70
V. Conclusions and Future Work = 74
A. Conclusions = 74
B. Future Works = 75
1. High-Speed Pipeline Reed-Solomon Decoder = 75
2. Multi-Mode Reed-Solomon Decoder = 76
3. BCH Decoder Using the New SE Algorithm = 76
Bibliography = 77
국문 요약 = 81
