Parallel signal decoding method

Details Parallel signal decoding method Parallel signal decoding method

2000-06-22

2004-02-17

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S785000, C714S769000

Reexamination Certificate

active

06694473

ABSTRACT:

This application incorporates by reference Taiwanese application serial No. 88112056, filed Jul. 16, 1999, of which this application is a translation.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates in general to a decoding method, and more particularly to a method of decoding coded data in parallel processing and pipeline mode.
2. Description of the Related Art
As computer technology is progressing, people have more demand on the products derived from it. The processing rate performed by the computers become faster and faster. People depend much more on computers for processing a large amount of data and executing complicated software. Therefore, people have more demand on data storage media, for example, floppy disks, compact disks (CDs), hard disks.
It is sometimes possible that data storage media may suffer from physical damage, for example, scratches, during production or use. In order to handle erroneous data and/or loss data due to damage of the data storage media, or pollution, data storage in data storage media such as compact disks is complete through a series of coding operations on the incoming data. The coding and the corresponding decoding operations effectively provide a way to minimize the effects of an error on the disk. Generally, the incoming user data is divided into a series of data units. The coding operations add a number of parity codes to each data unit for error-detection and correction codes purposes. Additionally, interleaving technique is involved in the coding operations for the enhancement of the error-correction probability by scrambling the coded data (i:e. a selection of data in a data unit is distributed over multiple data units). Furthermore, a number of codes for different functions, such as synchronization code, control code and protection code, are added to the resulting data unit. Thus, resulting coded data units are obtained as basic data units that are actually stored into the data storage media.
Therefore, when basic data units stored in the data storage media are read, a series of decoding operations are performed on the basic data units, resulting in the original user data. During decoding operations, the erroneous data due to reading error or damage to the media are detected and corrected according to the corresponding error-detection and correction method, which uses the parity codes, and the scrambled coded data are de-interleaved. By the decoding operations, the effects of an error on the disk are minimized.
The encoding of CD-read only memory (CD-ROM) information is governed by International Standard Organization (ISO)/IEC 10149, which is an extended specification of the CD-digital audio. Their relationship and the encoding and decoding method that the CD-ROM format based on are also disclosed in the U.S. Pat. Nos. 4,413,340 and 4,680,764.
As a brief summary of the encoding operations according to the CD-ROM format, when the user data other than digital audio are stored in a CD-ROM, the user data are encoded through a series of encoding operations, namely C
3
encoding, C
2
encoding, interleaving, and C
1
encoding. After the encoding operations, a series of encoded data units are obtained which are stored in the CD-ROM. The interleaving operation repartitions frames of C
2
coded data into different frames for C
1
encoding. After interleaving, if data is damaged, the damaged data is dispersed among different frames of the decoded data, and thus correction probability is enhanced.
Therefore, when data units are read from a CD-ROM, the following decoding operations are performed on the data units respectively: C
1
decoding, deinterleaving, C
2
decoding, and C
3
decoding, whereby deinterleaving is a reversed operation of interleaving.
As mentioned above, the encoding operations provide a way of error detection and correction in order to minimize the effects of erroneous data on the data storage media. Since the development of information theory and coding theory in 1948, numerous types of error-correcting systems have been created and developed. As implementations of the encoding and decoding methods arises, the data storage media or communication systems are developed into products which are reliable and efficient.
The first error-correcting system corrected a single bit in error in a group of bits. Shortly thereafter, error-correcting systems were developed to correct a single burst of bit errors in a block of bits. Error-correcting systems operate on data either as a set of bits or as a set of bytes, where the number of bits per byte is normally 8, but can be any number greater than 1. Error-correcting systems that operate on bits are called binary error-correcting systems and those that operate on bytes are called non-binary error-correcting systems. Early error-correcting systems are examples of binary systems.
Non-binary error-correcting systems were implemented after the invention in 1968 of an iterative algorithm to solve the key decoding equation known as the Berlekamp-Massey algorithm in honor of its inventors. Since 1968, several other iterative algorithms have been invented to solve the key decoding equation. In addition, algorithms, which operate on matrices, have been developed to solve the key decoding equation. Some decoding methods do not use the key decoding equation.
One of the most commonly used non-binary error-correcting schemes is known as Reed-Solomon Code, and was first described in “Polynomial codes over certain finite fields”, Reed I. S and Solomon G, Journal of Society of Industrial Application Mathematics 8, 300-304 (1960). The basic concepts of Reed-Solomon coding are now well known to those of ordinary skill in the art. Many attempts have been made by the art to improve the basic Reed-Solomon system. In addition, many disclosures for preparing an encoder and/or decoder for Reed-Solomon codes arise. For example, Reed-Solomon encoders and decoders are disclosed in U.S. Pat. Nos. 5,600,659 and 5,711,244. The Reed-Solomon codes are widely used in magnetic disk drives, optical disk drives, magnetic tape drives and in communications systems.
Nearly all conventional Reed-Solomon error-correcting systems are implemented such that most of the encoding and decoding operations are performed in a serial byte-by-byte fashion. Some Reed-Solomon implementations solve the key decoding equation in a parallel fashion, but nearly all implementations of Reed-Solomom error-correcting system encode incoming data serially, generate the syndrome serially and determine the most-likely error pattern serially. Thus, it leads to limit performance. Some prior Reed-Solomon error-correcting systems correct errors only, some correct erasures only and some correct both errors and erasures. (An error is a byte in error about which no information is known. An erasure is a byte that is likely to be in error and the location is known by the decoder before decoding begins. In the invention, an erasure is referred to as a byte failure location.)
In prior Reed-Solomon error-correcting systems that use byte failure location information, this information is transmitted directly from the transmission or storage channel(s) to the decoder. These systems require an entire block of data to be received before decoding can begin, so, data buffer must be provided for storing at least one block of data. For example, in disk array systems where the error-correction system within each disk drive is used to indicate a failed drive, an entire sector of data must be read from each disk in the array before byte failure location information can be determined.
Error correcting scheme of compact disks is based on Reed-Solomon codes. The error correction codes used in compact disks are called cross-interleaved Reed-Solomon codes (CIRC) because of the uses of interleaving technique. For the encoding and decoding of computer data in CD-ROM, see the ISO/IEC 10149 mentioned above for more details. The basic data units stored in CD-ROM are logically viewed as logical blocks, called sectors. One sector on a CD-ROM contains 98 frame

Affiliated with

Also associated with

Rating

Parallel signal decoding method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Parallel signal decoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel signal decoding method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3341044