Apparatus and method for trigonometric interpolation

[0002] This application claims the benefit of U.S. Provisional Application No: 60/162,391, filed on Oct. 29, 1999, which is incorporated by reference.

[0004] Apparatus and Method for Angle Rotation,” U.S. patent application Ser. No. 09/698,246, filed Oct. 30, 2000; and

[0005] Apparatus and Method for Rectangular-to-Polar Conversion,” U.S. patent application Ser. No. 09/698,249, filed Oct. 30, 2000.

[0006] 1. Field of the Invention

[0007] The present invention is related to digital signal processing and digital communications. More specifically the present invention is related to interpolation, angle rotation, rectangular-to-polar conversion, and carrier and symbol timing recovery for digital processing and digital communications applications.

[0008] 2. Related Art

[0009] Advances in technology have enabled high-quality, low-cost communications with global coverage, and provide the possibility for fast Internet access and multimedia to be added to existing services. Exemplary emerging technologies include cellular mobile radio and digital video broadcasting, both of which are described briefly as follows.

[0010] In recent years, cellular mobile radio has experienced rapid growth due to the desire for mobility while enjoying the two-way voice services it provides. GSM, IS-136 and personal digital cellular (PDC) are among the most successful second-generation personal communications (PCS) technologies in the world today, and are responsible for providing cellular and PCS services globally. As the technology advances, customers will certainly demand more from their wireless services. For example, with the explosive growth of the world wide web over the wired networks, it is desirable to provide Internet services over mobile radio networks. One effort to specify the future global wireless access system is known as IMT-2000 (Buchanan, K., et al., IEEE Pers. Comm. 4:8-13 (1997)). The goal of IMT-2000 is to provide not only traditional mobile voice communications, but also a variety of voice and data services with a wide range of applications such as multimedia capabilities, Internet access, imaging and video conferencing. It is also an aim to unify many existing diverse systems (paging, cordless, cellular, mobile satellite, etc.) into a seamless radio structure offering a wide range of services. Another principle is to integrate mobile and fixed networks in order to provide fixed network services over the wireless infrastructure. Such systems might well utilize broadband transport technologies such as a synchronous transfer mode (ATM).

[0011] For the applications of IMT-2000, a high-bit-rate service is needed. Moreover, for multimedia applications, the system should provide a multitude of services each requiring 1) a different rate, and 2) a different quality-of-service parameter. Thus, a flexible, variable-rate access with data rates approaching 2 Mb/s is proposed for IMT-2000.

[0012] The advent of digital television systems has transformed the classical TV channel into a fast and reliable data transmission medium. According to the specifications of the DVB project (Reimers, U., IEEE Comm. Magazine36:104-110 (1998)), digital TV is no longer restricted to transmitting sound and images but instead has become a data broadcasting mechanism which is fully transparent to all contents. Digital TV broadcasting by satellite, cable and terrestrial networks is currently under intensive development. A typical system looks like this: a DVB signal is received from a satellite dish, from cable, or from an antenna (terrestrial reception). A modem built into an integrated receiver/decoder (IRD) will demodulate and decode the signal. The information received will be displayed on a digital TV or a multimedia PC. In addition to being used as a digital TV, DVB can receive data streams from companies who wish to transmit large amounts of data to many reception sites. These organizations may be banks, chains of retail stores, or information brokers who wish to offer access to selected Internet sites at high data rates. One such system is MultiMedia Mobile (M³), which has a data rate of 16 Mb/s.

[0013] For proper operation, these third generation systems require proper synchronization between the transmitter and the receiver. More specifically, the frequency and phase of the receiver local oscillator should substantially match that of the transmitter local oscillator. When there is a mismatch, then an undesirable rotation of the symbol constellation will occur at the receiver, which will seriously degrade system performance. When the carrier frequency offset is much smaller than the symbol rate, the phase and frequency mismatches can be corrected at baseband by using a phase rotator. It is also necessary to synchronize the sampling clock such that it extracts symbols at the correct times. This can be achieved digitally by performing appropriate digital resamples resampling.

[0014] The digital resampler and the direct digital frequency synthesizer (DDS) used by the phase rotator are among the most complex components in a receiver (Cho, K., “A frequency-agile single-chip QAM modulator with beamforming diversity,” Ph.D. dissertation, University of California, Los Angeles (1999)). Their performance is significant in the overall design of a communications modem. For multimedia communications, the high-data-rate requirement would impose a demand for high computational power. However, for mobile personal communication systems, low cost, small size and long battery life are desirable. Therefore, it would be desirable to have an efficient implementation of the phase rotator, re-sampler, and DDS in order to perform fast signal processing that operates within the available resources. Furthermore, it would be desirable to have an efficient synchronization mechanism that uses a unified approach to timing and carrier phase corrections.

[0015] For Internet services it is important to provide instantaneous throughput intermittently. Packet data systems allow the multiplexing of a number of users on a single channel, providing access to users only when they need it. This way the service can be made more cost-effective. However, the user data content of such a transmission is usually very short. Therefore, it is essential to acquire the synchronization parameters rapidly from the observation of a short signal-segment.

[0016] For applications where low power and low complexity are the major requirements, such as in personal communications, it is desirable to sample the signal at the lowest possible rate, and to have a synchronizer that is as simple as possible. Therefore, it is also desirable to have an efficient synchronizer architecture that achieves these goals.

[0017] For applications utilizing Orthogonal Frequency Division Multiplexing (OFDM), sampling phase shift error produces a rotation of the Fast Fourier Transform (FFT) outputs (Pollet T., and Peters, M., IEEE Comm. Magazine37:80-86 (1999)). A phase correction can be achieved at the receiver by rotating the FFT outputs. Therefore, it is also desirable to have an efficient implementation structure to perform rotations of complex numbers.

[0018] The present invention is directed at high-performance and low-cost methods and apparatus for performing an accurate interpolation operation in a digital device for generating an output signal. Applications include digital re-sampling to change the data sampling rate of a given signal, and interpolation to correct for symbol timing errors in a digital communications device, as well as other applications.

[0019] More specifically, the present invention includes a method and apparatus for trigonometric interpolation that interpolates between two data samples at an offset μ, where the two data samples are part of a set of N-data samples. The trigonometric interpolator fits a trigonometric polynomial to the N-data sample set, and then evaluates the trigonometric polynomial at the offset μ. The trigonometric interpolator can be implemented for any number of data samples N, where the accuracy of the interpolation (and the hardware complexity) increases with the number of data samples. Simulations have shown that the trigonometric interpolator achieves superior interpolation performance over other methods of interpolation. Moreover, the trigonometric interpolator generally requires less hardware than other methods of interpolation.

[0020] The trigonometric interpolator can be implemented using a delay module, an adder/subtractor module, and at least one angle rotator. The delay module and adder/subtractor module generate one or more complex trigonometric coefficients based on the input samples. Each angle rotator rotates a corresponding complex trigonometric coefficient in the complex plane according the offset μ. The angle rotator can be implemented using a lookup table (e.g. memory device) or by using an angle rotator processor. The table lookup approach is advantageous for low latency applications and can be efficiently shared with a phase rotator that performs carrier synchronization. The angle rotator processor is advantageous for applications that require low complexity, and or low power requirements.

[0021] In embodiments, the number of angle rotators that are required to implement the trigonometric interpolation is reduced for a given set of N-data samples. This is accomplished by modifying data samples so that the trigonometric coefficient c_N/2is zero, thereby eliminating the need for the corresponding angle rotator. The hardware “price” for eliminating an angle rotator using this method is an additional multiplier.

[0022] In embodiments, the filter response of the interpolator can be modified to achieve an arbitrary frequency response in order to enhance the interpolator performance. More specifically, the frequency response of the interpolator can be shaped to effectively correspond with the frequency response of the input data samples and the offset μ. In other words, instead of optimizing the performance of the continuous-time interpolation filter, the fractional-delay filter for each delay value is optimized, thereby achieving even better performance.

[0023] Further features and advantages of the invention, as well as the structure and operation of various embodiments of the invention, are described in detail below with reference to the accompanying drawings. The drawing in which an element first appears is typically indicated by the leftmost character(s) and/or digit(s) in the corresponding reference number.

[0024] FIG. 1A illustrates a PSK transmitter.

[0025] FIG. 1B illustrates a PSK receiver.

[0026] FIG. 1C illustrates a block diagram of an OFDM system.

[0027] FIG. 1D illustrates a PSK receiver with carrier and timing recovery.

[0028] FIG. 2 illustrates an Interpolation environment.

[0029] FIG. 3 illustrates Lagrange basis polynomials.

[0030] FIG. 4 illustrates a Farrow structure that implements (2.5) and (2.6).

[0031] FIG. 5 illustrates a flowchart 500 representing trigonometric interpolation according to embodiments of the present invention.

[0032] FIG. 6A illustrates an impulse response of a Lagrange interpolator.

[0033] FIG. 6B illustrates an impulse response of a Trigonometric interpolator according to embodiments of the present invention.

[0034] FIG. 7A illustrates a frequency response for N=4 according to embodiments of the present invention.

[0035] FIG. 7B illustrates a frequency response for N=32 according to embodiments of the present invention.

[0036] FIG. 8A illustrates a signal with two samples/symbol and 100% excess BW according to embodiments of the present invention.

[0037] FIG. 8B illustrates an NMSE of the interpolated signal according to embodiments of the present invention.

[0038] FIG. 9 illustrates the critical path of the Lagrange cubic interpolator.

[0039] FIG. 10 illustrates a trigonometric interpolator with N=4 according to embodiments of the present invention.

[0040] FIG. 11 illustrates a trigonometric interpolator with N=8 according to embodiments of the present invention.

[0041] FIG. 12 illustrates a conceptual modification of input samples according to embodiments of the present invention.

[0042] FIG. 13 illustrates correcting the offset due to modification of original samples according to embodiments of the present invention.

[0043] FIG. 14 illustrates the modified trigonometric interpolator for N=4 according to embodiments of the present invention.

[0044] FIG. 15 illustrates the modified trigonometric interpolator for N=8 according to embodiments of the present invention.

[0045] FIGS. 16A-D illustrates a comparison of the amount of interpolation error using (A) Lagrange cubic, (B) the trigonometric interpolator 1000, (C) the trigonometric interpolator 1400, (D) the optimal structure (to be discussed in Section 4).

[0046] FIG. 17 illustrates a flowchart 1700 representing trigonometric interpolation according to embodiments of the present invention.

[0047] FIG. 18 illustrates trigonometric interpolation using a table lookup for angle rotation according to embodiments of the present invention.

[0048] FIG. 19 illustrates trigonometric interpolation using modified samples according to embodiments of the present invention.

[0049] FIG. 20 illustrates normalized impulse responses f of the interpolation filters according to embodiments of the present invention.

[0050] FIG. 21 illustrates normalized frequency responses F of the interpolation filters according to embodiments of the present invention.

[0051] FIG. 22 illustrates analysis of the frequency responses according to embodiments of the present invention.

[0052] FIG. 23 illustrates the effect of a more gradual transition at the band edge according to embodiments of the present invention.

[0053] FIG. 24 illustrates reducing the transition bandwidth by increasing N according to embodiments of the present invention.

[0054] FIGS. 25A-B illustrate (A) impulse response of the original filter and the modified filter; (B) The equivalent window, according to embodiments of the present invention.

[0055] FIG. 26 illustrates forming the frequency response of the discrete-time fractional-delay filter according to embodiments of the present invention.

[0056] FIGS. 27A-B illustrate a fractional-delay filter with (A) μ=0.12 and (B) μ=0.5, using the preliminary N=8 interpolator according to embodiments of the present invention.

[0057] FIGS. 28A-D illustrate modification to F(Ω), and the corresponding F_μ(ω) according to embodiments of the present invention.

[0058] FIGS. 29A-B illustrate F_μ(ω), with μ=0.5, N=8, (A) before and (B) after optimization according to embodiments of the present invention.

[0059] FIGS. 30A-30B illustrate F_μ(ω) for μ=0.5, N=4, (A) before and (B) after modification according to embodiments of the present invention.

[0060] FIGS. 31A-31B illustrate F_μ(ω), μ=0.5, simplified N=4 structure, (A) before and (B) after modification according to embodiments of the present invention.

[0061] FIG. 32 illustrates real and imaginary components of the ${\hat{F}}_{\mu }\left(l\right)e^{j\frac{\pi }{2}\mu }$

[0062] value according to embodiments of the present invention.

[0063] FIG. 33 illustrates a signal with two samples/symbol and 40% excess bandwidth according to embodiments of the present invention.

[0064] FIG. 34 illustrates a flowchart 3400 for optimizing trigonometric interpolation according to embodiments of the present invention.

[0065] FIG. 35 illustrates a flowchart 3500 for optimizing trigonometric interpolation according to embodiments of the present invention.

[0066] FIG. 36 illustrates an optimized interpolator 3600 according to embodiments of the present invention.

[0067] FIG. 37 illustrates an optimized interpolator 3700 according to embodiments of the present invention.

[0068] FIG. 38 illustrates an angle rotator 3800 according to embodiments of the present invention.

[0069] FIG. 39 illustrates an angle rotator 3900 according to embodiments of the present invention.

[0070] FIG. 40 illustrates an angle rotator 3900 and example multiplier sizes according to embodiments of the present invention.

[0071] FIG. 41 illustrates a flowchart 4100 for angle rotation according to embodiments of the present invention.

[0072] FIG. 42 illustrates an angle rotator 3900 and multiplier sizes to achieve 90.36 dB SFDR according to embodiments of the present invention.

[0073] FIG. 43 illustrates an output spectrum showing 90.36 dB SFDR according to embodiments of the present invention.

[0074] FIG. 44 illustrates a modified angle rotator 4400 when only one output is needed according to embodiments of the present invention.

[0075] FIG. 45 illustrates a flowchart 4500 for angle rotation when only one output is needed according to embodiments of the present invention.

[0076] FIG. 46 illustrates a phase accumulator 4600.

[0077] FIG. 47 illustrates a Quadrature Direct Digital Frequency Synthesizer/Mixer (QDDFSM) according to embodiments of the present invention.

[0078] FIG. 48 illustrates an angle rotator 4800 according to embodiments of the present invention.

[0079] FIG. 49 illustrates a Booth multiplier

[0080] FIG. 50 illustrates an original Booth table 5000.

[0081] FIG. 51 illustrates a negating Booth table 5100 according to embodiments of the present invention.

[0082] FIG. 52 illustrates a negating Booth multiplier 5200.

[0083] FIG. 53 illustrates a conditionally negating Booth decoder 5300 according to embodiments of the present invention.

[0084] FIG. 54 illustrates a conditionally negating multiplier 5400 according to embodiments of the present invention.

[0085] FIG. 56 illustrates an angle rotator as a cosine only direct digital synthesizer based on angle rotator 3900 according to embodiments of the present invention.

[0086] FIG. 57 illustrates an angle rotator as a cosine only direct digital synthesizer based on angle rotator 4400 according to embodiments of the present invention.

[0087] FIG. 58 illustrates a common packet format for packet based communications.

[0088] FIG. 59 illustrates a system model for packet based communications.

[0089] FIG. 60 illustrates mean values of a preamble correlator output, for θ=0, according to embodiments of the present invention.

[0090] FIG. 61 illustrates a synchronizer 6100 according to embodiments of the present invention.

[0091] FIG. 62 illustrates a flowchart 6200 associated with the synchronizer 6100 according to embodiments of the present invention.

[0092] FIG. 63 illustrates bias due to truncation.

[0093] FIG. 64 illustrates simultaneous operation of a symbol-timing synchronizer and a carrier phase recovery system 6400 according to embodiments of the present invention.

[0094] FIGS. 65A-65B illustrate a flowchart 62006500 associated with the synchronizer 61006400 according to embodiments of the present invention.

[0095] FIG. 66 illustrates timing variance, α=0.4.

[0096] FIG. 67 illustrates timing jitter variance, α=0.1.

[0097] FIG. 68 illustrates phase jitter variance, α=0.1.

[0098] FIG. 69 illustrates Cartesian-to-polar conversion.

[0099] FIGS. 70A-70B illustrate using Newton-Raphson iteration to find 1/X₁.

[0100] FIG. 71 illustrates a rectangular-to-polar converter 7100 according to embodiments of the present invention.

[0101] FIG. 72 illustrates angle rotation associated with the rectangular-to-polar converter 7100 according to embodiments of the present invention.

[0102] FIG. 73 illustrates a flowchart 7300 associated with the synchronizer 7100 according to embodiments of the present invention.

[0103] FIG. 74 illustrates Interpolation in a non-center interval according to embodiments of the present invention.

[0104] FIGS. 75A-B illustrate impulse responses of the non-center-interval interpolation filter (A) before and (B) after optimization, according to embodiments of the present invention.

[0105] FIGS. 76A-B illustrate frequency responses of the non-center-interval interpolator (A) before optimization and (B) after optimization, according to embodiments of the present invention.

[0106] FIG. 77 illustrates an exemplary computer system 7702, according to embodiments of the present invention.

[0107] FIG. 78 illustrates a data rate expansion circuit 7800 according to embodiments of the present invention.

[0108] 1. Introduction

[0109] 1.1 Exemplary Modulation Schemes and Synchronization Issues

[0110] 1.2 Overview

[0111] 2. Interpolation Using a Trigonometric Polynomial

[0112] 2.1 Interpolation Using an Algebraic Polynomial

[0113] 2.2 The Trigonometric Polynomial Method

[0114] 2.3 Performance Comparisons

[0115] 2.4 Efficient Implementation Structures

[0116] 2.4.1 Using a Lookup Table

[0117] 2.4.2 Using an Angle Rotation Processor

[0118] 2.5 Delays in the Computation

[0119] 2.6 Simplifications of the Preliminary Structures

[0120] 2.6.1 The Simplified Structure for N=4

[0121] 2.6.2 The Simplified Structure for N=8

[0122] 2.6.3 Performance Comparisons with Other Structures

[0123] 2.7 Trigonometric Interpolator Application

[0124] 2.8 Trigonometric Interpolator Summary

[0125] 3. Interpolation Filters with Arbitrary Frequency Response

[0126] 3.1 Formulating the Trigonometric Interpolator as an Interpolation Filter

[0127] 3.2 Analysis of the Frequency Response

[0128] 3.3 Implementing the Modified Algorithm

[0129] 3.4 Conditions for Zero ISI

[0130] 3.5 Optimization Algorithm

[0131] 3.6 Conclusion

[0132] 4. Design of Optimal Resamplers

[0133] 4.1 Motivation

[0134] 4.2 Resampler Optimizations

[0135] 4.3 Implementations

[0136] 4.4 Simulation Results

[0137] 4.5 Conclusion

[0138] 5. A High-Speed Angle Rotation Processor

[0139] 5.1 The angle rotation problem

[0140] 5.1.1 Single-Stage Angle Rotation

[0141] 5.1.2 Rotation by a Small Angle

[0142] 5.1.3 Partitioning into Coarse and Fine Rotations

[0143] 5.2 Simplification of the Coarse Stage

[0144] 5.3 Reduction of Multiplier Size in the Fine Stage

[0145] 5.4 Scaling Multiplier Simplification

[0146] 5.5 Computational Accuracy and Wordlength

[0147] 5.6 Comparison with the Single-Stage Mixer

[0148] 5.7 A Modified Structure When Only One Output is Needed

[0149] 5.7.1 Modifications to the Coarse Stage

[0150] 5.7.2 Scaling Multiplier Simplification

[0151] 5.8 Application of Angle Rotation Processors

[0152] 5.8.1 Using the Angle Rotation Processor in a Quadrature Direct Digital Frequency Synthesizer/Mixer

[0153] 5.8.1.1 A General Angle Rotator for Arbitrary Input Angles

[0154] 5.8.1.2 Adapting the General Angle Rotator to Make a QDDFSM

[0155] 5.8.2 How to Use the Conditionally Negating Multipliers in the General Angle Rotator

[0156] 5.8.2.1 Booth Multiplier

[0157] 5.8.2.2 How to Make a Negating Booth Multiplier

[0158] 5.8.2.3 How to Make a Conditionally Negative Booth Multiplier

[0159] 5.8.3 Using the Angle Rotation Processor in a Quadrature Direct Digital Frequency Synthesizer

[0160] 5.9 Conclusion

[0161] 6. Symbol Synchronization for Bursty Transmissions

[0162] 6.1 Initial Parameter Estimations for Burst Modems

[0163] 6.2 Background Information

[0164] 6.3 Symbol Timing Estimation Assuming θ=0

[0165] 6.4 Bias in Symbol Timing Estimation due to Truncating the Sequence

[0166] 6.5 Carrier-Independent Symbol Timing Recovery

[0167] 6.6 Carrier Phase Computation

[0168] 6.7 Simulation Result

[0169] 6.8 Conclusion

[0170] 7. A High-Speed Processor for Rectangular-to-Polar Conversion

[0171] 7.1 Partitioning the Angle

[0172] 7.2 The Two-Stage Algorithm

[0173] 7.2.1 Simplification in the Coarse Computation Stage

[0174] 7.2.1.1 The Reciprocal Table 7106

[0175] 7.2.1.2 The Arctangent Table 7110

[0176] 7.2.2 Hardware Reduction in the Fine Computation Stage 7124

[0177] 7.3 Magnitude Calculation

[0178] 7.4 Converting Arbitrary Inputs

[0179] 7.5 Test Result

[0180] 7.6 Conclusion

[0181] 8. Exemplary Computer System

[0182] 9. Appendices

[0183] 9.1 Appendix A: Proof of the Zero ISI Condition.

[0184] 9.2 Appendix B: Impulse Response of the Simplified Interpolators

[0185] 9.3 Appendix C: Fourier Transform of g(nT_s−μ)

[0186] 9.4 Appendix D: Interpolation on Non-Center Intervals

[0187] 9.5 Appendix E

[0188] 10. Conclusion

[0189] As discussed herein, third generation and other cutting edge communications systems require proper synchronization between the transmitter and the receiver. More specifically, the frequency and phase of the receiver local oscillator should substantially match that of the transmitter local oscillator and accurate symbol timing must be achieved. The following section discuss some exemplary modulation schemes and configurations, and their related synchronization issues. These example configurations are not meant to be limiting, and are provided for example purposes only. After which, an overview of the present invention is provided.

[0190] 1.1 Exemplary Modulation Schemes and Synchronization Issues

[0191] A key to the evolution of third-generation PCS is the ability to provide higher data rates via increased spectral efficiency of the access scheme. The IS-136 community intends to add a 200-KHz carrier bandwidth and adopt 8PSK modulation. This allows for data rates up to 384 Kb/s.

[0192] A simplified 8PSK transmitter 102 and receiver 104 are shown in FIG. 1A and FIG. 2B, respectively. The receiver 104, as shown, performs baseband sampling. Alternatively, the received signal could be sampled at an IF frequency, where the down-conversion to baseband is performed digitally. However, since it does not alter the main subject in the present invention, the baseband-sampled system is used as an example.

[0193] Referring to FIG. 1B, PSK receiver 104 down-converts an IF input signal 106 to baseband by multiplication with a local oscillator signal 108 using mixers 110. After filtering 111, A/D converters 112 sample the down-converted signal according to a sampling clock 114 in preparation for logic examination. After further filtering 116 and equalization 118, the logic decision devices 120 examine the sampled signal to determine a logic output for the two channels.

[0194] During down-conversion, an undesirable rotation of the symbol constellation will occur if the frequency and phase of the oscillator signal 108 does not match the oscillator signal of the transmitter 102. This symbol rotation can seriously degrade system performance. When the carrier frequency offset is much smaller than the symbol rate, the phase and frequency mismatches can be corrected at baseband, using a phase rotator 124, as shown in FIG. 1D.

[0195] The sampling clock 114 is generated locally in the receiver 104. The logic decision devices 120 make more accurate decisions when the sampling instant is optimal, i.e., synchronous to the incoming symbols.

[0196] If the timing information can be extracted from the signal 106, it can be used to adjust the phase of the sampling clock 114. This adjustment would require a voltage controlled oscillator (VCO) to drive the A/D converters 112. In this scenario, the digital portion of the circuit 104 needs to keep in synchronization with the A/D converters 112, which places strict requirements on the VCO. Moreover, changing the phase of the sampling clock 114 would cause jitter. High data-rate receivers are more sensitive to such jitter when used in multimedia communications.

[0197] Another solution to timing errors is to correct them entirely in the digital domain, with the equivalent of A/D sampling adjustment performed by a digital resampler 122, as shown in FIG. 1D. This resampler 122 is controlled by a timing recovery circuit (not shown) and it attempts to supply the optimal samples (i.e. synchronous) to the decision circuits 120. Using the digital resampler 122, the timing recovery loop is closed entirely in the digital domain. This allows the complete separation of digital components from analog components.

[0198] The digital resampler 122 and a direct digital frequency synthesizer (not shown) used by the phase rotator 124 are among the most complex components in a receiver (Cho, K., “A frequency-agile single-chip QAM modulator with beamforming diversity,” Ph.D. dissertation, University of California, Los Angeles (1999)). Their performance is significant in the overall design of the modem. For multimedia communications, the high-data-rate requirement imposes a demand for high computational power. However, for mobile personal communication systems, low cost, small size, and long battery life are desirable. Therefore, efficient implementation is the key to implementing fast signal processing within the available resources. It is also desirable to provide an efficient synchronization mechanism by using a unified approach to timing and carrier phase corrections. This can be accomplished by sharing resources between the resampler 122 and the phase rotator 124.

[0199] As for the digital video broadcasting system (DVB) systems, the most challenging of all DVB transmissions is the one used in terrestrial channels (DVB-T) due to the presence of strong echoes which characterize the propagation medium. A common approach for DVB-T is based on Coded-OFDM (orthogonal frequency division multiplexing). The major benefit of OFDM is that the serial baseband bitstream which needs to be transmitted is distributed over many individual subcarriers. Such spreading makes the signal robust against the effects of multipath and narrowband interference. The simplified block diagram of an OFDM modem 108 is shown in FIG. 1C.

[0200] FIG. 1C illustrates an orthogonal frequency division multiplexing system (OFDM) 126 having an OFDM transmitter 128 and an OFDM receiver 130. For the OFDM system 126, synchronization errors produce a rotation of the fast Fourier Transform (FFT) outputs of the OFDM receiver 130. (Pollet T., and Peeters, M., IEEE Comm. Magazine37:80-86 (1999)). A sampling phase correction for the received signals can be achieved by rotating the FFT outputs at the receiver. For FFT rotation, it is desirable to have an efficient implementation structure to perform rotations of complex numbers.

[0201] The example applications and modulation schemes described above in this section were provided for illustrative purposes only, and are not meant to be limiting. Other applications and combinations of such applications will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. These other applications are within the scope and spirit of the present invention.

[0202] 1.2 Overview

[0203] The following is an overview of the sections that follow.

[0204] Sections 2, 3 and 4, discussed herein, present a novel interpolation method for digital resampling using a trigonometric polynomial. In Section 2, after a brief review of interpolation methods, particularly those using a conventional polynomial, the trigonometric interpolation method is introduced. Efficient implementation structures for trigometric interpolation are given. The performance, hardware complexity and computational delay are compared with conventional polynomial interpolators. The trigonometric-polynomial based resampler can use the same hardware as is employed in the phase rotator for carrier synchronization, thus further reducing the total complexity in the synchronization circuitry.

[0205] In Section 3, a signal processing approach is used to analyze the interpolation method devised in Section 2. It shows how an arbitrary frequency response is achieved by applying a simple modification to the original interpolation algorithm. This enables the interpolator to also perform matched filtering of the received signal.

[0206] The approaches in Section 3 can be employed to improve the interpolator performance by optimizing the frequency response of the continuous-time interpolation filter. This method is based on optimizing the performance by conceptually reconstructing the continuous-time signal from existing samples. From the point of view of designing digital resamplers, however, what we are actually interested in are new samples corresponding to the new sampling instants. In Section 4, we optimize the interpolation filter such that the error in producing a new sample corresponding to every resampling instant is minimized, hence further improving the overall interpolation accuracy.

[0207] Section 5 presents an angle rotation processor that can be used to efficiently implement the trigonometric resampler and the carrier phase rotator. This structure can also implement the resampler for an OFDM receiver, which rotates the FFT outputs. It has many other practical applications.

[0208] The discussions in the previous Sections have assumed that the sampling mismatch that is supplied to the resampler is known. The problem of obtaining the synchronization parameters is studied in Section 6. For burst mode transmissions in packet data systems, we present an efficient architecture for feedforward symbol-timing and carrier-phase estimation.

[0209] Section 7 presents an efficient implementation of a key component in the feedforward synchronizer of Section 6, as well as in many other such synchronizers. This involves computing the angle from the real and imaginary components of a complex number. The discussion, however, extends to a general problem of Cartesian-to-polar conversion, which is encountered in many communication applications. An architecture that efficiently accomplishes this conversion is presented.

[0210] Section 8 presents an exemplary computer system in which the invention can be operated.

[0211] Section 9 includes various appendices.

[0212] Further discussions related to materials in Sections 2-7 are included in Dengwei Fu, “Efficient Synchronization for Multimedia Communications,” Ph.D dissertation, University of California, Los Angeles, 2000, which is incorporated-by-reference, in its entirety.

[0213] Additionally, the following articles are herein incorporated by reference in their entireties:

[0214] D. Fu and A. N. Willson, Jr., “A high-speed processor for digital sine/cosine generation and angle rotation,” in Conf. Record32nd Annual A silomar Conference on Signals, Systems and Computers, vol. 1, pp. 177-181, November 1998;

[0215] D. Fu and A. N. Willson, Jr., “Interpolation in timing recovery using a trigonometric polynomial and its implementation,” in Proc. GLOBECOM1998, Comm. Theory Mini-Conference Record, pp. 173-178, November 1998;

[0216] D. Fu and A. N. Willson, Jr., “Design of an improved interpolation filter using a trigonometric polynomial,” in Proc. Int. Symp. Circuits & Systems, vol. 4, pp. 363-366, May 30-Jun. 3, 1999;

[0217] D. Fu and A. N. Willson, Jr., “A high-speed processor for rectangular-to-polar conversion with applications in digital communications,” in Proc. GLOBECOM1999, vol. 4, pp. 2172-2176, December 1999;

[0218] D. Fu and A. N. Willson, Jr., “A fast synchronizer for burst modems with simultaneous symbol timing and carrier phase estimations,” in Proc. Int. Symp. Circuits & Systems, vol. 3, pp. 379-382, May 28-31, 2000; and

[0219] D. Fu and A. N. Willson, Jr., “Optimal interpolator using a trigonometric polynomial,” in Proc.43rd Midwest Symp. Circuits & Systems, 4 pages, Aug. 8-11, 2000.

[0220] As discussed in Section 1, when an analog-to-digital converter (ADC) is clocked at a fixed rate, the resampler must provide the receiver with correct samples, as if the sampling is synchronized to the incoming symbols. How can the resampler recover the synchronized samples by digital means without altering the sampling clock? Since the input analog signal to the ADC is bandlimited, as long as the sampling rate is at least twice the signal bandwidth, according to the sampling theorem, the sampled signal carries as much information as the continuous-time signal. Therefore, the value of the original continuous-time signal at an arbitrary point can be evaluated by applying an interpolation filter (e.g., sinc interpolation) to the samples. Hence, the design of the resampler has been transformed to the design of effective interpolation filters or, in other words, fractional-delay filters with variable delay.

[0221] There are numerous methods for designing fractional-delay filters. These filters have different coefficients for different delays. Thus, to implement variable-delay interpolation filters, one could compute one set of coefficients for each quantized delay value and store them in a memory. Then, in real-time, depending on the fractional delay extracted from the incoming signal, the corresponding coefficients could be loaded. However, this method is likely to result in a large coefficient memory.

[0222] To design low-cost modems, a large coefficient memory is undesirable. Gardner, et al., have shown that polynomials can be incorporated to compute the desired samples that are synchronous with the transmitted samples (Gardner, F. M., IEEE Trans. Comm. 41:502-508 (1993); Erup, L., et al., IEEE Trans. Comm. 41:998-1008 (1993)). In this case, an extensive coefficient memory is not needed. Moreover, the polynomial-based structure can be implemented efficiently with a so-called Farrow structure (Farrow, C., “A continuously variable digital delay element,” in Proc. IEEE Int. Symp. Circuits Syst. (June 1988), pp. 2641-2645). This method is reviewed in Section 2.1. Although this approach achieves reasonable performance, the hardware complexity grows rapidly as the number of samples used to calculate each new sample is increased for better accuracy. In addition, given a fractional delay μ, to produce a new sample using a degree N−1 polynomial, there will be N−1 sequential multiplications that involve μ since we must compute μ raised to the (N−1)-th power times a data value. Thus, the critical data path gets longer as Nincreases, thereby creating a limitation on the achievable data rate.

[0223] Starting in Section 2.2, a new approach to interpolation is introduced. Instead of approximating the continuous-time signal with a conventional (i.e., algebraic) polynomial, a trigonometric polynomial is used according to the present invention. First, some background information is given. Next, the detailed implementation is discussed. We then evaluate and compare the performance and computational complexity of the algebraic polynomial interpolation to that of our method, giving numerical results.

[0224] 2.1 Interpolation Using an Algebraic Polynomial

[0225] To interpolate using function values y(n) at N equally-spaced sample points, also referred to as a “base point set,” we can fit an algebraic polynomial of degree N−1 to the data, as in FIG. 2. As explained in (Gardner, F. M., IEEE Trans. Comm. 41:502-508 (1993)), there should be an even number of samples in the base point set, and the interpolation should be performed only in the center interval of the base point set. That is, N is restricted to be even. In other words, given 4 samples points in FIG. 2 including y(−1), y(0), y(1), and y(2), the interpolation is performed at offset ti between the points y(0) and y(1) to determine the point 202 on the curve p(t).

[0226] It seems that one would have to solve for the coefficients of the (N−1)-th degree polynomial from these available samples before the synchronized (i.e., interpolated) samples can be computed. However, a method devised by Farrow (Farrow, C., “A continuously variable digital delay element,” in Proc. IEEE Int. Symp. Circuits Syst. (June 1988), pp. 2641-2645) can compute the synchronized sample from the available samples efficiently with use of an algorithm that is well suited for VLSI implementation. To illustrate, we consider the following example of interpolation using a cubic Lagrange polynomial. Without loss of generality, let us assume the sampling interval is T_S=1. Using the Lagrange formula for N=4, the synchronized samples can be computed as

[0227] y(μ)=y(−1)C₋₁(μ)+y(0)C₀(μ)+y(1)C₁(μ)+y(2)C₂(μ)  (2.1)

[0228] where C_n(μ), n=−1, 0, 1, 2, are the third degree polynomials that are shown in FIG. 3.

[0229] Obviously, $\begin{array}{cc}{C}_n\left(\mu \right)=\{\begin{array}{cc}1& \mu ={\mathrm{nT}}_s,n\mathrm{an}\mathrm{integer}\\ 0& \mathrm{all}\mathrm{other}\mathrm{integers}.\end{array}& \left(2.2\right)\end{array}$

[0230] Thus, y(μ) in (2.1), the sum of polynomials C_n(μ) weighted by the y(n) values, must be a third degree polynomial and must go through the samples y(−1), y(0), y(1) and y(2). Writing C_n(μ) as $\begin{array}{cc}{C}_n\left(\mu \right)=\sum _{k=0}^3{c}_{\mathrm{nk}}{\mu }^k& \left(2.3\right)\end{array}$

[0231] the coefficients C_nkof C_n(μ) are fixed numbers. They are independent of μ. We can re-write (2.1) as $\begin{array}{cc}y\left(\mu \right)=\sum _{n=-1}^{2}y\left(n\right)\sum _{k=0}^3{c}_{\mathrm{nk}}{\mu }^k=\sum _{k=0}^3\left(\sum _{n=-1}^{2}y\left(n\right)c_{\mathrm{nk}}\right){\mu }^k=\sum _{k=0}^{3}v\left(k\right){\mu }^k& \left(2.4\right)\end{array}$

[0232] where $\begin{array}{cc}v\left(k\right)=\sum _{n=-1}^{2}y\left(n\right)c_{\mathrm{nk}}.& \left(2.5\right)\end{array}$

[0233] To minimize the number of multipliers, we can use a nested evaluation of (2.4), as

[0234] y(μ)=((ν(3)μ+ν(2))μ+ν(1))μ+ν(0).  (2.6)

[0235] A Farrow structure 400 (for N=4) that implements equations (2.5) and (2.6) is shown in FIG. 4. It consists of multiplications of data by fixed coefficients, and data multipliers, as well as addition operations.

[0236] 2.2 The Trigonometric Polynomial Method

[0237] To solve the problems discussed in the section 2.1, the present invention utilizes a trigonometric polynomial to fit the asynchronous samples in FIG. 2. Using W_N=e^−j2π/Nnotation, for t ε[−N/2+1, N/2], the polynomial may be written as: $\begin{array}{cc}y\left(t\right)=\frac{1}{N}\left(\sum _{k=-N/2+1}^{N/2-1}{c}_k{W}_N^{-\mathrm{kt}}+\frac{1}{2}{c}_{N/2}{W}_N^{-\left(N/2\right)t}+\frac{1}{2}{c}_{-N/2}{W}_N^{\left(N/2\right)t}\right).& \left(2.7\right)\end{array}$

[0238] The polynomial must cross the N samples. Thus, the coefficients C_kcan be determined by solving the N linear equations in N unknowns: $\begin{array}{cc}y\left(n\right)=\frac{1}{N}\sum _{k=-N/2+1}^{N/2}{c}_k{W}_N^{-\mathrm{kn}},n=-\frac{N}{2}+1,\dots ,\frac{N}{2}& \left(2.8\right)\end{array}$

[0239] whose solution is $\begin{array}{cc}{c}_k=\sum _{n=-N/2+1}^{N/2}y\left(n\right)W_N^{\mathrm{kn}},k=-\frac{N}{2}+1,\dots ,\frac{N}{2}.& \left(2.9\right)\end{array}$

[0240] The expression in (2.9) is simply the N-point discrete Fourier transform (DFT). This suggests that, given N equally-spaced samples, we can compute the DFT of these samples as in (2.9) to obtain the coefficients of the interpolating trigonometric polynomial in (2.7). Then, for a given offset μ, the synchronized sample y(μ) can be computed using that polynomial as: $\begin{array}{cc}y\left(\mu \right)=\frac{1}{N}\left(\sum _{k=-N/2+1}^{N/2}{c}_k{W}_N^{-k\mu }+c_{N/2}\cos \pi \mu \right).& \left(2.10\right)\end{array}$

[0241] Since c_kand c_−kare conjugates, this equation can be simplified as $\begin{array}{cc}y\left(\mu \right)=\frac{1}{N}\mathrm{Re}\left(c_0+2\sum _{k=1}^{N/2-1}{c}_k{W}_N^{-k\mu }+c_{N/2}{e}^{\mathrm{j\pi }\mu }\right).& \left(2.11\right)\end{array}$

[0242] Flowchart 500 in FIG. 5 summarizes the interpolation between two sample points at an offset μ using a trigonometric polynomial, where the two data samples that are to be interpolated are part of a set of N-data samples (see FIG.2). The flowchart is described as follows.

[0243] In step 502, a set of N-data samples are received having the two data samples that are to be interpolated.

[0244] In step 504, coefficients of a trigonometric polynomial are determined based on the set of N data samples, according to equation (2.9). In doing so, the N data samples are multiplied by a complex scaling factor W_N^knto generate a k^thcoefficient for the trigonometric polynomial, wherein W_N=e^−j2π/Nand wherein n represents an n^thdata sample of said N data samples.

[0245] In step 506, the trigonometric polynomial is evaluated at the offset μ based on equation (2.10) or (2.11).

[0246] In step 508, the real part of the evaluated trigonometric polynomial is determined and represents the desired interpolation value 202 in FIG. 2.

[0247] There are three issues that are to be considered in evaluating an interpolation scheme: 1) accuracy of interpolation, 2) complexity of implementation and 3) latency. In following sections, the trigonometric interpolation method is compared to the traditional polynomial method, particularly the Lagrange interpolator, in all these categories.

[0248] 2.3 Performance Comparisons

[0249] Let us first derive the impulse responses of the interpolators. With N samples, N an even integer, the Lagrange formula (2.1) is $\begin{array}{cc}y\left(\mu \right)=\sum _{n=-N/2+1}^{N/2}y\left(n\right)C_n\left(\mu \right).& \left(2.12\right)\end{array}$

[0250] In addition, the interpolation is performed in the center interval. Thus 0≦μ≦1. Let us define a new function f(t) such that

[0251] f(μ−n)=C_n(μ), 0≦μ≦1, −N/2+1≦n≦N/2.  (2.13)

[0252] Using the example of FIG. 3, defining t=μ−n, we have $\begin{array}{cc}f\left(t\right)=(\begin{array}{cc}{C}_2\left(t+2\right)& -2\le t<-1\\ C_1\left(t+1\right)& -1\le t<0\\ C_0\left(t\right)& 0\le t<1\\ C_{-1}\left(t-1\right)& 1\le t<2\\ 0& \mathrm{otherwise}.\end{array}& \left(2.14\right)\end{array}$

[0253] Thus, the Lagrange formula becomes $\begin{array}{cc}y\left(t\right)=\sum _{n=-N/2+1}^{N/2}y\left(n\right)C_n\left(t\right)=\sum _{n=-\infty }^{\infty }y\left(n\right)f\left(t-n\right).& \left(2.15\right)\end{array}$

[0254] Therefore, the approach to reconstruct the continuous signal using the Lagrange polynomial is in fact equivalent to applying an interpolation filter f(t) to the available samples, with f(t) being a piecewise polynomial. The interpolator's impulse response f(t) obtained from (2.14) is shown in FIG. 6A.

[0255] Taking the Fourier transform of f(t), we obtain its frequency response. This allows us to evaluate the interpolation accuracy by examining the frequency response of the interpolation filter. The frequency response 702 of the Lagrange cubic interpolator (N=4) is shown in FIG. 7A. The horizontal axis is the normalized frequency f/F_S, with F_S=1/T_S. An ideal frequency response should have value one in the passband (0≦f/F_S<0.5) and be zero in the stopband (f/F_S≧0.5).

[0256] For the interpolator using a trigonometric polynomial, we can express y(t) in terms of y(n) by substituting (2.9) into (2.10): $\begin{array}{cc}\begin{array}{c}y\left(\mu \right)=\frac{1}{N}\sum _{k=-N/2+1}^{N/2-1}{c}_k{W}_N^{-k\mu }+\frac{1}{N}{c}_{N/2}\cos \pi \mu \\ =\frac{1}{N}\sum _{k=-N/2+1}^{N/2-1}\left(\sum _{n=-N/2+1}^{N/2}y\left(n\right)W_N^{\mathrm{kn}}\right)W_N^{-k\mu }+\\ \frac{1}{N}\left(\sum _{n=-N/2+1}^{N/2}y\left(n\right)W_N^{\left(N/2\right)n}\right)\cos \mathrm{\pi \mu }\\ =\frac{1}{N}\sum _{n=-N/2+1}^{N/2}y\left(n\right)\left(\sum _{k=-N/2+1}^{N/2-1}{W}_N^{k\left(n-\mu \right)}+{\left(-1\right)}^n\cos \pi \mu \right)\\ =\frac{1}{N}\sum _{n=-N/2+1}^{N/2}y\left(n\right)\left(1+2\sum _{k=1}^{N/2-1}\cos \frac{2\pi k}{N}\left(\mu -n\right)+\cos \pi \left(\mu -n\right)\right).\end{array}& \left(2.16\right)\end{array}$

[0257] Defining $\begin{array}{cc}f\left(t\right)=(\begin{array}{cc}1+2\sum _{k=1}^{N/2-1}\cos \frac{2\pi k}{N}t+\cos \pi t& \left|t\right|\le N/2\\ 0& \left|t\right|>N/2\end{array}& \left(2.17\right)\end{array}$

[0258] we have $\begin{array}{cc}y\left(\mu \right)=\frac{1}{N}\sum _{n=-\infty }^{\infty }y\left(n\right)f\left(\mu -n\right)=\frac{1}{N}y\otimes f_{\mu }.& \left(2.18\right)\end{array}$

[0259] The impulse response f(t) in (2.17) is shown in FIG. 6B. The corresponding frequency response 704 of the trigonometric interpolator (for N=4) is shown in FIG. 7A in thin lines.

[0260] By comparing the frequency responses of the two interpolators, we can see that the trigonometric interpolation response 704 has a sharper roll-off in the transition band and more rapid attenuation in the stopband than the Lagrange response 702. These traits are enhanced as N increases, as demonstrated in FIG. 7B. For N=32, the trigonometric response 708 has a sharper rolloff than the Lagrange response 706 as shown in FIG. 7B.

[0261] Next we verify these observations by interpolating the samples of a practical time-domain signal. As an example, we interpolate a baseband signal with raised cosine spectrum and roll-off factor α=1.0, sampled at two samples per symbol period, as shown in FIG. 8A.

[0262] The interpolation accuracy here is measured as the normalized mean-squared difference between the signal interpolated with an ideal interpolator and the signal interpolated with the practical interpolator. The normalized mean-squared error (NMSE), discussed above, is calculated for both the Lagrange interpolator and the trigonometric interpolator for a range of typical values of N. The results are plotted in FIG. 8B.

[0263] Our test results demonstrate that the performance is improved with the trigonometric method. Using the same number of samples to interpolate, the proposed method produces a smaller NMSE, and the performance gain becomes greater as the number of samples increases.

[0264] 2.4 Efficient Implementation Structures

[0265] Recalling from Section 2.2, the trigonometric interpolation algorithm includes substantially two steps:

[0266] Step 1. Given a number of data samples N, calculate the Fourier coefficients c_k, k=0, . . . , N/2 using (2.9). In a preferred embodiment, an even number of N data samples are used. In other embodiments, an odd number of data samples are used.

[0267] Step 2. Compute the synchronized sample y(μ) for any given μ according to (2.11).

[0268] The first step involves multiplying the data samples by complex scaling factors W_N^kn. Since these factors lie on the unit circle, the computation in Step 1 can be simplified. Let us examine the case when N=4:

[0269] For N=4, the Fourier coefficients are obtained as:

[0270] c₀=y(−1)+y(0)+y(1)+y(2)

[0271] c₁=[y(0)−y(2)]+j[−y(1)+y(−1)]

[0272] c₂=y(0)−y(1)+y(2)−y(−1).  (2.19)

[0273] As seen in (2.19), there is no nontrivial scaling multiplier required for N=4.

[0274] We now compute the coefficients c_kin (2.9) for N=8. Using the trigonometric identities, we can obtain the following simple form for c_k, k=0 , . . . , 4: $\begin{array}{cc}{c}_0=y\left(-3\right)+y\left(-2\right)+y\left(-1\right)+y\left(0\right)+y\left(1\right)+y\left(2\right)+y\left(3\right)+y\left(4\right)c_1=\left\{y\left(0\right)-y\left(4\right)+\left[\underset{\_}{-y\left(-3\right)+y\left(1\right)}+\underset{\_}{y\left(-1\right)-y\left(3\right)}\right]\cos \left(\pi /4\right)\right\}+j\left\{y\left(-2\right)-y\left(2\right)+\left[\underset{\_}{y\left(-3\right)-y\left(1\right)}+\underset{\_}{y\left(-1\right)-y\left(3\right)}\right]\cos \left(\pi /4\right)\right\}{c}_2=\left\{-y\left(-2\right)+y\left(0\right)-y\left(0\right)-y\left(2\right)+y\left(4\right)\right\}+j\left\{-y\left(-3\right)+y\left(-1\right)-y\left(1\right)+y\left(3\right)\right\}{c}_3=\left\{y\left(0\right)-y\left(4\right)+\left[\underset{\_}{y\left(-3\right)-y\left(1\right)}+\underset{\_}{\left(-y\left(-1\right)+y\left(3\right)\right)}\right]\cos \left(\pi /4\right)\right\}+j\left\{-y\left(-2\right)+y\left(2\right)+\left[\underset{\_}{y\left(-3\right)-y\left(1\right)}+\underset{\_}{\left(-y\left(-1\right)-y\left(3\right)\right)}\right]\cos \left(\pi /4\right)\right\}{c}_4=-y\left(-3\right)+y\left(-2\right)-y\left(-1\right)+y\left(0\right)-y\left(1\right)+y\left(2\right)-y\left(3\right)+y\left(4\right).& \left(2.20\right)\end{array}$

[0275] The only non-trivial scaling multiplications are those multiplications by cos (π/4). It appears that four such multiplications are needed to compute all the complex coefficients c_k, k=0, . . . , 4. However, if we examine the data being multiplied by cos (π/4) (those terms embraced by the [ ] brackets), we observe that they are either the sums or differences of the [y(−3)−y(1)] and [y(−1)−y(3)] values. Therefore, we can compute [y(−3)−y(1)] cos(π/4) and [y(−1)−y(3)]cos(π/4), then use these two products to generate the c_n, coefficients. Thus, only two scaling multiplications are needed in computing all the coefficients.

[0276] Having observed the simplicity in the first step, let us focus on the second step. The second step may look complicated because of the complex multiplications c_kW_N^−kμ and _N/2e^jπμ. However, since |W_N^−kμ|=|e^jπμ|=1, these products are just rotations of points c_kand c_N/2in the complex plane. Furthermore, this is the same type of operation performed in the phase rotation for carrier recovery by the phase rotator 124 that is shown in FIG. 1D. This suggests that we can reduce the total complexity of the synchronization circuitry by sharing some resources needed by the digital resampler 122 and the carrier phase rotator 124. In one embodiment, a lookup table is utilized to determine the angle rotation associated with the angle $\frac{2\pi }{N}k\mu$

[0277] for rotation of the c_kcoefficients. In another embodiment, an angle rotator processor is utilized. Both embodiments are discussed further below, and the angle rotator processor is discussed in detail in section 5.

[0278] FIG. 10 illustrates a trigonometric interpolator 1000 that is one circuit configuration that implements the trigonometric interpolator equations (2.9)-(2.11), where the number of data samples is N=4. The interpolator 1000 is not meant to be limiting, as those skilled in the arts may recognize other circuit configurations that implement the equations (2.9)-(2.11). These other circuit configurations are within the scope and spirit of the present invention.

[0279] The trigonometric interpolator 1000 receives input data samples having two data samples that are to be interpolated at an offset μ (see FIG. 2). The resulting interpolated value y(μ) represents the interpolated point 202 in FIG. 2. The interpolator 1000 includes a delay module 1004, an adder/subtractor module 1006, and an angle rotator module 1008, and an adder 1012.

[0280] The adder/subtractor module 1006 includes multiple adders (or subtractors) 1014, where subtraction is indicated by a (−) igns sign.

[0281] The angle rotator module includes two angle rotators 1010. The angle rotators 1010 can be configured using an angle rotator processor or a table lookup (e.g. read only memory) as discussed below.

[0282] The operation of the trigonometric interpolator 1000 is discussed further in reference to the flowchart 1700 in FIG. 17, which is discussed below.

[0283] In step 1702, the interpolator 1000 receives a set of N-input data samples. The N-data samples include the two data samples that are to be interpolated at the offset i relative to one of the data samples, as shown in the FIG. 2. In FIG. 2, the interpolation is to be performed between y(0) and y(1) at the offset μ to determine the interpolation value 202.

[0284] In step 1706, the adder/subtractor module 1006 generates one or more trigonometric coefficients according to the equation (2.9). In FIG. 10, the coefficients are represented by C₀, C₁, and C₂for N=4, where the coefficients coefficient C₁is a complex coefficient.

[0285] In step 1708, the angle rotators 1010 rotate appropriate real and complex coefficients in a complex plane according the offset μ, resulting in rotated complex coefficients. More specifically, the angle rotator 1010arotates the real coefficient C₂, and the angle rotator 1010brotates the complex coefficient C₁in the complex plane.

[0286] In embodiments, as discussed herein, the angle rotators 1010 are table look-ups. In which case, a rotation factor is retrieved from the table lookup based on the offset μ, where the rotation factor includes the evaluated cosine and sine functions of $\frac{2\pi }{N}k\mu$

[0287] that are shown in the equations (2.21) below. The rotation factor is then multiplied by the corresponding real or complex coefficient, to generate the respective rotated complex coefficient. An interpolator 1800 having a table lookup ROM 1802 and a complex multiplier 1804 are shown in FIG. 18 for illustration.

[0288] In step 1710, the adder 1012 adds together C₀, a real part of the rotated coefficient C₁, and a real part of the rotated coefficient C₂. The adder 1012 also scales the output of the adder as necessary according to equation 2.10. The resulting value is the desired interpolation value at the offset μ, as represented by point 202 in FIG.2.

[0289] The trigonometric interpolator is not limited to the 4^thdegree embodiment that is shown in FIG. 10. The trigonometric interpolator can be configured as an N^thdegree interpolator based on N_data points, as represented by the equations (2.9)-(2.11). These other N^thdegree interpolators are within the scope and spirit of the present invention. For example and without limitation, FIG. 11 illustrates an interpolator 1100 having N=8. The trigonometric interpolator 1100 includes: a delay module 1102, an adder/subtractor module 1104 (having two scaling multipliers having coefficients cos (π/4)), an angle rotator module 1106, and an adder 1108_(having a ⅛ scale factor that is not shown). The operation of the interpolator 1100 will be understood by those skilled in the arts based on the discussion herein.

[0290] 2.4.1 Using a Lookup Table

[0291] For carrier recovery, the phase correction is generally accomplished by looking up the sine and cosine values corresponding to the phase, then by multiplying these values with the complex data. This requires the same operations as the rotation of c_kby an angle $\frac{2\pi }{N}k\mu ,$

[0292] that is: $\begin{array}{cc}\mathrm{Re}\left(c_k{W}_N^{-k\mu }\right)=\mathrm{Re}\left(c_k\right)\cos \frac{2\pi }{N}k\mu -\mathrm{Im}\left(c_k\right)\sin \frac{2\pi }{N}k\mu \mathrm{Im}\left(c_k{W}_N^{-k\mu }\right)=\mathrm{Re}\left(c_k\right)\sin \frac{2\pi }{N}k\mu +\mathrm{Im}\left(c_k\right)\cos \frac{2\pi }{N}k\mu .& \left(2.21\right)\end{array}$

[0293] The sine and cosine table can be used for both the resampler, as in (2.21), and the phase rotator for carrier recovery. In embodiments, a read only memory (ROM) is utilized as the lookup table. However, other embodiments could be utilized in including other types of memories. An interpolator 1800 utilizing a table lookup ROM 1802 and complex multiplier 1804 are shown in FIG. 18 for illustration. The ROM table access time is insignificant as compared to the computation time in other parts of the interpolator. Therefore, this method results in low hardware complexity and low computational delay. This implementation will be referred to as the table-lookup method.

[0294] 2.4.2 Using an Angle Rotation Processor

[0295] When a very low complexity implementation is desired at the expense of a slight increase in computational delay, we propose to use an efficient structure for angle rotation, which is described in Section 5. Based on this structure, each angle rotator has a hardware complexity slightly greater than that of two multipliers. In addition, a very small ROM is needed. We will subsequently refer to this particular implementation of our algorithm as the angle-rotation method.

[0296] Thus, there are at least two choices for implementing (2.21) as well as the phase rotator for carrier recovery. The trade-off is between complexity and speed. In a base-station where computation power is more affordable, the table lookup method might be used. In a hand-set, where cost is a major concern, an angle rotation processor might be used for both the resampler and the phase rotator, multiplexing the operations.

[0297] Now let us compare the complexity of the trigonometric resampler with that of the Lagrange method. Table 2.1 summarizes the comparisons for several typical N values. The numbers are based on the table-lookup method. It indicates that, for the same filter length N the trigonometric interpolation method needs less hardware.

[0298] 2.5 Delays in the Computation

[0299] The critical path of the Farrow structure 400 (FIG. 4) is now compared to that of the trigonometric interpolator. The Farrow structure implements the Lagrange interpolator as discussed above. The Farrow structure 400 is shown in FIG. 9_(or FIG. 4), with the critical path 902 indicated. The critical path 902 for this structure includes one scaling multip lier 904 and N-1 data multipliers 906.

[0300] In contrast, the critical path for the trigonometric interpolator 1000 is path 1002 and it contains just one angle rotation 1010, or only one multiplier if the table-lookup method is employed to replace the angle rotator 1010. Since the angle rotations for various angles can be carried out in parallel, the critical path does not lengthen as N increases.

[0301] Table 2.1 compares the computational delays for the trigonometric interpolator with that of the Lagrange interpolator for various values of N. The delay data for the trigonometric interpolator 1000 are based on the table-lookup method. As shown in FIG. 10, the trigonometric interpolator (for N=4) has only one multiplier in the critical path, whereas the Lagrange interpolator has 4 multipliers in the critical path. Therefore, the trigonometric interpolator has less latency than the Lagrange interpolator, which is important for voice communications.

[0302] 2.6 Simplifications of the Preliminary Structures

[0303] As mentioned in Section 2.4, to produce each y(μ) we first calculate the Fourier coefficients c_kusing existing samples, according to (2.9). We then compute Re(c_kW_N^−kμ) to be used in (2.11). This is accomplished either by retrieving W_N^−kμ from a lookup table, followed by two real multiplications, or by an angle-rotation processor.

[0304] 2.6.1 The Simplified Structure for N=4

[0305] Let us examine the trigonometric interpolator 1000 having N=4. To compute Re(2c₁W₄^−μ) and Re(c₂W₄^−2μ) the system requires either two angle rotators 1004 or two accesses to a lookup table.

[0306] If the input samples would happen to be such that c₂=0 then one fewer angle rotator, or one fewer ROM access, would be required. Of course, the original data samples y(−1), y(0), y(1), and y(2) are not likely to have the special property that c₂=y(0)−y(1)+y(2)−y(−1)=0. However, if the data samples are changed, then the modified samples can be determined to satisfy c₂=0. If the modified samples for interpolation, then the c₂angle rotator 1010acan be eliminated. However, the interpolation result will not then correspond to the original data samples.

[0307] It seems that the data samples can be changed to attain savings in hardware, as long as the interpolation result is fixed so that it corresponds to the original data samples. Of course, it must also cost less in hardware to “fix” the interpolation result than is saved in hardware by using the modified samples.

[0308] If the samples y(k) are modified to form {tilde over (y)}(k) according to:

[0309] {tilde over (y)}−(1)=y(−1)−K

[0310] {tilde over (y)}(0)=y(0)

[0311] {tilde over (y)}(1) y(1)+K

[0312] {tilde over (y)}(2)=y(2)+2K  (2.22)

[0313] then the K value can be adjusted to force the {tilde over (y)}(k) samples to satisfy c₂=0, where K is the slope of a straight line 1202 in FIG. 12.

[0314] To find K, the c₂value that corresponds to the modified samples is determined according to:

[0315] c₂={tilde over (y)}(0)−{tilde over (y)}(1)+{tilde over (y)}(2)−{tilde over (y)}(−1)

[0316] =y(0)−(y(1)+K)+(y(2)+2K)−(y(−1)−K)

[0317] =2K−(y(1)+y(−1)−y(0)−y(2)).  (2.23)

[0318] To force c₂=0, requires: $\begin{array}{cc}K=\frac{1}{2}\left(y\left(1\right)+y\left(-1\right)-y\left(0\right)-y\left(2\right)\right)& \left(2.24\right)\end{array}$

[0319] Therefore, the c₂angle-rotator can be eliminated, and c₀and c₁are determined accordingly as,

[0320] c₀=2(y(1)+y(−1))

[0321] c₁=[2y(0)−y(1)−y(−1)]+j[−2y(1)+y(0)+y(2)].  (2.25)

[0322] Then, the interpolated sample is $\begin{array}{cc}\tilde{y}\left(\mu \right)=\frac{1}{4}{c}_0+\frac{1}{2}\mathrm{Re}\left(c_1{e}^{j\frac{\pi }{2}\mu }\right).& \left(2.26\right)\end{array}$

[0323] However, {tilde over (y)}(μ) should be adjusted so that it corresponds to the original samples. From FIG. 12, the values expressing the difference between the original and the modified samples lie on the straight line 1202. From FIG. 13, it follows that the offset due to the modification of samples is Kμ. Therefore, the {tilde over (y)}(μ) value can be compensated by:

[0324] y(μ)={tilde over (y)}(μp)−Kμ.  (2.27)

[0325] Using equations (2.25), (2.26) and (2.27) leads to an interpolator 1400 as shown in FIG. 14. This simplified interpolator structure is not limited to N=4 configurations. In fact, this simplification technique can be applied to an interpolator with an arbitrary N value. To eliminate the angle-rotation needed by Re(c_N/2e^jπμ) in (2.11), the samples are modified according to

[0326] {tilde over (y)}(n)=y(n)+nk, n=integer.  (2.28)

[0327] Using (2.9), and then applying (2.28), results in $\begin{array}{cc}{c}_{N/2}=\frac{1}{N}\left(\underset{n=-N/2+1}{\sum ^{N/2}}{\left(-1\right)}^n\tilde{y}\left(n\right)\right)=\frac{1}{N}\left(\underset{n=-N/2+1}{\sum ^{N/2}}{\left(-1\right)}^{n}y\left(n\right)\right)+\frac{1}{2}K.& \left(2.29\right)\end{array}$

[0328] If we choose $\begin{array}{cc}K=-\frac{2}{N}\underset{n=-N/2+1}{\sum ^{N/2}}{\left(-1\right)}^{n}y\left(n\right)& \left(2.30\right)\end{array}$

[0329] we can force c_N/2=0.

[0330] Referring to FIG. 14, the interpolator 1400 includes the delay module 1004, an adder/subtractor module 1402, the angle rotator 1010b, a multiplier 1404, and an adder 1406. The interpolator 1400 has a simplified structure when compared the interpolator 1000 (in FIG. 10), as the interpolator 1400 replaces the angle rotator 1010bwith a multiplier 1404. As discussed above, this can be done because the coefficient C_N/2=0 (C₂=0 for N=4) by modification of the data samples, and therefore there is no need to have an angle rotator for C_N/2. The operation of the interpolator 1400 is further discussed in reference to the flowchart 1900 that follows.

[0331] In step 1902, the interpolator 1400 receives a set of N input data samples. The N data samples include two of the data samples that are to be interpolated at the offset μ, as shown in the FIG. 2.

[0332] In step 1904, the delay module 1004 delays the input data samples.

[0333] In step 1906, the adder/subtractor module 1402 modifies one or more of the data samples so that a coefficient c_N/2is 0. In embodiments the data samples are modified according to y(n)_mod=y(n)+n·K, wherein K is determined by the equation (2.30) above so that c_N/2is 0, and wherein y(n) represents the n^thdata sample of the N data sample set.

[0334] In step 1908, the adder/subtractor module 1402 generates one or more trigonometric coefficients according to modifications to the equation (2.9). In the N=4 case, equations (2.25) are implemented by the module 1402. In FIG. 14, for N=4, the coefficients are represented by C₀and C₁, where the coefficient C₁is a complex coefficient coefficicents. By comparing with FIG. 10, it is noted that the C₂coefficient is 0. Additionally, the adder/subtractor module 1402 outputs the K value for further processing. Notice also that in FIG. 14, the output scaling factor has been changed from ¼ to ½. This reflects several other straightforward simplifications that have been made to module 1402 and in the angle rotator 1010b. In embodiments, the steps 1906 and 1908 are to be performed simultaneously by the adder/subtractor module 1402, as will be understood by those skilled in the relevant arts.

[0335] In step 1910, the angle rotator 1010brotates the complex coefficient C₁in a complex plane according the offset μ, resulting in a rotated complex coefficient. In embodiments, as discussed herein, the angle rotator 1010bis table look-up. In which case, a complex rotation factor is retrieved from the table lookup based on the offset μ, and the resulting rotation factor is then multiplied by the corresponding complex coefficient, to generate the respective rotated complex coefficient. The rotation factor includes the evaluation of the cosine and sine factors that are shown in equations (2.21). Note that since C₂=0, the angle rotator 1010ais replaced with the multiplier 1404.

[0336] In the step 1912, the multiplier 1404 multiplies the K factor by the offset μ, to produce a Kμ factor.

[0337] In step 1914, the adder 1406 adds together C₀and Kμ and a real part of the rotated complex coefficient C₁, and scales the sum by the trivial factor ½, to produce the desired interpolation value. The addition of the Kμ factor compensates the desired interpolation value for the modification that was done to the data samples in order to force C_N/2, to zero in step 1906.

[0338] The simplified trigonometric interpolator is not limited to the four-sample embodiment that is shown in FIG. 14. The simplified trigonometric interpolator can be configured as an N-sample interpolator based on N_data points, as represented by the equations (2.28)-(2.30). These other N-sample interpolators are within the scope and spirit of the present invention. For example and without limitation, an interpolator with N=8 is discussed below.

[0339] 2.6.2 The Simplified Structure for N=8

[0340] According to (2.30), we choose $\begin{array}{cc}K=\frac{1}{4}\left(y\left(1\right)+y\left(3\right)+y\left(-3\right)+y\left(-1\right)-y\left(0\right)-y\left(2\right)-y\left(4\right)-y\left(-2\right)\right).& \left(2.31\right)\end{array}$

[0341] The coefficient values can be computed following this procedure:

[0342] p1=(4K+y(1)−y(−3)) cos π/4

[0343] p2=(4K+y(3)−y(−1)) cos π/4  (2.32)

[0344] c₀=2(y(1)+y(3)+y(−3)+y(−1))

[0345] c₁=[y(0)−y(4)−4K+p1−p2]+j[y(−2)−y(2)−4K−p1−p2]

[0346] c₂=[4K+y(0)+y(4)−y(2)−y(−2)]+j[4K+y(3)+y(−1)−y(−3)]

[0347] c₃=[y(0)−y(4)−4K−p1+p2]+j[−y(−2)+y(2)+4K−p1−p2]

[0348] c₄=0.  (2.33)

[0349] The resulting modified structure for N=8 is shown in FIG. 15 as interpolator 1500. Similar to the interpolator 1400, the interpolator 1500 includes a delay module 1504, an adder/subtractor module 1506, an angle rotator module 1508, a multiplier 1510, and an output scaling adder 1512. As in the interpolator 1400, the multiplier 1510 substantially replaces an angle rotator module. As in the interpolator 1100 for N=8 (FIG. 11), only two non-trivial scaling multiplications are needed for the modified structure 1500.

[0350] 2.6.3 Performance Comparisons with Other Structures

[0351] How does the simplified interpolator 1400 (FIG. 14) perform as compared to the interpolator 1000 (FIG. 10)? FIGS. 16A-C show the frequency responses, in solid lines, of the Lagrange cubic interpolator 400 (FIG. 4), the interpolator 1000 (FIG. 10) and the simplified interpolator 1400 (FIG. 14), respectively. For an input signal whose spectrum is a raised cosine with a=0.4, as shown in dashed lines, the amount of interpolation error corresponds to the gray areas. Clearly, the interpolator 1400 produces less error than the Lagrange cubic interpolator 400 and the interpolator 1000. (FIG. 16D will be discussed in Section 4.)

[0352] The results in Table 2.2 show that the modified structure for N=4 not only requires less hardware, it also obtains the highest accuracy among the three methods for these practical signals used in our simulation.

[0353] 2.7 Trigonometric Interpolator Application

[0354] An important application of the interpolation method and apparatus described in this patent is the following. It is often necessary to increase the sampling rate of a given signal by a fixed integer factor. For example, a signal received at a rate of 1000 samples per second might need to be converted to one at a rate of 4000 samples per second, which represents an increase of the sampling rate by the integer factor four. There are methods in common practice for doing such a conversion. One method is a very popular two-step process wherein the first step creates a signal at the desired higher sampling rate but one where simple zero-valued samples (three of them in the example situation just mentioned) are inserted after each input data value. The second step in the interpolation scheme is to pass this “up-sampled” or “data-rate expanded” signal through an appropriately designed lowpass digital filter which, in effect, smoothes the signal by “filling in” data values at the previously inserted zero-valued samples. In the process of doing this filtering operation it might or might not be important that the original data samples remain intact, and when this is important there exist certain special lowpass filters that will not alter those samples.

[0355] We can easily adapt the trigonometric interpolator described herein to efficiently create such a sampling rate conversion system, but one that does not require such filtering operations. If we denote the integer factor by which we desire to increase the data rate as L (in the above example, L=4) we proceed as follows. We build the system 7800 shown below in FIG. 78). System 7800 includes a Delay Module 7802 and Add/Subtract Module 7804 (that are similar those in FIG. 10), and such that it can accommodate incoming data at a rate r. We now build L copies of the Angle-Rotation Module 7806 (similar to that in FIG. 10), with each one being fed by the same outputs of the Add/Subtract Module. Within each of these L Angle-Rotation Modules 7806 we fix the μ value; that is, each one has a different one of the values: 1/L, 2/L, . . . , (1−L)/L. With such fixed F values, each Angle-Rotation Module 7806 can be constructed as a set of fixed multipliers (a very B17special case of the table-lookup method), although any of the Angle-Rotation Module implementations previously discussed can be employed.

[0356] As shown in FIG. 78, the L−1 outputs, i.e., the interpolated samples that are offset by the values 1/L, 2/L , . . . , (L−1)/L from the first of the two data points (indicated as μ=0 and μ=1 in the Delay Module of FIG. 78) are routed to a multiplexer 7808, along with the input data point from which all interpolated samples are offset. The multiplexer 7808 simply selects these samples, in sequence, and provides them to the output at the expanded data rate L x r.

[0357] A major advantage of the system 7800 is that all of the system's components are operated at the (slow) input data rate except the output multiplexer 7808. If desired, it would also be possible to employ fewer Angle-Rotation Modules 7806, but operating them at a higher data rate, and using several i values, sequentially, for each. This would result in a system that employed less hardware but one that traded off the hardware savings for a higher data rate operation of such modules. 2.8 Trigonomeoric Interpolator Summary

[0358] In this Section we have described an interpolation method that we have devised that uses trigonometric series for interpolation. Comparing the interpolations using the trigonometric polynomial and the Lagrange polynomial of the same degree, the trigonometric-based method achieves higher interpolation accuracy while simultaneously reducing the computation time and the amount of required hardware. Moreover, the trigonometric-based method performs operations that are similar to those of a phase rotator for carrier phase adjustment. This allows a reduction in the overall synchronization circuit complexity by sharing resources.

[0359] This trigonometric interpolator yields less computational delay, as compared to algebraic interpolators. To achieve the same throughput rate, this translates into more savings in hardware using the proposed structure, because the data registers that are required by algebraic interpolators to pipeline the computation for a faster rate would not be needed by our structure.

[0360] We have also introduced two implementations of the trigonometric interpolation method: one using a lookup table, and one using an angle rotation processor (to be discussed in Section 5).

[0361] After introducing a first interpolation method, we have shown that we can trade one angle rotator for a multiplier by conceptually modifying the input samples, then by “correcting” the interpolated value obtained from the “modified” samples. Through this modification, we have obtained a simpler implementation structure while simultaneously improving the performance when interpolating most practical signals. This performance improvement has been demonstrated by comparing the frequency responses of the interpolators and the mean-squared interpolation errors using these interpolators. Our discussion of the optimal digital resampler in Section 4 will be based on this simplified interpolator.

[0362] In Section 2, an interpolation method using a trigonometric polynomial was introduced, along with an example of such an interpolation structure of length N=4. In addition to being a very simple structure, our analyses and simulations also demonstrated that the trigonometric interpolator outperformed the interpolator of the same length using a Lagrange polynomial. In this Section, a more systematic approach will be taken to analyze this method from the digital signal processing point of view. A formula giving its impulse response allows us to analyze the frequency response of the interpolation filter. We then show how to modify the algorithm to achieve arbitrary frequency response. The discussions in this Section will provide the framework for the optimal interpolator of Section 4.

[0363] 3.1 Formulating the Trigonometric Interpolator as an Interpolation Filter

[0364] We have shown that, given N equally-spaced samples y(n), a continuous-time signal can be reconstructed as $\begin{array}{cc}y\left(t\right)=\sum _{n=-N/2+1}^{N/2}y\left(n\right)f\left(t-n\right)& \left(3.1\right)\end{array}$

[0365] where f(t) is the impulse response of a continuous-time interpolation filter. As in Section 2, it is assumed that the sampling period is T_s=1. This assumption makes the notation simpler and the results can easily be extended for an arbitrary T_s. In other words, the invention is not limited to a sampling period of T_s=1, as other sampling periods could be utilized. In Section 2 we have shown that f(t) can be expressed as: $\begin{array}{cc}f\left(t\right)=(\begin{array}{cc}1+2\underset{k=1}{\sum ^{N/2-1}}\cos \frac{2\pi }{N}\mathrm{kt}+\cos \pi t& \left|t\right|\le N/2\\ 0& \left|t\right|>N/2.\end{array}& \left(3.2\right)\end{array}$

[0366] FIG. 20 illustrates f for the trigonometric interpolation filters for N=8 and N=16. By computing the Fourier transform off we obtain the frequency response of the interpolation filter. The frequency responses for the N=8 and N=16 cases are plotted in FIG. 21. Since f(t) is real and symmetric around t=0, its frequency response has zero phase. In FIG. 21, the oscillatory behavior near the band edge is quite obvious. In addition, by comparing FIGS. 21aand b, we can see that as the filter length is increased from N=8 to N=16 the amount of ripple does not decrease. Well known as the Gibbs phenomenon, the magnitude of the ripples does not diminish as the duration of the impulse response is increased.

[0367] It is apparent that the amount of oscillation cannot be reduced using the method discussed thus far while only increasing the filter length N. Moreover, it seems that an arbitrary frequency response cannot be achieved using this method. To address these problems, let us examine how the frequency response of this method is determined.

[0368] 3.2 Analysis of the Frequency Response

[0369] Let us examine how the frequency response off for the trigonometric interpolator is obtained using the example in FIGS. 22 with N=8. According to (3.2), the interpolation filter's impulse response f(t) on the interval $-\frac{N}{2}\le t\le \frac{N}{2}$

[0370] is a weighted sum of cosine functions. We can view the finite-length filter f in (3.2) as having been obtained by applying a window 2206 according to the following: $\begin{array}{cc}w\left(t\right)=\{\begin{array}{cc}1& \left|t\right|\le N/2\\ 0& \left|t\right|>N/2\end{array}& \left(3.3\right)\end{array}$

[0371] to an infinitely-long, periodic function 2204 with period N: $\begin{array}{cc}\begin{array}{c}{f}_c\left(t\right)=1+2\sum _{k=1}^{N/2-1}\cos \frac{2\pi }{N}kt+\cos \pi t-\infty <t<\infty \\ =\sum _{k=-N/2+1}^{N/2-1}{W}_N^{kt}+\frac{1}{2}{W}_N^{-\left(N/2\right)t}+\frac{1}{2}{W}_N^{\left(N/2\right)t}\end{array}& \left(3.4\right)\end{array}$

[0372] such that

[0373] f(t)=f_c(t)w(t),−∞<t<∞.  (3.5)

[0374] Thus F the frequency response off can be obtained by convolving F_cand W the Fourier transforms of f_cand w, respectively.

[0375] The Fourier transform of the periodic function f_c(t),−∞<t <∞, is $\begin{array}{cc}{F}_c\left(\Omega \right)=\sum _{k=-N/2+1}^{N/2-1}\delta \left(\Omega -\frac{2\pi }{N}k\right)+\frac{1}{2}\delta \left(\Omega -\pi \right)+\frac{1}{2}\delta \left(\Omega +\pi \right)& \left(3.6\right)\end{array}$

[0376] which consists of a sequence of impulses 2208. We will subsequently refer to the weights of these impulses as frequency samples. Denoting the weight of $\delta \left(\Omega -\frac{2\pi }{N}k\right)$

[0377] by {circumflex over (F)}(k), we have $\begin{array}{cc}{F}_c\left(\Omega \right)=\sum _{k=-M}^M\hat{F}\left(k\right)\delta \left(\Omega -\frac{2\pi }{N}k\right)& \left(3.7\right)\end{array}$

[0378] where $M\ge \frac{N}{2}$

[0379] is an integer. In the case of (3.6), $M=\frac{N}{2}.$

[0380] For our particular interpolation filter, according to (3.6), all in-band frequency samples {circumflex over (F)}(k) =1 for |k|<N/2. For |k|>N/2, the out-of-band samples {circumflex over (F)}(k) =0. The two samples in the transition band are {circumflex over (F)}(N/2)={circumflex over (F)}(−N/2)=1/2. The transition bandwidth is determined by the distance between the last in-band, and the first out-of-band frequency samples.

[0381] Since w is a rectangular function, W must be a sinc function 2210. Convolving F_cand the sinc function W simply interpolates the frequency samples {circumflex over (F)}(k) to obtain F(ω), −∞≦ω≦∞, shown as response 2212. (Here we have plotted the symmetric F only on the positive half of the ω axis.) We thus have $\begin{array}{cc}\hat{F}\left(k\right)=F\left(\Omega \right){❘}_{\Omega =2\pi k/N},-\frac{N}{2}\le k\le \frac{N}{2}.& \left(3.8\right)\end{array}$

[0382] From response 2212, the continuous-frequency response F(ω) is uniquely determined by an infinite number of equally spaced frequency samples {circumflex over (F)}(k). If we modify the frequency samples 2214 near the passband edge to let the transition between the passband and stopband be more gradual, as depicted in FIG. 23, then the ripple is decreased. FIG. 23 demonstrates gradually reduced samples 2302, and the reduction of ripples in the overall response 2304, as compared to the response 2212 in FIG. 22. The cost of this improvement is an increased transition bandwidth in the response 2304, as compared to the response 2212.

[0383] If a narrower transition band is desired, we can increase the duration of the filter f(t). This can be seen by comparing FIG. 24, where N=16, with response 2304 in FIG. 23, in which N=8.

[0384] 3.3 Implementing the Modified Algorithm

[0385] By comparing (3.6) and (3.4) we can see that the frequency sample values, i.e., the weights of the impulses in (3.6), are determined by the weights in the sum in (3.4).

[0386] We can modify our original interpolation filter in (3.2) for |t|≦N/2 as $\begin{array}{cc}{f}_m\left(t\right)=\hat{F}\left(0\right)+2\underset{k=1}{\sum ^M}\hat{F}\left(k\right)\cos \frac{2\pi }{N}\mathrm{kt}.& \left(3.9\right)\end{array}$

[0387] By expressing (3.9) using the W_Nnotation, for |t|<N/2 we have $\begin{array}{cc}{f}_m\left(t\right)=\hat{F}\left(0\right)W_N^{0t}+\underset{k=1}{\sum ^M}\hat{F}\left(k\right)\left(W_N^{\mathrm{kt}}+W_N^{-\mathrm{kt}}\right)=\underset{k=-M}{\sum ^M}\hat{F}\left(k\right)W_N^{-\mathrm{kt}}.& \left(3.10\right)\end{array}$

[0388] and f_m(t)=0 for |t|>N/2. Substituting this result into (3.1), and re-ordering terms, we have $\begin{array}{cc}y\left(t\right)=\frac{1}{N}\sum _{k=-M}^M{\hat{c}}_k{W}_N^{-kt}& \left(3.11\right)\end{array}$

[0389] where $\begin{array}{cc}{\hat{c}}_k=\hat{F}\left(t\right)\left(\sum _{n=-N/2+1}^{N/2}y\left(n\right)W_N^{\mathrm{kn}}\right).& \left(3.12\right)\end{array}$

[0390] By comparing (3.12) to (2.9), we can see that, for

[0391] $k=-\frac{N}{2}+1,\dots ,\frac{N}{2},$  ĉ_k{circumflex over (F)}(k)c_k.  (3.13)

[0392] Thus, a modified algorithm can be implemented as the following steps:

[0393] Step 1′. (Same as Step 1 in Section 2.4): Given an even number of samples N, calculate the Fourier coefficients C_k, k=0, . . . ,N/2 using (2.9).

[0394] Step 2′: Multiply the coefficients c_kby scale factors {circumflex over (F)}(k) using (3.13).

[0395] Step 3′: Given a fractional delay μ, compute the synchronized samples using (3.11), which, due to ĉ_k=ĉ_−k, can be simplified as: $\begin{array}{cc}y\left(\mu \right)=\frac{1}{N}\mathrm{Re}\left({\hat{c}}_0+2\sum _{k=1}^M{\hat{c}}_k{W}_N^{-k\mu }\right).& \left(3.14\right)\end{array}$

[0396] It seems that, in Step 3′, we need coefficients ĉ(k) (hence c_k) not only for k≦N/2 but also for k>N/2 while only c_kvalues for k≦N/2 are computed in Step 1′. However, c_kvalues for k>N/2 can be obtained using

[0397] C_k=C_k−mN  (3.15)

[0398] where m is an integer such that 0≦k−mN≦N/2. We have (3.15) because c_kis periodic in k with period N, because c_kis obtained from the Fourier transform of the discrete-time signal y(n), −N/2+1≦n≦N/2.

[0399] At this point, we have shown that the continuous-time frequency response of the interpolation filter having impulse response f(t) can be improved by modifying the weights {circumflex over (F)}(k) in (3.10). Now a question arises: the modification of the weights would alter the shape of the impulse response of the f(t) filter. How do we guarantee that the resulting filter does not change the original samples?

[0400] 3.4 Conditions for Zero ISI

[0401] In order for f(t) not to alter the original samples when used for interpolation as in (3.1), it must have zero-crossings at integer multiples of the sampling period: $\begin{array}{cc}f\left(n\right)=\{\begin{array}{cc}1& n=0\\ 0& n\ne 0,n\mathrm{an}\mathrm{integer}.\end{array}& \left(3.16\right)\end{array}$

[0402] The well-known Nyquist condition for zero ISI (Proakis, J. G., Digital Communications, McGraw-Hill, New York, N.Y. (1993)) states that the necessary and sufficient condition for (3.16) is $\begin{array}{cc}\underset{n=-\infty }{\sum ^{\infty }}F\left(\Omega -2\pi n\right)=1-\infty <\Omega <\infty .& \left(3.17\right)\end{array}$

[0403] Since the filter's impulse response f(t) has a finite duration, i.e. f(t)=0 for |t|>N/2, (3.16) holds if and only if the frequency samples {circumflex over (F)}(k) satisfy $\begin{array}{cc}\underset{n=-\infty }{\sum ^{\infty }}\hat{F}\left(k-\mathrm{Nn}\right)=1,k=\mathrm{integer}.& \left(3.18\right)\end{array}$

[0404] The proof is given in Appendix A.

[0405] In summary, we can still guarantee that the modified interpolation filter f does not alter the original samples as long as the modified weights {circumflex over (F)}(k) (frequency samples) satisfy (3.18). Using this constraint, we can design the weights {circumflex over (F)}(k) to meet given frequency response requirements.

[0406] 3.5 Optimization Algorithm

[0407] Using the approach discussed, one can approximate an arbitrary frequency response by choosing appropriate weights {circumflex over (F)}(k). For example, a desired frequency response F_d(Ω) for an interpolation filter should be unity in the passband and be zero in the stopband, as $\begin{array}{cc}{F}_d\left(\Omega \right)=\{\begin{array}{cc}1& -\frac{\pi }{2}\le \Omega \le \frac{\pi }{2}\\ 0& \left|\Omega \right|>\pi .\end{array}& \left(3.19\right)\end{array}$

[0408] The interpolation error using our interpolation filter is defined as

[0409] e(Ω)=W_t(Ω)|F_d(Ω)−F(Ω)|  (3.20)

[0410] where W_t(Ω) is a weighting function.

[0411] From Section 3.2 we have F(Ω)=F_c(Ω){circumflex over (X)} sin c(Ω). Thus, we can express F(Ω) in terms of {circumflex over (F)}(k), using (3.7), as $\begin{array}{cc}\begin{array}{c}F\left(\Omega \right)=\left(\sum _{k=-M}^M\hat{F}\left(k\right)\delta \left(\Omega -\frac{2\pi }{N}\right)\right)\otimes \sin c\left(\Omega \right)\\ =\sum _{k=-M}^M\hat{F}\left(k\right)\sin c\left(\Omega -\frac{2\pi }{N}k\right).\end{array}& \text{(3.21)}\end{array}$

[0412] An optimal interpolation filter can be designed by choosing {circumflex over (F)}(k) to minimize the peak interpolation error, as $\begin{array}{cc}{L}_{\infty }=\underset{\Omega }{\max }\left\{e\left(\Omega \right)\right\}& \left(3.22\right)\end{array}$

[0413] or the mean-squared interpolation error $\begin{array}{cc}{L}_2={\int }_{-\infty }^{\infty }{e}^2\left(\Omega \right)d\Omega & \left(3.23\right)\end{array}$

[0414] subject to the constraint described by (3.18).

[0415] By examining FIGS. 23 and 24, we can see that, by modifying only two frequency samples, those nearest the band edge, a significant improvement is achieved. In these cases we have {circumflex over (F)}(k)=0 for |k|>N/2+1.

[0416] 3.6 Conclusion

[0417] In this Section, an interpolation method was presented that achieves arbitrary frequency response by modifying the trigonometric interpolator discussed in Section 2. Using this approach, the performance of a trigonometric interpolation filter can be further improved.

[0418] It is interesting to note that this procedure is equivalent to the well-known filter design method using windows. FIG. 25adepicts the impulse responses of the original filter (3.2) as the dashed line, and the modified filter (3.9) as the solid line. By comparing the two impulse responses, we have found a function illustrated in FIG. 25b. If we multiply the original impulse response by this function, we get the impulse response that we obtained by modifying the frequency samples. Therefore, this function is equivalent to a window. According to this interpretation, our frequency domain design method is equivalent to designing a better window than the rectangular window (3.3) in the time domain.

[0419] 4.1 Motivation

[0420] We have thus far discussed digital resampling using interpolation methods. To accomplish this, we conceptually reconstruct the continuous-time signal by fitting a trigonometric polynomial to the existing samples and then re-sample the reconstructed signal by evaluating this polynomial for a given sampling mismatch (or offset) μ. The reconstruction of the continuous-time bandlimited signal y(t) from existing samples y(m) using interpolation filter f(t), according to (3.1), is $\begin{array}{cc}y\left(t\right)=\underset{m=-N/2+1}{\sum ^{N/2}}y\left(m\right)f\left(t-m\right).& \left(4.1\right)\end{array}$

[0421] Then y is resampled at t=μ as $\begin{array}{cc}y\left(\mu \right)=\underset{m=-N/2+1}{\sum ^{N/2}}y\left(m\right)f\left(\mu -m\right)=y\otimes f_{\mu }& \left(4.2\right)\end{array}$

[0422] where f_μ(m)=f(m−μ).

[0423] In the previous sections we approached the problem only from the point of view of reconstructing the continuous-time signal, as in (4.1), since we have only examined the frequency response of the continuous-time filter f(t). However, what we actually are interested in is the new sample y(μ) that is obtained by resampling the continuous-time signal at a new sampling instant, t=μ.

[0424] Now, a question arises: Even when the frequency response F(Ω) of the continuous-time filter is optimized as in Section 3.5, do we necessarily obtain the minimum error in producing a new sample y(μ) for each p value?

[0425] According to (4.2), the new sample y(μ) is actually obtained by filtering the original samples y(m) using a discrete-time filter whose impulse response f_μ(m) depends on a particular delay μ. What is the desired frequency response of the f_μ(m) filter?

[0426] A digital resampler that is used in timing recovery simply compensates for the timing offset in sampling the received signal. Ideally, the f_μ(m) filter should not alter the signal spectrum as it simply delays the existing samples by μ. Obviously, the desired frequency response of the discrete-time f_μ(m) filter is

[0427] F_d(ω, μ)=e^jωμ

[0428] where ω is the normalized angular frequency. Let us define the frequency response of f_μ(m) as F_μ(ω). The error in approximating the ideal frequency response F_d(ω, μ) by F_μ(ω) for a given μ value, is

[0429] e(ω)=W_t(ω)|F_d(ω, μ)−F_μ(ω)  (4.4)

[0430] where W_t(ω) is a weighting function.

[0431] We now examine how the discrete-time fractional-delay frequency response F_μ(ω) is obtained. We denote by F(Ω) the Fourier transform of the continuous-time filter f(t). Hence, the Fourier transform of f(t−μ) must be e^−fΩμF(Ω). We know that f_μ(n)=f(n−μ) are just samples off f(t−μ), where −∞<t<∞. Therefore, according to the sampling theorem (Proakis, J. G., Digital Signal Processing, Macmillan, New York, N.Y. (1992)), the Fourier transform of f_μ(n) is $\begin{array}{cc}{F}_{\mu }\left(\omega \right)=\underset{k=-\infty }{\sum ^{\infty }}{e}^{-j\left(\Omega -2\pi k\right)\mu }F\left(\Omega -2\pi k\right)& \left(4.5\right)\end{array}$

[0432] after we replace Ω on the right-hand-side expression by the normalized angular frequency variable ω (ω=Ω since T_s=1). This relationship is shown in FIG. 26, where F(Ω) corresponds to the N=8 interpolator of FIG. 11. As discussed in Section 3.2, f(t) is symmetric around t=0. This implies that F(Ω) has zero phase. To make the f(t) filter physically realizable, of course, we must introduce a delay of N/2, where N corresponds to the length of the filter. However, this delay simply “shifts” all input samples by N/2, which is an integer because N is even, and it does not change the characteristic of the input signal. Thus, it does not influence the interpolation accuracy. Therefore, to simplify our notation, we just use F(Ω) as a real function. Hence, the phase of the complex function e^−fΩμF(Ω) is −Ωμ if F(Ω)≧0, or −Ωμ+π if F(Ω)<0 —the phase depends on μ. FIG. 26 shows that the frequency response of the discrete-time filter F_μ(ω) is obtained by first making an infinite number of copies of e^−fΩμF(Ω) by shifting this function uniformly in successive amounts of 2π, then by adding these shifted versions to e^−fΩμF(Ω). As a sum of complex functions, the shape of F_μ(ω) depends not only on the shape of the continuous-time frequency response F(Ω) but also on the value μ. The dependence of F_μ(ω) on μ is illustrated in FIG. 27, where F_μ(ω) is obtained from the function F(Ω) in FIG. 26, using μ=0.12 and μ=0.5. The magnitude of the ideal fractional-delay frequency response, defined in (4.3), is shown in both FIG. 27A and FIG. 27B as the dashed lines. It is evident that the frequency response 2706 is worse for μ=0.5 than the frequency response 2704 is for μ=0.12, since the response 2706 deviates more from the ideal frequency response 2702 than does the frequency response 2704. Hence, the interpolation error is larger for μ=0.5 than for μ=0.12. We have observed in our simulations that the largest interpolation error occurs when μ=0.5, i.e., when the interpolated sample is exactly in the middle of the two nearest existing samples. As μ approaches 0 or 1 (i.e., as the interpolated sample gets closer to an existing sample), the interpolation error becomes smaller. Moreover, the interpolation errors obtained for μ and 1−μ are the same.

[0433] 4.2 Resampler Optimizations

[0434] In Section 3, we analyzed the relationship between the weights {circumflex over (F)}(k) in (3.9) and the frequency response of the interpolator. We have shown that we can enhance F(Ω) by adjusting the {circumflex over (F)}(k) values. In FIG. 23 (N=8), for example, the {circumflex over (F)}(3) and {circumflex over (F)}(5) values correspond to the magnitude of the pulses 2302 near the band edge. If we adjust {circumflex over (F)}(3) and {circumflex over (F)}(5) such that the transition between the passband and stopband is more gradual, we can achieve a better frequency response.

[0435] To further improve the interpolation performance, we could take μ into account, by optimizing F_μ(ω) for each μ value. As in Section 3, we could adjust {circumflex over (F)}(k) near the band edge to change the shape of F(Ω), for each μ value, such that the discrete-time frequency response F_μ(ω), which is obtained from (4.5), best approximates the desired response of (4.3).

[0436] As discussed in Section 3, to guarantee that the original samples are not altered using the modified interpolator, the weights {circumflex over (F)}(k) should satisfy (3.18). When N=8, for example, we modify {circumflex over (F)}(3) and {circumflex over (F)}(5) together in order to satisfy (3.18). Here, however, our goal of optimization is to obtain the best approximation for the sample corresponding to a specific μ. Hence we need not be concerned with the issue of altering the original samples in Section 3, where there is only one set of optimized weights for all μ values.

[0437] Let us demonstrate this method using the example of N=8. We chose to modify {circumflex over (F)}(3) and {circumflex over (F)}(4). For each given μ, we search for the {circumflex over (F)}(3) and {circumflex over (F)}(4) values such that (4.4) is minimized. We denote such {circumflex over (F)}(3) and {circumflex over (F)}(4) values by {circumflex over (F)}_μ(3) and {circumflex over (F)}_μ(4) respectively, since they are now also dependent on μ. FIGS. 28A and B show the modifications to F(Ω) for μ=0.12 and μ=0.5, respectively. The corresponding optimized F_μ(ω) functions are illustrated in FIGS. 28C and 28D, respectively.

[0438] To demonstrate the performance improvement, let us use this example: Given μ=0.5, we optimize F_μ(ω) for the signal whose spectrum is shown in dashed lines 2902 in FIG. 29. Comparing the un-optimized frequency response 2904 with the optimized frequency response 2906, the modification clearly produces a better frequency response. More specifically, the response 2906 is flat in the frequency band where the power of the signal 2902 is concentrated, and the deviation from the ideal response mostly falls in the “don't care” band.

[0439] Similar to Section 3, to implement this improved method, we first compute the coefficients c_kfrom the existing samples as in (2.9). Then, given the μ value, we multiply, e.g., for N=8, the c₃and c₄values by {circumflex over (F)}_μ(3) and {circumflex over (F)}_μ(4), respectively. Finally, we compute the synchronized sample y(μ) using (2.11), where c₃and c₄are replaced by {circumflex over (F)}_μ(3) c₃and {circumflex over (F)}_μ(4) c₄, respectively.

[0440] We can apply similar modifications to the interpolator with N=4. FIG. 30A show the frequency response of the interpolator 1000, for μ=0.5, while FIG. 30B displays the results of a modified interpolator 1000, where parameters {circumflex over (F)}(1) and {circumflex over (F)}(2) are optimized, for μ=0.5, to maximize the interpolation accuracy for the signal whose spectrum is shown in dashed lines. As can be seen the optimized response 3006 is flatter in the part of the spectrum of the signal 3002 where most of its energy is concentrated than is the un-optimized response 3004.

[0441] The flowchart 3400 in FIG. 34 generalizes the optimization of the trigonometric optimization procedure. The flowchart 3400 is similar to the flowchart 1700, but includes the additional steps of 3402 and 3404 that are described as follows.

[0442] In step 3402, a factor {circumflex over (F)}_μ is determined to adjust the frequency response of the trigonometric interpolator so that it is consistent with the frequency response of N-data samples and the offset μ.

[0443] In step 3404, one or more of the complex coefficients are multiplied by the {circumflex over (F)}_μ to modify the frequency response of the interpolator so that it is consistent with the input signal and the offset μ.

[0444] The optimization routine can also be used with K-modified data samples that leads to the simplified interpolator structures of FIGS. 14 and 15. The flowchart 3500 illustrates the {circumflex over (F)}_μ factor modification in the context of the flowchart 1900.

[0445] As will be shown in the section that follows, the steps 3402, 3404, and 1708 can be combined into a single step if a table lookup is used to determine the rotation factor. In other words, the sine and cosine values can be multiplied by the {circumflex over (F)}_μ factor before they are stored in the ROM.

[0446] In Section 2.6, we have presented an efficient algorithm that eliminates one angle-rotation. For example, for N=4, we can “modify” the input samples according to (2.22). With this modification, we can treat the new samples as if the input signal satisfies c₂=0. The remaining non-zero coefficients are c₀and c₁. In the example for N=4 in the previous Section, two parameters, {circumflex over (F)}_μ(1) and {circumflex over (F)}_μ(2), are optimized to achieve the best approximation of a desired fractional-delay frequency response described by (4.3). Now, with c₂=0, we have only one parameter, {circumflex over (F)}_μ(1), to choose.

[0447] The impulse response of the simplified interpolation filter is derived in Appendix B. From the mathematical expression of the impulse response (B.5), we can obtain the corresponding frequency response. The frequency responses of the interpolator 1400 (FIG. 14) before and after applying the {circumflex over (F)}_μ(1) modification are shown in FIG. 31 A-B, respectively. We can see an improved frequency response 3106 over the response 3104, as the response 3106 is flatter in the part of the signal 3102 where its energy is concentrated. Furthermore, it seems that the frequency response 3106, where only c₁is modified (c₂=0!), is as good as the modified response 3006 in FIG. 30B where both c₁and c₂are modified.

[0448] 4.3 Implementations

[0449] It may appear that additional hardware is needed to implement the multiplication by, for example, {circumflex over (F)}_μ(1) for the simplified N=4 structure. Let us examine the corresponding computations. As we know, we first compute coefficients c₀and c₁according to (2.25) (c₂=0, of course). We then compute y(μ) using $\begin{array}{cc}y\left(\mu \right)=\frac{1}{4}\left(c_0\right)+\frac{1}{2}\mathrm{Re}\left({\hat{F}}_{\mu }\left(1\right)c_1{e}^{j\frac{\pi }{2}\mu }\right)-K\mu & \left(4.6\right)\end{array}$

[0450] according to (2.26) and (2.27), where K is defined in (2.24). As discussed in Section 2.4, the computation $\begin{array}{cc}\mathrm{Re}\left({\hat{F}}_{\mu }\left(1\right)c_1{e}^{j\frac{\pi }{2}\mu }\right)=\mathrm{Re}\left(c_1\right)(\mathrm{Re}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}}\right)-\mathrm{Im}\left(c_1\right)\mathrm{Im}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)& \left(4.7\right)\end{array}$

[0451] can be accomplished by retrieving the ${\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }$

[0452] value from a ROM lookup table and then multiplying Re(c₁)+j Im(c₁) by the retrieved value, since both {circumflex over (F)}_μ(1) and $e^{j\frac{\pi }{2}\mu }$

[0453] can be pre-determined for all μ values.

[0454] If the angle-rotation method is used, we can use a lookup table to store the {circumflex over (F)}_μ(1) values. In real-time, after computing $c_1{e}^{j\frac{\pi }{2}\mu }$

[0455] using an angle-rotation processor, we can multiply the result by {circumflex over (F)}_μ(1). In this case, if {circumflex over (F)}_μ(1) is allowed to be a complex number in optimizing performance, we then need two real multiplications to obtain $\mathrm{Re}\left({\hat{F}}_{\mu }\left(1\right)c_1{e}^{j\frac{\pi }{2}\mu }\right)$

[0456] in (4.6). However, if we restrict {circumflex over (F)}_μ(1) to be a real number, we can use just one real multiplication as $\begin{array}{cc}\mathrm{Re}\left({\hat{F}}_{\mu }\left(1\right)c_1{e}^{j\frac{\pi }{2}\mu }\right)={\hat{F}}_{\mu }\left(1\right)\mathrm{Re}\left(c_1{e}^{j\frac{\pi }{2}\mu }\right)& \left(4.8\right)\end{array}$

[0457] According to Table 4.1, the NMSE using complex and real {circumflex over (F)}_μ(1) values are −37.41 dB and −37.08 dB, respectively. Therefore, the performance degradation caused by restricting {circumflex over (F)}_μ(1) to be a real number is insignificant.

[0458] When the table-lookup method is employed, the implementation structure for the optimal interpolator is the same as that for the interpolator 1400, except for the coefficient c₁which is now multiplied by ${\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }$

[0459] instead of $e^{j\frac{\pi }{2}\mu }.$

[0460] The table should therefore contain the $\mathrm{Re}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)$

[0461] and $\mathrm{Im}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)$

[0462] values, rather than the $\sin \frac{\pi }{2}\mu$

[0463] and $\cos \frac{\pi }{2}\mu$

[0464] values used by the interpolator 1400. We now show that the size of the table is the same as the one storing the sine and cosine values.

[0465] Let us examine the contents of the lookup table. FIG. 32 displays the $\mathrm{Re}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)$

[0466] and $\mathrm{Im}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)$

[0467] values, used by (4.7), where the real values are represented by curve 3202, and the imaginary values are represented by the curve 3204. These values are monotonic with respect to μ, just like the $\sin \frac{\pi }{2}\mu$

[0468] and $\cos \frac{\pi }{2}\mu$

[0469] values for 0≦μ1. Moreover, simulations show that, when optimal values of {circumflex over (F)}(1) are reached, the real and imaginary components of ${\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }$

[0470] display the following complementary relationship: $\begin{array}{cc}\mathrm{Im}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)=\mathrm{Re}\left({\hat{F}}_{1-\mu }\left(1\right)e^{j\frac{\pi }{2}\left(1-\mu \right)}\right).& \left(4.9\right)\end{array}$

[0471] Therefore, we need only store one of the $\mathrm{Re}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)$

[0472] and $\mathrm{Im}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)$

[0473] values. The other can be obtained by looking-up the value corresponding to 1−μ. This is the same technique used in storing and retrieving the sine and cosine values with the purpose of reducing the table size.

[0474] Various circuit implementations of optimized interpolators having N=4 are illustrated in FIGS. 36-37. These circuit implementations are presented for example purposes only and are not meant to be limiting, as those skilled in the arts will recognize other circuit implementation based on the discussion given herein, including interpolator configurations having different N values.

[0475] FIG. 36 illustrates an optimized interpolator 3600 that is based on the simplified interpolator 1400 (FIG. 14). The interpolator 3600 includes an {circumflex over (F)}_μ ROM 3602 and a multiplier 3604. The ROM 3600 stores the appropriate {circumflex over (F)}_μ value indexed by μ. The multiplier 3604 multiples the complex coefficient C₁by the appropriate {circumflex over (F)}_μ value, and therefore optimizes the frequency response of the interpolator 3600. As discussed above, the order of the angle rotator 1010band the multiplier 3604 can be interchanged so that the rotated complex coefficient is modified by the {circumflex over (F)}_μ value.

[0476] FIG. 37 illustrates an optimized interpolator 3700 that is similar to the optimized interpolator 3600, except that the {circumflex over (F)}_μ ROM 3602, the multiplier 3604, and the angle rotator 1010bare combined into to a single ROM 3702, that stores the $\mathrm{Re}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)$

[0477] and $\mathrm{Im}\left({\hat{F}}_{\mu }\left(1\right)e^{j\frac{\pi }{2}\mu }\right)$