WO1995001673A1

WO1995001673A1 - Filter windows for fourier transform signal compression

Info

Publication number: WO1995001673A1
Application number: PCT/AU1994/000364
Authority: WO
Inventors: Gregory Keith Smart; Alan Bernard Bradley
Original assignee: Royal Melbourne Institute Of Technology
Priority date: 1993-06-30
Filing date: 1994-06-30
Publication date: 1995-01-12

Abstract

A method of compressing the required bandwidth of an input signal includes subjecting the input signal to an input filter window (23) which is a first function of time h(r). The signal is then transformed to the frequency domain (24), and a modified signal is synthesised in the frequency domain (32). The modified signal is inversely transformed to the time domain (51) to derive an intermediate signal, which is subjected to an output filter window (56) which is a second function of time f(r) to derive a synthesised output signal (58) of compessed bandwidth with respect to the input signal. The functions h(r) and f(r) are different but satisfy a predetermined relationship independent of the synthesis, selected to optimise the reconstruction of the input signal in the synthesised output signal.

Description

FILTER WINDOWS FOR FOURIER TRANSFORM SIGNAL COMPRESSION

Field of the Invention

This invention relates to Fourier transform or frequency domain sig compression and is concerned in particular with the forms of analysis and synth filter windows employed in this process.

Background Art

Fourier transform signal compression has particular potential for audio sig processing because it is capable of readily handling mixed digital signal strea including, e.g. data and fax components. The alternative linear predictive codi (LPC) codes the signals in terms of a set of most common patterns, but t technique makes assumptions about voice patterns which may not be entirely va across different languages and population groups, has difficulty accommodating d and fax signals, and requires a significant time slice to complete each analysis. U recently, however, it was thought that Fourier transform signal compression, in whi compression coding is achieved by selecting only significant frequency bands in t frequency domain, was limited by apparent restrictions on the useful forms of filt windows applied in the time domain at the input (or analysis) and output (synthes transformations. More particularly, it was considered that, to achieve substantia perfect reconstruction in the output signal, the analysis and synthesis windows sho be identical, and should be limited to a time domain window shape that satisfie condition for time domain aliasing cancellation and for which the analysis a synthesis windows added to unity. This restriction prevented wider use of otherwi optimum window shapes such as the Dolph-Chebyshev.

The present inventors have recently demonstrated [ISSPA 92 (Internatio

Symposium on Signal Processing and its Applications) August 1992, Gold Coa Australia], that the conditions of aliasing cancellation and summation to unity co be decoupled and that an extra degree of freedom in the choice of windows cou thereby be achieved by providing a series pair of synthesis windows - a prima window identical to the analysis window, and an equalisation window defined by

w(r) = flr+m¹ + M²

where w(r) is the equalisation window function, f(r) represents both the analysis a synthesis window functions, r is a time variable, and M the interval betwe successive time marks.

Disclosure of the Invention

It has now been realised, in accordance with the invention, that the analys and synthesis windows can in fact be different, that relationships can be foun between the functions for the two windows which ensure optimal reconstructio independently of the compression coding applied in the frequency domain.

The invention accordingly provides a method of compressing the require bandwidth of an input signal, comprising: subjecting the input signal to an input filter window which is a first functio of time h(r); transforming the signal to the frequency domain; synthesising a modified signal in the frequency domain; inverse transforming the modified signal to the time domain to derive a intermediate signal; and subjecting said intermediate output signal to an output filter window whic is a second function of time f(r) to derive a synthesised output signal of compresse bandwidth with respect to said input signal; wherein the functions h(r) and f(r) are different but satisfy a predetermine relationship independent of said synthesis, selected to optimise the reconstruction o said input signal in said synthesised output signal. The invention also provides apparatus for compressing the required bandwid of an input signal, comprising: means for subjecting the input signal to an input filter window which is a fi function of time h(r); means for transforming the signal to the frequency domain; means for synthesising a modified signal in the frequency domain; means for inverse transforming the modified signal to the time domain derive an intermediate signal; and means for subjecting said intermediate signal to an output filter window whi is a second function of time f(r) to derive a synthesised output signal of compress bandwidth with respect to said input signal; wherein the functions h(r) and f(r) are different but satisfy a predetermine relationship independent of said synthesis, selected to optimise the reconstruction said input signal in said synthesised output signal.

The invention still further provides a method ' f deriving a synthesised digit data stream from an input digital data stream comprising: subjecting the input data stream to an input filter window which is a fir function of time h(r); transforming the data stream to the frequency domain; synthesising a modified data stream in the frequency domain; inverse transforming the modified data stream to the time domain to deriv an intermediate data stream; and subjecting the intermediate data stream to an output filter window which i a second function of time f(r) to derive a synthesised digital data stream o compressed bandwidth with respect to said input data stream; wherein the functions h(r) and f(r) are different but satisfy a predetermine relationship independent of said synthesis, selected to optimise the reconstruction o said input data stream in said synthesised output data stream.

The transformation and inverse transformation may comprise Fourie transformations, and in particular, Cosine modulations. The optimisim preferably includes increasing the accuracy of th transformation to the frequency domain.

The input signal is preferably a digital input signal and may, in one ver useful application, comprise a digital audio signal, e.g. a digital voice signal. Th filter windows are preferably applied by multiplying the respective signals by th respective window functions for each of a number of preselected frequency bands i accordance with said Fourier transformation.

The synthesis step or synthesis means preferably includes deriving th modified signal with values for a limited segment of the frequency band of th Fourier transformed signal, or for only selected frequencies thereof.

Preferably, the input and output filter windows are symmetrical.

A preferred universal relationship between said window functions, at least fo symmetrical input (analysis) and output (synthesis) window functions h(r) and f(r), is:-

- — Λ(r) r²- +s ha( —r+M (i)

where r is the time relative to a regular time mark and M is the time interval between successive time marks.

The digital input signal may conveniently be in accordance with Pulse Code

Modulation (PCM) format, for example 64K PCM where 8 bits values representing a sample are produced at the rate of 8000 per second.

The synthesis, or coding, step may be effected by allocating bits to frequency bands according to strength counts which are computed by: (a) Computing the power in each frequency band;

(b) Finding the greatest power in any band;

(c) Setting a threshold at half that power, and adding 1 to the strengt count for each band which exceeds that threshold; and (d) Repeating step (c) for 5 or more times.

Where the input signal is an analogue signal, it is preferably first converte to digital form, e.g. by any convenient known technique such as PCM coding.

Preferably, where the signal is an audio signal derived from a telephon system, the frequency range of the signal is divided into 64 bands of 62.5 Hz eac and 8 bits are allocated to each band for each 8 millisecond interval which i processed. It is commonly found that 12 or fewer bands have sufficient strength t be significant, and that the strength can be accurately encoded with an average o 4 bits for each of the 12 or fewer bands which need to be described in an transmission. Naturally, it is necessary to provide "control" information to speci which bands have been described in the transmitted signal and the number of bit allocated to each. In reconstruction, the signal in all bands which are not specifie in this control information is assumed to be zero.

Brief Description of Drawings

The invention will be further described, by way of example only, wit reference to the accompanying drawings, in which:

Figure 1 is a block diagram of suitable signal processing apparatus which ma be programmed to provide apparatus according to an embodiment of the invention

Figures 2 and 3 are flow charts depicting successive steps of a compressio method according to a preferred embodiment of the invention; and

Figure 4 is a diagram showing suitable window functions for the input and output filter windows.

Disclosure of Preferred Embodiments

The inventive method may be effected in a suitably programmed digital sign processor such as, for example, the TI 320C30 processor available from Texa Instruments, Inc. Figure 1 is a block diagram of an EVM 30 evaluation module fo the TI 320C30 processor, obtainable as an integrated circuit board for a persona computer system. The processor chip 320C30, designated at 12, is coupled to th main bus 15 of a personal computer 17 via an emulation chip 12, built into th processor chip, and a suitable interface 14. Processor chip 12 is also fitted with memory chip 16, a serial input port 18, and a CODEC 20.

To carry out the method of the invention, an appropriate program is loade into processor chip 12 and stored in memory 16. A preferred program carries ou the steps set out in the flow chart comprising Figures 2 and 3. A digital data stream at serial input port 18, is fed through a 128-byte buffer 22, multiplied by an analysi window filter function h(r) at 23 and then transformed to the frequency domain b transform 24 to provide frequency data 26. Transfer 24 is effectively a Cosin modulation consisting of a fast-Fourier transform 28 between respective comple modulations 30.

Frequency data 26 is then manipulated to synthesise a modified signal at 3 in the frequency domain. In an initial coder stage 45, the data 47 is serially treate in successive subsets 40 comprising three blocks of data, for example each of 8 msec length. Bits are allocated to these blocks of data (42) and the value of the bits is determined as quantisised coefficients (44) in dependence on vector quantisation of side information (46) and a determination of data block power (48). A bit stream 50 is thereby obtained and processed in a decoder stage 49 to derive the modified signal at 32 in the manner set out in Figure 3. The modified signal is now inverse transformed to the time domain, again by a Cosine modulation 51 utilising inverse fast-Fourier transfoπn 52 and a pair of complex modulations 54. Signal 53 is subjected to an output filter window function f(r) at 56 to derive a synthesised outpu signal 58 of compressed bandwidth with respect to input signal at port 18.

As discussed, functions (h(r) and f(r) are selected so that they are differen but satisfy a predetermined relationship independent of the synthesis stage effecte in coder 45 and decoder 49, which relationship is selected to optimise th reconstruction of the input signal in the synthesised output signal.

At this point it is proposed to demonstrate the derivation of relationship (1 above. Given a symmetrical input (analysis) window function h(r) and a symmetrica output (synthesis) window function f(r), it can be shown (e.g. CITRI publication TR 91-8 Dec 1991) that aliasing is cancelled if:

Λ(r)flr+Af)-Λ(r+A_Q/(r)=0 (2)

and that the output signal will have the same strength at all frequencies and times as the input signal if

Λ(r+iW) (r+Λ )+Λ(r) (r)=l (3)

To obtain a solution for f(r) in terms of h(r), first multiply (1) by h(r+M), and (3) by h(r) to get ...

and A(r)A(r+A_ /(r+Af)+Λ(r)^(r)=A(r) (5)

respectively. Then subtract (4) from (5) to obtain

Λ(r)²Λr)+A(r+A_ ²y(r)=A(r) (6)

This can be solved for f(r) to yield

f)

Λr)= (1) h(r)²+h(r+M

An example of a favourable application of the invention, and in particular o the relationship (1) above, will now be described. It has already been noted ho restrictions set by traditional teaching have prevented wider use of otherwis optimum window shapes such as the Dolph-Chebyshev. These window functions were not previously used because of the requirement for identical analysis and synthesis windows: if these were to be Dolph-Chebyshev windows, one could not obtain a uniform unity multiple in all parts of the frequency spectrum, nor arrange for perfect ahas cancellation. On the other hand, the frequency responses for Dolph Chebyshev (and indeed also for Kaiser-bessel) windows are high (>-20dB) up to 200 Hz, but are very low (<-40dB or -60dB) at high frequencies. Thus each frequency band is more sharply selected yielding higher signal quality.

The present invention overcomes these limitations and permits Dolph-

Chebyshev functions to be utilised for both h(r) and f(r). Figures 4 depicts a pair of Dolph-Chebyshev filter window functions which satisfy relationship (1). A test circuit was set up for voice and data transmission, incorporating signal compression according to the invention. The input and output windows h(r) and f(r) were selected to be these different but symmetrical Dolph-Chebyshev functions related in accordance with relationship (1). The data input signal was 64K PCM and synthesis in the frequency domain was in accordance with steps (a) to (d) above.

A high quality of voice transmission was observed, by comparison wit conventional comparison circuits, while the quality of the reconstruction in th output signal was indicated by the high rate of transmission of fax data signa utilising the test circuit.

A further example of a window shape or function to which the invention advantageously applicable is the Kaiser-Bessel window.

Throughout this specification and the claims which follows, unless the conte requires otherwise, the word "comprise", or variations such as "comprises" o "comprising", will be understood to imply the inclusion of a stated integer or grou of integers but not the exclusion of any other integer or group of integers.

Claims

CLAIMS:-

1. A method of compressing the required bandwidth of an input signa comprising: subjecting the input signal to an input filter window which is a first functio of time h(r); transforming the signal to the frequency domain; synthesising a modified signal in the frequency domain; inverse transforming the modified signal to the time domain to derive a intermediate signal; and subjecting said intermediate output signal to an output filter window whic is a second function of time f(r) to derive a synthesised output signal of compresse bandwidth with respect to said input signal; wherein the functions h(r) and f(r) are different but satisfy a predetermine relationship independent of said synthesis, selected to optimise the reconstruction o said input signal in said synthesised output signal.

2. A method according to claim 1 wherein said transformation and invers transformation comprise respective Cosine modulations.

3. A method according to claim 1 or 2 wherein said transformation and invers transformation include Fourier transformations.

4. A method according to claim 1, 2 or 3 wherein said input signal is a digita data stream.

5. A method according to claim 4 wherein said digital data stream is a digita audio signal.

6. A method according to any preceding claim wherein the respective filte windows are applied by multiplying the respective signals by the respective windo functions for each of a fixed number of preselected frequency bands of fixed or known width in accordance with the respective transformation.

7. A method according to any preceding claim wherein said synthesis ste includes deriving the modified signal with values for a limited segment of th frequency band of the transformed signal, or for only selected frequencies thereof

8. A method according to any preceding claim wherein the input and outpu filter windows are symmetrical.

9. A method according to claim 8 wherein said predetermined relationship fo symmetrical input and output window functions h(r) and f(r), is:-

fir) = h(f

(1) h{rf + h(r+M)²

10. A method according to any preceding claim wherein the input signal is a digital signal of Pulse Code Modulation (PCM) format.

11. A method according to any preceding claim wherein said synthesis step is effected by allocating bits to frequency bands according to strength counts which are computed by:

(a) Computing the power in each frequency band;

(b) Finding the greatest power in any band;

(c) Setting a threshold at half that power, and adding 1 to the strength count for each band which exceeds that threshold; and (d) Repeating step (c) for 5 or more times.

12. A method according to any preceding claim wherein said input signal is an audio signal derived from a telephone system, the frequency range of the signal is divided into 64 bands of 62.5 Hz each, and 8 bits are allocated to each band for each 8 millisecond interval which is processed.

13. A method according to any preceding claim wherein said input and outpu filter window functions comprise Dolph-Chebyshev or Kaiser-Bessel windo functions.

14. Apparatus for compressing the required bandwidth of an input signal, comprising: means for subjecting the input signal to an input filter window which is a first function of time h(r); means for transforming the signal to the frequency domain; means for synthesising a modified signal in the frequency domain; means for inverse transforming the modified signal to the time domain to derive an intermediate signal; and means for subjecting said intermediate signal to an output filter window which is a second function of time f(r) to derive a synthesised output signal of compressed bandwidth with respect to said input signal; wherein the functions h(r) and f(r) are different but satisfy a predetermined relationship independent of said synthesis, selected to optimise the reconstruction of said input signal in said synthesised output signal.

15. Apparatus according to claim 14 comprising suitably programmed computer apparatus.

16. A method of deriving a synthesised digital data stream from an input digital data stream comprising: subjecting the input data stream to an input filter window which is a first function of time h(r); transforming the data stream to the frequency domain; synthesising a modified data stream in the frequency domain; inverse transforming the modified data stream to the time domain to derive an intermediate data stream; and subjecting the intermediate data stream to an output filter window which is a second function of time f(r) to derive a synthesised digital data stream of compressed bandwidth with respect to said input data stream; wherein the functions h(r) and f(r) are different but satisfy a predetermined relationship independent of said synthesis, selected to optimise the reconstruction of said input data stream in said synthesised output data stream.