Maximum likelihood detection with difference metrics and programmed coefficients

[0002] This invention relates to maximum likelihood detection of data recorded as analog signals representing a finite number of states, and, more particularly to reduction of errors resulting from maximum likelihood detection.

[0003] Maximum likelihood detection of data recorded as analog signals and detected from partial response samples is highly advantageous in magnetic disk drives, where the disks and heads are fixed and non-removable. The characteristics of the channel are fixed, including the particular disk media, the particular recording and read heads, the linear velocity and flying height between the disk media and the recording and read heads, and the recording and read electronics. The channel characteristics can be measured and, once known, tend to remain constant. Additionally, a specific code may be employed which maximizes the distances between the sensed states. Only limited changes are taken into account, such as differences in data rates between inner and outer tracks, minor servo offtrack operation, minor disk defects, and some head wear over time. Thus, a specific maximum likelihood detection circuit can be designed which is specific to the type of disk drive and which will have a low error rate at high recording densities. Further, such minor changes have been accommodated by employing digital FIR (finite impulse response) filters whose coefficients are programmable, thus changing the frequency response of the filters to better match the signal being read to the maximum likelihood detector. Examples include, U.S. Pat. No. 5,321,559, Nguyen et al., U.S. Pat. No. 5,365,342, Abbott et al., and U.S. Pat. No. 5,442,760, Abbott et al.

[0004] It becomes more difficult to use such maximum likelihood detection with recording devices which have removable media.

[0005] Removable media devices tend to be mass storage devices which allow data to be recorded on media which is removed from the device and stored elsewhere, such as in the storage shelves of an automated data storage library, or in true archive storage outside of a drive or library on storage shelves or in boxes and other containers. The amount of data so stored quickly becomes very large and, if a new and upgraded media is introduced, there is a desire on the part of the user to resist re-recording all of the archived data onto the upgraded media. Hence, a backwards compatibility is typically required for removable media devices. Examples of removable media devices include optical disk and optical tape storage, which may be read-only, write-once, and rewritable media, and be different types of media, such as molded, magneto-optic and phase-change media.

[0006] Optical media is subject to variation from media to media in recorded data output characteristics based on the type of media, above, variation in media materials between manufacturers and over time, and between recording densities.

[0007] Another example of removable media devices includes magnetic tape recording, which have media to media variation based on different data densities on the same type of media, different types of media such as chromium-based, nickel-based, ferrous-based media, or between materials used by different manufacturers. Additionally, tape media may have differing thicknesses and therefore differing media to head (flying and contact) characteristics over the recording and read head, resulting in differing head to media spacings.

[0008] Maximum likelihood detection in such differing circumstances is exceedingly difficult, and may require a different maximum likelihood detector for each circumstance.

[0009] Further, in the context of a single drive type, the drives may have an alignment of the head with respect to the media which differs between drives, also resulting in differing channel characteristics.

[0010] The use of a changeable FIR, as in the above patents, is unlikely to compensate for the change in channel characteristics.

[0011] Additionally, the maximum likelihood trellis for maximum likelihood detection conventionally utilizes continuing accumulation of metrics until the accumulation reaches an overflow condition, and the register containing the accumulated metric is then reset, normalizing the accumulated value.

[0012] It is therefore an object of the present invention to provide maximum likelihood detection of data recorded as analog signals representing a finite number of states which reduces errors resulting from maximum likelihood detection with normalized values.

[0013] Disclosed are a maximum likelihood detector and a method for maximum likelihood detection of digital samples of data recorded as analog signals representing a finite number of states, the digital samples representing the channel output of recorded analog signals at a predetermined timing with respect thereto. The method comprises the steps of:

[0014] providing numerical metric coefficients relating to the probability of the digital samples comprising a data sequence;

[0015] respectively applying the numerical metric coefficients to each of the digital samples to generate alternative metrics;

[0016] providing a previous metric which comprises a difference metric function of a previous digital sample;

[0017] selecting the one of the respective generated alternative metrics which minimizes the mean squared error with respect to the previous metric;

[0018] identifying the one of the finite number of states represented by the selected metric; and

[0019] responding to the identified one of the finite states, setting a maximum likelihood state detector to a maximum likelihood state dictated by the identified one of the finite states, the set maximum likelihood state detecting the recorded analog signals.

[0020] Each separate set of metric coefficients may comprise programmed numerical metric coefficients relating to the probability of the samples comprising a data sequence under different detection characteristics.

[0021] The alternative metrics are compared to the previous metric, and, the selection of the provided metric is based upon the comparison.

[0022] The numerical metric coefficients are derived from the difference between metrics directly associating “0” and “1” states of the recorded signal. This insures that there is no unbounded accumulation of metrics.

[0023] The derived numerical coefficients are applied to each of the digital samples to provide at least one difference metric. A lot plurality of alternative metrics are generated relating to the digital samples. The one of the respective generated alternative metrics is selected which remains within defined positive and negative bounds by comparing the generated alternative metrics to the difference metric. The one of the finite number of states represented by the selected metric is identified, and the maximum likelihood detector is set, detecting the analog signal.

[0024] Where the recorded analog signals having the different detection characteristics are recorded on different media, the step of programming each metric coefficient may be conducted based upon an identification of the different media.

[0025] The programmed numerical metric coefficients may be derived from logarithmic relationships of the digital samples to the finite number of states.

[0026] For a fuller understanding of the present invention, reference should be made to the following detailed description taken in conjunction with the accompanying drawings.

[0027] FIG. 1 is a diagrammatic representation of a channel which may implement the present invention;

[0028] FIG. 2 is a representation of a stream of write data and its corresponding representation in NRZ and NRZI;

[0029] FIGS. 3A-3D are diagrams of channel impulse response curves, including exemplary sample times;

[0030] FIGS. 4A-4D are diagrams of channel step response curves, including exemplary sample times;

[0031] FIG. 5 is a diagram of an example of a maximum likelihood trellis branching from one sample to the next for first order detection;

[0032] FIG. 6 is a block diagram of programming inputs and logic for applying programmed metric coefficients to digital samples of channel output signals to provide metrics thereof in accordance with the present invention;

[0033] FIGS. 7 and 8 are a block diagrams of logic for providing selected first order difference metrics from the metrics of the circuit of FIG. 6, and selecting the maximum likelihood branch which minimizes the mean squared error with respect to the previous finite maximum likelihood state in accordance with the present invention;

[0034] FIG. 9 is a diagram of an example of a maximum likelihood trellis branching from one sample to the next for second order detection;

[0035] FIGS. 10-13 are a block diagrams of logic for providing selected second order difference metrics from the metrics of the circuit of FIG. 6, and selecting the maximum likelihood branch which minimizes the mean squared error with respect to the previous finite maximum likelihood state in accordance with the present invention;

[0036] FIGS. 14-19 are a block diagrams of logic for providing selected third order difference metrics from the metrics of the circuit of FIG. 6, and selecting the maximum likelihood branch which minimizes the mean squared error with respect to the previous finite maximum likelihood state in accordance with the present invention;

[0037] FIG. 20 is a flow chart depicting the methodology in accordance with the present invention for determining metric coefficients for programming the logic of FIG. 6;

[0038] FIG. 21 is a flow chart depicting the methodology for maximum likelihood detection in accordance with the present invention;

[0039] FIG. 22 is a block diagram of an embodiment of the present invention for programming the metric coefficients of the maximum likelihood detector; and

[0040] FIG. 23 is a flow chart depicting a method for programming the metric coefficients of the maximum likelihood detector of FIG. 22.

[0041] This invention is described in preferred embodiments in the following description with reference to the Figures, in which like numbers represent the same or similar elements. While this invention is described in terms of the best mode for achieving this invention's objectives, it will be appreciated by those skilled in the art that variations may be accomplished in view of these teachings without deviating from the spirit or scope of the invention.

[0042] Referring to FIGS. 1 and 2, a write-read channel is illustrated in FIG. 1 that implements the present invention for write data, such as that illustrated in FIG. 2, as supplied at an input 10. Typical binary data 12 is signaled as NRZ data 13, having a signal voltage for each one bit and no signal voltage for each zero bit. When binary data is recorded on data storage media, the data is typically converted to NRZI data 14 by circuit 15 and supplied to a target channel 17 to reduce the number of data pulses and thereby to allow storage of greater quantities of data in the same space. Thus, it is this NRZI data that a maximum likelihood detector 18 must use to base its reconstruction of the write data 12.

[0043] The typical target channel 17 is designed to reproduce the data as faithfully as possible within reasonable cost constraints. Although a tape system employing a tape media 20 and write and read heads 21 and 22 is illustrated, optical or magnetic disk systems may also be employed. In any of the systems, a write equalizer 24 and a read equalizer 26 are employed to offset to some extent certain non-linearities of the media and drive systems and to provide the read signals at the same amplitude. In maximum likelihood detection systems, the read equalizer 26 is digital and an analog to digital converter 27 is employed to provide the digital samples of the output of the read head 22 indicating the signal amplitudes, and a clock recovery circuit 28 is provided to insure that the digital samples have the correct timing.

[0044] FIGS. 3A-3D are diagrams of channel impulse response curves, and FIGS. 4A-4D are diagrams of channel step response curves, including exemplary sample times. FIGS. 3A and 4A illustrate the ideal class PR I impulse and step response curves 30 and first order samples, and non-ideal impulse and step response 31 and first order samples which are not equal, such as may be encountered in an optical storage system. FIGS. 3B and 4B illustrate the ideal class PR II impulse and step response curves 32 and second order samples, and non-ideal impulse and step response 33 and second order samples which are not exact multiples and are not equal, also such as may be encountered in an optical storage system. FIGS. 3C and 4C illustrate the ideal class PR IV impulse and step response curves 34 and second order samples, and non-ideal impulse and step response curves 35 and second order samples that are unequal and offset, such as may be encountered in a magnetic tape storage system. FIGS. 3D and 4D illustrate the ideal class Extended PR IV impulse and step response curves 36 and third order samples, and non-ideal impulse and step response curves 37 and third order samples that are unequal, such as may also be encountered in a magnetic tape storage system.

[0045] As is well known, the idealized classes allow simplified maximum likelihood detection by having digital samples that are integrally related so that it is easy to calculate the appropriate metrics. As described above, maximum likelihood detection of magnetic disk drives, where the disks and heads are fixed and non-removable can have the equalizers 24 and 26 of FIG. 1 designed so that the idealized signals are provided to the maximum likelihood detector.

[0046] However, also as described above, it becomes more difficult to use such maximum likelihood detection with recording devices which have removable media.

[0047] Examples of removable media devices include optical disk and optical tape storage. Optical media is subject to variation from media to media in recorded data output characteristics based on the type of media, above, variation in media materials between manufacturers and over time, and variation in recording densities.

[0048] Another example of removable media devices includes magnetic tape recording systems, which have media to media variation based on different data densities on the same type of media, different types of media such as chromium-based, nickel-based, ferrous-based media, or between materials used by different manufacturers. Additionally, tape media may have differing thicknesses and therefore differing media to head (flying and contact) characteristics over the recording and read head, resulting in differing head to media spacings.

[0049] Maximum likelihood detection in such differing circumstances is exceedingly difficult, and may require a different maximum likelihood detector for each circumstance.

[0050] Thus, in accordance with the one aspect of the present invention, the maximum likelihood detector metrics are programmed with at least one numerical metric coefficient relating to the probability of the digital samples comprising a data sequence.

[0051] For example, the first order maximum likelihood detection of digital samples of data recorded as analog signals 30 or 31 of FIGS. 3A and 4A, having two finite states, is illustrated in FIG. 5, showing the possible maximum likelihood trellis branching from one sample to the next for first order detection of the “0” and “1” states of the recorded signal. In the example of FIG. 5, each point selected for Cases “0”, “1”, “2” and “3” is determined for a particular media for a particular head by determining (e.g., by calculation or measurement) the mean value for each point. The mean values are then employed in metric equations to assess the various Cases and then the equations are solved to determine particular metric coefficients, which in the normal case of removable media signals 31 do not have the idealized integral relationship of the class PR I signals 30.

[0052] In accordance with the present invention, programmed multiplicative and additive metric coefficients allow the maximum likelihood detector to be adaptable. The detector is thus able to accommodate changes to the transfer function of the channel, for example, by a change of media, changing the mean of probability functions for the data of the channel.

[0053] The metric coefficients are derived, in accordance with another aspect of the present invention, for use with difference metrics. Logic for implementing the derived metric coefficients is provided, the numerical metric coefficients are determined from the mean of probability functions, and programmed into the logic. FIGS. 6-8 illustrate an embodiment of logic implementing the invention for first order maximum likelihood detection, FIGS. 10-13 illustrate an embodiment for second order maximum likelihood detection, and FIGS. 14-19 illustrate an embodiment for third order maximum likelihood detection.

[0054] For the purpose of illustration, the methodology and equations for the first order maximum likelihood detection difference metrics of the signals and samples illustrated in FIGS. 3A and 4A will be described in detail.

[0055] The channel sample y_kis the function of the input bits a_k, and a_k−1. The goal of the maximum likelihood detector is to produce an accurate estimate of the channel input sequence {a_k} by observing the pulse amplitude modulated sequence {y_k}. As is known by those of skill in the art, the maximum likelihood detector does this by maximizing the likelihood function p(y_k|s₀; {a_k})=p(y_k|s_k; {a_k}), where s₀=the initial state, and s_k=the current state. The probability of the given output sample at time k depends only upon the current state of the system and the possible input a_kε{0,1}. The total likelihood function can be described as:

[0056] p(y_k|s₀; {a_k})=Π_kp(y_k|s_k; {a_k}).

[0057] Taking the natural log of the likelihood function:

[0058] ln[p(y_k|s₀; {a_k})]=Σ_kln[p(y_k|s_k; {a_k})].

[0059] The power of the maximum likelihood detector is derived through its recursive nature. The log of the likelihood function is accumulated into metrics at each sample time k, with the most likely estimates being saved in metrics and the least likely estimates being rejected.

[0060] In a first order linear maximum likelihood detection system, the overall channel function is F(D)=f₀+f₁D, where D=one sample delay. With this channel function, in the absence of noise and at sampling time k, the output sequence {y_k}=f₀a_k+f₁a_k−1. For an input a_kε {a₀, a₁}, where a₀represents a binary 0 and a₁represents a binary 1, in a linear system:

[0061] Y_kε{a₀f₀+a₀f₁=μ₀, a₀f₀+a₁f₁=μ₁, a₁f₀+a₀f₁=μ₂, a₁f₀+a₁f₁=μ₃},

[0062] Alternatively, for non-linear systems, the resultant mean value (μ_X) can be measured from the actual system response.

[0063] For this system, at any time k, there are two metrics: $\begin{array}{c}{m\left(0\right)}_k=\mathrm{maximum}\text{:}m{\left(0\right)}_{k-1}+\ln [p(y_k|s_k=0;a_0)]\\ {m\left(1\right)}_{k-1}+\ln [p(y_k|s_k=1;a_0)]\\ {m\left(1\right)}_k=\mathrm{maximum}\text{:}m{\left(0\right)}_{k-1}+\ln [p(y_k|s_k=0;a_1)]\\ {m\left(1\right)}_{k-1}+\ln [p(y_k|s_k=1;a_1)]\end{array}$ $\mathrm{where}{s}_k=0\mathrm{if}{a}_{k-1}=a_0\mathrm{and}{s}_k=1\mathrm{if}{a}_{k-1}=a_1$

[0064] The channel signal {y_k} is a random process which contains an ideal signal perturbed by noise. If it is assumed that y_kis perturbed by the zero mean additive white gaussian noise of variance δ², then:

[0065] ln[p(y_k|s_k=0;a₀)]=−((y_k−μ₀)²/2 δ²)−(1/2)ln[2 πδ²]

[0066] ln[p(y_k|s_k=0;a₁)]=−((y_k−μ₂)²/2 δ²)−(1/2)ln[2 πδ²]

[0067] ln[p(y_k|s_k=1;a₀)]=−((y_k−μ₁)²/2 δ²)−(1/2)ln[2 πδ²]

[0068] ln[p(y_k|s_k=1;a₁)]=−((y_k−μ₃)²/2 δ²)−(1/2)ln[2 πδ²]

[0069] After the removal of the constant terms, the metric equations become: $\begin{array}{c}{m\left(0\right)}_k=\mathrm{maximum}\text{:}{m\left(0\right)}_{k-1}+2{\mu }_0{Y}_k-{\mu }_0^2\\ {m\left(1\right)}_{k-1}+2{\mu }_1{Y}_k-{\mu }_1^2\\ {m\left(1\right)}_k=\mathrm{maximum}\text{:}{m\left(0\right)}_{k-1}+2{\mu }_2{Y}_k-{\mu }_2^2\\ {m\left(1\right)}_{k-1}+2{\mu }_3{Y}_k-{\mu }_3^2\end{array}$

[0070] As described above, the metrics are difficult to implement in that there are no bounds on the size of the metrics, and they must be normalized in order for them to work with limited capacity registers.

[0071] In accordance with the present invention, by employing difference metrics, the size of the metric register is constrained within known bounds. Thus, the derived metric coefficients will be employed for use with difference metrics.

[0072] Referring additionally to FIG. 5, for the first order maximum likelihood detector, there are four ways that the trellis diagram can branch from one sampling time to the next, respectively called “Case 0”, “Case 1”, “Case 2”, and “Case 3”.

[0073] The metric coefficients of the difference metrics are derived, employing the “cases” of FIG. 5.

[0074] Thus, employing difference metrics:

[0075] 1. For Case 0 to have occurred:

[0076] m(0)_k+2μ₀y_k−μ₀²>m(1)_k−1+2μ₁y_k−μ₁²

[0077] m(0)_k+2μ₂y_k−μ₂²<m(1)_k−1+2μ₃y_k−μ₃²

[0078] Defining

[0079] DJ_k=m(1)_k−m(0)_k

[0080] if

[0081] DJ_k−1<2(μ₀−μ₁)y_k+(−μ₀²+μ₁²);

[0082] and

[0083] DJ_k−1>2(μ₂−μ₃)y_k+(−μ₂²+μ₃²);

[0084] then Case 0 has occurred and DJ_k=DJ_k−1+2(μ₃−μ₀)y_k+(−μ₃²+μ₀²);

[0085] Defining:

[0086] g₁=2(μ₀−μ₁) and P₁=−μ₀²+μ₁²,

[0087] g₂=2(μ₂−μ₃) and P₂=−μ₂²+μ₃²,

[0088] g₃=2(μ₃−μ₀) and P₃=−μ₃²+μ₀²;

[0089] that DJ_k−1<g₁y_k+P₁; and DJ_k−1>g₂y_k+P₂;

[0090] then, Case 0 has occurred, so that

[0091] DJ_k=DJ_k−1+g₃y_k+P₃.

[0092] 2. If

[0093] DJ_k−1<2(μ₀−μ₁)y_k+(−μ₀²+μ₁²);

[0094] and

[0095] DJ_k−1<2(μ₂−μ₃)y_k+(−μ₂²+μ₃²);

[0096] then Case 1 has occurred and DJ_k=2(μ₂−μ₀)y_k+(μ₂²+μ₀²);

[0097] Defining:

[0098] g₁=2(μ₀−μ₁) and P₁=−μ₀²+μ₁²,

[0099] g₂=2(μ₂−μ₃) and P₂=−μ₂²+μ₃²,

[0100] g₄=2(μ₂−μ₀) and P₄=−μ₂²+μ₀²;

[0101] so that Dj_k−1<g₁y_k+P₁; and DJ_k−1<g₂y_k+P₂;

[0102] then, Case 1 has occurred, so that

[0103] DJ_k=g₄y_k+P₄.

[0104] 3. If

[0105] DJ_k−1>2(μ₀−μ₁)y_k+(−μ₀²+μ₁²);

[0106] and

[0107] DJ_k−1<2(μ₂−μ₃)y_k+(−μ₂²+μ₃²);

[0108] then Case 2 has occurred and DJ_k=−DJ_k−1+2(μ₂−μ₁)y_k+(μ₂²+μ₁²)

[0109] Defining:

[0110] g₁=2(μ₀−μ₁) and P₁=−μ₀²+μ₁²,

[0111] g₂=2(μ₂−μ₃) and P₂=−μ₂²+μ₃²,

[0112] g₅=2(μ₂−μ₁) and P₅=−μ₂²+μ₁²;

[0113] so that DJ_k−1>g₁y_k+P₁; and DJ_k−1<g₂y_k+P₂;

[0114] then Case 2 has occurred, so that

[0115] DJ_k=−DJ_k−1+g₅y_k+P₅.

[0116] 4. If

[0117] DJ_k−1>2(μ₀−μ₁)y_k+(−μ₀²+μ₁²);

[0118] and

[0119] DJ_k−1>2(μ₂−μ₃)y_k+(−μ₂²+μ₃²);

[0120] then Case 3 has occurred and DJ_k=2(μ₃−μ₁)y_k+(−μ₃²+μ₁²);

[0121] Defining:

[0122] g₁=2(μ₀−μ₁) and P₁=−μ₀²+μ₁²,

[0123] g₂=2(μ₂−μ₃) and P₂=−μ₂²+μ₃²,

[0124] g₆=2(μ₃−μ₁) and P₆=−μ₃²+μ₁²;

[0125] so that DJ_k−1>g₁y_k+P₁; and DJ_k−1>g₂y_k+P₂;

[0126] then Case 3 has occurred, so that

[0127] DJ_k=g₆y_k+P₆.

[0128] The sample outputs of the expected waveforms are determined, for example, by measuring a number of sample outputs for waveforms with known inputs, and calculating the mean values of each of the sample points, and the metric coefficient numerical values are calculated for the mean values of the sample outputs, thereby providing the numerical metric coefficients.

[0129] Thus, in accordance with the present invention, the metric coefficients are derived from the difference between metrics directly associating “0” and “1” states of the recorded signal.

[0130] FIG. 6 illustrates an embodiment of the present invention for providing programming inputs 401, 402, 411 and 412 for supplying programmed metric coefficients “g₁”, “g₂”, “P₁” and “P₂” respectively to registers 421, 422, 431 and 432. As described above, the metric coefficients g₁and g₂are multiplier (product) metric coefficients, and the metric coefficients P₁and P₂are additive (offset) metric coefficients. The programmed metric coefficients are respectively applied by logic 441, 442, 451 and 452 to each digital sample of channel output signals “y” supplied at input 50 and delayed (“k” indicates the delay time in terms of sequential digital samples) by register 51. The application of the metric coefficients provides alternative metrics thereof at registers 52 and 53, respectively at outputs 54 and 55.

[0131] The alternative metrics are employed in a maximum likelihood detector for comparison to a function of the current sample and a prior selected metric in order to select the metric which minimizes the mean squared error with respect to the previous metric. Thus, the programming inputs 401, 402, 411 and 412 allow the alternative metrics to be tailored to the particular media which is being read.

[0132] In higher order maximum likelihood detectors, additional programming inputs may be provided to generate additional alternative metrics, as will be explained.

[0133] Programming inputs 403-406 and 413-416 respectively supply programmed metric coefficients “g₃”-“g_N”, “P₃”-“P_N” to registers 423-426 and 433-436, which are employed, in accordance with another aspect of the present invention, to calculate the various difference metrics for the various cases, for example, of FIG. 5. Again, as described above, the metric coefficients g₃-g_Nare multiplier (product) metric coefficients, and the metric coefficients P₃and P_Nare additive (offset) metric coefficients. The programmed metric coefficients are respectively applied by logic 443-446, 453-456 to each digital sample of channel output signals “y” supplied at input 50 and delayed by register 51.

[0134] For the example of the cases of FIG. 5, 4 sets of metric coefficients are employed for the calculation of 4 difference metrics for 4 possible cases, employing the above described equations. Thus, registers 460-463 respectively supply outputs 465-468 representing respectively, g₃y_k+P₃, g₄y_k+P₄, g₅y_k+P₅, and g₆y_k+P₆.

[0135] Since the metric coefficients “g₁”-“g_N” and “P₁”-“P_N” are derived from the difference between metrics directly associating “0” and “1” states of the recorded signal for first order maximum likelihood detection, this insures that no accumulation of metrics is unbounded, and there is never an overflow at the difference metric register.

[0136] Thus, the programmed metric coefficients “g₁”-“g₆” and “P₁”-“P₆” derived from the above are supplied, in FIG. 6, at programming inputs 401-406 and 411-416 to registers 421-426 and 431-436. The programmed metric coefficients are respectively applied by logic 441-446 and 451-456 to each digital sample “y” supplied at input 50. The resultant outputs are stored in registers 52-53 and 460-463, delayed and supplied on outputs 54-55 and 465-468 to the logic of FIG. 7.

[0137] In FIG. 7, the outputs 465-468 are further processed and selectively combined with a previous metric from register 68, by logic 470-472, in accordance with the above “case” equations. Thus, the difference metrics are provided on inputs 468, 480, 481 and 466 to a multiplexor 64, the metric on line 481 representing case “0”, on input 466 representing case “1”, on input 480 representing case “2”, and on input 468 representing case “3”. As the result, the provided metrics are related to the programmed metric coefficients and to the previous metric 68.

[0138] Use of the difference metrics and resultant difference metric coefficients allows a selector 60 of FIG. 7, which responds to the inputs at lines 61 and 62, to select as the difference metric “DJ_k” 63 at multiplexor 64 from between the calculated metrics of inputs 468, 480, 481 or 466 of multiplexor 64. The signals on lines 61 and 62 have binary values, which, when taken together, represent the four cases and operate the multiplexor 64 to gate the one of the inputs 468, 480, 481 or 466 represented by the particular case. The cases are encoded by the state of the lines 61 and 62 from FIG. 8, a negative signal indicating a binary “1” and a positive signal indicating a binary “0”, resulting in the two lines representing the four cases. The selection of one of the provided difference metrics of inputs 468, 480, 481 and 466, insures that the resultant metric on output 63 remains within defined bounds.

[0139] The cases designated on lines 61 and 62 are generated by comparing the alternative metrics on inputs 54 and 55 (from FIG. 6) to the previous difference metric.

[0140] The difference metric “DJ_k” 63 at multiplexor 64 is delayed in register 68 and supplied on output 69 after one delay time as “DJ_(k−1)” to adders 70 and 71 of FIG. 8. Each respective alternative metric “g₁y_k+P₁” and “g₂y_k+P₂” from outputs 54 and 55 is supplied to invertors 490 and 491 for multiplying by minus one and are added to the previous difference metric “DJ_(k−1)” 69 by adders 70 and 71 to provide the respective positive and negative states on outputs 61 and 62 which identify the one of the finite number of cases represented by the selected accumulated metric. Effectively, the adders 70 and 71 provide a comparison of the metrics to the previous difference metric. The states on outputs 61 and 62 are used to select the next difference metric “DJ_k” 63 at multiplexor 64, and are used to select a trellis path in path memory 80 to a maximum likelihood state dictated by the identified finite state. The path memory 80 will provide the appropriate data bit at output 81.

[0141] The use, in accordance with the present invention, of a difference metric “DJ_k” 63 employs only a single metric selection, as opposed to the prior methods.

[0142] The flow chart of FIG. 20 depicts the methodology in accordance with the present invention for determining metric coefficients 300 derived for use with difference metrics. The first step 301 is to determine the maximum likelihood detection sampling metrics for the “0” and “1” states of the recorded signal as a function of the previous state.

[0143] In accordance with the present invention, step 303 is provided to derive difference metrics for various cases defining the maximum likelihood trellis branches. By employing difference metrics, the size of the metric register is constrained within known bounds.

[0144] Specifically, the difference metrics comprise the difference between metrics for two sequential samples. Multiple difference metrics represent, respectively, the differences between many means of samples, which, when all are considered, completely span the entire state space. The difference metrics may derived in different ways, but the equations still reduce to the same structure and are based on the same fundamentals including timing.

[0145] Referring additionally to FIG. 5, for the first order maximum likelihood detector, there are four ways that the trellis diagram can branch from one sampling time to the next, respectively called “Case 0”, “Case 1”, “Case 2”, and “Case 3”.

[0146] Next, in step 305, the metric coefficients of the difference metrics are derived, employing the “cases” of FIG. 5. One of skill in the art will understand that the derivation may employ various approaches, such as logarithms, and may incorporate techniques which reduce the complexity of the metrics. It is these metric coefficients that are employed in steps 306 and 307, where the sample outputs for the expected waveforms, for example, of a particular media, are determined, and the metric coefficient numerical values are calculated for the expected sample outputs.

[0147] The equations for deriving the metric coefficients minimize the mean squared error between the received signal and the ideal signal, which is the noise-free signal.

[0148] In steps 306 and 307, the sample outputs of the expected waveforms are determined, for example, by measuring a number of sample outputs for the waveforms, and calculating the mean values of each of the sample points, and the metric coefficient numerical values are calculated for the mean values of the sample outputs, thereby providing the numerical metric coefficients 309.

[0149] Thus, in the process of steps 300-309 of FIG. 20, the metric coefficients are derived from the difference between metrics directly associating “0” and “1” states of the recorded signal, and the numerical metric coefficients are calculated for programming the programmable inputs.

[0150] FIG. 21 illustrates in a flow chart the methodology for maximum likelihood detection in accordance with the present invention, beginning at step 320. Step 321 comprises programming the at least two numerical metric coefficients relating to the probability of the digital samples comprising a data sequence that were defined in the process of FIG. 20.

[0151] In step 322, the programmed metric coefficients are respectively applied to each digital sample of channel output signals “y” supplied at an input. The application of the metric coefficients provides alternative metrics thereof at at least two respective outputs, as discussed above.

[0152] Also as discussed above, in prior maximum likelihood detectors, the alternative metrics are each accumulated to a prior metric, the most likely accumulated metric is selected, and the next alternative metrics are accumulated to the accumulated metric. The accumulation is accomplished in registers, and tends to grow without bound, so that, at some point, the capacity of the accumulation registers can be exceeded, resulting in overflow. In order to prevent overflow and a resultant discontinuity in the data, the registers are often normalized and the maximum likelihood detector adjusted to the normalized accumulation registers.

[0153] In step 323, the programmed metric coefficients, e.g., in FIG. 6, “g₁”-“g₆” and “P₁”-“P₆”, derived from the above are respectively applied by logic to each digital input sample “y”. The resultant outputs are stored and are further processed and selectively combined with a previous metric in accordance with the above “case” equations. Thus, step 323 comprises providing the difference metrics, representing the respective cases, e.g., of FIG. 5, the metric on line 481 of FIG. 7 representing case “0”, on input 466 representing case “1”, on input 480 representing case “2”, and on input 468 representing case “3”. As the result, the provided metrics are related to the alternative metrics and to the previous metric 68.

[0154] Use of the difference metrics and resultant difference metric coefficients allows, in step 324, a selector 60 of FIG. 7 to select as the difference metric “DJ_k” 63 from between the calculated metrics of inputs 468, 480, 481 or 466 of multiplexor 64.

[0155] The selection of step 324, by selecting one of the provided difference metrics of inputs 468, 480, 481 and 466, insures that the resultant metric on output 63 remains in defined bounds. The cases designated on lines 61 and 62 are generated, in substep 325 by comparing the alternative metrics on inputs 54 and 55 to the previous difference metric.

[0156] In substep 326, the states on outputs 61 and 62 are used to select the next difference metric “DJ_k” 63, and are used in step 327 to select a trellis path in path memory 80 to a maximum likelihood state dictated by the identified finite state. The path memory 80 will provide the appropriate data bit at output 81.

[0157] The use, in accordance with the present invention, of a difference metric “DJ_k” 63 employs only a single metric selection, as opposed to the prior methods.

[0158] FIG. 9 illustrates the possible maximum likelihood trellis branching for second order digital samples of data recorded as analog signals 32 or 33 of FIGS. 3B and 4B, having three finite states, or for second order detection of a signal of the form of signal 31 of FIGS. 3A and 4A, where the respective samples of the signal are very unequal, requiring substantially different metrics. In the example of FIG. 9, each point selected for Cases “0”, “1”, “2” and “3” is determined for a particular media for a particular head by determining the mean value “m” for each point. As above, the equations are solved to determine particular metric coefficients.

[0159] Second order maximum likelihood detection involves more complicated equations, but the process of determining the metric coefficients 300 of FIG. 20 is the same. In a linear second order maximum likelihood detection system, the overall channel function is F(D)=f₀+f₁D+f₂D². With this channel function, in the absence of noise and at sample time k, the output sequence is {y_k}=f₀a_k+f₁a_k−1+f₂a_k−2. Thus, in step 301, for a binary input a_kε{a₀, a₁}, where a₀represents a binary 0 and a₁represents a binary 1:

[0160] Y_kε{a₀f₀+a₀f₁+a₀f₂=μ₀, a₀f₀+a₀f₁+a₁f₂=μ

[0161] ₁, a₁f₀+a₁f₁+a₁f₂=μ₃, a₁f₀+a₀f₁+a₀f₂=μ

[0162] ₄, a₁f₀+a₁f₁+a₀f₂=μ₆, a₁f₀+a₁f₁+a₁f₂=μ₇}

[0163] Because of the (1,k) NRZI code constraints, two of the eight possible values for y_khave been eliminated. Alternatively, for non-linear systems, the resultant mean value (μ_X) can be measured from the actual system response.

[0164] For this system, at any time k, there are four metrics: $\begin{array}{c}{m\left(0\right)}_k=\mathrm{maximum}\text{:}m{\left(0\right)}_{k-1}+\ln [p(y_k|s_k=0;a_0)]\\ {m\left(1\right)}_{k-1}+\ln [p(y_k|s_k=1;a_0)]\end{array}$ ${m\left(1\right)}_k={m\left(3\right)}_{k-1}+\ln [p(y_k|s_k=3;a_0)]$ ${m\left(2\right)}_k={m\left(0\right)}_{k-1}+\ln [p(y_k|s_k=0;a_1)]$ $\begin{array}{c}{m\left(3\right)}_k=\mathrm{maximum}\text{:}{m\left(2\right)}_{k-1}+\ln [p(y_k|s_k=2;a_1)]\\ {m\left(3\right)}_{k-1}+\ln [p(y_k|s_k=3;a_1)]\end{array}$ $\begin{array}{c}\mathrm{Where}{s}_k=0\mathrm{if}{a}_{k-1}=a_0\mathrm{and}{a}_{k-2}=a_0\\ 1\mathrm{if}{a}_{k-1}=a_0\mathrm{and}{a}_{k-2}=a_1\\ 2\mathrm{if}{a}_{k-1}=a_1\mathrm{and}{a}_{k-2}=a_0\\ 3\mathrm{if}{a}_{k-1}=a_1\mathrm{and}{a}_{k-2}=a_1\end{array}$

[0165] It is important to note that m(1)_kand m(2)_kare functions of only one previous metric. This fact can be used to reduce the hardware complexity and improve the detector performance.

[0166] ln[p(y_k|s_k=0;a₀)]=−((y_k−μ₀)²/2 δ²)−(1/2)ln[2 πδ²]

[0167] ln[p(y_k|s_k=1;a₀)]=−((y_k−μ₁)²/2 δ²)−(1/2)ln[2 πδ²]

[0168] ln[p(y_k|s_k=3;a₀)]=−((y_k−μ₃)²/2 δ²)−(1/2)ln[2 πδ²]

[0169] ln[p(y_k|s_k=0;a₁)]=−((y_k−μ₄)²/2 δ²)−(1/2)ln[2 πδ²]

[0170] ln[p(y_k|s_k=2;a₁)]=−((y_k−μ₆)²/2 δ²)−(1/2)ln[2 πδ²]

[0171] ln[p(y_k|s_k=3;a₁)]=−((y_k−μ₇)²/2 δ²)−(1/2)ln[2 πδ²]

[0172] After the removal of the constant terms, the metric equations become:

[0173] m(0)_k=maximum {m(0)_k−1+2μ₀y_k−μ₀²;m(1)_k−1+2μ₁y_k−μ₁²}

[0174] m(1)_k=m(3)_k−1+2μ₃y_k−μ₃²

[0175] m(2)_k=m(0)_k−1+2μ₄y_k−μ₄²

[0176] m(3)_k=maximum {m(2)_k−1+2μ₆y_k−μ₆²;m(3)_k−1+2μ₇y_k−μ₇²}

[0177] As shown in FIG. 9, for a second order (1,k) constrained maximum likelihood detector, there are four ways that the trellis diagram can branch from one sampling time to the next. For unconstrained second order maximum likelihood detection, there are 16 possible ways that the trellis can branch. By integrating the modulation code constraints into the detector, the number of branches is reduced to the four illustrated branches.

[0178] Once again, as described above, the metrics are difficult to implement in that there are no bounds on the size of the metrics, and they must be normalized in order for them to work with limited capacity registers.

[0179] In accordance with the present invention, by employing difference metrics, the size of the metric register is constrained within known bounds. Thus, in steps 303 and 305, the metric coefficients of the difference metrics are derived, employing the “cases” of FIG. 9. As above, it is these metric coefficients that are employed in steps 306 and 307, where the sample outputs for the expected waveforms, for example, of a particular media, are determined, and the metric coefficient numerical values are calculated for the expected sample outputs.

[0180] Thus, employing difference metrics:

[0181] 1. For Case 0 to have occurred;

[0182] Thus, in step 303:

[0183] 1. For Case 0 to have occurred:

[0184] m(0)_k−1+2μ₀y_k−μ₀²>m(1)_k−1+2μ₁y_k−μ₁²

[0185] m(2)_k−1+2μ₆y_k−μ₆²>m(3)_k−1+2μ₇y_k−μ₇²

[0186] Defining:

[0187] DJ(a,b)_k=m(a)_k−m(b)_k

[0188] if

[0189] DJ(1,0)_k−1<2(μ_o−μ₁)y_k−μ₀²+μ₁²

[0190] and

[0191] DJ(3,2)_k−1<2(μ₆−μ₇)y_k−μ₆²+μ₇²

[0192] then Case 0 has occurred and:

[0193] DJ(1,0)_k=DJ(3,0)_k−1+2(μ₃−μ₀)y_k−μ₃²+μ₀²

[0194] DJ(2,0)_k=2(μ₄−μ₀)y_k−μ₄²+μ₀²

[0195] DJ(3,0)_k=DJ(2,0)_k−1+2(μ₆−μ₀)y_k−μ₆²+μ₀²

[0196] DJ(2,1)_k=−DJ(3,0)_k−1+2(μ₄−μ₃)y_k−μ₄²+μ₃²

[0197] DJ(3,1)_k=−DJ(3,2)_k−1+2(μ₆−μ₃)y_k−μ₆²+μ₃²

[0198] DJ(3,2)_k=DJ(2,0)_k−1+2(μ₆−μ₄)y_k−μ₆²+μ₄²

[0199] 2. If

[0200] DJ(1,0)_k−1>2(μ_o−μ₁)y_k−μ₀²+μ₁²

[0201] and

[0202] DJ(3,2)_k−1<2(μ₆−μ₇)y_k−μ₆²+μ₇²

[0203] then Case 1 has occurred and:

[0204] DJ(1,0)_k=DJ(3,1)_k−1+2(μ₃−μ₁)y_k−μ₃²+μ₁²

[0205] DJ(2,0)_k=−DJ(1,0)_k−1+2(μ₄−μ₁)y_k−μ₄²+μ₁²

[0206] DJ(3,0)_k=DJ(2,1)_k−1+2(μ₆−μ₁)y_k−μ₆²+μ₁²

[0207] DJ(2,1)_k=−DJ(3,0)_k−1+2(μ₄−μ₃)y_k−μ₄²+μ₃²

[0208] DJ(3,1)_k=−DJ(3,2)_k−1+2(μ₆−μ₃)y_k−μ₆²+μ₃²

[0209] DJ(3,2)_k=DJ(2,0)_k−1+2(μ₆−μ₄)y_k−μ₆²+μ₄²

[0210] 3. If

[0211] DJ(1,0)_k−1<2(μ_o−μ₁)y_k−μ₀²+μ₁²

[0212] and

[0213] DJ(3,2)_k−1>2(μ₆−μ₇)y_k−μ₆²+μ₇²

[0214] then Case 2 has occurred and:

[0215] DJ(1,0)_k=DJ(3,0)_k−1+2(μ₃−μ₀)y_k−μ₃²+μ₀²

[0216] DJ(2,0)_k=2(μ₄−μ₀)y_k−μ₄²+μ₀²

[0217] DJ(3,0)_k=DJ(3,0)_k−1+2(μ₇−μ₀)y_k−μ₇²+μ₀²

[0218] DJ(2,1)_k=−DJ(3,0)_k−1+2(μ₄−μ₃)y_k−μ₄²+μ₃²

[0219] DJ(3,1)_k=2(μ₇−μ₃)y_k−μ₇²+μ₃²

[0220] DJ(3,2)_k=DJ(3,0)_k−1+2(μ₇−μ₄)y_k−μ₇²+μ₄²

[0221] 4. If

[0222] DJ(1,0)_k−1>2(μ_o−μ₁)y_k−μ₀²+μ₁²

[0223] and

[0224] DJ(3,2)_k−1>2(μ₆−μ₇)y_k−μ₆²+μ₇²

[0225] then Case 3 has occurred and:

[0226] DJ(1,0)_k=DJ(3,1)_k−1+2(μ₃−μ₁)y_k−μ₃²+μ₁²

[0227] DJ(2,0)_k=−DJ(1,0)_k−1+2(μ₄−μ₁)y_k−μ₄²+μ₁²

[0228] DJ(3,0)_k=DJ(3,1)_k−1+2(μ₇−μ₁)y_k−μ₇²+μ₁²

[0229] DJ(2,1)_k=−DJ(3,0)_k−1+2(μ₄−μ₃)y_k−μ₄²+μ₃²

[0230] DJ(3,1)_k=2(μ₇−μ₃)y_k−μ₇²+μ₃²

[0231] DJ(3,2)_k=DJ(3,0)_k−1+2(μ₇−μ₄)y_k−μ₇²+μ₄²

[0232] BV utilizing the fact that each difference metric can be expressed as the sum of two other difference metrics (DJ(a,c)_k+DJ(b,c)_k) it is possible to reduce the number of difference metrics to three. If the number of difference metrics is reduced to four, then each difference metric calculation requires no more than two difference metrics be summed together. This method provides greater parallelism and enhances the speed at which hardware can operate.

[0233] 1. Equations based on DJ(1,0)_k:

[0234] if

[0235] DJ(1,0)_k−1<2(μ_o−82₁)y_k−μ₀²+μ₁²

[0236] then

[0237] DJ(1,0)_k=DJ(3,2)_k−1+DJ(2,0)_k−1+2(μ₃−μ₀)y_k−μ₃²+μ₀²

[0238] DJ(2,0)_k=2(μ₄−μ₀)y_k−μ₄²+μ₀²

[0239] else

[0240] DJ(1,0)_k=DJ(3,1)_k−1+2(μ₃−μ₁)y_k−μ₃²+μ₁²

[0241] DJ(2,0)_k=−DJ(1,0)_k−1+2(μ₄−μ₁)y_k−μ₄²+μ₁²

[0242] 2. Equations based on DJ(3,2)_k:

[0243] if

[0244] DJ(3,2)_k−1<2(μ₆−μ₇)y_k−μ₆²+μ₇²

[0245] then

[0246] DJ(3,1)_k=−DJ(3,2)_k−1+2(μ₆−μ₃)y_k−μ₆²+μ₃²

[0247] DJ(3,2)_k=DJ(2,0)_k−1+2(μ₆−μ₄)y_k−μ₆²+μ₄²

[0248] else

[0249] DJ(3,1)_k=2(μ₇−μ₃)y_k−μ₇²+μ₃²

[0250] DJ(3,2)_k=DJ(3,1)_k−1+DJ(1,0)_k−1+2(μ₇−μ₄)y_k−μ₇²+μ₄²

[0251] Defining:

[0252] g₁=2(μ₀−μ₁) and P₁=−μ₀²+μ₁²,

[0253] g₂=2(μ₆−μ₇) and P₂=−μ₆²+μ₇²,

[0254] g₃=2(μ₃−μ₀) and P₃=−μ₃²+μ₀²,

[0255] g₄=2(μ₄−μ₀) and P₄=−μ₄²+μ₀²,

[0256] g₅=2(μ₃−μ₁) and P₅=−μ₃²+μ₁²,

[0257] g₆=2(μ₄−μ₁) and P₆=−μ₄²+μ₁²,

[0258] g₇=2(μ₆−μ₃) and P₇=−μ₆²+μ₃²,

[0259] g₈=2(μ₆−μ₄) and P₈=−μ₆²+μ₄²,

[0260] g₉=2(μ₇−μ₃) and P₉=−μ₇²+μ₃²,

[0261] g₁₀=2(μ₇−μ₄) and P₁₀=−μ₇²+μ₄²;

[0262] Then,

[0263] 1. Equations based on DJ(1,0)_k:

[0264] if

[0265] DJ(1,0)_k−1<g₁y_k+P₁

[0266] then

[0267] DJ(1,0)_k=DJ(3,2)_k−1+DJ(2,0)_k−1+g₃y_k+P₃

[0268] DJ(2,0)_k=g₄y_k+P₄

[0269] else

[0270] DJ(1,0)_k=DJ(3,1)_k−1+g₅y_k+P₅

[0271] DJ(2,0)_k=−DJ(1,0)_k−1+g₆y_k+P₆

[0272] 2. Equations based on DJ(3,2)_k:

[0273] if

[0274] DJ(3,2)_k−1<g₂y_k+P₂

[0275] then

[0276] DJ(3,1)_k=−DJ(3,2)_k−1+g₇y_k+P₇

[0277] DJ(3,2)_k=DJ(2,0)_k−1+g₈y_k+P₈

[0278] else

[0279] DJ(3,1)_k=g₉y_k+P₉

[0280] DJ(3,2)_k=DJ(3,1)_k−1+DJ(1,0)_k−1+g₁₀y_k+P₁₀

[0281] Again, one of skill in the art will recognize that alternative approaches may be utilized to derive the difference metrics.

[0282] As above, in steps 306 and 307, the sample outputs of the expected waveforms are determined, for example, by measuring a number of sample outputs for the waveforms, and calculating the mean values of each of the sample points, and the metric coefficient numerical values are calculated for the mean values of the sample outputs, thereby providing the numerical metric coefficients 309.

[0283] Referring to FIG. 6, the programmed metric coefficients are applied to each digital sample of channel output signals “y”, to generate the alternative metrics and the inputs to the difference metrics so that the difference metrics representing the 4 cases of FIG. 9 may be calculated.

[0284] FIGS. 10 and 11 illustrate an embodiment of the present invention for calculating the difference metric values, using a second order detection, for example, of a signal of the form of signal 33 of FIGS. 3B and 4B, or, with alternative programmed inputs, of a signal of the form of signal 35 of FIGS. 3C and 4C, where the respective samples of the signal are very unequal, as discussed above. The logic of FIGS. 10 and 11 provides 4 selected second order difference metrics at outputs 86-89 by combining the inputs 90-97 from the outputs 465-468 of FIG. 6, combined with previous second order difference metrics at outputs 100-103 from registers 104-107. The inputs are combined by logic 114-122 in accordance with the above equations to provide the various difference metrics.

[0285] The selection is under the control of the logic of FIG. 13 by comparison logic 124-127, where the alternative metrics at outputs 54 and 55 of FIG. 6 are compared to selected second order previous difference metrics DJ(1,0)_(k−1)100 and DJ(3,2)_(k−1)102 of FIG. 10. The alternative metrics are respectively compared with the selected previous difference metrics in logic 124-127 to provide the respective CSD0 and CSD1 outputs 128 and 129. The state of the outputs 128 and 129 again provide the selection codes to select the difference metrics at multiplexors 110-113 in FIGS. 10 and 11. As described above, the selected difference metrics remain within defined bounds in accordance with the present invention, and are not continuously accumulated without bounds.

[0286] The comparisons by the logic 124-127 provide the respective positive and negative states on outputs 128 and 129 which identify the one of the finite number of states represented by the selected accumulated metric, and are used to set a maximum likelihood path memory 130 to a maximum likelihood state dictated by the identified finite state. The maximum likelihood elements path memory comprises a plurality of identical sub-blocks which are depicted in FIG. 12 as sub-block 140. The path memory 130 provides the appropriate data bit at output 131.

[0287] An embodiment of a third order maximum likelihood detector is described with reference to FIGS. 13-19. Referring to the signals of FIGS. 3D and 4D, the channel sample y_kis the function of the four input bits a_k, a_k−1, a_k−2, and a_k−3. As discussed above, the goal of the maximum likelihood detector is to produce an accurate estimate of the channel input sequence {a_k} by observing the pulse amplitude modulated sequence {y_k}. The maximum likelihood detector does this by maximizing the likelihood function through the power of recursive nature of the Viterbi decoder, with the log of the likelihood function accumulated into metrics at each sample time k.

[0288] In the (1, 7) third order decoder, there are 6 possible states and metrics. There are two states that are not valid modulation code outputs which can be eliminated. Thus, with ak representing the current bit and sk representing the preceding state: $\begin{array}{c}{m\left(0\right)}_k=\mathrm{maximum}\text{:}m{\left(0\right)}_{k-1}+\ln [p(y_k|s_k=0;a_k=0)]\\ {m\left(1\right)}_{k-1}+\ln [p(y_k|s_k=1;a_k=0)]\end{array}$ ${m\left(1\right)}_k={m\left(3\right)}_{k-1}+\ln [p(y_k|s_k=3;a_k=0)]$ $\begin{array}{c}{m\left(3\right)}_k=\mathrm{maximum}\text{:}{m\left(6\right)}_{k-1}+\ln [p(y_k|s_k=6;a_k=0)]\\ {m\left(7\right)}_{k-1}+\ln [p(y_k|s_k=7;a_k=0)]\\ {m\left(4\right)}_k=\mathrm{maximum}\text{:}m{\left(0\right)}_{k-1}+\ln [p(y_k|s_k=0;a_k=1)]\\ {m\left(1\right)}_{k-1}+\ln [p(y_k|s_k=1;a_k=1)]\end{array}$ ${m\left(6\right)}_k={m\left(4\right)}_{k-1}+\ln [p(y_k|s_k=4;a_k=1)]$ $\begin{array}{c}{m\left(7\right)}_k=\mathrm{maximum}\text{:}m{\left(6\right)}_{k-1}+\ln [p(y_k|s_k=6;a_k=1)]\\ {m\left(7\right)}_{k-1}+\ln [p(y_k|s_k=7;a_k=1)].\end{array}$

[0289] Also, because of the modulation code, the metrics at states 1 and 6 can select only one previous metric.

[0290] Thus, for the generalized 3rd order Viterbi decoder, where the channel signal {y_k} contains an ideal signal perturbed by zero mean additive white gaussian noise of variance δ², then: y_k=f(a_k, a_k−1, a_k−2, a_k−3) and s_k=4a_k−1+2a_k−2+a_k−3, and (the notation is switched to separately represent the 0 and 1 in view of the complexity of the equations),

[0291] ln[p(y_k|s_k=0;a_k=0)]=−((y_k−μ_0/0)²/2 δ²)−(1/2)ln[2 πδ²]

[0292] ln[p(y_k|s_k=1;a_k=0)]=−((y_k−μ_1/0)²/2 δ²)−(1/2)ln[2 πδ²]

[0293] ln[p(y_k|s_k=3;a_k=0)]=−((y_k−μ_3/0)²/2 δ²)−(1/2)ln[2 πδ²]

[0294] ln[p(y_k|s_k=4;a_k=0)]=−((y_k−μ_4/0)²/2 δ²)−(1/2)ln[2 πδ²]

[0295] ln[p(y_k|s_k=6;a_k=0)]=−((y_k−μ_6/0)²/2 δ²)−(1/2)ln[2 πδ²]

[0296] ln[p(y_k|s_k=7;a_k=0)]=−((y_k−μ_7/0)²/2 δ²)−(1/2)ln[2 πδ²]

[0297] ln[p(y_k|s_k=0;a_k=1)]=−((y_k−μ_0/1)²/2 δ²)−(1/2)ln[2 πδ²]

[0298] ln[p(y_k|s_k=1;a_k=1)]=−((y_k−μ_1/1)²/2 δ²)−(1/2)ln[2 πδ²]

[0299] ln[p(y_k|s_k=3;a_k=1)]=−((y_k−μ_3/1)²/2 δ²)−(1/2)ln[2 πδ²]

[0300] ln[p(y_k|s_k=4;a_k=1)]=−((y_k−μ_4/1)²/2 δ²)−(1/2)ln[2 πδ²]

[0301] ln[p(y_k|s_k=6;a_k=1)]=−((y_k−μ_6/1)²/2 δ²)−(1/2)ln[2 πδ²]

[0302] ln[p(y_k|s_k=7;a_k=1)]=−((y_k−μ_7/1)²/2 δ²)−(1/2)ln[2 πδ²]

[0303] The calculations of steps 300-309 of FIG. 20 are similar to the above, as is understood by those of skill in the art, and results in six possible states and metrics, respectively (after substitution of log probabilities with elimination of all common terms into the metrics) giving the following equations:

[0304] m(0)_k=maximum {m(0)_k−1+2μ_0/0y_k−μ_0/0²; m(1)_k−1+2μ_1/0y_k−μ_1/0²}

[0305] m(1)_k=m(3)_k−1+2μ_3/0y_k−μ_3/0²

[0306] m(3)_k=maximum {m(6)_k−1+2μ_6/0y_k−μ_6/0²; m(7)_k−1+2μ_7/0y_k−μ_7/0²}

[0307] m(4)_k=maximum {m(0)_k−1+2μ_0/1y_k−μ_0/1²; m(1)_k−1+2μ_1/1y_k−μ_1/1²}

[0308] m(6)_k=m(4)_k−1+2μ_4/1y_k−μ_4/1²

[0309] m(7)_k=maximum {m(6)_k−1+2μ_6/1y_k−μ_6/1²;m(7)_k−1+2μ_7/1y_k−μ_7/1²}.

[0310] Since there are only six possible sates and metrics, and, because of the 1, 7 modulation code, the metrics at states 2 and 6 can select only one previous metric, the reduction of states and metric branching due to the modulation code make the difference metric reductions far simpler, resulting in six difference metrics rather than the fifteen possible difference metrics. The derivation and reduction of the difference metrics, based on the above, is understood by those of skill in the art and will not be repeated here. Various approaches may be made in the reduction process within the context of formulating the appropriate reductions. In one example,

[0311] Defining:

[0312] g₁=2(μ_0/0−μ_1/0) and P₁=+μ_1/0²−μ_0/0²,

[0313] g₂=2(μ_6/0−μ_7/0) and P₂=+μ_7/0²−μ_6/0²,

[0314] g₃=2(μ_0/1−μ_1/1) and P₃=+μ_1/1²−μ_0/1²,

[0315] g₄=2(μ_6/1−μ_7/1) and P₄=+μ_7/1²−μ_6/1²,

[0316] g₅=2(μ_3/0−μ_0/0) and P₅=+μ_0/0²−μ_3/0²,

[0317] g₆=2(μ_3/0−μ_1/0) and P₆=+μ_1/0²−μ_3/0²,

[0318] g₇=2(μ_6/0−μ_3/0) and P₇=+μ_3/0²−μ_6/0²,

[0319] g₈=2(μ_4/1−μ_6/0) and P₈=+μ_6/0²−μ_4/1²,

[0320] g₉=2(μ_7/0−μ_3/0) and P₉=+μ_3/0²−μ_7/0²,

[0321] g₁₀=2(μ_4/1−μ_7/0) and P₁₀=+μ_7/0²−μ_4/1²,

[0322] g₁₁=2(μ_4/1−μ_0/1) and P₁₁=+μ_0/1²−μ_4/1²,

[0323] g₁₂=2(μ_0/1−μ_3/0) and P₁₂=+μ_3/0²−μ_0/1²,

[0324] g₁₃=2(μ_4/1−μ_1/1) and P₁₃=+μ_1/1²−μ_4/1²,

[0325] g₁₄=2(μ_1/1−μ_3/0) and P₁₄=+μ_3/0²−μ_1/1²,

[0326] g₁₅=2(μ_6/1−μ_4/1) and P₁₅=+μ_4/1²−μ_6/1²,

[0327] g₁₆=2(μ_7/1−μ_4/1) and P₁₆=+μ_4/1²−μ_6/1²;

[0328] Then,

[0329] 1. For State 1:

[0330] Equations based on DJ(1,0)_k; (CSD0):

[0331] if

[0332] DJ(1,0)_k−1<g₁y_k+P₁

[0333] then

[0334] DJ(1,0)_k=DJ(3,1)_k−1+DJ(1,0)_k−1+g₅y_k+P₅

[0335] else

[0336] DJ(1,0)_k=DJ(3,1)_k−1+g₆y_k+P₆

[0337] 2. For state 3:

[0338] Equations based on DJ(7,6)_k; (CSD1):

[0339] if

[0340] DJ(7,6)_k−1<g₂y_k+P₂

[0341] then

[0342] DJ(3,1)_k=DJ(6,3)_k−1+g₇y_k+P₇

[0343] DJ(6,3)_k=−DJ(6,4)_k−1+g₈y_k+P₈

[0344] else

[0345] DJ(3,1)_k=DJ(7,6)_k−1+DJ(6,3)_k−1+g₉y_k+P₉

[0346] DJ(6,3)_k=−DJ(7,6)_k−1−DJ(6,4)_k−1+g₁₀y_k+P₁₀

[0347] 3. For State 4:

[0348] Equations based on DJ(1,0)_k; (CSD2):

[0349] if

[0350] DJ(1,0)_k−1<g₃y_k+P₃

[0351] then

[0352] DJ(6,4)_k=DJ(4,1)_k−1+DJ(1,0)_k−1+g₁₁y_k+P₁₁

[0353] DJ(4,1)_k=−DJ(3,1)_k−1−DJ(1,0)_k−1+g₁₂y_k+P₁₂

[0354] else

[0355] DJ(6,4)_k=DJ(4,1)_k−1+g₁₃y_k+P₁₃

[0356] DJ(4,1)_k=−DJ(3,1)_k−1+g₁₄y_k+P₁₄

[0357] 4. For state 7:

[0358] Equations based on DJ(7,6)_k; (CSD3):

[0359] if

[0360] DJ(7,6)_k−1<g₄y_k+P₄

[0361] then

[0362] DJ(7,6)_k=DJ(6,4)_k−1+g₁₅y_k+P₁₅

[0363] else

[0364] DJ(7,6)_k=DJ(7,6)_k−1+DJ(6,4)_k−1+g₁₆y_k+P₁₆;

[0365] As above, the measurements and calculations are made to determine the numerical values of the programmable metric coefficients.

[0366] Using the EPRIV Viterbi decoder, which is a more restricted version of the 3rd order Viterbi decoder, the mean values of the probability functions may be determined through a linear process on the digital function (1−D)(1+D)².

[0367] An example of mean values for calculating the programming inputs for the programmable coefficients is as follows.

[0368] For EPRIV, y_k=h_oa_k+h₁a_k−1+h₂a_k−2+h₃a_k−3where h_o=1, h₁=1, h₂=−1, and h₃=−1. Thus:

[0369] μ_o/o=0

[0370] μ_1/o=h₃=−1

[0371] μ_3/o=h₂+h₃=−2

[0372] μ_4/o=h₁=1

[0373] μ_6/o=h₁+h₂=0

[0374] μ_7/o=h₁+h₂+h₃=−1

[0375] μ_0/1=h₀=1

[0376] μ_1/1=h₀+h₃=0

[0377] μ_3/1=h₀+h₂+h₃=−1

[0378] μ_4/1=h₀+h₁=2

[0379] μ_6/1=h₀+h₁+h₂=1

[0380] μ_7/1=h₀+h₁+h₂+h₃=0

[0381] Substitution of the above mean values into the difference metrics gives the following equations:

[0382] For State 0:

[0383] If

[0384] 2y_k+1>DJ(1,0)_k−1

[0385] Then

[0386] DJ(1,0)_k=DJ(3,1)_k−1+DJ(1,0)_k−1−4y_k−4

[0387] Else

[0388] DJ(1,0)_k=DJ(3,1)_k−1−2y_k−3

[0389] For State 3:

[0390] If

[0391] 2y_k+1>DJ(7,6)_k−1

[0392] Then

[0393] DJ(3,1)_k=DJ(6,3)_k−1+4y_k+4

[0394] DJ(6,3)_k=−DJ(6,4)_k−1+4y_k−4

[0395] Else

[0396] DJ(3,1)_k=DJ(7,6)_k−1+DJ(6,3)_k−1+2y_k+3

[0397] DJ(6,3)_k=−DJ(7,6)_k−1−DJ(6,4)_k−1+6y_k−3

[0398] For State 4:

[0399] If

[0400] 2y_k−1>DJ(1,0)_k

[0401] Then

[0402] DJ(6,4)_k=DJ(4,1)_k−1−DJ(1,0)_k−1+2y_k−3

[0403] DJ(4,1)_k=−DJ(3,1)_k−1−DJ(1,0)_k−1−6y_k+3

[0404] Else

[0405] DJ(6,4)_k=DJ(4,1)_k−1+4y_k−4

[0406] DJ(4,1)_k=−DJ(3,1)_k−1+4y_k+4

[0407] For State 7:

[0408] If

[0409] 2y_k−1>DJ(7,6)_k−1

[0410] Then

[0411] DJ(7,6)_k=DJ(6,4)_k−1−2y_k+3

[0412] Else

[0413] DJ(7,6)_k=DJ(7,6)_k−1+DJ(6,4)_k−1−4y_k+4

[0414] Thus, referring to FIG. 6, the programmed inputs respectively comprise:

[0415] g₁=2, P₁=1;

[0416] g₂=2, P₂=1;

[0417] g₃=2, P₃=−1;

[0418] g₄=2, P₄=−1;

[0419] g₅=−4, P₅=−4;

[0420] g₆=−2, P₆=−3;

[0421] g₇=4, P₇=4;

[0422] g₈=4, P₈=−4;

[0423] g₉=2, P₉=3;

[0424] g₁₀=2, P₁₀=−3;

[0425] g₁₁=2, P₁₁=−3;

[0426] g₁₂=−6, P₁₂=6;

[0427] g₁₃=4, P₁₃=−4;

[0428] g₁₄=4, P₁₄=4;

[0429] g₁₅=−2, P₁₅=3;

[0430] g₁₆=−4, P₁₆=4.

[0431] These numerical metric coefficients are then programmed into the respective registers of the logic of FIG. 6. As discussed above, the programmable multiplicative and additive numerical metric coefficients allow the decoder to be adaptable. For example, upon a change of media, the mean of probability functions may vary due to variation of the transfer function of the channel, and other numerical metric coefficients may be selected.

[0432] FIGS. 14-17 illustrate an embodiment of the present invention for calculating the difference metric values, using the exemplary third order detection equations, above. For example, the difference metric values are calculated from input samples y_kof a signal of the form of signal 37 of FIGS. 3D and 4D, where the respective samples of the signal are very unequal, as discussed above. The logic of FIGS. 14-17 provide 6 selected third order difference metrics at outputs 221-226 by combining the inputs 235-246 from the outputs 468 of FIG. 6, together with previous third order difference metrics at outputs 251-256 from registers 257-262. The inputs are combined by logic 263-274 in accordance with the above equations to provide the various difference metrics.

[0433] The selection is under the control of the logic of FIG. 18 by comparison logic 275-278, where the alternative metrics, calculated from the programmed metric coefficients and supplied at outputs 54, 55, 465, etc., of FIG. 6, are provided, respectively, at inputs 231, 232, 233, and 234 and compared to selected third order previous difference metrics DJ(1,0)_(k−1)251, and DJ(7,6)_(k−1)252 of FIGS. 14 and 15. The alternative metrics are respectively compared with the selected previous difference metrics in logic 275-278 to provide the respective CSD0, CSD1, CSD2, and CSD3 outputs 280-283. The state of the outputs 280-283 again provide the selection codes to select the difference metrics at multiplexors 291-296 in FIGS. 14-17. As described above, the selected difference metrics remain within defined bounds in accordance with the present invention, and are not continuously accumulated without bounds.

[0434] The comparisons by the logic 275-278 of FIG. 18 provide the respective positive and negative states on outputs 280-283 which identify the one of the finite number~of states represented by the selected accumulated metric, and are used to set a maximum likelihood path memory 297 to a maximum likelihood state dictated by the identified finite state. The maximum likelihood elements path memory comprises a plurality of identical sub-blocks which are depicted in FIG. 19 as sub-block 298. The path memory 130 will provide the appropriate data bit at output 299.

[0435] FIGS. 22 and 23 illustrate an embodiment of the present invention for programming the numerical metric coefficients of the maximum likelihood detector for carrying out step 321 of FIG. 21. A removable media 340 to be detected may comprise a label having markings thereon for identifying the media 340, or the first few bytes of the media to be read may have more universal characters which are easily read which identify the media 340. Those of skill in the art may envision further alternative identifiers.

[0436] As discussed above, examples of different types of removable media 340 include optical disk and optical tape storage, which may be read-only, write-once, or rewritable media, and may be different types of media, such as molded, magneto-optic and phase-change media, or magnetic tape media, which have media to media variation based on different data densities on the same type of media, different types of media such as chromium-based, nickel-based, ferrous-based media, or between materials used by different manufacturers, or differing thicknesses and therefore differing media to head characteristics over the recording and read head.

[0437] A media detector 342 may therefore comprise a well-known optical reader or scanner (of the type used in libraries) or may comprise logic associated with the read channel, and, in step 343, determines the type of media 340. Numerical metric coefficients that have been generated in the process of FIG. 20, may be stored in a lookup table 344 and, in step 345, the numerical metric coefficients are selected by coefficient selector 346. In step 347, the coefficient selector 346 provides the selected numerical metric coefficients to the maximum likelihood detector 348, at the appropriate registers, to program the maximum likelihood detector with the selected numerical metric coefficients.

[0438] Thus, the present invention is able to provide maximum likelihood detection of data recorded as analog signals representing a finite number of states, which reduces errors resulting from maximum likelihood detection under differing circumstances, typically as the result of differing media 340. Further, the metric coefficients are derived from the difference between metrics directly associating “0” and “1” states of the recorded signal for maximum likelihood detection, to insure that no accumulation of metrics is unbounded, so that there is never an overflow at the accumulation register.

[0439] While the preferred embodiments of the present invention have been illustrated in detail, it should be apparent that modifications and adaptations to those embodiments may occur to one skilled in the art without departing from the scope of the present invention as set forth in the following claims.