1. Home
  2. An introduction to source-coding
  3. Subband coding
  4. Uniformly-modulated filterbanks

4.2 Uniformly-modulated filterbanks

<< Chapter < Page
  An introduction to source-coding   Page 1 / 1
Chapter >> Page >
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 attentionto orthogonal transformation matrices. Orthogonal matrices had the property that, in the absence ofquantization 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/synthesisstructure 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 inherentto 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 [link] .
    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). 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).
    N -band analysis and synthesis filterbanks.
  • Uniform Modulation: The most conceptually straightforward FB is known as the“uniformly modulated” FB. Uniform modulation means that all branches isolate signal componentsin non-overlapping frequency bands of equal width 2 π / N . We will assume that the i t h branch has its frequency band centered at ω i = 2 i π / N . (See [link] .)
    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. 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.
    Frequency bands for the uniformly-modulated filterbank ( N = 4 ).
  • Analysis FB: The i t h 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 [link] .) The ideal lowpass filter has linear phase and magnitude response thatis unity for ω ∈ ( - π / N , π / N ) and zero elsewhere. (See [link] .)
    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. 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.
    Ideal (dashed) and typical (solid) prototype-filter magnitude responses for the uniformly modulated filterbank.
    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 / 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 [link] . Note that the downsampling operation does not induce aliasingwhen the analysis filter is the ideal lowpass filter described above.
  • Synthesis FB: To reconstruct the input signal 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 - 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 ) and zero elsewhere; the same specifications given for the ideal analysis filter.(See [link] .) As shown in [link] , re-modulation is accomplished by shifting the i t h 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 ) is a potentially delayed (but otherwise perfect) copy of the input signal x ( n ) :
    u ( n ) = x ( n - δ ) for some delay δ .
    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). 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).
    N -band modulated analysis/synthesis filterbanks.
  • Effect of Non-Ideal Filtering: In practice, the analysis and synthesis filters will not have ideallowpass responses, and thus the reconstructed output u ( n ) will not necessarily equal a delayed version of the input x ( n ) . These shortcomings typically result from filter implementationsbased on a finite number of design parameters. (See [link] for a typical lowpass filter magnitude response.) It should be noted that, under certain conditions, it is possibleto design sets of analysis filters { H i ( z ) } and synthesis filters { K i ( 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 thatthe smallest quantization errors swamp out errors caused by non-PR filtering.
  • Polyphase/DFT Implementation: When H ( z ) and K ( z ) are length- M FIR filters, the unique elements in [link] are the N uniform-modulation coefficients { e j 2 π n / N ; n = 0 , ⋯ , N - 1 } and the 2 M the lowpass filter coefficients { h n } and { k n } . It might not be surprising that each half of the uniformly-modulated FBhas an implementation that requires only one N -dimensional DFT and M multiplies to process an N -block of input samples. [link] illustrates one such implementation, where the “polyphase” filters { H ( ℓ ) ( z ) } and { K ( ℓ ) ( z ) } are related to the “prototype” filters H ( z ) and K ( z ) through the impulse response relations:
    h m ( ℓ ) : = h m N + ℓ k m ( ℓ ) : = k m N + ℓ for ℓ = 0 , ⋯ , N - 1 .
    The term “polyphase” comes about because the magnitude responses of well-designed { H ( ℓ ) ( z ) } and { K ( ℓ ) ( z ) } are nearly flat, while the slopes of the phase response of these filters differ bysmall amounts. The equivalence of [link] and [link] will be established in the homework.
    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). 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).
    Polyphase/DFT implementation of N -band uniformly modulated analysis/synthesis filterbanks.
    Recognize that the filter computations in [link] occur on downsampled (i.e., low-rate) data, in contrast to those in [link] . To put it another way, all but one of every N filter outputs in [link] are thrown away by the downsampler, whereas none of the filter outputs in [link] are thrown away. This reduces the number of required filter computations by a factorof N . Additional computational reduction occurs when the DFT is implementedby a fast transform. Below we give a concrete example.

    Computational savings of polyphase/fft implementation)

    Lets take a look at how many multiplications we save by using the polyphase/DFT analysis filterbank in [link] instead of the standard modulated filterbank in [link] . 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 [link] , modulation requires 2 N real multiplies, and filtering of the complex-valued modulator outputs requires 2 × N × M additional real multiplies, for each input point x ( n ) . This gives a total of

    2 N ( M + 1 ) real multiplies per input .

    In the polyphase/FFT structure of [link] , it is more convenient to count the number of multiplies required for each blockof 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 / N , filtering the block requires N × M / N = M real multiplies. Though the standard radix-2 N -dimensional complex-valued FFT uses N 2 log 2 N complex multiplies, a real-valued N -dimensional FFT can be accomplished in N log 2 N real multiplies when N is a power of 2. This gives a total of

    M + N log 2 N real multiplies per N inputs, or M / N + log 2 N real multiplies per input!

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

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, An introduction to source-coding: quantization, dpcm, transform coding, and sub-band coding. OpenStax CNX. Sep 25, 2009 Download for free at http://cnx.org/content/col11121/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'An introduction to source-coding: quantization, dpcm, transform coding, and sub-band coding' conversation and receive update notifications?

Ask