Ch. 14 Subband Coding Introduction & Multirate Background

Ch. 14 Subband Coding

Introduction &

Multirate Background

Introduction

Given signal x[n] to compress…

Idea

: Split signal into M signals x

[n], x

[n], … , x

[n]

such that each signal can be more easily/effectively compressed.

Goal

: signals x

[n], x

[n], … , x

[n] should be made such that

– Each x

[n] is uncorrelated…

• then using SQ on each is a viable (though still suboptimal) approach

–Some x

[n] have smaller dynamic range

• Then can use fewer bits for a given desired distortion

– Should be a clear way to exploit psychological effects (for audio and

video) or other effects that imply some x

[n] are more important

Illustration of Subbands

DTFT

of x[n]

(Ω)

Each x

[n] is called a

subband signal

[-π,0) is not shown

(Recall Symmetry)

Motivational Form (Not Practical)

Compress

& Code

…

x[n]

[n]

Compress

& Code

bit

stream

bit

stream

De-Code

…

bit stream

bit

stream

Data Link

[n]

[]

De-Code

Problems w/ This Form

• Output of each filter is at

input sampling rate

–Overallsample rate after

subband filters is M×F

• Can’t build Ideal BPFs

– Can’t reconstruct by just

adding together

• Inefficient to implement M

separate filters

Ideal

BPFs

…

Fixing Sample Rate Problem: Multirate

Take a look at x

[n]

Ωπ-π

π/M

-π/M

(Ω)

This signal is oversampled

by a factor of M

(If it were not oversampled it would fill the entire -π to π)

To sample it slower by a factor of M… just throw away M-1 samples out of

every M samples (called “Decimation by M

”)…

[n]

x[n]

[0] x

[1] x

[2] x

[3] x

[4] x

[5] x

[6] x

[7] x

[8]

M = 3

[n]

x[n]

↓M

[0] x

[3] x

[6]

M = 3

Now… we need someway at the decoder side to get back up to the original

sampling rate (called “Expansion by M

”)…

[n]

x[n]

↓M

M = 3

Code De-Code

Link

↑M

ˆˆˆ

[0] [3] [6]xxx"

ˆˆˆ

[0] 0 0 [3] 0 0 [6]xxx"

Has correct # samples/sec…

But can’t have those zeros!!!

A filter can “smooth out” the jumps due to the zeros (called “Interpolation

”)….

↑M

ˆˆˆ

[0] [3] [6]xxx"

ˆˆˆ

[0] 0 0 [3] 0 0 [6]xxx"

[n]

ˆˆˆˆˆˆˆ

[0][1][2][3][4][5][6]xxxxxxx"

Ideally:

Subband Coding System

We can do a similar thing for all the other channels… and the result is:

Roughly…What should the analysis filters look like?

Gaps will

result in

loss of info

Note: These are not true achievable shapes of filter frequency responses

Subband Coding System Details

Encoding/Decoding Goals:

1. Choose methods matched to resulting channel characteristics

2. Allocate bit budget across the channels

Filter Design Goal: If we remove encode/decode… then we want our filters

to be designed so that output = input… this is called “Perfect Reconstruction

”.

Analysis Filters

must also provide frequency decomposition into

essentially non-overlapping subbands… should give “easy to code” signals

Synthesis Filters

are chosen to give the desired perfect reconstruction.

Their design will depend on the design of the analysis filters.

Multi-Rate Goal: properly decrease and then restore the sampling rate

Decimation

reduces each channel’s sample rate to keep the total analysis

filter bank’s output sample rate equal to the input sample rate

Interpolation

returns each channel to original rate before reconstruction

To understand how filter banks work we need to understand:

• Effect of decimation on signal spectrum

• Effect of expansion on signal spectrum

• How to choose Analysis & Synthesis filters to achieve perfect

reconstruction (PR)

Decimation (Down Sampling)

Consider

H(Ω)

x[n]

y[n]

(sampled @ F

)

First let H(Ω) be an ideal

LPF w/ cut-off frequency Ω = π/2… “half-band filter”

π/2–π

H(Ω)

–π/2 π

Ideal Filter

for Illustration

π–π

X(Ω)

()

π–π π/2-π/2

Y(Ω)

Now… imagine what continuous-time signal would give y[n] if it were

sampled at F

π–π π/2-π/2

Y(Ω)

/2F

/4-F

So… if we sampled this CT signal at

half the original rate (@ F

/2)

then we would get this:

π-π

(Ω)

/2-F

π–π

X(Ω)

↓2

()

–π

π/2–π

H(Ω)

–π/2 π

Ideal Filter

for Illustration

So… just looking at things in the DT domain with the sampling rate change

happening because of down-sampling… we should see the SAME thing:

In general… if the filter passes only in the range Ω∈[-π/M, π/M] we can

downsample by M

Now… all of this was based on “intuition” and for an Ideal

LPF… We need to

do a detailed analysis….

π–π

Y(Ω)

W(Ω)

x[n] y[n] w[n]

[] [ ] forwn yMn n Z=∈

M-Fold Decimation

[0] [0]

[1] [3]

[2] [6]

For M=3

Decimation – Time-Domain Math View

↓M

y[n]

w[n]

Math Analysis of Decimation

To really understand what is happening we need to look in the

frequency domain…

Notation:

)(

)()(

)}({)()}({

MMM

zXzXzZx

↓↓↓

• Similar for DTFT

• Similar for Expansion

Q: What is X

(↓M)

(z) in terms of X(z)???

What do we expect????!!!!

Lower F

causes Spectral Replicas to Move to Lower Frequencies

Should look exactly like

sampling at a lower F

Thus… increased aliasing is possible!!!

To answer this we need to define a useful function (“comb” function):

∑∑

−

∞

−∞=

==−=

]mod[][][

MnkMnnc

δδ

Call this ()…

This is like a DT

Fourier Series and is

easily verified!

036-3-6

(m)

M-Fold Decimation – Frequency-Domain



][][

)(

nMcnMx

nMxnx

↓

Now… use the comb function to write decimation:

Doesn’t Really Do

Anything Here…

But Later it Will!!

Action of C

[n]

∑∑

∞

−∞=

−

↓

⎥

⎦

⎤

⎢

⎣

⎡

nxzX

)(

][)(

Now… take Z-Transform, using this form:

M-Fold Decimation – Frequency-Domain (cont.)

Now… take Z-Transform, using this form:

01 2

()

[0] [ ] [2 ]

() [][]

xzxMz xMz

Xz xnMcnMz

−

∞

−

↓

=−∞

++ + +

∑



[0] 0 0 [ ] 0

[] []

xz xMz

xnc nz

−

∞

−

=−∞

+++++ ++

∑

"" "





()

)(

][

][)(

)(

zWX

zWnx

nxzX

−

∞

−∞=

−

∞

−∞=

−

↓

∑

∑∑

⎥

⎦

⎤

⎢

⎣

⎡

⎥

⎦

⎤

⎢

⎣

⎡

Now… just manipulate:

)(

zWX

−

↓

∑

ZT of Decimated Signal is…

M-Fold Decimation – Frequency-Domain (cont.)

Now to see a little better what this says… convert ZT to DTFT.

MjMj

ezez

//1

θθ

=⇒=

1. Axis-Scale X

(θ) to get X

(θ/M) – a stretch

2. Then shift by 2πm to get new replicas

Î Decimation Adds Spectral Replicas of Scaled DTFT

∑

−

↓

⎟

⎠

⎞

⎜

⎝

⎛

−

)(

πθ

Mmjm

−−

=Also, by definition:

DTFT of Decimated Signal is…

Stretches

Spectrum

M-Fold Decimation – Frequency-Domain (cont.)

Recall: DTFT is the ZT evaluated on the unit circle:

Then we get….

M = 3

0 π 2π 3π 4π 5π 6π 7π 8π 9π-π-2π-3π-4π-5π-6π-7π-8π-9π

±π/3

(θ)

Original

0 π 2π 3π 4π 5π 6π 7π 8π 9π-π-2π-3π-4π-5π-6π-7π-8π-9π

(θ/3)

m = 0

0 π 2π 3π 4π 5π 6π 7π 8π 9π-π-2π-3π-4π-5π-6π-7π-8π-9π

((θ-2π)/3)

m = 1

0 π 2π 3π 4π 5π 6π 7π 8π 9π-π-2π-3π-4π-5π-6π-7π-8π-9π

((θ-4π)/3)

m = 2

Example: DTFT for M-Fold Decimation

M = 3

π 2π 3π 4π 5π 6π 7π 8π 9π-π-2π-3π-4π-5π-6π-7π-8π-9π

(θ/3)

m = 0

0 π 2π 3π 4π 5π 6π 7π 8π 9π-π-2π-3π-4π-5π-6π-7π-8π-9π

((θ-2π)/3)

m = 1

π 2π 3π 4π 5π 6π 7π 8π 9π-π-2π-3π-4π-5π-6π-7π-8π-9π

((θ-4π)/3)

m = 2

)(

↓

0 π 2π 3π 4π 5π 6π 7π 8π 9π-π-2π-3π-4π-5π-6π-7π-8π-9π

M × DTFT of

Decimated Signal

No Aliasing!!!

Example: Continued

1. The M-decimated signal will have no aliasing… only if

the signal being decimated has:

MX /for 0)(

πθθ

This makes complete sense from an

“ordinary” sampling theorem view point!!!

2. After M-decimating an M

-band signal, the spectrum of

the decimated signal will fill the [-π, π] band.

Such a signal is called

an “M

-Band Signal”

Example: Insights

Although decimation changes the digital frequency of the

signal, the corresponding “physical” frequency is not

changed… as the following example shows:

↓3

x[n]

=60 MSPS

(↓3)

[n]

= 60/3

= 20 MSPS

π-π

(↓3)

(θ)

−

-10

MHz

π-π

(θ)

−

-10

MHz

Signal Still Occupies Same Physical Frequency

Note

Expansion

Also Has

No Effect

on Physical

Frequency

Effect on “Physical” Frequency

Q: What is X

(↑L)

(z) in terms of X(z)???

What do we expect????!!!!

Certainly NOT the same as really sampling at a higher rate

because of the inserted zeros!!!

Frequency Domain analysis answers this!!!

)()(

)(

Lzz

zXzX =

↑

ZT of Expanded Signal is…

L-Fold Expansion – Frequency-Domain

1 zeros 1 zeros

[0] 0 0 [1] 0 0 [2]

xz xz xz

−−

=++ ++++ ++++"" "

 

() ()

() []

zxnz

∞

−

↑↑

=−∞

∑

[] ( )

Ln z L

xnz X z

∞

−

=−∞

∑

Now to see a little better what this says… convert ZT to DTFT.

Recall: DTFT is the ZT evaluated on the unit circle:

θθ

jLLj

ezez =⇒=

DTFT of Decimated Signal is…

)()(

)(

θθ

LXX

↑

Scrunches

Spectrum

L-Fold Expansion – Frequency-Domain (cont.)

0 π 2π 3π 9π-π-2π-3π

)(

…

L = 3

)(

π 2π 3π-π-2π-3π

…

π/3

-π/3

Expansion Causes Images

to Appear in the [-π,π] Range

…

0 π 2π 3π-π-2π-3π

…

π/3

-π/3

Here’s what we’d have if we REALLY sampled

3 times as fast… No Images

!!!

Example: DTFT for L-Fold Expansion

Effect of Non-Ideal Filters

π–π

X(Ω)

↓2

()

π/2–π

H(Ω)

–π/2 π

x[n] y[n] w[n]

Y(Ω)

π–π 2π–2π

Y((Ω-2π)/2)

Y(Ω/2)

π–π 2π–2π 4π-4π

–3π 3π

π–π 2π–2π 4π-4π

–3π 3π

Aliasing

W(Ω)

π–π 2π–2π 4π-4π

–3π 3π

Aliasing

Summary

So… in practice we can change the rate of a signal… but there will always be some

error due to non-ideal filters (both in the case of downsampling and in the case of

upsampling).

Generally, we can design the filters to make these errors negligible …

BUT

… such filters are long FIR filters and that can lead to efficiency issues

Note

: Similar analyses can be done for

•HPF

followed by Decimation

• Interpolation followed by HPF

↓M

()H Ω

x[n] y[n] w[n]

↑M

()K

w[n] v[n] u[n]

()

−

Ω−

⎛⎞

Ω=

⎜⎟

⎝⎠

∑

() ()()YXHΩ= Ω Ω

w/ H(Ω) having a passband

width of π/M

() ()( )UKWM

=Ω Ω

w/ K(Ω) having a

passband width of π/M

End