基于欧几里德算法的 Reed-Solomon 码译码算法

需积分: 9 199 浏览量更新于2024-09-05 收藏 98KB PDF 举报

Reed-Solomon 码的 Transform 域解码算法 Reed-Solomon 码是一种广泛应用于数据存储和传输中的错误纠正码。近三十年来，研究人员一直致力于改进 Reed-Solomon 码的解码算法。传统的 Reed-Solomon 码解码算法通常需要计算 error-locator 和 error-evaluator 多项式，然后进行 Chien 搜索和 Forney 算法以确定错误的位置和值。然而，这些步骤都需要复杂的计算和大量的计算资源。本文提出了一种基于欧几里德算法的 Reed-Solomon 码解码算法，该算法可以直接在 Transform 域中计算码字的谱，并无需计算 error-locator 和 error-evaluator 多项式，也不需要进行 Chien 搜索和 Forney 算法。该算法的概念非常简单，且仅在 Transform 域中操作。 Transform 域解码算法的优点在于，它可以减少计算复杂度和计算资源的需求，从而提高解码速度和效率。同时，该算法也可以应用于其他类型的错误纠正码，例如 BCH 码和 LDPC 码等。本文的贡献在于提出了一种新颖的 Reed-Solomon 码解码算法，该算法可以提高解码速度和效率，并减少计算资源的需求。该算法的出现将对数据存储和传输领域产生深远的影响。知识点： 1. Reed-Solomon 码是一种广泛应用于数据存储和传输中的错误纠正码。 2. 传统的 Reed-Solomon 码解码算法通常需要计算 error-locator 和 error-evaluator 多项式，然后进行 Chien 搜索和 Forney 算法。 3. Transform 域解码算法可以直接计算码字的谱，无需计算 error-locator 和 error-evaluator 多项式。 4. Transform 域解码算法可以减少计算复杂度和计算资源的需求，从而提高解码速度和效率。 5. Transform 域解码算法可以应用于其他类型的错误纠正码，例如 BCH 码和 LDPC 码等。关键词：Reed-Solomon 码、Transform 域、解码算法、欧几里德算法、错误纠正码。

P1A-4

A Transform-Domain Decoding Algorithm for Reed-Solomon Codes

Z. H. Cai, J. Z. Hao, S. M. Sun, P. S. Chin and Z. N. Chen

Institute for Infocomm Research, 21 Heng Mui Keng Terrace, Singapore 119613

Abstract –– This paper presents a Reed-Solomon decoding

algorithm based on the Euclidean algorithm. The algorithm is

conceptually simple and operates only in transform domain.

The spectrum of the codeword is directly computed without

the explicit knowledge of error-locator and error-evaluator

polynomials; the Chien search and the Forney algorithm are

not necessary.

Index Terms –– Block Codes, Channel Coding, Decoding,

Reed-Solomon Codes.

I. INTRODUCTION

The decoding algorithm for algebraic codes, including

Reed-Solomon codes, has been investigated for over three

decades [1]. Consider a Reed-Solomon code over GF(q)

with length n, number of information symbols k, and

designed odd distance d, (n=q-1, k, d=q-k). Assume the

number of errors 2/)1( −=≤ dte , the ‘conventional’

approaches take the following steps to decode the received

word

)(xv :

1) Computer the syndromes polynomial S(x),

2) Solve the Berlekamp’s key equation to find the error-

locator polynomial

)(

and error-evaluator polynomial

)(

Ω ,

3) Find the roots of the

)(

, and

4) Find the error values at error locations.

It is well known that the error-locator and error-evaluator

polynomials are related through Berlekamp’s key-equation

)(mod)()()(

xxxSx Ω=Λ

. Usually this equation is solved

by the Berlekamp-Massey algorithm [2] or Euclidean

algorithm [3].

There are other methods to decode RS codes without the

computation of syndromes [4]. The key equation is changed

to a new Welch-Berlekamp key-equation, which is based on

the remainder polynomial. Recently methods that decode

RS codes beyond the error-correcting bound have been

proposed as well [5][6], where the list-decoding of Reed-

Solomon is viewed as a bivariate interpolation problem.

Based on the bivariate interpolation, a interesting RS

decoding algorithm that involves no syndrome calculation

or error value/location evaluation is suggested in [6,

Appendix C] by setting m = 1 and L = 1 in Kötter’s

bivariate interpolation algorithm.

In this paper a conventional decoding algorithm for RS

codes is presented. It is motivated by the approach

suggested by R. E. Blahut [1, Figure 9.3]. It needs the

spectrum of the received senseword to compute partial

Greatest Common Divisor (GCD) based on Euclidean

algorithm. The spectrum of the codeword can be recovered

through a polynomial division. Compared to the bivariate

interpolation approach in [6], it is conceptually simpler. The

advantage of our method is it does not require the codes to

be cyclic and it could be generalized to decode algebraic

geometry codes via Gröbner bases.

The paper is organized as follows. Section II presents the

transform-domain decoding algorithm for Reed-Solomon

codes with fixed generator polynomial offset. A method to

remove the offset constraint on the generator polynomial is

discussed in the section III and the section IV summarizes

the paper.

II. T

HE TRANSFORM-DOMAIN DECODING ALGORITHM

For the time being assume the generator polynomial of

the (n, k, d) RS code is

∏

−

−=

)()(

tnj

xxg

, i.e. the offset

of the generator polynomial is fixed as n-2t. The offset

restriction will be removed later in Section III. Let the

spectrum polynomial of the codeword c(x) be C(x) which

has degree at most k-1. In the following deduction we

assume the error pattern, ),...,,(

110 −

eeee

, has weight

less than or equal to t, i.e., the number of the elements, e, in

the following indices set,

{}

0| ≠=

eiM , (1)

satisfies

tMe ≤= . The received word )(xv satisfies the

following equation

)()()(

+= . (2)

Let the spectrum polynomials of v(x), e(x) be V(x) and

E(x), respectively. Obviously we have

)()()(

+= . (3)

A proof of the algorithm in [1, Figure 9.3] is given as

follows:

635

下载后可阅读完整内容，剩余3页未读，立即下载

Zhaohuibpps

粉丝: 0
资源: 4

基于欧几里德算法的 Reed-Solomon 码译码算法

Reed-Solomon Encoding and Decoding.pdf

rs.c.zip_BERLEKAMP solomon_Berlekamp-Massey_Reed_Reed Solomon_b

An efficient multi-standard QC-LDPC decoder based on the row-layered decoding algorithm

Hard-Information Bit-Reliability Based Decoding Algorithm for Majority-Logic Decodable Nonbinary LDPC Codes

Decoding Reed Solomon Codes using PGZ Algorithm:Decoding Reed Solomon coded BPSK signal using the Peterson Gorenstein Zieler algorithm-matlab开发

sphere-decoding-algorithm.rar_Sphere Decode_sphere-decoding_球形_球

Efficient Sorting Architecture for List-Fast-SSC Decoding of Polar Codes

A depth-dependent derandomized sampling algorithm for lattice decoding

Manchester-Coding---Decoding.rar_MANCHESTER_optisystem_曼彻斯特

matlab的BER代码-LDPC-like-Decoding-of-Polar-Codes:参见论文“极坐标码置信度传播解码的稀疏图”

最新资源