Matched Spectral Null Codes With Partitioned Systolic Trellis Structures

This invention relates to coding and maximum-likelihood detection of input strings of binary data applied to partial-response channels. More particularly, it relates to methods and apparatus wherein a maximum-likelihood detector employs a periodic partitioned systolic trellis structure with time-varying replication of states and edges, preferably implemented with vertical compression of portions of the trellis structure to constrain spectral-null sequences generated from an initial running-digital-sum (RDS) value to assume a certain prescribed subset of RDS values at both the end and at least one prespecified interior position within the trellis period, for providing improved coding gain, constraints for timing and gain control, and reduced error-event lengths.

The following prior art references are considered by applicants to be the most pertinent to the present invention:

[A] U.S. Pat. No. 4,888,779, granted Dec. 19, 1989, entitled "Matched Spectral Null Trellis Codes For Partial Response Channels."

[B] U.S. Pat. No. 5,257,272, granted Oct. 26, 1993, entitled "Time-Varying Modulo N Trellis Codes For Input Restricted Partial Response Channels."

[C] U.S. Pat. No. 5,280,489, granted Jan. 18, 1994, entitled "Time-Varying Viterbi Detector For Control Of Error Event Length."

[D] U.S. Pat. No. 5,327,440, granted Jul. 05, 1994, entitled "Systolic Architecture For Viterbi Detection Of DC-Free Sequences."

[E] Commonly assigned U.S. application Ser. No. 08/174,904, (Docket SA9-93-023), filed Dec. 24, 1993, entitled "Permuted Trellis Codes For Input Restricted Partial Response Channels."

[F] Commonly assigned U.S. application Ser. No. 08/242,942, (Docket SA9-94-012), filed May 16, 1994, entitled "Trellis Codes With Algebraic Constraints For Input Restricted Partial Response Channels."

Partial response channels of interest for data storage devices include those with channel polynomials of the form P(D)=(1-D.sup.n) or (1+D.sup.n), where n is a nonnegative integer. Channels with this form have a practical implementation advantage in that they can be de-interleaved into n separate (1-D) channels or n separate (1+D) channels, respectively. In Reference [A], coding and detection are accomplished by n-way interleaving of appropriate codes for the dicode channel, with polynomial (1-D), or n-way interleaving of appropriate codes for the so-called class-I partial-response channel, with polynomial (1+D).

Reference [A] discloses a method for increasing the reliability of partial response storage channels by increasing the minimum distance between coded output sequences using codes designed to match the spectral nulls in a channel partial response polynomial. The Viterbi detectors in Reference [A] reduce complexity by tracking only the spectral content of detected sequences.

The "minimum distance" of a particular detector trellis (sometimes referred to in the art as d.sup.2.sub.free) is defined as the minimum sum of the squared differences between sequences of noiseless sample values resulting from two distinct paths that diverge from a common state on the trellis and remerge to a common state. For partial response, maximum likelihood (PRML) detection, the minimum distance is 2; but the first-order matched-spectral null codes of Reference [A] increase the minimum distance to 4. In order to realize the benefits of increased minimum distance in a Viterbi detector with finite path memory, it is required that any pair of sequences consisting of a coded sequence and another detector trellis sequence accumulate the distance within a finite number of samples. If the code contains "quasicatastrophic" sequences, which are defined as sequences that are represented by more than one distinct path through the detector trellis, the minimum distance will not be accumulated in a finite number of samples, so it is necessary for the code to avoid such sequences. Reference [A] describes a method for eliminating quasicatastrophic sequences. However, in practice, reducing the required path memory to an appropriate length forces the encoder/decoder to become unacceptably complex.

Reference [B] describes a Viterbi detector which replicates a conventional trellis pattern for the desired channel N times. The N copies of the channel response trellis are interconnected in such a way that a preselected function associates each state in the trellis with a particular integer value modulo N. The number N is selected according to the channel detection and coding constraints so that diverging erroneous sequences of minimum distance lead to detector states which are distinct from the correct detector state. Only certain values of the preselected function tracked modulo N are allowed every m bits in order to increase the minimum distance between output sequences in the partial response channel and eliminate quasicatastrophic sequences. The codes described in Reference [B] do not match the spectral nulls in the polynomial for the channel.

Reference [C] describes a Viterbi detector based upon a time-varying trellis structure for detection of codes with spectral nulls or spectral-density nulls. The time-varying structure provides for reduced error-event length by eliminating paths corresponding to certain quasi-catastrophic sequences. The trellis is obtained by selective deletion of states and edges from the trellis that tracks the spectral content of the output sequences. However, while this selective deletion eliminates duplicate paths generating quasicatastrophic sequences, it also eliminates many paths generating sequences that might have been acceptable codewords and thereby reduces the achievable rate of codes supported by the modified trellis. Therefore, in order to maintain the desired high code rates, it was necessary to significantly increase the codeword block length or the number of trellis states, resulting in larger code and detector complexity.

Reference [D] describes sequences that are concatenated according to rules that depend upon the running digital sum (RDS) value of a sequence and that of its successor. The detector trellis structure combines subtrellises that track RDS or RDS modulo N, with reassignment of survivor metrics and survivor sequences at the subtrellis boundaries according to the sequence concatenation rules. The resulting detector trellis structure requires periodic permutation of states and hence is referred to as a "permuted" trellis code. The sequences and the concatenation rules are selected to realize coding gain, eliminate quasi-catastrophic sequences from the detector trellis, limit the complexity of the maximum-likelihood detector, and improve runlength constraints relative to earlier proposed methods.

Reference [E] describes sequences that satisfy an algebraic constraint on a predetermined algebraic attribute which identifies output sequences that differ from each other by a preselected error event. The detector tracks the algebraic attribute by iteratively computing from the symbols sequentially output from the detector trellis the value of the algebraic attribute at the end of each codeword. Violations of the algebraic constraint are flagged to detect the occurrence of the preselected error event. Allowable channel input sequences are constrained so that they will assume only a single value periodically in time. The detector trellis is made time-varying by removing from the trellis all output sequences that fail to satisfy the preselected algebraic constraint, thereby correcting said error event. The trellis is constructed to incorporate the current state of the partial response channel memory, the current state of the algebraic attribute, and, in an inner-coded system, the state of the inner code.

Reference [F] describes a systolic Viterbi detector trellis structure for MSN-coded and uncoded PRML channels. The architecture eliminates redundant detector calculations and incorporates modified butterfly trellis geometries and rotates state-metric assignments by one for simplifying the detector apparatus.

None of these references suggests (1) providing an encoder for a spectral-null code that partitions the set of sequences that are quasicatastrophic in a running-digital-sum (RDS) time-varying trellis structure by constraining codewords generated from an initial RDS value to assume prescribed subsets of allowable RDS values at both the codeword end and at least one prespecified interior location in the codeword; (2) providing a time-varying detector with a partitioned trellis structure which reflects the constraint on the encoded sequences by replicating certain states and edges in order to effect partitioning of the quasicatastrophic sequences; and (3) providing high rate MSN codes which further reduce the maximum length of error events at minimum distance and next-minimum distance, while retaining the beneficial features of the codes described in the above cited references.

An apparatus and method are described for improving reliability of a data storage device that transmits binary data as codewords over a partial response channel. A modified encoder constructs from the binary data a spectral-null trellis code that constrains the codewords generated from an initial RDS value to assume prescribed subsets of allowable RDS values at both the codeword boundary and a prespecified interior location of the codeword. This partitions certain sets of sequences with specified RDS values among the initial RDS values.

A modified Viterbi detector generates a most probable binary output sequence from codewords received by the channel. The detector uses a trellis structure that reflects the partitioning constraints imposed by the encoder, replicating specified states and edges in a periodic, time-varying manner. The constraints on the RDS within the codeword guarantees distance accumulation properties that favorably impact the truncation depths of the code; that is, the number of steps in the trellis beyond which any pair of sequences generated by diverging trellis paths accumulate a prescribed distance, such as the minimum or next-minimum distance.

The function of the detector using the partitioned trellis preferably is implemented by combining a "vertically compressed" systolic RDS trellis structure with auxiliary trellis structures for determining the most probably survivor sequences for specific states at the preselected interior location in the RDS trellis structure.

FIG. 1 is a block diagram of a data storage system embodying the invention comprising a modified encoder, a partial response channel, a modified Viterbi detector, and a decoder;

FIG. 2 depicts a configuration of concatenated subsets of length-5 binary sequences with specified running-digital-sum (RDS) values, yielding 275 length-10 sequences outgoing from each of two initial RDS values and representing candidate codewords for a rate 8/10 code;

FIG. 3 depicts a modified configuration of concatenated subsets of length-5 binary sequences with specified RDS values, yielding the 256 codewords consisting of length-10 sequences outgoing from each of two initial RDS values for a specific rate 8/10 code;

FIG. 4 depicts a partitioned systolic trellis structure corresponding to the concatenation configuration of FIG. 2;

FIG. 5 depicts a "vertically compressed" systolic RDS trellis structure that is used in conjunction with auxiliary trellis structures to implement the modified architecture for the partitioned trellis structure of FIG. 4;

FIG. 6 depicts one of the auxiliary trellis structures used in the modified architecture to compute survivor paths and metrics for states 2.sub.1 and -2.sub.0 at time 5 modulo 10 in the trellis structure of FIG. 5;

FIG. 7 depicts the final four stages of the auxiliary trellis structure of FIG. 6;

FIG. 8 is a two-dimensional depiction of the 256 data bytes x,y with first four coordinates x broken into subsets X.sub.j,j=0,1, . . . , 4 of Hamming weights j=0,1, . . . , 4 and second four coordinates y broken into subsets Y.sub.j,j=0,1, . . . , 4 of Hamming weights j=0,1, . . . , 4;

FIG. 9 shows a grid of data bytes subdivided into regions F.sub.1,F.sub.2,F.sub.3,F.sub.4 ;

FIG. 10 is a depiction of the mapping of data byte regions G,H,I,J,K onto 80 allowable sequences in the set A.sub.1 A.sub.1 ;

FIG. 11 is a schematic of the logic equations for the Hamming weight indicator functions used in the encoder and decoder;

FIG. 12 depicts the trellis structure of FIG. 5 with states assigned to physical Add-Compare-Select (ACS) units according to a cyclic rotate-by-three rule;

FIG. 13 is a schematic diagram showing interconnections of the ACS units specified by the state-to-ACS assignments of FIG. 12;

FIG. 14 is a schematic diagram showing how an auxiliary survivor computation is performed using the auxiliary trellis structure of FIG. 6;

FIG. 15 is a schematic diagram showing a modified register exchange technique for a local Survivor Memory Unit (SMU);

FIG. 16 is a schematic diagram of a local SMU incorporating one traceback method with 3-bit ancestor state representation;

FIG. 17 depicts the vertically compressed trellis structure of FIG. 5 with even and odd stages indicated, along with 3-bit state identifiers;

FIG. 18 is a schematic diagram of a local SMU incorporating an alternative traceback method with 1-bit "differential" state identifiers and an even-odd phase identifier; and

FIG. 19 is a schematic diagram of a global SMU incorporating a codeword-length traceback method for generating maximum likelihood codeword estimates.

A new class of matched spectral null (MSN) trellis codes, with "partitioned" trellis structures is disclosed. Two rate 8/10 MSN partitioned codes are described that have the smallest truncation depths (for minimum and next-minimum distance) of existing rate 4/5, 8/10, or 16/20 trellis codes for Class-4 partial response. Unlike previously proposed codes, these new codes, as earlier noted, constrain the codewords generated from an initial RDS value to assume prescribed subsets of allowable RDS values at both the codeword boundary and at least one prespecified interior location of the codeword. The added constraint on the RDS within the codeword guarantees distance properties that favorably impact the truncation depths. The choice of the interior position at which the RDS constraint is enforced provides a tradeoff between code constraints and detector trellis complexity. In addition, the added constraint allows use of a simple two-state encoder and a block decoder that eliminates error propagation.

The detectors for the MSN codes here described are based upon a novel, reduced-complexity, time-varying "partitioned" systolic trellis structure which differs significantly from the time-varying trellis structures described in the cited prior art. In essence, the RDS constraints imposed by the code partition the quasicatastrophic sequences (i.e., sequences which can be generated in the canonical trellis from more than one initial RDS state) into disjoint subsets, and assign each subset to an initial RDS state. The partitioned trellis structure reflects this assignment.

Use of auxiliary trellises to determine the survivor sequences for specific internal states in the time-varying detector structure permits portions of the partitioned trellis of a rate 8/10 code to be vertically compressed to form a six-state structure that is contained in the systolic trellis of the rate 8/10 MSN code disclosed in Reference [A]. One of the rate 8/10 codes herein described even admits a six-state modified detector that achieves true maximum-likelihood performance. In contrast, a straightforward implementation of the partitioned detector trellis would almost double the required number of trellis states (and therefore of Add-Compare-Select (ACS) units) relative to the six-state systolic structure of the rate 8/10 MSN code described in Reference [F] and would require some four-input comparators.

As depicted in FIG. 1, input data, such as in the form of binary symbol strings, is transmitted from a bus 10 to an encoder 11. Encoder 11 comprises means to generate, from a unique initial RDS value, binary codewords constrained to assume prescribed subsets of RDS values at the end of each codeword and also at a prespecified location within each codeword. Each codeword serves as input to a partial response channel 12 with a system polynomial P(D) representing the channel memory. A channel output sequence is generated by partial response channel 12, corrupted by noise, and detected at the channel output by a modified Viterbi detector 13 for implementing the invention. Detector 13 calculates and estimates, from the channel output sequence, the most probable coded sequence. A decoder 14 uses this estimate, as calculated by detector 13, to recover the original input data and output it to a bus 15. Trellis codes and corresponding Viterbi detectors are disclosed for use with partial response channels having characteristic polynomials of the form P(D)=1.+-.D.sup.n. The encoder 11 and detector 13 are made time-varying, as taught in References [B], [C], [D] and [E].

According to a feature of the invention, and as indicated in FIG. 1, detector 13 comprises a conventional branch metric circuit 16, add-compare-select (ACS) units 17 with a modified interconnection configuration, and a survivor metric unit (SMU) 18 which includes a local SMU subunit (LSMU) 19 and a global SMU subunit (GSMU) 20 (each hereinafter more fully described). Detector 13 has a partitioned systolic trellis structure that divides into disjoint subsets those sequences that are quasicatastrophic with respect to a conventional or a time-varying RDS trellis structure, as in References [A] or [C], respectively. Detector 13 assigns each subset to a unique initial RDS state that renders said sequences noncatastrophic and thus available for use by the partitioned code.

In the preferred rate 8/10 codes constructed in accordance with the invention, two 5-bit subsequences are concatenated to form each 10-bit codeword. The configuration of concatenated subsets is depicted in FIG. 2. The nodes represent charge states and the edges represent sets of 5-tuples with a given accumulated charge. Binary 0 and 1 are assumed to represent -1 and +1 charges, respectively. Thus, for example, the edge labelled A.sub.1 represents the subset of all 5-bit sequences that accumulate a charge of +1 and connect charge state -1 to state 0.

The subsets A.sub..+-.1 and A.sub..+-.3 are easily determined by enumerating the 32 possible combinations of 5 bits and computing the accumulated charge. These subsets (converted to decimal numbers) are:

The paths of length 10 from state -1 to -1 and -1 to +1 represent concatenation of subsets of 5-bit sequences. For example, concatenation of 5-bit sequences from subset A.sub.1 with those from the subset A.sub.-1 results in a net accumulated charge of 0. Thus, as shown, the charge states remain unchanged at the beginning and end of the concatenated sequences, and these paths terminate in state -1. Likewise, concatenation of sequences from subset A.sub.3 with those from A.sub.-1 produces sequences that accumulate a charge of +2. These sequences start from state -1 and end in state +1.

These paths of length 10 define the available codewords for state -1, denoted S(-1), which are compactly represented in terms of the subsets A.sub..+-.1 and A.sub..+-.3 as follows:

Likewise, the codewords for state +1, denoted S(+1), are:

According to a feature of the invention, the set S(+1) of codewords emanating from state +1 in FIG. 2 does not contain the sequences of length 10 represented by A.sub.1 A.sub.-3 or A.sub.1 A.sub.-1, (indicated by the dash line labeled A.sub.1). Similarly, the set S(-1) of codewords emanating from state -1 in FIG. 2 does not contain the sequences of length 10 represented by A.sub.-1 A.sub.1 or A.sub.-1 A.sub.3 (also indicated by a dash line labeled A.sub.-1). Consequently, set S(+1) does not intersect the set S(-1) of codewords emanating from state -1. Also, the codewords from state +1 are the bit-wise complements of those from state -1. If the data-to-codeword assignment is chosen in such a way that an input data byte b assigned to a codeword c in set S(+1) is also assigned to the complementary codeword c in S(-1), the code will have 180-degree phase invariance.

Based on the number of elements in each subset A.sub.1,A.sub.-1,A.sub.3,A.sub.-3 and the definition of the sets S(+1) and S(-1), it is easily verified that there are 275 candidate codewords for each of the two originating states. A rate 8/10 code requires only 256 codewords. The extra codewords can be eliminated, for example, to satisfy requirements related to the k-constraint or to the minimum number of non-zero samples per codeword.

Table 1, and all other tables, are set forth in an APPENDIX hereto, which is made part hereof. As shown on Table 1, by removing a particular subset of 12 codewords a set of 263 codewords is retained that can be used to define a code with maximum output zero runlength k=4 within codewords and k=5 at the codeword boundaries; i.e., at the beginning and end of the codeword. The code thus defined has at least three non-zero samples per codeword, a feature useful for assuring sufficient frequency of timing and gain updates for decision-directed control loops. Only 36 codewords do not contain a sequence of the form "010" or "101", which forms are particularly beneficial for timing recovery. Of these, 26 are highly likely to generate such a sequence at the codeword boundary. Eliminating seven of the remaining 10 words to produce 256 codewords yields a code that is less susceptible to errors in timing recovery.

If preferred, a different subset of 256 codewords can be selected from the original 275 to generate a code whose codewords are precisely those generated by the partitioned trellis structure obtained from FIG. 4 by deleting all edges and leaving states -2.sub.0 and +2.sub.1. This allows maximum-likelihood detection with moderate complexity, but it does not provide flexibility in choosing codewords that will achieve desirable timing recovery constraints. FIG. 3 shows the configuration of concatenated subsets for such a code. The sets B.sub..+-.1 and B.sub..+-.3 referred to in FIG. 3 are subsets of A.sub..+-.1 and A.sub..+-.3, respectively, and (converted to decimal numbers) are defined as:

Given the number of elements in each set, it is easily shown that there are exactly 256 codewords from each originating state in FIG. 3. The code parameters related to timing/gain recovery constitute to an MSN code with k=5 and at least two non-zero samples per byte.

The codes defined by FIGS. 2 and 3 and constructed in accordance with the invention provide reduced truncation depths, improved block decoder structure, and superior error-rate performance. "Truncation depth", as earlier defined, is the length beyond which any code output sequence achieves the specified distance from any other sequence supported by the trellis structure. The truncation depth for minimum distance 4 and next-minimum distance 6 is reduced by more than 50% and near-maximum-likelihood performance (or true maximum-likelihood performance, in the configuration depicted in FIG. 3) is achieved with the modified Viterbi detector 13, hereinafter to be described.

In the following description of an RDS systolic trellis structure, such as described in Reference [F], the trellis states are designated as V.sub.m, where V is an RDS value and m denotes the (1-D) dicode channel memory. The V will be an odd integer value at even times or stages of the trellis and an even integer value at odd times or stages of the trellis.

To avoid quasicatastrophic sequences in the codes herein described, the RDS systolic detector structure taught by the prior art is modified to create a time-varying partitioned trellis structure of period 10 that not only supports all of the coded channel output sequences, but also generates each with a unique trellis path. The code will then have no sequences that are quasicatastrophic with respect to the modified trellis structure. As a result, the maximum length .eta.(4) of minimum distance 4 error events and the maximum length .eta.(6) of next-minimum distance 6 error events desirably are reduced to:

Moreover, the corresponding truncation depths, .tau.(4) and .tau.(6) satisfy the same bounds:

These bounds are significantly less than those of the trellis codes disclosed in the cited references. These reduced bounds result from the use of the code concatenation configuration disclosed in FIG. 2 or FIG. 3 with the partitioned trellis structure of FIG. 4 or preferably the vertically compressed partitioned trellis structure of FIGS. 5 and 6.

For sake of illustration, the following description will explain how the invention is implemented with the rate 8/10 code configuration depicted in FIGS. 2 and 4.

The modified detector trellis structure, depicted in FIG. 4, reflects the inherent partitioning of the RDS charge states at the middle of the codeword, as well as the RDS constraints at the codeword boundaries. As a result of the partitioning, codewords from state -1 pass through only charge states 0 and +2 after five bits, and codewords from state +1 pass through only charge states 0 and -2 after five bits.

As shown in FIG. 4, each beginning and ending state shown in FIG. 2 is split into two states to reflect the channel memory of the dicode channel. Thus, the three possible states in the middle of the codeword become six states.

If the Viterbi algorithm is applied to the partitioned trellis structure depicted in FIG. 4, there are two potential drawbacks from the standpoint of circuit complexity and throughput rate. First, at certain instants, as many as 10 add-compare-select (ACS) units may be needed to operate in parallel. Second, at certain states at time 5 (modulo 10), a four-way comparison will be required, rather than the conventional two-way comparison.

More specifically, the partitioned trellis structure can best be visualized as a "Y" turned 90.degree. counterclockwise and having angled trellis portions N and P that join the same trellis portion Q. Referring to FIG. 4, at time 5, the trellis states 0.sub.1, 0.sub.0, +2.sub.1, and +2.sub.0 of portion N are commoned with these same trellis states in the portion Q; and at time 5, the trellis states -2.sub.1, -2.sub.0, 0.sub.1, and 0.sub.0 of portion P are commoned with these same trellis states in portion Q.

In the partitioned trellis structure, the survivor sequence at state -2.sub.1, at time 5 is now forced to come from a code string in the set A.sub.-3, along a path originating from state 1.sub.1 or 1.sub.0. The only 5-bit code sequence satisfying this condition is 00001, and the two corresponding trellis paths comprise the path from state 1.sub.1 with outputs -10001, and the path from state 1.sub.0 with outputs 00001.

In the partitioned trellis structure, the survivor sequence at state -2.sub.0 at time 5 is also now forced to come from a 5-bit code sequence in the set A.sub.-3 along a path originating from state 1.sub.1 or 1.sub.0. There are only four such code strings:

with corresponding trellis sequences:

where, for convenience, the two output samples in the braces correspond to the labels on the first edge of the paths from state 1.sub.1 and 1.sub.0, respectively.

In a complementary manner, the survivor sequence at state 2.sub.0 at time 5 must come from the code bit sequence 1 1 1 1 0, corresponding to the paths from states -1.sub.1 and -1.sub.0 that generate output samples 0 0 0 0 -1 and 1 0 0 0 -1, respectively.

Similarly, the partitioned trellis forces the survivor sequence at state 2.sub.1 at time 5 to come from a 5-bit code sequence in the set A.sub.3 along a path originating from state -1.sub.1 or -1.sub.0. There are again only four such code strings:

with corresponding trellis sequences:

where the two output samples in the braces correspond to the labels on the first edge of the path from states -1.sub.1 and -1.sub.0, respectively.

According to the invention, these drawbacks are resolved by performing a recursive auxiliary calculation during times 1 to 5 (modulo 10) using the auxiliary trellis depicted in FIG. 6 in combination with a state-metric transfer at time 5 (modulo 10) to a "vertically compressed" or "flattened" portion of the partitioned trellis structure, as depicted in FIG. 5, for simplifying implementation of the algorithm by the Viterbi detector 13. More specifically, the portions N and P in FIG. 4, while still commoned to portion Q, are vertically compressed, after deleting the edges in FIG. 4 designated with an X, to provide the resultant trellis structure depicted in FIG. 5. The auxiliary trellis shown in FIG. 6 and its complement reflect the paths and sequences of FIG. 4 that are eliminated by deletion of the edges X that were part of the partitioned structure prior to its vertical compression.

In the vertically compressed six-state trellis structure, the conventional Viterbi algorithm is applied to determine the survivor sequences and metrics at all states and all times, except the survivor sequences and metrics for the states -3.sub.0 and 3.sub.1 at time 4, and for states -2.sub.1 and 2.sub.0 at time 5.

At time 4 (modulo 10), the survivor sequence for state -3.sub.0 is the concatenation of the survivor sequence for state 0.sub.0 at time 1 with the sequence 0 0 0 appended. The survivor metric is set to the survivor metric for state 0.sub.0 at time 1. Note that the intermediate branch metrics are all zero in the systolic trellis structure.

The computation of the survivor sequence and metric for state -2.sub.0 at time 5 is determined from the auxiliary trellis shown in FIG. 6. In FIG. 6 the survivor metrics at time 0 for states 1.sub.1 and 1.sub.0 are denoted by X and Y, respectively. The survivor extensions for time 1 are computed, in the manner described in Reference [A], using ACS units available in the vertically compressed trellis structure shown in FIG. 5. The remaining computation is governed by the final four stages of the auxiliary trellis structure, which are shown in FIG. 7. In FIG. 7, the survivor metrics for states 0.sub.0 and 2.sub.1 at time 1 are denoted by X'and Y', respectively. The resulting survivor metric at time 5 is described by the expression:

where the symbols b.sub.i.sup.+ and b.sub.i.sup.- denote the branch metrics at time i corresponding to an edge labelled with a symbol +1 or a symbol -1, respectively. This can be written as:

where

Using the following scaled definitions of the conventional "linearized" branch metrics:

and

where y.sub.i denotes the received sample at time i, the metric calculation can be written as:

The implementation of this minimization is simplified by rewriting it in the form:

Note that the following features contribute to a simplified architecture for the calculation:

1. Y" is available directly from a register (not shown) whose contents are provided by the vertically compressed partitioned trellis structure of FIG. 5.

2. X'+1 is a fixed increment on X', and can be hardwired, avoiding the need for an additional adder. If preferred, the X' term could be used independently, and the increment by 1 could be incorporated into the minimization

3. This internal minimization can be performed recursively using a 6-bit adder and a 7-bit compare-select (CS) circuit.

4. The final minimization can be performed with an available ACS unit, in a fashion similar to the one used at time 1. Note that four ACS units from the six-state trellis are available at time 5.

The survivor computations for the complementary states, 3.sub.1 at time 4 and 2.sub.1 at time 5, are complementary to the preceding computations. In particular, the minimization for state 2.sub.1 at time 5 can be expressed in the form:

where the quantities T, S", and R' are the obvious counterparts of Z, Y", and X', discussed in connection with FIG. 7.

The auxiliary trellis computations for the complementary pairs of states can be executed as follows:

a) Determine min, max {y.sub.3 -y.sub.2, y.sub.4 -y.sub.3, y.sub.5 -y.sub.4 } recursively.

b) Store the quantities (X'+1), Y", (R'+1,), S" in registers. (The added terms 1 and -1 can be lumped into step a if desired.)

c) Perform the final minimization at time 5 using ACS units available from the six-state trellis of FIG. 5.

Boolean logic implements the encoding and decoding functions for the rate 8/10 partitioned MSN codes. The concatenated structure underlying the code sequences shown in FIG. 2 is exploited to derive a "two-dimensional" data-to-codeword assignment that allows a simple encoder and decoder implementation.

Code sequences are denoted by w=uv, where u=u.sub.1, . . . , u.sub.5 and v=v.sub.1, . . . , v.sub.5 are the first and last 5-bit subsequences of w.

FIG. 2 constrains the allowable code sequences in such a way that u and v must come from prescribed combinations of the subsets A.sub..+-.1 and A.sub..+-.3. These subsets contain the sequences with accumulated charge indicated by the subscript. There is another, equivalent characterization of the sequences in each of the subsets; namely, in terms of their Hamming weight (i.e., the number of 1's in the sequence). Specifically, the sequences in subset A.sub.k are precisely those 5-tuples with Hamming weight j, where ##EQU1## The notations U.sub.j and V.sub.j denote the 5-tuples of weight j from which u and v are drawn.

Data sequences are denoted by z=xy, where x=x.sub.1, . . . , x.sub.4 and y=y.sub.1, . . . , y.sub.4 are the first and last 4-bit sequences of z. The notations X.sub.j and Y.sub.j denote the 4-tuples of weight j from which x and y are drawn. Note that the number of elements in each of the sets X.sub.j and Y.sub.j is precisely ().

FIG. 8 is a two-dimensional depiction of the 256 data bytes x,y, with the coordinate x broken into the sets X.sub.j, j=0, 1, . . . , 4 and the coordinate y broken into the sets Y.sub.j, j=0, 1, . . . , 4. The set of data bytes can be decomposed into subsets of the form X.sub.i Y.sub.j, corresponding to the rectangular regions shown in FIG. 8.

The data-to-codeword assignment for state -1 makes use of the two-dimensional decomposition based upon Hamming weight. For 97% of the data bytes, the encoder mapping is defined by a pair of simple mappings, each defining one of the individual coordinates u and v in terms of one of the coordinates x or v.

FIG. 9 shows a grid of data bytes subdivided into regions F.sub.1, F.sub.2, F.sub.3, F.sub.4. The four regions are first mapped into the four groups of allowable code sequences described by A.sub.1 A.sub.-1 ; A.sub.3 A.sub.-1 ; A.sub.3 A.sub.-3 ; A.sub.1 A.sub.1 ; or, in terms of Hamming weight sets, U.sub.3 V.sub.2 ; U.sub.4 V.sub.2 ; U.sub.4 V.sub.1 ; U.sub.3 V.sub.3. These mappings are simple in structure, as will now be shown.

Regions F.sub.1, F.sub.2, F.sub.3 are defined by

The mapping of these regions is determined by four coordinate maps, denoted .alpha., .beta., .gamma., .delta., defined as follows: ##EQU2##

Referring now to FIGS. 9 and 10, mapping of region F.sub.4 is somewhat more complicated, and is defined on the following subregions:

The map on subregion G is determined by the map .alpha. above, as well as the map

in which

where data 4-tuples and code 5-tuples are represented in decimal.

The map on subregion H is determined by the map .mu..sub.1 above and the rule:

Similarly, the map on subregion I is determined by the map

where

and the rule:

where 4-tuples and code 5-tuples are again represented in decimal.

The map on subregion J is determined by the map

where ##EQU3## and the rule:

Finally, the map on subregion K is determined by the map .alpha. above and the rule:

The functions defined above map the 255 data bytes (256 minus the data byte in subregion L) into a subset of the 275 possible sequences in FIG. 2, including all 175 of the sequences in A.sub.1 A.sub.-1, A.sub.3 A.sub.-1, A.sub.3 A.sub.-3, and 80 of the 100 sequences in A.sub.1 A.sub.1. As noted above, 12 codewords in the former three sets must be excluded in order to achieve the desired runlength and non-zero-sample constraints and to simplify the detector trellis structure, leaving 263 candidate codewords. These 12 excluded codewords, along with the data bytes mapped to them, as earlier stated, are set forth in Table 1.

To define the code for this implementation, seven more codewords must be eliminated. The sequences thus eliminated and the data bytes that map to them are set forth in Table 2.

There are a total of 13 "exceptional" data bytes that must be remapped to avoid generation of code sequences that have been eliminated from A.sub.1 A.sub.-1, A.sub.3 A.sub.-1, and A.sub.3 A.sub.-3. Note that the mapping defined above on regions G, H, I, J, K does not generate any of the eliminated sequences in A.sub.1 A.sub.1. They "hit" the 80 allowable sequences in A.sub.1 A.sub.1, where, as shown in FIG. 10, the set A.sub.1 A.sub.1 is depicted by a two-dimensional grid.

The 13 exceptional data bytes, and the byte (0,15) comprising region L, are then mapped to the remaining 14 valid code sequences in the top and bottom rows of the grid. The mapping is simplified by breaking the set of 14 data bytes into two subsets denoted E.sub.1 and E.sub.2, where:

and

The bytes in E.sub.1 are mapped to the valid code sequences with v=7, and the bytes in E.sub.2 are mapped to the valid code sequences with v=28.

The logic implementing these mappings is set forth in Table 3. The logic for the next state function t when the encoder is in state -1 is:

When the encoder is in state +1, the data-to-codeword mapping and the next state function are obtained by bit-wise complementing the corresponding functions defined above for state -1.

Table 4 sets forth the decoder logic. This is simpler than the encoder logic, because the decoder mapping is determined only on 10-bit words that are in the image of the encoder. This provides flexibility in the logic design.

Both the encoder logic and decoder logic make use of Hamming weight indicator functions, which, for simplification, are represented by the same symbols as the subsets with fixed Hamming Weights used in the two-dimensional descriptions of codewords and data bytes. These functions can be implemented in several possible ways. For example, consider the indicator functions X.sub.0, X.sub.1, X.sub.2, X.sub.3, X.sub.4, where ##EQU4## Logic equations for these functions are set forth in Table 5.

Table 6 lists the noncode trellis sequences for the preferred code implemented by the encoder logic of Table 3 and the partitioned trellis defined by FIG. 4 or by FIGS. 5 and 6. These are the 10-symbol codewords supported by the trellis which do not belong to the code. Table 7 sets forth Boolean logic for a flag variable that can be used to identify detector outputs that are invalid. This flag may be used to provide erasure information for the error recovery procedure used in the data storage system depicted in FIG. 1.

It will be understood that, if preferred, other methods known to those skilled in the art can be used to implement the logical functions of encoder 11 and decoder 14, such as a ROM-based lookup table approach or a lexicographical coding approach.

As illustrated in FIG. 11, the encoder 11 and decoder 14 defined by Tables 3 and 4 comprise a plurality of two-input AND gates 30 and two-input OR gates 32, which implement the logic functions set forth in Table 5. Excluding the Hamming weight indicator functions, which add a total of approximately 50 gates 30,32, depending on the implementation, there are 307 for the encoder 11 and 235 for the decoder 14.

As earlier noted, the Viterbi detector 13 comprises branch metric circuits 16, ACS units 17, and an SMU 18 comprising a local SMU subunit (LSMU) 19 and a global SMU subunit (GSMU) 20.

The branch metric circuitry 16 may be identical with that disclosed in Reference [F] and hence will not be specifically described herein.

The six-state systolic trellis structure for the partitioned MSN code(s) requires six ACS units 17. To render the ACS topology and branch metric connections "time invariant", the six ACS units are interconnected so as to cyclically rotate assignment of each of the six output states by a preselected integer n. Applicants determined that this integer n for a particular code should be equal to the quotient obtained by dividing the number of RDS states by a number that is divisible into the codeword length. Thus, for a rate 8/10 code with six states and a 10-bit codeword length, the assignment should be cyclically rotated by 3 because 6/3=2, which is divisible into 10.

Referring now to FIG. 12, the trellis states at each stage are numbered 1, 2, 3, 4, 5, and 6 (top-to-bottom), and the ACS units 17 are denoted by A, B, C, D, E, and F. FIG. 12 describes the preferred cyclical, rotate-by-three assignment of output states. This assignment preserves the branch metric inputs at each ACS unit 17.

When applied to the six-state systolic RDS trellis, and as hereinafter more fully described, this rotate-by-three assignment eliminates the need for input multiplexers (MUXs) except when computing metrics for states 1 and 6. In effect, the survivor metrics for a given state are computed alternately by a pair of ACS units 17; e.g., the survivor metric for state 1 is generated alternately by ACS units A and D. Edge labels 0, +1, and -1 are denoted by blank, +, and -, respectively.

The time-variation of the vertically compressed trellis is preferably implemented by means of an ACS-override feature, controllable by programmable bits, which can force a predetermined decision and corresponding update to the survivor metric and survivor path.

FIG. 13 illustrates an apparatus, including six interconnected ACS units 17A-E, for achieving the rotate-by-three assignment of output states. This apparatus comprises six one-cycle delay units 40a-f, four three-cycle delay units 42a,b,e,f, six compare select units (C/S) 44a-f, six MUXs 46a-f, and six adders 48a-f. Delay units 40a,42a and 40f,42f at the output of ACS units A and F, in combination with MUXs 46a and 46f at the inputs of ACS units D and C perform an auxiliary trellis computation. This computation is required for states 1 and 6 at time 4 modulo 10. It is combined with the branch metric supplied to adders 48d,c when MUXs 46a,f are triggered by a signal on line 49 at time 5 modulo 10 to provide the correct survivor metrics for states 1 and 6 at time 5 modulo 10. In addition, delay units 40a-f and three-cycle delay units 42a,b,e,f, together with MUXs 46b,c,d,e and branch metric MUXs 47a,b applied to adders 48a,e perform another auxiliary trellis computation that is required for states 2 and 5 at time 5 modulo 10. MUXs 46b,c,d,e and MUXs 47a,b are also triggered by a signal on line 49 at time 5 modulo 10.

FIG. 14 illustrates a circuit that may be used to execute simultaneously the maximization and minimization required for the complementary auxiliary survivor metric computation; namely:

and

Delay unit 50a and subtractor 52 generate quantities y.sub.n -y.sub.n-1, at successive instants. At each instant, the quantity y.sub.n -y.sub.n-1 is supplied to compare units 54a and 54b. Delay units 50b and 50c additionally supply the minimum and maximum, respectively, of the previously computed differences y.sub.j -y.sub.j-1 to the compare units 54a and 54b, respectively. Selector units 56a and 56b then generate the minimum and maximum, respectively, of the quantities supplied to compare units 54a and 54b, respectively. The new minimum and maximum, respectively, are then fed back via delay units 50b and 50c, respectively. The recursively computed minimum and maximum quantities are supplied to registers 58a and 58b for use in the auxiliary trellis computation.

An SMU of 30-bits depth achieves virtually all of the available coding gain for the partitioned code. The SMU 18 is preferably organized as the local and global subunits LSMU 19 and GSMU 20, respectively (FIG. 1). The LSMU 19 processes the most recent 10-bit codeword, while the GSMU 20 accommodates the preceding 20 bits.

The LSMU 19 stores survivor information based on the most recently received samples for the six states in the RDS trellis structure over a period of 10 bits. LSMU 19 can be organized using variations of one of the following methods:

1) Modified Register Exchange

If the register exchange method is used, registers and multiplexers are suitably interconnected to reflect the interconnection of the detector trellis. Auxiliary trellis survivor sequences are mapped into the appropriate registers in the LSMU at times 5 modulo 10. A key feature of the method is that the survivor sequences are directly stored in the LSMU; no subsequent decoding is required.

FIG. 15 shows circuitry for a modified register exchange implementation of LSMU which provides the substitution of auxiliary trellis survivor sequences at times 5 modulo 10 for states 2 and 5, as well as the substitutions for states 1 and 6 at time 5 modulo 10. The register labels A-F correspond to the ACS units assigned to the states 1-6 in the trellis, as in FIG. 12.

The systolic interconnections between the registers, as determined by the systolic trellis structure, are omitted for simplification. The auxiliary sequences are mapped into the local memory, depending on the ACS decisions at time 5 modulo 10 and the output of the logic units 60a and 60b for states 2 and 5, respectively.

2) Traceback Method

Use of the traceback method largely avoids the use of 1-bit registers and a multiplexer between each register, and reduces significantly the wiring and the interconnection requirements. Shift registers store the "ancestor" state information, which is subsequently decoded to derive the survivor sequences. The length of the shift register depends upon the traceback configuration used.

The following approaches may be employed to implement the traceback method in the LSMU:

(a) FIG. 16 illustrates an implementation using a 3-bit Ancestor State Representation. LSMU 19 stores the most recent ancestor state information in six last-in-first-out (LIFO) 30-bit shift registers 70a-f based on the updated outputs from the ACS units 17. Since there are six possible intermediate states, a 3-bit word is required to identify the ancestor state uniquely at each time instant. At the end of ten most recent updates, the contents of the shift registers are used to traceback the survivor sequences for each of the four originating and terminating charge states in the partitioned code. In addition to the six 30-bit shift registers 70a-f needed to store the ancestor state information, four six-way multiplexers 72b-e and four decoding logic units 74b-e, corresponding to the four terminating charge states and their ACS units B-E are required. Use of a 30-bit buffer can be avoided by using the LIFO arrangement in the shift registers.

(b) In the trellis for the partitioned code shown in FIG. 17, the time instants are identified by "e"(even) and "o"(odd) labels. Note that the ancestor for a given state comes from either the same state, or one below or above it. If the identity of the "above" and the "below" states is ignored for the present, it will be noted that one bit of information is required to identify the ancestor state. Thus, a "0" may represent the case where the ancestor state and the current state are the same, and a "1" may represent the case where the ancestor state differs from the current state. The ambiguity associated with the "different" state is easily resolved by the time instant labels. For example, examine the state labelled 011. During "e" time instants, the "different" state is always the one above 011; and during the "o" instants, it is the opposite. Similarly, for the other states. Thus, instead of using 3-bit state labels, only 1-bit labels are needed in the LSMU.

As illustrated in FIG. 18, only six 10-bit shift registers 80a-f are required to store the partial information about the ancestor states. The logic blocks 84b-e (which could also be implemented with a 16.times.4 lookup table) combine this information with an independently generated "phase identifier" signal p and the previous predecessor state s to identify the new predecessor state. The previous predecessor state information bit s and the 3-bit state identifier are supplied to decode blocks 86b-e which then generate a decoded bit to be stored in the codeword registers of the GSMU 20. As in the notation convention used in FIG. 18, the four MUXs 82b-e, predecessor state logic blocks 84b-e, and symbol decode logic blocks 86b-e have labels corresponding to the four terminating charge states with their ACS units B-E.

FIGS. 17 and 18 thus illustrate a 1-bit Ancestor State Representation, in which the size of LSMU 19 and buffering requirement can be significantly reduced by storing "differential" state information. Table 8 depicts the required state transitions for the approach illustrated in FIG. 18. The state labels are arbitrary and may be arranged to minimize the required logic.

The survivor sequences from LSMU 19 are loaded into GSMU 20. Since loading is performed on a 10-bit basis, GSMU 20 must necessarily make use of traceback method to generate the detected codewords.

FIG. 19 shows an apparatus for implementing the GSMU traceback function. Depth-four stacks of 10-bit survivor registers 92a,b,c contain the four survivor sequences of length 30 bits for states 2,3,4 and 5; with the most recent 10-bit survivor extensions supplied to stack 92a by LSMU 19.

A parallel set of stacks of 2-bit pointer registers 94a,b,c provide the traceback pointer information. The traceback proceeds as follows:

A trellis boundary state is selected arbitrarily, here taken to be state C. The 2-bit traceback pointer in the corresponding register in pointer stack 94a is supplied to MUX 96a. This pointer designates the predecessor trellis-boundary state for the initial state C. MUX 96a then selects from the predecessor state register in stack 94b the 2-bit pointer for that state and supplies it to MUX 96b. MUX 96b then selects, from the corresponding pointer register in stack 94c, the 2-bit pointer which, when supplied to MUX 96c, causes GSMU 20 to output the 10-bit sequence in the corresponding register in survivor sequence stack 92c as the next 10 bits of the maximum likelihood sequence estimate. This process is repeated after every 10 cycles of ACS operation when LSMU 19 has computed the 10-bit extensions of the survivor sequences and shifted them into the survivor register stack 92a.

While the invention has been described as implemented with the rate 8/10 code depicted in FIG. 2, it will be understood by those skilled in the art that the invention may also readily be implemented with the rate 8/10 code depicted in FIG. 3 by using a vertically compressed systolic trellis structure substantially like that shown in FIG. 5, but deleting from FIG. 5 all edges entering or leaving the states -2.sub.0 and +2.sub.1 at time 5.

It will also be understood that the candidate codewords of a partitioned trellis code may be defined by a configuration of concatenated subsets of sequences with specified RDS values where the concatenated sequences have unequal lengths which sum to the codeword length. In other words, the codewords may be constrained to assume at the end and at one or more prespecified locations within each codeword (not necessarily equidistant from both ends of the codewords) subsets of permissible RDS values prescribed by an initial RDS value. The selection of sequence lengths may be varied to achieve various tradeoffs between code rate, runlength constraints, RDS constraints, path memory length, and code/detector complexity.

While the invention, for sake of illustration, has been shown and described as applied to two specific rate 8/10 codes, it will be apparent that the invention may be applied to other RLL codes, and that various changes in detail may be made without departing from the scope and teaching of the invention. Accordingly, the methods and apparatus herein described are to be considered as merely illustrative, and the invention is to be limited only as specified in the claims. ##SPC1##