Coding Method and Apparatus Using Quaternary Codes

The present invention relates generally to the encoding of data strings, here the encoding of sequential binary data, for digital transmission or recording systems. In particular, the novel coding technique employs high-rate quaternary codes that offer advantageous properties for transmission over metallic cables or optical fibers and for recording in storage media. Further, the present invention is directed to an encoder utilizing the novel coding technique and to new codes, and to a transmission or recording system employing the above method of encoding and the new codes.

In the prior art, many digital transmission or recording systems require the use of codes which impose restrictions on the channel input sequences. Such codes, often termed constrained, modulation, or channel codes, are mainly used to improve timing and gain control in the receiver (or decoder in a recording system), to reduce intersymbol interference, and to shape the spectrum of the transmitted or recorded sequences so that the spectrum matches the frequency characteristics of the channel. In particular, many line codes were designed to suppress the spectral components of encoded sequences near the zero frequency. Such codes are instrumental in reducing the effects of baseline wander in a receiver.

Codes of that kind are DC-free, i.e., have a first order spectral null at zero frequency, if, and only if, the running digital sum (RDS) is bounded. The number of values N that the RDS can assume determines the low frequency content of the code spectrum. For example, the modified version of the ternary MS43 line code described by P. A. Franaszek in "Sequence-State Coding for Digital Transmission", Bell System Technical Journal, Vol. 47, pp. 143-157, January 1968, which was adopted by the German Bundespost as a standard for an ISDN transceiver, is based on a bounded RDS constraint with N=6.

Binary and multilevel codes with a spectral null at zero frequency possess desirable distance properties in addition to their spectrum shaping properties and can therefore be used to improve the reliability of transmission over noisy channels. In particular, they can be used to increase the Euclidian distance at the output of partial-response channels which are often encountered in digital recording and wire transmissions.

Binary Codes for partial-response channels that expand bandwidth by using convolutional codes with good Hamming Distance properties have been considered, e.g., by J. K. Wolf and G. Ungerboeck in "Trellis Codes for Partial Response Channels", IEEE Trans. Commun., Vol. COM-34, pp. 765-773, August 1986. Binary codes that expand bandwidth by enforcing a spectral null have been given, e.g., in U.S. Pat. No. 4,888,775 by R. Karabed and P. H. Siegel, issued in 1989. All these coding schemes are binary, and are well suited for applications such as saturation recording.

Multilevel coding schemes, as discussed, e.g., by G. D. Forney and A. R. Calderbank in "Coset Codes for Partial Response Channels; or Coset Codes with Spectral Nulls", IEEE Trans. Inform. Theory, Vol. IT-35, pp. 925-943, September 1989, achieve higher immunity against noise by expanding the signal alphabet and using trellis or known coset codes adapted for partial-response channels. Low rate (R less than or equal to 1 bit/symbol) quaternary trellis codes for partial response channels have also been constructed using concatenated coding schemes and set partitioning of the channel output signal set. Multilevel coding schemes are well suited for applications such as bandwidth efficient digital transmission and AC-bias recording.

A primary object of the present invention is to provide an optimal and advantageous method and apparatus for storing or transmitting data using optimized quaternary codes.

A further object of the present invention is to provide a method and means for constructing and applying optimized quaternary codes in the above apparatus. These optimized codes offer the spectral shaping properties of line codes, in particular for baseband wire/cable transmission.

Another object of the present invention is to increase/improve the noise margin during transmission or storage, especially in partial response class IV channels.

A still further object of the present invention is to reduce the average transmitted power at the channel input.

A method of encoding and decoding data according to the principles of the present invention meeting these and other objects comprises forming a v-state machine according to a v-state transition diagram and generating a first set of quaternary symbol sequences that is part of a second set of quaternary symbol sequences derived from a u-state transition diagram wherein the running digital sum of the sequences of the second set assumes values taken from a finite set of integers, such that each of v states is associated with 2K transitions, each transition corresponding to an m-symbol code word; encoding in said v-state machine a k-bit data byte into an m-symbol quaternary code word and generating a next state of said v-state machine as a function of its current state and the last encoded k-bit data byte. Sequences of m-symbol quaternary code words are decoded by estimating the encoded k-bit data bytes from output samples received from a partial response channel by generating the most likely sequence of m-symbol words that can be derived from the u-state transistion diagram, and mapping said generated m-symbol codes words into k-bit data bytes. The present invention also describes encoder/decoder apparatus for performing the disclosed encode/decode methods.

The invention meets these and other objects by the methods stated in claims 1 and 2 and the apparatus defined in claims 6 and 7. preferred embodiments and details of the methods and apparatus according to the invention are defined in the respective subclaims.

In brief, the quaternary coding technique disclosed here differs from conventional multilevel coding schemes for partial-response channels in that it optimizes the data transfer by applying a novel encoding method, i.e., a novel selection process for the code in which the data are to be transmitted or stored. The resulting transmitted (or stored) code exhibits spectral nulls at all frequencies where the channel transfer function vanishes.

Advantages are, first, less errors since the Euclidian distance at the channel output is increased; second, lower power consumption; and third, a relatively simple decoder design, including, e.g., a Viterbi detector.

In the following, the preferred embodiment of the invention shall be described in detail with reference to the appended drawing, starting with the mathematical background, discussion of simulation results, and implementations, and in which:

FIG. 1 is an infinite-state transition diagram illustrating quaternary sequences having a spectral null at DC;

FIG. 2 illustrates a first u-state transition diagram according to the present invention;

FIG. 3 illustrates a first v-state transition diagram according to the present invention;

FIG. 4 illustrates a second u-state transition diagram according to the present invention;

FIG. 5 illustrates a second v-state transition diagram according to the present invention;

FIG. 6 illustrates a third u-state transition diagram according to the present invention;

FIG. 7 illustrates a third v-state transition diagram according to the present invention;

FIG. 8 is a graph illustrating the event error probability as a function of the energy-per-symbol to noise-power-density ratio; 2E.sub.s /RN.sub.n, scaled by the rate loss;

FIG. 9 is a graph illustrating the power spectral density of various codes generated according to the present invention;

FIG. 10 is a block diagram illustrating a first encoder implementation according to the present invention;

FIG. 11 is a block diagram illustrating a first decoder implementation according to the present invention;

FIG. 12 is a block diagram illustrating a second encoder implementation according to the present invention; and

FIG. 13 is a block diagram illustrating a second decoder implementation according to the present invention.

The tables form part of the description and arc, for the sake of convenience, appended to the following text that describes the invention in detail, and in which:

Table 1 lists the capacity C (bit/symbol) for finite-state subdiagrams of the infinite-state transition diagram shown in FIG. 1;

Table 2 specifies the encoder mapping for the encoder of FIG. 3;

Table 3 lists code words in hexadecimal presentation for the encoder of FIG. 3;

Table 4 describes a 10-state trellis structure for Viterbi-detecting the code of Table 3;

Table 5 specifies the encoder mapping for the encoder of FIG. 5;

Table 6 lists code words in hexadecimal representation for the encoder of FIG. 5;

Table 7 describes an 8-state trellis structure for Viterbi-detecting the code of Table 6;

Table 8 specifies the encoder mapping for the encoder of FIG. 7;

Tables 9A/9B list code words in hexadecimal presentation for the encoder of FIG. 7;

Table 10 describes a 12-state trellis structure for Viterbi-detecting the code of Table 9; and

Table 11 provides a code comparison.

The codes given in this section are based on Finite-State Transition Diagrams (FSTDs) whose edges are labeled by symbols from the quaternary alphabet {-3,-1,+1,+3}. Referring now to FIG. 1 an infinite-state transition diagram whose subdiagrams generate quaternary sequences with bounded RDS, i.e., with a spectral null at DC is illustrated. Let G.sub.N be a finite-state subdiagram of this infinite-state transition diagram obtained by restricting the state set to N consecutive states. In this case, the number of states in G.sub.N and the number of distinct values assumed by the RDS are the same. Table 1 contains the capacity C, i.e., the maximum achievable code rate, associated with G.sub.N for different values of N.

The communication system model consists of a transmitter, a partial-response channel and a receiver. The transmitter employs finite-state machine encoders which map binary data streams into quaternary sequences. The set of all possible encoded sequences is a subset of the set of all sequences generated by the FSTD on which the encoder is based.

The receiver utilizes a soft-decision Viterbi detector followed by a block decoder which inverts the encoder mapping. The Viterbi detector performs sequence estimation on the trellis that combines the FSTD and the partial-response channel trellis. In other words, it chooses the most likely sequence generated by the FSTD in the sense that when it is transmitted over a noise-free channel, it results in a string of symbols which has a minimum Euclidean distance to the noisy received sequence. The complexity of the resulting Viterbi detectors can be kept within manageable limits without sacrificing performance by exploiting the periodic nature of quaternary FSTDs.

The construction of efficient codes is usually based on a technique known as state splitting. In the most common form of state splitting, referred to as output state splitting, the outgoing transitions (or edges) of a split state are distributed among the two resulting offsprings, whereas the incoming transitions of the split state are duplicated. A sequence of such splittings results in an equivalent FSTD where the number of outgoing transitions from each state is now sufficient to perform rate k/m bit/symbol coding. This increase in outgoing transitions has been achieved at the expense of an increase in decoder look-ahead. In other words, the sliding window of the sliding block decoder has become larger. In the construction of the disclosed quaternary codes, state splitting has been applied in a reverse manner. The incoming transitions of a split state are distributed among the two resulting offsprings whereas the outgoing transitions of the split state are duplicated. Therefore, rather than increasing the number of outgoing transitions, this technique, referred to as input state splitting, allows redirection of transitions without incurring any increase in decoder look-ahead. As a consequence, quasi-catastrophic error propagation can be avoided without climinating a large number of low-power code words and/or increasing decoder look-ahead. Keeping as many as possible low-power code words has the advantage of reducing the average transmitted power.

In general, the p-th power of G.sub.N is an N-state transition diagram where a transition from state i to state j corresponds to a p-step path from state i to state j in G.sub.N and vice versa The codes disclosed here are based on 3-state transition diagrams derived from the second power (p=2) of G.sub.7 and G.sub.11. In this case, each transition is labeled with two quaternary symbols.

The maximum rate that encoders derived from G.sub.7 N=7, can achieve, is 1.566 bit/symbol (see Table 1). In this case, the number of identical symbols at the input and output of the dicode channel is restricted to 6 and 5, respectively.

FIG. 2 shows a u-state transition diagram, i.e, the 3-state irreducible component of the second power of G.sub.7 from which one of the 8B/6Q codes (rate R=8/6 bit/symbol) is derived. The third power of the FSTD in FIG. 2 gives rise to a new 3-state transition diagram where each state has at least 256 outgoing 6-symbol transitions allowing the realisation of a 3-state 8B/6Q encoder.

One observes that it is possible to start at different encoder states and generate exactly the same sequences. Such sequences give rise to the phenomenon of quasi-catastrophic error propagation and should be eliminated. This can be achieved by eliminating transitions that start and end at the same state and cause error propagation, and rearranging transitions via input state splitting of the center state. In other words, transitions are rearranged such that edges arriving at the center state are partitioned and redirected to its two offsprings and the outgoing edges are duplicated. This leads to a 4-state transition diagram that does not generate sequences which could give rise to quasi-catastrophic error propagation. Since there are more than 256 transitions emanating from each of the 4 states, one can discard the transitions that contribute most to the average transmitted power. The reduced average transmitted power associated with sequences generated by this encoder is thus P.sub.s =2.93 which is considerably smaller than P.sub.s =5, i.e., the average transmitted power of a reference 2B/1Q scheme.

The structure of a resulting v-state encoder (v=4), often referred to as a v-state machine, is shown in FIG. 3. The encoder mapping is specified in Table 2 and, finally, the list of code words in hexadecimal representation is given in Table 3. The two quaternary symbols corresponding to a hexadecimal number are obtained by grouping the binary representation of a hexadecimal number into 2 dibits and converting every dibit 00, 01, 10, 11 into -3, -1, +1, +3, respectively. As an example, the code word D99 has the binary representation 110110011001 and corresponds to the 6 symbols +3-1+1-1+1-1 at the input of the channel. The bar on a list of i code words such as L(i) indicates that the signs of code word symbols in the original list of code words L(i) have been inverted.

For example, +1-1+1-1+1-1 (D99) is in A(43) (see Table 3) and represents the label of one of the 43 transitions in A(43) from state 1 to state 2 or from state 2 to state 4 (see FIG. 3). The inverse of D99 is -3+1-1+1-1+1 and belongs to A(43). Table 2 consists of two subtables specifying the mapping of 8-bit data words into 6-symbol code words. Subtable 2.1 provides data word to code word assignment when the encoder is in state 1 and state 4. Subtable 2.2 does the same for the encoder states 2 and 3. The entries of the first column in both subtables indicate lists of data words d in decimal form. For example, the entry d=0-42 in the first column of Subtable 2.1 indicates the data words 00000000=0, 00000001=1, . . . , 00101010=42. The entries of the second and third columns in both tables are of the form L(i)/s where L(i) is a list of i code words and s=1,2,3,4 indicates the next encoder state. For example, .DELTA.(43)/2 in the first column of Subtable 2.1 indicates a list of 43 code words that can be generated when the encoder changes its state from state s=1 (present state) to state s=2 (next state).

Decoding is accomplished in two steps. First, a Viterbi detector with a path memory of 24 symbols operating every two symbol intervals on the 10-state combined FSTD and channel trellis releases two quaternary symbols after a delay equal to the path memory. The 10-state trellis is described in Table 4 where the (i,j)th location--i vertically and j horizontally indicated--provides the channel input and output symbol pairs associated with the transition from trellis state i to trellis state j. For example, the transition from trellis state 3 to trellis state 5 is associated with the channel input symbol pair +1 -1 and the channel output symbol pair 2 -2. In a second step, a block decoder without look-ahead operating on groups of 6 quaternary symbols inverts the encoder mapping in Table 2 and releases 8 information bits.

An 8B/6Q code that requires only 8 trellis states for Viterbi detection has also been designed. The construction of this code is based on the u-state transition diagram shown in FIG. 4. This FSTD is a subdiagram of the FSTD shown in FIG. 2, obtained by eliminating four edges arriving at the center state labeled by (-1, +3), (+1, -3), (+3, -3), (-3, +3). The RDS of sequences generated by this FSTD takes still 7 different values as before. However, the capacity has now decreased to 1.431 bit/symbol. Applying input state splitting to the center state in the third power of the FSTD in FIG. 4, one can design an 8B/6Q encoder with reduced average transmitted power, no quasi-catastrophic error propagation and a corresponding block decoder without look-ahead. The structure of the resulting 4-state encoder is shown in FIG. 5, the encoder mapping is specified in Table 5 and, finally, the list of code words in hexadecimal representation is given in Table 6. The average transmitted power now is P.sub.s =3.29 which is slightly higher than in the previous case. Decoding is performed on an 8-state trellis obtained by combining the FSTD in FIG. 4 and the trellis of the dicode channel. This trellis is described in Table 7. Finally, the path memory of the Viterbi detector is limited to only 24 symbols.

A higher rate code that requires 12 trellis states for Viterbi detection has also been designed. The construction of this code is based on a subdiagram of the 5-state irreducible component of the second power of G.sub.11, N=11. Elimination of the two corner states at both ends of this 5-state component leads to a u-state transition diagram shown in FIG. 6, wherein u-3. The RDS of sequences generated by this FSTD takes 11 different values and the capacity is 1.613 bit/symbol. Applying input state splitting to the center state in the third power of the FSTD in FIG. 6, one can design an 9B/6Q encoder with reduced average transmitted power, no quasi-catastrophic error propagation, and a corresponding block decoder without look-ahead. The structure of the resulting 4-state encoder is shown in FIG. 7 and the encoder mapping is specified in Table 8. Subtable 8.1 provides data byte to code word assignment when the encoder is in state 1 or state 4 (present state), whereas Subtable 8.2 shows the same for encoder states 2 and 3. Finally, the list of code words in hexadecimal representation is given in Tables 9A and 9B. The average transmitted power now is P.sub.s =4.02 which is slightly higher than in the previous two cases, but still 20% lower than the average transmitted power of the uncoded baseline system. Decoding is performed on a 12-state trellis obtained by combining the FSTD in FIG. 6 and the trellis of the dicode channel. This trellis is described in Table 10. Finally, the path memory of the Viterbi detector is again limited to only 24 symbols.

For example, the 6-symbol code word +1 -3 +1 +3 -1 -1 has the hexadecimal representation 8B5 and belongs to the list of code words F(18) (see Table 9). The code word 8B5 in F(18) can be generated when the encoder is in state s=2 or s=3 (see Subtable 8.2 and FIG. 7). In both cases, the next state is state s=2 or s=3 as it can be seen from Subtable 8.2 and FIG. 7.

Simulation results for the proposed codes have verified the expected coding gains. FIG. 8 shows event error probabilities, P.sub.E as a function of the energy-per-symbol to noise-power-density ratio scaled by the rate loss, 2E.sub.s/RND in dB. Curve 1 in FIG. 8 gives the theoretical performance of an MLSE (Maximum Likelihood Sequence Estimation) receiver for uncoded quaternary transmission over the dicode channel (R=2 bit/symbol) estimated by ##EQU1##

Curves 2-4 in FIG. 8 correspond to the performance of receivers for coded quaternary transmission at rates R=8/6 bit/symbol and R=9/6 bit/symbol over the dicode channel.

Curve 2 shows the case of the rate R=9/6 bit/symbol code where the Viterbi detector operates on the 12-state combined trellis described in Table 10. Compared to curve 1, a gain in noise margin of 2.9 dB is obtained. Curve 3 corresponds to a rate R=8/6 bit/symbol code where the Viterbi detector operates on the 8-state combined trellis in Table 7. Compared to curve 1, a gain of approximately 3.4 dB is obtained. Finally, curve 4 shows the case of a rate R=8/6 bit/symbol code where the receiver utilizes a 10-state Viterbi detector with a trellis described in Table 4. A comparison of curve 4 with curve 1 indicates a gain of 3.8 dB in noise margin.

It is also of interest to calculate the spectrum of the particular codes proposed here. This will shed some light on spectral characteristics of encoded sequences such as width of spectral notch at f=0 and average transmitted power. FIG. 9 shows the power spectral densities of the various codes described in the previous section versus the normalized frequency, f/f.sub.s, where f stands for frequency and f.sub.s represents the symbol frequency, i.e. the inverse of the duration of a quaternary symbol. The area under the curves in FIG. 9 corresponds to the average transmitted power P.sub.s. It can be seen that all three codes have reduced average transmitted power, i.e. their average transmitted power is considerably less than the average transmitted power in the case of uncoded quaternary transmission. Finally, Table 11 summarizes the parameters associated with the three codes described in the previous section and compares them against the baseline system of uncoded quaternary transmission.

The finite-state machine encoders and block decoders disclosed here can be implemented either by random logic or by Read Only Memory blocks (ROMs).

Referring now to FIGS. 10 and 11, a ROM-based realization of the two 8B/6Q finite-state machine encoders described in Tables 2 and 5 is shown. It consists of an 8-bit input register 1, a 2-bit state register 2, a 1k.times.14 ROM 3, and a converter 4. Registers 1 and 2 are clocked at a rate of f.sub.s /6, where f.sub.s is the symbol rate.

At the end of an encoder cycle, a 12-bit code word is generated which is serialized and mapped into 6 quaternary symbols in converter 4. Decoding of the 8B/6Q codes is accomplished by a Viterbi detector 5 in cascade with a block decoder 6 shown in FIG. 11.

Channel output samples are quantized to q bits. A serial-to-parallel converter, consisting of two q-bit registers 7 and 8 and a 2q-bit register 9, supplies a Viterbi detector 5 with two q-bit channel output samples. Registers 7 and 8 are clocked at a rate f.sub.s, whereas register 9 is clocked at a rate f.sub.s /2. Viterbi detector 5 accepts the two q-bit samples and delivers four bits corresponding to delayed estimates of two quaternary symbols. The decision delay is equal to the path memory of the Viterbi detector. Three consecutive 4-bit outputs of Viterbi detector 5 stored in registers 10, 11, and 12, respectively, are passed on to a 12-bit register 13 whose content is interpreted as the 12-bit address of a 4k.times.8 ROM 6. This ROM 6 constitutes the block decoder. Registers 10, 11, and 12 are clocked at a rate f.sub.s /2, whereas register 13 is clocked at a rate f.sub.s /6. The content of an 8-bit output register 14 represents the transmitted data byte. The output register 14 is clocked at a rate f.sub.s /6.

Referring now to FIGS. 12 and 13, a ROM-based realization of the 9B/6Q finite-state machine encoder described in Table 8 is shown. It consists of a 9-bit input register 15, a 2-bit state register 16, a 2k.times.14 ROM 17, and a converter 18.

At the end of an encoder cycle, a 12-bit code word is generated which is serialized and mapped into 6 quaternary symbols by converter 18. Decoding of the 9B/6Q code is accomplished by a 12-state Viterbi detector 19 in cascade with a block decoder 20, here a 4k.times.9 ROM, shown in FIG. 13.

Channel output samples are quantized to q bits. A serial to parallel converter, consisting of two q-bit registers 21 and 22 and a 2q-bit register 23, supplies Viterbi detector 19 with two q-bit channel output samples. Registers 21 and 22 are clocked at a rate f.sub.s, whereas register 23 is clocked at a rate f.sub.s /2. Viterbi detector 19 accepts the two q-bit samples and delivers four bits corresponding to delayed estimates of two quaternary symbols. The decision delay is equal to the path memory of the Viterbi detector. Three consecutive 4-bit outputs of Viterbi detector 19 stored in registers 24, 25, and 26, respectively, are passed on to a 12-bit register 27 whose content is interpreted as the 12-bit address of a 4k.times.9 ROM 20. This ROM 20 constitutes the block decoder. Registers 24, 25, and 26 are clocked at a rate f.sub.s /2, whereas register 27 is clocked at a rate f.sub.s /6. The content of a 9-bit output register 28 represents the transmitted data byte. The output register 28 is clocked at a rate f.sub.s /6.

While the present invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit, scope and teaching of the invention. Accordingly, the invention herein disclosed is to be considered merely as illustrative and limited in scope only as specified in the appended claims.