High Speed Versatile Reed-Solomon Decoder for Correcting Errors and Erasures

A new Chien search method for shortened Reed-Solomon （RS） code is proposed, based on this, a versatile RS decoder for correcting both errors and erasures is designed. Compared with the traditional RS decoder, the weighted coefficient of the Chien search method is calculated sequentially through the three pipelined stages of the decoder. And therefore, the computation of the errata locator polynomial and errata evaluator polynomial needs to be modified. The versatile RS decoder with minimum distance 21 has been synthesized in the Xilinx Virtex-Ⅱ series field programmable gate array （FPGA） xe2v1000-5 and is used by coneatenated coding system for satellite communication. Results show that the maximum data processing rate can be up to 1.3 Gbit/s.

Adaptive Hybrid Forward Error Correction Coding Scheme for Video Transmission

This paper proposes an adaptive hybrid forward error correction(AH-FEC)coding scheme for coping with dynamic packet loss events in video and audio transmission.Specifically,the proposed scheme consists of a hybrid Reed-Solomon and low-density parity-check(RS-LDPC)coding system,combined with a Kalman filter-based adaptive algorithm.The hybrid RS-LDPC coding accommodates a wide range of code length requirements,employing RS coding for short codes and LDPC coding for medium-long codes.We delimit the short and medium-length codes by coding performance so that both codes remain in the optimal region.Additionally,a Kalman filter-based adaptive algorithm has been developed to handle dynamic alterations in a packet loss rate.The Kalman filter estimates packet loss rate utilizing observation data and system models,and then we establish the redundancy decision module through receiver feedback.As a result,the lost packets can be perfectly recovered by the receiver based on the redundant packets.Experimental results show that the proposed method enhances the decoding performance significantly under the same redundancy and channel packet loss.

Erasure-Correction-Enhanced Iterative Decoding for LDPC-RS Product Codes

Low-density parity-check(LDPC)codes are widely used due to their significant errorcorrection capability and linear decoding complexity.However,it is not sufficient for LDPC codes to satisfy the ultra low bit error rate(BER)requirement of next-generation ultra-high-speed communications due to the error floor phenomenon.According to the residual error characteristics of LDPC codes,we consider using the high rate Reed-Solomon(RS)codes as the outer codes to construct LDPC-RS product codes to eliminate the error floor and propose the hybrid error-erasure-correction decoding algorithm for the outer code to exploit erasure-correction capability effectively.Furthermore,the overall performance of product codes is improved using iteration between outer and inner codes.Simulation results validate that BER of the product code with the proposed hybrid algorithm is lower than that of the product code with no erasure correction.Compared with other product codes using LDPC codes,the proposed LDPC-RS product code with the same code rate has much better performance and smaller rate loss attributed to the maximum distance separable(MDS)property and significant erasure-correction capability of RS codes.

BILINEAR FORMS AND LINEAR CODES

Abraham Lempel et al made a connection between linear codes and systems of bilinear forms over finite fields. In this correspondence, a new simple proof of a theorem in [1] is presented; in addition, the encoding process and the decoding procedure of RS codes are simplified via circulant matrices. Finally, the results show that the correspondence between bilinear forms and linear codes is not unique.

Multiple-Symbol Interleaved RS Codes and Two-Pass Decoding Algorithm

For communication systems with heavy burst noise, an optimal Forward Error Correction(FEC) scheme is expected to have a large burst error correction capability while simultaneously owning moderate random error correction capability. This letter presents a new FEC scheme based on multiple-symbol interleaved Reed-Solomon codes and an associated two-pass decoding algorithm. It is shown that the proposed multi-symbol interleaved Reed-Solomon scheme can achieve nearly twice as much as the burst error correction capability of conventional single-symbol interleaved Reed-Solomon codes with the same code length and code rate.

New MDS Euclidean and Hermitian Self-Dual Codes over Finite Fields

In this paper, we construct MDS Euclidean self-dual codes which are ex-tended cyclic duadic codes. And we obtain many new MDS Euclidean self-dual codes. We also construct MDS Hermitian self-dual codes from generalized Reed-Solomon codes and constacyclic codes.

ERASED-CHASE DECODING FOR RS-CODED MPSK SIGNALING OVER A RAYLEIGH FADING CHANNEL

In this paper,a novel dual-metric,the maximum and minimum Squared Euclidean Distance Increment (SEDI) brought by changing the hard decision symbol,is introduced to measure the reli-ability of the received M-ary Phase Shift Keying (MPSK) symbols over a Rayleigh fading channel. Based on the dual-metric,a Chase-type soft decoding algorithm,which is called erased-Chase algorithm,is developed for Reed-Solomon (RS) coded MPSK schemes. The proposed algorithm treats the unre-liable symbols with small maximum SEDI as erasures,and tests the non-erased unreliable symbols with small minimum SEDI as the Chase-2 algorithm does. By introducing optimality test into the decoding procedure,much more reduction in the decoding complexity can be achieved. Simulation results of the RS(63,42,22)-coded 8-PSK scheme over a Rayleigh fading channel show that the proposed algorithm provides a very efficient tradeoff between the decoding complexity and the error performance. Finally,an adaptive scheme for the number of erasures is introduced into the decoding algorithm.

On Deep Holes of Projective Reed-Solomon Codes over Finite Fields with Even Characteristic

Projective Reed-Solomon code is an important class of maximal distance separable codes in reliable communication and deep holes play important roles in its decoding.In this paper,we obtain two classes of deep holes of projective Reed-Solomon codes over finite fields with even characteristic.That is,let F_(q) be finite field with even characteristic,k∈{2,q-2},and let u(x)be the Lagrange interpolation polynomial of the first q components of the received vector u∈F_(q)+1 q Suppose that the(q+1)-th component of u is 0,and u(x)=λx^(k)+f_(≤k-2)(x),λx^(q-2)+f_(≤k-2)(x),where λ∈F^(*)_(q) and f_(≤k-2)(x)is a polynomial over F_(q) with degree no more than k-2.Then the received vector u is a deep hole of projective Reed-Solomon codes PRS(F_(q),k).In fact,our result partially solved an open problem on deep holes of projective Reed-Solomon codes proposed by Wan in 2020.

Three New Classes of Subsystem Codes

In this paper,we construct three classes of Clifford subsystem maximum distance separable(MDS)codes based on Reed-Solomon codes and extended generalized Reed-Solomon codes over finite fields Fq for specific code lengths.Moreover,our Clifford subsystem MDS codes are new because their parameters differ from the previously known ones.

Optimal Asymmetric Quantum Codes from the Euclidean Sums of Linear Codes

In this paper,we first give the definition of the Euclidean sums of linear codes,and prove that the Euclidean sums of linear codes are Euclidean dual-containing.Then we construct two new classes of optimal asymmetric quantum error-correcting codes based on Euclidean sums of the Reed-Solomon codes,and two new classes of optimal asymmetric quantum error-correcting codes based on Euclidean sums of linear codes generated by Vandermonde matrices over finite fields.Moreover,these optimal asymmetric quantum errorcorrecting codes constructed in this paper are different from the ones in the literature.

On deep holes of standard Reed-Solomon codes

Determining deep holes is an important open problem in decoding Reed-Solomon codes. It is well known that the received word is trivially a deep hole if the degree of its Lagrange interpolation polynomial equals the dimension of the Reed-Solomon code. For the standard Reed-Solomon codes [p-1, k]p with p a prime, Cheng and Murray conjectured in 2007 that there is no other deep holes except the trivial ones. In this paper, we show that this conjecture is not true. In fact, we find a new class of deep holes for standard Reed-Solomon codes [q-1, k]q with q a power of the prime p. Let q≥4 and 2≤k≤q-2. We show that the received word u is a deep hole if its Lagrange interpolation polynomial is the sum of monomial of degree q-2 and a polynomial of degree at most k-1. So there are at least 2(q-1)qk deep holes if k q-3.

On error distance of Reed-Solomon codes

The complexity of decoding the standard Reed-Solomon code is a well known open prob-lem in coding theory. The main problem is to compute the error distance of a received word. Using the Weil bound for character sum estimate, we show that the error distance can be determined precisely when the degree of the received word is small. As an application of our method, we give a significant improvement of the recent bound of Cheng-Murray on non-existence of deep holes (words with maximal error distance).

On Reed-Solomon Codes

The complexity of decoding the standard Reed-Solomon code is a well-known open problem in coding theory.The main problem is to compute the error distance of a received word.Using the Weil bound for character sum estimate,Li and Wan showed that the error distance can be determined when the degree of the received word as a polynomial is small.In the first part,the result of Li and Wan is improved.On the other hand,one of the important parameters of an error-correcting code is the dimension.In most cases,one can only get bounds for the dimension.In the second part,a formula for the dimension of the generalized trace Reed-Solomon codes in some cases is obtained.

低时延RS-CC级联码的设计与实现

为提高手持无线电台的纠错和时延特性,考虑设计一种短码长RS-CC级联码。通过对Reed-Solomon码缩短和截断以及对卷积码删余,提出了一种低时延的级联码设计方案,并进行性能分析和软硬件实现。结果表明,在高斯信道下,当E b/N0达到4.2 dB时,能够实现10-4的误码率性能。设计的RS-CC级联码码长较短,编解码固有时延低,译码速度提升30%,适合低时延应用。

Homogeneous Interpolation Problem and Key Equation for Decoding Reed-Solomon Codes

The concept of homogeneous interpolation problem (HIP) over fields is introduced.It is discovered that solving HIP over finite fields is equivalent to decoding Reed-Solomon (RS) codes.The Welch-Berlekamp algorithm of decoding RS codes is derived;besides,by introducing the concept of incomplete locator of error patterns,the algorithm called incomplete iterative decoding is established.

A pipelined Reed-Solomon decoder based on a modified step-by-step algorithm

We propose a pipelined Reed-Solomon(RS) decoder for an ultra-wideband system using a modified stepby-step algorithm. To reduce the complexity, the modified step-by-step algorithm merges two cases of the original algorithm. The pipelined structure allows the decoder to work at high rates with minimum delay. Consequently, for RS(23,17) codes, the proposed architecture requires 42.5% and 24.4% less area compared with a modified Euclidean architecture and a pipelined degree-computationless modified Euclidean architecture, respectively. The area of the proposed decoder is 11.3% less than that of the previous step-by-step decoder with a lower critical path delay.

A Low Power Error Detection in the Syndrome Calculator Block for Reed-Solomon Codes: RS(204,188)

Reed-Solomon （RS） codes have been widely adopted in many modern communication systems. This paper describes a new method for error detection in the syndrome calculator block of RS decoders. The main feature of this method is to prove that it is possible to compute only a few syndrome coeffi- cients -- less than half-- to detect whether the codeword is correct. The theoretical estimate of the prob- ability that the new algorithm failed is shown to depend on the number of syndrome coefficients computed. The algorithm is tested using the RS（204,188） code with the first four coefficients. With a bit error rate of 1 ~ 104, this method reduces the power consumption by 6% compared to the basic RS（204,188） decoder. The error detection algorithm for the syndrome calculator block does not require modification of the basic hardware implementation of the syndrome coefficients computation. The algorithm significantly reduces the computation complexity of the syndrome calculator block, thus lowering the power needed.

ENUMERATION RESULTS FOR THE CODEWORDS HAVING NO INNER PERIODS IN REED-SOLOMON CODES

Let x=(x0, …, xn-1) be a sequence in the finite field GF（q） with length n, Si, x is the i-cyclic shift of x,i.e. Six=(xi, xi+1, …, xi-1) （where i+1 means （i+1）rood n）. If there exists a positive integer 0【r≤n making Srx=x+（u, u, …, u） hold for some u∈GF（q）, then the r is called one of the generalized periods of this sequence x. The least one rmin of such periods is called the minimum generalized period of x. In narticular, if rmin=n (i. e. the

Iterative list decoding approach for Reed-Solomon codes

A novel adaptively iterative list decoding(ILD) approach using for Reed-Solomon(RS) codes was investigated. The proposed scheme is exploited to reduce the complexity of RS Chase algorithm(CA) via an iterative decoding attempt mode. In each decoding attempt process, a test pattern is generated by flipping the bits of the least reliable positions(LRPs) within the received hard-decision(HD) vector. The ILD algorithm continues until a test pattern is successfully decoded by the underlying Berlekamp-Massey algorithm(BMA) of RS codes. Flipping within the same bits, the ILD algorithm provides the same test pattern set as the conventional RS CA, thus there is no degradation in error-rate performance. Without decoding all test patterns, the ILD algorithm can simplify the decoding complexity by its early termination. Simulation results show that the average complexity of the ILD algorithm is much lower than that of the conventional RS CA(and is similar to that of BMA decoding) at high signal-to-noise ratio(SNR) region with no less to the RS CA decoding error-rate performance.

On Ordinary Words of Standard Reed-Solomon Codes over Finite Fields

Reed-Solomon codes are widely used to establish a reliable channel to transmit information in digital communication which has a strong error correction capability and a variety of efficient decoding algorithm.Usually we use the maximum likelihood decoding(MLD)algorithm in the decoding process of Reed-Solomon codes.MLD algorithm relies on determining the error distance of received word.Dür,Guruswami,Wan,Li,Hong,Wu,Yue and Zhu et al.got some results on the error distance.For the Reed-Solomon code C,the received word u is called an ordinary word of C if the error distance d(u,C)=n-deg u(x)with u(x)being the Lagrange interpolation polynomial of u.We introduce a new method of studying the ordinary words.In fact,we make use of the result obtained by Y.C.Xu and S.F.Hong on the decomposition of certain polynomials over the finite field to determine all the ordinary words of the standard Reed-Solomon codes over the finite field of q elements.This completely answers an open problem raised by Li and Wan in[On the subset sum problem over finite fields,Finite Fields Appl.14(2008)911-929].