English  |  正體中文  |  简体中文  |  Items with full text/Total items : 6491/11663
Visitors : 24735018      Online Users : 53
RC Version 3.2 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search

Please use this identifier to cite or link to this item: http://ir.ncue.edu.tw/ir/handle/987654321/16455

Title: 錯誤及擦失更正之步階式里德-所羅門解碼演算法
Step-by-Step Reed-Solomon Decoding Algorithm for Error/Erasure Correcting
Authors: 陳棟洲
Contributors: 電子工程學系
Keywords: Reed-Solomon codes;Step-by-step;Error;Erasure
Date: 2003
Issue Date: 2013-05-06T04:01:27Z
Publisher: 國立交通大學
Abstract: In the step-by-step Reed-Solomon decoding, in order to reduce the computation complexity, speed up the decoding process, and correct errors and erasures, new decoding algorithms and procedures are proposed and investigated in this thesis.
First, we present a new step-by-step RS decoding algorithm for errors-only correcting to reduce the computation complexity of the conventional step-by-step RS decoding algorithm. The step-by-step RS decoding algorithm corrects the errors in terms of the differences between the original syndrome matrices and the temporarily changed syndrome matrices. This idea is based on the fact that the weight of error patterns can be distinguished from each other by using the syndrome matrices. If the weight of the error pattern is reduced, both the error location and the corresponding error value are found. However, the conventional step-by-step decoding algorithm must perform 2m - 1 iterations for each received symbol to detect whether or not every nonzero element of GF(2m) is the possible error value. For decoding each received symbol, we derive and simplify the computation of the determinants of the changed syndrome matrices. Then a new syndrome matrix is developed and defined. Several theorems for the new syndrome matrix are proposed. The new step-by-step decoding algorithm for errors-only correcting can directly determine whether the decoded symbol is an error location or not by detecting the new syndrome matrix. The corresponding error value then can be immediately obtained if the decoded symbol is an error location. Compared with the conventional step-by-step decoding algorithm, the computation complexity can be reduced by a factor of 2m — 1 for Reed-Solomon codes over GF(2m).
Secondly, we propose a fast step-by-step decoding procedure to speed up the decoding process. The fast step-by-step decoding procedure decodes the received symbols in order from rn-1, rn-2, ..., till r0. For decoding each symbol rn-j, we derive several formulas to obtain fast the corresponding syndrome values and syndrome matrices of rn-j from those of rn-j+1. We find directly a probable and unique value of the corresponding error value which is designated as the quasi-error-value. Then the truth of the quasi-error-value is detected and the corresponding error value of rn-j is determined. Based on the fast step-by-step decoding procedure, a pipelined high-speed decoder architecture is presented, too. This pipelined decoder can be operated in a bit rate of several Gbits/sec and thus suitable for the very high speed data transmission systems.
Finally, a step-by-step decoding algorithm for correcting errors and erasures is proposed and investigated. This decoding algorithm decodes the received symbols in the manner of symbol-by-symbol. For decoding each symbol, the corresponding error or erasure value can be directly found. A fast step-by-step decoding procedure for correcting errors and erasures is also proposed. Compared with the standard algebraic decoding, this step-by-step error/erasure decoding algorithm does not need to find the coefficients of the error-locator polynomial, to search the error locations, and to calculate the error evaluator and error/erasure polynomials for obtaining the error and erasure values.
在本論文中,我們針對步階式里德-所羅門解碼演算法,期使能降低解碼演算法之運算複雜度、加快解碼之速度、以及增加對擦失符碼(erased symbol)之更正能力,我們對只作錯誤更正(errors-only correcting)以及同時作錯誤和擦失更正(errors/erasures correcting)提出新的步階式里德-所羅門解碼演算法和解碼程序。首先,我們提出一個新的步階式里德-所羅門錯誤更正解碼演算法,可以降低傳統步階式解碼演算法之運算複雜度。利用癥狀矩陣(syndrome matrices),潛藏在接收字碼中之錯誤符碼的個數可以被得知。步階式解碼演算法便利用原始癥狀矩陣和改變被解碼符碼後之癥狀矩陣間的差異,檢測被改變之字碼中的錯誤符碼個數是否降低,若錯誤符碼個數降低,則被解碼之符碼便是一錯誤符碼,且相對於此錯誤符碼之錯誤值可立即被找到。然而,傳統步階式解碼演算法必須對有限場GF(2m)中的所有非零元素去改變被解碼之符碼值,因而對每一符碼必須做2m — 1次檢測。 因此,我們針對每一符碼作解碼時,推導並簡化癥狀矩陣之行列式值的運算,同時衍生出一新癥狀矩陣。並對此新的癥狀矩陣,提出數個定理。則我們只須檢測此新的癥狀矩陣,便可確知被解碼之符碼是否為一錯誤符碼。且相對於被解碼符碼之錯誤值可直接求得。和傳統步階式解碼演算法比較,新提出之步階式解碼演算法可降低解碼運算複雜度約(2m — 1)倍。接著,我們提出一快速之步階式解碼程序來加快里德-所羅門碼之解碼速度。對於接收到之字碼,依序從第一個接收符碼到最後一個接收符碼,一個符碼一個符碼作解碼。針對每一個符碼作解碼時,我們可直接找到符合該符碼之錯誤值的唯一可能值,我們稱之為準錯誤值。接著只須針對此準錯誤值作一檢測以確定其真實性,便可得到相對於被解碼之符碼的錯誤值。依據此快速步階式解碼程序,我們也同時提出一高速之解碼器架構。此高速解碼器可操作於每秒數十億位元之資料傳輸,因此適合於高速數據傳輸系統中使用。以往,步階式里德-所羅門解碼法從未被探討對擦失(erasures)作更錯。我們根據所提出之步階式里德-所羅門錯誤更正演算法、癥狀值之線性轉換、癥狀矩陣、以及循環碼之特性,提出一可同時作錯誤和擦失更正之步階式里德-所羅門解碼演算法。此解碼法一樣是從第一個接收符碼到最後一個接收符碼,一個符碼一個符碼作解碼。針對每一符碼作解碼時,可直接找出該符碼之錯誤或擦失值。相較於代數解碼演算法,此新提出之演算法不需要計算錯誤位置多項式之係數、不需解錯誤位置多項式以求出錯誤位置、也不需要計算相對於錯誤位置或擦失位置之錯誤值或擦失值。另外,一適合建構高速解碼器之快速解碼程序也同時被提出。
Relation: 博士論文; 國立交通大學電子工程系
Appears in Collections:[電子工程學系] 專書

Files in This Item:

File SizeFormat
2050301311002.pdf64KbAdobe PDF597View/Open

All items in NCUEIR are protected by copyright, with all rights reserved.


DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback