Direction-Constrained Ternary Codes Using Peak and Polarity Detection

This invention relates to a method and apparatus for coding binary symbol strings into ternary symbol strings and synchronously recording said ternary symbol strings onto a magnetic medium such that clocked recovery of the recorded signal may subsequently be made using only peak and polarity detection.

In the prior art, Cupp, U.S. Pat. No. 3,618,044, discloses and claims a method and apparatus for converting binary into ternary recording codes and transforming the ternary symbol strings into a clocked multilevel recording signal and imprinting said recording signal upon a magnetic medium. Cupp, however, is concerned with and processes absolute signal levels rather than signal transitions.

Larkin, U.S. Pat. No. 3,133,274, converts a ternary symbol string into a binary (2-level) write current waveform, which waveform is then used for saturation recording. Further, Larkin uses a synchronous clock and a peak/polarity detector for recovering the saturated recorded code symbols. Central to his invention is the notion of decoding a detected positive peak as a "2", and a negative peak as a "1". In Larkin, the absence of a peak is taken to be a "0". It should be appreciated that, in saturation recording, a negative and positive peak must alternate. Thus, it would not be possible to record and recover a string in Larkin of "2" followed by "2". That is, one could not force two consecutive peaks to both be positive. This is avoided in Larkin by inserting a dummy negative peak in-between the positive peaks corresponding to the "2" symbols. This superflous negative peak will not occur at a code bit time as marked by the clock. Therefore, Larkin discards all such superflous or dummy peaks which were inserted solely to conform to the necessary peak polarity alternation as the detected peaks are decoded into code symbols. However, Larkin ignores the effect of insertion of superflous transitions in the write signal "in-between clock times" which is the shifting of peaks from their expected positions. Peak insertion will increase the detection error unless the clock is slowed down and recording density is lost.

It is an object of this invention to ascertain a class of ternary square wave signals detectable by peak position and polarity detection alone without need for amplitude discrimination, ternary codes being used to increase data density recording at the same clock rate as binary codes.

This object is satisfied by use of selective direction-constrained run length limited (RLL) signals. The direction constraint imposes the rule that half-step transitions can only occur in pairs of the same polarity. Alternate half-step pairs of opposite polarity are forbidden. Forcing the peaks corresponding to half-step transitions to occur in consecutive pairs with the same polarity avoids the need for amplitude discrimination. The RLL (d,k) constraint includes a "d" number of clock times when a transition is forbidden and "k>d" clock times within which consecutive transitions must occur. The latter determines a minimum frequency for clocking purposes while the former eases the peak shift problem by optimizing the minimum transition spacing.

More particularly, the invention is manifest as a method for coding binary symbol strings into ternary symbol strings and synchronously recording said ternary symbol strings onto a magnetic medium such that clocked recovery of the recorded signal may be subsequently made using only peak position and polarity detection. The method comprises the steps of (a) mapping a binary symbol string into a direction-constrained run length limited (RLL) ternary symbol string (e.g. r-bit or variable length blocking of a binary symbol string; converting the blocked symbol string into a run length limited n>r-bit blocked ternary symbol string at a predetermined rate); (b) transforming the ternary symbol string into a clocked multilevel recording signal, said recording signal including signal levels in the range -a<0<+a, transitions between levels being made as either full-steps (+a to -a, -a to +a), or halfsteps (0 to .+-.a or .+-.a to 0), consecutively occurring half-steps being limited to pairs of like polarity (+a, +a; -a, -a), half-steps of alternate polarity (+a, -a; -a, +a) being excluded; and (c) imprinting a magnetic medium with the recording signal.

The invention also includes a method for recovering the duly recorded signal from a magnetic medium. Signal recovery occurs in a high-density, high-data rate nonsaturated magnetic recording environment. The signals consist of the waveforms derived in step (b) above from a (d,k) run length limited, direction-constrained, ternary symbol encoding of binary symbol strings. Recovery uses peak position and polarity detection for readback thereof. The method steps for binary symbol string recovery comprises (a) reading back the recorded signals and detecting therefrom the presence of magnitude peaks and their polarities; (b) converting the detected peak polarities to ternary code symbols, the conversion includes a maximum delay of k+1 clock times; and (c) inverse mapping of the recovered ternary string into the binary data, e.g. blocking the ternary symbols into length n and obtaining r<n length binary symbols by way of table lookup and a lookahead of a predetermined number of ternary symbol blocks. Relatedly, in the recovery method, the delay is used to permit context decoding of half-steps, and further, the number of ternary symbol lookahead blocks is a function of the (d,k) constraint and the code rate (r/n).

With reference to the prior art, it should be noted for example, that Cupp, unlike this invention, fails to impose either an RLL constraint or consecutive halfpulse pairs of like polarity constraint therein. Consequently, Cupp, unlike the invention, fails to overcome the peak shift problem resolved by the invention. Further, Cupp apparently relies upon an equalizer to compensate for the amplitude difference between half- and full-step peaks.

In contrast with the invention, the dummy transitions of Larkin would probably cause severe peak shift which would lead to errors in clocking the detected peaks. As a result, some type of run length limited code would be necessary to achieve high recording density. Lastly, Larkin does not address the loss of potential data density occasioned by his use of dummy transitions. The insertion of these transitions merely adds redundancy rather than information to the recorded string.

FIG. 1 depicts a full-ternary channel waveform.

FIG. 2 shows a direction-constrained ternary channel waveform.

FIG. 3 exhibits a block diagram representation of direction-constrained ternary code-to-waveform conversion.

FIG. 4 sets out a finite state machine representation of the direction-constrained ternary-towaveform conversion of FIG. 3.

FIG. 5 lays out an encoding table for a rate 3/4 direction-constrained ternary (1,3) code.

FIG. 6 depicts a decoding table for the code in FIG. 5.

FIG. 7 sets out a block diagram for the recovery of the ternary-encoded signal.

FIG. 8 illustrates a clocked waveform-to-ternary conversion according to the invention.

FIG. 9 shows a state machine in abstract (tabular) form for converting waveform peak detection events into a direction-constrained ternary code.

FIGS. 10 and 11 exhibit a circuit for recovery of the (1,3) direction-constrained ternary code from a peak and polarity detected waveform.

FIG. 12 illustrates blocked binary to RLL direction-constrained ternary and vice versa.

Current approaches to recording digital information on magnetic media use only two levels of magnetization. That is, the medium is saturated in either one of two polarities. With AC bias recording, it becomes possible to achieve discrete levels of magnetization on magnetic media such as disks or tapes.

In contrast to the art, this invention utilizes three states of "levels". The three states are saturated minus (-a), saturated plus (+a), and degaussed (0). In the method and apparatus of this invention, the medium passes under a read/write head and time is divided into "bit periods" or recording channel time units.

When two levels of recording are employed, a detector need only detect the existence of a flux reversal and assign it to a bit period or channel time unit. Information concerning the direction of the flux reversal is redundant. If coding is employed which can utilize both the existence and direction of flux reversals, then more information can be packed into code strings. When three levels are used, reference may be made to a "ternary channel". Run length constraints may be applied to a ternary channel where the constraints define when transitions are allowed relative to the last transition. When no other constraints are applied, there exists a full-ternary RLL channel. For a full-ternary RLL channel, there are two choices for each transition. That is, a transition can go from +a to -a or 0, or from 0 to -a or +a, or from -a to 0 or +a. The detector must be able to discriminate between a transition from +a to 0, and +a to -a, by the magnitude of the detected flux reversal. Thus, two thresholds are required; that is, a threshold between noise and a half-reversal (+a to 0), and a threshold between a half-reversal and a fullreversal (+a to -a).

Referring now to FIG. 1, there is shown a waveform for a full-ternary (1,3) constraint. This is an extension of the binary (1,3) constraint where there is a requirement to have a flux reversal no sooner than (d+1) time units but no later than (k+1) time units after the last flux reversal, d being 1 and k being 3. Once the two time units have occurred following the last flux change, the ternary channel may have a transition to any of the other two channel states. In this invention, the direction constraints relieve the detector of the need for a double threshold and yet achieve increased information carrying capacity in the use of three recording levels.

Referring now to FIG. 2, there is shown a direction-constrained ternary channel waveform. In considering the "problem transitions" of the full-ternary (1,3) channel, it is necessary to distinguish the half-transition (+a to 0) from the full-transition (+a to -a) and the similar transitions from the recording state -a. To alleviate the problem transition, suppose there is introduced the requirement that a (+a to 0) transition be followed by a (0 to -a) transition. That is, one leaves the 0 state in the same direction as one enters it. Now, there is no need to discriminate between the half- and full-magnitudes of the flux reversals on the basis of the observed peak amplitudes in the readback signal if the polarity of the next observed peak is noted. If there are obtained two successive peaks of the same polarity, the flux transition corresponding to the first peak must have been a half-magnitude transition, as well as the flux transition corresponding to the second peak. After having determined the polarity of the next peak, a determination can be made as to whether the previous transition was of half- or full-magnitude.

Referring now to FIG. 3, there is shown a logical block diagram conversion of a binary datastream into a form of coding suitable for energizing either a positive P, zero Z, or negative N amplitude level to be impressed upon a suitable recording medium. For a (1,3) code, the binary data is blocked three bits at a time and applied to encoder 1. The encoder employing a directionconstrained binary-to-ternary transformation generates a sequence of ternary code symbols, any symbol of which may assume the value of 0, 1, or 2. In turn, the modulator 3 and waveform driver 5 transform the ternary code string into a sequence of amplitude levels (p, z, or n) which is applied by write head 7 to a magnetic recording medium.

In this and the following discussion, reference will be made to finite state machine (FSM) representation and design. Thus, the following Wulf et al, "Fundamental Structures of Computer Science", Addison-Wesley Publishing Co., ISBN 0-201-08725-1, pp. 9-48, the machine equivalent of digital computing transformations can be represented by an FSM having an input symbol set, an output symbol set, a set of internal states, a first function for mapping an ordered pair drawn from an input symbol, and a present internal state into a next internal state and a second function for mapping an ordered pair of input symbols and internal states into an output symbol. In this regard, one could consider the conversion of a binary bit string into magnetic recording levels as to be formed by two successive FSM's. The first is formed by encoder 1 and the second consisting of modulator 3, waveform driver 5, and write head 7.

Referring now to FIG. 5, there is shown an encoding table representation of such an FSM for encoder 1. Since a (1,3) direction-constrained ternary code is to be produced at the output of said encoder, the input binary bit string is applied thereto three bits at a time. Thus, there are eight possible 3-bit input combinations. These are represented by appropriate columns in FIG. 5. Each of the eleven row entries labeled A, B, C, . . . , L designates a counterpart internal state of the FSM of encoder 1, Likewise, the row and column entry defines the ternary output and the next internal state to be assumed by the encoder. Thus, if the 3-bit input combination "100" were applied to the encoder which was in state G, then the output would be "0102" with the next internal state being "K" assumed by said encoder for a next input combination of, say "010", and the encoder in state K, the output would be "0200" with the next state being F.

Referring now to FIG. 4, there is shown the tabular representation of an FSM which takes ternary values, one at a time, as inputs and produces direction-constrained amplitude levels as a waveform output suitable for recording on a magnetic medium. In this second FSM, four internal states are represented, these being P, N, K, and L. As an operative example for an input ternary value of 0 and an internal state of N, then the next state is N and there is no change to the waveform output. If this is followed by the next ternary value of 1 with the FSM being in state N, then the next state is P and the waveform output is full positive. Suppose the very next ternary value were 2 with the present state P, then the next state would be K and the output would be half-negative to 0. Also, in the FSM of FIG. 4, two row entries namely for present states K and L having a ternary value input of 1 have neither a next state nor affect on the waveform. Indeed, these are forbidden. Such a circumstance represents full-steps from degaussed state (0), which is impossible.

Referring now to FIGS. 5 and 6, the directionconstrained ternary (1,3) code is of the "sliding block" type with state-dependent encoding and finite lookahead decoding. The code has a rate 3/4 corresponding to an efficiency of 92 percent. The sliding block code type was popularized by Adler et al, "Algorithms for Sliding Block Codes", IEEE Transactions on Information Theory, pp. 5-22, January 1983.

In order to recover the original bit string from the recorded waveforms on a magnetic medium, it is first necessary to access said waveforms, convert them to ternary code, and then execute a ternary-to-binary transformation. In this regard, FIG. 7 depicts a block diagram to convert a differentiated waveform to a ternary code string. In this matter, a read head is a differentiator picking up only the changes in recorded amplitude level. The derivative waveform is sent to conventional peak detection circuitry which provides two logic signals as outputs. The first output indicates whether there was a peak detected at a given clock time. The second output is obtained from a conditional circuit. This circuit ascertains whether a peak was detected. If the binary information state of the conditional circuit was zero, then the peak was positive. Otherwise, the detected peak was negative. As noted, the peak detector output is fed to the peak-to-ternary finite state machine which converts this information back to the original direction-constrained ternary information. The peak-to-ternary FSM imposes a delay for the results because the half-peaks require the next peak to be detected before the ternary symbol can be fully resolved. That is, recovery of the ternary code string is by decoding in context. An example of this may be seen by referring to FIG. 8.

FIG. 6 shows a decoding table, including lookahead blocks, for a particular implementation of a fixed length, rate 3/4, direction-constrained RLL (1,3) code. FIG. 12 illustrates the conversion of blocked binary data to a ternary string. The internal state of the encoder is shown at each step, along with the ternary output of the encoder. FIG. 12 also illustrates the decoding of the blocked recovered ternary string (the output of the peak-to-ternary demodulator algorithm) to the binary data string. The use of finite lookahead (no more than 1 block of 4 ternary symbols) to recover the original binary string is shown.

Referring now to FIG. 8, there is shown an example of waveform-to-ternary conversion. The topmost waveform (a) shows the waveform as originally written. It begins at the initial level POS. There are six transitions between the three levels shown. The levels are POS, 0, and NEG. The clock periods are represented by four character spaces and are labeled a, b, . . . , o. Beneath this waveform is a row which shows the output of the recovery FSM which reads the signal and encodes it into a 2-bit code. In this 2-bit code, 00=no peak, 1x=peak, 10=positive peak, and 11=negative peak. These output signals drive the peak-to-ternary algorithm whose output is the original direction-constrained ternary code, i.e. the output from encoder 1.

The peak-to-ternary demodulation algorithm, which should be read together with FIG. 8, consists of six steps. For purposes of demodulation, the algorithm is entered each clock time, when the peak detector has new output values for peak and polarity. The algorithm steps include:

Step 1. If there is no peak, then the final ternary symbol is 0 after which exit the algorithm.

Step 2. If there is a peak from step 1, record its polarity as the new previous polarity (PREVPOL) for the next clock time and go to the next step.

Step 3. Given that there is a peak, then compare the current polarity (POL) with PREVPOL and then go to the next step.

Step 4. If POL is opposite to PREVPOL, provisionally assign symbol "1" to this clock time and exit. If the polarities are not opposite, then go to the next step.

Step 5. Assume that there is a peak and current polarity (POL) which is the same as PREVPOL. Consequently, assign symbol "2" to this peak and go to the next step.

Step 6. Assign symbol "2" as the final value to the previous peak, which had been initially assigned a value of "1" and exit.

Note that FIG. 8(d) shows where the delay in the recovered ternary sequence occurs relative to the waveform. That is, the first half-transition at time "b" is delayed as is the second to last at time "1".

Referring now to FIG. 9, when taken together with FIGS. 10 and 11, there is shown an embodiment for converting the detected peaks and polarities of the differentiated readback signal obtained from the magnetic storage medium to the direction-constrained ternary code. FIG. 10 is directed to circuits for transforming the peak and polarity detection into an initial ternary signal set, while FIG. 11 takes this intermediate level and converts it to a final direction-constrained ternary code sequence. With reference to the peak-to-ternary (demodulation) algorithm, the circuit of FIG. 10 implements steps 1-5 while the circuit of FIG. 11 performs step 6. It should be recalled that steps 1-5 of the algorithm are directed to tracking the previous polarity and the initial value of a recorded symbol, while step 6 determines when the initial value of "1" for a clock time needs to be changed and then renders that change.

Referring now to FIG. 9, there is shown a table defining a FSM to convert peak detection to initial direction-constrained ternary code. Referring to FIG. 10, the indication of peak detection is applied to path 21 while that of polarity is applied to path 23. Relevantly, all of the flipflops in the embodiments shown in FIGS. 10 and 11 are of the D type and are edge triggered. In this regard, reference should be made to G. G. Langdon, Jr., "Computer Design", Computeach Press, Inc., San Jose, Calif., ISBN 0-9607864-0-6, pp. 512-518, copyright 1982. See also Montgomery Phister, "Logical Design of Digital Computers", Wiley, N.Y., 1958. Flipflop 33 is responsive either to the existence of detected peaks and polarities over paths 21 and 23 through AND gate 29 and OR gate 31, or the absence of a peak on path 21 and a set condition of flipflop 33 set back over path 35 through AND gate 27 and OR gate 31. Note, that the absence of a peak on path 21 appears as an input to AND gate 27 through inverter 25. Path 21 is applied to AND gate 39 as well as forming an input to the first stage 43. The polarity signal applied on path 23 together with the output of flipflop 33 on path 35 is applied to an exclusive OR Invert gate 37. To determine if the previous two peaks had the same polarity, a signal representative of a half-transition on path 41 is derived from AND gate 39 responsive to the output of exclusive OR Invert gate 37 and the peak signal condition on path 21. The output of FIG. 10 is the initial ternary determination, as shown in the top row of FIG. 8(c). FIG. 11 is the circuit which converts the initial ternary to the final ternary (i.e. which goes from the top row of FIG. 8(c) to the third or bottom row of FIG. 8(c), via step (6) of the peak-to-ternary demodulation algorithm. The final binary-coded ternary output appears in the form of signals on paths 53 and 55 respectively of FIG. 11. The peak out on path 53 is obtained as the last state output of a right shifting peak register formed by D-type flipflops 43, 45, 47, 49, and 51. The output on path 55 is obtained from the shift register chain of D-type flipflops 65, 63, 61, 59, and 57.

How many bits these shift registers must have in order to convert an initial determination of ternary "1" to a ternary "2" is considered. For example, if k is the maximum allowable clock time between adjacent peaks, it follows that since the peak following an initial ternary value of "1" can be as long as k+1 clock times later, then it is desirable to shift the ternary output symbols of the circuit in FIG. 10 into a "k+2" digit ternary right-shifting shift register. For the code in this disclosure, the value of k+2 is 5. The ternary digit is represented by the two binary bits called peak and half, i.e. the outputs on paths 21 and 41 respectively. As a consequence, there exists a (k+2) bit shift register for peak and a (k+2) bit shift register for half. The digit representing the previous peak is the position indicated by the leftmost "1" value in the peak shift register.

If the shift register positions are numbered 1, 2, . . . , k+2, then when the ternary digit positions mentioned in note 2 of FIG. 9 are to be right shifted into position 1, positions 2 through k+1 are to be considered the allowable node transition symbols of the maximum clock times between peak (value k) constraint. Further, the rightmost shift register position k+2 is the furthest position from the previous peak's digit position that could possibly receive the change.

For example, to consider the effect the change required by note 2 would have on a 5-digit shift register, consider the use of a "leading 1" detection circuit fed by the outputs of positions 1 through k+1 of the peak shift register in order to locate the bit value "1" in the lowest-numbered bit position. Suppose, for example, two half-transitions occur in adjacent clock times. The first half-transition will be in position 1 while the second would be detected by exclusive OR gate 37 and AND gate 39. The identified bit position by the "leading 1" detection logic circuit will be position 1. Therefore, position 2 of the half-shift register must have the value "1" after the shift. Thus, as the second half-transition value (ternary 2) is being shifted into position 1, the bit value "1" is being shifted into position 2 of the half-shift register. This converts the value from a ternary 1 to a ternary 2.

The circuit in FIG. 11 accepts the initial ternary values from the output on respective paths 21 and 41 of the circuit in FIG. 10. The FIG. 11 circuit selectively changes an initial ternary "1" symbol to a ternary value of "2" under specified conditions.

In FIG. 11, the interstage coupling between the register stages 65, 63, 61, 59, and 57 is by way of counterpart OR gates 81, 83, 85, and 87. One input of each counterpart OR gate is the output of the immediate adjacent D flipflop register stage. Thus, for example, to do the shift, one input of OR gate 83 is formed from the output of flipflop 63. A second input into the counterpart OR gate is formed from an AND gate. Thus, AND gates 67, 71, 75, and 79 are the respective second inputs to OR gates 81, 83, 85, and 87. During an operation which converts a ternary 1 to a ternary 2, only one of these AND gates is value TRUE, corresponding to the peak in flipflops 43, 45, 47, or 49 with the halftransition signal on path 41. The peak is determined by a priority determination circuit consisting of inverter 69, NOR gates 73 and 77, and AND gates 67, 71, 75, and 79.

In order to change a ternary 1 to ternary 2, such a change occurs during a shift by forcing a "1" into the lower (HALF) shift register instead of the "0" that would have been normally shifted therein. This change occurs when the output of the half-signal circuit is "1". The half thus "opens" AND gates 67, 71, 75, or 79 to the unique bit value of "1" in the peak register consisting of flipflops 43, 45, 47, and 49. This "1" is ORed into the appropriate data input of the half-shift register consisting of flipflops 63, 61, 59, and 57. In all other cases, the output of the AND gates is "0". This "0" is ORed with the bit value from the previous shift register stage in order to give the output of that data value.

FIG. 8 shows the conversion of the waveform to ternary. FIG. 8(a) is the original waveform and FIG. 8(b) shows the output of the peak detector of FIG. 7 for steps (1) and (2) of the algorithm. FIG. 8(c), top line, shows the state of flipflop 33, PREVPOL, of FIG. 10 for each time period for steps (1) and (2) of the algorithm. The second line of FIG. 8(c), whether the peak is the same as the previous, represents the output of XOR Invert gate 37 of FIG. 10 and step (3) of the algorithm. The third line of FIG. 8(c) represents the output peak, path 21, and half, path 41, at each step, which corresponds to steps (4) and (5) of the algorithm. These two binary signals are for the initial ternary value. Finally, the last line of FIG. 8(c) shows the output of FIG. 11, which corresponds to step (6) of the algorithm. For example, consider what happens at time "d", the second peak detected. The top line of FIG. 8(c) shows it to be positive and the second line has "yes", meaning the polarity is the same as the previous. The fourth line of FIG. 8(c) shows the ternary value is "2" since there was a half-transition. However, now the initial ternary of "1" must be converted for time "b". So, while the ternary value of time "d" is going to be shifted into flipflops 43 and 65, the ternary value for time "b" will be shifted into flipflops 47 and 61. The conversion of ternary 1 to ternary 2 is done through inverter 69, AND gate 71 (all of whose inputs are TRUE), and OR gate 61.

From the foregoing description, it will be apparent that there has been provided an improved system with the transmission and storage of digital information. It will be appreciated that the invention is also applicable to several forms of magnetic storage such as magnetic disk and drum as well as to data transmission in general. Variations and modifications in the described system within the scope of the invention will become apparent to those skilled in this art.