System and Scheme for Maximum Transition Run Length Codes With Location Dependent Constraints

The present invention relates to encoding systems. In particular, the present invention relates to encoding systems in disc drives.

In the field of digital communications, digital information is conveyed from a transmitter to a receiver through a channel. "Channel" is a generalized term that can include many things. For instance, in satellite communication systems, the channel consists of the atmosphere between the earth-bound transmitter and the satellite. In data storage devices, such as magnetic disc drives, the channel includes a storage medium where the signal is stored for some period of time before being delivered to the receiver.

All channels introduce noise into the signals they convey. To detect and sometimes to correct signal errors caused by this channel noise, the art has developed a large number of coding techniques. These coding techniques convert data words formed of a number of data bits, m, into larger code words formed of a number of code bits, n. The additional bits in the code words permit the detection and sometimes the correction of errors in the signals received from the channel.

The ratio of the number of data bits to the number of code bits, m/n, is known as the code rate of the code. In general, the ability to detect and correct errors in a received signal increases as the code rate decreases because a lower code rate means a greater number of additional bits in the code word. However, each additional bit added by the encoder increases the time and energy needed to transmit the signal through the channel. Thus, to minimize the time and energy needed to send the code, the code rate should be maximized. A lower code rate results in more bit crowding, which reduces error rate performance.

In one type of coding, known as non-return-to-zero-inverse (NRZI), every digital one in a code word is represented by a transition in the transmitted signal, and every digital zero is represented by a lack of transitions in the transmitted signal. To allow the receiver to generate a clock signal using a phase lock loop and the received signal, the encoded signal is generally limited so that the number of consecutive zeros is no greater than a maximum number "k". This kind of code is known as a run-length-limited (RLL) code with a "k" constraint. It is also known to limit the number of consecutive ones in an encoded value to limit the effects of inter-symbol interference, which occurs when consecutive transitions in the transmitted signal interfere with each other. Such codes are known as maximum transition run (MTR) codes with an "L" constraint, where L is the maximum number of consecutive transitions allowed in the channel signal. For example, to avoid three or more consecutive transitions, codes with an MTR constraint L=2 can be designed.

Although MTR codes reduce inter-symbol interference, they eliminate a large number of available code words making it difficult and sometimes impossible to implement MTR constraints with high rate codes. MTR codes improve the bit-error rate by eliminating the most error prone patterns, which in turn limits the code rate achievable with a given MTR constraint.

The present invention addresses this and other problems, and offers other advantages over the prior art.

A method and apparatus for encoding data produces a code stream of code words, where each code word includes two subsets of code bits. Each subset of code bits is constrained by a different maximum transition run constraint.

In an alternative embodiment, the method and apparatus produces a code stream comprised of alternating even bit locations and odd bit locations, where the even bit locations are constrained by a different maximum run length constraint than the odd bit locations. In preferred embodiments, even bit locations within the code stream have a maximum transition run constraint of three and odd bit locations within the code stream have a maximum transition run constraint of two.

In further embodiments of the present invention, the code stream is formed through a series of concatenated even and odd code words. Even code words within the code stream have maximum transition run constraints of two for the code words' odd bit locations and three for the code words' even bit locations. For odd code words, the maximum transition run constraints are two for the code words' even bit locations and three for the cod words' odd bit locations.

FIG. 1 is a plan view of a disc drive.

FIG. 2 is a block diagram of a coding system of the present invention.

FIG. 3 is an organizational layout of an encoded stream showing the numbering and naming convention used with the present invention.

FIG. 4 is a state diagram for the code of the present invention.

FIG. 1 is a plan view of a disc drive 100 that includes a housing with a base plate 102 and a top cover 104 (sections of top cover 104 are removed for clarity). Disc drive 100 further includes a disc pack 106, which is mounted on a spindle motor (not shown). Disc pack 106 can include a plurality of individual discs which are mounted for co-rotation about a central axis. Each disc surface has an associated head gimbal assembly (HGA) 112 which is mounted to disc drive 100 for communication with the disc surface. Each HGA 112 includes a gimbal and a slider, which carries one or more read and write heads. Each HGA 112 is supported by a suspension 118 which is in turn attached to a track accessing arm 120 known generally as a fixture, of an actuator assembly 122.

Actuator assembly 122 is rotated about a shaft 126 by a voice coil motor 124, which is controlled by servo control circuitry within internal circuit 128. HGA 112 travels in an arcuate path 130 between a disc inner diameter 132 and a disc outer diameter 134. When the head is properly positioned, write circuitry within internal circuitry 128 encodes data for storage on the disc and sends an encoded signal to the head in HGA 112, which writes the information to the disc. At other times, the read head in HGA 112 reads stored information from the disc and provide a recovered signal to detector circuitry and decoder circuitry within internal circuitry 128 to produce a recovered data signal.

FIG. 2 is a block diagram of a generalized communication system 148 used with the present invention. For the disc drive of FIG. 1, communication system 148 is formed by internal logic 128, head gimbal assembly 112 and disc 106. Within communication system 148, an encoder 150 receives data samples 152 and produces a even and odd code words 153. Even and odd code words 153 are provided to parallel-to-serial converter 155 in a parallel manner such that all of the bits of a respective code word are provided to converter 155 at the same time. Parallel-to-serial converter 155 converts each parallel code word of even and odd code words 153 into a serial representation and concatenates the serial representations to produce a sequence of even and odd bits 154. The sequence of even and odd bits 154 meets several constraints discussed further below. Transmitter/channel precoder 156 receives the sequence of even and odd bits 154 and conditions the sequence so that it is optimized for the type of detector used to recover the signal from the channel. Transmitter/channel precoder 156 produces write signal 158, which is provided to channel 160.

Channel 160, which is comprised of a write head, a disc, and a read head when the communication system is a disc drive, conveys the encoded information from transmitter/precoder 156 to receiver/detector 162 as a read signal 164. Receiver/detector 162 amplifies and filters read signal 164 and recovers an encoded signal from the read signal using one of several known detection methods. For instance, receiver/detector 162 may use a Viterbi detector, Decision Feedback Equalization (DFE), Fixed-Delay Tree Search with Decision Feedback (FDTS/DF) or Reduced State Sequence detection (RSSE). After detecting and amplifying the signal from channel 160, receiver/detector 162 produces a recovered sequence of even and odd bits 165, which are provided to serial-to-parallel converter 163. The sequence of even and odd bits 165 is in a serial format at the input to serial-to-parallel converter 163. Serial-to-parallel converter 163 groups the bits into code words and converts the code words from a serial format to a parallel format. Serial-to-parallel converter 163 then outputs even and odd code words 166 in a parallel format. The even and odd code words 166 are provided to decoder 168. Decoder 168 uses the inverse of the coding rules used by encoder 150 and converts the even and odd code words 166 into recovered data stream 170.

FIG. 3 shows an organizational layout for a code stream 178 of bits that is helpful in describing the numbering and naming system used in connection with the present invention. Code stream 178 is an example of the type of bit stream that can appear as the sequence of even and odd bits 154 or the sequence of even and odd bits 165 of FIG. 2.

In FIG. 3, the first bit in time is to the far left and later bits in time extend to the right. Above code stream 178 is number line 176, which assigns an integer to each bit in code stream 178 based on its overall location within the entire code stream. Under the present invention's numbering system, the first bit is numbered as bit zero, the second bit is bit one and so on. Above number line 176 is even/odd line 174, which provides an "E" designation for each even bit in code stream 178 and an "O" designation for each odd bit in code stream 178. The "E" and "O" designation is vertically aligned with its respective bit in code stream 178.

Above, even/odd line 174 is code-word-bit numbering line 177, which assigns an integer for each bit corresponding to the bit's location within a code word. In the embodiment of FIG. 3, each code word has 9 bit locations numbered 0 to 8. Above code-word-bit numbering line 177 is code word even/odd line 175, which provides an "E" designation for each even bit location in a code word and an "O" designation for each odd bit location in a code word.

Below code stream 178 is code-word count 180, which associates a number with each grouping of nine bits in code stream 178. Thus, the first nine bits form code word zero, the second nine bits form code word one, and the third nine bits form code word two. Vertically aligned with code-word count 180 is even/odd code word line 182 which provides an "E" designation for each even code word in code stream 178 and an "O" designation for each odd code word.

Code bits 184, 186, and 188 provide examples of the numbering and even/odd designations of the present invention. Code bit 184 is the fifth bit in code stream 178 and is assigned an overall numerical value of 4 in number line 176. Code bit 184 is also the fifth bit in the first code word, and thus is assigned a code-word-bit number of 4 in code-word-bit numbering line 177. Code bit 184 is designated as an even bit in both even/odd line 174 and code word even/odd line 175. Code bit 184 is part of the first code word 190, which is numbered code word zero in code word count 180 and which is designated as an even code word in even/odd code word line 182.

Bit 186 is the twentieth bit in code stream 178, has a numerical value of nineteen in the code stream and is considered an odd bit overall as shown in even/odd line 174. Although it is the twentieth bit overall, bit 186 is only the second bit in code word 194, and as such, has a code-word-bit number of 1 in code-word-bit numbering line 177. This means that it is an odd code bit within code word 194, as shown in code word even/odd line 175. Code word 194 has a numerical value of two and is considered an even code word.

Bit 188, which is the thirteenth bit in code stream 178 has an overall numerical value of twelve in numbering line 176 and is considered an even bit overall. Although bit 188 is the thirteenth bit overall, it is only the fourth bit in code word 192. As the fourth bit in code word 192, bit 188 has a code-word-bit number of 3 in code-word-bit numbering line 177, and is considered an odd bit within the code word. Thus, although bit 188 is an even bit overall, it is an odd bit within code word 192.

The code of the present invention provides a rate 8/9 code with location dependent maximum transition run constraints. In one embodiment of this code, transition runs beginning from odd bit locations within each code word are limited to two transitions (L.sub.1 =2) and transition runs starting from even bit locations are limited to three transitions (L.sub.2 =3).

With nine-bit code words using binary values for each bit, there are 2.sup.9 =512 possible code words. After applying the MTR constraints described above, there are 356 code words that can be used to encode 2.sup.8 =256 possible data words.

To ensure that invalid patterns do not occur when code words are concatenated, the 356 code words are mapped into a two-state system where an individual code word does not appear in more than one state but can appear twice within the same state. During encoding, the two-state coding system is in one of the two states, state S0 or state S1. Each data word has an associated code word and next state value in both state S0 and S1. The code word is the value produced by encoder 150 and the next state value determines what state the two-state system will be in when the next data word arrives. The assignment of code words to particular states and the movement between states is partially controlled by two state definitions. The first state definition is that all code words in state S1 begin with `0`. Because of this state definition, any code word may precede state S1 because the concatenation of any code word with a code word that begins with `0` will not violate the MTR constraint. The second state definition restricts code words that precede state S0 to those that end with `0`. Under this definition, any code word ending with a `0` may be used before state S0.

Using these state definitions, the mapping for an 8/9 rate MTR code with local L.sub.1 =2 and L.sub.2 =3 constraints can be derived. Such a mapping is shown in Table 1 below, where the nine-bit code words are represented by two hexadecimal values in the two right most locations and a single binary value in the left most location. The eight bit data words are represented by two hexadecimal values.

Because a single code word can occur twice within a given state for two different data words, the decoder must determine the state of the next code word to decode the present code word. For example, if code word "120" is received, and the decoder is in state S0, the code word represent either data word "50" or data word "70". The decoder must determine which state the next code word belongs to before it can determine what data word the code word "120" represents. If the next code word is from state S0, "70" will be the decoded output, otherwise "50" will be the decoded output.

In order for a detector to identify code words that violate the MTR constraint and thus contain an error, the detector must keep track of whether it has an odd numbered code word or an even numbered code word. Since there are nine bits in each code words, if the decoder did not keep track of even and odd code words but merely kept track of whether it had an even or odd bit overall, the tenth received bit would considered an odd bit overall. However, since the tenth received bit is the first bit of the second code word, it is an even bit within that code word. Therefore, in order to properly track even and odd locations within code words, the detector must be complex enough to keep track of even and odd code words in addition to keeping track of even and odd bits within code words.

To reduce this complexity, the present invention provides an alternate rate 8/9 code word mapping. In this alternate mapping, even code words are constrained in the same manner as described above such that transition runs beginning from odd bit locations are limited to two transitions (L.sub.1 =2) and transition runs beginning from even bit locations are limited to three transitions (L.sub.2 =3). However, odd code words under this alternate mapping have different localized MTR constraints. Specifically, for odd code words, transition runs beginning from odd bit locations are limited to three transitions (L.sub.1 =3) and transition runs beginning from even bit locations are limited to two transitions (L.sub.2 =2). By interleaving code words that use these two different sets of constraints, an MTR code is formed that provides universal MTR constraints of two for odd bit locations and three for even bit locations counting from the beginning of the code stream. Thus, the decoder does not have to keep track of whether the current code word is in an even temporal location or an odd temporal location. It only has to keep track of the overall temporal location of the bits.

Of the possible 512 nine-bit code words, 317 meet the L.sub.1 =3 and L.sub.2 =2 MTR constraint. To ensure proper concatenation, the 317 code words that meet this constraint and the 356 code words that meet the L.sub.1 =2 and L.sub.2 =3 MTR constraint are divided into four states each, forming a total of eight states. The four states for the code words having an MTR constraint of three for even code words (L.sub.2 =3) and two for odd code words (L.sub.1 =2) are denoted as states S0, S2, S4 and S6. The four states for the code words satisfying the MTR constraint of three for odd positions (L.sub.1 =3) and two for even positions (L.sub.2 =2) are denoted as states S1, S2, S5 and S7.

The four states for one group of code words shares common state definitions with the four states for the other group of code words. Code words in states S0 or S1 can begin with any two bits including "11" so code words preceding state S0 or state S1 must end with "0". The code words in state S2 or state S3 may only begin with "10" so code words preceding state S2 or state S3 must end with "00" or "01". Code words in states S4, S5, S6, and S7 only begin with "0" so any code word may proceed these states.

Given these state definitions, the 356 code words that satisfy the MTR constraint of three for temporally even bit positions and two for temporally odd bit positions are divided between states S0, S2, S4, and S6. Similarly, the 317 code words that satisfy the MTR constraint of three for temporally odd bit positions and two for temporally even bit positions are divided between states S1, S3, S5, and S7. Note that many code words satisfy both constraints and thus are found in more than one state. However, code words found in even numbered states such as S0, S2, S4, or S6 are not found in another even numbered state. Similarly, a single code word does not appear in two different odd numbered states (S1, S3, S5, or S7). The code words found in an even numbered state, however, can be found in an odd numbered state. In addition, code words may be repeated within a state.

To realize the universal MTR constraint of two for odd bit positions and three for even bit positions over the entire encoded signal, the next state for any even numbered state, states S0, S2, S4 or S6, must be an odd numbered state, states S1, S3, S5, or S7. Similarly, the next state for any odd numbered state, must be an even numbered state.

An encoding/decoding table for a code based on these eight states is shown in Table 2 below. In Table 2, "NS" in the headers indicates the next state for the encoder/decoder. The code words of these tables are described in a modified hexadecimal format where the two right-most character locations are described by hexadecimal characters and the left-most character location is described by a binary value.

In designing encoding/decoding Tables 1 and 2, undesirable patterns or long-run patterns with small Euclidean distances are avoided. For example, patterns of repeating tribits, "11101110 . . . " are eliminated. In addition, patterns with long runs of "11001100 . . . " are eliminated as these patterns may force the detector to keep a long memory length. Thus, not all of the 317 possible code words that meet the MTR constraint of two for even bit locations and three for odd bit locations appear in the tables and not all of the 356 code words that satisfy the MTR constraint of three for even bit locations and two for odd bit locations appear in the tables.

FIG. 4 shows a state diagram for the present invention's universal MTR code of three for even bit locations and two for odd bit locations. State 200 represents the initial state of the encoder/decoder, which is an even bit location. If the bit associated with state 200 is `0`, the code moves to state 201, which is an odd bit location. If the bit associated with state 201 is `0`, the code returns to state 200. If the associated bit is `1`, the code advances to state 202.

State 202 is associated with an even bit location and if that bit location contains a `0`, the code returns to state 201. If the bit location contains a `1`, the code moves to state 203, which is associated with an odd bit location. Since state 203 only occurs after two consecutive ones beginning from an odd bit location, the bit associated with state 203 must be `0`, causing the code to return to state 200.

If the bit associated with state 200 is `1`, the code goes to state 205, which is associated with an odd bit location. If the value of the bit associated with state 205 is `0`, the code returns to state 200. If the value of the bit associated with state 205 is `1`, the code moves to state 206, which is associated with an even location. A `0` in the even bit location of state 206 moves the code to state 201. A `1` in the even bit location associated with state 206 moves the code to state 207. Since state 207 is associated with three consecutive ones beginning from an even bit location, the MTR constraint of three for even bit locations requires that the bit associated with the odd location of state 207 be `0` and the code returns to state 200.

In summary, the present invention provides a method and apparatus for producing a code stream 158. The coding system includes an encoder 150 capable of converting data values 152 into a series of code symbols 154 in alternating even 188 and odd 186 locations, such that fewer than a first maximum transition run limit of consecutive same first code symbols start from any even bit location 188 and fewer than a second number of consecutive same first symbols start from any odd bit location 186. The coding system further includes a transmitter 156 coupled to encoder 150 and to channel 160 and capable of transmitting an encoded signal based on the series of code symbols 154.

It is to be understood that even though numerous characteristics and advantages of various embodiments of the present invention have been set forth in the foregoing description, together with details of the structure and function of various embodiments of the invention, this disclosure is illustrative only, and changes may be made in detail, especially in matters of structure and arrangement of parts within the principles of the present invention to the full extent indicated by the broad general meaning of the terms in which the appended claims are expressed. For example, the particular elements may vary depending on the particular application for the coding method and apparatus while maintaining substantially the same functionality without departing from the scope and spirit of the present invention. In addition, although the preferred embodiment described herein is directed to a coding system for a disc drive, it will be appreciated by those skilled in the art that the teachings of the present invention can be applied to other systems, like satellite communications or cellular phone systems, without departing from the scope and spirit of the present invention.