خط مشی دسترسیدرباره ماپشتیبانی آنلاین
ثبت نامثبت نام
راهنماراهنما
فارسی
ورودورود
صفحه اصلیصفحه اصلی
جستجوی مدارک
تمام متن
منابع دیجیتالی
رکورد قبلیرکورد بعدی
Document Type:Latin Dissertation
Language of Document:English
Record Number:52513
Doc. No:TL22467
Call number:‭3258830‬
Main Entry:Jun Ma
Title & Author:Efficient algebraic soft -decision decoding of Reed -Solomon codesJun Ma
College:University of California, San Diego
Date:2007
Degree:Ph.D.
student score:2007
Page No:216
Abstract:Algebraic soft-decision decoding of Reed-Solomon codes delivers promising gain over conventional hard-decision decoding. The major computational steps in algebraic soft-decoding (as well as Sudan-type list-decoding) are bivariate polynomial interpolation and factorization. In this thesis, we present techniques from both algorithmic and VLSI architectural level that greatly reduce the implementation complexity of a soft-decision Reed-Solomon decoder. A divide-and-conquer approach to perform the bivariate polynomial interpolation procedure is discussed in Chapter 3. This method can potentially reduce the interpolation complexity of algebraic soft-decision decoding of Reed-Solomon code. In Chapter 4, a computational technique, based on re-encoding coordinate transformation, is derived that can significantly reduces complexity of bivariate interpolation procedure. With this technique, the original interpolation problem is transformed into another reduced interpolation problem, which could be orders of magnitude smaller than the original one. A rigorous proof is presented to show that the two interpolation problems are equivalent. In addition, an efficient factorization procedure that applies directly to the reduced interpolation problem is given. We apply the re-encoding coordinate transformation technique to the Lee-O'Sullivan interpolation algorithm in Chapter 5. A new basis construction algorithm is developed and it takes into account the additional constraints imposed by the interpolation problem that results upon the re-encoding transformation. The re-encoding coordinate transformation reduces the computational and storage complexity of the Lee-O'Sullivan algorithm by orders of magnitude, and makes it directly comparable to Koetter's algorithm in situations of practical importance. Chapter 6 presents a VLSI design example of the re-encoding coordinate transformation technique introduced in the previous chapter. A fast and optimal algorithm to determine the re-encoding positions and an architecture that enables concurrent processing and eliminates idle time of the various hardware units are proposed. The entire design is synthesized using SMIC's 0.18---μm library to a total area of 0.51mm2. It has a throughput of approximately 500Mbps. A high-speed interpolation architecture is presented in Chapter 7. This novel architecture applies hybrid data format to represent a finite field number, thus breaks the long critical path delay bottleneck associated with existing architectures. The proposed architecture also enables maximum overlap in time between computations at adjacent iterations. It is estimated that the proposed architecture can achieve significantly higher throughput than conventional designs with equivalent or lower hardware complexity. Partial factorization of bivariate polynomial is also an important step of algebraic soft-decision decoding of Reed-Solomon codes, and it contributes to a significant portion of the overall decoding latency. In Chapter 8, a novel architecture based on direct root computation is proposed to greatly reduce the factorization latency. Compared with existing works, not only does our new architecture have a significantly smaller worst-case decoding latency, but it is also more area efficient since the large amount of hardware consumption for routing polynomial coefficients can be completely avoided.
Subject:Applied sciences; Decoding; Reed-Solomon codes; Soft-decision decoding; Electrical engineering; 0544:Electrical engineering
Added Entry:A. Vardy
Added Entry:University of California, San Diego