Abstract:
An extended symbol Galois field error correcting device is provided. The device includes a singly-extended Reed-Solomon encoder configured to generate an encoded codeword, {tilde over (c)}(x). The device also includes a channel medium that is signal coupled with the singly-extended Reed-Solomon encoder. The channel medium is configured to receive the encoded codeword, {tilde over (c)}(x), and output a received input codeword, {tilde over (r)}(x). The channel medium is capable of introducing error, {tilde over (e)}(x), to the encoded codeword, {tilde over (c)}(x). The device further includes a singly-extended Reed-Solomon decoder that is coupled with the channel medium. The singly-extended Reed-Solomon decoder is configured to receive the received input codeword, {tilde over (r)}(x). The singly-extended Reed-Solomon decoder has error detection circuitry and extended symbol correction circuitry. The error detection circuitry is configured to detect presence of error, {tilde over (e)}(x), within the received input codeword, {tilde over (r)}(x). The extended symbol correction circuitry is configured to correct the received input codeword, {tilde over (r)}(x), by computing syndromes of an intermediate output codeword (c′ j ). A corrected extended parity symbol (c_) is provided such that the corrected extended symbol (c_) is multiplexed with the intermediate output codeword (c′ j ) to yield a final output codeword, {tilde over (c)}=[c_c′].

Description:
TECHNICAL FIELD 
     This invention relates to the detection and correction of digital data, and more particularly, to systems and methods for detecting and correcting errors in digital data with singly-extended Reed-Solomon decoders. 
     BACKGROUND OF THE INVENTION 
     Recently, the need has increased for efficient and reliable digital data transmission and storage techniques. The fields of communications and computing have merged such that there exists a great demand for exchanging, processing and storing of digital information with large-scale, high-speed data networks. Even personal computers (PCS) have seen large increases in speed and complexity, and with a coupling to the Internet, have also developed an increased need for apparatus and methods for transferring digital information. A resulting primary concern is the control of errors during exchange, processing and storage of digital information so that data can be reliably reproduced. 
     As early as 1948, it was shown that error reduction could be realized from a noisy channel or storage medium by properly encoding information. Since this date, a significant amount of effort has been expended on devising ways of efficiently encoding and decoding information so that error is controlled, particularly in noisy environments. More recently, the use of high-speed digital systems has resulted in a need to realize reliable data transmission such that coding/decoding has become a significant factor in the design of modern communication systems and digital computers. 
     The intercommunication of computers, data processing systems and communications systems occurs via transmission of digital data comprising signals. Digital signals comprise a series of “ones” and “zeros”. Transfer of such signals oftentimes subjects the signals to errors resulting from the presence of noise, defects in storage media and defects in the transmission path or data channel extending between an information source and a destination device. Hence, there exists a need to correct for such errors in order that transmitted and stored information is not lost. 
     One system for detecting and correcting errors in digital information utilizes Reed-Solomon decoders. One relatively recent attempt is evidenced by U.S. Pat. No. 4,413,339 issued to Riggle, et al., wherein an error detecting and correcting system implements Reed-Solomon (1026,1006) code having codewords whose symbols are elements in the Galois field GF(2 10 ) generated by either the primitive polynomial x 10 +x 3 +1 or x 10 +x 7 +1. 
     However, prior art solutions involving Reed-Solomon decoders generally utilize the following technique. The extended error value (e_) in the extended received-symbol (r_) is calculated by adding the syndrome (S n−k+1 ) of the received input codeword to the computed error values coming out of the RS decoder. That is,          e   _     =       s     n   -   k   +   1       +       ∑     j   =   0       n   -   1              e   j          α     j        (     n   -   k   +   1     )                                      
     The disadvantage associated with the prior art techniques is that the syndrome value (S n−k+1 ) needs to be buffered until the error values are computed and ready. However, buffering causes the required overall latency and the number of logic elements used to increase. 
     For additional background information evidencing the state of the art, reference may be had to  Error Control Coding: Fundamentals and Applications , Shu Lin and Daniel J. Costello, Jr., Prentice-Hall, Inc., Englewood Cliffs, N. J., 1983. Such reference is herein incorporated by reference as evidencing the present state of the art. 
     For yet additional background information pertaining to extended Reed-Solomon Codes, reference may be had to The Decoding of Extended Reed-Solomon Codes,  Discrete Mathematics  90 (1991), pp. 21-40, A. Dür, North-Holland. Such reference is herein incorporated by reference as evidencing the present state of the art. 
     Therefore, additional needs exist to reduce the overall latency and the number of logic elements needed when implementing a singly-extended Reed-Solomon decoder. 
     SUMMARY OF THE INVENTION 
     In accordance with the present invention, error correction of an extended symbol in a singly-extended Reed-Solomon decoder is implemented using existing error detection logic elements. The fundamental principles of this invention are that an encoded extended-symbol (c_) is generated by evaluating the encoded codeword, c(x), for α (n−k+1) . The final encoded codeword, {tilde over (c)}=[c_c], is transmitted to a standard RS decoder which is used to correct the received input codeword, {tilde over (r)}=[r_r], excluding the extended symbol, r_. By computing the syndromes of the intermediate output codeword (c′ j ) of the standard RS decoder, it turns out that the corrected extended-symbol (c_) is in the (S n−k+1 ) output syndrome register and is latched on the (n− 1 )th (one before the last) clock cycle. During the (n)th (last) clock cycle, the corrected extended-symbol (c_) is multiplexed with the intermediate output codeword (c′ j ) to yield the final output codeword, {tilde over (c)}=[c_c]. 
     The goal of this invention is to make use of existing error detection logic while minimizing latency and hardware requirements. For example, a 3 m 2×1 multiplexer can be used with 2 m registers to correct the received extended-symbol. 
     According to one aspect of the invention, an extended symbol Galois field error correcting device is provided. The device includes a singly-extended Reed-Solomon encoder configured to generate an encoded codeword, {tilde over (c)}(x). The device also includes a channel medium that is signal coupled with the singly-extended Reed-Solomon encoder. The channel medium is configured to receive the encoded codeword, {tilde over (c)}(x), and output a received input codeword, {tilde over (r)}(x). The channel medium is capable of introducing error, {tilde over (c)}(x), to the encoded codeword, {tilde over (c)}(x). The device further includes a singly-extended Reed-Solomon decoder that is coupled with the channel medium. The singly-extended Reed-Solomon decoder is configured to receive the received input codeword, {tilde over (r)}(x). The singly-extended Reed-Solomon decoder has error detection circuitry and extended symbol correction circuitry. The error detection circuitry is configured to detect presence of error, {tilde over (e)}(x), within the received input codeword, {tilde over (r)}(x). The extended symbol correction circuitry is configured to correct the received input codeword, {tilde over (r)}(x), by computing syndromes of an intermediate output codeword (c′ j ). A corrected extended parity symbol (c_) is provided such that the corrected extended symbol (c_) is multiplexed with the intermediate output codeword (c′ j ) to yield a final output codeword, {tilde over (c)}=[c_c′]. 
     According to another aspect of the invention, a Reed-Solomon decoder is provided. The Reed-Solomon decoder includes error detection circuitry configured to receive an input codeword and operative to detect presence of error within the input codeword. The Reed-Solomon decoder also includes extended symbol correction circuitry that is coupled with the error detection circuitry and configured to correct the input codeword by computing syndromes of an intermediate output codeword. Furthermore, the Reed-Solomon decoder includes a multiplexer that is associated with the extended symbol correction circuitry. The extended symbol correction circuitry causes a corrected extended parity symbol to be provided in an output syndrome register associated with an (n−1)th clock cycle such that, during the (n)th clock cycle, the corrected extended parity symbol is multiplexed with the intermediate output codeword to yield a final output codeword. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Preferred embodiments of the invention are described below with reference to the following accompanying drawings. 
     FIG. 1 illustrates in block diagram form one preferred structure of a typical data transmission system having an error correcting and detecting system constructed in accordance with this invention. 
     FIG. 2 illustrates in greater detail a general singly-extended Reed-Solomon decoder architecture usable with the structure depicted in FIG.  1 . 
     FIG. 3 illustrates a logic diagram of a singly-extended RS(n+1,k) decoder error detection and extended symbol correction output detection circuit. 
     FIG. 4 illustrates a logic diagram of one instance of a singly-extended RS(8,4) decoder error detection and extended symbol correction output detection circuit. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     This disclosure of the invention is submitted in furtherance of the constitutional purposes of the U.S. Patent Laws “to promote the progress of science and useful arts” (Article 1, Section 8). 
     FIG. 1 is a schematic block diagram view illustrating a typical data transmission system utilizing Applicant&#39;s invention and designated generally with reference numeral  10 . Data transmission system  10  is understood to encompass the transmission and storage of digital information between an information source  12  and a destination  14 . According to one configuration, information source  12  comprises a digital computer. Alternatively, information source  12  comprises an individual or a machine. According to one implementation, destination  14  comprises a digital computer. Alternatively, destination  14  comprises an individual or a machine. 
     As shown in FIG. 1, data transmission system  10  includes a singly-extended Reed-Solomon encoder  16 , a singly-extended Reed-Solomon decoder  18 , and a channel medium  20 . Channel medium  20  comprises any one of a number of transmission channels, such as telephone lines, telemetry links, high-frequency radio links, microwave links, satellite links, bus links, and storage medium. Examples of storage medium include core and semiconductor memories, drums, magnetic tapes, disk files, optical memory units, and so on. 
     In operation, each of the above types of channel medium is subject to potential noise disturbances. For example, on a telephone line, disturbances may result from switching impulse noise, cross-talk from other lines, thermal noise, or lightning. Accordingly, a noise source  22  is represented in FIG. 1 as introducing noise, {tilde over (e)}(x), into channel medium  20 . 
     As shown in FIG. 1, singly-extended Reed-Solomon encoder  16  encodes data words, or messages, in the form of information polynomials, I(x), emanating from information source  12 , as described below in further detail with reference to equation (2). The encoded data words are then transferred through channel medium  20  to destination  18  by way of singly-extended Reed-Solomon decoder  18 . In the process of being transferred through channel medium  20 , noise can be introduced via channel medium  20 . It is understood that singly-extended Reed-Solomon encoder  16  includes a standard Reed-Solomon encoder placed in series with an extended symbol generator. 
     As shown in FIG. 1, singly-extended Reed-Solomon encoder  16  receives information, or message, polynomial, I(x). In response, singly-extended Reed-Solomon encoder  16  outputs an extended codeword {tilde over (c)}(x) to channel medium  20 . Channel medium  20  then outputs a received input codeword {tilde over (r)}(x) to singly-extended Reed-Solomon decoder  18 . Finally, singly-extended Reed-Solomon decoder  18  outputs the final encoded codeword {tilde over (c)}(x) to destination  14 . 
     As shown in FIG. 1, singly-extended Reed-Solomon encoder  16  is implemented with Reed-Solomon error correcting codes that are defined over the Galois Field GF(2 m ) using a generator polynomial for a Reed-Solomon code as described below in greater detail with reference to equation (1). Such a generator polynomial is described in greater detail in S. Lin, D. J. Costello, Error Control Coding:  Fundamentals and Applications , New Jersey, Prentice-Hall, 1983, incorporated herein by reference as illustrating the state of the art. 
     FIG. 2 illustrates in greater detail the architecture for one implementation of singly-extended Reed-Solomon decoder  18  as used within the data transmission system  10  of FIG.  1 . More particularly, a general singly-extended Reed-Solomon decoder architecture is illustrated for decoder  18  in three stages; namely, “STAGE 1”, “STAGE 2” and “STAGE 3”. 
     In “STAGE 1”, received input codeword, {tilde over (r)}=[r_r], is input into syndrome computation circuitry  24 . An output signal comprising the syndrome values (s 1 , s 2 , . . . , s n−k+1 ) from circuitry  24  is then delivered to standard error values computation circuitry  26  within “STAGE 2”. Additionally, the syndrome computation circuitry  24  generates a “NO-ERROR” signal that is input to “STAGE 2” and “STAGE 3”. 
     In “STAGE 2”, standard error values computation circuitry  26  receives the output signal comprising the syndrome values (s 1 , s 2 , . . . , s n−k+1 ) and generates output signals comprising calculated error values, e j , for j=0, 1, . . . , (n−1), and an “ERR_EN” signal which will be discussed below in greater detail. “STAGE 2” includes a buffer  28 . Calculated error values, e j , are input into an array of m (where m is the number of data bits) 2-input “exclusive-or” (XOR) gates  40  within “STAGE 2”. The “ERR_EN” signal is input into circuitry  30  within “STAGE 3”. Additionally, XOR gate  40  receives the received vector symbols, {circumflex over (r)} j  for j=0, 1, . . . , n. XOR gate  40  generates an intermediate output codeword c′ j  that is input to “STAGE 3”. 
     In “STAGE 3”, processing circuitry  30  receives a “NO_ERROR” signal, an “ERR_EN” signal and intermediate output codeword c′ j . As discussed below in greater detail, processing circuitry  30  includes error detection circuitry and extended symbol correction circuitry that cooperate to generate “CORR_ERROR” and “UNCORR_ERROR” signals. “STAGE 3” also includes an array of m-bit flip-flops  36  which provides a hardware register for latching intermediate output codeword c′ j . Processing circuitry  30  also generates an “EXT_EN” signal and an encoded extended symbol c_ using equation (9) as described in greater detail below. The corrected extended symbol c_ is provided in an (s −k+1 ) output syndrome register within the processing circuitry  30  (see FIG.  3 ), and is latched onto the (n−1)th (one before the last) clock cycle using the “ERR_EN” signal within processing circuitry  30  (see FIG.  3 ). During the (n)th (last) clock cycle, the corrected extended symbol, c_, is multiplexed via multiplexer  38  with the intermediate output codeword c′ j  using the “EXT_EN” signal to yield the corrected extended symbol. The resulting output codeword is {tilde over (c)}. 
     FIG. 3 illustrates in greater detail the logic diagram of the processing circuitry  30 , comprising the error detection circuitry and the extended symbol correction circuitry, for the singly-extended Reed-Solomon (RS) decoder  18  of FIG.  2 . More particularly, the logic diagram of an RS(n+1,k) decoder error detection and extended symbol correction apparatus is illustrated in FIG.  3 . FIG. 4 shows one instance for a singly-extended RS(8,4) error detection and extended symbol correction apparatus. 
     As shown in FIGS. 3 and 4, circuitry  30  includes an array of XOR gates  40  operatively associated with respective GF(2 m ) constant multipliers  42  and discrete flip-flops (DFF)  44 . Such a generator polynomial is described in greater detail in S. Lin, D. J. Costello, Error Control Coding:  Fundamentals and Applications , New Jersey, Prentice-Hall, 1983, previously incorporated herein by reference. Additionally, the logic circuitry of circuitry  30  includes an array of associated OR gates  46 , NOR gates  48  and  50 , AND gate  52 , 2×1 multiplexer with a flip-flop (MXFF)  54  and an m-bit 2×1 MXFF  56  and NOT gate  58 . 
     As shown generally above in FIGS. 1-4, Applicant&#39;s invention is related to the error correction of an extended symbol in a singly-extended Reed-Solomon (RS) decoder using existing error detection logic elements for forward error correction applications. An encoded extended-symbol (c_) is generated by evaluating the encoded codeword, c(x), at the (n−k+1) power of α. The final encoded codeword, {tilde over (c)}=[c_c], is transmitted to a standard RS decoder which is used to correct the received input codeword, {tilde over (r)}=[r_r], excluding the received extended-symbol, r_. By computing the syndromes of the intermediate output codeword (c′ j ) of the standard RS decoder, it turns out that the corrected extended-symbol (c_) is in the (s n−k+1 ) output syndrome register and is latched on the (n−1)th (one before the last) clock cycle. During the (n)th (last) clock cycle, the corrected extended-symbol (c_) is multiplexed with the intermediate output codeword (c′ j ) to yield the final output codeword, {tilde over (c)}=[c_c′], as shown by multiplexer  38  (of FIG.  2 ). 
     In prior art applications, the extended error value (e_) in the extended received-symbol (r_) is calculated by adding the syndrome (s n−k+1 ) of the received input codeword to the computed error values coming out of the RS decoder. That is,          e   _     =       s     n   -   k   +   1       +       ∑     j   =   0       n   -   1              e   j          α     j        (     n   -   k   +   1     )                                      
     However, since the syndrome value (s n−k+1 ) needs to be buffered until the error values are computed and ready, the required overall latency and the logic elements will increase. One goal of Applicant&#39;s invention is to use the existing error detection logic of FIGS. 3 and 4 with no added latency and minimal hardware (3 m 2×1 multiplexer and 2 m registers) to correct the received extended-symbol. As shown in greater detail below, a novel algorithm is given for the generalization of any singly-extended RS(n+1, k) decoder followed by several examples. 
     Algorithm and Architecture 
     Let GF(2 m ) be the finite field of 2 m  elements. Also, let n=2 m −1. The RS error correcting codes are defined over the Galois Field GF(2 m ). 
     A. Singly-Extended Reed-Solomon Encoder 
     The singly-extended Reed-Solomon encoder consists of a standard Reed-Solomon encoder and extended parity symbol generation circuitry. 
     I. Standard Reed-Solomon Encoder 
     A generator polynomial for a Reed-Solomon (RS) code is given as                g        (   x   )       =       ∏     i   =   1       n   -   k            (     x   +     α   i       )               (   1   )                                
     The information (message) polynomial, i(x), input to the encoder consists of k, m-bit symbols, and is described in greater detail in S. Lin, D. J. Costello, Error Control Coding:  Fundamentals and Applications , New Jersey, Prentice-Hall, 1983, already incorporated herein by reference.                i        (   x   )       =       ∑     j   =   0       k   -   1                         i   j          x   j                 (   2   )                                
     The remainder polynomial, p(x), is obtained by:                p        (   x   )       =         i        (   x   )       ·     x     n   -   k           g        (   x   )                 (   3   )                                
     The remainder polynomial can be rewritten as:                p        (   x   )       =       ∑     j   =   0       n   -   k   -   1              p   j          x   j                 (   4   )                                
     The remainder constitutes (n−k) parity (checkbytes) symbols which are added to the information polynomial i(x) to form an n symbol codeword c(x):                c        (   x   )       =         x     n   -   k              ∑     j   =   0       k   -   1              i   j          x   j           +       ∑     j   =   0       n   -   k   -   1              p   j          x   j                   (   5   )                 c        (   x   )       =       ∑     j   =   0       n   -   1              c   j          x   j                 (   6   )                                
     Using equation (6), a valid codeword will have roots at the first through the (n−k) power of α. Using equation (5), the encoder transmits the encoded symbols in the following vector order: 
     
       
         c=[p 0 p 1  . . . p n−k−2 p n−k−1 i 0 i 1  . . . i k−2 i k−1 ]  (7) 
       
     
     or using equation (6), the following result is produced: 
     
       
         c=[c 0 c 1  . . . c n−2 c n−1 ]  (8) 
       
     
     The order of transmission is right to left. 
     II. Extended Parity Symbol Generation 
     An extended parity symbol (c_) is generated by evaluating the codeword c(x) using equation (6) at the (n−k+1) power of α. 
     
       
         c_=c(α n−k+1 )  (9) 
       
     
     This extended symbol produces a singly-extended RS(n+1,k) code and is used to form the last symbol of a transmitted RS codeword having a length of (n+1). The extended codeword then appears as follows: 
     
       
         {tilde over (c)}(x)=x ·c(x)+c —   (10) 
       
     
     Using equations (5) and (10), the encoder transmits the enclosed symbols in the following vector order: 
     
       
         {tilde over (c)}=[c_p 0 p 1  . . . p n−k−2 p n−k−1 i 0 i 1  . . . i k−2 i k−1 ]  (11) 
       
     
     or using equations (7), (8), and (11), the following results: 
     
       
         {tilde over (c)}=[c_c 0 c 1  . . . c n−2 c n−1 ]=[c_c]  (12) 
       
     
     The order of the transmission is from right to left. 
     B. Standard Reed-Solomon Decoder 
     The error-correcting power of an RS(n, k) code is related to t=(n−k)/2 where t is number of bytes which can be corrected per codeword, the difference (n−k) is the number of checkbytes, n is the codeword length, and k is number of information bytes. The RS(n,k) code has a minimum distance of d min =(n−k)+1. 
     Assume that the codeword received by the RS decoder is: 
     
       
         r(x)=c(x)+e(x)  (13) 
       
     
     or                r        (   x   )       =       ∑     j   =   0       n   -   1              r   j          x   j                 (   14   )                                
     where e(x) is the error polynomial and is defined as:                e        (   x   )       =       ∑     j   =   0       n   -   1              e   j          x   j                 (   15   )                                
     r(x) and e(x) can be represented in their vector forms as: 
     
       
         r=[r 0 r 1  . . . r n−2 r n−1 ]  (16) 
       
     
     and 
     
       
         e=[e 0 e 1  . . . e n−2 e n−1 ]  (17) 
       
     
     The syndromes are calculated by evaluating equation (14) at α j , where α j  is an arbitrary Galois Field element: 
     
       
         s j =r(α j ) where j=1,2, . . . , (n−k)  (18) 
       
     
     For additional background information evidencing the state of the art, reference may be had to Error Control Coding:  Fundamentals and Applications , D. J. Costello, S. Lin, New Jersey: Prentice-Hall, 1983. Such reference is previously incorporated herein. 
     The other way of calculating the syndromes are by using a parity check matrix H which is given in terms of the roots of g(x) as 
     
       
         H=[α 0  α i  α 2i  . . . α (n−2)i  α (n−1)i ] where i=1, 2, . . . (n−k)  (19) 
       
     
     The H matrix for a standard RS code can further be expanded as:              H   =     [         1       α         α   2           ∘   ∘   ∘   ∘   ∘   ∘   ∘           α     n   -   1               1         α   2           α   4           ∘   ∘   ∘   ∘   ∘   ∘   ∘           α       (     n   -   1     )        2               ∘       ∘       ∘         ∘   ∘   ∘   ∘   ∘   ∘   ∘         ∘           ∘       ∘       ∘         ∘   ∘   ∘   ∘   ∘   ∘   ∘         ∘           1         α     n   -   k             α     2        (     n   -   k     )               ∘   ∘   ∘   ∘   ∘   ∘   ∘           α       (     n   -   1     )          (     n   -   k     )               ]             (   20   )                                
     For additional background information evidencing the state of the art, reference may be had to  On Decoding Doubly Extended Reed-Solomon Code , J. M. Jensen, Proceedings of the    1995   International Symposium on Information Theory, p. 280, September 1995; and  Time Domain Decoding of Extended Reed-Solomon Codes , L. L. Joiner, J. J. Komo, IEEE Transaction on Information Theory, pp. 238-241, 1996. Such references are herein incorporated by reference as evidencing the present state of the art. 
     The syndromes of a standard RS decoder are given as: 
     
       
         S=rH T =[S 1 S 2  . . . S n−k ]  (21) 
       
     
     Where H is the parity matrix and r is the received codeword given by equation (16). Once the syndromes are known, a standard RS decoder can be used to do the error correction, and to generate the output codeword, c j : 
      c j =r j +e j  where j=0,1, . . . , n−1  (22) 
     C. A Singly-Extended Reed-Solomon Decoder 
     Since the largest possible minimum distance for an RS(n,k) code is d min =(n−k)+1, RS codes are maximum-distance separable (MDS). Singly-extended RS codes retain the MDS property. That is, the minimum distance for RS decoders is d min &gt;2t+1. A singly-extended RS code is an (n+1,k) MDS code and as such the error correcting capability has increased with d min =(n−k)+2. The new length is a power of 2. 
     For additional background information evidencing the state of the art, reference may be had to  On MDS Extensions of Generalized Reed-Solomon Codes , G. Seroussi, R. M. Roth, IEEE Transaction on Information Theory, vol. IT-32, No. 3, pp. 349-354, May 1996; and The Decoding of Extended Reed-Solomon Codes,  Discrete Mathematics  90 (1991), pp. 21-40, A. Dür, North-Holland. The first reference above is herein incorporated by reference as evidencing the present state of the art. The second reference above has already been incorporated by reference herein. 
     Assume that the codeword received by the singly-extended RS decoder is: 
     
       
         {tilde over (r)}(x)={tilde over (c)}(x)+{tilde over (e)}(x)  (23) 
       
     
     or                  r   ~          (   x   )       =         ∑     j   =   0       n   -   1              r   j          x   j         +     r   _               (   24   )                                
     where {tilde over (e)}(x) is the error polynomial and is defined as:                  e   ~          (   x   )       =         ∑     j   =   0       n   -   1                         e   j          x   j         +   e_             (   25   )                                
     Using equations (16) and (17), {tilde over (r)}(x) and {tilde over (e)}(x) can be represented in their vector forms as: 
     
       
         {tilde over (r)}=[r_r 0 r 1  . . . r n−2 r n−1 ]=[r_r]  (26) 
       
     
     and 
     
       
         {tilde over (e)}=[e_e 0 e 1  . . . e n−2 e n−1 ]=[e_e]  (27) 
       
     
     where r is the received vector symbols and e is the error vector symbols. Also, r_ is the extended received symbol and e_ is the extended error symbol. 
     The syndromes of the singly-extended RS decoders are calculated using equation (18) along with the extended syndrome given below:                S     n   -   k   +   1       =     r_   +       ∑     j   =   0       n   -   1                         r   j          α     j        (     n   -   k   +   1     )                       (   28   )                                
     The singly-extended RS codes can be derived from the standard RS codes using the following discussions. The parity check matrix {tilde over (H)} for a singly-extended code is given as:                H   ~     =     [         O                               H                                                                                                               1       1         α     n   -   k   +   1             α     2        (     n   -   k   +   1     )               ∘   ∘   ∘   ∘   ∘   ∘   ∘           α       (     n   -   1     )          (     n   -   k   +   1     )               ]             (   29   )                                
     By using equation (20), the parity check matrix {tilde over (H)} can further be expressed as:                H   ~     =     [         0       1       α         α   2           ∘   ∘   ∘   ∘   ∘   ∘   ∘           α     n   -   1               0       1         α   2           α   4           ∘   ∘   ∘   ∘   ∘   ∘   ∘           α       (     n   -   1     )        2               ∘       ∘       ∘       ∘         ∘   ∘   ∘   ∘   ∘   ∘   ∘         ∘           ∘       ∘       ∘       ∘         ∘   ∘   ∘   ∘   ∘   ∘   ∘         ∘           0       1         α     n   -   k             α     2        (     n   -   k     )               ∘   ∘   ∘   ∘   ∘   ∘   ∘           α       (     n   -   1     )          (     n   -   k     )                 1       1         α     n   -   k   +   1             α     2        (     n   -   k   +   1     )               ∘   ∘   ∘   ∘   ∘   ∘   ∘           α       (     n   -   1     )          (     n   -   k   +   1     )               ]             (   30   )                                
     The syndromes of a singly-extended RS decoder arc given as 
     
       
         {tilde over (S)}={tilde over (r)}{tilde over (H)} T =[S 1  S 2  . . . S n−k  S n−k+1 ]  (31) 
       
     
     Where {tilde over (H)} is the parity matrix of a singly-extended RS decoder and {tilde over (r)} is the received codeword given by equation (26). Comparing the standard RS(n,k) code with the singly-extended RS(n+1, k) code, it can be seen that the singly-extended RS(n+1, k) code has one more extra syndrome namely S n−k+1  given by equation (28) or (31) and an extended error symbol, e_. 
     Once the syndromes, equations (18) and (28), have been calculated, a standard RS decoder can be used to decode a singly-extended RS(n+1, k) code except the extended symbol which is decoded using the following novel technique. 
     FIG. 2 shows a general architecture for a singly-extended RS(n+1, k) decoder. It consists of three stages. 
     Stage 1) Syndrome Computation 
     In this stage, the syndromes are computed using equations (18) and (28) and are fed to stage 2. If the syndromes are all zero, the no error, NO_ERROR, flag will be set. The ERR_EN will be active during the (n−1)th clock cycle if the NO_ERROR flag is not set. 
     Stage 2) Standard Error Calculations 
     In this stage, the error vector symbols, e j  for j=0, 1, . . . , (n−1), in the received vector symbols, r j  for j=0, 1, . . . , (n−1), are found using the standard RS decoder excluding the error value, e_, in the extended symbol, r_. The received codeword, {tilde over (r)}=[r_r], is delayed using a buffer and it is aligned with the calculated error values, e j . The intermediate output codeword c′ j  is obtained by: 
     
       
         c′ j =r j +e j  where j=0, 1, . . . , (n−1)  (32) 
       
     
     Stage 3) Calculation of the Error, e_, in the Extended Symbol, r —   
     FIG. 3 shows a general logic diagram of the output detection circuit which is modified for the calculation of the error, e_, in the extended symbol, r_. In this stage, the error value, e_, in the extended symbol, r_, is obtained by using the existing output detection logic elements. The procedure is as follows: 
     i) Calculate the syndromes (s 1 s 2  . . . s n−k s n−k+1 ) of the output codeword c′ j  for j=0, 1, . . . ,(n−1) using equation (31). 
     ii) Check the syndromes (s 1 s 2  . . . s n−k ) of the output codeword c′ j  on the (n−1)th (one before the last) clock cycle: 
     a) If the syndromes (s 1 s 2  . . . s n−k ) are all zero and the NO_ERROR flag is set, then there are no errors in the received codeword, {tilde over (r)} j  for j=0, 1, . . . ,n. That is {tilde over (e)} j  for j=0, 1, . . . ,n are all equal to zero. This condition causes the ERR_EN to stay inactive in order to keep the EXT_EN low (inactive). The resulting codeword output is: 
     
       
         {tilde over (c)}=[r_c′ 0 c′ 1  . . . c′ n−2 c′ n−1 ]  (33) 
       
     
     b) If the syndromes (s 1 s 2  . . . s n−k ) are all zero and the NO_ERROR flag is not set, the correctable error, CORR_ERROR, flag will be set to indicate that t or less errors may have been corrected in the received codeword, {tilde over (r)} j  for j=0, 1, . . . ,n, excluding the error value, e_, in the extended symbol, r_. By definition, the encoded extended symbol c_ using equation (9) was found to be c_=c(α n−k+1 ). This means that the corrected extended symbol c_ is in the (s n−k+1 ) output syndrome register and is latched on the (n−1)th (one before the last) clock cycle using the ERR_EN signal. During the (n)th (last) clock cycle, the corrected extended symbol, c_, is multiplexed with the intermediate output codeword c′ j  using the EXT_EN signal to yield the corrected extended symbol. The resulting output codeword is then: 
     
       
         {tilde over (c)}=[c_c′ 0 c′ 1  . . . c′ n−2 c′ n−1 ]  (34) 
       
     
     c) If the syndromes (s 1 s 2  . . . s n−k ) are not all zero, then the uncorrectable error, UNCORR_ERROR, flag will be set to indicate that the error(s) in the input codeword, {tilde over (r)} j , (excluding the error value, e_, in the extended symbol, r_) could not be corrected since there were more than t errors. This condition causes the ERR_EN to stay inactive in order to keep the EXT_EN low (inactive). In this case, the extended symbol would be the input codeword extended symbol r_. The final output codeword would then be: 
     
       
         {tilde over (c)}=[r_c′ 0 c′ 1  . . . c′ n−2 c′ n−1 ]  (35) 
       
     
     In the following section, several examples of singly-extended RS(8,4) code are given. FIG. 4 shows the logic diagram of the singly-extended RS(8,4) decoder output detection and extended symbol correction. The generator polynomial used in these examples is found using equation (1).                g        (   x   )       =         ∏     i   =   1     3                     (     x   +     α   i       )       =       (     x   +   α     )          (     x   +     α   2       )          (     x   +     α   3       )                 (   36   )                                
     The primitive polynomial used to form the GF(8) is ρ(x)=x 7 +x 3 +1 where ρ(α)=0. 
     Suppose that the information polynomial is 
     
       
         i(x)=x 3   (37) 
       
     
     Using equation (3), the remainder polynomial can be found as 
     
       
         p(x)=αx 2 +x+α 2   (38) 
       
     
     Using equation (5), the input codeword is: 
     
       
         c(x)=x 6 +αx 2 +x+α 2   (39) 
       
     
     Using equations (9) and (39), the extended symbol is: 
     
       
         c_=c(α 3 )=α 6   (40) 
       
     
     This extended symbol is used to form the last symbol of a transmitted Reed-Solomon codeword having length of 8 which produces an RS(8,4) code. Using equation (10), the extended codeword then appears as follows: 
     
       
         {tilde over (c)}(x)=x 7 +αx 3 +x 2 +α 2 x+α 6   (41) 
       
     
     or in vector form using equation (12) (the order of transmission is from right to left): 
     
       
         {tilde over (c)}=[α 6 α 2 1α0001]  (42) 
       
     
     EXAMPLES 
     Case 1) A singly-extended RS(8,4) Code with No Error 
     Suppose that the received codeword vector by the Reed-Solomon decoder is {tilde over (r)}=[α 6 α 2 1α0001]. Using equations (18) and (28), the syndromes are calculated as s 1 =s 2 =s 3 =s 4 =0. Since the syndromes are all zero, there are no errors in the input codeword and hence the NO_ERROR flag will be set. Similarly, the syndromes for the intermediate output codeword excluding the extended symbol are zero, which indicates that at most 2 or less errors may have been corrected. However, since the NO_ERROR flag is already set, the ERR_EN will be inactive to keep the EXT_EN low (inactive). In this case, the correct extended symbol, r_=α 6 , is the received codeword extended symbol which is appended to the intermediate output codeword, c′=[α 2 1α0001]. The final output codeword using equation (33) is {tilde over (c)}=[α 6 α 2 1α0001]. 
     Case 2) A singly-extended RS(8,4) Code with 1 Error 
     Suppose that the received codeword vector by the Reed-Solomon decoder is {tilde over (r)}=[α 4 α 2 1α0001]. Using equations (18) and (28), the syndromes are calculated as s 1 =0; s 2 =0; s 3 =0; s 4 =α 3  which means that there are errors in the input codeword. Similarly, the syndromes for the intermediate output codeword excluding the extended symbol are all zero which indicates that at most 2 or less errors have been corrected. Since the NO_ERROR flag is not set, the CORR_ERROR and the ERR_EN flags will both be set during the 7 th  clock cycle. The extended symbol, c_=α 6 , which is in the s 4  syndrome register will be multiplexed with the intermediate output codeword, c′=[α 2 1α0001], using the EXT_EN signal during the 8 th  clock cycle. The final output codeword using equation (34) is {tilde over (c)}=[α 6 α 2 1α0001]. 
     Case 3) A singly-extended RS(8,4) Code with 2 Errors 
     Suppose that the received codeword vector by the Reed-Solomon decoder is {tilde over (r)}=[α 4 α 2 1α000α]. Using equations (18) and (28), the syndromes arc calculated as s 1 =α 2 ; s 2 =α; s 3 =1; s 4 =α 4  which means that there are errors in the input codeword. Similarly, the syndromes for the intermediate output codeword excluding the extended symbol are all zero which indicates that at most 2 or less errors may have been corrected. Since the NO_ERROR flag is not set, the CORR_ERROR and the ERR_EN flags will both be set during the 7 th  clock cycle. The extended symbol, c_=α 6 , which is in the S 4  syndrome register will be multiplexed with the intermediate output codeword, c′=[α 2 1α0001], using the EXT_EN signal during the 8 th  clock cycle. The final output codeword using equation (34) is {tilde over (c)}=[α 6 α 2 1α0001]. 
     Case 4) A singly-extended RS(8,4) Code with 3 Errors 
     Suppose that the received codeword vector by the Reed-Solomon decoder is {tilde over (r)}=[α 4 α 2 αα000α]. Using equations (18) and (28), the syndromes are calculated as s 1 =α; s 2 =α 6 ; s 3 =α 2 ; s 4 =α 5  which means that there are errors in the input codeword. Similarly, the syndromes for the intermediate output codeword excluding the extended symbol are s 1 =α; s 2 =α 6 ; s 3 =α 2 ; s 4 =1 which indicates that more than 2 errors exist in the input codeword. The ERR_EN stays inactive in order to keep the EXT_EN low (inactive). In this case, the UNCOR_ERROR flag will be set. The extended symbol, r_=α 4 , is the received codeword extended symbol which is appended to the intermediate output codeword, c′=[α 2 αα000α]. Using equation (35), the final output codeword is {tilde over (c)}=[α 4 α 2 αα000α]. 
     In compliance with the statute, the invention has been described in language more or less specific as to structural and methodical features. It is to be understood, however, that the invention is not limited to the specific features shown and described, since the means herein disclosed comprise preferred forms of putting the invention into effect. The invention is, therefore, claimed in any of its forms or modifications within the proper scope of the appended claims appropriately interpreted in accordance with the doctrine of equivalents.