Paper V: Convolution as a packet transfer matrix

E4 Convolution as a packet transfer matrix

On this page · Permalink · Source line 1902

Let \(h\in\ell^1({\mathbb Z}^d)\) and \(x\in\ell^p({\mathbb Z}^d)\), with \(1\leq p\leq\infty\), and define

\[ (Hx)(n) =(h*x)(n) =\sum_{q\in{\mathbb Z}^d}h(q)x(n-q). \]

Young's inequality gives

\[ \|Hx\|_p\leq\|h\|_1\|x\|_p \]

for every \(1\leq p\leq\infty\).

Permalink · Source line 1904

Definition E4.1: Packet transfer kernel

For output residue \(r\in R\) and input residue \(s\in R\), define a kernel on \(L\) by

\[ h_{rs}(m)=h(r-s+m), \qquad m\in L. \]

Permalink · Source line 1916 · Claim record · Lean coverage · Code · Worked examples

Theorem E4.2: Exact convolution transfer law

Let \(y=h*x\). Then

\[ y_r(\ell) = \sum_{s\in R}\sum_{m\in L}h_{rs}(m)x_s(\ell-m). \]

Equivalently,

\[ {\mathcal A}_LH{\mathcal A}_L^{-1} = (H_{rs})_{r,s\in R}, \]

where \(H_{rs}\) is convolution on \(L\) by \(h_{rs}\).

Read proof · Read statement and proof side by side · Permalink · Source line 1925 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E4.2

Evaluate the output at \(r+\ell\). Write every input address as \(s+\ell'\). The convolution offset is

\[ (r+\ell)-(s+\ell') =(r-s)+(\ell-\ell'). \]

Setting \(m=\ell-\ell'\) gives the formula.

Back to statement · Read statement and proof side by side · Permalink · Source line 1941 · Claim record · Lean coverage · Code · Worked examples

Proposition E4.3: Transfer norm control

For every output residue \(r\),

\[ \sum_{s\in R}\|h_{rs}\|_{\ell^1(L)} = \|h\|_{\ell^1({\mathbb Z}^d)}. \]

The packet transfer matrix acts on the polyphase direct sum with norm at most \(\|h\|_1\) on every \(\ell^p\) space.

Read proof · Read statement and proof side by side · Permalink · Source line 1950 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition E4.3

For fixed \(r\), every \(q\in{\mathbb Z}^d\) has a unique representation \(q=r-s+m\) with \(s\in R\) and \(m\in L\). This proves the equality of the absolute sums. The operator norm bound also follows by conjugating Young's inequality through the isometric analysis map.

Back to statement · Read statement and proof side by side · Permalink · Source line 1960 · Claim record · Lean coverage · Code · Worked examples

Proposition E4.4: Composition of transfer matrices

If \(G\) and \(H\) are convolution operators with packet matrices \((G_{rs})\) and \((H_{rs})\), then the packet matrix of \(GH\) is

\[ (GH)_{rt} = \sum_{s\in R}G_{rs}H_{st}. \]

In one dimensional transform notation, the corresponding matrix symbols multiply pointwise.

Read proof · Read statement and proof side by side · Permalink · Source line 1964 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition E4.4

Conjugation by \({\mathcal A}_L\) preserves composition:

\[ {\mathcal A}_LGH{\mathcal A}_L^{-1} = ({\mathcal A}_LG{\mathcal A}_L^{-1})({\mathcal A}_LH{\mathcal A}_L^{-1}). \]

Reading the \((r,t)\) block gives the formula.

Back to statement · Read statement and proof side by side · Permalink · Source line 1974 · Claim record · Lean coverage · Code · Worked examples

E4.1 The one dimensional symbol

On this page · Permalink · Source line 1984

For \(L=N{\mathbb Z}\) with \(N\geq1\), first take \(|z|=1\). The assumption \(h\in\ell^1({\mathbb Z})\) makes the following symbol series absolutely convergent. Define

\[ H_{ks}(z)=\sum_{m\in{\mathbb Z}}h(Nm+k-s)z^{-m}. \]

For \(x\in\ell^1({\mathbb Z})\), the channel transforms converge absolutely on the unit circle and satisfy

\[ {\boldsymbol{Y}}(z)={\boldsymbol{H}}_N(z){\boldsymbol{X}}(z). \]

For \(x\in\ell^2({\mathbb Z})\), the same identity holds almost everywhere in the \(L^2\) Fourier sense. For finite impulse-response kernels it also holds at nonzero \(z\) wherever the input channel transforms are weighted absolutely summable. This is the classical polyphase matrix. It is the exact block matrix of the original convolution operator.

Permalink · Source line 1986

Corollary E4.5: Finite impulse response closure

If \(h\) has finite support, every packet kernel \(h_{ks}\) has finite support. Matrix multiplication of polyphase symbols agrees with composition of the original finite impulse response operators.

Read proof · Read statement and proof side by side · Permalink · Source line 1996 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary E4.5

Finite support is preserved by taking residue subsequences. The composition statement is Proposition E4.4.

Back to statement · Read statement and proof side by side · Permalink · Source line 2000 · Claim record · Lean coverage · Code · Worked examples

Example E4.6: A four phase finite impulse response operator

Let

\[ h(0)=1, \quad h(1)=2, \quad h(2)=3, \quad h(3)=4, \quad h(4)=5, \]

with all other taps zero. For four residue channels, the transfer symbol is

\[ {\boldsymbol{H}}_4(z) = \begin{pmatrix} 1+5z^{-1}&4z^{-1}&3z^{-1}&2z^{-1}\\ 2&1+5z^{-1}&4z^{-1}&3z^{-1}\\ 3&2&1+5z^{-1}&4z^{-1}\\ 4&3&2&1+5z^{-1} \end{pmatrix}. \]

The delay term records the tap that crosses a coarse cell boundary. No approximation is introduced by the matrix representation.

Permalink · Source line 2004

Absolute FIR tap weights in the sixteen transfer blocks of a four-phase operator. — Absolute tap weight in the transfer blocks of the four phase operator in Example E4.6.

Read and explore

Proofs and implementation

About this work

Other resources