Skip to content Skip to navigation

Connexions

You are here: Home » Content » Uniformly-Modulated Filterbanks

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • NSF Partnership display tagshide tags

    This module is included inLens: NSF Partnership in Signal Processing
    By: Sidney BurrusAs a part of collection: "An Introduction to Source-Coding: Quantization, DPCM, Transform Coding, and Sub-band Coding"

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content display tagshide tags

    This module is included inLens: Connexions Featured Content
    By: ConnexionsAs a part of collection: "An Introduction to Source-Coding: Quantization, DPCM, Transform Coding, and Sub-band Coding"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This module is included inLens: UniqU's lens
    By: UniqU, LLCAs a part of collection: "An Introduction to Source-Coding: Quantization, DPCM, Transform Coding, and Sub-band Coding"

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module is included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Uniformly-Modulated Filterbanks

Module by: Phil Schniter. E-mail the author

Summary: Filterbanks with uniform sub-band bandwidth are described, and the tradeoff between reconstruction error and frequency-selectivity is discussed. The polyphase/DFT filterbank implementaiton is also discussed, along with its computational cost.

  • Perfect Reconstruction Filterbanks: Recall that in our study of transform coding, we restricted our attention to orthogonal transformation matrices. Orthogonal matrices had the property that, in the absence of quantization error, the reconstruction error was zero. For sub-band coding, “perfect reconstruction” (PR) filterbanks (FBs) are analogous to orthogonal matrices. Specifically, a PR-FB is defined as an analysis/synthesis structure which gives zero reconstruction error when synthesis stage is fed exact (unquantized) copies of analysis outputs. Initially we consider the design of ideal sub-band analysis and synthesis FBs and later the design of practical FBs. For the purpose of FB design we ignore the effects of quantization error. Our rational is as follows: the absence of quantization error corresponds to the high bit-rate scenario, in which case we desire that the filtering operations inherent to sub-band coding introduce little or no error of their own. Removing the quantizers from Figure 2 from "Introduction and Motivation", we obtain the analysis/synthesis FBs in Figure 1.
    Figure 1: N-band analysis and synthesis filterbanks.
    This is a large, complex flowchart which will be described from left to right, as this is the flow of the diagram. The diagram begins with the expression x(n), and from this expression is a line that splits into a series of arrows each pointing to the right at boxes containing the expressions H_0(z), H_1(z), and so on to a final box H_(N-1)(z). From the ends of each of these boxes are more arrows pointing to the right, this time each at an identical circle containing a down arrow and the variable N. The arrows pointing at these circles are labeled from top to bottom x_0(n), x_1(n), to x_(N-1)(n). To the right of these circles again are a series of arrows that point to the right. There is then a gap in the diagram, followed by a series of identical arrows to those preceding it. These arrows each point at circles containing an up arrow and the variable N. To the right of these circles are more arrows pointing at boxes containing the labels K_0(z), K_1(z), and so on to a final box containing K_(N-1)(z). The arrows pointing at these boxes are labeled from top to bottom y_0(n), y_1(n), to y_(N-1)(n). Each of these boxes point with arrows to the right at a single circle containing a plus sign. The arrows are labeled from top to bottom u_0(n), u_1(n), to u_(N-1)(n). From the plus sign is a final arrow pointing to the right, labeled u(n).
  • Uniform Modulation: The most conceptually straightforward FB is known as the “uniformly modulated” FB. Uniform modulation means that all branches isolate signal components in non-overlapping frequency bands of equal width 2π/N2π/N. We will assume that the ithith branch has its frequency band centered at ωi=2iπ/Nωi=2iπ/N. (See Figure 2.)
    Figure 2: Frequency bands for the uniformly-modulated filterbank (N=4N=4).
    This figure is a graph with horizontal axis ω, plotting a series of rectangles. Above the figure is a large equation that reads ω_i = 2πi/N. The horizontal values on the axis range from 0 to 2π. There are two arrows pointing up from these two furthest points on the horizontal axis. The arrow pointing directly up from the horizontal value 0 is labeled ω_0. Along the axis are four identical, connected rectangles that lie on the horizontal axis from approximately -π/4 to 7π/4, each with a width of π/2. There are dashed vertical lines crossing the midpoint of the base of these rectangles and extending through the height of the rectangle. These dashed lines continue in aligned succession with ω_0, and are subsequently labeled ω_1, ω_2, and ω_3. Above these rectangles is a horizontal arrow pointing in both directions, labeled 2π/N.
  • Analysis FB: The ithith frequency range may be isolated by modulating the input spectrum down by ωi and lowpass filtering the result. (See the first two stages of the analysis bank in Figure 4.) The ideal lowpass filter has linear phase and magnitude response that is unity for ω∈(-π/N,π/N)ω∈(-π/N,π/N) and zero elsewhere. (See Figure 3.)
    Figure 3: Ideal (dashed) and typical (solid) prototype-filter magnitude responses for the uniformly modulated filterbank.
    This figure is a graph with horizontal axis ω, ranging in value from -π to π, and vertical axis |H(π)|. There is one dashed rectangle with its base sitting on the horizontal axis, and with its width measured from horizontal position -π/N to π/N. The height is not measured or labeled. There is also a solid curve that, in a calmly wavelike distortion follows the horizontal axis to the bottom-left vertex of the rectangle. The curve then sharply increases to follow the boundary of the dashed rectangle, until at the bottom-right vertex it flattens to continue following the horizontal axis to the edge of the graph.
    With ideal lowpass filtering, the resulting signals have (double-sided) bandwidths that are N times smaller than the sampling rate. Nyquist's sampling theorem (see Oppenheim & Schafer) says that it is possible to sample signals with this bandwidth at 1/N1/N times the filter output rate without loss of information. This sample rate change can implemented via downsampling-by-N, resulting in the analysis FB of Figure 4. Note that the downsampling operation does not induce aliasing when the analysis filter is the ideal lowpass filter described above.
  • Synthesis FB: To reconstruct the input signal x(n)x(n), the synthesis FB must restore the downsampled signals to their original sampling rate, re-modulate them to their original spectral locations, and combine them. Upsampling is the first stage of sampling-rate restoration. Recall from Equation 18 from "Fundamentals of Multirate Signal Processing" (and Figure 8 from "Fundamentals of Multirate Signal Processing") that a downsampler-upsampler cascade creates N-1N-1 additional uniformly-spaced spectral copies of the original baseband spectrum. Thus, to remove the unwanted spectral images, an “anti-imaging” lowpass filter is applied to each upsampler's output. Ideally, this lowpass filter is linear phase with magnitude response that is unity for ω∈(-π/N,π/N)ω∈(-π/N,π/N) and zero elsewhere; the same specifications given for the ideal analysis filter. (See Figure 3.) As shown in Figure 4, re-modulation is accomplished by shifting the ithith branch up by ωi. When the analysis and synthesis filters share a common phase response, the re-modulator outputs can be combined coherently by a simple summation. Under all of these ideal conditions, the output signal u(n)u(n) is a potentially delayed (but otherwise perfect) copy of the input signal x(n)x(n):
    u(n)=x(n-δ)forsomedelayδ.u(n)=x(n-δ)forsomedelayδ.
    (1)
    Figure 4: N-band modulated analysis/synthesis filterbanks.
    This is a large, complex flowchart which will be described from left to right, following the flow of the diagram. The flowchart begins with the expression x(n), and from this expression is a line that splits into a series of arrows each pointing to the right at a series of circles containing an x. Below each circle is an arrow pointing up, labeled e^(-jω_0n). To the right of these circles are arrows that each point to the right at a series of identical rectangles labeled H(z). To the right of these rectangles are more arrows pointing to the right at a series of circles containing a down arrow and the variable N. To the right of these circles is another series of arrows pointing to the right. At this point in the flow chart, there is a gap. To the right of the gap is another series of identical arrows as those on the left side of the gap. These arrows each point at circles that contain an up arrow and the variable N. To the right of these circles are more arrows that point at identical boxes labeled K(z). To the right of these boxes are more arrows that point at a series of circles containing an x. Below each of these circles is an arrow pointing up, labeled e^(-jω_0n). To the right of these circles are arrows that all point at a single final object, a circle containing a plus sign. To the right of this object is one final arrow pointing to the right, labeled u(n).
  • Effect of Non-Ideal Filtering: In practice, the analysis and synthesis filters will not have ideal lowpass responses, and thus the reconstructed output u(n)u(n) will not necessarily equal a delayed version of the input x(n)x(n). These shortcomings typically result from filter implementations based on a finite number of design parameters. (See Figure 3 for a typical lowpass filter magnitude response.) It should be noted that, under certain conditions, it is possible to design sets of analysis filters {Hi(z)}{Hi(z)} and synthesis filters {Ki(z)}{Ki(z)} with finite parameterizations which give the “perfect reconstruction” (PR) property (see Vaidyanathan). Though such filters guarantee PR, they do not act as ideal bandpass filters and thus do not accomplish perfect frequency analysis. (Consider the length-N DFT and DCT filter responses: by the orthogonal matrix argument, these are perfectly reconstructing, but from Figure 4 from "Introduction and Motivation" and Figure 5 from "Introduction and Motivation", they are far from perfect bandpass filters!) Due to their limited frequency-selectivity, none of the currently-known PR filterbanks are appropriate for high-quality audio applications. As a result, we focus on the design of filterbanks with
    1. near-perfect reconstruction and
    2. good frequency selectivity.
    As we will see, it is possible to design practical filters with excellent frequency selectivity and responses so close to PR that the smallest quantization errors swamp out errors caused by non-PR filtering.
  • Polyphase/DFT Implementation: When H(z)H(z) and K(z)K(z) are length-M FIR filters, the unique elements in Figure 4 are the N uniform-modulation coefficients {ej2πn/N;n=0,⋯,N-1}{ej2πn/N;n=0,⋯,N-1} and the 2M2M the lowpass filter coefficients {hn}{hn} and {kn}{kn}. It might not be surprising that each half of the uniformly-modulated FB has an implementation that requires only one N-dimensional DFT and M multiplies to process an N-block of input samples. Figure 5 illustrates one such implementation, where the “polyphase” filters {H(ℓ)(z)}{H(ℓ)(z)} and {K(ℓ)(z)}{K(ℓ)(z)} are related to the “prototype” filters H(z)H(z) and K(z)K(z) through the impulse response relations:
    hm(ℓ):=hmN+ℓkm(ℓ):=kmN+ℓforℓ=0,⋯,N-1.hm(ℓ):=hmN+ℓkm(ℓ):=kmN+ℓforℓ=0,⋯,N-1.
    (2)
    The term “polyphase” comes about because the magnitude responses of well-designed {H(ℓ)(z)}{H(ℓ)(z)} and {K(ℓ)(z)}{K(ℓ)(z)} are nearly flat, while the slopes of the phase response of these filters differ by small amounts. The equivalence of Figure 4 and Figure 5 will be established in the homework.
    Figure 5: Polyphase/DFT implementation of N-band uniformly modulated analysis/synthesis filterbanks.
    This is a large, complex flow chart that mostly moves to the right, so it will be read from left to right, starting at the top-right. The flowchart begins with the expression x(n). From this expression is one arrow pointing to the right at a circle containing a down arrow and the variable N, and another arrow connected to the initial expression pointing down at a box labeled z^1. This establishes a pattern, where below the z^-1 box is an arrow that points to the right at a down arrow N-cirlce, and a connected arrow that continues the pattern to another z-box. To the right of each of these down-arrow N-circles is another arrow pointing to the right at boxes that are labeled from top to bottom, H^(0)(z), H^(1)(z), and so on to a final box labeled H^(N-1)(z). Each of these boxes point to the right with small arrows at a single large box labeled Conjugate DFT: √N W*_N. To the right of this large box are more small arrows in alignment with the preceding series. These arrows point at a gap, and to the right of the gap are more arrows that continue the flowchart. The arrows point at another large box with identical labeling. From this box is another series of arrows, each pointing at boxes labeled from top to bottom K^(0)(z), K^(1)(z), and so on to a final box K^(N-1)(z). To the right of these boxes are arrows pointing to the right at circles labeled with an up-arrow and the variable N. These circles are all connected to a similar pattern as the beginning of the flowchart, with boxes containing the label z^-1. The movement in this pattern, however, is upward at a final expression in the top-right, u(n).
    Recognize that the filter computations in Figure 5 occur on downsampled (i.e., low-rate) data, in contrast to those in Figure 4. To put it another way, all but one of every N filter outputs in Figure 4 are thrown away by the downsampler, whereas none of the filter outputs in Figure 5 are thrown away. This reduces the number of required filter computations by a factor of N. Additional computational reduction occurs when the DFT is implemented by a fast transform. Below we give a concrete example.

    Example 1: Computational Savings of Polyphase/FFT Implementation)

    Lets take a look at how many multiplications we save by using the polyphase/DFT analysis filterbank in Figure 5 instead of the standard modulated filterbank in Figure 4. Here we assume that N is a power of 2 (see Sorensen, Jones, Heideman & Burrus TASSP 87), so that the DFT can be implemented with a radix-2 FFT. With the standard structure in Figure 4, modulation requires 2N2N real multiplies, and filtering of the complex-valued modulator outputs requires 2×N×M2×N×M additional real multiplies, for each input point x(n)x(n). This gives a total of

    2N(M+1)realmultipliesperinput.2N(M+1)realmultipliesperinput.
    (3)

    In the polyphase/FFT structure of Figure 5, it is more convenient to count the number of multiplies required for each block of N inputs since each new N-block produces one new sample at every filter input and one new N-vector at the DFT input. Since the polyphase filters are each length-M/NM/N, filtering the block requires N×M/N=MN×M/N=M real multiplies. Though the standard radix-2 N-dimensional complex-valued FFT uses N2log2NN2log2N complex multiplies, a real-valued N-dimensional FFT can be accomplished in Nlog2NNlog2N real multiplies when N is a power of 2. This gives a total of

    M+Nlog2NrealmultipliesperNinputs,orM/N+log2Nrealmultipliesperinput!M+Nlog2NrealmultipliesperNinputs,orM/N+log2Nrealmultipliesperinput!
    (4)

    Say we have N=32N=32 frequency bands and the prototype filter is length M=512M=512 (which turn out to be the values used in the MPEG sub-band filter). Then using the formulas above, the standard implementation requires 3283232832 multiplies per input, while the polyphase/DFT implementation requires only 2121!

Content actions

Download module as:

PDF | More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks