Reduced-complexity sequence detection

Details Reduced-complexity sequence detection Reduced-complexity sequence detection

2000-04-05

2003-04-22

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C360S040000

Reexamination Certificate

active

06553541

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to electronic devices, and more particularly to partial response sequence detectors as are useful in magnetic data storage and retrieval.
Magnetic recording and playback systems for digital data storage typically have a functional structure as illustrated in FIG.
13
. Such a system operates as follows: for a write of data to storage, data bits first receive error correction encoding (such as Reed-Solomon); this coding aims to correct errors generated in the write-read process and which escape correction by the detection method of the read process. Further, interleaving blocks of error correction encoded bits helps correct bursts of errors by spreading the errors over many blocks. Next, the error correction encoded bits are modulation (channel) coded (such as runlength-limited coding); the modulation coding helps read timing recovery and may eliminate troublesome bit patterns. A further preceding may help intersymbol interference decoding. The modulation coded bits modulate the polarity of the write current in a read/write head over the magnetic media (e.g., a spinning disk) to set the magnetization directions of domains in the magnetic media. The pattern of magnetization directions constitutes the stored data.
The read process reverses the write process. First, the read/write head senses the domain magnetization direction changes by voltages induced through magnetoresistance changes. After amplification the sensed voltages drive clocked analog-to-digital converters and equalizers to yield a stream of digital samples. Noise in the read sensing, amplification, and conversion generates errors in the stream of digital samples. A detector (such as a peak detector or a Viterbi maximum likelihood detector) recovers the modulation encoded bits from the stream of digital samples. The modulation decoder then converts the coded bits to the error correction bits, and lastly, the deinterleaver and error correction decoder corrects errors and recovers the data bits.
For partial response signaling various classes of frequency response for the signal channel prior to detection have been defined; and the class IV response appears particularly suitable for magnetic recording due to pulse shapes requiring minimal equalization. The partial response class IV channel is defined by a channel transfer function polynomial of the form (1−D)(1+D)
N
where N is a positive integer and D is a one period delay.
FIGS. 14
a
-
14
c
shows the ideal sensed voltage pulse shapes and sampling times for N=1, 2, and 3; the corresponding pulses are termed PR4, EPR4, and E
2
PR4 (or EEPR4), respectively. Thus an (E)PR4 sensed voltage consists of a sequence of overlapping (E)PR4 pulses spaced one period apart and with positive, negative, or zero amplitudes depending upon the corresponding transitions of magnetization domain orientations. The sampling of the (E)PR4 sensed voltage yields the digital stream input to the detector, typically a sequence detector such as a maximum likelihood Viterbi decoder. Higher storage densities on a magnetic disk require more samples per induced pulse and consequent more overlap, and thus use the higher order partial response channels. For example, storage densities of about 3 bits per pulse halfwidth would use E
2
PR4 which has four nonzero samples per pulse; see
FIG. 14
c
. The demand for such high density originates with small, portable devices such as notebook computers.
However, higher order partial response channels require more complex Viterbi detectors because the number of states grows as 2
N+1
, and thus the corresponding number of computations and the time required to perform the computations increases rapidly. But high complexity implies high power consumption and slow execution, and this contradicts the requirements of notebook computers and their battery-based power supplies. Hence, there is a demand for low-complexity Viterbi detectors for high order partial response channels.
Maximum likelihood detection of a digital stream with intersymbol interference can be described in terms of maximizing probabilities of paths through a trellis of state transitions (branches). Each state corresponds to a possible pattern of recently received data bits and each stage of the trellis corresponds to a receipt of the next (noisy) input. For example,
FIG. 15
illustrates one stage (one sample input) in the trellis for an EPR4 detector; the states are labeled with three previous data bits (reflecting the three sample overlap of pairs of pulses corresponding to isolated data bits) and the branches are labeled with the bit for the transition plus the corresponding scaled noiseless sample input (2, 1, 0, −1, or −2).
FIG. 16
shows a prior art Viterbi detector for EPR4 which includes one add-compare-select (ACS) unit for each trellis state and a branch metric unit for each of the target levels t
ij
; the survival register for each state is in the path memories block. Each branch metric unit computes the square of the difference between its target value and the noisy input sample value. Each ACS stores a metric for its state and has inputs for the appropriate branch metric computations and the related state metrics from other ACS units. At receipt of an input sample signal to the detector, each ACS adds its (two) input branch metric computations to the corresponding state metrics of the states emitting the branches; and then it compares these (two) sums and selects the smaller as the updated state metric for its state. Each state's survival register updates its contents to maintain a survival path for the state; that is, the sequence of selected branches (bits) that have led to the updated state metric. The detected branches will correspond to the path with the smallest metric. At any time the maximum likelihood path through the trellis up to that time is the path traced backwards through the trellis starting from the state with the smallest state metric at that time and recursively using the branch previously selected as the branch into the traced-to state; that is, the survival register contents for the state with the smallest state metric.
The length of the survival registers depends on the modulation code used. As the decision goes deeper into the survival registers, more of the contesting survival paths (versus the correct path) will be eliminated, the detected data will become more accurate.
A straightforward implementation of a Viterbi sequence detector for E
2
PR4 channel requires 16 state metric units and 7 branch metric computations. This can include an array of 16 single-step or two-step (combining two trellis steps) add-compare-select (ACS) units. In the case of a single-step implementation, the ACS units are two-way (two sums of branch metric plus state metric compared) and in the case of a two-step, they are four-way (four sums of branch metric pairs plus state metric compared). And the two-step has two successive branch metrics computed and input to an ACS unit.
The performance of the Viterbi detector is key to the performance of the whole magnetic read channel. Its increased complexity reduces the speed of the channel, while increasing the power consumed and integrated circuit area occupied.
Several methods have been proposed to reduce the complexity of the Viterbi detector; including both coding constraints and elimination of less probable paths in the trellis. For example, U.S. Pat. No. 5,291,499 chooses a set of error events to be considered and then groups states than can share a single ACS without neglecting the chosen error events. Each ACS compares the sums of branch metrics plus state metrics for all states in the groups and retains only the smallest; that is, only a single one of the states in the group is retained by the ACS. This effectively discards less likely trellis paths.
Another approach limits the target levels considered for samples to the Viterbi detector and thus limits the number of branches to consider. For example, Shaflee and Moon, Low-Complexity Viterbi

Affiliated with

Also associated with

Rating

Reduced-complexity sequence detection does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reduced-complexity sequence detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduced-complexity sequence detection will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3013163