4413339 Multiple Error Detecting and Correcting System Employing Reed-Solomon Codes Jun81

This patent describes a system for the rapid detection and correction of multiple errors in digital data, particularly for high-speed data transfer and magnetic storage, using Reed-Solomon codes.

Key features and innovations include:

1. Reed-Solomon (1023, 1006) Code over GF(2^10): The system employs a Reed-Solomon code with 10-bit symbols, generated by primitive polynomials like x^10+x^3+1 or x^10+x^7+1. This allows for the correction of up to eight (T=8) 10-bit symbols and detection of nine or more.

2. Residue-Based Syndrome Computation:

   • During writing, an original data word (d(x)) is encoded to produce a code word (w(x)) with a set of checksum symbols (E(x)).
   • Upon retrieval, the received data symbols (c(x)) are re-encoded to produce a second set of checksum symbols (E2(x)).
   • Instead of dividing the entire received word for error detection, the system performs a modulo-two sum (exclusive-OR) of the stored checksums (E1(x)) and the newly generated checksums (E2(x)) to create a much shorter "residue" R(x).
   • Error syndromes (Si) are then computed directly from this residue R(x), significantly speeding up the initial error analysis compared to processing the entire received data word.

3. Intelligent Error Monitoring and Bypassing: An error monitor tracks the number of non-zero symbols (NR) in the residue R(x) to make rapid decisions:

   • If NR is less than or equal to T (e.g., 8), it indicates that any errors are confined to the checksum symbols and the data portion (c(x)) is correct. In this case, the data is immediately transferred, bypassing all time-consuming error correction routines.
   • If NR equals T+1, the error is deemed uncorrectable, and the system can attempt re-reads or abort the operation.
   • If NR is greater than or equal to T+2, it indicates potentially correctable errors in the data, prompting the initiation of the full error correction routine.

4. Optimized Single Error Detection: For fast correction of single symbol errors, the system includes a test to determine if the ratio Si+1/Si is constant across all syndromes. If true, a rapid, conventional single error correction algorithm is used.

Benefits:

• Speed: Significantly reduces the time required for error detection and correction by using a short residue R(x) for syndrome computation and by intelligently bypassing full decoding routines when not necessary.
• Efficiency: Economical implementation by allowing the encoder circuit to also function as the residue generator.
• Robustness: Effectively handles multiple, "bursty" errors common in magnetic storage devices.