Search

A novel single parity check-multiplicity assignment decoding algorithm based on voltage magnitude (VM_SPC-MA) is proposed, which is applied to the concatenated scheme of single parity check (SPC) inner code and Reed–Solomon (RS) outer code, following the Consultative Committee for Space Data Systems (CCSDS) standard. The algorithm determines whether the SPC code is in error by SPC, then obtains the reliability information of the inner code bits for error correction based on the characteristics of the received bit-level voltage, and decodes the outer code based on the reliability information of the inner codewords and the channel information. The decoding performance is greatly improved by connecting the inner and outer codes through the multiplicity assignment (MA) module, which makes full use of the channel information. Compared with the low-complexity Chase decoding based on the hard-decision decoding (HDD-LCC) and SPC_Kaneko-RS_Chase decoding, simulation results show that the SPC-RS concatenated decoding scheme based on VM_SPC-MA algorithm can provide up to 1.78 and 1.05 dB of coding gain when the bit error rate is (BER) = 10−5. Besides, the hardware design of the SPC-MA module is provided and applied to the serial LCC decoder based on syndrome calculation-polynomial selection (PS)-Chien search and Forney algorithm (SPCF). The implementation results in ASIC show that the area efficiency of the complete concatenated decoder increases by 27.38% compared to the unified syndrome computation (USC)-based LCC decoder in a 0.13- $\mu \text{m}$ process.

Reed-Solomon (RS) codes have been widely used in digital communication and storage systems. The commonly used decoding algorithms include Berlekamp-Massey (BM) algorithm and its variants such as the inversionless BM (iBM) and the Reformulated inversionless BM (RiBM). All these algorithms require the computation-intensive procedures including key equation solver (KES), and Chien Search & Forney algorithm (CS&F). For RS codes with the error correction ability t≤ 2, it is known that error locations and magnitudes can be found through direct equation solver. However, for RS codes with t=3, no such work has been reported yet. In this paper, a low-complexity algorithm for triple-error-correcting RS codes is proposed. Moreover, an optimized architecture for the proposed algorithm is developed. For a (255, 239) RS code over GF(2^8), the synthesis results show that the area-efficiency of the proposed decoder is 217% higher than that of the conventional RiBM-based RS decoder in 4-parallel. As the degree of parallelism increases, the area-efficiency is increased to 364% in the 16-parallel architecture. The synthesis results show that the proposed decoder for the given example RS code can achieve a throughput as large as 124 Gb/s.

This paper proposes a soft input decoding algorithm and a decoder architecture for generalized concatenated (GC) codes. The GC codes are constructed from inner nested binary Bose–Chaudhuri–Hocquenghem (BCH) codes and outer Reed–Solomon codes. In order to enable soft input decoding for the inner BCH block codes, a sequential stack decoding algorithm is used. Ordinary stack decoding of binary block codes requires the complete trellis of the code. In this paper, a representation of the block codes based on the trellises of supercodes is proposed in order to reduce the memory requirements for the representation of the BCH codes. This enables an efficient hardware implementation. The results for the decoding performance of the overall GC code are presented. Furthermore, a hardware architecture of the GC decoder is proposed. The proposed decoder is well suited for applications that require very low residual error rates.

In this paper, the simplified step-by-step Reed-Solomon (RS) decoding algorithm was adopted in this work to reduce the hardware complexity and power consumption. According to the advantages of the step-by-step RS decoding algorithm, we propose the three-parallel hardware architecture to speed up the RS decoding rate without the need for recursively solving the error-location polynomial and performing the Forney algorithm. Finally, using TSMC 90nm technology, the proposed design has a working frequency of up to 286MHz. The gate counts and throughput of this chip core are approximately 131K gates and 6.8Gb/s at 286MHz, respectively.

In this work, we propose a novel design rule of block-wise concatenated Bose-Chaudhuri-Hocquenghem (BC-BCH) codes for storage devices using multi-level per cell (MLC) NAND flash memories. BC-BCH codes designed in accordance with the proposed design rule are called quasi-primitive BC-BCH codes in which constituent BCH codes are deliberately chosen for their lengths to be as close to primitive BCH codes as possible. It will be shown that such quasi-primitive BC-BCH codes can achieve significant improvements of error-correcting capability over the existing BC-BCH codes when an iterative hard-decision based decoding (IHDD) is assumed. In addition, we propose a novel collaborative decoding algorithm which targets at resolving dominant error patterns associated with the IHDD. Error-rate performances of error-control systems with the proposed quasi-primitive BC-BCH and existing BC-BCH codes are compared. For more comprehensive performance comparisons, systems with a hypothetically long BCH code and a product code are also considered in the comparisons.

Reed–Solomon (RS) codes possess excellent error correction capability. Algebraic soft-decision decoding (ASD) of RS codes can provide better correction performance than the hard-decision decoding (HDD). The low-complexity Chase (LCC) decoding has the lowest complexity cost and similar or even higher coding gain among all of the available ASD algorithms. Instead of employing complicated interpolation technique, the LCC decoding can be implemented based on the HDD. This study proposes a modified serial LCC decoder, which employs a novel syndrome calculation, polynomial selection, Chien search and Forney algorithm block. In addition, an improved two-dimensional optimisation is provided to reduce the hardware complexity of the proposed decoder. Compared with the previous design, the proposed decoder can improve about 1.27 times speed and obtain 1.29 times higher efficiency in terms of throughput-over-slice ratio.

In Computing devices in the world wide, where number of computing and communication systems are increased rapidly. In the channel noise has greater impact on the messages or data transmitted through the wired/wireless network. The Reed–Solomon (RS) decoder plays a vital role in removing the error from the received messages or data. The RS decoder has four main blocks, namely, Syndrome Computation (SC) block, Key Equation Solver (KES) block, Chien Search (CS) block and Forney Algorithm (FA) block. The researchers have thrown a number of works on each and every block of RS decoder. Moreover, the parallel and pipelined RS decoder shows a greater improvement in terms of gate element, latency, coding gain and throughput. Although this architecture has higher performance gain, the computation complexity in the SC block is not addressed. This paper presents an efficient architecture to compute the α-factor of SC blocks in RS decoder. The proposed RS decoder is developed using Verilog HDL (Hardware Description Language) and synthesized in Synopsys Design Compiler (DC). The proposed architecture is implemented in 90 nm CMOS technology and the results are evaluated in terms of gate count, clock rate, latency and throughput. The evaluated results of the proposed decoder show a remarkable improvement when compared with a conventional RS decoder.

A fast, area efficient very large scale integration (VLSI) architecture is proposed for a unique decoding algorithm of Hermitian codes which was presented recently by Lee and O'Sullivan from an interpolation perspective. The algorithm iteratively computes the sent message through a majority voting procedure by using the Grobner bases of interpolation modules. The algorithm has a regular structure which makes it suitable for VLSI implementation. The circuitry is simplified as the decoding algorithm directly gives the message word at the end of the decoding algorithm without separate steps like Chien search and Forney's formula. In terms of hardware requirements, for the widely used high rate Hermitian codes, the Lee–O'Sullivan algorithm is q times faster than Kotters algorithm with the same space complexity of O(q 4). Further speed improvements can be achieved by combining the main idea of Guruswami list decoding with the Lee–O'Sullivan algorithm. In terms of hardware, the addition of this concept, will further reduce the running time of the algorithm and make the circuitry about two times faster than the original Lee–O'Sullivan algorithm. The implementation results for both the Koetter and the Lee–O'Sullivan algorithms on Xilinx Virtex-5 shows that the proposed decoder can be operated at higher clock frequency with almost same area complexity.

To date, Forney's method has been the most efficient and widely-used method for evaluating error magnitudes of Reed-Solomon (RS) codes in time-domain decoding. In this letter, a new method is proposed to evaluate error magnitudes of RS codes. The proposed method has lower computational complexity than Forney's one.

BCH codes are adopted in many systems, such as flash memory, optical communications, and digital video broadcasting. By trying 2η test vectors, the soft-decision Chase decoding algorithm of BCH codes can achieve significant coding gain over hard-decision decoding. Previous one-pass Chase schemes find the error locators based on the Berlekamp's algorithm and need hardware-demanding selection methods to decide which locator corresponds to the correct code word. In this brief, a novel interpolation-based one-pass Chase decoder is proposed for BCH codes. By making use of the binary property of BCH codes, an innovative yet low-complexity method is developed to select the interpolation output leading to successful decoding without bringing any performance loss. The code word recovery step is also significantly simplified through nontrivial mathematical derivations. From architectural analysis, the proposed decoder with η = 4 for a (4200, 4096) BCH code has 2.3 times higher efficiency in terms of throughput-over-area ratio than the prior one-pass Chase decoder based on the Berlekamp's algorithm, while achieving the same error-correcting performance.

Let $q\geq 3$ be a prime power. Maximal designed distances of primitive Hermitian dual containing $q^{2}$-ary BCH codes (narrow-sense or non-narrow-sense) are determined by a careful analysis of properties of cyclotomic cosets. Non-narrow-sense BCH codes which achieve these maximal designed distances are presented, and a sequence of nested non-narrow-sense BCH codes that contain these BCH codes with maximal designed distances are constructed and their parameters are computed. Consequently, new nonbinary quantum BCH codes are derived from these non-narrow-sense BCH codes. The nonbinary quantum BCH codes presented here have better parameters than those quantum BCH codes available in the literature.

A simple algorithm for decoding nonsystematic Reed–Solomon codewords was proposed by A. Shiozaki and independently by S. Gao. We first exhibit the companion algorithm for decoding systematic Reed–Solomon codes. Next, we improve this algorithm into one that is identical to traditional Reed–Solomon decoding. The algorithm will then be adjusted to work with nonstandard Reed–Solomon codes. Finally, we modify the algorithm into one that decodes Reed–Solomon codes with erasures that is slightly more efficient than existing techniques.

Two code constructions generating new families of good nonbinary asymmetric quantum BCH codes and good nonbinary subsystem BCH codes are presented in this paper. The first one is derived from q-ary Steane’s enlargement of CSS codes applied to nonnarrow-sense BCH codes. The second one is derived from the method of defining sets of classical cyclic codes. The asymmetric quantum BCH codes and subsystem BCH codes here have better parameters than the ones available in the literature.

An efficient RS encoder for a parity replacer circuit of ATSC M/H mobile DTV receiver is presented. First, we derive the non-systematic RS encoder architecture which requires the well-known Forney algorithm to evaluate the parity symbol values located at arbitrary positions. We notice that only at most three information symbols corresponding to the trellis initialization symbol determine the RS parity symbols to be replaced in the parity replacer circuit. So we derive another form of the Forney algorithm to represent the parity symbol value as a linear combination of the input information symbols. With the new form, efficient architecture for implementing the RS encoder of a parity replacer is presented.

In this paper, we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and Bose-Chaudhuri-Hocquenghen (BCH) codes. The resulting list decoding algorithms exhibit the following significant properties.

The research of visible light communications(VLC) has became a focus of wireless communications in recent years. In this paper, the channel coding technique for VLC systems were studied. According to the characteristics of VLC channel, RS codes were designed to correct the burst and random errors. The pipeline architecture was designed in the proposed system, and the RS decoder was divided into 4 modules, the syndrome calculation module, the key equation calculation module, the Chein Search module and the Forney algorithm module. In the Chein search module, the RiBM algorithm was used for reduction of complexity. All FPGA implementations of the 4 modules were provided in detail, and simulation results were shown on the Quartus II 9.0 platform. The simulation results show that, no more than 8 random and burst errors can be completely correct by one single proposed RS (204,188) codeword.

The aggregate error locator is defined and a computation method is given. The aggregate error locator is then used in a type of Forney algorithm to compute the error values in the received words of a Ca,b algebraic geometry code.

We present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a fraction (1-r-/spl epsiv/)/2 of errors over an alphabet of constant size depending only on /spl epsiv/, for every 0 0. The error-correction performance of these codes is optimal as seen by the Singleton bound (these are "near-MDS" codes). Such near-MDS linear-time codes were known for the decoding from erasures; our construction generalizes this to handle errors as well. Concatenating these codes with good, constant-sized binary codes gives a construction of linear-time binary codes which meet the Zyablov bound, and also the more general Blokh-Zyablov bound (by resorting to multilevel concatenation). Our work also yields linear-time encodable/decodable codes which match Forney's error exponent for concatenated codes for communication over the binary symmetric channel. The encoding/decoding complexity was quadratic in Forney's result, and Forney's bound has remained the best constructive error exponent for almost 40 years now. In summary, our results match the performance of the previously known explicit constructions of codes that had polynomial time encoding and decoding, but in addition have linear-time encoding and decoding algorithms.

Reed-Solomon (RS) codes play an important role in providing error protection and data integrity. Among various Reed-Solomon decoding algorithms, the Peterson-Gorenstein-Zierler (PGZ) algorithm in general has the least computational complexity for small t values. However, unlike the iterative approaches (e.g., Berlekamp-Massey and Euclidean algorithms), it will encounter divided-by-zero problems in solving multiple t values. In this paper, we propose a multi-mode hardware architecture for error numbers ranging from zero to three. We first propose a cost-down technique to reduce the hardware complexity of a t e 3 decoder. A Finite-field Inversion (FFI) elimination scheme is also proposed in our PGZ kernel. Next, we perform an algorithmic-level derivation to identify the configurable feature of our design. With those manipulations, we are able to perform multi-mode RS decoding in one unified VLSI architecture with very simple control scheme. The very low cost and simple data-path make our design a good choice in small-footprint embedded VLSI systems such as Error Control Coding (ECC) in memory/storage systems.

A construction of polynomial-time decodable codes for discrete memoryless multiple access channels (MACs) is proposed based on concatenated codes. Concatenated codes, originally developed by Forney, can achieve any rate below capacity for the single-user discrete memoryless channel while requiring only polynomial-time decoding complexity in the code length. In this letter, Forney's construction together with multi-level concatenation is generalized to MACs. An error exponent for the constructed code is derived, and it is shown that the constructed code can achieve any rate in the capacity region.

For decoding with erasures, Forney's scheme is known to be optimal in the sense that no other scheme can make the erasure probability P/sub ers/ and undetected error probability P/sub uer/ simultaneously smaller. We propose a scheme for erasure decision which tests the likelihood ratio as well as the likelihood itself and show that the attainable upper bounds on P/sub ers/ and P/sub uer/ are the same as those proved for the optimal scheme up to a constant factor. We also show that the scheme gives, when applied to convolutional codes, a bound which is related to the block-coding bound via Forney's inverse concatenation construction. We show that this bound is the same as the one which naturally arises when we apply Raghavan and Baum's (1998) optimal scheme to convolutional code.

Using a Forney formula to solve for the error magnitudes in decoding algebraic-geometric (AG) codes requires producing functions /spl sigma//sub P/, which are 0 at all but one point P of the variety of the error-locator ideal. The best such function is produced here in a reasonably efficient way from a lex Grobner basis. This lex basis is, in turn, produced efficiently from a weighted grevlex basis by using the FGLM algorithm. These two steps essentially complete the efficient decoding scheme based on a Forney formula started in the author's previous work (see ibid., vol.42, p.1263-8, 1996).

This paper presents a new high speed parallel decoding algorithm for double-error-correcting binary BCH codes.

In the decoding of one-point algebraic-geometry codes with one defining equation in two variables we generalize the Forney formula for the Bose-Chaudhuri-Hocqungham (BCH) codes.

This correspondence contains a straightforward generalization of decoding of BCH codes to the decoding of algebraic-geometric codes, couched in terms of varieties, ideals, and Grobner bases. This consists of 1) a Berlekamp-Massey-type lattice-shifting row-reduction algorithm with majority voting similar to algorithms in the current literature, 2) a realization that it produces a minimal Grobner basis B for the error-locator ideal I(V) relative to a particular weighted total degree monomial ordering, 3) a factoring of that basis into several minimal PLEX bases, that facilitates finding the variety V of error positions, and 4) a direct generalization of Forney's formula to calculate error magnitudes using functions /spl sigma/p, which are by-products of this factoring.

We present a new way to find all possible error patterns up to a given weight greater than the designed error correcting capability (e/sub BCH/). Possible error positions are localized by indicators. Our method can be seen as an extension of the step-by-step decoder introduced by Massey (1965) for BCH codes. We consider the decoding of binary cyclic codes.

This paper researches and analyzes the national standard of QR Code and the characteristics of systematic form of Reed-Solomon (RS) codes in QR Code. Furthermore, RiBM algorithm, Chien search algorithm and Forney algorithm are applied to implement Reed-Solomon algorithm. consequently, the computational complexity of RS error-correcting decoding is reduced and the decoding speed of QR Code is improved.

The Ungerboeck and Forney observation models for offset QPSK are derived for three different representations for OQPSK. The representations and their corresponding Ungerboeck observation models are different, but the trellises used by the maximum likelihood sequence estimators possess the same complexity. The Forney observation models are obtained in straight-forward way for the bit-based representations for OQPSK, but there is no Forney observation model in the traditional sense for the symbol-based OQPSK representation. In the case of the symbol-based OQPSK representation, a method for whitening the resulting non-linear system is described.

Forney's (1968) exponent is effectively the best one for the block-coded automatic repeat-request systems (ARQ) and it has been conjectured that a counterpart of Forney's exponent is attainable by convolutional codes with reasonable decoder complexity. In the paper, it is show that the scheme of Yamamoto and Itoh (1980), which is known to be one of the simplest convolutionally coded ARQ schemes, actually gives a better performance than ever expected and that it has an error exponent quite close to the conjectured counterpart of Forney's exponent at relatively low rates. It is further shown that the likelihood ratio test used by Yamamoto and Itoh gives Forney's exponent in the case of block-coded ARQ. >

The problem of efficient maximum-likelihood soft decision decoding of binary BCH codes is considered. It is known that those primitive BCH codes whose designed distance is one less than a power of two, contain subcodes of high dimension which consist of a direct-sum of several identical codes. The authors show that the same kind of direct-sum structure exists in all the primitive BCH codes, as well as in the BCH codes of composite block length. They also introduce a related structure termed the "concurring-sum", and then establish its existence in the primitive binary BCH codes. Both structures are employed to upper bound the number of states in the minimal trellis of BCH codes, and develop efficient algorithms for maximum-likelihood soft decision decoding of these codes. >

The well-known Forney algorithm, Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm and product construction for minimal linear conventional trellises have all successfully extended to tail-biting trellises. As first author of this paper, one of my paper, in a way, popularized Massey construction of minimal linear conventional trellises to tail-biting trellises, just referred as TB-Massey trellises. In this paper, we make some necessary and important optimization and improvement of TB-Massey trellises, mainly via elaborately constricting vertexes of the trellis graph as far as possible. Then display performance of all kinds of the extended tail-biting trellises by comparison. Though having not found the thorough generalized tail-biting Massey trellises, we get some positive progress and results

Let q be a power of an odd prime number p. We use finite fields to character q-ary BCH codes, then use puncturing and gluing methods to construct self-orthogonal BCH codes. Finally we obtain families of q-ary quantum codes by using the self-orthogonal BCH codes constructed.

A (240,K) Reed-Solomon decoding algorithm for CMMB (China Mobile Multimedia Broadcasting) application is presented. A modified Euclid's algorithm (MEA) Reed-Solomon decoding method was implemented for the Key Equation Solver. And an improved Forney algorithm is also proposed. The modified algorithm was analyzed and compared with BM algorithm. The simulation result shows that the modified algorithm has such advantages as high efficiency and low complexity with good decoding performance. It meets the need of real- time communication.

Guruswami and Indyk showed in [1] that Forney's error exponent can be achieved with linear coding complexity over binary symmetric channels. This paper extends this conclusion to general discrete-time memoryless channels and shows that Forney's and Blokh-Zyablov error exponents can be arbitrarily approached by one-level and multi-level concatenated codes with linear encoding/decoding complexity. The key result is a revision to Forney's general minimum distance decoding algorithm, which enables a low complexity integration of Guruswami-Indyk's outer codes into the concatenated coding schemes., Comment: Submitted to IEEE Communications Letters

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.

UWB is the most spotlighted wireless technology that transmits data at very high rates using low power over a wide spectrum of frequency band. UWB technology makes it possible to transmit data at rate over 100 Mbps within 10 meters. To preserve important header information, MB-OFDM UWB adopts Reed-Solomon (23,17) code. In receiver, RS decoder needs high speed and low latency using efficient hardware. In this paper, we suggest the architecture of RS decoder for MB-OFDM UWB. We adopts modified-Euclidean algorithm for key equation solver block which is most complex in area. We suggest pipelined processing cell for this block and show the detailed architecture of syndrome, Chien search and Forney algorithm block. At last, we show the hardware implementation results of RS decoder for ASIC implementation.

A well known soft decoding algorithm that can make use of algebraic decoding techniques is the GMD algorithm introduced by Forney. This algorithm is based on several error-erasure decoding trails where unreliable positions are successively erased. Chase proposed a closely related family of algorithms for binary codes where unreliable positions are "switched', i.e. different estimates for the positions are used in intermediate steps during the decoding process. In our algorithm, suitable for non binary codes, we try to combine erasures and switchings in a favourable way. A version of the algorithm comparable in complexity with the GMD algorithm is investigated. Simulations show that our algorithm in many cases has a somewhat better error correcting capability then the GMD algorithm.

This paper studies the concatenation of turbo codes and Reed-Solomon (RS) codes. The error patterns of turbo codes are first analyzed. Since error patterns of turbo codes are much different than those of convolutional codes, the design rules for a matched interleaver between turbo codes and RS codes are provided. As an application to digital video broadcasting by satellite (DVB-S), the performance of Forney interleavers with different spreading abilities is studied for a fixed turbo code. For a (34,6) Forney interleaver, the performance of turbo codes with different block sizes is also studied. A delay and performance tradeoff can be made via simulation results.

Derives an estimate for the error term in the binomial approximation of spectra of BCH codes. This estimate asymptotically improves on the bounds by Sidelnikov (1971), Kasami et al. (1985), and Sole (1990). >

This paper proposes a Reed-Solomon (RS) decoder for applications that require high-speed data communication and reliability. The proposed architecture can support variable n and k values (37

A step-by-step decoding algorithm is proposed for double-error-correcting (DEC) Reed-Solomon (RS) codes of length n=2/sup m/-1. Since the decoding algorithm can directly find the error value at the highest-order position in a received vector without determining the error location polynomial, the decoding procedure is very simple and regular, and therefore it is suitable for hardware implementation. Moreover, the new algorithm can also be used for decoding DEC binary BCH codes and DEC nonbinary BCH codes. Finally, based on the decoding algorithm a hardware decoder is also presented.

An analogy is examined between serially concatenated codes and parallel concatenations whose interleavers are described by bipartite graphs with good expanding properties. In particular, a modified expander code construction is shown to behave very much like Forney's classical concatenated codes, though with improved decoding complexity. It is proved that these new codes achieve the Zyablov bound /spl delta//sub Z/ on the minimum distance. For these codes, a soft-decision, reliability-based, linear-time decoding algorithm is introduced, that corrects any fraction of errors up to almost /spl delta//sub Z//2. For the binary-symmetric channel, this algorithm's error exponent attains the Forney bound previously known only for classical (serial) concatenations.

Using Willems' (1989) model for dynamical systems, G.D. Forney and M.D. Trott (see IEEE Trans. on Inform. Theory, vol. 39, 1993) studied the dynamics of group codes defined on Z. Convolutional codes are examples of such group codes. The purpose of the paper is to study convolutional codes from a dynamical system point of view using the dynamics of group codes defined by Forney and Trott. >

The most time consuming step in the decoding of BCH codes is the calculation of the error locator polynomial. This is done using an iterative algorithm or direct solution which is often computationally expensive. By performing a simple check on which syndromes are zero, many decoding failures can be detected before the polynomial is calculated. In this paper, tree diagrams for decoding are constructed based on these checks.

A new lower bound an the error exponent of concatenated codes is derived which coincides with Forney's (1966) upper bound for all code rates.

We propose a new erasure decision scheme for decoding with erasures and show that the scheme also attains the bounds on the erasure probability and undetected error probability which are first derived for Forney's (1968) optimal scheme. The new scheme gives, when applied to convolutional codes, bounds which are related to those for block codes by Forney's inverse concatenation construction without substantial increase in decoder complexity.

One of the checks for the correctness of the result of decoding a BCH code C is that the error values are in the field over which C is defined. For binary narrow-sense BCH codes this check can be omitted, but in general it can not.

We compare the BCH decoding algorithm introduced by Fitzpatrick (see IEEE Trans. Info. Theory IT-41, no.5, p.1290-1302, 1995) with the Berlekamp-Massey algorithm.