Partial-response maximum-likelihood

Last updated

In computer data storage, partial-response maximum-likelihood (PRML) is a method for recovering the digital data from the weak analog read-back signal picked up by the head of a magnetic disk drive or tape drive. PRML was introduced to recover data more reliably or at a greater areal-density than earlier simpler schemes such as peak-detection. [1] These advances are important because most of the digital data in the world is stored using magnetic storage on hard disk or tape drives.

Contents

Ampex introduced PRML in a tape drive in 1984. IBM introduced PRML in a disk drive in 1990 and also coined the acronym PRML. Many advances have taken place since the initial introduction. Recent read/write channels operate at much higher data-rates, are fully adaptive, and, in particular, include the ability to handle nonlinear signal distortion and non-stationary, colored, data-dependent noise (PDNP or NPML).

Partial response refers to the fact that part of the response to an individual bit may occur at one sample instant while other parts fall in other sample instants. Maximum-likelihood refers to the detector finding the bit-pattern most likely to have been responsible for the read-back waveform.

Theoretical development

Continuous-time Partial-Response (class 4) and corresponding 'eye pattern' Class 4 Partial-Response Eye Diagram.jpg
Continuous-time Partial-Response (class 4) and corresponding 'eye pattern'

Partial-response was first proposed by Adam Lender in 1963. [2] The method was generalized by Kretzmer in 1966. Kretzmer also classified the several different possible responses, [3] for example, PR1 is duobinary and PR4 is the response used in the classical PRML. In 1970, Kobayashi and Tang recognized the value of PR4 for the magnetic recording channel. [4]

Maximum-likelihood decoding using the eponymous Viterbi algorithm was proposed in 1967 by Andrew Viterbi as a means of decoding convolutional codes. [5]

By 1971, Hisashi Kobayashi at IBM had recognized that the Viterbi algorithm could be applied to analog channels with inter-symbol interference and particularly to the use of PR4 in the context of Magnetic Recording [6] (later called PRML). (The wide range of applications of the Viterbi algorithm is well described in a review paper by Dave Forney. [7] ) A simplified algorithm, based upon a difference metric, was used in the early implementations. This is due to Ferguson at Bell Labs. [8]

Implementation in products

Early PRML chronology (created around 1994) PRML chronology circa 1994 (scanned Nov 1, 2019).pdf
Early PRML chronology (created around 1994)

The first two implementations were in Tape (Ampex - 1984) and then in hard disk drives (IBM - 1990). Both are significant milestones with the Ampex implementation focused on very high data-rate for a digital instrumentation recorder and IBM focused on a high level of integration and low power consumption for a mass-market HDD. In both cases, the initial equalization to PR4 response was done with analog circuitry but the Viterbi algorithm was performed with digital logic. In the tape application, PRML superseded 'flat equalization'. In the HDD application, PRML superseded RLL codes with 'peak detection'.

Tape recording

The first implementation of PRML was shipped in 1984 in the Ampex Digital Cassette Recording System (DCRS). The chief engineer on DCRS was Charles Coleman. The machine evolved from a 6-head, transverse-scan, digital video tape recorder. DCRS was a cassette-based, digital, instrumentation recorder capable of extended play times at very high data-rate. [9] It became Ampex' most successful digital product. [10]


The heads and the read/write channel ran at the (then) remarkably high data-rate of 117 Mbits/s. [11] The PRML electronics were implemented with four 4-bit, Plessey analog-to-digital converters (A/D) and 100k ECL logic. [12] The PRML channel outperformed a competing implementation based on "Null-Zone Detection". [13] A prototype PRML channel was implemented earlier at 20 Mbit/s on a prototype 8-inch HDD, [14] but Ampex exited the HDD business in 1985. These implementations and their mode of operation are best described in a paper by Wood and Petersen. [15] Petersen was granted a patent on the PRML channel but it was never leveraged by Ampex. [16]

Hard disk drives

In 1990, IBM shipped the first PRML channel in an HDD in the IBM 0681 It was full-height 5¼-inch form-factor with up to 12 of 130 mm disks and had a maximum capacity of 857 MB.

The PRML channel for the IBM 0681 was developed in IBM Rochester lab. in Minnesota [17] with support from the IBM Zurich Research lab. in Switzerland. [18] A parallel R&D effort at IBM San Jose did not lead directly to a product. [19] A competing technology at the time was 17ML [20] an example of Finite-Depth Tree-Search (FDTS). [21] [22]

The IBM 0681 read/write channel ran at a data-rate of 24 Mbits/s but was more highly integrated with the entire channel contained in a single 68-pin PLCC integrated circuit operating off a 5 volt supply. As well as the fixed analog equalizer, the channel boasted a simple adaptive digital cosine equalizer [23] after the A/D to compensate for changes in radius and/or changes in the magnetic components.

Write precompensation

The presence of nonlinear transition-shift (NLTS) distortion on NRZ recording at high density and/or high data-rate was recognized in 1979. [24] The magnitude and sources of NLTS can be identified using the 'extracted dipulse' technique. [25] [26]

Ampex was the first to recognize the impact of NLTS on PR4. [27] and was first to implement Write precompensation for PRML NRZ recording. 'Precomp.' largely cancels the effect of NLTS. [14] Precompensation is viewed as a necessity for a PRML system and is important enough to appear in the BIOS HDD setup [28] although it is now handled automatically by the HDD.

Further developments

Generalized PRML

PR4 is characterized by an equalization target (+1, 0, -1) in bit-response sample values or (1-D)(1+D) in polynomial notation (here, D is the delay operator referring to a one sample delay). The target (+1, +1, -1, -1) or (1-D)(1+D)^2 is called Extended PRML (or EPRML). The entire family, (1-D)(1+D)^n, was investigated by Thapar and Patel. [29] The targets with larger n value tend to be more suited to channels with poor high-frequency response. This series of targets all have integer sample values and form an open eye-pattern (e.g. PR4 forms a ternary eye). In general, however, the target can just as readily have non-integer values. The classical approach to maximum-likelihood detection on a channel with intersymbol interference (ISI) is to equalize to a minimum-phase, whitened, matched-filter target. [30] The complexity of the subsequent Viterbi detector increases exponentially with the target length - the number of states doubling for each 1-sample increase in target length.

Post-processor architecture

Given the rapid increase in complexity with longer targets, a post-processor architecture was proposed, firstly for EPRML. [31] With this approach a relatively simple detector (e.g. PRML) is followed by a post-processor which examines the residual waveform error and looks for the occurrence of likely bit pattern errors. This approach was found to be valuable when it was extended to systems employing a simple parity check [32] [33] [34]

PRML with nonlinearities and signal-dependent noise

As data detectors became more sophisticated, it was found important to deal with any residual signal nonlinearities as well as pattern-dependent noise (noise tends to be largest when there is a magnetic transition between bits) including changes in noise-spectrum with data-pattern. To this end, the Viterbi detector was modified such that it recognized the expected signal-level and expected noise variance associated with each bit-pattern. As a final step, the detectors were modified to include a 'noise predictor filter' thus allowing each pattern to have a different noise-spectrum. Such detectors are referred to as Pattern-Dependent Noise-Prediction (PDNP) detectors [35] or noise-predictive maximum-likelihood detectors (NPML). [36] Such techniques have been more recently applied to digital tape recorders. [37]

Modern electronics

Although the PRML acronym is still occasionally used, advanced detectors are more complex PRML operate at higher data-rates. The analog front-end typically includes AGC, correction for the nonlinear read-element response, and a low-pass filter with control over the high-frequency boost or cut. Equalization is done after the ADC with a digital FIR filter. (TDMR uses a 2-input, 1-output equalizer.) The detector uses the PDNP/NPML approach but the hard-decision Viterbi algorithm is replaced with a detector providing soft-outputs (additional information about the reliability of each bit). Such detectors using a soft Viterbi algorithm or BCJR algorithm are essential in iteratively decoding the low-density parity-check code used in modern HDDs. A single integrated circuit contains the entire read and write channels (including the iterative decoder) as well as all the disk control and interface functions. There are currently two suppliers: Broadcom and Marvell. [38]

See also

Related Research Articles

Hard disk drive Data storage device

A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magnetic material. The platters are paired with magnetic heads, usually arranged on a moving actuator arm, which read and write data to the platter surfaces. Data is accessed in a random-access manner, meaning that individual blocks of data can be stored and retrieved in any order. HDDs are a type of non-volatile storage, retaining stored data when powered off. Modern HDDs are typically in the form of a small rectangular box.

In telecommunication, a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of the encoder over the data, which gives rise to the term 'convolutional coding'. The sliding nature of the convolutional codes facilitates trellis decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity.

In telecommunication, intersymbol interference (ISI) is a form of distortion of a signal in which one symbol interferes with subsequent symbols. This is an unwanted phenomenon as the previous symbols have similar effect as noise, thus making the communication less reliable. The spreading of the pulse beyond its allotted time interval causes it to interfere with neighboring pulses. ISI is usually caused by multipath propagation or the inherent linear or non-linear frequency response of a communication channel causing successive symbols to blur together.

The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events, especially in the context of Markov information sources and hidden Markov models (HMM).

In information theory, turbo codes are a class of high-performance forward error correction (FEC) codes developed around 1990–91, but first published in 1993. They were the first practical codes to closely approach the maximum channel capacity or Shannon limit, a theoretical maximum for the code rate at which reliable communication is still possible given a specific noise level. Turbo codes are used in 3G/4G mobile communications and in satellite communications as well as other applications where designers seek to achieve reliable information transfer over bandwidth- or latency-constrained communication links in the presence of data-corrupting noise. Turbo codes compete with low-density parity-check (LDPC) codes, which provide similar performance.

Magnetic storage Storage of data in a magnetizable medium through encoded patterns of magnetization

Magnetic storage or magnetic recording is the storage of data on a magnetized medium. Magnetic storage uses different patterns of magnetisation in a magnetizable material to store data and is a form of non-volatile memory. The information is accessed using one or more read/write heads.

Voice activity detection (VAD), also known as speech activity detection or speech detection, is the detection of the presence or absence of human speech, used in speech processing. The main uses of VAD are in speech coding and speech recognition. It can facilitate speech processing, and can also be used to deactivate some processes during non-speech section of an audio session: it can avoid unnecessary coding/transmission of silence packets in Voice over Internet Protocol (VoIP) applications, saving on computation and on network bandwidth.

Perpendicular recording, also known as conventional magnetic recording (CMR), is a technology for data recording on magnetic media, particularly hard disks. It was first proven advantageous in 1976 by Shun-ichi Iwasaki, then professor of the Tohoku University in Japan, and first commercially implemented in 2005. The first industry-standard demonstration showing unprecedented advantage of PMR over longitudinal magnetic recording (LMR) at nanoscale dimensions was made in 1998 at IBM Almaden Research Center in collaboration with researchers of Data Storage Systems Center (DSSC) – a National Science Foundation (NSF) Engineering Research Center (ERCs) at Carnegie Mellon University (CMU).

In 1953, IBM recognized the immediate application for what it termed a "Random Access File" having high capacity and rapid random access at a relatively low cost. After considering technologies such as wire matrices, rod arrays, drums, drum arrays, etc., the engineers at IBM's San Jose California laboratory invented the hard disk drive. The disk drive created a new level in the computer data hierarchy, then termed Random Access Storage but today known as secondary storage, less expensive and slower than main memory but faster and more expensive than tape drives.

Multiuser detection deals with demodulation of the mutually interfering digital streams of information that occur in areas such as wireless communications, high-speed data transmission, DSL, satellite communication, digital television, and magnetic recording. It is also being currently investigated for demodulation in low-power inter-chip and intra-chip communication. Multiuser detection encompasses both receiver technologies devoted to joint detection of all the interfering signals or to single-user receivers which are interested in recovering only one user but are robustified against multiuser interference and not just background noise.

In telecommunication, equalization is the reversal of distortion incurred by a signal transmitted through a channel. Equalizers are used to render the frequency response—for instance of a telephone line—flat from end-to-end. When a channel has been equalized the frequency domain attributes of the signal at the input are faithfully reproduced at the output. Telephones, DSL lines and television cables use equalizers to prepare data signals for transmission.

Noise-Predictive Maximum-Likelihood (NPML) is a class of digital signal-processing methods suitable for magnetic data storage systems that operate at high linear recording densities. It is used for retrieval of data recorded on magnetic media.

Evangelos Eleftheriou is a Greek electrical engineer. He is an IBM Fellow and was responsible for the Cloud and Computing Infrastructure department at the IBM Research – Zurich laboratory in Rüschlikon, Switzerland.

Yoshihiro Shiroishi

Yoshihiro Shiroishi was born in 1951 in Tokyo, Japan. He is a Chief Architect and Technical Advisor at the Hitachi Research & Dev. Group, Tokyo, Japan. Shiroishi was named Fellow of the Institute of Electrical and Electronics Engineers (IEEE) in 2015 for leadership in the development of high density magnetic recording technologies and devices.

Christopher H. Bajorek Data storage engineer, inventor, technology leader (b. 1943, d. -)

Christopher Henry Bajorek is a data storage engineer noted for his leadership in developing and implementing magnetoresistive sensors into magnetic stripe readers, tape drives and hard disk drives.

John C. Mallinson British-American physicist

John C. Mallinson was a British physicist who made significant contributions to the understanding of magnetism and magnetic recording. He is perhaps best remembered for his theoretical work on structures with one-sided magnetic flux. Their use is exemplified in the Halbach array and in the familiar refrigerator magnet.

Two-dimensional magnetic recording

Two-dimensional magnetic recording (TDMR) is a novel technology recently introduced in hard disk drives (HDD) used for computer data storage. Most of the world's data is recorded on HDDs, and there is continuous pressure on manufacturers to create greater data storage capacity in a given HDD form-factor and for a given cost. In an HDD, data is stored using magnetic recording on a rotating magnetic disk and is accessed through a write-head and read-head. TDMR allows greater storage capacity by advantageously combining signals simultaneously from multiple read-back heads to enhance the recovery of one or more of data-tracks. In this manner, data can be stored with higher areal-density on the disks thus providing higher capacity in each HDD. TDMR is a read-back technology and thus applies equally well to future recording (writing) technologies such as Heat-Assisted Magnetic Recording (HAMR) and Microwave-Assisted Magnetic Recording (MAMR).

Mason Lamar Williams American engineer, physicist, and inventor in Magnetic Recording

Mason Lamar Williams III was an engineer and physicist, noted for his contributions in the areas of magnetic recording and data storage on hard disk drives (HDD). A large part of his career was with the IBM Almaden Research Center in San Jose, California. After retiring, Williams played a major role in the restoration and demonstration of the IBM RAMAC at the Computer History Museum in Mountain View, California

Michael Mallary American data storage engineer, inventor, and author

Michael L. Mallary is an engineer, physicist, inventor, and author who is noted for his contributions in the areas of magnetic recording and data storage on hard disk drives (HDD). His work has concentrated on developing and optimizing magnetic components to maximize data storage density. In particular, he is responsible to inventing the 'trailing-shield' write head used universally in modern HDDs. Mallary is a Fellow of the Institute of Electrical and Electronics Engineers and recipient of the IEEE Magnetics Society Achievement Award.

Neal Bertram American physicist, teacher, and author

Neal Bertram is a physicist noted for his contributions to the theory of magnetic recording. From 1968 to 1985, he worked for Ampex Corporation in Redwood City. From 1985 to 2004, he was an Endowed Chair Professor at the Center for Memory and Recording Research (CMRR), University of California at San Diego. He is the author of the book "Theory of Magnetic Recording". He is an elected Fellow of the Institute of Electrical and Electronics Engineers. In 2003, he won the IEEE Reynold B. Johnson Information Storage Systems Award.

References

  1. ↑ G. Fisher, W. Abbott, J. Sonntag, R. Nesin, "PRML detection boosts hard-disk drive capacity", IEEE Spectrum, Vol. 33, No. 11, pp. 70-76, Nov. 1996
  2. ↑ A. Lender, "The duobinary technique for high-speed data transmission", Trans. AIEE, Part I: Communication and Electronics, Vol. 82 , No. 2 , pp. 214-218, May 1963
  3. ↑ E. Kretzmer, "Generalization of a Technique for Binary Data Communication", IEEE Trans. Comm., Vol. 14, No. 1, pp. 67-68 Feb. 1966
  4. ↑ H. Kobayashi and D. Tang, "Application of Partial-response Channel Coding to Magnetic Recording Systems", IBM J. Res. Dev., Vol, 14, No. 4, pp. 368-375, July 1970
  5. ↑ A. Viterbi, "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm", IEEE Trans. Info. Theory, Vol. 13, No. 2, pp. 260-269, Apr. 1967
  6. ↑ H. Kobayashi, "Correlative level coding and maximum-likelihood decoding", IEEE Trans. Inform. Theory, vol. IT-17, PP. 586-594, Sept. 1971
  7. ↑ D. Forney, “The Viterbi Algorithm”, Proc. IEEE, Vol. 61, No. 3, pp. 268-278, Mar. 1973
  8. ↑ M. Ferguson, ”Optimal reception for binary partial response channels” Bell Syst. Tech. J., vol. 51, pp. 493-505, Feb. 1972
  9. ↑ T. Wood, "Ampex Digital Cassette Recording System (DCRS)", THIC meeting, Ellicott City, MD, 16 Oct., 1996 (PDF)
  10. ↑ R. Wood, K. Hallamasek, "Overview of the prototype of the first commercial PRML channel", Computer History Museum, #102788145, Mar. 26, 2009
  11. ↑ C. Coleman, D. Lindholm, D. Petersen, and R. Wood, "High Data Rate Magnetic Recording in a Single Channel", J. IERE, Vol., 55, No. 6, pp. 229-236, June 1985. (invited) (Charles Babbage Award for Best Paper)
  12. ↑ Computer History Museum, #102741157, "Ampex PRML Prototype Circuit", circa 1982
  13. ↑ J. Smith, "Error Control in Duobinary Data Systems by Means of Null Zone Detection", IEEE Trans. Comm., Vil 16, No. 6, pp. 825-830, Dec., 1968
  14. 1 2 R. Wood, S. Ahlgrim, K. Hallamasek, R. Stenerson, "An Experimental Eight-inch Disc Drive with One-hundred Megabytes Per Surface", IEEE Trans. Mag., vol. MAG-20, No. 5, pp. 698-702, Sept. 1984. (invited)
  15. ↑ R. Wood and D. Petersen, "Viterbi Detection of Class IV Partial Response on a Magnetic Recording Channel", IEEE Trans. Comm., Vol., COM-34, No. 5, pp. 454-461, May 1986 (invited)
  16. ↑ D. Petersen, "Digital maximum likelihood detector for class IV partial response", US Patent 4504872, filed Feb. 8, 1983
  17. ↑ J. Coker, R. Galbraith, G. Kerwin, J. Rae, P. Ziperovich, "Implementation of PRML in a rigid disk drive", IEEE Trans. Magn., Vol. 27, No. 6, pp. 4538-43, Nov. 1991
  18. ↑ R.Cidecyan, F.Dolvio, R. Hermann, W.Hirt, W. Schott "A PRML System for Digital Magnetic Recording", IEEE Journal on Selected Areas in Comms, vol.10, No.1, pp.38-56, Jan 1992
  19. ↑ T. Howell, et al. "Error Rate Performance of Experimental Gigabit per Square Inch Recording Components", IEEE Trans. Magn., Vol. 26, No. 5, pp. 2298-2302, 1990
  20. ↑ A. Patel, "Performance Data for a Six-Sample Look-Ahead 17ML Detection Channel", IEEE Trans. Magn., Vol. 29, No. 6, pp. 4012-4014, Dec. 1993
  21. ↑ R. Carley, J. Moon, "Apparatus and method for fixed delay tree search", filed Oct. 30th, 1989
  22. ↑ R. Wood, "New Detector for 1,k Codes Equalized to Class II Partial Response", IEEE Trans. Magn., Vol. MAG-25, No. 5, pp. 4075-4077, Sept. 1989
  23. ↑ T. Kameyama, S. Takanami, R. Arai, "Improvement of recording density by means of cosine equalizer", IEEE Trans. Magn., Vol. 12, No. 6, pp. 746-748, Nov. 1976
  24. ↑ R. Wood, R. Donaldson, "The Helical-Scan Magnetic Tape Recorder as a Digital Communication Channel", IEEE Trans. Mag. vol. MAG-15, no. 2, pp. 935-943, March 1979
  25. ↑ D. Palmer, P. Ziperovich, R. Wood, T. Howell, "Identification of Nonlinear Write Effects Using Pseudo-Random Sequences", IEEE Trans. Magn., Vol. MAG-23, no. 5, pp. 2377-2379, Sept. 1987
  26. ↑ D. Palmer, J. Hong, D. Stanek, R. Wood, "Characterization of the Read/Write Process for Magnetic Recording", IEEE Trans. Magn., Vol. MAG-31, No. 2, pp. 1071-1076, Mar. 1995 (invited)
  27. ↑ P. Newby, R. Wood, "The Effects of Nonlinear Distortion on Class IV Partial Response", IEEE Trans. Magn., Vol. MAG-22, No. 5, pp. 1203-1205, Sept. 1986
  28. ↑ "Kursk: BIOS Settings - Standard CMOS Setup, Feb 12, 2000". Archived from the original on October 4, 2018. Retrieved October 8, 2019.
  29. ↑ H.Thapar, A.Patel, "A Class of Partial Response Systems for Increasing Storage Density in Magnetic Recording", IEEE Trans. Magn., vol. 23, No. 5, pp.3666-3668 Sept. 1987
  30. ↑ D. Forney, "Maximum Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference", IEEE Trans. Info. Theory, vol. IT-18, pp. 363-378, May 1972.
  31. ↑ R. Wood, "Turbo-PRML, A Compromise EPRML Detector", IEEE Trans. Magn., Vol. MAG-29, No. 6, pp. 4018-4020, Nov. 1993
  32. ↑ Conway, T. (July 1998). "A new target response with parity coding for high density magnetic recording channels". IEEE Transactions on Magnetics. 34 (4): 2382–2386. doi:10.1109/20.703887.
  33. ↑ R. Cideciyan, J. Coker; E. Eleftheriou; R. Galbraith, "NPML Detection Combined with Parity-Based Postprocessing", IEEE Trans. Magn. Vol. 37, No. 2, pp. 714–720, March 2001
  34. ↑ M. Despotovic, V. Senk, "Data Detection", Chapter 32 in Coding and Signal Processing for Magnetic Recording Systems edited by B. Vasic, E. Kurtas, CRC Press 2004
  35. ↑ J. Moon, J. Park, "Pattern-dependent noise prediction in signal dependent noise" IEEE J. Sel. Areas Commun., vol. 19, no. 4, pp. 730–743, Apr. 2001
  36. ↑ E. Eleftheriou, W. Hirt, "Improving Performance of PRML/EPRML through Noise Prediction". IEEE Trans. Magn. Vol. 32, No. 5, pp. 3968–3970, Sept. 1996
  37. ↑ E. Eleftheriou, S. Ölçer, R. Hutchins, "Adaptive Noise-Predictive Maximum-Likelihood (NPML) Data Detection for Magnetic Tape Storage Systems", IBM J. Res. Dev. Vol. 54, No. 2, pp. 7.1-7.10, March 2010
  38. ↑ "Marvell 88i9422 Soleil SATA HDD Controller" (PDF). September 2015. Archived from the original (PDF) on 2016-12-13. Retrieved 2019-10-09.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.