**SYSTEM AND METHOD FOR SPECTRALLY SHAPING TRANSMITTED DATA SIGNALS**

JP3442279 | CONTROL DEVICE FOR MATERIAL TESTING MACHINE |

JPS59182647 | DATA COMPRESSING SYSTEM |

JPH09321810 | SERIAL DATA COMMUNICATION SYSTEM |

Kim, Dae-young (6231 Lexington Ridge Drive, Lexington, MA, 02173, US)

Tung, Chien-cheng (2509 Francis Avenue, Mansfield, MA, 02048, US)

*;*

**H03M5/00***;*

**H04B14/04***;*

**H04L25/49***; (IPC1-7): H04B14/04; H04K1/10*

**H04L27/18**US5548615A | ||||

US5040191A | ||||

US5608397A | ||||

US5150381A |

1. | A system for transmitting from a transmitter, on a per frame basis, digital information bits which are encoded into a predefined number of signed symbols per frame for transmission over a network to a receiver, wherein the transmitted 6igned symbols have a desired spectral shape; the digital information bits being divided into a first predetermined number of magnitude information bits and a second predetermined number of sign information bits per frame, the transmitter comprising: a magnitude mapping device for mapping the magnitude information bits to the predefined number of symbol magnitudes per frame; a sign bit encoder for encoding the sign information bits into the predefined number of encoded symbol sign bits per frame; and a signal point selector, responsive to the magnitude mapping device and the sign bit encoder, which combines the symbol magnitudes and the encoded symbol sign bits to form the predefined number of transmitted signed symbols per frame; the sign bit encoder comprising: a coset representative generator which generates for each frame, coset representative sign bits for the sign information bits, defining a coset representative element for a convolutional code which identifies a coset of the convolutionat code containing candidates of encoded symbol sign bits; and a symbol sign bit selector, responsive to the coset representative sign bits and the symbol magnitudes, which selects the encoded symbol sign bits from the candidates of encoded symbol sign bits that produce the transmitted signed symbols with the desired spectral shape. |

2. | The systern of claim 1 wherein the first predetermined number of magnitude information bits is rn bits and the second predetermined number of sign information bits is nrbits, where n corresponds to the predefined number of symbols per frame and rcorresponds to a number of redundancy bits used by the sign bit encoder, 3. |

3. | The system of claim 2 wherein the coset representative generator includes a difterential encoder to differentlally encode predetemtined bit positions of the nrbits provided to the sign bit encoder to achieve polarity inversion invariance. |

4. | The system of claim 3 wherein the magnitude mapper maps the m magnitude information bits to n symbols per frarne using a modulus conversion mapping scheme. |

5. | The system of claim 4 wherein the coset representative generator further includes a matrix block, which multiplies the nr sign information bits by a matrix, HT, to produce the n coset representative sign bits per frame. |

6. | The system of claim 5 wherein the symbol sign bit selector Includes a selection controller and a filter; wherein the selection controller includes: logic for generating from the coset representative sign bits candidates of encoded symbol sign bits; logic for combing the candidates of encoded symbol sign bits with the symbol magnitudes to form encoded signed symbol candidates; wherein the filter includes: logic, responsive to the encoded signed symbol candidates, for determining the RFS for each of the encoded signed symbol candidates and logic for providing the RFS for each of the encoded signed symbol candidates to the selection controller; and wherein the selection controller further includes: logic, responsive to the determined RFS for each of the encoded signed symbol candidates, for choosing the encoded symbol sign bits associated with the encoded signed symbol candidate with the minimum determined RFS,. |

7. | The system of claim 5 wherein the symbol sign bit selector utilizes look ahead and includes a selection controller and a filter; wherein the selection controller includes: logic for generating from the coset representative sign bits candidate sequences of encoded symbol sign bits; logic for combing the candidate sequences with the symbol magnitudes to form encoded signed symbol candidate sequences; wherein the filter includes: logic, response to the encoded signed symbol candidate sequences, for determining the PFS for each of the encoded signed symbol candidate sequences and logic for providing the RFS for each of the encoded signed symbol candidate sequences to the selection controller; and wherein the selection controller further includes; logic, responsive to the determined HFS for each of the encoded signed symbol candidate sequences, for choosing the encoded symbol sign bits from the encoded signed symbol candidate with the minimum determined RFS. |

8. | The system of claim 7 wherein the RFS for the ith symbol is determined by the filter as follows:. |

9. | The system of claim 8 wherein the RFS is determined on a frame basis for the kth frame by the filter as follows: where j is the symbol (time) index. |

10. | The system ot claim 9 wherein the RFS is determined using lookahead as follows: where d is the lookahead depth. |

11. | The system of claim 10 wherein the receiver includes a magnitude and sign extractor which separates the transmitted signed symbols into the encoded symbol sign bits and symbol magnitudes and a sign bit decoder which decodes the encoded symbol sign bits into the sign information bits. |

12. | The system of claim 11 wherein the sign bit decoder includes a matrix block having a matrix HT by which the encoded symbol sign bits are multiplIed to recover the sign information bits. |

13. | The system of claim 12 further including a differential decoder which differentially decodes the predefined bit positions of the recovered sign information bits. |

14. | The system of claim 13 further including an octet converter, responsive to the signal point selector, for transmitting over the network octets corresponding to the signed symbols. |

15. | The system of claim 13 wherein n is equal to six, r is equal to one and matrix H#T is defined as follows: 0 o 0 O O 1/(1+D) 0 0 O O 1/(1+D) O H#T = 0 0 0 1/(1+D) 0 0 0 0 1/(1+D) O 0 0 0 1/(1+D) 0 0 0 0. |

16. | The system of claim 15 wherein convolutional code is defined as follows: G(D) = [1+D 1 1+D 1 1+D 1]. |

17. | The system of claim 16 wherein the matrix H' is defined as follows: 1 1+D 1 1+D 1 O 0 0 0 1+D o 0 0 0 1+D 0 H@ = 0 0 0 1+D 0 0 o l+D 0 0 0 1+D 0 0 0 0 15. |

18. | The system of claim 7 wherein the RFS is the running digital sum (RDS) and the RDS for the ith symbol is determined by the filter as follows: where j is the symbol (time) index. |

19. | The system of claim 18 wherein the RDS is determined on a frame basis for the kth frame by the equivalence class selector as follows: where j is the symbol (time) index. |

20. | The system of claim 19 wherein the RDS is determined using look ahead as follows: where A is the lookahead depth. |

21. | A method for transmitting from a transmitter, on a per frame basis, digital information bits which are encoded into a predefined number of signed symbols per frame for transmission over a network to a receiver, the symbols having a desired spectral shape, the digital information bits being divided into a first predetermined number of magnitude information bIts and a second predetermined number of sign information bits per frame, the method comprising; mapping the magnitude information bits to the predefined number of symbol magnitudes per frame: encoding the sign information bits Into the predefined number of encoded symbol sign bits per frame; and combining the symbol magnitudes and the encoded symbol sign bits to form the predefined number of transmitted signed symbols per frame; the step of encoding including: generating for each frame coset representative sign bits for the sign information bits, defining a coset representative element for a convolutional code which identifies a coset of the convolutional code containing candidates of encoded symbol sign bits; and selecting, using the coset representative sign bits and the symbol magnitudes, the encoded symbol sign bits from the candidates of encoded symbol sign bits that produce the transmitted signed symbols with the desired spectral shape. |

22. | The method of claim 21 wherein the first predetermined number of magnitude information bits is m bits and the second predetermined number of sign information bits is nZr bits, where n corresponds to the predefined number of symbols per frame and r corresponds to a number of redundancy bits used in the encoding step. |

23. | The method of claim 22 wherein the step of generating includes differentially encoding predetermined bit positions of the nrbits to achieve polarity inversion invariance. |

24. | The method of claim 23 wherein the step of mapping maps the m magnitude Information bits to n symbols per frame using a modulus conversion mapping scheme. |

25. | The method of claim 24 wherein the step of generating further includes multiplying the n.rsign information bits by a matrix, H , to produce the n coset representative sign per frame. |

26. | The method of claim 25 wherein the step of selecting includes: generating from the coset representative sign bits candidates of encoded symbol sign bits; combing the candidates of encoded symbol sign bits with the symbol magnitudes to form encoded signed symbol candidates; determining the RFS for each of the encoded signed symbol candidates and logic for providing the RFS for each of the encoded signed symbol candidates to the selection controller, and choosing the encoded symbol sign bits associated with the encoded signed symbol candidate with the minimum determined RFS. |

27. | The method of claim 25 wherein the step of selecting utilizes look ahead and includes: generating from the coset representative sign bits candidate sequences of encoded symbol sign bits; combing the candidate sequences with the symbol magnitudes to form encoded signed symbol candidate sequences; determining tha FlFS for each of the encoded signed symbol candidate sequences and logic for providing the RFS for each of the encoded signed symbol candidate sequences to the selection controller; and choosing the encoded symbol sign bits from the encoded signed symbol candidate with the minimum determined RFS. |

28. | The method of claim 27 wherein the RFS tor the ith symbol is determined as follows:. |

29. | The method of claim 28 wherein the RFS Is determined on a frame basis for the I:th frame as follows: where j is the symbol (time) Index. |

30. | The method of claim 29 wherein the RFS is determined using look ahead as follows: where A is the lookahead depth. |

31. | The method of claim 30 furttrer including, in the receiver, separating the transmitted signed symbols into the encoded symbol sign bits and symbol magnitudes and decoding the encoded symbol sign bits into the sign informatlon bits. |

32. | The method of claim 31 wherein the step of decoding includes <BR> <BR> <BR> multiplying by a matrix @ HT the encoded symbol sign bits to recover the sign Information bits. |

33. | The method of claim 32 further including differentially decoding the predetermined bit positions of the recovered sign informatlon bits. |

34. | The method of clairn 33 further including transmitting over the network octets corresponding to the signed symbols. |

35. | The method of claim 33 wherein n is equal to six, r is equal to one and matrix H.T is defined as follows; 0 0 0 0 0 1/(1+D) 0 O O o ll(1+ D) 0 H#t = 0 0 0 1/(1+D) 0 0 O O 1/(1+D) 0 0 0 0 ll(l+D) 0 0 0 0. |

36. | The method of claim 35 wherein convolutional code is defined as follows; G(D) = [1+D 1 1+D 1 1+D 1]. |

37. | The method of claim 36 wherein the matrix HT is defined as follows: 1 1+D 1 1+D 1 O 0 0 O 1+D HT = 0 0 0 1+D 0 o 0 1+D 0 0 o 1+D 0 0 O 1+D 0 0 0 0. |

38. | The method of claim 27 wherein the RFS is the running digital sum (RDS) and the RDS for the ith symbol is determined as follows: where j is the symbol (time) index. |

39. | The method of claim 38 wherein the RDS is determined an a frame basis for the kth frame as follows: where j is the symbol (time) index. |

40. | The method of claim 39 wherein the RDS is determined using look ahead as follows: where A is the lookahead depth. |

41. | In a transmitter, a system for precoding, on a per frame basis, digital information bits into a predefined number of precoded levels per frame; the digital information bits being divided into a first predetermined number of magnitude information bits and a second predetermined number of sign information bits per frame, the system comprising; a magnitude mapping device for mapping the magnitude information bits to the predefined number of symbol magnitudes per frame; a sign bit encoder for encoding the sign information bits into the predefined number of encoded symbol sign bits per frame: a signal point selector, responsive to the magnitude mapping device and the sign bit encoder, which combines the symbol magnitudes and encoded symbol sign bits to form the predefined number of signed symbols per frame and outputs the precoded levels corresponding to the signed symbols; the sign bit encoder comprising: a coset representative generator which generates for each frame, coset representative sign bits for the sign information bits, defining a coset representative elemont for a convolutional code which identIfies a coset of the convolutional code containing candidates of encoded symbol sign bits; and a symbol sign bit selector, responsive to the coset representative sign bits and the symbol magnitudes, which selects the encoded symbol sign bits from the candidates of encoded symbol sign. |

42. | In a transmitter, a method for precoding, on a per frame basis, digital information bits into a predefined number of precoded levels per frame; the digital information bits being divided into a first predetermined number of magnitude information bits and a second predetermined number of sign information bits per frame, the method comprising; mapping the magnitude information bits to the predefined number of symbol magnitudes per frame; encoding the sign Information bits into the predefined number of encoded symbol sign bits per frame; combining the symbol magnitudes and encoded symbol sign bits to form the predefined number of signed symbols per frame and outputting the precoded levels corresponding to the signed symbols; the step of encoding comprising: generating for each frame coset representative sign bits for the sign information bits, defining a coset representative element for a convolutional code which identifies a coset of the convolutional code containing candidates of encoded symbol sign bits; and selecting, using the coset representative sign bits and the symbol magnitudes, the encoded symbol sign bits from the candidates of encoded symbol sign. |

43. | A receiver for receiving from a network, on a per frame basis. digital Information bits which have been encoded into a predefined number of signed symbols per frame by a transmitter, wherein the transmitted signed symbols have a desired spectral shape; the digital information bits being divided into a first predetermined number of magnitude information bits and a second predetermined number of sign information bits per frame, the receiver comprising: a magnitude and sign extractor which separates the transmitted signed symbols into encoded symbol sign bits and encoded symbol magnitudes; a magnitude demapper which decodes the encoded symbol magnitudes into the magnitude information bits: and a sign bit decoder which decodes the encoded symbol sign bits into the sign information bits; wherein the sign bit decoder includes a matrix block having a matrix HT by which the encoded symbol sign bits are multiplied to recover the sign information blts. |

44. | The receiver of claim 43 wherein HT is defined as follows: l l+D l I+D O 0 0 0 1+D HT= 0 0 O 1+D 0 0 0 1+D 0 0 û l+D Q O 0 1+D 0 0 0 0. |

Humblet; Daeyoung Kim and David Tung; the present application is based on this application and priority thereto for common subject matter is hereby claimed; US Patent App. No. 08/747,840, entitled Device, System and Method for Spectrally Shaping Transmitted Data Signals, filed November 13, 1996, having inventors Vedat Eyuboglu and Pierre A. Humblet; and US Patent App., Attomey Docket No. CX096044P02, entitled Device and Method for Precoding Data Signals, filed December 29, 1997, having inventors M. Vedat Eyuboglu, Pierre A. Humblet; and Daeyoung Kim.

Field Of Invention This invention relates to high-speed data communications and more particularly to a system and method for spectrally shaping transmitted data signals.

Background Of Invention The public switched telephone network (PSTN) consists of a digital backbone network and analog local loops that connect end users to this backbone. In a typical telephone call, the analog signal sent by the local user is digitized at the local central office and converted into a 64 kbit/s bit stream which is carried across the digital backbone network and then converted back to analog at the remote central office for transmission to the end user over the remote local loop. Dial-up modems, e.g. V.34 modems, communicate over the PSTN by modulating the digital information into an analog signal for transmission. The digital-to-analog conversion process at the entry point to the digital backbone introduces quantization noise which limits the data transmission speed to around 30 bits.

A technique that enables transmission at speeds signlficantly higher than 30 ?(bit/s. potentially up to 56 bits, when one user has a direct connection to a digital network, for example, via ISDN or T1, has been developed. Moreover, a standardized protocol for this type of transmission exists, Intemational Telecommunications Union (ITU) standard V.90, and is expected to be ratified soon. WIth this technique, random digital information is encoded into C1-law or A-law octets (depending on the region of the world) by a digital pulse code modulation (PCM) modem using a channel encoder. The octets are mapped directly into symbols In the digital-to-analog (D/A) converter located in the end user's central office. (Unless indicated otherwise, all discussions below pertain to CL-law: the extensions to A-law are straightforward.) The mapping could use all or any subset of the 255 levels of the D/A converter, subject to regulatory restrictions on average power.

Since information is carried across the digital network in the form of octets, the encoded data is first mapped into octets for transmission at a rate of 8000 octets per second. Then, in the end user's central office, the octets are converted into corresponding symbols in the DJA converter. The resulting B kHz sequence of symbols is passed through a low pass filter (LPF) and transmitted over the analog loop to the end user's analog PCM modem. The output of the DIA converter can be viewed as a sequence of impulses each having an amplitude corresponding to one of the D/A levels. The analog PCM modem recovers the original information by first detecting which symbols were transmitted, and then inverse mapping these symbols to obtain an estimate of the original digital information.

When the information is transmitted randomly, a spectral analysis of the signal after the D/A conversion reveals that the spectrum of the sequence output by the DIA converter is essentially flat. Therefore, when this sequence Is passed through the LPF at the central office, the spectrum of the signal takes on the shape of the spectrum of the LPF. Unfortunately, this spectrum has a significant amount of energy near DC (f=O) which can drive transformers in the system into saturation and introduce unwanted non-linear distortion on the signal being transmitted. In this application, this type of distortion cannot be tolerated and therefore there is a need for its elimination.

More generally, with PCM there is a need for a scheme that can shape the spectrum ot the signal transmitted from the DIA converter. Further, there is a need for a spectral shaping scheme that is applicable to various types of transmission technologies in addition to PCM. lilirlef Description of the Drawlngs FIG. 1 is a simplified block diagram of a typical telephone company central office; FIG. 2 is plot of the frequency spectrum of the symbols, y,(, output from the CI-law to linear converter of FIG. 1 and the spectral shape of the low pass filter of FIG. 1; FIG. 3 is a plot of a portion of two frequency spectrums each having a null at DC, wherein one spectrum falls off to zero very abruptly at DC and the other spectrum falls off more gradually; FIG. 4 is schematic block diagram of a transmitter of a central site digital PCM modem configured according to this invention; FIG. 5 is a schematic block diagram of a receiver of an end user analog PCM modem configured according to this invention; FIG. 6 is a schematic block diagram of the sign bit encoder of the transmitter depicted in FIG. 4; FIG. 7 is a schematic block diagram of the coset representative generator depicted in FIG. 6; FIG. 8 Is schematic block diagram of the symbol sign bit selector of FIG.

6; FIG. 9 is a trellis diagram which represents a convolutional code; FIG. 10 is a flow diagram illustrating the generalized logic for the symbol sign bit selector as depicted in FIG. 8; FIG. 11 is a schematic block diaGram ol the sign bit decoder depicted in FIG. 5; and FIG. 12 is a schematic block diagram of the present invention utilized as a precoder in an upstream PCM transmitter.

Description of a Preferred Embodiment The present invention involves a system and method for spectrally shaping transmitted data signals that is generally applicable to various data transmission technologies. For purposes of explanation, the invention is described herein with regard to a PCM transmission system. However, persons having ordinary skill in the art will appreciate that the invention may be extended to other transmission technologies and that the PCM implementation described herein may be readily extended to those technologies.

FIGS. 1 and 2 illustrate the presence of energy near DC in the signals transmitted to an end user's analog PCM modem over an analog loop. There Is shown in FIG. 1 a portion of a typical telephone central office 10 on a PSTN which receives at input 12 u.law octets transmitted from a central site digital PCM modem (not shown) directly attached to the digital portion of the telephone system. The octets are converted by a DIA converter, also known as a @ µ-law to linear converter 14, to a sequence of symbols, y. Each of the symbols corresponds to one of 255 u-law levels. The symbols are output over line 16 to a low pass filter (LPF) 18 which outputs over analog loop 20 to the end user analog PCM modem's receiver a filtered analog signal s(t). The analog signal is demodulated and decoded by the receiving modem, which outputs a digital bit stream. The digital bit stream is an estimate of the originally transmitted data.

The sequence of symbols, y, on line 16 frorn flaw to linear converter 14 has a tlat frequency response 22, FIG. 2. The spectral shape 24 of LPF 18 contains a significant amount of energy near DC (f=D) as illustrated at point 26.

Since the sequence yW has a flat frequency response, the spectrum of the signal s(t) output by filter 18 has the same spectral shape 24 as the filter 18 and therefore the signal s(t) also contains a significant amount of energy near DC. As described above, this energy near DC tends to saturate the transformers in the system, which produces unwanted non-linear distortion in the signal s(t) transmitted to the receiving modem.

In applications such as PCM, this distortion must be reduced. This can be accomplished by reduclng the signal energy of the transmitted signal near DC to produce a DC null. Such a DC null 25 is depicted in FIG. 3. As is known in the state-of-the-art, in order to create this spectral null at DC in the transmitted signal1 the running digital sum (RDS) of the transmitted symbols, y, (namely, the algebraic sum of all previously transmitted levels) must be maintained near zero. The shape of the spectrum around DC null 28 can vary from a relatively shallow sloped spectrum 30 to a spectrum 32 which falls off very abruptly at DC. The sharpness of the null depends on how tightly the RDS is controlled.

As described below, the present invention encodes the digital data being transmitted in a manner that maintains the RDS near zero. This creates a spectral null at DC thereby reducing the non-linear distortion caused by transformer saturation. More generally, the invention may also be used to encode digital data being transmitted to shape the spectrum of the transmitted signal. as desired.

Transmitter 40, FIG. 4, in a digital PCM modem receives a serial digital bit stream 42 from data terminal equipment (not shown), such as a personal computer, and encodes the received bits into octets 44 for transmission over digital network 46. Serial bit stream 42 is converted to parallel format by serial to parallel converter 48. The transmittinglencodìng scheme of this invention is based on an symbol data frame, where k represents the data frame (time) index. For example, there may be 2, 3, 4. 5 or 6 symbols transmitted per data frame. The symbols transmitted correspond to u-law constellation points selected to represent the information bits. For each data frame, serial to parallel converter 48 outputs (n-r)+m information bits, where ris the number of redundancy bits. The number of redundancy bits as specified in the V.90 standard may be O, 1, 2 or 3.

It should be noted that for the remainder of the description lowercase variables denote scalar quantities, while uppemase variables denote matrices.

Also, row vectors are represented by a bold lowercase variables and all inidices start from 0, e.g., xk = (xk,0, xk,1,...), me n-rbits, labeled bits v represent the information carried through sign bits (the sign information bits) and the m bits, labeled bits ut, represent the information carried through the magnitudes (the magnitude information bits). The number of bits, m, can be determined by choosing m to satisfy the following: where M, is the number of positive constellation points for the i-th symbol in a data frame. This process is more fully described in the V.90 standard.

The m magnitude information bits, UK @ are provided to magnitude mapper 50 which maps the m bits to n symbol magnitudes, gk, by a mapping scheme such as a shell mapping, as described in the ITU V.34 standard, or by a modulus conversion, described in the ITU V.90 standard. The magnitudes to which the magnitude information bits are mapped are the magnitudes af the µ-law points used as constellation points in transmitting the information bits.

These magnitude mapping schemes and the constellation point selection process are understood by persons skilled in the art and further description of them need not be provided herein. The remaining information bits in the data frame, the sign information bits vk, are provided to sign bit encoder 52 which generates n sign bits, , (encoded symbol sign bits) as described in detail below. The n symbol magnitudes, gk, and the n sign blots, , are provided to signal point selector 54 and are combined to form n signed symbols yk, The n signed symbols Yea are then provided to octet converter 56 which selects an octet corresponding to each of the signed symbols and transmits the octets to digital network 46. With other transmission technologies the octet converter, which converts the signed symbols to a form compatible with the digital portion of the PSTN, may not be used and the signal point selector would output the signed symbols directly to the network.

The octets 44' exiting digital network 46 (possibly modified by digital impairments in the network) are received by central office (CO) 60. The octets 44' are converted into symbols by a DIA converter in CO 60 and transmitted as an 8 kl-Iz sequence of levels over the analog loop 62 to receiver 64 of an end user analog PCM modem. The analog levels are received by receiver front end 66, which digitizes the analog levels, performs timing recovery, equalization and symbol decision.

Receiver front end 66 outputs received symbols, y*, in serial format to serial to parallel converter 68 which converts the serial symbols into frames of n parallel signed symbols yk, The n parallel signed symbols y, are provided to magnitude and sign extractor 70 which extracts symbol magnitudes g,, and sign bits s from Yk Symbol magnitudes gk are provided to magnitude demapper 72, e.g. a modulus conversion demapper, to recover the magnitude information bits uk. Since the demapping process is understood by persons skilled in the art, it will not be explained herein, The sign bits 8,t are provided to sign bit decoder 74 to recover the sign information bits vk, as described below. The decoded information bits may then be further processed and provided to data terminal equipment, such as a personal computer.

Sign bit Encoding Sign bit encoder 52 is depicted in more detail in FIG. 6. The sign information bits Vk are provided to cost representative generator 80 which generates for each frame n coset representative sign bits t,, and provides them to symbol sign bit selector 82. The n coset representative sign bits 4 during each frame define a coset representative element tor a defined convolutional code, G(D), used by symbol sign bit selector 82 and the entire sequence of coset representative sign bits t(P) collectively define a coset representative for the convolutional code. The n coset representative sign bits 4 also identify a coset of the convolutional code which contains candidates of encoded symbol sign bits, as described in more detail below.

Using the n coset representative sign bits t,, symbol sign bit selector 62 modifies coset representative sign bits t by EXCLUSIVE OR'ing the bits with valid convolutional code sequences defined by a trellis diagram, such as the trellis diagram depicted in FIG. 9 and described below, to form the candidates of encoded symbol sign bits. These candidates are elements of the coset identified by the coset representative sign bits. With the symbol magnitudes, symbol sign bit selector 82 selects for each frame the candidate of encoded symbol sign bits rom the candidates of encoded symbol sign bits that produces the desired spectral shape and provides those sign bits to signal point selector 54, FIG. 4. The output of symbol sign bit selector 82 for the entire sequence, as opposed to on a per frame basis, may be represented as s(D)=t(D) 23 c(D), where s(D) is the sequence of encoded symbol sign bits, t(D) is the coset representative for the convolutional code and c(D) are the code sequences which are elemsnts of the convolutional code, G(D).

It should be noted that with this selection process any of the candidates of encoded symbol sign bits may be used and will be decoded, as described below, to the encoded sign intormation bits v,Thus, the present spectral shaping scheme has no affect on the symbol magnitudes and therefore does not affect the transmIt power. As a result, it is easy to design a systom to satisfy the transmitter power limitations imposed by the FCC and still accomplish spectral shaping.

Coset representative generator 80 is depicted in more detail in FIG. 7 to include differential encoder 84 and matrix block 86, Noise on the data channel might cause a polarity Inversion by affecting the transmitted sign bits.

By employing differential encoding, differential encoder 84, and decoding, differential decoder 132, FIG. 11, of the sign bits to certain bit positions, e.g., even positions 0, 2 and 4 for the HT, H4 and G(D) given below, it is possible to achieve polarity inversion invariance. The differentially encoded sign Information bits v,r'are multiplied (in modulo 2) (i.e., filtered) in matrix block 64 by matrix H4 ,, to produce the n coset representative sign bits to which are provided to symbol sign bit selector B2.

An example of this matrix when there are six (6) symbols transmitted per frame and one redundancy bit, as specified In the ITU V.90 standard, is as follows: o O O O O 1/(1+D) O 0 0 0 1/(1+D) 0 H*T O 0 0 ° 1)(1 + D) O 0 (2) o O 1/(1+D) O O O O 1/(1+D) 0 0 0 0 where D is the frame delay, which is the delay based on the frame (time) index k.

As shown in FIG. 8, symbol sign bit selector 82 includes selection controller 88 which receives the n coset representative sign bits teach frame from coset representative generator 80 and n symbol magnitudes from magnitude mapper 50, FIG. 4 and outputs encoded symbol sign bits, sk, for each frame. Selection controller 88 combines the candidates of encoded symbol sign bits with the magnitudes to form encoded signed symbol candidates, which are provided to filter 90. Filter 90 calculates a metric referred to herein as a running filter sum (RFS), described below, for each candidate and provides them to selection controller 86 which selects the encoded symbol sign bits associated with the encoded signed symbol candidate that minimizes RFS. The operation of symbol sign bit selector 82 is described below with regard to FIGS, 9 and 10.

Selection controller 88 modifies the n coset representative sign bits 1k per frame by EXCLUSIVE-ORing the coset representative sign bits with valid code sequences of the convolutional code. The convolutional code is the set of possible sequences defined by a trellis diagram and the valid code sequences are the sequences that do not violate the constraints of the trellis diagram. For purposes of description, selection controller 88 will use a single redundancy bit rand a convolutional code G(D) = [1+D 1 1+d 1 1+D 1]. Representing this in terms of a trellis diagram requires the use of a two-state trellis diagram, such as trellis diagram 100, FIG. 9. The constraints of the trellis diagram are described as follows.

For a given frame k, selection controller 88 modifies the n coset representative sign bits t,, by EXCLUSIVE-OR'ing them with certain convolutional code sequences according to the constraInts of trellis diagram 100. The convolutional code sequences in this example are as follows: A: 000000 (i.e. do nothing) B: 111111 (i.e. invert all sign bits in frame j) C: 101010 (i.e. invert even-numbered sign bits in frame j) D: 010101 (i.e. invert odd-numbered sign bits in frame j) Thus, at the beginning of a frame k if the state, Qk, of selection controller 88 is 0, only convalutional code sequences A 102 and B 104 are valid sequences in frame k. Conversely, if the state , Qk, of selection controller 88 is 1, only convolutional code sequences C 106 and D 108 are valid sequences in frame k. As described above, the coset representative sign bits are lEXCLUSlVER'ed wlth each of the valid code sequences, thereby forming candidates of encoded symbol sign bits, e.g. ( tk # A, tr d3 B). Each of the candidates is also an element of a coset of the convolutional code identified by the coset representative sign bits (or the element of the coset representative). Then, each candidate is combined with the symbol magnitudes to form encoded signed symbol candidates which are provided to filter 90, FIG. 8, where the RFS for each is calculated and returned to selection controller 88, Selection controller 88 outputs the encoded symbol sign bits for frame j that minimize the RFS.

The current state Qk , together with the convolutional code sequence of the encoded symbol sign bits selected for frame k are used to determine the next state by following the constraints of trellis diagram 100. For example, if <BR> <BR> <BR> <BR> candidate tk # $ B was selected for frame k, the state of selection controller 88 at the beginning of frame °k+1 is 1.

The spectral shaping achieved using the present invention may be improved by introducing look-ahead. That is, instead of selecting the encoded symbol sign bits based solely on the current frame, symbol sign bit selector 82 may use the symbol magnitudes produced by the magnitude mapper 50, FIG.

4, and the coset representative sign bits for the current trame and for future frames to decide which encoded symbol sign bits achieve the best spectral shaping. The V.90 standard specifies that up to three frames in the future may be used depending on the amount of look-ahead delay negotiated during startup.

The spectral shaping metric RI=S, based on a filter transfer function h(D), is computed for all possible paths (or candidate sequences) through the trellis diagram up to the look-ahead delay or depth A by filter go, and the selection controller selects the encoded symbol sign bits associated with the candidate sequence for frame k that produces the smallest RFS.

Referring again to trellis diagram 100, FIG. 9, the possible candidate sequences for a look-ahead depth of 1 is described. At the beginning of a frame k if the state, ak , of selection controller SB is 0, convolutional code sequences A 102 and 13 104 are valid sequences for frame k. However, the code sequences for frame k+1 must also be considered, Since in frame k code sequences A 102 and B 104 are valid, then in frame k+1 the state, Qk+1 could be 0 or 1 and therefore code sequences A 102', B 104', C 106' and D 108' are valid. As described above, the coset representative sign bits are EXCLUSIVE-OR'ed with each of the valid code sequences to form candidates of encoded symbol sign bits. With look-ahead, the coset representative sign bits for each frame k and k+1 are EXCLUSIVE-OR'ed with the valid code sequences in each path of the trellis diagram thereby forming candidate sequences. The candidate sequences In this example are the following four sequences: {1) (tk # A, tk+1 # A); 2) (tk # A, tk+1 # B); 3) (tk # B, tk+1 # C); and 4) (t, {3 B, tX i3 D)). The RFS for each sequence is determined and the candidate encoded symbol sign bits for frame k in the determined sequence is chosen.

In FIG. 10, flow chart 120 describes the operation of symbol sign bit selector 82. In step 122, selection controller SB generates the candidates (or candidate sequences in the case of look-ahead) of encoded symbol sign bits by rnodifying the coset representative sign bits according to the trellis diagram.

Then, in step 124 selaction controller combines the symbol magnitudes and the candidates of encoded symbol sign bits to form encoded signed symbol candidates (or candidate sequences) and provides theft to filter 90. In step 126, filter 90 determines the RFS for each candidate (or candidate sequence) and provides the RFS for each candidate (or candidate sequence) to selection controller 88. Finally, in step 12it, selection contmller 88 chooses the candidate of encoded symbol sign bits (or candidate sequence) that minimizes RFS and sends the encoded symbol sign bits.

It must be noted that this invention may utilize various convolutional codes, G(D), which are represented by different trellis diagrams and different convolutional code sequences. The extension to various convolutional codes and code sequences in light of the description herein will be straightforward to persons of ordinary skill in the at, In general, with PCM, the spectral shaping scheme according to this invention, shapss the spectrum of the analog signal transmitted from the D/A converter in CO 60, FIG. 5, by setting the response of filter 90, FIG. 8, to achieve a desired spectral shape and by minimizing the RFS. The response, h(d), of fitter 90, which defines the desired spectral shape, may be expressed as follows: where A(D) and B(D) are functlons and a and b are real numbers chosen to achieve the desired spectral shape. And, NA and Na are the number of coefficients used for tha numerator and denominator, respectively, to represent h(D), The RFS on a symbol-by.symbol basls may be calculated as follows: and the RFS on a frame basis for the kth frame may be calculated as follows; where j is the symbol (time) index.

When using the sign bit encoder of the present invention to create a spectral null at DC, the RFS is the running digital sum (RDS) and the response, h(D), of filter 90 Is expressed as follows: h(D)=i-D (6) From the transmitted signed symbols yak filter 90 calculates the RDS of transmitted signed symbols Yak at symbol time ias follows: where j is the symbol (time) index and the RDS on a frame basis for the kth frame may be calculated as follows: where j is the symbol (time) index.

For look-ahead, with a look-ahead depth , the RDS is calculated as follows: where LRDS is the look-ahead RDS. We can similarly introduce look-ahead to generally minimize RFS as follows: Sign Blt Decoding Sign bit decoder 74 in receiver 64, FIG. 5, is shown in FIG 11 to include a matrix block 110. In matrix block 110 the sign bits sk are multiplied (in modulo 2) (i.e., filtered) by matrix H7@x(n-1) to recover the differentially encoded sign information bits v'.

An example of matrix HT when there are six symbols transmitted per frame (n=6) and one redundancy bit (r=1) is shown in equation (11) as follows: 1 1+D 1 1+D 1 O 0 0 O 1+D o 0 0 1*D 0 HT= 0 0 1+D 0 0 (11) O l+D O 0 0 1+D 0 0 0 0 The matrix HT is designed so that the decision error in value to error in the received sign signal 1a will not propagate more than one frame. This Is because HT is a finite impulse response (FIR) type of matrix and there is only a single delay.

In order to demonstrate how the each of the candidates of encoded symbol sign bits generated by sign bit encoder 52, FIG. 4, for each frame of symbols to be transmitted are decoded to the same sign information bits, the encoding and decoding processes must be expressed mathematically. The information bits recovered, UL, (decoding) can be expressed mathematically as follows: = S,,-lT (12) and the slgn bits sk (encoding) can be expressed mathematically s follows; sk = vkHT + rkG (13k) If the right hand side of equation (13) is substituted Into equation (12) for sk, then the following equation is derived: #k = vkH#THT + rkGHT (14) By selecting G, HT and H#T so that the following conditions are satisfied: (1) HT <BR> <BR> <BR> H#T = 1 (where 1 is the identity matrix); and (2) GHT = 0, then #k = vk regardless of the value of 4.

In the above example, trellis diagram 100, FIG. 9, a single redundancy bit, rk, is and convolutional code G(D) = (1+D 1 1+D 1 1+D 1), Since 1*rk=rk and D*rk=rk, then rkG(D) is equivalent to rk(1 1 1 1 1 1) + rk, (1 0 1 0 1 0). <BR> <BR> <BR> <P> Here, rF, represents the states, Qk , of the trellis diagram and 4represents the branches or paths taken through the trellis diagram. The four convolutlonal code sequences A-D can be mapped to the r,,. rk representation as follows: A: 000000 - rk-1=0, rk=0 B: 111111 - rk-1=0, rk=1 C: 101010 - rk-1=1, r"'0 D: 010101 - rk-1=1, rk=1 where code sequences A-D can be thought of as r,,G(D) Since the value of kd does not affect how the information bits are decoded. each set of n sign bits generated by the different valid code sequences may be used to produce the same decoded information. As a result, the set of n sign bits that minimize the RFSIRDS can be selected to perform spectral shaping as desired.

Upstream PCM Transmission The spectral shaping scheme according to this Invention can also be used in an equalization context as in the transmitter of an analog PCM modem used for upstream PCM transmission to perform precodlng. In this case, the response h(D) represents the channel response between the transmitting modem and the analog-to digital (A/D) converter in the central office (CO) line card, and typically includes the effects of filtering in the transmItting modem front-end, the analog local loop and the CO line card.

By using the principles of this invention a channel output sequence x(n) (z(n) with prefiltering) can be generated that produces a sequence y(D) at the AID converter input whose signal points mimic the AID quantization levels. In this case, the objective is to minimize the energy of the transmitted signal x(D) = y(D)/h(D) while maintaining a low constellation expansion at the AID converter input. Constellation expansion is undesirable in this case as well because larger constellation expansion may lead to increased echo-induced quantization noise and other impairments.

In this application, usually the channel responsive h(D) will be determined either by the receiving modern or jointly by the transmitting and receiving modems based on channel measurements made during modem start-up, and then during data transmission the transmitting modem will map the incoming bits-into the transmission sequence x(D), which after passing through the channel are converted to the channel output sequence y(D). The channel response h(D) is usually chosen to be minimum phase, which is easily accomplished, for example through additional filtering in the transmitter.

Transmitter 40', FIG. 10, is a transmitter in an analog PCM modem which is capable of upstream PCM transmission. Transmitter 40' uses the spectral shaping scheme of this invention to precode, using precoder 140, the incoming data bit stream 42'. One type of PCM upstream precoding (referred to as one-dimensional precoding which precodes on a per symbol basis) is described in detail in US Patent App., Attorney Docket No. CX096044P02, entitled Device and Method for Precoding Data Signals, filed December 29, 1997, having inventors M. Vedat Eyuboglu, Pierre A. Humblet; and Daeyoung Kim. Precoder 140 performs multi-dimensional precoding, i.e. it precodes symbols on a per frame basis. The present implementation dlffers from one- dimensional precodlng, but the concept Is analogous to the one-dimensional case and reference may be made to the above co-pending application for further detail.

Precoder 140 includes a serial to parallel converter 48', magnitude mapper 50', sign bit encoder 52' and a signal point selector 54'. These components are configured and operate as do the components with like numbers Ir. FIG. 4 with minor modifications. For example, the operation of the sign bit encoder is modified to perform precoding, as described below. and the signal point selector outputs n precoded levels, +" per frame corresponding to the signed symbols, y*, instead of the signed symbols themselves. The n precoded levels, , are provided to parallel to serial converter 142 which outputs the prscoded levels in serial form to prefilter 144. Prefilter 144 filters the levels and outputs the filtered levels to digital to analog converter 146 which in turn transmits precoded analog levels over analog channel 148. The channel modifies the precoded levels x,, and ideally produces levels corresponding to the signed symbols, y, at the quantizer in central office (CO) 150. In other words, the precoder selects precoded levels, x, that produce levels corresponding to the desired signed symbols, y*, at the quantizer by accounting for the response of analog channel 148, or more precisely a target channel response, h(n), The target channel response, h(n) is equal to g(n), the response of prefilter 144, convolved with c(n), the response of analog channel 148, where n is the symbol tirne index and h(0)=1 . That relationship can be expressed as follows; y(n) = h(0)x(n) + h(i)x(n-1) +... h(N,)X(n-Nh) (15) Since h(O) is designed to equal 1, then equation (15) can be simplified as follows: The value for h(n) at a given time is known and the past values of x(n) are also known. Filter 90, FIG. 8, calculates the summation temt of equation (16) as the RFS and provides it to selection controller BITS, The past values of x(n) are determined from the previous symbols y(n) by the known relationship, x(D):y(D)Th(D) and stored in filter 90 and the selection controller B8 operates according to flow diagram 120, FIG. 10, by selecting the encoded symbol sign bits that minimize x(n). Instead of sending signed symbols y(n), precoded levels are transmitted.

In addition to the mapping operations described above, one needs to include modules for echo cancellation which separates the two directions of transmission, a timing interpolation fitter which ensures that the symbols are transmitted in synchronism with the network clock. This timing interpolation filter will typically be driven by the clock recovery circuit used in the downstream receiver. The transmitter may also include a linear filter which is primarily responsible for limiting the transmission bandwidth to about 4 kHz and to provide the necessary prefiitering which would make the overall channel response h(D) minimum phase.

Further1 in a practical system one could also include a form of trellis coding to increase noise immunity. For example, the trellis coding techniques described in the application referred to above, entitled System and Device for, and Method of, Communicating According to a Trellis Code of Baseband Signals Chosen from a Fixed Set of Baseband Signal Points, filed November 14, 1996, US Apl. Ser. No, 08/749040 (Attorney Docket No CX096050) can be used. That application is incorporated herein In its entirety by reference. The operatlon of the system is essentially unaffected by trellis coding.

It should be noted that this invention may be embodied in software and/or firmware, which may be stored on a computer useable medium, such as a computer disk or memory chip. The invention may also take the form of a computer data signal embodied in a carrier wave, such as when the invention is embodied in software/firmware, which is electrically transmitted, for example, over the Internet.

The present invention may be embodied in other specific forms without departing from the spirit or essential characteristics. The described embodiments are to be considered in all respects oniy as illustrative and not restrictIve. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes, which come within the meaning and range within the equivalency of the claims, are to be embraced within their scope.

What is claimed is:

**Previous Patent:**COMMUNICATION AND ALERT DEVICE FOR UNDERWATER DIVERS

**Next Patent: A SYSTEM AND METHOD OF POINT-TO-MULTIPOINT WIRELESS COMMUNICATION USING A POINT-TO-POINT COMMUNICATI...**