Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2002-02-28
2004-02-24
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C375S222000
Reexamination Certificate
active
06697831
ABSTRACT:
BACKGROUND
The invention relates generally to mathematical algorithms for data transmissions, and, more particularly, to algorithms for performing modulus conversions of transmitted data.
Conventional computer systems transmit data using modems connected to telephone lines or other communication media. Generally, there are two types of modem in such a system, server modems and client modems. Signal directions are generally referred to in this area as downstream, from server modems to client modems, and upstream, from client modems to server modems. Server modems are generally used by Internet service providers (ISPs) for transmitting signals downstream to and receiving signals upstream from client modems. Similarly, client modems are generally used by customers of ISPs, and are configured to send signals upstream to and receive signals downstream from ISP server modems.
Each type of modem typically uses an analog to digital converter and a digital to analog converter, (A/D-D/A converter) typically combined into a single device called a CODEC. This CODEC converts incoming analog signals to digital signals that can be processed by a signal-processing unit and converts digital signals from a signal processing unit to outgoing analog signals that can be transmitted on a communication medium such as a telephone line. In many cases, server modems do not have their own CODECs, but rely on the CODECs within the telephone network to do the conversions. The signal processing unit, sometimes referred to as a “data pump,” is conventionally a dedicated chip known as a Digital Signal Processor (DSP), which is preprogrammed with algorithms for converting the digital signals into information bits and vice versa.
The modem may also include a second dedicated chip, sometimes called the “controller,” which is a microcontroller preprogrammed to control the DSP, convert the information bits from the DSP into data usable by the computer system, and convert data from the computer system into information bits for the DSP. The controller may implement certain schemes to correct errors in the information bits, and may also implement certain schemes to compress the information bits for more efficient transmission. Some modems eliminate the dedicated controller chip by performing the control functions on the host computer system. These modems are commonly referred to as controllerless modems. Other modems may perform some or all of the signal processing functions on the host computer system using techniques commonly referred to as Host Signal Processing (HSP.)
Modem modulation schemes used in modem communication systems are typically defined in terms of analog signals. Many modulation schemes operate by altering the characteristics of a sine wave, the frequency of which is referred to as the carrier frequency. For example, Quadrature Amplitude Modulation (QAM) operates by altering the amplitude and phase of a carrier frequency at a fixed rate. Other modulation schemes operate without a carrier. For example, Pulse Coded Modulation (PCM) operates by directly altering the level of a signal at a fixed rate. In either case, this fixed rate is known as the baud frequency or symbol frequency. Since most modern modems use digital signal processing techniques, these analog signals must be converted to digital form using a sampling rate, which is often a multiple of the baud frequency. Thus, an integer number of samples can be thought of as representing a “baud” or “symbol.” Depending on the modulation scheme and the sophistication of the algorithms it uses, the symbols, either individually or in groups, represent a certain number of information bits. The relationship between the information bits and the transmitted symbols is determined by a mapping scheme. The average number of information bits transmitted per second is commonly called the “data rate” or “bit rate.”
Standard protocols for modem modulation schemes have been developed to improve compatibility in the telecommunications industry. The International Telecommunications Union (ITU), formerly the International Telegraph and Telephone Consultative Committee (CCITT), for example, has developed standard recommendations that evolve with the changing technology in the modem industry. Earlier recommendations such as V.21, V.22 and V.23 use frequency division multiplexing (FDM) for duplex communication. Newer recommendations such as V.32bis, V.34, V.90 and V.92 use echo cancellation for duplex communication. V.90 and V.92 describe duplex communication using PCM modulation in at least one direction. Modems designed according to V.90 or V.92 are sometimes called 56 kbps modems, referring to the maximum bit rate specified in the downstream direction. All modems implementing a particular recommendation must use specified modulation and mapping schemes when transmitting data across the data transmission system, in order to ensure interoperability among multiple vendors' products.
Modulation schemes typically define sets of allowable symbol parameters known as constellations. Mapping methods provide ways to represent information bits to be transmitted in terms of available points in the constellations. In both the V.90 and V.92 recommendations, multiple modulus conversion (MMC) is employed as a mapping scheme in order to map long frames of information bits onto multiple constellations of different sizes. In particular, the V.90 recommendation specifies MMC to be used in the downstream direction, from the server modem to the client modem. The V.92 recommendation specifies MMC to be used in both directions.
In conventional applications of MMC, input data is used to form a quotient, which is successively divided by a set of known moduli. The remainders of each division are used as the output of the process. This process is a great burden on a modem processor, because typically division operations require multiple cycles to perform. Also, typically the input data is larger than the modem processor can handle with one operation. To address these problems, several techniques have been developed to perform such calculations. One commonly used method uses a long division algorithm, whereby the incoming quotient is partitioned into several segments, each requiring a separate division operation.
In general, the MMC algorithm takes as input a number Q
0
, a non-negative integer. In addition, the algorithm takes as input a plurality of moduli Y
i
, where 1≦i≦M, which are all positive integers. Typically, Y
i
≧2 and Q
0
<Y
1
*Y
2
* . . . Y
M
. The output of the algorithm is a set of values Q
i
and R
i
, all non-negative integers, such that the following mathematical relationships hold:
Q
0
=Y
1
*Q
1
+R
1
Q
1
=Y
2
*Q
2
+R
2
. . .
Q
i−1
=Y
i
*Q
i
+R
i
where
0
≦R
i
<Y
i
Equivalently, Q
0
can be expressed in terms of the remainders produced by the MMC process and the respective moduli, Y
i
:
Q
0
=R
1
+R
2
Y
1
+R
3
Y
1
Y
2
+. . . +R
M
Y
1
Y
2
. . . Y
M−1
+Q
M
Y
1
Y
2
. . . Y
M
Note that if Q
0
<Y
1
*Y
2
* . . . Y
M
, as is typically the case in a communication system, then Q
M
=0.
This algorithm requires that a division operation be done for each modulus, resulting in an output quotient and remainder for each modulus. The division corresponding to the final modulus Y
M
may be skipped if the input is limited as described above, so that Q
M
is known in advance to be 0. In that case, it can be shown that R
M
=Q
M−1
.
The following example illustrates the mathematical concept of MMC. All values are expressed in decimal format. In this example, the input Q
0
=933, and there are four input moduli: Y
1
=5, Y
2
=6, Y
3
=7, and Y
4
=8. Here are the steps in the process:
1. Receive the input value of 933.
2. Divide the input by first modulus, 5. 933/5=quotient 186, remainder 3.
3. Divide new quotient by second modulus, 6. 186/6=quotient 31, remainder 0.
4. Divide new quotient by third modulus, 7. 31/7=quotient
Cookman Jordan C.
Dong Ping
Ess Technology Inc.
Ngo Chuong Dinh
Stevens Law Group P.C.
LandOfFree
Device and method for performing multiple modulus conversion... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method for performing multiple modulus conversion..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for performing multiple modulus conversion... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3342701