Coded data generation or conversion – Digital code to digital code converters – Byte length changed
Reexamination Certificate
1999-11-30
2001-08-07
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Byte length changed
C341S106000
Reexamination Certificate
active
06271776
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention pertains to encoding and decoding of data for transmission to/from a recording medium or over a data channel.
2. Related Art and Other Considerations
A challenge in the design and operation of encoders and decoders is minimizing the size and complexity of logic circuitry and/or memory utilized thereby. In this regard, the encoding and decoding of large blocks of data should be relatively fast so as not to impede the transmission of data over a data channel, or the transducing of data (e.g., reproduction or recording of data) relative to a storage medium, such as a rotating disk medium (e.g., magnetic disk or optical disk), for example.
One existing technique for encoding and decoding data is enumerative coding combined with a trellis scheme. A trellis is made from a state diagram that describes the code, and is formed over time as showing how many paths emanate from a node to a final state. An example of such technique is described by Mansuripur, “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. Basically, for encoding according to such a technique, one views an entire block of data (e.g., 17 bits for a 17/18 encoding scheme) as an integer. The integer is utilized as a starting point for working through a trellis, comparing the starting point integer and modifying the integer as necessary along the way through the trellis. At each point along the trellis, one output bit of the encoded codeword is produced.
Enumerative coding combined with a trellis scheme is particularly applicable to a Quadbit mod 2 code. A Quadbit mod 2 code allows quadbits (four consecutive NRZI transitions) on every other bit position. As referenced herein, bits of an encoded codeword or data block are labeled starting with the length of the block minus one, and descending down to zero. Using this numbering convention, quadbits are allowed to start on even numbered bits. When the length of each block is even, quadbits start on even-numbered bits and end on odd-numbered bits. The quadbit constraint does not allow runs of longer than four transitions in any codeword (i.e., data block).
As an example of encoding using enumerative coding in combination with a trellis scheme, consider an incoming 17/18 data block which, when viewed as an integer, has the value 68506. The incoming data block thus has 17 bits, and is to be encoded to an 18 bit value. The trellis of
FIG. 8
is applicable to a 17/18 encoder/decoder, and shows the bit positions 17 through 0 arranged in columns and various even numbered states S
0
through S
8
arranged in rows. The incoming data block (i.e., integer value 68506) is first compared with the first value in the trellis, specifically the value 70632 in bit position 17, state S
2
. Since 68506 is less than 70632, the technique follows the upper path in the trellis, ending at state S
0
(as indicated by the dashed line). Since the upper path indicated by a dashed line is utilized, the technique outputs a NRZI 0 (zero) bit as the first bit of the 17/18 encoded output string. Next, the value 68506 is compared with the number associated with the trellis position to which the upper path led, namely bit position 16, state S
0
. The value 35316 is at bit position 16, state S
0
, which means that the value 68506 is compared with 35316. The value 68506 is greater than or equal to 35316, with the result that the technique follows the lower path (i.e., the solid line path) to bit position 15, state S
2
. Since a solid line path is taken, the technique outputs a NRZI 1 (one) value. Moreover, since a solid line path was taken, the technique subtracts 35316 from 68506, resulting in a new value 33190 to be used for the next comparison. Then, as the next comparison, the new value 33190 is compared with the value at bit position 15, state S
2
(i.e., 18630). Since 33190 is greater than or equal to 18630, the technique follows the lower path, generating a NRZI 1, and does another subtraction.
The technique thus continues in the foregoing manner, until the entire trellis is traversed. At each point of the trellis, a comparison is made. If, in the comparison, the operative input value is greater than or equal to the trellis position value, the lower path (solid line) is followed with the result that a NRZI 1 value is generated and a subtraction is performed. On the other hand, if the operative input value is less than the trellis value, the upper path (dashed line) is followed with the result that a NRZI 0 value is generated and no subtraction is performed. When a trellis state is reached that has only one path leaving it, the encoder must follow such path, with no comparison or subtraction being performed. For the representative incoming 17/18 data block having the integer value 68506 utilized for the example above, the output sequence is 011110000111100001.
In the trellis scheme enumerative coding technique described above, the same trellis is used for a decoding operation in an essentially reverse procedure from the encoding operation. In decoding, however, an integer is built up (representing the decoded word) rather than taking apart an integer to create an encoded word, as occurs during encoding. In decoding, the decoded data integer is first initialized to zero. Then, the technique follows the trellis according to the dashed and solid lines. If the first bit of the sequence to be decoded is a NRZI 1, the number shown at the state from which the line leads (i.e., the state in which the compare is performed) is added to the decoded word integer. On the other hand, if the first bit of the sequence to be decoded is a NRZI 0, no addition is performed. The decoding technique then moves to the next state of the trellis, and either adds or ignores the value associated with the state in accordance with whether the bit to be decoded is a NRZI 0 or NRZI 1. The final summation after traversing the entire trellis is the decoded data block or data word.
In general it is desirable to keep trellis size to a minimum. This is equivalent to desiring the original state transition diagram to have as few states as possible. But the more constraints a code has, the more states its transition diagram is likely to have. In fact, while a QM2 (quadbit mod 2) code can be described with five states, these states only enforce the quadbit constraint. They neither enforce a runlength constraint, nor a quasi-catastrophic constraint. Adding a runlength constraint can be accomplished by adding a number of states equal to the desired runlength minus one. For example, a runlength constraint of 9 can be added to the QM2 code to get a state transition diagram with 13 states. However, this more than doubles the number of states, and there are still quasi-catastrophic sequences which should be removed. Also, the comparison numbers in the trellis lose some symmetry when adding a runlength constraint, which also increases implementation complexity.
Some particular sequences of bits, such as quasi-catastrophic sequences alluded to above, should be avoided for encoding and decoding. Examples of quasi-catastrophic sequences are an all-zeroes sequence, an all-ones sequence, and any sequence which has a continuous run of an even number of zeros followed by an even number of ones (zeros and ones, in the present discussion, being in NRZI representation). In order to avoid the problems attending such sequences, these sequences are normally coded out so that a detector does not have to deal with them. Coding out of the undesirable sequences involves special trellis considerations that makes the trellis larger and introduces other problems. Thus, a typical enumerative coding technique in combination with a trellis scheme, such as that described above, does not lend itself easily to removing such undesirable sequences.
What is needed, therefore, and an object of the present invention, is an encoding and decoding technique which effectively keeps a state diag
Turk Stephen Alan
Zook Christopher Paul
Cirrus Logic Inc.
Shifrin Dan
Young Brian
LandOfFree
Selectively removing sequences from an enumerative... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Selectively removing sequences from an enumerative..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Selectively removing sequences from an enumerative... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2531283