# US 6,732,058 B2 · Method and apparatus for computation reduction for tone detection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,732,058 B2
- Document ID: US6732058B2
- Status: Granted
- Kind: B2
- Application number: 10/134,382
- Filed: 2002-04-30
- Published: 2003-09-25
- Granted: 2004-05-04
- Earliest claimed: 2002-03-20
- Assignees: Tropic Networks Inc.
- Inventors: Dongxing Jin; Ping Wan; Derrick Remedios; Leonard Marziliano
- Web page: https://patentgrep.com/patent/US6732058B2

## CPC

- G06F 17/142: {Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm}
- G06F 17/141: {Discrete Fourier transforms}
- G06F 17/147: {Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform (G06F17/145 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Various methods and apparatuses are provided for performing a radix-M FFT (Fast Fourier Transform) upon N time domain samples to produce N/S frequency domain samples for detecting tones of dithers impressed on channels of a WDM (wavelength Division Multiplexed) optical signal. Successive tones have a tone frequency spacing, Δfta, and a sampling frequency, fs, is chosen so that fs=NΔfta/S. S is a spacing given by S=Mw with w being an integer. The radix-M FFT is performed in k=logm(N) stages and within the stages a reduced number of radix-M computations, when compared to the number of radix-M computations of a conventional radix-M FFT, are performed on data points associated with the N time domain samples. This is possible because successive frequency domain samples of the N/S frequency domain samples differ by Δfta=SΔf where Δf is a frequency bandwidth.

## Claims

### Claim 1

A method of performing a radix-M FFT (Fast Fourier Transform), wherein M is an integer satisfying M≧2, the method comprising:
sampling a signal, containing tones, with a sampling frequency, fs, to produce N time domain samples each initializing a respective one of N data points, wherein N is an integer; and
to produce frequency domain samples having a frequency bandwidth Δf=fs/N and center frequencies of frequency spacing MwΔf with w being an integer satisfying w≧1:
performing, for each one of k stages wherein k=logM(N), radix-M computations upon a respective subset of the N data points, wherein the respective subset contains only data points upon which the frequency domain samples that contain the tones are dependent;
wherein the sampling frequency, fs, is such that the frequency domain samples contain the tones.

### Claim 2 (depends on 1)

A method according to claim 1 wherein the performing, for each one of k stages wherein k=logM(N), radix-M computations comprises:
for a stage, r, of the k stages wherein r is an integer satisfying 1≦r≦w, performing N/Mr radix-M computations upon the respective subset of the N data points; and
for a stage, r, of the k stages wherein w<r≦k, performing N/Mw+1 radix-M computations upon the respective subset of the N data points.

### Claim 3 (depends on 2)

A method according to claim 2 wherein the performing, for each one of k stages wherein k=logM(N), radix-M computations comprises a total of Ncomp radix-M computations given by N comp = N S ⁢ ( k - w M + M w - 1 M - 1 ) .

### Claim 4 (depends on 1)

A method according to claim 1 wherein the tones have a frequency spacing, Δfta, and the sampling frequency, fs, satisfies fs=NΔfta/Mw.

### Claim 5 (depends on 4)

A method according to claim 4 applied to a WDM (Wavelength Division Multiplexed) optical signal having a plurality of channels wherein at least some of which each have impressed a unique dither resulting in a respective unique tone of the tones, the respective unique tone having a tone frequency, fta, satisfying fta=aΔfta+C where a is an integer and C in a positive real number.

### Claim 6 (depends on 5)

A method of determining channel power of the WDM optical signal of claim 5 comprising converting a power associated with a respective one of the frequency domain samples into a channel power.

### Claim 7 (depends on 5)

A method according to claim 5 wherein C=n′Δf, wherein n′ is an integer and wherein the tone frequency, fta, satisfies fta=(aS+n′)Δf wherein S is an integer satisfying S=Mw.

### Claim 8 (depends on 7)

A method according to claim 7 comprising identifying which block of data of block number d, of S blocks of data each comprising N′=N/S respective data points of the N data points, contains data points upon which the frequency domain samples are dependent, d and N′ being integers and wherein d=mod(n′,S).

### Claim 9 (depends on 8)

A method according to claim 8 comprising re-ordering, using bit reversal operations, data points contained in the block of data of block number d.

### Claim 10 (depends on 1)

A method according to claim 1 comprising performing the radix-M FFT using DIF (Decimation In Frequency).

### Claim 11 (depends on 1)

A method according to claim 1 comprising performing the radix-M FFT using DIT (Decimation In Time).

### Claim 12

A method of performing a radix-M FFT, wherein M is an integer satisfying M≧2, the method comprising:
sampling a signal, containing tones, with a sampling frequency, fs, to produce a sequence of 2N real valued time domain samples, wherein N is an integer;
splitting the sequence of 2N real valued time domain samples into two sequences of N real valued data points and combining the two sequences of N real valued data points into a sequence of N complex valued data points; and
to produce frequency domain samples having a frequency bandwidth, Δf=fs/N, and center frequencies of frequency spacing MwΔf with w being an integer satisfying w≧1, comprising:
performing, for each one of k stages wherein k=logM(N), radix-M computations upon a respective subset of the sequence of N complex valued data points, wherein the respective subset contains only data points upon which the frequency domain samples are dependent; and
applying a split function only to data points of the sequence of N complex valued data points upon which the frequency domain samples are dependent after the performing, for each one of k stages wherein k=logM(N), radix-M computations;
wherein the sampling frequency, fs, is such that the frequency domain samples contain the tones.

### Claim 13 (depends on 12)

A method according to claim 12 comprising re-ordering, using bit reversal operations, data points obtained from the split function which correspond to the frequency domain samples.

### Claim 14 (depends on 12)

A method according to claim 12 applied to a signal containing tones of tone frequencies, fta, given by fta=(aS+n′)Δf, wherein a, n′ and S are integers with S=Mw, the method comprising:
identifying which block of data of block number d, of S blocks of data each containing N′=N/S respective data points of the sequence of N complex valued data points, contains data points upon which the split function is applied, wherein d and N′ are integers; and
wherein d=mod(n′,S) and the sampling frequency, fs, being such that d is one of d=0 and d=S/2 when S is an even integer and d=0 when S is an odd integer.

### Claim 15

A processing apparatus adapted to perform a radix-M FFT upon N time domain samples, wherein N and M are integers with M≧2, sampled at a sampling frequency, fs, from a signal containing tones to produce frequency domain samples that contain the tones, the apparatus comprising:
a memory adapted to store data comprising N data points each being initialized by a respective one of the N time domain samples;
a processor capable of accessing the memory and adapted to:
perform, for each one of k stages wherein k=logM(N), radix-M computations upon a respective subset of the N data points, wherein the respective subset contains only data points upon which the frequency domain samples that contain the tones are dependent;
wherein the frequency domain samples have a frequency bandwidth, Δf=fs/N, and have center frequencies of frequency spacing MwΔf with w being an integer satisfying w≧1, the sampling frequency, fs, being such that the frequency domain samples contain the tones.

### Claim 16 (depends on 15)

An apparatus according to claim 15 wherein the processor is adapted to perform:
for a stage, r, of the k stages wherein r is an integer satisfying 1≦r≦w, N/Mr radix-M computations upon a respective subset of the N data points upon which the frequency domain samples that contain the tones are dependent; and
for a stage, r, of the k stages wherein w<r≦k, performing N/Mw+1 radix-M computations upon a respective subset of the N data points upon which the frequency domain samples that contain the tones are dependent.

### Claim 17 (depends on 16)

An apparatus according to claim 16 wherein the processor is adapted to perform a total of N comp = N S ⁢ ( k - w M + M w - 1 M - 1 )
radix-M computations which comprise the N/Mr radix-M computations and the N/Mw+1 radix-M computations.

### Claim 18 (depends on 15)

An apparatus according to claim 15 wherein successive tones of the tones have a constant frequency spacing, Δfta, and the sampling frequency, fs, satisfies fs=NΔfta/Mw.

### Claim 19 (depends on 18)

An apparatus according to claim 18 wherein the processor is adapted to instruct a signal detector to sample the N time domain samples at the sampling frequency, fs, given by fs=NΔfta/Mw.

### Claim 20 (depends on 18)

An apparatus according to claim 18 applied to a WDM optical signal having a plurality of channels wherein at least some of which each have impressed a unique dither resulting in a respective unique tone of the tones, the respective unique tone having a tone frequency, fta, satisfying fta=aΔfta+C where a is an integer and C in a positive real number.

### Claim 21 (depends on 20)

An apparatus according to claim 20 wherein the processor is further adapted to convert a power associated with a frequency domain sample, of the frequency domain samples that contain the tones, into a channel power of a respective one of the plurality of channels.

### Claim 22 (depends on 20)

An apparatus according to claim 20 wherein C=n′Δf, wherein n′ is an integer and wherein the tone frequency, fta, satisfies fta=(aS+n′)Δf wherein S is an integer satisfying S=Mw.

### Claim 23 (depends on 20)

An apparatus according to claim 20 wherein the processor is adapted to identify which block of data of block number d, of S blocks of data each comprising N′=N/S respective data points of the N data points, contains data points upon which the frequency domain samples that contain the tones are dependent, wherein d and N′ are integers and wherein d=mod(n′,S).

### Claim 24 (depends on 15)

An apparatus according to claim 15 wherein the processor is adapted to perform the radix-M FFT using DIF.

### Claim 25 (depends on 15)

An apparatus according to claim 15 wherein the processor is adapted to perform the radix-M FFT using DIT.

### Claim 26 (depends on 15)

An apparatus according to claim 15 comprising a DMA (Direct Memory Access) unit and wherein the memory comprises an internal memory and an external memory, the external memory being adapted to store the N data points and respective twiddle factors used in the N/Mr radix-M computations and the N/Mw+1 radix-M computations and the DMA unit being adapted to import and export any of the N data points and the respective twiddle between the internal memory and the external memory.

### Claim 27 (depends on 26)

An apparatus according to claim 26 wherein the DMA unit is adapted to partially re-order the frequency domain samples that contain the tones using bit reversal operations and wherein the processor is adapted to re-order the frequency domain samples that contain the tones, which are partially re-ordered, using bit reversal operations.

### Claim 28 (depends on 15)

An apparatus according to claim 15 adapted to re-order the frequency domain samples that contain the tones using bit reversal operations.

### Claim 29 (depends on 15)

An apparatus according to claim 15 wherein the processor is a CPU (Central Processor Unit).

### Claim 30

A processing apparatus adapted to perform a radix-M FFT upon a sequence of 2N real valued time domain samples, wherein N and M are integers with M≧2, sampled at a sampling frequency, fs, from a signal containing tones to produce frequency domain samples that contain the tones, the apparatus comprising:
a memory adapted to store data comprising the sequence of 2N real valued time domain samples;
a processor capable of accessing the memory and adapted to:
split the sequence of 2N real valued time domain samples into two sequences of N real valued data points and combine the two sequences of N real valued data points into a sequence of N complex valued data points;
perform, for each one of k stages wherein k=logM(N), radix-M computations upon a respective subset of the sequence of N complex valued data points, wherein the respective subset contains only data points upon which the frequency domain samples that contain the tones are dependent; and
apply a split function only to data points of the sequence of N complex valued data points upon which the frequency domain samples that contain the tones are dependent after the radix-M computations are performed for each one of the k stages;
wherein the frequency domain samples have a frequency bandwidth, Δf=fs/N, and center frequencies of frequency spacing MwΔf with w being an integer satisfying w≧1, the sampling frequency, fs, being such that the frequency domain samples contain the tones.

### Claim 31 (depends on 30)

An apparatus according to claim 30 adapted to re-order, using bit reversal operations, data points obtained from the split function which correspond to the frequency domain samples that contain the tones.

### Claim 32 (depends on 30)

An apparatus according to claim 30 applied to a signal containing tones of tone frequencies, fta, given by fta=(aS+n′)Δf, wherein a, n′ and S are integers with S=Mw, the processor being adapted to identify which block of data of block number d, of S blocks of data each containing N′=N/S respective data points of the sequence of N complex valued data points, contains data points upon which the split function is applied, wherein d and N′ are integers; and
wherein d=mod(n′,S) and wherein the sampling frequency, fs, is such that d is one of d=0 and d=S/2 when S is an even integer and d=0 when S is an odd integer.

### Claim 33

An article of manufacture comprising:
a computer usable medium having computer readable program code means embodied therein for causing a radix-M FFT upon a sequence of N time domain samples, wherein N and M are integers with M≧2, sampled at a sampling frequency, fs, from a signal containing tones to produce frequency domain samples that contain the tones, the N time domain samples each initializing a respective one of N data points and the computer readable code means in said article of manufacture comprising:
computer readable code means for performing, for each one of k stages wherein k=logM(N), radix-M computations upon a respective subset of the N data points, wherein the respective subset contains only data points upon which the frequency domain samples that contain the tones are dependent;
computer readable code means for determining the sampling frequency, fs, so that the frequency domain samples have a frequency bandwidth, Δf=fs/N, and have center frequencies of frequency spacing MwΔf with w being an integer satisfying w≧1, and so that the frequency domain samples contain the tones.

### Claim 34 (depends on 33)

An article of manufacture according to claim 33 comprising computer readable code means for re-ordering, using bit reversal operations, data points of the N data points, which correspond to the frequency domain samples that contain the tones after the radix-M computations are performed for each one of the k stages.

### Claim 35

An article of manufacture comprising:
a computer usable medium having computer readable program code means embodied therein for causing a radix-M FFT upon a sequence of 2N real valued time domain samples, wherein N and M are integers with M≧2, sampled at a sampling frequency, fs, from a signal containing tones to produce frequency domain samples that contain the tones, the computer readable code means in said article of manufacture comprising:
computer readable code means for splitting the sequence of 2N real valued time domain samples into two sequences of N real valued data points and combining the two sequences of N real valued data points into a sequence of N complex valued data points; and
computer readable code means for performing, for each one of k stages wherein k=logM(N), radix-M computations upon a respective subset of the N complex valued data points, wherein the respective subset contains only data points upon which the frequency domain samples that contain the tones are dependent;
computer readable code means for applying a split function only to data points of the sequence of N complex valued data points upon which the frequency domain samples are dependent after the performing, for each one of k stages wherein k=logM(N), radix-M computations; and
computer readable code means for determining the sampling frequency, fs, so that the frequency domain samples have a frequency bandwidth, Δf=fs/N, and have center frequencies of frequency spacing MwΔf with w being an integer satisfying w≧1, and so that the frequency domain samples contain the tones.

### Claim 36 (depends on 35)

An article of manufacture according to claim 35 comprising computer readable code means for re-ordering, using bit reversal operations, data points obtained from the split function which correspond to the frequency domain samples that contain the tones.
