 |
Claims  |
|
|
We claim:
1. An apparatus for processing an input stream of pulse samples in a PRML
communication channel, comprising:
(a) a receiver connected to receive the input stream of pulse samples;
(b) at least one sequence detector, connected to receive the pulse samples,
for detecting a digital sequence of binary data from the pulse samples,
comprising a plurality of path memories, the path memories comprising a
plurality of memory elements, each memory element storing one bit of the
digital sequence;
(c) at least one parity generator for generating a parity signal having two
states, active and inactive, responsive to the number of "1" bits stored
in at least two of the memory elements of at least one of the path
memories of the sequence detector:
(d) at least one path selector for selecting one of two of the path
memories out of the plurality of path memories of the sequence detector,
the path selector using the parity signal for selecting the path memory;
and
(e) at least one look ahead generator for generating a look ahead signal
having two states, active and inactive, responsive to the bits stored in
at least one of the memory elements of at least two of the path memories
of the sequence detector, the path selector using the look ahead signal
for selecting the path memory.
2. The apparatus as recited in claim 1, wherein:
the digital sequence comprising a plurality of codewords wherein each
codeword comprises a predetermined k number of bits; and
the sequence detector storing a first codeword and at least part of a
second codeword in the plurality of path memories;
the parity signal being generated from the memory elements of the path
memories storing at least part of the first codeword; and
the look ahead signal being generated from the memory elements of the path
memories storing at least part of the second codeword; and
the path selector selecting the path memory storing at least part of the
first codeword.
3. The apparatus as recited in claim 2, wherein:
the sequence detector comprises four path memories comprising n+k memory
elements each, wherein n is the number of bits of the second codeword
stored in the path memories; and
the path memories storing two survivor sequences of k bits, different in
only one bit, wherein one of the survivor sequences storing the first
codeword; and
the path selector selecting the path memory storing the survivor sequence
comprising the first codeword.
4. The apparatus as recited in claim 3, wherein:
the path memories storing an even and odd interleave subsequence, the odd
interleave consisting only of odd bit positions and the even interleave
consisting of even bit positions; and
the at least one parity generator comprising a first and second parity
generator; and
the first parity generator responsive to the memory elements storing the
odd interleave of the two survivor sequences of k bits; and
the second parity generator responsive to the memory elements storing the
even interleave of the two survivor sequences of k bits; and
the at least one path selector comprising a first and second path selector;
and
the first path selector responsive to the first parity generator and for
selecting the path memory storing the odd interleave of the survivor
sequence comprising the first codeword; and
the second path selector responsive to the second parity generator and for
selecting the path memory storing the even interleave of the survivor
sequence comprising the first codeword; and
the look ahead signal responsive to at least one of the n memory elements
of at least two of the path memories.
5. The apparatus as recited in claim 2, wherein:
the input stream of pulse samples is divided into an even and odd
interleave; and
the first codeword comprising a first and second part wherein each part
comprising at least one bit; and
the sequence detectors comprise two sequence detectors, each sequence
detector comprising two path memories, each sequence detector processing
one of the interleaves; and
the path memories of one of the sequence detectors storing a single
survivor sequence, the single survivor sequence comprising the first part
of the first codeword; and
the path memories of the other sequence detector storing two survivor
sequences, different in one bit, wherein one of the two survivor sequences
comprising the second part of the first codeword; and
the path selector selecting the path memory storing the survivor sequence
comprising the second part of the first codeword; and
the look ahead signal responsive to the sequence detector comprising the
path memories storing the single survivor sequence.
6. An apparatus for processing an input stream of pulse samples in a PRML
communication channel, comprising:
(a) a receiver connected to receive the input stream of pulse samples;
(b) at least one sequence detector, connected to receive the pulse samples,
for detecting a digital sequence of binary data from the pulse samples,
comprising a plurality of path memories, the path memories comprising a
plurality of memory elements, each memory element storing one bit of the
digital sequence;
(c) at least one parity generator for generating a parity signal having two
states, active and inactive, responsive to the number of "1" bits stored
in at least two of the memory elements of at least one of the path
memories of the sequence detector; and
(d) at least one path selector for selecting one of two of the path
memories out of the plurality of path memories of the sequence detector,
the path selector using the parity signal for selecting the path memory,
wherein:
the digital sequence comprising a plurality of codewords wherein each
codeword comprises a predetermined k number of bits;
the sequence detector storing a first codeword and at least part of a
second codeword in the plurality of path memories;
the parity signal being generated from the memory elements of the path
memories storing at least part of the first codeword; and
the path selector selecting the path memory such that the parity of bits
out of the digital sequence detected matches the parity of the first
codeword.
7. The apparatus as recited in claim 6, further comprising a decoder for
decoding the codewords into a stream of datawords comprising a
predetermined j number of bits.
8. The apparatus as recited in claim 7, wherein j is 8 and k is 9.
9. The apparatus as recited in claim 7, wherein:
the input stream of pulse samples is divided into an even and odd
interleave; and
k is greater than j and
there are 2.sup.k sequence words comprising 2.sup.j codewords and 2.sup.k-j
errorwords, wherein the codewords decode into 2.sup.j datawords; and
the errorwords decode into datawords having corresponding codewords
different from the errorwords in two contiguous bit positions within
either interleave.
10. The apparatus as recited in claim 6, wherein:
the sequence detector comprises four path memories comprising n+k memory
elements each, wherein n is the number of bits of the second codeword
stored in the path memories; and
the path memories storing two survivor sequences of k bits different in
only one bit, wherein one of the survivor sequence storing the first
codeword; and
the path selector selecting the path memory storing the survivor sequence
comprising the first codeword.
11. The apparatus as recited in claim 10, wherein:
the path memories storing an even and odd interleave subsequence, the odd
interleave consisting only of odd bit positions and the even interleave
consisting of even bit positions; and
the at least one parity generator comprising a first and second parity
generator; and
the first parity generator responsive to the memory elements storing the
odd interleave of the two survivor sequences of k bits; and
the second parity generator responsive to the memory elements storing the
even interleave of the two survivor sequences of k bits; and
the at least one path selector comprising a first and second path selector;
and
the first path selector responsive to the first parity generator and for
selecting the path memory storing the odd interleave of the survivor
sequence comprising the first codeword; and
the second path selector responsive to the second parity generator and for
selecting the path memory storing the even interleave of the survivor
sequence comprising the first codeword.
12. The apparatus as recited in claim 6, wherein:
the input stream of pulse samples is divided into an even and odd
interleave; and
the first codeword comprising a first and second part wherein each part
comprising at least one bit; and
the sequence detectors comprise two sequence detectors, each sequence
detector comprising two path memories, each sequence detector processing
one of the interleaves; and
the two path memories of one of the sequence detectors storing a single
survivor sequence, the single survivor sequence storing the first part of
the first codeword; and
the two path memories of the other sequence detector storing two
corresponding survivor sequences, different in one pit, wherein one of the
two survivor sequences comprising the second part of the first codeword;
and
the path selectors selecting the path memory storing the survivor sequence
comprising the second part of the first codeword.
13. An apparatus for processing an input stream of pulse samples in a PRML
communication channel, comprising:
(a) a receiver connected to receive the input stream of pulse samples;
(b) at least one sequence detector, connected to receive the pulse samples,
for detecting a digital sequence of binary data from the pulse samples,
comprising a plurality of path memories, the path memories comprising a
plurality of memory elements, each memory element storing one bit of the
digital sequence;
(c) at least one parity generator for generating a parity signal having two
states, active and inactive, responsive to the number of "1" bits stored
in at least two of the memory elements of at least one of the path
memories of the sequence detector; and
(d) at least one path selector for selecting one of two of the path
memories out of the plurality of path memories of the sequence detector,
the path selector using the parity signal for selecting the path memory,
wherein:
the input stream of pulse samples is divided into an even and odd
interleave; and
the sequence detectors comprise two sequence detectors, each sequence
detector comprising two path memories, each sequence detector processing
one of the interleave.
14. The apparatus as recited in claim 13, wherein:
the sequence detectors are sliding threshold sequence detectors; and
the PRML communication channel is a PR4 communication channel.
15. A method for processing an input stream of pulse samples in a PRML
communication channel, comprising the steps of:
(a) receiving an input stream of pulse samples;
(b) detecting a digital sequence of binary data from the pulse samples
utilizing at least one sequence detector comprising a plurality of path
memories, the path memories comprising a plurality of memory elements,
each memory element storing one bit of the digital sequence;
(c) generating at least one parity signal having two states, active and
inactive, responsive to the number of "1" bits stored in at least two of
the memory elements of at least one of the path memories of the sequence
detector; and
(d) utilizing the part signal for selecting one of two of the path memories
out of the plurality of path memories of the sequence detector;
wherein:
the digital sequence comprising a plurality of codewords wherein each
codeword comprises a predetermined k number of bits;
the sequence detector storing a first codeword and at least part of a
second codeword in the plurality of path memories;
the at least one parity signal being generated from the memory elements of
the path memories storing at least part of the first codeword; and
the path memory is selected in step (d) such that the parity of k bits out
of the digital sequence detected matches the parity of the first codeword.
16. The method as recited in claim 15, further comprising the step of
decoding the codewords into a stream of datawords comprising a
predetermined j number of bits.
17. The method as recited in claim 16, wherein j is 8 and k is 9.
18. The method as recited in claim 16, wherein:
the input stream of pulse samples is divided into an even and odd
interleave; and
k is greater than j; and
there are 2.sup.k sequence words comprising 2.sup.j codewords and 2.sup.k-j
errorwords, wherein the codewords decode into 2.sup.j datawords; and
the errorwords decode into datawords having corresponding codewords
different from the errorwords in two contiguous bit positions within
either interleaved.
19. The method as recited in claim 15, wherein the sequence detector
comprises four path memories.
20. The method as recited in claim 15, wherein:
the sequence detector comprises four path memories comprising n+k memory
elements each, wherein n is the number of bits of the second codeword
stored in the path memories; and
the path memories storing two survivor sequences of k bits different in
only one bit, wherein one of the survivor sequence storing the first
codeword; and
the path memory selected in step (d) storing the survivor sequence
comprising the first codeword.
21. The apparatus as recited in claim 20, wherein:
the path memories storing an even and odd interleave subsequence, the odd
interleave consisting only of odd bit positions and the even interleave
consisting of eve bit positions; and
the at least one parity signal comprising a first and second parity signal;
and
the first parity signal responsive to the memory elements storing the odd
interleave of the two survivor sequences of k bits; and
the second parity signal responsive to the memory elements storing the even
interleave of the two survivor sequences of k bits; and
selecting the path memory in step (d) comprises the steps of:
utilizing the first parity signal for selecting the path memory storing the
odd interleave of the survivor sequence comprising the first codeword; and
utilizing the second parity signal for selecting the path memory storing
the even interleave of the survivor sequence comprising the first
codeword.
22. The method as recited in claim 15, wherein:
the input stream of pulse samples is divided into an even and odd
interleave; and
the sequence detectors comprise two sequence detectors, each sequence
detector comprising two path memories, each sequence detector processing
one of the interleaves.
23. The method as recited in claim 22, wherein:
the sequence detectors are sliding threshold sequence detectors; and
the PRML communication channel is a PR4 communication channel.
24. The method as recited in claim 15, wherein:
the input stream of pulse samples is divided into an even and odd
interleave; and
the first codeword comprising a first and second part wherein each part
comprising at least one bit; and
the sequence detectors comprise two sequence detectors, each sequence
detector comprising two path memories, each sequence detector processing
one of the interleaves; and
the two path memories of one of the sequence detectors storing a single
survivor sequence, the single survivor sequence storing the first part of
the first codeword; and
the two path memories of the other sequence detector storing two
corresponding survivor sequences, different in one pit, wherein one of the
two survivor sequences comprising the second part of the first codeword;
and
the path memory selected in step (d) storing the survivor sequence
comprising the second part of the first codeword. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
FIELD OF INVENTION
This invention related to computer technology and more specifically to
systems for storing and retrieving digitized data on magnetic storage
media.
CROSS REFERENCE TO RELATED APPLICATIONS AND PATENTS
This application is related to U.S. patent application Ser. No. 08/258,308
entitled, "Method and Apparatus for Encoding Data in a PRML Class-IV
Digital Communication Channel". The above-named patent application is
assigned to the same entity.
BACKGROUND OF THE INVENTION
The application of Partial Response Maximum Likelihood (herein after PRML)
techniques to digital communication channels is well documented. See Y.
Kabal and S. Pasupathy, "Partial Response Signaling", IEEE Trans. Commun.
Tech., Vol. COM-23, pp.921-934, Sep. 1975; Edward A. Lee and David G.
Messerschmitt, "Digital Communication", Kluwer Academic Publishers,
Boston, 1990; and G. D. Forney, Jr., "The Viterbi Algorithm", Proc. IEEE,
Vol. 61, pp. 268-278, Mar. 1973. Applying PRML techniques to magnetic
storage systems is also well documented. See Roy D. Cideciyan, Francois
Dolivo, Walter Hirt, and Wolfgang Schott, "A PRML System for Digital
Magnetic Recording", IEEE Journal on Selected Areas in Communications,
Vol. 10 No. 1, January 1992, pp.38-56; Wood et al, "Viterbi Detection of
Class IV Partial Response on a Magnetic Recording Channel", IEEE Trans.
Commun., Vol. Com-34, No. 5, pp. 454-461, May 1986; and Coker Et al,
"Implementation of PRML in a Rigid Disk Drive", IEEE Trans. on Magnetics,
Vol. 27, No. 6, November 1991.
In magnetic storage systems, a transducing head writes digital data onto
the surface of a magnetic storage medium, such as a magnetic disk. The
digital data serves to modulate the current in the head coil in writing a
sequence of corresponding magnetic flux transitions which represent the
digital data. When reading the recorded data, the head again passes over
the magnetic medium and transduces the magnetic transitions into pulses in
an analog read signal, which are then decoded by read channel circuitry to
reproduce the digital sequence.
Decoding the pulses into a digital sequence can be performed by a simple
pulse detector read channel or, as in more recent designs, by a partial
response maximum likelihood (PRML) read channel. The PRML read channel
scheme is preferred over the simpler pulse detection scheme because it
decreases the necessary bandwidth, thereby allowing more data to be stored
on the storage medium.
In conventional peak detection as well as PRML schemes, a channel code
provides clocking and automatic gain control (AGC) information. To perform
the timing and gain control, the number of consecutive zero samples must
be limited since timing and in control information is derived only when
non-zero samples are read from the channel. Typically, an RLL code having
a (d,k) constraint, which specifies the minimum and maximum run lengths of
zeros respectively, encodes the data before recording it to the storage
medium. For instance, a byte oriented (d=0,k=4) 8/9 encodes binary data
represented as 8 bit data bytes into 9 bit codewords in order to achieve
the desired (d,k) constraint. Because the PRML technique utilizes
inter-symbol interference (ISI) in a controlled manner, the d constraint
in Partial Response class-IV channels is unnecessary (d=0). However the k
constraint is still necessary in class-IV systems to provide the timing
and control information.
The sampled data in Partial Response (PR) channels is typically converted
into digital sequence using Maximum Likelihood (ML) detection techniques
(thus PRML). A Viterbi sequence detector normally implements the maximum
likelihood Viterbi algorithm for detecting the digital sequence from the
sampled data. See G. D. Forney, Jr., "The Viterbi Algorithm", Proc. IEEE,
Vol. 61, pp. 268-278, Mar. 1973.
Prior art implementations of encoders and Viterbi sequence detectors in
Partial Response class-IV channels introduced an additional constraint on
the number of consecutive zeros in each of the even an odd interleaves of
the encoded data in order to minimize the path memory of the detector.
Thus the conventional modulation codes for PR class-IV systems utilizing
Viterbi detection are characterized by (d,k/k1) where k1 represents the
maximum run length of zeroes in both the even and odd subsequences. A
small value of k is desirable for accurate timing and gain control, and a
small value of k1 reduces the size of the path memory in the Viterbi
detector. A method for encoding the channel data according to the (d,k/k1)
constraints is described in U.S. Pat. No. 4,707,681, the disclosure of
which is herein incorporated by reference.
FIG. 3 shows an example trellis diagram for the 1-D.sup.2 PR class-IV
channel and the affect the k1 constraint has on the path memory length of
the Viterbi detector. As shown in the diagram, the path memories merge
into one survivor sequence only after a "1" has been detected in both the
even 40 and odd 42 interleaves. Therefore, in prior art implementations
the length of the Viterbi detector path memories must be greater than
2(k1+1)+1 to guarantee that the paths merge into the correct sequence 34.
A further problem with the prior art implementations is that a minimum
delay of 2(k1+1)+1 samples is required before the paths merge and the
correct sequence is available. This latency degrades the performance of
the storage systems; for instance, it increases the delay between reading
the ID field and writing data to the disk. The latency also degrades the
performance of other read channel components that use the output of the
sequence detector, such as servo control.
Another problem with the prior art is the inability to correct errors in
the data samples due to noise. For instance, if noise in the system causes
a "1" to be erased, the path memories of the Viterbi detector may not be
merged after 2(k1+1)+1 samples and the detected sequence may not be
correct.
It is a general object of the present invention to provide a method and
apparatus for processing data in a PR class-IV communication channel that
does not require the conventional, k1 constraint, thereby minimizing the
path memory and latency of the Viterbi detector. Another object of the
invention is to correct errors in the detected sequence when a "1" is
erased due to noise in the system.
SUMMARY OF THE INVENTION
The objects of the present invention are achieved by a novel method and
apparatus for encoding, detecting and decoding data in a PR class-IV
magnetic recording channel. The data is encoded using run length limited
(RLL) (d,k) coding, without the conventional k1 constraint (i.e., there is
no interleave constraint on the maximum number of consecutive zeros).
There are two preferred embodiments of the present invention; the first
embodiment uses minimum path memory and minimizes the latency of the
Viterbi detector but does not correct for errors due to noise, and the
second embodiment corrects for errors but uses more path memory and has
more latency.
In the minimum latency embodiment, the codewords are divided into three
sets. The first set contains codewords having at least one "1" bit in both
the even and odd interleave within a predetermined first N number of bits.
The second set contains codewords having at least one "1" bit in the even
interleave and zero "1" bits in the odd interleave within the first N
number of bits. The third set contains codewords having at least one "1"
bit in the odd interleave and zero "1" bits in the even interleave within
the first N number of bits.
The path memories of the minimum latency embodiment are N+n long where n is
the num her of bits in a codeword (e.g., 9 in a 8/9 code). Thus the path
memories are long enough to store N bits out of a current codeword, and n
(i.e. all) bits of the previous codeword. Because the codewords in the
first set contain a "1" in both interleaves within the first N bits, the
path memories prior to the two "1" bits are guaranteed to have merged.
That is, the codeword detected previous to the N bits of the current
codeword is guaranteed to be available in the merged part of the path
memories as shown in FIG. 5a.
The codewords in the second set, having at least one "1" bit in the even
interleave within the first N bits of the codeword, guarantees that the
path memories storing the even interleave of the previous codeword will be
the same and the odd interleave will be different in only one bit as shown
in FIG. 5b. Similarly, the codewords in the third set, having at least one
"1" bit in the odd interleave within the first N bits of the codeword,
guarantees that the path memories storing the odd interleave of the
previous codeword will be the same and the even interleave will be
different in only one bit as shown in FIG. 5c.
Since the path memories storing the previous codeword are different in only
one bit when followed by a codeword from either the second or third set,
the correct path can be selected by knowing the parity of the previous
codeword as determined by which set the following codeword belongs. For
instance, if codewords from the second set always follow codewords with
even parity, and codewords from the third set always follow codewords wit
odd parity, the correct sequence for the previous codeword can be
determined by choosing the path with the correct parity. The encoding
method and apparatus of the present invention ensures that codewords with
an even or odd parity are followed by codewords from the correct set.
By encoding the data according to the present invention, the correct
sequence for the previous codeword can be determined before the path
memories merge, thereby minimizing the latency of the Viterbi detector.
Compared to the prior art implementations having a latency of 2(k1+1)+1
bits, the latency of the present invention is N bits. Thus if K1=4 and
N=3, the latency of the present invention is approximately four times less
than the prior art.
In the error correcting embodiment of the present invention, the path
memories are long enough to store M+n bits, where M is greater than N in
the first embodiment. The codewords are again divide into three sets. The
first set has an additional property of at least two "1" bits in both the
even and odd interleaves within a predetermined first M bits of the
codeword. The second and third set have an additional property of at least
one "1" bit in one of the interleaves and less than two "1" bits in the
other interleave within the first M bits of the codeword.
If the codeword out of the second or third set has only one "1" bit in
either interleave within the M bits, and that "1" bit is erased, the path
memories storing the previous codeword will not have merged. However,
since the parity of the previous codeword is known, the correct path can
still be chosen and the errors caused by choosing the wrong path in the
prior art implementations avoided.
Two example codes corresponding to the two embodiments are disclosed to
illustrate the encoding technique of the present invention. Both are 8/9
rate (0,4) codes meaning that each eight source bits encoded into nine
channel bits such that no more than four consecutive "0"s occur in the
encoded data. There is no k1 constraint, that is, there is no constraint
on the maximum number of consecutive "0"s in either interleave.
The two example codes are not meant to limit the invention. Codes having
rates other than 8/9 and constraints other than (0,4) could be used
without departing from the scope and spirit of the invention.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of the recording system including an encoder, a
pre-coder, a 1-D.sup.2 Partial Response class-IV channel, a Viterbi
detector and a decoder.
FIG. 2 shows a state diagram for a 1-D.sup.2 Partial Response Class-IV
channel and the corresponding survivor sequence extension from each state
for the trellis diagram.
FIG. 3 is an example trellis diagram for a 1-D.sup.2 Partial Response
Class-IV channel as related to the prior art k1 constraint.
FIG. 4 is a block diagram of the encoder of the present invention.
FIG. 5a, 5b, and 5c show example trellis diagrams for a 1-D.sup.2 Partial
Response Class-IV channel storing a first and second codeword of the
present invention.
FIG. 6a, 6b, and 6c show example trellis diagrams for a pair of 1-D
channels processing the even and odd interleaves of the 1-D.sup.2 Partial
Response Class-IV channel storing a first and second codeword of the
present invention.
FIG. 7a and 7b show example trellis diagrams for a 1-D.sup.2 Partial
Response Class-IV channel storing a first and second codeword of the
present invention where a "1" bit has been erased from the second codeword
due to noise.
FIG. 8a, 8b and 8c show example trellis diagrams for a 1-D.sup.2 Partial
Response Class-IV channel storing a first and second codeword of the
present invention where a look-ahead signal is generated from the path
memories storing the first bit of the second codeword.
FIG. 8d is a block diagram of the detector/decoder of the present invention
where the detector is implemented using a pair of two state 1-D sliding
threshold Viterbi detectors.
FIG. 9a and 9b show a detailed diagram of the two state 1-D sliding
threshold Viterbi detector for the minimum latency embodiment of the
present invention.
FIG. 10 shows the implementation of the multiplexor for selecting the
output of the two state 1-D sliding threshold Viterbi detectors.
FIG. 11a and 11b show a detailed diagram of the two state 1-D sliding
threshold Viterbi detector for the error correcting embodiment of the
present invention.
FIG. 12 shows a block diagram of the four state 1-D.sup.2 Viterbi detector
for an alternative embodiment of the present invention.
DETAILED DESCRIPTION OF THE PRESENT INVENTION
Partial Response class-IV magnetic recording channels are characterized by
a 1-D.sup.2 polynomial which exhibits spectral nulls at dc and at the
Nyquist frequency. The output of the channel is thus a function of the
current input and the input at n-2:
y(n)=x(n)-x(n-2).
With the binary input data modulating the write current such that a "1" bit
generates current in a positive direction (+1) and a "0" bit in the
negative direction (-1), the output samples of the channel y(n) take on
the values 2,0,-2, hereinafter normalized to 1 0,-1.
Referring now to FIG. 1, the 8-bit data words are encoded into 9-bit
codewords using the encoder 3 of the present invention. In order to
prevent error propogation and to retain the global k constraint for timing
and gain control, the output of the encoder 20 is pre-coded by a
1/1-D.sup.2 polynomial 2 before writing the codewords to the channel 6.
This pre-coding is taken into account in the Viterbi detector 4 when the
sampled data is read from the recording channel 6. The detector 4 detects
the digital sequence for the codewords and the codewords are decoded 5
back into 8-bit data words.
The binary input 16 the channel 6 and normalized output 18 can be depicted
by a state diagram 8 as shown in FIG. 2. In the diagram a state 12
represents the previous two output bits 16 from the pre-coder 2. A
transition is depicted by the current encoder output 20 and the
corresponding pre-coder output 16 and channel output 18.
The operation of the Viterbi sequence detector can be further understood
from a trellis diagram. As shown in FIG. 2, each state of the state
diagram 8 corresponds to a state in the trellis diagram 10. Each path 22
from one state to the next represents one bit 16 of a survivor sequence
for a detected codeword given the current sample value 18 read from the
1-D.sup.2 channel 6. A survivor sequence is a possible correct recorded
sequence given several samples read from the channel.
For example, a non-zero sample read from the channel is caused either by a
"1" in the recorded sequence or a "0" in the recorded sequence and noise
in the channel. Thus two survivor sequences are saved, one with a "1" and
the other with a "0". The correct sequence is determined from future
samples read from the channel; that is, the correct sequence is determined
by choosing the sequence with the maximum likelihood of being correct
given future samples read from the channel. The maximum likelihood
sequence is the sequence that minimizes the mean squared error between the
sample value read from the channel and the sample value expected. For
instance, if a sample value read from the channel is +0.8, then the
squared sample error value for a "0" in the sequence is (0-(+0.8)).sup.2,
and the squared sample error value for a "1" in the sequence is
(+1-(+0.8).sup.2.
A sum of the mean squared errors is stored for each survivor sequence, and
the sequence with the least mean squared error has the highest probability
of being correct. After a "1" in each interleave of the recorded sequence
has been processed by the Viterbi detector, there is only one survivor
sequence with a minimum mean squared error up to the first "1", and the
paths storing the other survivor sequences will have merged into this
maximum likelihood path.
At any given time there can be up to four survivor sequences; there are
four path memories in the Viterbi detector. To aid in understanding the
invention, each of the four path memories is represented by a
corresponding state in the trellis diagram.
Referring now to FIG. 3, shown is a trellis diagram for a particular
recorded sequence 36 (i.e., an encoded sequence) and corresponding sample
sequence 38 read from the 1-D.sup.2 channel 6. The sequence is labeled as
odd 30 and even 32 interleaves, and each interleave has a constraint of
k1=4; that is, the encoding scheme uses the prior art technique. As shown
in the diagram, the path memories do not merge into a single survivor
sequence 34 until a "1" bit 40 in the even interleave and a "1" bit 42 in
the odd interleave have been detected. Therefore the length of the path
memories must be at least 2(k1+1)+1 or 2(4+1)+1=11 bits long, and the next
bit in the correct sequence available until 11 samples have been read from
the channel. Before a complete codeword is available, there is a latency
of 2(k1+1)+1+n, where n is the number of bits in a codeword (e.g., 9 in a
8/9 code). This latency is undesirable as previously described. Further,
if the "1" bit 42 in the odd interleave is erased, the path memories will
not have merged after 2(k1+1) bits and the survivor sequence selected for
the codeword may not be correct.
ENCODER
A block diagram of the encoder 3 of the present invention is shown in FIG.
4. Eight bits 48 of source data are encoded 50 into nine bit codewords 20
using the parity 54 (modulo-2 sum) of the previous codeword. The encoding
scheme is unique to the present invention and is hereinafter described.
The minimum latency encoding scheme of the present invention, which has the
k constraint but not the k1 constraint, can be understood from the trellis
diagrams shown in FIGS. 5a, 5b and 5c. In these figures, an 8/9 code is
implemented and the trellis diagram stores 9 bits 60 of a first codeword
and 2 bits 62 from a second codeword that follows the first.
As shown in FIG. 5a, if the 2 bits 62 from the second codeword are {1,1},
then the path memories storing the first codeword will have merged into a
single survivor sequence 60 because there is a "1" bit in both the even
and odd interleave. That is, the parity of the first codeword is not
necessary to select the correct path memory because all the path memories
are the same If the 2 bits 62 from the second codeword are {0,1} or {1,0},
then the path memories will store two survivor sequences different by only
one bit.
For instance, FIG. 5b shows the case where the 2 bits 62 from the second
codeword are {0,1} wherein the two resulting survivor sequences for the
first codeword are {1,1,0,0,0,0,0,0,0} 64 and {1,0,0,0,0,0,0,0,0} 66.
Since the two sequence are different in only one bit, the correct sequence
can be selected using the parity of the first codeword. Thus if the parity
is even, the first survivor sequence 64 is selected, and if the parity is
odd, the second survivor sequence 66 is selected. FIG. 5c shows the same
result for the case where the 2 bits 62 from the second codeword are
{1,0}. The parity of the first codeword is determined during the encoding
process.
If the second data word encodes into a codeword out of a first group of
codewords wherein the first two bits are {1,1}, then the parity of the
first codeword is ignored since the path memories will have merged into
one survivor sequence. If the second data word does not encode into the
{1,1} group, then it is encoded into either the {0,1} or {1,0} group of
codewords depending on the parity of the first codeword. For instance, if
the first codeword has even parity, then the second codeword is selected
from the {0,1} group of codewords, and if the first codeword has odd
parity, then the second codeword is selected from the {1,0} group. When
the data is detected by the Viterbi detector, the path memory storing the
first codeword is selected based on its corresponding parity as determined
by the second codeword.
To this point, the invention has been described with respect to a 1-D.sup.2
four state Viterbi detector. However, the 1-D.sup.2 channel can be
factored into a pair of interleaved 1-D channels and detected using a pair
of two state Viterbi detectors. See Roy D. Cideciyan, Francois Dolivo,
Walter Hirt, and Wolfgang Schott, "A PRML System for Digital Magnetic
Recording", IEEE Journal on Selected Areas in Communications, Vol. 10 No
1, January 1992, pp.38-56. Using two interleaved sequence detectors
simplifies the detection algorithm, and the encoding technique of the
present invention is applicable to this interleaved detection scheme.
FIGS. 6a, 6b, and 6c show the two state trellis diagrams for the
interleaved detectors corresponding to the four state trellis diagrams in
FIGS. 5a, 5b, and 5c, respectively. In FIG. 6a there is a "1" in both
interleaves within the first two bits of the second codeword; the path
memories for both the even and odd interleave have merged into the correct
sequence for the first codeword. In FIG. 6b there is a "1" only in the odd
interleave within the first two bits of the second codeword; the even
interleave has not merged and contains two survivor sequences. FIG. 6c
shows a similar situation where the odd interleave has not merged into a
single survivor sequence.
As in the four state detector described above, the correct survivor
sequence for the first codeword is selected based on its parity as
determined by the second codeword. The even interleave will not be merged
only when followed by a codeword from the {1,0} group; the path memory of
the even interleave is selected such that the parity of the first codeword
is odd since codewords that precede the {1,0} codewords always have odd
parity. Similarly, the odd interleave will not be merged only when
preceded by a codeword from the {0,1} group; the path memory of the odd
interleave is selected such that the parity of the first codeword is even
since codewords that precede the {0,1} codewords always have even parity.
For the 8/9 code having a {0,4} constraint, there are not enough 9 bit
codewords in the groups of {1,1,X,X,X,X,X,X,X}, {0,1,X,X,X,X,X,X,X}, and
{1,0,X,X,X,X,X,X,X} to encode 256 data words; a third bit must be used.
The resulting groups of codewords and corresponding parity of the previous
codeword are shown in Table 1.
TABLE 1
______________________________________
GROUP1: {0,0,1,X,X,X,X,X,X}
odd parity
GR0UP2: {0,1,0,X,X,X,X,X,X}
odd parity
GR0UP3: {0,1,1,X,X,X,X,X,X}
don't care
GR0UP4: {1,0,0,X,X,X,X,X,X}
even parity
GR0UP5: {1,0,1,X,X,X,X,X,X}
even parity
GR0UP6: {1,1,0,X,X,X,X,X,X}
don't care
GR0UP7: {1,1,1,X,X,X,X,X,X}
don't care
______________________________________
Groups 3, 5, 6 and 7 have "1" bit in both the even and odd interleave
within the firs 3 bits and thus perform the same function as the {1,1}
group described above. The remaining groups are divided into those that
follow codewords with even and odd parity as follow; groups 1 and 2 always
follow codewords with odd parity, and groups 4 and 5 always follow
codewords with even parity. The mapping of data words to codewords is
arbitrary, and the assignment of even and odd parity may also be reversed.
An example mapping octal notation of data words to codewords is shown in
Table 2 and Table 3. Table 2 shows the mapping of data words into
codewords out of groups 3, 5, 6 and 7. Table 3 shows the mapping of data
words into codewords out of groups 1 and 2 if the parity of the previous
codeword is odd, and into codeword out of groups 4 and 5 if the parity of
the previous codeword is even.
TABLE 2
______________________________________
Data CW
______________________________________
000 362
001 342
002 312
003 352
004 662
005 642
006 612
007 652
010 332
011 322
012 311
013 313
014 341
| | |
