Direction-constrained ternary codes using peak and polarity detection

A class of ternary square wave signals is detectable by peak polarity detection alone without need for amplitude discrimination. The ternary codes are used to increase data density recording at the same clock rate as binary codes. This is satisfied by selective direction-constrained run length limited (RLL) signals. The direction constraint is that the half-step transitions can only occur in pairs of the same polarity. Alternate half-step pairs of opposite polarity are forbidden. This avoids the need for amplitude discrimination. The RLL (d,k) constraint includes "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. This eases peak shift detection.

TECHNICAL FIELD 
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. 
BACKGROUND OF THE INVENTION 
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. 
THE INVENTION 
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&gt;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&gt;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&lt;0&lt;+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&lt;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.

DESCRIPTION OF THE PREFERRED EMBODIMENT AND INDUSTRIAL APPLICABILITY 
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.