Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
2000-06-26
2002-10-29
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
Reexamination Certificate
active
06473010
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and apparatus for determining the Error Correction Code (ECC) failure rate or probability of iterative decoding algorithms. The invention further relates to a program of instructions (e.g., software) for implementing the method.
BACKGROUND OF THE INVENTION
The performance of digital communication and storage systems can be significantly improved by the use of error correction coding. As a result, most, if not all, such systems use some form of error correction coding, which generally involves systematically adding redundant bits to each block of data as insurance against read/write errors. A given ECC can recover the original data from a contaminated block if the number of erroneous bits is less than the maximum number allowed by that particular code.
In the magnetic recording industry, different error correction coding and detection schemes are compared against each other by considering both the bit error rate (BER) versus signal-to-noise (SNR) curves and the ECC failure probability. The BER provides useful information as to the frequency of errors. However, since the data is encoded using an ECC, the true goal is to minimize the ECC failure probability rather than the BER itself. Therefore, one needs to compare not only the frequency of errors (which is reflected by the BER) but also the types and magnitudes of errors that occur. If scheme A has fewer errors overall than scheme B, but the probability of a large error burst is higher for A than for B, then the ECC failure rate may be higher for A than for B.
For systems in which an output BER below 10
−10
is desirable, ECCs, such as Reed-Solomon (RS) codes, are usually concatenated with convolutional codes. In recent years, convolutional codes have been replaced by iterative codes to deliver the required BER. Since an iterative decoding algorithm is required to decode such iterative codes, the failure probability of the ECC is based on the error characteristics of the decoding algorithm. While iterative codes such as turbo codes and low-density parity-check (LDPC) codes have shown very good performance for communication systems at output BERs of 10
−3
to 10
−7
, performance is much less certain at output BERs below 10
−10
. Moreover, bit-by-bit simulation of systems with an output BER below 10
−10
is difficult due to the fact that the number of bits that need to be processed is too large.
Due to such difficulty, the ECC failure probability of iterative decoding algorithms are typically not known until after the integrated circuit implementing the decoding algorithm has been fabricated. Having to construct the decoding circuit before the effectiveness of the underlying decoding algorithm is known can be both time-consuming and costly.
SUMMARY OF THE INVENTION
It is therefore an object of this invention to overcome the above-mentioned problems.
It is another object of this invention to provide a design-based tool capable of estimating ECC failure probabilities in the BER range below 10
−10
of iterative decoding algorithms to determine the ECC failure performance of a particular algorithm by modeling it before the circuit implementing the algorithm is fabricated.
It is a further object of this invention to provide a program of instructions embodied on a device-readable medium for implementing such a design-based tool.
According to one aspect of the invention, a method is provided for determining error correction code failure probability of an iterative decoding algorithm for a pre-selected range of signal-to-noise ratio values and a pre-selected interleaved error correction code. The method comprises the steps of: determining a signal-to-noise ratio value range where a bit error rate of the iterative decoding algorithm with respect to signal-to-noise ratio defines an error floor region; determining a probability P
dmin
of a minimal distance error event occurring in the decoding algorithm for at least one signal-to-noise ratio value within the previously-determined signal-to-noise ratio value range; determining probability w
i
that a minimal distance error event corrupts i bytes in the same interleave of the pre-selected error correction code; and determining the error correction code failure probability for the signal-to-noise ratio value range determined in step (a) based on the previously determined probabilities P
dmin
and w
i
.
In addition to defining an error floor region, the bit error rate of the iterative decoding algorithm with respect to signal-to-noise ratio further defines a steep drop region and a transitional region, where the signal-to-noise ratio value range of the error floor region is greater than a signal-to-noise ratio value range of the transitional region which is greater than a signal-to-noise ratio value range of the steep drop region.
Preferably, the step of determining P
dmin
comprises determining a probability P
dmin
of a minimal distance error event occurring in the decoding algorithm for a plurality of signal-to-noise ratio values within the previously-determined signal-to-noise ratio value range. This determining step also preferably comprises determining a minimum Hamming weight of error events of the decoding algorithm d
min
and multiplying the probability P
dmin
by d
min
.
Another aspect of the invention involves an apparatus for determining error correction code failure probability of an iterative decoding algorithm for a pre-selected range of signal-to-noise ratio values and a pre-selected interleaved error correction code. The apparatus comprises various circuits for implementing the functions described above. These circuits may be physically distinct integrated circuits, or they may be embodied as a single integrated circuit.
In accordance with another aspect, the invention provides a device-readable medium embodying a program of instructions for execution by a device, such as a computer processor, for performing a method of determining error correction code failure probability of an iterative decoding algorithm for a pre-selected range of signal-to-noise ratio values and a pre-selected interleaved error correction code. The program of instructions comprises instructions for carrying out the steps of the above-described method.
Other objects and attainments together with a fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4630032 (1986-12-01), Gordon
patent: 5475388 (1995-12-01), Gormish
patent: 5805006 (1998-09-01), Sutardja et al.
Weishi Feng, et al. “On the Performance of Parity Codes in Magnetic Recording Systems”, IEEE Globecom 2000, pp 8-11.
T. Conway, “A new target response with parity coding for high density magnetic recording channels,”IEEE Trans. On Magnetics, vol. 34, No. 4, pp. 2382-2386, Jul. 1998.
H. Sawaguchi and S. Mita, “Soft-output decoding for concatenated error correction in high-order PRML channels,” inProc. of IEEE International Conference on Communications (ICC)1999, Vancouver, Jun. 1999.
R. He and N. Nazari, “An analytical approach for performance evaluation of partial response systems in the presence of signal-Dependent medium noise,” inProc. of Globecom1999, Rio de Janeiro, Brazil, Dec. 1999.
Weisihi Feng, Andrei Vityaev, Greg Burd, Nersi Nazari, “On the Performance of Parity Codes in Magnetic Recording Systems, ”inIEEE Globecom2000.
Burd Greg
Vityaev Andrei
Wu Zining
Janofsky Eric B.
Katten Muchin Zavis & Rosenman
Marvell International Ltd.
Young Brian
LandOfFree
Method and apparatus for determining error correction code... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining error correction code..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining error correction code... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2921855