HIGH-SPEED DECODING ALGORITHMS OF CYCLIC CODES AND THEIR INTEGRATED-CIRCUIT DESIGNS

Abstract

Many methods and algorithms have been developed for decoding the cyclic codes. In the thesis, we discuss some existing high speed decoding algorithms of cyclic codes. However, the implementations of these methods are complex by present technology. A new step-by-step decoding method of cyclic codes is therefore presented,which corrects the errors directly in terms of the weight variance of the error pattern. This new method uses "decision vectors" and "decision vector sets" to simply represent the relations among the syndrome values of error pattern. It reduces the hardware complexity and thus, makes the decoder easier to be implemented in a single monolithic chip. In addition to the reduction of hardware complexity, a decoder implemented by the new method can also work at a data rate as high as other high speed decoding methods. Based on the new decoding method, a high speed decoding algorithms of t-error-correcting binary Bose-Chaudhuri-Hocquenghem (BCH) codes is presented. A corresponding structure of line-speed decoder is also proposed. This decoder requires only n clock cycles for decoding one received word, where is the block length of the code. Besides, a hgih speed decoding algorithm of Reed-Solomon (RS) codes is presented. Based on this algorithm, two types of decoder, the sequential decoder and the vector decoder can work at line-speed rate. The presented decoders are constructed by four basic modules: the syndrome calculation module, the comparison module, the decision module and the shift-control module. The syndrome calculation module is used to calculate syndrome values of received word. The comparision module is used to determine the decision vectors from syndrome values. In terms of the difference between decision vectors, the decision module can decide whether an error occurs. The shift-control module is used to speed up decoding speed in the sequential decoder (used in nonbinary cyclic codes). These modules may be realized by suing only linear feedback shift-registers (LFSRs), ROMs and logic gates. Comparing decoders implemented by the new step-by-step method with those decoders implemented by the standard algebraic method and the transform method, the new step-by-step decoders have the following advantages : (1) simple structure of decoder (2) low circuit complexity of the modules (3) only a few simple control clock signals are required (4) the decoding speed is independent of the code length and thus a high speed decoding can be achieved. Since the new step-by-step decoding method makes use of the cyclic properties of the cyclic codes, this method can be applied for other methods, such as standard algebraic and Kasami's error-trapping methods.