A dissertation submitted in fulfilment of the requirements for the degree of Master of Science in the Centre for Telecommunication Access and Services, School of Electrical and Information Engineering, University of the Witwatersrand, Johannesburg, 2016 / Reed-Solomon codes are very popular codes used in the field of forward error correction due to their correcting capabilities. Thus, a lot of research has been done dedicated to the development of decoding algorithms for this class of code. [Abbreviated Abstract. Open document to view full version]

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2017-05-25T12:10:45Z No. of bitstreams: 1 Elcio Kondo_.pdf: 2605139 bytes, checksum: bc6eb6e69a381723f69fbce90af22fab (MD5) / Made available in DSpace on 2017-05-25T12:10:45Z (GMT). No. of bitstreams: 1 Elcio Kondo_.pdf: 2605139 bytes, checksum: bc6eb6e69a381723f69fbce90af22fab (MD5) Previous issue date: 2017-01-11 / Nenhuma / Atualmente vários equipamentos eletrônicos são equipados com memórias NAND Flash para armazenar dados. Essas memórias são controladas através de um circuito integrado com um controlador de memória, que internamente possui um sistema para garantir a integridade das informações armazenadas, os quais são conhecidos por Error Correction Codes (ECC). Os ECCs são códigos capazes de detectar e corrigir erros através de bits redundantes adicionados à informação. Normalmente, os códigos ECC são implementados em hardware dentro do controlador de memória NAND Flash. Neste trabalho comparou-se alguns códigos de ECC utilizados pela indústria, para as comparações utilizou-se os códigos ECC: Hamming, BCH (Bose-Chaudhuri-Hocquenghem) e Reed- Solomon. Sistematicamente realizou-se comparações entre os ECCs selecionados e escolheu-se os dois mais apropriados (BCH e Hamming), os quais foram implementados em linguagem VHDL, o que possibilitou identificar o código com melhor vantagem econômica no uso em memórias NAND Flash. / Nowadays several electronic equipment are using NAND Flash memories to store data. These memories are controlled by an integrated circuit with an memory controller embedded that internally has a system to ensure the integrity of the stored information, that are known as Error Correction Codes (ECC). The ECCs are codes that can detect and correct errors by redundant bits added to information. Usually the ECC codes are implemented on NAND Flash memory controller as a hardware block. On this text ECC codes used by industry, the Hamming code, BCH (Bose-Chaudhuri-Hocquenghem) and Reed-solomon codes were compared.Systemically compare between selected ECCs were done and selected two codes (BCH and Hamming), which were described in VHDL language and allowed to identify the best code with better economical advantage for NAND Flash memories.

Lookup-table (LUT)-based method is a common approach used in all kinds of research topics. In this dissertation, we present several new designs for table-based function evaluation and table-based error correcting coding. In Chapter 3, a new function evaluation method, called two-level approximation, is presented where piecewise degree-one polynomials are used for initial approximation in the first level, followed by the refined approximation for the shared normalized difference functions in the second level. In Chapter 4, we present a new non-uniform segmentation method that searches for the optimal segmentation scheme with the different design goals of minimizing either ROM, total area, or delay. In Chapter 5, a new design methodology for table-based function evaluation is presented. Unlike previous approaches that usually determine the bit widths by assigning allowable errors for individual hardware components, the total error budget of our new design is considered jointly in order to optimized the bit widths of all the hardware components, leading to significant improvements in both area and delay. Finally, in Chapter 6, the similar table-based concept is used in the design of error correcting encoder using the modified polynomial of the Lagrange interpolation formula, resulting in smaller critical path delay and lower power consumption.

With the approach of the era of digital TV system around the world, how to grasp the design techniques of the receiver of the DVB-T has become a very important topic. The goal of this thesis is to pursue a highly optimized VLSI architecture compatible to the channel decoding standard of the DVB-T protocol. The channel decoding scheme adopted in DVB-T is based on the concatenated code; which is comprised of an inner Viterbi decoder, outer Reed-Solomon decoder and inner and outer de-interleaver modules. These modules all require a significant amount of data storage space, therefore the main feature of the proposed channel decoder architectures is to realize the data storage based on RAM instead of registers. This approach can lead to the reduction of silicon area and the dynamic power dissipation compared with the shift register based architecture. In order to achieve this, in the design of Viterbi module, the popular register-exchange and trace-back techniques used for the detection of the survivor path has been combined for the survivor memory management unit. As for the design of Reed-Solomon decoder, it is designed based on the modified inverse-free Berlekamp-Massey algorithm. A novel finite field constant multiplier architecture has been proposed which can reduce the required gate count of the multipliers by 20%. For outer convolutional deinterleaver, a specific address generator has been designed such that the data deinterleaver path can be merged and implemented as two memory blocks. For inner symbol deinterleaver, a lookahead technique has been applied to the design of address generator and deinterleaver memory has been reduced by a half compared with those in the literature. These four modules have been verified and integrated as robust channel decoder silicon IP. The related models used for IP integration and verification have also been provided. The prototyping on the FPGA has been tested to satisfy the requirement of the spec.

Reed-Solomon codes are a class of maximum distance separable error correcting codes with known fast error correction algorithms. They have been widely used to assure data integrity for stored data on compact discs, DVDs, and in RAID storage systems, for digital communications channels such as DSL internet connections, and for deep space communications on the Voyager mission. The recent explosion of storage needs for "Big Data'' has generated renewed interest in large storage systems with extended error correction capacity. Reed-Solomon codes have been suggested as one potential solution. This dissertation reviews the theory of Reed-Solomon codes from the perspective taken in Reed and Solomon's original paper on them. It then derives the Welch-Berlekamp algorithm for solving certain polynomial equations, and connects this algorithm to the problem of error correction. The discussion is mathematically rigorous, and provides a complete and consistent discussion of the error correction process. Numerous algorithms for encoding, decoding, erasure recovery, error detection, and error correction are provided and their computational cost is analyzed and discussed thus allowing this dissertation to serve as a manual for engineers interested in implementing Reed-Solomon coding.

No description available.

Reed-Solomon (RS) codes are powerful error-correcting codes that can be found in a wide variety of digital communications and digital data-storage systems. Classical hard decoder of RS code can correct t = (dmin -1) /2 errors where dmin = (n - k+ 1) is the minimum distance of the codeword, n is the length of codeword and k is the dimension of codeword. Maximum likelihood decoding (MLD) performs better than the classical decoding and therefore how to approach the performance of the MLD with less complexity is a subject which has been researched extensively. Applying the bit reliability obtained from channel to the conventional decoding algorithm is always an efficient technique to approach the performance of MLD, although the exponential increase of complexity is always concomitant. It is definite that more enhancement of performance can be achieved if we apply the bit reliability to enhanced algebraic decoding algorithm that is more powerful than conventional decoding algorithm. In 1997 Madhu Sudan, building on previous work of Welch-Berlekamp, and others, discovered a polynomial-time algorithm for decoding low-rate Reed- Solomon codes beyond the classical error-correcting bound t = (dmin -1) /2. Two years later Guruswami and Sudan published a significantly improved version of Sudan's algorithm (GS), but these papers did not focus on devising practical implementation. The other authors, Kotter, Roth and Ruckenstein, were able to find realizations for the key steps in the GS algorithm, thus making the GS algorithm a practical instrument in transmission systems. The Gross list algorithm, which is a simplified one with less decoding complexity realized by a reencoding scheme, is also taken into account in this dissertation. The fundamental idea of the GS algorithm is to take advantage of an interpolation step to get an interpolation polynomial produced by support symbols, received symbols and their corresponding multiplicities. After that the GS algorithm implements a factorization step to find the roots of the interpolation polynomial. After comparing the reliability of these codewords which are from the output of factorization, the GS algorithm outputs the most likely one. The support set, received set and multiplicity set are created by Koetter Vardy (KV) front end algorithm. In the GS list decoding algorithm, the number of errors that can be corrected increases to tcs = n - 1 - lJ (k - 1) n J. It is easy to show that the GS list decoding algorithm is capable of correcting more errors than a conventional decoding algorithm. In this dissertation, we present two hybrid list decoding and Chase-like algorithms. We apply the Chase algorithms to the KV soft-decision front end. Consequently, we are able to provide a more reliable input to the KV list algorithm. In the application of Chase-like algorithm, we take two conditions into consideration, so that the floor cannot occur and more coding gains are possible. With an increase of the bits that are chosen by the Chase algorithm, the complexity of the hybrid algorithm increases exponentially. To solve this problem an adaptive algorithm is applied to the hybrid algorithm based on the fact that as signal-to-noise ratio (SNR) increases the received bits are more reliable, and not every received sequence needs to create the fixed number of test error patterns by the Chase algorithm. We set a threshold according to the given SNR and utilize it to finally decide which unreliable bits are picked up by Chase algorithm. However, the performance of the adaptive hybrid algorithm at high SNRs decreases as the complexity decreases. It means that the adaptive algorithm is not a sufficient mechanism for eliminating the redundant test error patterns. The performance of the adaptive hybrid algorithm at high SNRs motivates us to find out another way to reduce the complexity without loss of performance. We would consider the two following problems before dealing with the problem on hand. One problem is: can we find a terminative condition to decide which generated candidate codeword is the most likely codeword for received sequence before all candidates of received set are tested? Another one is: can we eliminate the test error patterns that cannot create more likely codewords than the generated codewords? In our final algorithm, an optimality lemma coming from the Kaneko algorithm is applied to solve the first problem and the second problem is solved by a ruling out scheme for the reduced list decoding algorithm. The Gross list algorithm is also applied in our final hybrid algorithm. After the two problems have been solved, the final hybrid algorithm has performance comparable with the hybrid algorithm combined the KV list decoding algorithm and the Chase algorithm but much less complexity at high SNRs. / Thesis (M.Sc.Eng.)-University of KwaZulu-Natal, 2005

Thesis (M.S. in Electrical Engineering)--Naval Postgraduate School, September 2009. / Thesis Advisor(s): Robertson, R. Clark. "September 2009." Description based on title screen as viewed on 6 November 2009. Author(s) subject terms: Link-16/JTIDS, (31, 15) Reed-Solomon (RS) coding, 32-ary Orthogonal signaling, Additive White Gaussian Noise (AWGN), Pulse-Noise Interference (PNI), Perfect Side Information (PSI). Includes bibliographical references (p. 49-51). Also available in print.

Thesis (M.S. in Electronic Warfare Systems Engineering)--Naval Postgraduate School, September 2009. / Thesis Advisor(s): Robertson, Ralph C. "September 2009." Description based on title screen as viewed on 5 November 2009. Author(s) subject terms: Link-16/JTIDS, Reed-Solomon (RS) coding, Cyclic Code-Shift Keying (CCSK), Minimum-Shift Keying (MSK), convolutional codes, concatenated codes, perfect side information (PSI), Pulsed-Noise Interference (PNI), Additive White Gaussian Noise (AWGN), coherent detection, noncoherent detection. Includes bibliographical references (p. 79). Also available in print.

Reed-Solomon code is nowadays broadly used in many fields of data transmission. Using of error correction codes is divided into two main operations: information coding before sending information into communication channel and decoding received information at the other side. There are vast of decoding algorithms of Reed-Solomon codes, which have specific features. There is needed knowledge of features of algorithms to choose correct algorithm which satisfies requirements of system. There are evaluated cyclic decoding algorithm, Peterson-Gorenstein-Zierler algorithm, Berlekamp-Massey algorithm, Sugiyama algorithm with erasures and without erasures and Guruswami-Sudan algorithm. There was done implementation of algorithms in software and in hardware. Simulation of implemented algorithms was performed. Algorithms were evaluated and there were proposed methods to improve their work.