Dynamic magnetic information storage or retrieval – General processing of a digital signal – Data verification
Reexamination Certificate
2002-05-30
2004-06-29
Hudspeth, David (Department: 2651)
Dynamic magnetic information storage or retrieval
General processing of a digital signal
Data verification
C360S046000, C714S794000, C714S795000, C375S262000
Reexamination Certificate
active
06757122
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to data storage and/or communication systems. More particularly, the invention relates to the iterative soft and hard decoding of linear codes defined by the parity check matrices composed from submatrices with a cyclic property (circulants).
BACKGROUND OF THE INVENTION
Recently, various types of turbo codes have been proposed for communication channels and storage systems. Combined with a BCJR (Bahl, Cocke, Jelinek and Raviv) algorithm or a Soft-Output Viterbi Algorithm (SOVA) those codes provide flexible tradeoffs in complexity and Bit Error Rate (BER). But due to the high latency of the decoding process, turbo codes are inappropriate for extremely high speed communication and high-density magnetic recording applications.
Similar BER characteristics at the lower level of complexity can be also achieved by the use of the Gallager Low Density Parity Check (LDPC) codes defined by a parity check matrix with some small fixed number of ones in each column. Originally, the LDPC codes have been constructed by random choice of the parity check matrix, but such codes require very complex encoders and decoders in general. Despite tremendous progress in achieving BER characteristics using LDPC codes, the problems of implementation complexity were left aside until the current time. A significant insight into the nature of iterative decoding has been gained due to interpretation of the decoding algorithms in terms of belief propagation in graphical models, but these graphical models of message passing are used mainly for the illustrative purposes, and the complexity factors still dominate system architecture and design considerations, especially in extremely high speed applications such as magnetic recording. The high complexity of the existing schemes is a direct consequence of the fact that parity check matrices of the random LDPC codes do not have a regular structure, and therefore large amounts of memory and logic gates are required to build corresponding encoders and decoders.
The results of several studies of LDPC based communication and storage systems have been recently reported and several schemes based on random regular and irregular LDPC codes have been described. The irregular LDPCs have parity check matrices with multiple column weights and linearly dependant rows (deficient rank parity check matrix). These codes enable faster encoding since the dimension of the systematic form of the parity check matrix used to calculate parity bits turns out to be much smaller than the number of parity check equations used in decoding. However, the parity check matrix of an irregular code is still similar to the random structure of a Gallager LDPC. Another approach is the algebraic construction of LDPC codes using finite geometries. The finite geometry LDPC codes are quasi-cyclic and their encoders can be implemented using linear shift registers with feedback connections defined by the generator polynomial of the code. The resulting codes have been demonstrated to have excellent performance in AWGN, although their rates are still low for high data rate applications, and decoder complexities are somewhat high.
A class of structured high rate LDPC codes with orthogonal parities has been constructed from Kirkman triple systems. Both finite geometries and Kirkman systems are special classes of the Balanced Incomplete Block Designs (BIBD). Although many different types of the BIBD are described in the mathematical literature, not many of them give LDPC codes with high rates and sufficiently large minimum Hamming distances.
Therefore, the complexity issues remain to be the dominant factor that prevent the wide use of the LDPC based architectures, especially in extremely high speed applications such as magnetic recording. The high complexity of the existing schemes is a direct consequence of the fact that parity check matrices of the random LDPC codes do not have a regular structure, and therefore large amounts of memory and logic gates are required to build corresponding encoders and decoders. A proposed method of overcoming the problems of implementation complexity would be a significant improvement in the art.
SUMMARY OF THE INVENTION
The present invention provides a novel method and apparatus for decoding digital information transmitted through the communication channel or recorded on a recording medium. In some embodiments of the invention, the method and apparatus are applied in the systems where data is encoded using structured LDPC codes with parity check matrices composed from circulants (a matrix is called a circulant if all its columns or rows are cyclic shifts of each other). A class of such codes is constructed from integer lattices, and described later. A more complete understanding of the present invention, as well as other features and advantages of the present invention, may be obtained with reference to the following detailed description and accompanying drawings.
REFERENCES:
patent: 6185716 (2001-02-01), Riggle
Fan et al., Sep. 22-24, 1999, University of Illinois, “Thirty-Seventh Annual Allerton Conference on Communication, Control and Computing”, pp. 1315-1318.*
Z. Wu, “Coding and Iterative Detection for Magnetic Recording Channels,” The Kluwer International Series in Engineering and Computer Science, Chapter 3, pp. 47-65, Jan. 2000.
Y. Kou, S. Lin, and M. Fossorier, “Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results,” IEEE Transactions on Information Theory, vol. 47, No. 7, pp. 2711-2736, Nov. 2001.
R. G. Gallager, “Low-Density Parity-Check Codes,” Cambridge, Massachusetts, MIT Press, Jul. 1963.
B. Vasic, “Structured Iteratively Decodable Codes Based on Steiner Systems and Their Application in Magnetic Recording,” Globecom 2001, San Antonio, Texas, Nov. 2001.
J. Hagenauer and P. Hoeher, “A Viterbi Alorithm with Soft-Decision Outputs and its Applications,” Dallas GLOBECOM '89, pp. 1680-1686, Nov. 27-30, 1989.
L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory, vol. IT-20, No. 2, pp. 284-287, Mar. 1974.
J. L. Fan, A. Friedmann, E. Kurtas, and S. McLaughlin, “Low Density Parity Check Codes for Magnetic Recoding,” Thrity-seventh Annual Allerton Conference on Communication, Control and Computing, Monticello, Illinois, pp. 1314-1323, Sep. 22-24, 1999.
D. J. C. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices,” IEEE Transactions on Information Theory, vol. 45, No. 2, pp. 399-431, Mar. 1999.
T. Richardson, A. Shokrollahi, and R. Urbanke, “Design of Provably Good Low-Density Parity Check Codes,” 2000 IEEE International Symposium on Information Theory, pp. 199, Jun. 25-30, 2000.
R. M. Tanner, “Recursive Approach to Low Complexity Codes,” IEEE Transactions on Information Theory, vol. IT-27, No. 5, pp. 533-547, Sep. 1981.
Fan, J. L. “Constrained Coding and Soft Iterative Decoding”, Proceedings of the IEEE Information Theory Workshop 2001, Sep. 2, 2001, pp. 18-20.
Soljanin, E. “Simple Soft-Output Detection for magnetic Recording Channels”, Proceedings of the 2000 IEEE International Symposium on Information Theory ISIT 2000, Sorrento, Italy, Jun. 25-30, 2000, IEEE International Symposium on Information Theory, New York, NY, Jun. 25, 2000, p. 257.
Kurtas Erozan Mehmet
Kuznetsov Alexander Vasilievich
Vasic Bane
Hudspeth David
Rodriguez Glenda P.
Seagate Technology LLC
Westman Champlin & Kelly P.A.
LandOfFree
Method and decoding apparatus using linear code with parity... 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 decoding apparatus using linear code with parity..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and decoding apparatus using linear code with parity... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3320018