Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-03-09
2003-06-03
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C341S059000
Reexamination Certificate
active
06574773
ABSTRACT:
FIELD OF INVENTION
The present invention relates to data transmission in communication systems, such as the recording and reproduction of binary data in disk storage systems for digital computers, particularly to a cost-effective, high-throughput enumerative encoder/decoder (ENDEC) for encoding/decoding a data stream using a plurality of segmented compare tables representing the full compare table of an enumerative trellis.
MICROFICHE APPENDIX
This application includes a microfiche appendix of 1 microfiche comprising 50 frames.
BACKGROUND OF THE INVENTION
Communication systems generally employ a channel code in order to increase the effective signal-to-noise ratio (SNR), thereby increasing the transmission speed while maintaining some arbitrarily low bit error rate. As illustrated in
FIG. 1
, an encoder
2
encodes an input data stream
4
into an encoded data stream
6
which is then transmitted through a communication channel
8
(e.g,. recorded to a disk). At the receiving end, a decoder
10
decodes the received data stream
12
into decoded output data
14
, wherein noise in the communication channel
8
may induce errors in the decoded output data
14
. Encoding the input data stream
4
before transmission decreases the bit error rate by increasing noise immunity (increasing the effective SNR). In magnetic disk storage systems, for example, a run-length limited (RLL) channel code is typically employed to limit the spacing between consecutive medium transitions as well as to constrain the maximum spacing between consecutive medium transitions (i.e., constrain the minimum and maximum number of “0” bits between “1” bits in NRZI recording). The first constraint (the “d” constraint) increases the effective SNR by attenuating intersymbol interference (ISI). The second constraint (the “k” constraint) increases the effective SNR by increasing the accuracy of the phase error estimate in the timing recovery phase-locked loop. Other constraints may also be implemented by the channel code; for example, a maximum transition run-length (MTR) limits the maximum number of consecutive medium transitions which increases the effective SNR by “coding out” certain dominant error events from a trellis sequence detector.
Encoding the input data stream to satisfy a given set of code constraints requires that a certain number of redundancy bits be added to the transmitted (recorded) data stream. The redundancy bits decrease the transmission rate (storage density) by increasing the total number of bits which must be transmitted for every uncoded bit. This is generally referred to as the “code rate” and is denoted by the ratio m
where m represents the number of unencoded bits and n represents the number of encoded bits. Employing a channel code allows for an increase in the transmission rate (storage capacity) only if the code rate is sufficiently large; however, maximizing the code rate often means increasing the cost and complexity of the ENDEC circuitry. Thus, significant effort is spent on designing channel codes which exhibit a high code rate while minimizing the cost and complexity of the ENDEC circuitry.
One known method for implementing a channel ENDEC which provides relatively high code rates with nominal cost and complexity is a technique referred to as “enumerative coding”. This technique is described in detail by M. Mansuripur in “Enumerative Modulation Coding with Arbitrary Constraints and Post-Modulation Error Correction Coding for Data Storage Systems,”
SPIE
, vol. 1499, Optical Data Storage, 1991, pp. 72-86, the disclosure of which is incorporated herein by reference.
Enumerative codes are essentially block codes wherein an m-bit input block or dataword is encoded into an n-bit output block or codeword. The m-bit input block is viewed as an integer which is processed through an enumerative trellis. Each state in the enumerative trellis is assigned a value representing the number of unique paths through the enumerative trellis starting from that state. The enumerative trellis is derived from a state transition diagram which defines the channel code in terms of the code constraints.
As an example, consider the state transition diagram shown in
FIG. 2A
which implements a “Quadbit mod 2” constraint. The “Quadbit mod 2” constraint enhances the operation of a trellis sequence detector by allowing four consecutive medium transitions to occur only if started on every other sample interval, as well as coding out sequences comprising more than four consecutive medium transitions. From the state transition diagram shown in
FIG. 2A
an enumerative trellis can be constructed for a rate 17/18 channel code as shown in FIG.
2
B. The 17/18 enumerative trellis has five states (S
0
through S
8
) wherein state S
2
has been selected as both the starting state and the ending state.
During the encoding process, at each state in the enumerative trellis an input value is compared to the state value and an output bit is generated (0 or 1) for the 18-bit output codeword, the bits for which are labeled along the top of the enumerative trellis in FIG.
2
B. For example, if the input value is less than the state value a “0” bit is generated and the input value is not modified, otherwise a “1” bit is generated and the input value is updated by subtracting the state value. The selected branch leads to the next state, wherein another comparison is made and another output bit generated. This process continues until the last state of the enumerative trellis has been reached wherein all 18 bits of the output codeword will have been generated.
The encoding operation with respect to the enumerative trellis of
FIG. 2B
is further understood by considering the 17-bit input dataword (10000101110011010) which has an integer value of 68506. This is the initial input value compared with the starting state value of 70632 at S
2
; since 68506 is less than 70632, a “0” bit is generated for bit
18
by following the dashed-line branch to state S
0
(the input value is not modified). Next, the input value of 68506 is compared to the current state value 35316 at S
0
; since 68506 is greater than 35316, a “1” bit is generated for bit
17
by following the solid-line branch to state S
2
, and the input value 68506 is modified by subtracting the state value 35316 to generate a next input value of 33190. The new input value 33190 is compared to the state value 18630 at S
2
; since 33190 is greater than 18630, a “1” bit is generated for bit
16
by following the solid-line branch to state S
4
, and the input value 33190 is modified by subtracting the state value 18630 to generate a next input value of 14560. This process continues until all 18 output bits have been generated and the last state in the enumerative trellis has been reached. For the representative 17-bit input dataword (10000101110011010) the 18-bit output codeword generated by the enumerative trellis of
FIG. 2B
is (011110000111100001).
Certain of the states in an enumerative trellis may have only one output branch in which case the encoder is forced to output a “0” or “1” bit. For example, state S
8
in the trellis of
FIG. 2B
has only one output branch, a dashed-line branch for outputting a “0” bit. When this state is reached, the encoder is forced to output a “0” bit by following the dashed-line branch to state S
2
and the input value is not modified.
When a codeword is received (read from the disk), it is decoded using the same enumerative trellis as that used for encoding. The decoding process is essentially the inverse of the encoding process; that is, an integer representing the decoded dataword is constructed by traversing the trellis in response to the bits in the received codeword starting with the same bit as with the encoding process (the most significant bit). The integer is initialized to zero, and then starting with the first state in the enumerative trellis, the state value is added to the integer if the received bit is a “1” bit, otherwise the integer is not modified. The branch corresponding to the received “0” or “1” bit is followed in t
Turk Stephen A.
Zook Christopher P.
LandOfFree
Cost-effective high-throughput enumerative ENDEC employing a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cost-effective high-throughput enumerative ENDEC employing a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cost-effective high-throughput enumerative ENDEC employing a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3098612