Fast decoder and encoder for Reed-Solomon codes and recording/playback apparatus having such an encoder/decoder

Abstract

A decoding device for code words which are protected against the occurrence of several symbol errors per code word by means of a Reed-Solomon code is provided with a word buffer which comprises a space for the storage of an erasure indication per symbol received. For correction of the code word, first the syndrome symbols are formed by multiplication by the parity check matrix. The sum of twice the number of error symbols and once the number of erasure symbols may not be larger than the number of syndrome symbols. First the syndrome symbols are modified so that the syndrome symbols which could possibly relate to error symbols (non-erasure symbols) are no longer influenced by the erasure symbols. The key equation and error locator equation for the non-influenced syndrome symbols can then be separately solved, so that the locations of error symbols can be found. The latter syndrome symbols are then modified, when necessary, for calculated error locations, while the error values or erasure values are determined from a set of mutually independent syndrome symbols whose number equals the sum of error symbols and erasure symbols. There is provided an arithmetic unit for the Galois-field which, for the sake of simplicity, performs the calculations on the exponents of the symbols which are written as powers of the basic symbol of the Galois-field.

What is claimed is: 
     
       1. A device for decoding multisymbol code words protected from errors by a Reed-Solomon code for each multisymbol code word comprising: means for sequentially receiving code symbols contained in said code words including a buffer means for storing the code symbols of a code word including erasure indications which relate to a code symbol;   a first arithmetic means connected to said means for receiving for multiplying said code symbols by a parity check matrix for producing a plurality of syndrome symbols for each code word;   second arithmetic means connected to said first arithmetic means for receiving said plurality of syndrome symbols, and connected to said buffer means for receiving said erasure indications, said second arithmetic means including a log table for converting a Galois-field element to an associated power of the basic element of the Galois-field, and including means for converting said associated power of the basic element to a second Galois-field element, said second arithmetic means in response to an erasure indication updating the syndrome symbols for each code symbol which is identified as being an erasure symbol and for reducing said plurality of syndrome symbols one symbol for each erasure signal, said second arithmetic means solving a key equation for any remaining syndrome symbols up to a maximum equal to an integer portion of one half the number of said syndrome symbols which remain, using a zero point of an error locator polynomial, and for evaluating each error position thus located for an error value for said error position, and treating each symbol of an error position as a secondary erasure symbol.   
     
     
       2. A decoding device as claimed in claim 1, for code words which are systematic at the symbol level, wherein said first arithmetic means includes a control input (EDS) for receiving an encoding/decoding signal in order to form syndrome symbols from a code word under the control of the decoding signal, and to subsequently form a set of error locations from the syndrome symbols, and an error value for each error location, and to form under the control of an encoding signal a series of parity symbols from a series of data symbols which have been corrected with respect to the already present symbols. 
     
     
       3. A decoding device as claimed in claim 1 or 2, wherein said buffer means comprises two alternating buffer elements SME1, 2, each of which serves to accommodate a complete code word, each buffer element having a memory EME1, 2 for the erasure locations, each of said memories being addressed by an associated counter ECO1, 2 which is decremented by a read control signal and which is incremented by a write control signal. 
     
     
       4. A decoding device as claimed in claim 1, wherein said Galois-field arithmetic unit comprises a chain which is formed by a converter for converting a symbol into an element of the set comprising an exponent, double exponent, inverted exponent, halved exponent, a selectively activatable adder which is provided with a bypass, and a second converter for reconverting an exponent into the associated symbol. 
     
     
       5. A decoding device as claimed in claim 1, wherein said first arithmetic means comprise a parallel connection of (d-1) registers, each of which serves for a provisional syndrome symbol, a series connection of (d-2) multiplier elements for multiplying each symbol received by the basic element of the relevant Galois-field, each multiplier element being connected between the inputs of two successive registers, per code word symbol received, the registers being cyclically driven in the sequence of the multiplier elements, an exclusive-OR circuit XOR which comprises a code symbol input and a feedback input which is fed by all registers of the parallel connection, the output of the exclusive-OR circuit being reconnected to the series connection forming an output of the first arithmetic means. 
     
     
       6. A decoding device as claimed in claim 5, wherein between the exclusive-OR circuit and the input of the series connection there is connected a further symbol register (SR). 
     
     
       7. A decoding device as claimed in claim 1, wherein said buffer means comprise a counter (LCO) which can be loaded by an adjustable register (WLE) in order to count down the number of symbols received and to form a reception ready signal when a predetermined position is reached. 
     
     
       8. A decoding device as claimed in claim 1, wherein said second arithmetic means comprise a strategy-determining register (56) for storing the permissible number of erasure symbols and for supplying an uncorrectability signal when a larger number of erasure symbols is received in a code word. 
     
     
       9. A decoding device as claimed in claim 8, wherein said second arithmetic means comprises a second strategy-determining register for storing the permissible number of error symbols in excess of the erasure symbols and supplies an uncorrectability signal when the number of error symbols found in a code word is larger than said permissible number. 
     
     
       10. A decoding device as claimed in claim 4, wherein said Galois-field arithmetic unit comprises two parallel-connected memories which are bidirectionally connected to said chain as well as to a connection to further parts of the second arithmetic means.