Encoding and decoding techniques for data in 24 bit sequence

[0003] This application claims priority benefits from U.S. provisional patent application 60/100,264 entitled RATE 24/25 (0,7/7) RUN LENGTH LIMITED CODE WITH MINIMUM HAMMING WEIGHT CONSTRAINT filed on Sep. 14, 1998.

[0004] The present invention relates to communicating digital data through a communication channel. More particularly, the present invention relates to encoding and decoding techniques for data in 24 bit sequences.

[0005] In the field of digital communications, digital information is typically prepared for transmission through a channel by encoding it. The encoded data is then used to modulate a transmission to the channel. A transmission received from the channel is then typically demodulated and decoded to recover the original information.

[0006] The encoding of the digital data serves to improve communication performance so that the transmitted signals are less corrupted by noise, fading, or other interference associated with the channel. The term “channel” can include media such as transmission lines, wireless communication and information storage devices such as magnetic disc drives. In the case of information storage devices, the signal is stored in the channel for a period of time before it is accessed or received. Encoding can reduce the probability of noise being introduced into a recovered digital signal when the encoding is adapted to the known characteristics of the data and its interaction with known noise characteristics of a communication channel.

[0007] In typical encoding arrangement, data words of m data bits are encoded into larger code words of n code bits, and the ratio m/n is known as the code rate of the encoding arrangement. Decreasing the code rate improves decoding and can also improve error correction, however, decreased code rate also increases energy consumption and slows communication.

[0008] Encoding for magnetic media also typically includes non-return-to-zero-invert-on-ls (NRZI) coding and resynchronization of the received signal using a phase locked loop (PLL). In order to ensure adequate synchronization of the PLL, a run length limit (RLL) of the number “k” of consecutive zeros is an integral part of the encoding. In systems where two interleaved subsequences are encoded to produce two smaller code words for detection by a Viterbi detector, the maximum run length or number “i” of zeros in each of the bitwise interleaved sub-sequence is also limited to reduce delay in the Viterbi detector. The number “w” of ones in a code word affects energy consumption and is known as a Hamming weight. These constraints improve performance, but also tend to eliminate a large number of available code words, which can tend to require a lower code rate. Finding an efficient set of constraints “k”, “i”, and “w” within a suitable code rate is complex for long digital words.

[0009] In particular, it is found that transmission of relatively long digital words representing 24 bits of information through a channel that introduces channel noise in the form of irregular timing of received bits and unpredictable short bursts of bit errors is a problem. This problem is present in magnetic disc drives and can be present in other types of channels as well.

[0010] The present invention relates to systems and methods for communicating digital data through a communication channel that improve transmission and solves the above mentioned synchronization and decoding problems.

[0011] An encoding system receives 24 bits of information as first and second 12 bit sequences of the data. The encoding system includes a first encoder that generates an 11 bit first codeword and state variables as a function of the first sequence. A second encoder generates a 14 bit second codeword as a function of the second sequence and the state variables. The state variables are represented by four or fewer bits in the second codeword. The first and second codeword together form a 25 bit codeword that coupled to the communication channel.

[0012] A decoder system then receives the 25 bit codeword from the communication channel and separates the 25 bit codeword into a 14 bit codeword and an 11 bit codeword. A first decoder receives the 14 bit codeword and generates a first decoded 12 bit sequence. The first decoder also generates decoded state variables as a function of four or fewer bits of the 14 bit codeword. A second decoder receives the 11 bit second portion and the state variables and generates a second 12 bit decoded sequence, the first and second decoded sequence together forming a decoded 24 bit sequence of data.

[0013] The first and second codewords together form a 25 bit codeword. The encoder limits runs of zeros by encoding the 25 bit codeword with a run length limit K=7.

[0014] In a preferred embodiment, the encoding and decoding systems and methods are used in a magnetic disc drive.

[0015] FIG. 1 is a perspective view of an embodiment of a magnetic disc drive in which the present invention can be used.

[0016] FIG. 2 is a block diagram of embodiments of encoding and decoding systems for communicating data according to the present invention.

[0017] FIG. 3 is a flow chart of a method of encoding data.

[0018] FIG. 4 is a flow chart of a method of decoding data.

[0019] FIG. 1 is a perspective view of a magnetic disc drive 100 in which the present invention is useful. Disc drive 100 includes a housing with a base 102 and a top cover (not shown). Disc drive 100 further includes a disc pack 106, which is mounted on a spindle motor (not shown), by a disc clamp 108. Disc pack 106 includes a plurality of individual discs, which are mounted for co-rotation about central axis 109. Each disc surface has an associated head 110, which is mounted to disc drive 100 for communication with the disc surface. In the example shown in FIG. 1, heads 110 are supported by suspensions 112 which are in turn attached to track accessing arms 114 of an actuator 116. The actuator shown in FIG. 1 is of the type known as a rotary moving coil actuator and includes a voice coil motor (VCM), shown generally at 118. Voice coil motor 118 rotates actuator 116 with its attached heads 110 about a pivot shaft 120 to position heads 110 over a desired data track along an arcuate path 122 between a disc inner diameter 124 and a disc outer diameter 126. Voice coil motor 118 operates under control of internal circuitry 128.

[0020] The heads 110 and rotating disc pack 106 form a communication channel which can receive digital data and reproduce the digital data at a later time. Write circuitry within internal circuitry 128 receives data, typically from a digital computer, and then encodes data in codewords adapted to the communication channel. The encoded data is then used to modulate a write current provided to a write transducer in the head 110. The write transducer in the head 110 causes successive code words to be encoded on a magnetic layer on disc pack 106. At a later time, a read transducer in the head recovers the successive code words from the magnetic layer as a serial modulated read signal. Read circuitry within internal circuitry 128 demodulates the read signal into successive parallel codewords. The demodulated code words are then decoded by decoder circuitry within circuitry 128, which recovers the digital data for use, typically by a digital computer, at a later time.

[0021] FIG. 2 shows a block diagram of an embodiment of a system 150 for communicating digital data. System 150 communicates through a communication channel 152, that can comprise an arrangement of magnetic storage discs and heads as shown in FIG. 1. Channel 152 can also be other types of communication channels such as an optical, wireless or transmission line channel.

[0022] An encoding system 154 is adapted to receive first and second 12 bit sequences 156, 158 of the data. The encoding system 154 includes encoder 200 that generates an 11 bit first codeword 160, identified as Y10:0 as a function of the first sequence 156. The encoder 200 also generates state variables 162, 164, 166, identified as S0, S1, S2, as functions of the first sequence 156.

[0023] The encoding system 154 includes encoder 202 that generates a 14 bit second codeword 168, identified as Z13:0, as a function of the second sequence 158 and the state variables 162, 164, 166. The state variables are represented in the second codeword 168 by four or fewer bits, preferably the in four initial bits of the second codeword 168.

[0024] In FIG. 2, the encoding system 154 comprises encoder circuits 200, 202, identified as ENC-A and ENC-B. The encoding system 154 also comprises code testers 204, 206, identified as CT-A and CT-B. Detailed examples of operations of the code testers, encoder circuits and decoder circuits is shown in Tables 1-12 below.

[0025] A modulator 170 receives the first and second codewords 160, 168 and is adapted to couple first and second modulated codewords 172, 174 to the communication channel 152. Codewords 160, 168 together comprise a 25 bit codeword. Modulator 170 can be arranged in a conventional manner to receive codewords 160, 168 in a parallel format and provide modulated codewords 172, 174 with analog or physical properties that are compatible with the communication channel 152. In a case where communication channel 152 comprises a magnetic disc and head, codewords 172, 174 will be in the form of serial write currents delivered to a write transducer in the head. With other types of communication channels, modulation can include other known forms of modulation such as AM, FM, PM, FSK, spread spectrum and the like. The system described here can be used over the internet or an intranet, for example.

[0026] A receiver 175 in a decoding system 182 receives the first and second modulated codewords 172, 174 from the communication channel 152. Receiver 175 includes a demodulator 176. Receiver 175 can include a Viterbi detector. The demodulator 176 generates first and second demodulated codewords 178, 180. Demodulated codewords 178, 180 can include errors as a result of passing through the communication channel 152. Decoder system 182 receives the first and second demodulated codewords 178, 180. A decoder 210 receives the codeword 180 and generates a decoded sequence 184 and state variables 186, 188, 190, identified as S0′, S1′, S2′, as functions of the second demodulated code word 180. A decoder 208 receives codeword 178 and generates a first decoded sequence 192 as a function of the first demodulated codeword 178 and the decoded state variables 186, 188 and 190. Outputs FA and FB of decoders 208, 210 indicate when invalid codewords are decoded.

[0027] The first and second demodulated codewords 178, 180 together form a 25 bit codeword. The encoding system 154 limits runs of zeros by encoding the 25 bit codeword with a run length limit (RLL) k=7. The encoding system 154 also limits runs of zeros by encoding the first and second codewords 160, 168 each with a run length limit (RLL) i=7. The encoding system 154 guarantees minimum code energy by encoding the 25 bit word with a minimum Hamming weight w=9.

[0028] The decoding system 182 comprises code pattern tester CT-A and CT-B shown at 194, 196 that decode most sequences by recognizing patterns that meet with “k”, “i” and “w” constraints. The decoding system 182 also comprises decoder circuits 208, 210, identified as DEC-A, DEC-B. The demodulator 176 preferably includes a local oscillator 177 in a phase locked loop (PLL) that generates a local oscillator output synchronized with the modulated first and second codewords 172, 174. the demodulator 176 generates, or demodulates, the first and second demodulated codewords as a function of the local oscillator output. The communication channel 152 can be in a disc drive, and the modulator is adapted to modulate the disc drive write output, while the demodulator is adapted to demodulate the disc drive read signal. The synchronization of the local oscillator compensates for speed variations in the disc drive.

[0029] In FIG. 3, a method of encoding digital data for transmission through a communication channel is shown at 250. At 252, a first sequence of 12 bits of data is received at a first encoder. At 254, the first encoder generates a first codeword of 11 bits and generates state variables as a function of the first sequence. At 256, a second encoder receives a second sequence of 12 bits of data and the state variables. At 258, the second decoder generates a second codeword of 14 bits as a function of the second sequence and the state variables, the state variables being represented by four or fewer bits in the second codeword. At 260, the first and second codewords are combined together to form a 25 bit codeword. At 262, a run length limit K=7 is set on the 25 bit codeword to limit errors.

[0030] In FIG. 4, a method of decoding digital data for transmission received from a communication channel is shown at 300. At 302, a 25 bit encoded digital codeword with a run length limit K=7 is received, the codeword representing a 24 bit sequence of data. At 304, the 25 bit encoded digital codeword is separated into a 14 bit first portion and an 11 bit second portion. At 306, the 14 bit first portion is received in a first decoder and the first decoder generates a first decoded 12 bit sequence, and also generates decoded state variables as a function of four or fewer bits of the first portion. At 308, the 11 bit second portion and the state variables are received in a second decoder. At 310, a second decoded 12 bit sequence is generated in the second decoder, the first and second decoded 12 bits sequences together forming a decoded 24 bit sequence of data.

[0031] Further details of encoders, decoders and code decoders are shown in Tables 1-12 below. Tables are used rather than circuit diagrams of flow charts to provide a more compact, understandable description of the logic operations performed. It is understood that the functions described by the tables can be performed in hardware, software, firmware or any combination of hardware, software and firmware.

[0032] Table 1, “Equations for Encoder and Decoder,” provides definitions for the symbols or logical operators used in the logic statements in Tables 2-7.

[0033] Table 2 below shows an embodiment of logic operations or calculations in the 11-bit codeword tester (CT-A), shown at 194, 204 of FIG. 2. Table 2 lists the 11 bits of input WA10-WA0 to the code tester 194 or 204 and the output TA. Intermediate results UA0-UA8, HWA are calculated as shown, and then the output TA is calculated as a function of UA0-UA8 as shown in Table 2.

[0034] Table 3 below shows an embodiment of logic operations or calculations in the 14-bit codeword tester (CT-B) shown at 206, 196 of FIG. 2. Table 3 lists the 14 bits of inputs WB13-WB0 to the code tester 206 or 196 and the output TB. Intermediate results UB0-UB11, HWB are calculated as shown, and the output TB is calculated as a function of UB0-UB11.

[0035] Table 4, shown below and continued on following pages, shows an embodiment of logic operations or calculations in the 11-bit encoder (ENC-A) 200 in FIG. 2. Table 4 lists the inputs to code tester 200 as 11 bits of inputs A10-A0 and one bit TA received from the code tester 204. Various intermediate results NA0-Gn0 are calculated as shown in Table 4, and then the outputs Y10-Y0, S0, S1, S2, WB12, WB13 are calculated using various combinations of the inputs and intermediate results as shown at the conclusion of Table 4.

[0036] Table 5, shown on the following pages, shows an embodiment of logic operations or calculations in the 14-bit Encoder (ENC-B) 202 of FIG. 2. Table 5 lists the inputs to Encoder 202 as 12 bits of inputs B11-B0 and three state variables S2, S1, S0. One bit TB is received from the code tester 206. Various intermediate results NA0-T0 are calculated as shown in Table 5, and then the outputs Z13-Z0 are calculated using various combinations of the inputs and intermediate results as shown in Table 5.

[0037] Table 6 below shows an embodiment of logic operations or calculations in the 11-bit Decoder (DEC-A) 208 of FIG. 1. Table 6 lists the inputs to Decoder 208 as 11 bits of inputs Y10-Y0, and three state variables S2, S1, S0, which are recovered state variables. One bit TA is received from the code tester 194 of FIG. 1. Various intermediate results NB1-S12 are calculated as shown in Table 5, and then the outputs A11-A0, FA are calculated using various combinations of the inputs and intermediate results as shown in Table 6.

[0038] Table 7, shown on the following pages, shows an embodiment of logic operations or calculations in the 14-bit Decoder (DEC-B) 210 of FIG. 1. Table 7 lists the inputs to Decoder 210 as 14 bits of inputs Z10-Z0. One bit TB is received from the code tester 196 of FIG. 2. Various intermediate results NB1-T0 are calculated as shown in Table 7, and then the outputs B11-B0, FB, S2, S1, S0 are calculated using various combinations of the inputs and intermediate results as shown in Table 7.

[0039] TABLE 8 below describes in a simplified format how the states S0, S1, S2 (and also S0′, S1′, and S2′) of FIG. 1 relate to 14 bits code patterns, with “X” indicating no dependency on a bit or, in other words, a so-called “don't care” relationship to a particular bit.

[0040] Table 9 on the following pages is a state diagram which maps each 12-bit data word to a corresponding 11-bit code word and next state value. The bit patterns of the data words are shown in hexadecimal form for simplicity with the least significant digit in the 12 bit data word represented in the top line and the two most significant digits represented in the leftmost column of Table 9 followed by an “x” as placeholder for the least significant digit. For example, the 12 bit data word “000” is the first entry in Table 9 where the first row labeled 00X intersects with the column labeled “0”. The 11 bit code word for the data word “000” is the 11 bit code word is “198” and the next state value is “0”. These values are shown at that intersection as “198-0”. In Table 9, the 12 bit data words cover the range 000 to FFF, and the corresponding 11 bit code words range within the limits 000 to 7FF. In FIG. 9, all words are shown in hexadecimal format.

[0041] Table 10 on the following pages is an encoding table for the 14-bit encoder when the state S0 is active. The arrangement of Table 10 is similar to Table 9, however, the state is “0” for all of Table 10 as indicated at the top of Table 10.

[0042] Table 11 below is an encoding table for the 14-bit encoder when the state S1 is active. The arrangement of Table 11 is similar to Table 10. In Table 11, the state S1 is indicated at the top of the table to be active.

[0043] Table 12 below is an encoding table for the 14-bit encoder when the state S2 is active. The arrangement of Table 12 is similar to Tables 10, 11. In Table 12, the state S2 is indicated at the top of the table to be active.

[0044] The various constraints on run length limits, Hamming weight are integrated into the encoding and decoding used. The “i” constraint directly affects the delay of decisions in the Viterbi algorithm and also influences the length of error propagation, and the “i” constraint is kept as short as possible. The “k” constraint is also kept short. The encoder 202 and decoder 208 are state driven and all of the code words are carefully chosen such that the state can be determined by the four leading bits of a 14 bit codeword as shown in Table 8.

[0045] The m bit data word is separated into two interleaved sequence of p=12 and q=12 bits. The sequence of p bits is mapped into a u=11 bit codeword and a sequence of q bits is mapped into a v=14 bit codeword. Since 2^pcodewords are needed for a p bit sequence, and 2^qcodewords are needed for a q bit sequence, the conditions 2^p≦N_uand 2^q≦N_vfor the number of bits N in the codewords must be met. An integer “t” is then found experimentally that satisfies the conditions 2^p≦[N_u*t] and [2^q*t]≦N_vsimultaneously. This arrangement ensures that the codewords can be divided into groups corresponding to the state numbers.

[0046] The encoding process of mapping m bits of data into n bits of the codewords can be done as follows:

[0047] 1. Break the m-bit pattern into two patterns of p bits and q bits.

[0048] 2. Map the p bit pattern into a u bit codeword and a state number S.

[0049] 3. Go to the group of v bit codewords that is labeled with state number S and map the q bit pattern into a v bit codeword.

[0050] 4. Combine the u bit and the v bit codewords to form the n-bit codeword.

[0051] The decoding process can be done as follows:

[0052] 1. Break the n bit pattern into two patterns of u bits and v bits in length.

[0053] 2. Since the v bit patterns in each state are unique, the state number S of the v bits can be determined. and the q bit data pattern is recovered.

[0054] 3. Based on the state number S and the u bit code word, recover the p bit data pattern.

[0055] 4. Combine the p bit and q bit data patterns to form or recover the m bit data pattern.

[0056] With m=24, n=25, k=7, i=7, w=9, the values p=12, q=12, u=11, v=14 are selected. There are then 1,484 eleven bit code words and 13,484 fourteen bit code words possible. If t is selected to be 3, then 2^p=2¹²=4096 and (N_u*t)=4452 and (2^q*t)=(2¹²*3)=12288 and N_v=13484 and the inequality conditions above are met. As there are more than enough 14 bit codewords, codewords are chosen so that each state can be determined with a minimal number of bits of the codeword as shown in Table 1.

[0057] By employing the method of mapping a data word directly into a code word, the amount of logic in the encoder and decoder can be kept low. This method is able to encode a majority of the data words. In the encoder, 12 bit data words are encoded into 11 bit code words and 14 bit code words alternately. To encode a 12 bit data word into an 11 bit code word, the least significant 11 bits are entered into a codeword tester CT-A which checks if the 11 bit pattern already satisfies the required constraints. If the constraints are satisfied, the 11 bit word is shifted out as the code word. The state for the next code word is determined by the most significant bit of the data word. If the bit is a “0”, the next state will be S1. If the bit is a “1”, the next state will be S2. By exhaustive search, there are 1484 11 bit patterns that satisfy the constraints. Of the 4096 possible words, 1484 have S1 as the next state, 1484 have S2 as the next state, leaving 1128 data words that do not satisfy the constraints and will be mapped into code words using Boolean logic expressions in equations Ga through Gn shown below.

[0058] To encode a 12 bit data word into a 14 bit code word, two bits are attached to the 12 bit word as the most significant bits, and the value of these two bits depends on the state indicated by the previous code word mapping. The values 11, 10, and 01 are chosen for corresponding states S2, S1 and S0. These 14 bits are entered into codeword tester CT-B which identifies the 14 bit patterns that satisfy the constraints and shifts those patterns out as the code word. There are 3728, 3464 and 3468 patterns that satisfy the constraints for states S2, S1 and S0 respectively. Since each state needs 4096 patterns, there are 368, 632 and 628 remaining patterns for states S2, S and S0 respectively. There are 2824 14-bit patterns that start with 00 available. The Boolean logic that maps these remaining patterns can be found in equations with terms Ha to Hf, Ja to Jh and Ka to Kh.

[0059] The decoders are constructed similarly. By using code pattern testers, about 86% of the code patterns can be encoded and decoded simply by the code testers. Only about 14% of the patterns require the more complex Boolean logic in the decoders.

[0060] The system (150) for communicating digital data through a communication channel (152) comprises an encoding system (154) adapted to receive first (156) and second (158) 12 bit sequences of the data. The encoding (154) generates an 11 bit first codeword (160) and state variables S0 (162), S1 (164), S2 (166) as functions of the first sequence (156). The encoding system (154) generates a 14 bit second codeword (168) as a function of the second sequence (158) and the state variables (162, 164, 166). A modulator (170) receives the first and second codewords (160, 168) and couples first and second modulated codewords (172, 174) to the communication channel (152). A receiver (179) includes a demodulator (176) that receives first and second modulated codewords (172, 174) from the communication channel (152). The demodulator (176) generates first and second demodulated codewords (178, 180).

[0061] The decoding system (182) receives the first and second demodulated codewords (178, 180). The decoding system (182) generates a second decoded sequence (184) and decoded state variables S0′ (186), S1′ (188), S2′ (190) as a function of the second demodulated code word (180). The decoding system (182) generates a first decoded sequence (192) as a function of the first demodulated codeword (178) and the decoded state variables (186, 188, 190).

[0062] The first and second codewords (160, 168) together form a 25 bit codeword. The encoding system (154) limits runs of zeros by encoding the 25 bit codeword with a run length limit k=7, and by encoding the first and second codewords (160, 168) each with a run length limit i=7. The encoder guarantees a minimum code energy by encoding the 25 bit word with a Hamming weight w=9.

[0063] The decoding system (182) comprises code pattern testers (194, 196) that decode sequences that meet the “k”, “i” and “w” constraints. The decoding system (182) can be a Viterbi detector. The demodulator (176) can generate a local oscillator (177) output synchronized with the modulated first and second codewords (172, 174). The demodulator (176) can generate the first and second demodulated codewords (178, 180) as a function of the local oscillator (177) output.

[0064] The communication channel (152) can be in a disc drive (100) with a modulator modulating the disc drive write output, and the demodulator demodulating the disc drive read signal. The synchronization of the local oscillator (177) compensates for speed variations in the disc drive (100). The magnetic disc drive (100) comprises a magnetic disc (106), and a read and write transducer head(110) coupled to the magnetic disc.

[0065] 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. While encoding and decoding are shown in block diagram form, it is understood that it can be done using lookup tables as shown. For example, the particular elements may vary depending on the particular application for the disc drive while maintaining substantially the same functionality without departing from the spirit and scope of the present invention. In addition, although a 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 and cellular phone systems, without departing from the spirit and scope of the invention. Various other codes may be used, more than one encoding or decoding table may be linked together, additional or different state numbers may be used, or the data provided to the encoders or decoders can be partitioned or overlap.