System and Method for Encoding Data Such That After Precoding the Data Has a Pre-Selected Parity Structure

This application relates to U.S. patent application Ser. No. 08/541,675, entitled "System And Method For Coding Partial Response Channels With Noise Predictive Viterbi Detectors," filed Oct. 10, 1995 by Razmik Karabed and Nersi Nazari, which is incorporated herein by reference.

1. Field of the Invention

The present invention relates generally to methods for transmission of binary digital data over partial response maximum likelihood (PRML) channels. More particularly, the present invention relates to a novel encoding system and method designed for use with a precoder such that the precoder produces codes with Hamming distance greater than one to eliminate error events with a small distance at the output of the channel. Still more particularly, the present invention relates to an encoding system and method that produces codes which satisfy a set of parity equations when precoded.

2. Description of the Related Art

The use of partial response maximum likelihood (PRML) channels is well known in the art as a method for transmitting data. Prior art methods for coding and detection in PRML channels include: 1) J. K. Wolf and G. Ungerboeck, in "Trellis Coding For Partial-Response Channels," IEEE Trans. Comm., August 1986, pp. 765-773; 2) R. Karabed and P. Siegel disclose one such method in U.S. Pat. No. 4,888,775 entitled "Trellis Codes For Partial-Response Channels," issued Dec. 19, 1989; 3) R. Karabed and P. Siegel in U.S. Pat. No. 4,888,779 entitled "Matched Spectral Null Codes for Partial Response Channels," issued Dec. 19, 1989; 4) R Karabed and N. Nazari, U.S. patent application Ser. No. 08/541,675, entitled "System And Method For Coding Partial Response Channels With Noise Predictive Viterbi Detectors," filed Oct. 10, 1995 which is incorporated herein by reference; and 5) R. Galbraith, U.S. Pat. No. 5,196,849 entitled "Method and Apparatus For Implementing PRML Codes with Maximum Ones," issued Mar. 23, 1993. The prior art methods vary in their performance, or error probability, and also vary in transmission rate.

U.S. patent application Ser. No. 08/541,675, entitled "System And Method For Coding Partial Response Channels With Noise Predictive Viterbi Detectors," discloses the use of codes which preclude error events with small distance at the output of the channel. This approach shows that codes producing a Hamming distance of 2 or more at the input of the channel improve performance, and reduces the error probability. However, this method does not address the situation when a precoder is used.

The prior art often uses precoders to eliminate error propagation. For example, a 1/(1.sym.D) precoder over a 1-D channel produces non-zero channel output for each non-zero precoder input, and produces a zero channel output for each zero precoder input. In magnetic recording, a "1" channel input denotes magnetic polarization in one direction and a "0" channel input denotes magnetic polarization in the opposite direction. If a precoder is not used, then errors persist continually in the system as the magnetic polarization directions are switched. Commonly, a precoder is used to eliminate this problem and exemplary precoders include: a 1/(1.sym.D) precoder for a 1-D channel; a 1/(1.sym.D) precoder for a (1D)(1+D).sup.3 channel; a 1/(1.sym.D).sup.2 precoder for a 1-D.sup.2 channel; and a 1/(1.sym.D.sup.4)precoder for a (1-D).sup.4 channel. However, such prior art precoding methods do not provide input codes which have hamming distance greater than one for the channel.

Thus, there continues to be a need for methods of encoding signal to provide improved channel performance. In particular, there is a need for a system and method that further improves the performance of partial response channels by using a code generation method that produces codes with a desired parity structure at the output of the precoder.

The present invention is a system and method for encoding and decoding input strings to improve the performance of partial response channels. The present invention advantageously provides a unique system and method for encoding and decoding binary digital signals such that after precoding the strings will have a predetermined parity structure, and thereby eliminate error events with small distance, and improve overall channel performance. The system of the present invention preferably comprises an encoder, a precoder, a PR channel, a detector, and a decoder. An input signal is received by the encoder. The encoder generates a code string by adding one or more bits and outputs the code string to the precoder. The encoder applies such encoding such that the code string after being modified by the precoder has a pre-selected parity structure. The encoder preferably comprises a serial-to-parallel converter, a code generator and a parallel-to-serial converter. The code generator produces one of three trellis codes such as an 8/9, 8/10 or 9/11 code. The present invention also includes a decoder that is coupled to the output of the detector. The decoder restores a received string to the format that it had at the encoder by performing a function that is the "inverse" of the encoder.

The method of the present invention preferably includes a number of methods. One such method is directed to encoding bit strings and comprises the steps of: 1) converting the input string to input bits, and 2) adding at least one bit to produce a pre-selected parity structure after precoding. Another method is directed to transmitting serial strings and comprises the steps of: 1) encoding an input string by adding at least one bit such that a pre-selected parity structure is produced after precoding, 2) transmitting the encoded signal through a precoder; 3) sending the precoded sequence through a channel to generate a channel output sequence; 4) producing a detector output sequence by applying the channel output sequence to a detector; and 5) decoding the detector output sequence.

The present invention is particularly advantageous over the prior art because it provides a systematic encoding scheme in which many of the encoded bits are the same as the input bits used to generate the encoded bits. This systematic approach of the present invention provides an encoder that is easy to implement because a majority of the bits are directly "feed through" and non-trivial logic circuits are only needed to generate the control bits. The decoder is likewise easy to construct and can be implemented in a circuit that simply discards the control bit.

The present invention has other advantages and features which will be more readily apparent from the following detailed description of the invention and the appended claims, when taken in conjunction with the accompanying drawings, in which:

FIG. 1 is a block diagram of a preferred embodiment of a communication system including a partial response channel, an encoder and a decoder constructed according to the present invention;

FIG. 2 is a block diagram of a first embodiment of an encoder constructed according to the present invention;

FIG. 3 is a block diagram of first embodiment of a decoder constructed according to the present invention for use in conjunction with the encoder of FIG. 2;

FIGS. 4A and 4B are block diagrams of a first embodiment of a code generator used in the first embodiment of the encoder and constructed according to the present invention to generate a first code;

FIG. 5 is block diagram of a second embodiment of the code generator used in the first embodiment of the encoder of the present invention to generate a first code;

FIG. 6 is block diagram of a third embodiment of the code generator used in the first embodiment of the encoder of the present invention to generate a first code;

FIG. 7 is a second embodiment of the encoder constructed according to the present invention;

FIG. 8 is a block diagram of a second embodiment of the decoder of the present invention for use in conjunction with the encoder of FIG. 7;

FIG. 9 is a block diagram of a first embodiment of a code generator used in the second embodiment of the encoder and constructed according to the present invention to generate a second code;

FIG. 10 is block diagram of a second embodiment of the code generator used in the second embodiment of the encoder of the present invention to generate a second code;

FIG. 11 is a third embodiment of the encoder constructed according to the present invention and having cascaded code generators;

FIG. 12 is a block diagram of a third embodiment of the decoder of the present invention for use in conjunction with the encoder of FIG. 11;

FIG. 13 is a block diagram of a first embodiment of a code generator used in the third embodiment of the encoder and constructed according to the present invention to generate a third code; and

FIG. 14 is block diagram of a second embodiment of the code generator used in the third embodiment of the encoder of the present invention to generate a third code.

While the present invention will now be described with reference to a communication system encountered in magnetic recording practice, those skilled in the art will realize that the present invention can be incorporated into any one of a variety of systems for transmitting binary data.

Referring now to FIG. 1, a preferred embodiment of a communication system 10 constructed in accordance with the present invention is shown. The preferred embodiment of the system 10 comprises an encoder 12, a precoder 14, a partial response (PR) channel 16, a detector 18, and a decoder 20. The PR channel 16 preferably further comprises a low pass filter 40, a noise source 42 and an adder 44. The encoder 12 produces a novel trellis code. The novel trellis code is particularly advantageously because after preceding, the code sequence output by the precoder satisfies a given set of parity equations. More specifically, the pre-selected parity structure improves the performance of the partial response channel 16 by eliminating error events with small distance at the channel output. The present invention preferably provides three trellis codes: code 1, code 2, and code 3. The first code, Code 1, has rate 8/9 and it satisfies one parity equation after preceding by 1/(1.sym.D.sup.2); the parity equation is on all codeword bits after precoding. The second code, Code 2, has rate 8/10 and it satisfies two parity equations after precoding by 1/(1.sym.D.sup.2); one parity equation on the even codeword bits after preceding and one parity equation on the odd codeword bits after precoding. The third code, Code 3, has rate 9/11, and it is a cascaded of two codes, code 3' and code 3". Code 3' is any given rate 9/10 code. Code 3" inserts a bit into each codeword received from code 3' such that the resulting codeword satisfies one parity equation after precoding by 1/(1.sym.D); the parity equation is on all codeword bits after precoding.

As shown in FIG. 1, an input signal on a line 22 is transmitted to an input of the encoder 12. The input signal or data is preferably in the form of a binary symbol string, b.sub.0,b.sub.1,b.sub.2, . . . The encoder 12 produces and outputs a coded sequence, v.sub.0,v.sub.1,v.sub.2, . . . , from the input signal. The code sequence is preferably one of the above three trellis codes as will be described in more detail below. The preferred embodiments for encoding the input signal are described below with particularity, however, for ease of understanding the remaining components of the system 10 will first be described. The output of the encoder 12 is coupled to line 24 to provide the coded sequence on line 24.

The precoder 14 has an input and an output. The input of the precoder 14 is coupled to line 24 to receive the coded sequence. The precoder 14 generates a precoded sequence x.sub.0,x.sub.1,x.sub.2 . . . , based on the coded sequence. The precoder 14 preferably takes one of two forms, either a 1/(1.sym.D) precoder or a 1/(1.sym.D.sup.2) precoder. Those skilled in the art will realize that the precoder 14 may be any one of a variety of conventional precoders, and for such conventional precoders, the trellis code must be adjusted such that a given set of parity equations are satisfied after encoding and precoding by the encoder 12 and the precoder 14, respectively. If the precoder 14 is 1/(1.sym.D), then the precoded sequence and the code sequence are related by x.sub.i =v.sub.i .sym.x.sub.i-1. On the other hand, if the precoder 14 is 1/(1.sym.D.sup.2), then they are related as x.sub.i =v.sub.i .sym.x.sub.i-2. The output of the precoder 14 is coupled to line 26 to provide the precoded sequence x.sub.0 x.sub.1 x.sub.2 . . . , to the PR channel 16.

The preferred embodiment for the PR channel 16 has an input and an output, and further comprises: the filter 40, the noise source 42, and the adder 44. The filter 40 has an input and an output. The input of the filter 40 forms the input of the PR channel 16 and is coupled to line 26 to receive the precoded sequence from the precoder 14. In the preferred embodiment, the filter is either a h (D)=1-D or a h (D)=1-D.sup.2 filter. The filter 40 produces a filter output sequence, y.sub.0 y.sub.1 y.sub.2 . . . If the filter 40 is 1-D, then the channel filter output sequence y.sub.0 y.sub.1 y.sub.2 . . . and the precoded sequence x.sub.0 x.sub.1 x.sub.2 . . . are related by y.sub.i =x.sub.i -x.sub.i-1, but if the channel filter 40 is 1-D.sup.2, then the channel filter output sequence y.sub.0 y.sub.1 y.sub.2 . . . and the precoded sequence x.sub.0 x.sub.1 x.sub.2 . . . are related by y.sub.i =x.sub.i -x.sub.i-2. The output of the filter 40 is coupled to line 46 which is in turn coupled to a first input of the adder 44. A second input of the adder 44 is coupled to line 45 to receive a noise signal, n(t), from the noise source 42. The noise source 42 produces a noise sequence n.sub.0 n.sub.1 n.sub.2 . . . , that is output on line 45. The adder 44 adds the noise signal, n(t), and the filter 40 output to produce a channel output sequence, r.sub.0 r.sub.1 r.sub.2 . . . , on line 28. The channel output sequence r.sub.0 r.sub.1 r.sub.2 . . . is the sum of the channel filter sequence and the noise sequence, i.e., r.sub.i =y.sub.i +n.sub.i.

The system 10 also includes the detector 18 having an input and an output. The input of the detector 18 is coupled to line 28 to receive the channel output sequence. The detector 18 is preferably a Viterbi detector, but may also be a noise predictive Viterbi detector or other types of detectors, and generates a detector output sequence, u.sub.0 u.sub.1 u.sub.2 . . . , which is a reproduction of the coded sequence v.sub.0 v.sub.1 v.sub.2 . . . , from the channel output sequence. The detector 18 can be any conventional Viterbi detector. The output of the detector 18 is coupled to line 30 to provide the reproduction of the coded sequence v.sub.0 v.sub.1 v.sub.2 . . . to the decoder 20.

Finally, the output of the detector 18 is provided on line 30 to the input of the decoder 20. The decoder 20 also performs the inverse of the encoder 12 in order to reproduce the input signal. The output of the decoder is provided on line 32 as an output signal. The decoder 20 generates a decoded sequence b'.sub.0 b'.sub.1 b'.sub.2 . . . which is a reproduction of the input data. The decoder 20 has several embodiments as will be described in detail below, and the present invention provides an embodiment of the decoder 20 corresponding to each trellis code provided.

Referring now to FIG. 2, a first embodiment of the encoder 12a of the present invention will be described. In the first embodiment, the encoder 12a performs the encoding using a first code, code 1, that has a rate 8/9 and it satisfies one parity equation after preceding. In this embodiment, the precoder 14 precodes by 1/(1.sym.D.sup.2). The parity equation is preferably on all codeword bits after preceding. The Code 1 encoder 12a takes 8 bits, b.sub.8k,b.sub.8k+1, . . . ,b.sub.8k+7, every time k.gtoreq.0, and produces 9 bits v.sub.9k,v.sub.9k+1, . . . ,v.sub.9k+8. We use the notation v.sub.i (k), i .epsilon. {0, 1, . . . , 8}, for v.sub.9k+i, and use b.sub.i (k), i.epsilon.{0, 1, . . . , 7}, for b.sub.8k+i. For this code, we desire ##EQU1## for every k.gtoreq.0, where x.sub.i is the output of a 1/(1.sym.D.sup.2) precoder corresponding to input v.sub.i. Lemma 2 and Corollary 2.1 (See Appendix A) are used for n=8 to compute a.sub.q, a.sup.(e) (k), and a.sup.(o) (k), for q.epsilon. {0, 1, . . . , 8} as: ##EQU2## Therefore, the control integers are 0, 3, 4, 7 and 8, and T.sub.1 (k) is: ##EQU3##

The present invention uses bit 8 as a control integer to force the equation T.sub.1 (k)+a.sup.(e) (k)cs.sub.1 (k)+a.sup.(o) (k)cs.sub.2 (k)=0, for all k.gtoreq.0. Therefore, the output, v, of the code 1 is described by the following equations. ##EQU4##

As shown in FIG. 2, the first embodiment of the encoder 12a includes a serial-to-parallel converter 150, a parallel-to-serial converter 152, and a code generator 154. The serial-to-parallel converter 150 has an input and plurality of outputs, and is preferably a one-to-eight converter. The serial-to-parallel converter 150 receives a serial string having a predetermined number of bits, and provides those bits simultaneously or in parallel at its outputs. The input of the serial-to-parallel converter 150 is coupled to line 22 to receive the binary string b.sub.0,b.sub.1,b.sub.2, . . . Each of the outputs of the serial-to-parallel converter 150 provides a single bit of the binary string such that eight bits are output. Each of the outputs of the serial-to-parallel converter 150 is coupled to a respective input of the parallel-to-serial converter 152 to generate the bits v.sub.0 through V.sub.7 according to the above equations. The parallel-to-serial converter 152 preferably has a plurality of inputs (nine) and an output. The parallel-to-serial converter 152 receives a predetermined number of bits in parallel and converts them into a serial string of bits, v.sub.0,v.sub.1,v.sub.2 . . . The output of the parallel-to-serial converter 152 is coupled to line 24 to provide the encoded sequence. The additional input of the parallel-to-serial converter 152 is coupled to line 170 to receive an additional bit from the code generator 154. The code generator 154 preferably has a plurality of inputs coupled to receive b.sub.0 (k) through b.sub.7 (k) from the parallel-to-serial converter 152. The code generator 154 produces an additional bit, b.sub.8 (k) according to equation 3 above. This additional bit is sent to the parallel-to-serial converter 152 and is used as bit v.sub.8 (k). The code generator 154 in the present invention has several embodiment 154a, 154b, 154c, which will be described in more detail below with reference to FIGS. 4-6.

Referring now to FIG. 3, a first embodiment of the decoder 20a constructed according to the present invention for decoding signals encoded with code 1, is shown. The decoder 20a preferably comprises a serial-to-parallel converter 160 and a parallel-to-serial converter 162. The serial-to-parallel converter 160 preferably has an input and nine outputs, and converts an input string into a nine parallel bits. The input of the serial-to-parallel converter 160 is coupled to line 30 to receive the sequence output by the detector 18. The parallel-to-serial converter 162 preferably has eight inputs and an output, and converts the eight input parallel bits into a string. The output of the parallel-to-serial converter 162 is coupled to line 32 to provide the reconstructed input string. Eight of the nine outputs, u.sub.0 (k) through u.sub.7 (k) of the serial-to-parallel converter 160 are coupled to respective inputs of the parallel-to-serial converter 162. The ninth output, u.sub.8 (k), is not coupled to any input of the parallel-to-serial converter 162, thereby effectively dropping this bit from the sequence and decoding the bit stream from nine bits to eight bits, the original format for the string.

While the encoder 12a and the decoder 20a have and will be described as including a serial-to-parallel converters and parallel-to-serial converters, those skilled in the art will realize that the present invention may be constructed without use of such converters. Since the control bit is assigned to one of the bits for each code, an alternate embodiment of the encoder does not require the converters. As bits enter into the alternate embodiment of the encoder, they simply pass through except at time instances where a control bit needs to be inserted. At such an instance, the input stream is stopped (via such a method as clock gapping) and the control bit is computed and inserted at the output of the encoder.

Referring now to FIGS. 4A and 4B, a first embodiment for the code generator 154a that generates the additional bit of code 1 is shown. The first embodiment for the code generator 154a comprises combinational logic, a plurality of latches, and delays as shown in FIG. 4A, and implements the equation 3 in hardware. The series of a first latch, a delay and a second latch that are used to store a first current and next states. The even bits are Exclusive-ORed together, the odd bits are Exclusive-ORed together, then ANDed with the e and e.sup.c signals, respectively, before being applied to the input of the first latch. The input to the first latch also receives a current state feedback component from latch 2. A second series of a third latch, a delay and a fourth latch are similarly coupled and store a second current and next states. The input to the third latch is provided by an output of an Exclusive-OR gate that receives the output of the fourth latch and the results Exclusive-ORing the even bits together, and Exclusive-ORing the odd bits together, and then ANDing the output with the e.sup.c and e, respectively. The output of each series of latches is again ANDed with e and e.sup.e signals, respectively, before being combined using Exclusive-OR gates to provide the generator 154a output on line 170. As shown in FIG. 4B, the e and e.sup.c signals are produced from a serial coupling of a fifth latch, a delay and a sixth latch. The output of the sixth latch provides the e signal and is also inverted to provide the e.sup.c signals which is fed back as the input to the fifth latch. In the preferred embodiment, the initial state of the second latch is cs.sub.1 (0)=x.sub.-2, the initial state of the fourth latch is Cs.sub.2 (0)=x.sub.-1, and the initial state of the sixth latch is a a.sup.(e) (0)=1.

Referring now to FIG. 5, a second embodiment of the code generator 154b for the first code, code 1, is shown. The second embodiment of the code generator 154b is shown in FIG. 5, and is based on the same equation as the embodiment 154a of FIGS. 4A and 4b, and the equation can be rewritten as T.sub.1 (k)+h.sup.(e) x.sub.kn+k-2 +h.sup.(o) x.sub.kn+k+1 =0. Therefore, using equation (EQ 1), v.sub.8 (k) can be written as

However, h.sup.(e) =1 and h.sup.(o) =0, thus equation (EQ 4) simplifies to

The second embodiment of the code 1 code generator 154b is based on (EQ 5). As shown in FIG. 5, the code generator 154b includes four Exclusive-OR gates a first latch and a second latch. A first Exclusive-OR gate 180 receives the b.sub.3 (k) and the b.sub.7 (k) signals, and a second Exclusive-OR gate 182 receives the b.sub.4 (k) and the b.sub.0 (k) signals. The output of the first and second Exclusive-OR gates 180, 182 are provided as the inputs to the third Exclusive-OR gate 184 which in turn is input to Exclusive-OR gate 186. The output of Exclusive-OR gate 186 provides the output of the second embodiment of the code generator 154b and is coupled to line 170. The other input of the Exclusive-OR gate 186 is coupled to the output of latch B to provide a signal equal to x.sub.kn+k-2. The first and second latches are coupled in series and the input to the first latch, latch A is the output of precoder 14 on line 26. The second embodiment of the code generator is particularly advantageous because feedback from the precoder 14 is used to minimize the gate used in the code generator 154b.

Referring now to FIG. 6, a third embodiment of the code generator 154c for code 1 is shown. The third embodiment of the code generator 154c shown in FIG. 6 is based on is based on Corollary 2.7 (See Appendix A), which describes a finite state machine characterized by ##EQU5## Now, we use the following expression for ns.sub.2 (k) given in Corollary 2.7. ##EQU6## r.sub.1 and r.sub.2 are 5 and 4, respectively, however, we place a one for r.sub.1 and a zero for r.sub.2, since arithmetic is mod 2. FIG. 6 shows the third embodiment of code 1 code generator 154c. As can be seen, the third embodiment is similar to the first embodiment, but simplified, and comprises a plurality of Exclusive-OR gates and a first and second series of latches and delays. The signals b.sub.6 (k), b.sub.2 (k), b.sub.3 (k) and b.sub.7 (k) are Exclusive-ORed and input to the first latch. The signals b.sub.1 (k), b.sub.5 (k), b.sub.3 (k) and b.sub.7 (k) are Exclusive-ORed with output of the second latch, and then input to the third latch. Finally, the signals b.sub.4 (k), b.sub.0 (k), b.sub.3 (k) and b.sub.7 (k) are Exclusive-ORed with output of the fourth latch, and provide the output of the third embodiment of the code generator 154b on line 170. The initial state of latch 4 is cs.sub.2 (0)=r.sub.2 x.sub.-1 +r.sub.1 x.sub.-2 =x.sub.-2, and the initial state of latch 2 also is cs.sub.1 (0)=r.sub.2 x.sub.-1 +r.sub.1 x.sub.-2 =x.sub.-2

Referring now to FIGS. 7-10, a second embodiment of the system 10 will be described. In the second embodiment of the system 10, the system has an encoder 12b and a decoder 20b that are very similar to the first embodiment except that the encoder 12b has a different encoding scheme, namely code 2. Code 2 is a rate 8/10 code and it satisfies two parity equations after precoding by 1/(1.sym.D.sup.2)--one parity equation on the even codeword bits after precoding and one parity equation on the odd codeword bits after precoding. The Code 2 encoder 12b takes 8 bits, b .sub.8k' b .sub.8k+1' . . . ,b .sub.8k+7' every time k.ltoreq.0, and produces 10 bits, v .sub.10k' v .sub.10k+1' . . . ,v .sub.10k+9. The notation used is v .sub.i (k), i.epsilon.{0, 1, . . . , 9}, for v .sub.10k+i, and b.sub.i (k), i.epsilon.{0, 1, . . . , 7}, for b.sub.8k+i.

For this second code, it is desirable that: ##EQU7## for every k.gtoreq.0, where x.sub.i is the output of a 1/(1.sym.D.sup.2) precoder corresponding to input v.sub.i.

The equations C1 and C2 are independent, therefore, using Lemma 3, we apply Lemma 2 twice, once for each of the parity equations C1 and C2. Applying Lemma 2 to C1 for n=9, we compute a.sub.q.sup.(1), a.sup.(e)(1) (k), and a.sup.(o)(1) (k), for q.epsilon.{0, 1, . . . , 9} are computed to have values: ##EQU8## Therefore, the control integers are 0, 4, and 8, and T.sub.1.sup.(1) (k) i s

Using Corollary 2.2 (See Appendix A) t, we obtain ##EQU9## For C1, the control integer (0, 4 or 8) is chosen to force the (p.sup.3) equation

Using the values derived using lemma 2 above, we can simplify (EQ 8).

Applying Lemma 2 to C2, a.sub.q.sup.(2),a.sup.(e)(2) (k), and a.sup.(o)(2) (k), for q.epsilon.{0, 1, . . . , 9}, are computed to have the following values: ##EQU10## Therefore, the control integers are 1, 5, and 9, and T.sub.1.sup.(2) (k) i s

Again using Corollary 2.2, we obtain ##EQU11## C2 control integer (1, 5 or 9) is chosen to force the (p.sup.3) equation

And equation 12 is simplified to:

The present invention preferably used bit 8 as a control integer for C1, to force (EQ 9), and bit 9 is used as a control integer for C2, to force (EQ13), for all k.gtoreq.0. Therefore, the output, v, of the code 2 encoder 12b is described by the following equations.

As shown in FIG. 7, the second embodiment of the encoder 12b includes a serial-to-parallel converter 250, a parallel-to-serial converter 252, and a code generator 254, similar to the first embodiment. However, in contrast to the first embodiment 12a, the second embodiment of the encoder 12b has a code generator 254 that adds two bits to the output stream. The serial-to-parallel converter 250 has an input and plurality of outputs, and is preferably a one-to-eight converter. The serial-to-parallel converter 250 receives a serial string having a predetermined number of bits, and provides those bits in parallel at its outputs. The input of the serial-to-parallel converter 250 is coupled to line 22 to receive the binary string b.sub.0,b.sub.1,b.sub.2, . . . The serial-to-parallel converter 250 is preferably an 1-to-8 converter. Each of the outputs of the serial-to-parallel converter 250 is coupled to a respective input of the parallel-to-serial converter 252 to generate the bits v.sub.0 through v.sub.7 according to the above equations. The parallel-to-serial converter 252 preferably has a plurality of inputs (ten) and an output. The parallel-to-serial converter 252 receives a predetermined number of bits in parallel and converts them into a serial string of bits, v.sub.0,v.sub.1,v.sub.2, . . . The output of the parallel-to-serial converter 252 is coupled to line 24 to provide the encoded sequence. The two additional inputs of the parallel-to-serial converter 252, v.sub.8 and v.sub.9 are coupled to line 270 and line 272, respectively, to receive two additional bits from the code generator 254. The code generator 254 preferably has a plurality of inputs which are coupled to receive b.sub.0 (k) through b.sub.7 (k) from the parallel-to-serial converter 252. The code generator 254 produces two additional bits, b.sub.8 (k) and b.sub.9 (k) according to the equations immediately above. These additional bits are sent to the parallel-to-serial converter 252 and are used as bit v.sub.8 (k) and v.sub.9 (k), respectively. The code generator 254 in the present invention has several embodiment 254a, and 254b, which will be described in more detail below with reference to FIGS. 9 and 10.

Referring now to FIG. 8, a second embodiment of the decoder 20b for decoding signals encoded with code 2, is shown. The decoder 20b preferably comprises a serial-to-parallel converter 260 and a parallel-to-serial converter 262. The serial-to-parallel converter 260 preferably has an input and ten outputs, and converts an input string into ten parallel bits. The input of the serial-to-parallel converter 260 is coupled to line 30 to receive the sequence output by the detector 18. The parallel-to-serial converter 262 preferably has eight inputs and an output, and converts the eight input parallel bits into a string. The output of the parallel-to-serial converter 262 is coupled to line 32 to provide the reconstructed input string. Eight of the ten outputs, u.sub.0 (k) through u.sub.7 (k) of the serial-to-parallel converter 260 are coupled to respective inputs of the parallel-to-serial converter 262. The ninth and tenth outputs, u.sub.8 (k) and u.sub.9 (k) are not coupled to any input of the parallel-to-serial converter 262, thereby effectively dropping these bits from the sequence and decoding the bit stream from ten bits to eight bits to recreate the original format for the string.

Referring now to FIG. 9, a first embodiment for the code 2 code generator 254a is shown. The first embodiment for the code 2 code generator 254a is a hardware implementation of equations v.sub.8 (k)=v.sub.0 (k)+v.sub.4 (k)+cs.sub.1.sup.(1) (k), and v.sub.9 (k)=v.sub.1 (k)+v.sub.5 (k)+cs.sub.2.sup.(2) (k). b.sub.6 (k) and b.sub.2 (k) are Exclusive-ORed together and the result is input into a first latch storing a next state. The output of the latch is delayed and then applied to the input to a second latch storing a current state. The output of the second latch is Exclusive-ORed with b.sub.4 (k) and b.sub.0 (k) to produce the first additional encoding bit that is output on line 270. The initial state of latch 2 is cs.sub.1.sup.(1) (0)=x.sub.-2. Similarly, the hardware for producing the second additional bit, v.sub.9 (k), has an identical structure, but receives b.sub.3 (k), b.sub.7 (k), b.sub.1 (k), and b.sub.5 (k) as inputs. The initial state of latch 4 is preferably cs.sub.2.sup.(2) (0)=x.sub.-1.

Referring now to FIG. 10, a second embodiment of the code 2 code generator 254b is shown. Based on corollary 2.4, (EQ 8) can be written as T.sub.1.sup.(1) (k)+h.sup.(e)(1) x.sub.kn+k-2 +h.sup.(o)(1) x.sub.kn+k-1 =0. Therefore, using (EQ 6), v.sub.8 (k) can be written as

However, h.sub.(e)(1) =1 and h.sup.(o)(1) =0, thus (EQ 14) simplifies to

Similarly, (EQ 12) can be written as T.sub.1.sup.(2) (k)+h.sup.(e)(2) x.sub.kn+k-2 +h.sup.(o)(2) x.sub.kn+k-1 =0. Therefore, using (EQ10), v.sub.9 (k) can be written as

However, h.sup.(e)(2) =0 and h.sup.(o)(2) =1, thus (EQ16) simplifies to

The second embodiment of the code 2 encoder 254b is based on (EQ15) and (EQ17), and implements these equations with hardware. For example, as shown in FIG. 10, b.sub.1 (k), b.sub.5 (k), and the output of the precoder 14 via latch A (x.sub.kn+k-1) are exclusive-ORed together and output as v.sub.9 (k). Likewise, the output of the precoder 14 via latch B (x.sub.kn+k-2) and b.sub.4 (k) and b.sub.0 (k), are exclusive-ORed and provide on line 270 as v.sub.8 (k).

Referring now to FIG. 11, a third embodiment for the encoder 12c of the present invention is shown. The third embodiment for the encoder 12c provides a code with a rate 9/11, and is a cascade of two codes, code 3' and code 3". With the present invention, Code 3' is any given rate 9/10 code. Code 3" inserts a bit into each codeword received from code 3' such that the resulting codeword satisfies one parity equation after precoding by 1/(1.sym.D); the parity equation is on all codeword bits after preceding. Specifically, the code 3 encoder 12c takes 9 bits, b.sub.9k,b.sub.9k+1, . . . ,b.sub.9k+8, every time k.gtoreq.0 and produces 11 bits, v.sub.11k, v.sub.11k+1, . . . v.sub.11k+10. More specifically, code 3' takes b.sub.9k,.sub.9k+1, . . . ,b.sub.9k+8, and produces a 10 bit vector, V'.sub.10k, v'.sub.10k+1, . . . ,v'.sub.10k+9, and code 3" takes the 10 bit vector and generates 11 bits, v.sub.11k,v.sub.11k+1, . . . ,v.sub.11k+10, The notation v.sub.i (k),i.epsilon.{0,1, . . . ,10} is used for V.sub.11k+i, and the notation v'.sub.i (k),i.epsilon.{0,1, . . . ,9}, for v'.sub.10k+i, and b.sub.i (k),i.epsilon.{0,1, . . . ,8}, is used for b.sub.9k+i. For this third code, it is desirable that: ##EQU12## for every k.gtoreq.0, where x.sub.i is the output of a 1/(1.sym.D) precoder corresponding to input v.sub.i. Lemma 1 and Corollary 1.1 are used for n=10 to compute a.sub.q, for q.epsilon.{0,1, . . . ,10} the following values: ##EQU13## Therefore, the control integers are 0, 2, 4, 6, 8 and 10, and T.sub.1 (k) is

Using Corollary 1.2, with n=10 and r=11, code 3" is characterized as:

cs(k)=Current state at time k.gtoreq.0,

cs(0)=Current state at time 0=x.sub.-1,

ns(k)=Next state at time, k.gtoreq.0 ##EQU14## The present invention uses bit 10 as a control integer to force the equation

for all k.gtoreq.0. Therefore, the output, v, of the code 3" is described by the following equations.

As shown in FIG. 11, the third embodiment of the encoder 12c includes a serial-to-parallel converter 350, a parallel-to-serial converter 352, a first code generator 354, and a second code generator 356. Unlike the first two embodiment, the third embodiment utilizes a plurality of cascaded code generators. The serial-to-parallel converter 350 has an input and plurality of outputs, and is preferably a one-to-eight converter. The serial-to-parallel converter 350 receives a serial string having a predetermined number of bits, and provides those bits in parallel at its outputs. The input of the serial-to-parallel converter 350 is coupled to line 22 to receive the binary string b.sub.0,b.sub.1,b.sub.2, . . . Each of the outputs of the serial-to-parallel converter 350 is coupled to a respective input of the first code generator 354. The first code generator 354 preferably provides a plurality of input and a plurality of outputs. For example, the first code generator 354 has eight inputs and nine outputs. As has been noted above, the first code generator 354 may be any one of a number of 8/9 rate code generators. The first code generator 354 uses the input string to generate a code 3' sequence. The nine parallel outputs of the first code generator 354 are preferably coupled to the first nine respective inputs of the parallel-to-serial converter 352 to generate the bits v.sub.0 through v.sub.9 according to the above equations. In this embodiment, the parallel-to-serial converter 352 preferably has a plurality of inputs (eleven) and an output. The parallel-to-serial converter 352 receives a predetermined number of bits in parallel and converts them into a serial string of bits, v.sub.0,v.sub.1,v.sub.2, . . . The output of the parallel-to-serial converter 352 is coupled to line 24 to provide the encoded sequence. One input of the parallel-to-serial converter 352, v.sub.10 is coupled to line 372 to receive an additional bit from the second code generator 356. The second code generator 356 preferably has a plurality of inputs which are coupled to receive v'.sub.0 (k) through v'.sub.9 (k) from the first code generator 354. The second code generator 356 produces an additional bits, v.sub.10 (k) according to the equations immediately above. This additional bit is sent to the parallel-to-serial converter 352 and is used as bit v.sub.10 (k). The second code generator 356 in the present invention has several embodiment 356a, and 356b, which will be described in more detail below with reference to FIGS. 13 and 14.

Referring now to FIG. 12, a third embodiment of the decoder 20c for decoding signals encoded with code 3, is shown. The decoder 20c preferably comprises a serial-to-parallel converter 360, a parallel-to-serial converter 362 and a code 3' decoder 364. The serial-to-parallel converter 360 preferably has an input and eleven outputs, and converts an input string into eleven parallel bits. The input of the serial-to-parallel converter 360 is coupled to line 30 to receive the sequence output by the detector 18. The code 3' decoder 364 preferably has a plurality (ten) of input and a plurality (nine) of outputs. The inputs of the code 3' decoder 364 are coupled to receive ten of the eleven outputs, u.sub.0 (k) through u.sub.9 (k), of the serial-to-parallel converter 360. Of the nine outputs of the code 3' decoder 364 are likewise coupled to respective inputs of the parallel-to-serial converter 362. The parallel-to-serial converter 362 preferably has nine inputs and an output, and converts the nine input parallel bits into a string. The output of the parallel-to-serial converter 362 is coupled to line 32 to provide the reconstructed input string.

Referring now to FIG. 13, a first embodiment for the code 3" code generator 356a is shown. The first embodiment for the code 3" code generator 356a is a hardware implementation of the equation v.sub.10 (k)=cs(k)+v.sub.0 (k)+v.sub.2 (k)+v.sub.4 (k)+v.sub.6 (k)+v.sub.8 (k). As shown in FIG. 13, a first group of outputs, v'.sub.1 (k), v'.sub.3 (k),v'.sub.5 (k),v'.sub.7 (k), and v'.sub.9 (k) from the code 3' encoder 354 are exclusive-ORed and applied to the input of the first latch to produce through delay and a second latch the cs(k) signal. The initial state of latch 2 is Cs (0)=x.sub.-1. This signal is in turn exclusive-ORed with a second group of outputs, v'.sub.0 (k),v'.sub.2 (k),v'.sub.4 (k),v'.sub.6 (k), and v'.sub.8 (k) to produce the v.sub.10 (k) signal on line 372.

A second embodiment of code 3" encoder 356b is shown in FIG. 14. Based on Corollary 1.4, EQ20 can be written as T.sub.1 (k)+x.sub.kn+k-1 =0. Therefore, using (EQ18), v.sub.10 (k) can be written as v.sub.10 (k)=v.sub.0 (k)+v.sub.2 (k)+v.sub.4 (k)+V.sub.8 (k)+x.sub.kn+k-1. The second embodiment of code 3" encoder 356b is based on and implements the above equation in hardware.

While the present invention has been described above with reference to specific preferred embodiments, the description is illustrative of the invention and is not to be construed as limiting the invention. For example, one specific modification is that the desired parity after precoding requires a mod n for some n>2 arithmetic, since mod 2 arithmetic has be considered in detail above. Various other modifications to the present invention can be made to the preferred embodiments by those skilled in the art without departing from the true spirit and scope of the invention as defined by the appended claims.

Necessary & Sufficient Conditions To Produce A Code With A Pre-Selected Parity Structure After Precoding

The following lemma gives a necessary and sufficient conditions on the coded sequence v.sub.0 v.sub.1 v.sub.2 . . . such that consecutive blocks of length n+1 of 1/(1.sym.D) precoder output sequence, x.sub.0 x.sub.1 x.sub.2 . . . , satisfy a given parity equation, for some integer n>0.

LEMMA 1: Let a binary sequence x.sub.0 x.sub.1 x.sub.2 . . . be the output of a 1/(1.sym.D) precoder corresponding to a binary input sequence v.sub.0 v.sub.1 v.sub.2 . . . ; let x.sub.1 be the initial value of the precoder; let {i.sub.1, i.sub.2, . . . , i.sub.r } be a non-empty subset of J={0, 1, 2, . . . , n}, for some integer n.

Then ##EQU15## for every integer k.gtoreq.0 if and only if

for every integer k.gtoreq.0, where ##EQU16## and where v.sub.-1 =x.sub.-1, and for q.epsilon.{0,1, . . . ,n}, ##EQU17## (Note, arithmetic is mod 2 except stated otherwise.) PROOF:

The output of 1/(1.sym.D) precoder relates to its input according to EQ5 below.

Therefore, for every integer m.gtoreq.0, ##EQU18##

Now using EQ6, we can write EQ1 as ##EQU19##

We break the second sum into two sums as follows. ##EQU20##

Therefore, for every integer k.gtoreq.0, EQ1 is equivalent to ##EQU21##

The double summation in the above equation is the same as T.sub.1 (k), hence, EQ2 follows from EQ9. Q.E.D.

We call EQ2 the pre-precoder-parity (p.sup.3) equation for 1/(1.sym.D), and we refer to an integer q in q={0, 1, . . . , n} as a control integer if a.sub.q =1.

The following corollaries are direct consequences of Lemma 1.

COROLLARY 1.1: Let {i.sub.1, i.sub.2, . . . , i.sub.r }={0,1,2, . . . , n}=J, for a positive integer n., then for q.epsilon.{0,1, . . . ,n}, we have

a.sub.q =1 if (q+n) is even,

a.sub.q =0 if (q+n) odd.

COROLLARY 1.2: EQ1 can be forced at the output of a 1/(1.sym.D) precoder by a finite state machine having at time k: ##EQU22## where one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted to force (p.sup.3) equation for 1/(1.sym.D), i.e., at time k=0, the equation T.sub.1 (k)+rx.sub.-1 =0, and at time k.gtoreq.1, the equation T.sub.1 (k)+rT.sub.2 (k)=0. Equivalently, one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted to satisfy the equation T.sub.1 (k)+rcs(k)=0, for all k.gtoreq.0. Note that q is a control integer here.

Note that cs (k) and ns (k) become rT.sub.2 (k) and rT.sub.2 (k+1), respectively.

COROLLARY 1.3: If r is even, then cs (k)=ns (k)=0 for all k.gtoreq.0.

Therefore, no state information need to be kept, and the finite state machine reduces to a block encoder.

COROLLARY 1.4: T.sub.2 (k)=x.sub.kn+k-1.

This follows from EQ6. Among consequences of this corollary are: (1) the (p.sup.3) equation for 1/(1.sym.D) can be written as T.sub.1 (k)+rx.sub.kn+k-1 =0, (2) cs (k) and ns (k) become rx.sub.kn+k-1 and rx.sub.(k+1)n+k, respectively. Therefore, the output of the precoder at time kn+k-1 can act as current state at time k for the finite state machine of corollary 1.2.

Advantage of using the output of the precoder for computing current state, as described above, is that errors don't propagate.

COROLLARY 1.5: In Corollary 1.2, the next state, ns (k), can be computed as ##EQU23##

This follows from the fact that T.sub.1 (k)+cs (k)=0 (note arithmetic is mod 2).

The following lemma gives a necessary and sufficient conditions on the coded sequence v.sub.0 v.sub.1 v.sub.2 . . . such that consecutive blocks of length n+1 of 1/(1.sym.D.sup.2) precoder output sequence, x.sub.0 x.sub.1 x.sub.2 . . . , satisfy a given parity equation, for some integer n.gtoreq.0.

LEMMA 2: Let a binary sequence x.sub.0 x.sub.1 x.sub.2 . . . be the output of a 1/(1.sym.D.sup.2) precoder corresponding to a binary input sequence v.sub.0 v.sub.1 v.sub.2 . . . ; let x.sub.-1 and x.sub.-2 be the initial values of the precoder; let {i.sub.1,i.sub.2, . . . , i.sub.r } be a set of distinct integers belonging to J={0, 1, 2, . . . , n}, for some integer n. Then ##EQU24## for every integer k.gtoreq.0 if and only if

for every integer k.gtoreq.0, where ##EQU25## and where v.sub.-1 =x.sub.-1, and v.sub.-2 =x.sub.-2, and for q.epsilon.{0,1, . . . ,n}, ##EQU26## (Note, arithmetic is mod 2 except states otherwise.) .left brkt-bot.x.right brkt-bot. and .left brkt-top.x.right brkt-top. are the floor and ceiling functions of x, respectively.)

PROOF:

The output of 1/(1.sym.D.sup.2) precoder relates to its input according to EQ15 below.

Therefore, for every integer .left brkt-bot.k/2.right brkt-bot..gtoreq.l.gtoreq.0, ##EQU27##

Now using EQ16, we can write EQ11 as ##EQU28## where j=kn+k. We break the second sum into two sums as follows. ##EQU29##

The above can be written as ##EQU30##

The first double summation is the same as T.sub.1 (k), and the second double sum can be broken into two double sums S (odd) and S (even) as follows. ##EQU31##

The sum, S (odd) can be written as ##EQU32## and S (even) can be written as ##EQU33##

Now, S (odd)+S (even)=T.sub.2 (k). To see this, use a change of variable q=(j+i.sub.t -2m-1)/2 in S (odd), and a change of variable q=(j+i.sub.t -2m)/2 in S (even). Hence, EQ12 follow from EQ19. Q.E.D.

We call EQ12 the pre-precoder-parity (p.sup.3) equation for 1/(1.sym.D.sup.2), and we refer to an integer q in {0, 1, . . . , n} as a control integer if a.sub.q =1.

The following corollaries are direct consequences of Lemma 2.

COROLLARY 2.1: Let {i.sub.1, i.sub.2, . . . , i.sub.r 56 =0, 1, 2, . . . , n}=J, for a positive integer n, then for q.epsilon.{0,1, . . . ,n} and an even n, we have

a.sub.q =1 if (q+n) is 0 or 3 (mod4),

a.sub.q =0 otherwise, ##EQU34## and for odd n, we have ##EQU35##

Recall that arithmetic is mod 2 except stated otherwise.

COROLLARY 2.2: EQ11 can be forced at the output of a 1/(1.sym.D.sup.2) precoder by a finite state machine having at time k: ##EQU36## where S (k)={kn+k, kn+k+1, . . . , kn +k +n}, and one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted to force (p.sup.3) equation for 1/(1.sym.D.sup.2), i.e., at time k=0, the equation T.sub.1 (k)+a.sup.(e) (0)x.sub.-2 +a.sup.(o) (0)x.sub.-1 =0, and at time k.gtoreq.1, the equation T.sub.1 (k)+T.sub.2 (k)=0. Equivalently, one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted to satisfy the equation T.sub.1 (k)+a.sup.(e) (k)cs.sub.1 (k)+a.sup.(o) (k)cs.sub.2 (k)=0, for all k.gtoreq.0. Note that q is a control integer here. Note that a.sup.(e) (k)cs.sub.1 (k)+a.sup.(o) (k)cs.sub.2 (k) and a.sup.(e) (k)ns.sub.1 (k)+a.sup.(o) (k)ns.sub.2 (k) become T.sub.2 (k) and T.sub.2 (k+1), respectively.

COROLLARY 2.3: If a.sup.(e) (k) and a.sup.(o) (k) are even for all k.gtoreq.0, then cs(k)=ns (k)=(0, 0) for all k.gtoreq.0.

Therefore, no state information need to be kept, and the finite state machine reduces to a block encoder. This condition arises when n+1 is even and number of even i.sub.t is even and number of odd i.sub.t is even. ##EQU37##

To see this, let i.sup.(e) (k) denotes the largest even integer less than kn+k, and let i.sup.(o) (k) denote the largest odd integer less than kn+k, then using EQ16, T.sub.2 (k) of EQ14 can be written as

However, the right side of EQ20 equals h.sup.(e)x.sub.kn+k-2 +h.sup.(o)x.sub.kn+k-1.

Among consequences of this corollary are that the (p.sup.3) equation for 1/(1.sym.D.sup.2) can be written as

further cs(k) become ##EQU38##

Therefore, the output of the precoder at times kn+k-1 and kn+k-2 can provide the current state at time k for the finite state machine of corollary 2.2. Again, advantage of using the output of the precoder for computing current state as described above is that errors don't propagate. ##EQU39##

On the other hand, if n is even, then ##EQU40## where ›x!.sub.2 denotes the remainder of division x.div.2.

COROLLARY 2.6: If n is odd, then EQ11 can be forced at the output of a 1/(1.sym.D.sup.2) precoder by a finite state machine having at time k: ##EQU41## where S (k)={kn+k, kn+k+1, . . . , kn+k+n}, and one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted to force (p.sup.3) equation for 1/(1.sym.D.sup.2). More specifically, one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted such that T.sub.1 (k)+cs (k)=0.

This corollary follows from Lemma 2 and Corollary 2.5. We note that the next state ns (k) can be computed alternatively by ##EQU42## since T.sub.1 (k)+cs(k)=0.

The following two corollaries are similar to Corollary 2.6, however, they are for the case of even n.

COROLLARY 2.7: If n is even, then EQ11 can be forced at the output of a 1/(1.sym.D.sup.2) precoder by a finite state machine having at time k: ##EQU43## where one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted to force (p.sup.3) equation for 1/(1.sym.D.sup.2). More specifically, one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted such that T.sub.1 (k)+cs (k)=0.

Before proving this corollary, we define the following sums: ##EQU44## where v.sub.-1 =x.sub.-1 and v.sub.-2 =x.sub.-2. Based on these sums, EQ14 can be written as

Now we prove Corollary 2.7 by induction. First, for k=0, we have:

Condition 1(0): ns.sub.1 (0)=R.sup.(e) (1)a.sup.(o) (1)+R.sup.(o) (1)a.sup.(e) (1),

Condition 2(0): ns.sub.2 (0)=R.sup.(e) (1)a.sup.(e) (1)+R.sup.(o) (1)a.sup.o (1),

Condition 3(0): T.sub.2 (1)=cs.sub.2 (1)=ns.sub.2 (0).

To see these, let's consider one of the above conditions, let's say Condition 1(0). Now, based on the hypotheses of this corollary we have ##EQU45##

Therefore, substituting (EQ 22) into (EQ 23) we obtain ##EQU46##

Thus, Condition 1(0) follows from Corollary 2.5 and the definition of sums R.sup.(o) (k) and R.sup.(e) (k). Now let's assume Conditions 1-3 hold for some non-negative integer k. Therefore, we have

Condition1(k): ns.sub.1 (k)=R.sup.(e) (k+1)a.sup.(o) (k+1)+R.sup.(o) (k+1)a.sup.(e) (k+1),

Condition2(k): ns.sub.2 (k)=R.sup.(e) (k+1)a.sup.(e) (k+1)+R.sup.(o) (k+1)a.sup.(0) (k+1),

Condition3(k): T.sub.2 (k+1)=CS.sub.2 (k+1)=ns.sub.2 (k).

Next, we show Conditions 1-3 will hold for k+1.

(Proof of Condition 1(k+1)) Based on the hypotheses of this corollary we have ##EQU47##

However, we have cs.sub.2 (k+1)=ns.sub.2 (k), therefore, using Condition 2(k), the above equality becomes ##EQU48## where k'=k+1. Using Corollary 2.5, (EQ 24) simplifies to ns.sub.1 (k+1)=R.sup.(e) (k+2)a.sup.(o) (k+2)+R.sup.(o) (k+2)a.sup.(e) (k+2).

We omit the proof of Condition 2(k+1) since it is very similar to the above. Condition 3(k+1), then, follows directly from definitions.

Therefore, the finite state machine of Corollary 2.7 satisfies EQ12 for all k.gtoreq.0. Finally, we note that ns.sub.1 (k) can be computed by ##EQU49## since T.sub.1 (k)+cs.sub.2 (k)=0.

The next finite state machine is yet another way of forcing EQ11 based on Lemma 2.

COROLLARY 2.8: If n is even, then EQ11 can be forced at the output of a 1/(1.sym.D.sup.2) precoder by a finite state machine having at time k: ##EQU50## where S (k)={kn+k, kn+k+1, . . . , kn+k+n}, and one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted to force (p.sup.3) equation for 1/(1.sym.D.sup.2). More specifically, one bit v.sub.kn+k+q in the output, q such that a.sub.q =1, is adjusted such that

T.sub.1 (k)+cs.sub.2 (k)=0 if k is even,

T.sub.1 (k)+cs.sub.1 (k)=0 if k is odd.

To prove this corollary use an induction.

LEMMA 3: If more than one parity equation is to hold at the output of a 1/(1.sym.D) or 1/(1.sym.D.sup.2) precoder, then

(a) each parity equation would produce a pre-precoder-parity equations of its own on the input of the precoder, and the input must satisfy all these conditions simultaneously, furthermore,

(b) if the parity equations are independent, then their (p.sup.3) equations are independent, and a distinct control integer must be chosen in order to force each (p.sup.3) equation.

PROOF:

Part (a) is a straightforward generalization of Lemmas 1 and 2, and part (b) follows from the fact that the map from {i.sub.1 i.sub.2 . . . i.sub.r } to {a.sub.0,a.sub.1, . . . , a} is invertible for both 1/(1.sym.D) and 1/(1.sym.D.sup.2). We remark that we can always start with a set of independent parity equations by eliminating dependent equations one by one.