Survival selection rule

Details Survival selection rule Survival selection rule

1999-12-16

2002-07-02

Baker, Stephen (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06415415

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to encoding for disk drives and, particularly, to an improved Viterbi detector for sampled amplitude read channels.
2. Description of the Related Art
Viterbi decoders are typically employed in sampled amplitude channels. Viterbi decoders are specific implementations of the Viterbi algorithm. A Viterbi detector unit is based on periodic examination of metrics associated with alternate sequences of recorded bits, wherein each sequence is typically labeled as a “path” and the associated metric is designated a “path metric.” The most probable path is then determined by choosing a minimum path metric based on an iterative process involving successive comparison of associated path metrics. This is illustrated by way of example in
FIG. 1
, which shows an exemplary trellis for a partial response channel. In particular, as shown in
FIG. 1
, a Viterbi detector is characterized by a labeled trellis H having Q states s
1
,s
2
, . . . ,s
Q
. In the example shown, Q=4. For each state sand each time k, a metric m
s
(k), a survivor sequence ss
s
(k), metric/survivor sequence update rules, and an initial state s* are defined. In the example illustrated, s* is the state s
1
at time k−4. Given a state s (e.g., state
100
) and a time k, the survivor sequence ss
s
(k) is a label sequence in H starting from s* at time zero and ending on s at time k. Usually, only the last t labels of each survivor sequence are saved. The parameter t is called the truncation depth of the Viterbi detector. Thus, in
FIG. 1
, t=4.
In traditional Viterbi detectors, the updating rules are as follows. Let s
1
, s
2
, . . . , s
q
be the predecessor states to the state s. And let h
i
be the label on the edge from s
i
to s. Further, let r
k
be the current value of the received sequence. Then, the updating rules are:
Update m
s
(k): m
s
(k)=min{m
s
1
(k−1)+(r
k
−h
1
)
2
, . . . ,m
s
q
(k−1)+(r
k
−h
q
)
2
}.
Update ss
s
(k): If the j
th
state, s
j
, produces the minimum above (m
s
(k)), then ss
s
(k)=(ss
s
j
(k−1), h
j
).
For every state, s, and time, k, let v
s
=(last t coordinates of ss
s
(k)). In general, the output of a Viterbi detector at time k, Y(k), is a function of
(&ngr;
s1
(1),&ngr;
s2
(1), . . . ,&ngr;
sQ
(1):
m
s1
(
k
),
m
s2
(
k
) , . . . ,
m
sQ
(
k
)),
as shown:
Y
(
k
)
=F
(&ngr;
s1
(1),&ngr;
s2
(1), . . . ,&ngr;
sQ
(1):
m
s1
(
k
) ,
m
s2
(
k
), . . . ,
m
sQ
(
k
).
A first conventional implementation of the function F is shown below:
F
1
(&ngr;
s1
(1),&ngr;
s2
(1), . . . ,&ngr;
sQ
(1):
m
s1
(k),
m
s2
(k), . . . ,
m
sQ
(k))=&ngr;
sw
(1), for a fixed w.
That is, the Viterbi detector output at time k is determined to be the output at a particular state w. For example, in
FIG. 1
, an arbitrary state w is state
52
. According to F
1
, the Viterbi output is the path ending at state
52
for which the metric is minimized.
Another conventional implementation is shown below:
F
2
(&ngr;
s1
(1),&ngr;
s2
(1), . . . ,&ngr;
sQ
(1):
m
s1
(
k
),
m
s2
(
k
), . . . ,
m
sQ
(
k
)=&ngr;
sw
(1),
where
m
sw
(
k
)=min{
m
s1
(
k
),
m
s2
(
k
), . . . ,
m
sQ
(
k
)}.
F
2
thus determines a path metric for each state at time k (e.g., states
50
,
52
,
54
, and
56
) and the output of the Viterbi detector is the sequence which minimizes the branch metrics over all the states and all possible paths.
The function F
1
is easy to implement, but F
2
is a better function—it produces fewer detector errors. However, when Q is large F
2
is not easy to implement.
SUMMARY OF THE INVENTION
These and other drawbacks in the prior art are overcome in large part by a system and method according to the present invention. In particular, a survival selection rule according to the present invention compares paths at a plurality of endpoint states but fewer than the total number of endpoint states.


REFERENCES:
patent: 4888779 (1989-12-01), Karabed et al.
patent: 4939555 (1990-07-01), Calderbank et al.
patent: 5040191 (1991-08-01), Forney, Jr. et al.
patent: 5111483 (1992-05-01), Serfaty
patent: 5181209 (1993-01-01), Hagenauer et al.
patent: 5214672 (1993-05-01), Eyuboglu et al.
patent: 5291499 (1994-03-01), Behrens et al.
patent: 5327440 (1994-07-01), Fredrickson et al.
patent: 5349608 (1994-09-01), Graham et al.
patent: 5377133 (1994-12-01), Riggle
patent: 5406570 (1995-04-01), Berrou et al.
patent: 5412669 (1995-05-01), Foland, Jr.
patent: 5418795 (1995-05-01), Itakura et al.
patent: 5450338 (1995-09-01), Oota et al.
patent: 5497384 (1996-03-01), Fredrickson et al.
patent: 5537445 (1996-07-01), Blaker et al.
patent: 5684811 (1997-11-01), Doran
patent: 5689532 (1997-11-01), Fitzpatrick
patent: 5691993 (1997-11-01), Fredrickson
patent: 5754352 (1998-05-01), Behrens et al.
patent: 5757294 (1998-05-01), Fisher et al.
patent: 5784392 (1998-07-01), Czaja et al.
patent: 5809080 (1998-09-01), Karabed et al.
patent: 5809081 (1998-09-01), Karabed et al.
patent: 5812334 (1998-09-01), Behrens et al.
patent: 5841818 (1998-11-01), Lin et al.
patent: 5844738 (1998-12-01), Behrens et al.
patent: 5844741 (1998-12-01), Yamakawa et al.
patent: 5844922 (1998-12-01), Wolf et al.
patent: 5857002 (1999-01-01), Melas
patent: 5881075 (1999-03-01), Kong et al.
patent: 5928378 (1999-07-01), Choi
patent: 6038269 (2000-03-01), Raghavan
patent: 6084925 (2000-07-01), Baek
McEliece et al., “Truncation Effects in Viterbi Decoding”, IEEE Conf. Military Commun., vol. 1, Oct. 1989, pp. 171-178.*
Kubota et al., “Novel Viterbi Decoder VLSI Implementation and its Performance”, IEEE Transactions on Communications, vol. 41, No. 8, Aug. 1993, pp. 1170-1178.

Affiliated with

Also associated with

Rating

Survival selection rule does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Survival selection rule, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Survival selection rule will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2837671