Method for reducing a computational complexity in non-linear filter arrangements as well as corresponding filter arrangements
View Patent ↗A method for creating a form of a non-linear filter suitable for reducing a computational complexity is proposed. The filter is resolved into polyphase components in such a way that the polyphase components can be interchanged with a conversion of the sampling rate of a signal to be sent to the filter or of a signal to be emitted by the filter. Corresponding filters and filter arrangements are also proposed. In this way, a computational complexity for calculating the signal to be emitted by the filter can be significantly simplified. The invention can be used in echo compensation.
1. A method of implementing a non-linear filter arrangement in an echo canceller in a communication system, the method comprising:
providing, with a sampling rate converter, a conversion of a sampling rate of a signal associated with the echo canceller;
forming, with a processor, a non-linear filter connected in series with the sampling rate converter in a first defined order;
resolving, with the processor, the non-linear filter into a summation of polyphase components; and
reducing the computational complexity of the non-liner filter by:
removing polyphase components that do not contribute to the output of the non-linear filter arrangement;
modifying the polyphase components; and
interchanging the modified polyphase components with the sampling rate converter so that the modified polyphase components and the sampling rate converter are in a second defined order which is the reverse of the first defined order; and
implementing the non-linear filter arrangement with the modified polyphase components and the sampling rate converter in the second defined order in the echo canceller.
2. The method of claim 1 , wherein the signal associated with the echo canceller is a signal fed to the filter.
3. The method of claim 1 , wherein the signal associated with the echo canceller is a signal emitted by the filter.
4. The method of claim 1 , wherein the filter is a non-linear Volterra filter.
5. The method of claim 4 , wherein each homogeneous component of n th order of the Volterra filter is resolved according to
Hn
(
z
1
,
z
2
,
…
,
zn
)
=
∑
i
1
L
-
1
∑
i
2
L
-
1
…
∑
in
L
-
1
Hn
i
1
,
i
2
,
…
,
in
(
z
1
L
,
z
2
L
,
…
,
zn
L
)
·
z
1
-
i
1
z
2
-
i
2
…
zn
-
in
wherein Hn(z 1 ,z 2 , . . . ,zn) is the z-transform of the respective homogeneous component of n th order, L is a factor by which the conversion of the sampling rate is carried out, Hn i1,i2, . . . ,in (z 1 L , . . . zn L ) are the polyphase components, and are delay components.
6. The method of claim 4 , wherein the polyphase component of each homogeneous component of n th order of the Volterra filter are calculated according to
Hn
i
1
,
i
2
,
…
,
in
(
z
1
L
,
z
2
L
,
…
,
zn
L
)
=
∑
m
1
=
0
N
∑
m
2
=
0
N
…
∑
mn
=
0
N
hn
[
i
1
+
Lm
1
,
i
2
+
Lm
2
,
…
,
in
+
Lmn
]
z
1
-
Lm
1
z
2
-
Lm
2
…
zn
-
Lmn
in which Hn i1,i2, . . . , in (z 1 L ,z 2 L , . . . ,zn L ) are the polyphase components of n th order, wherein i 1 ,i 2 , . . . ,in are indices that run from 0 to L-1, where L is a factor by which the sampling rate is converted in the conversion of the sampling rate, wherein hn is a homogeneous Volterra core of n th order of the Volterra filter in time representation, and where N is a memory length of the core hn.
7. The method of claim 4 , wherein the polyphase components of each homogeneous component of n th order of the Volterra filter are calculated according to
Hn
i
1
,
i
2
,
…
,
in
(
z
1
L
,
z
2
L
,
…
,
zn
L
)
=
∑
m
1
=
0
N
∑
m
2
=
0
N
…
∑
mn
=
0
N
hn
[
i
1
+
Lm
1
,
i
2
+
Lm
2
,
…
,
in
+
Lmn
]
z
1
-
Lm
1
z
2
-
Lm
2
…
zn
-
Lmn
wherein Hn i1,i2, . . . ,in (z 1 L ,z 2 L , . . . ,zn L ) are the polyphase components of n th order, wherein i 1 ,i 2 , . . . ,in are indices that run from 0 to L−1, where L is a factor by which the sampling rate is converted in the conversion of the sampling rate, wherein hn is a homogeneous Volterra core of n th order of the Volterra filter in time representation, wherein hn exists in triangular form, and wherein N is a memory length of the core hn.
8. A method of implementing a filter arrangement in an echo canceller in a communication system, comprising:
increasing a sampling rate of a signal fed to a sampling rate converter by a specified factor;
forming, with a processor, a non-linear filter connected downstream of the sampling rate converter;
resolving, with the processor, the non-linear filter into a summation of polyphase components;
reducing the computational complexity of the non-liner filter by:
removing polyphase components that do not contribute to the output of the filter arrangement;
modifying the polyphase components; and
interchanging the modified polyphase components with said sampling rate converter so that the modified polyphase components are upstream of the sampling rate converter; and
implementing the filter arrangement with the modified polyphase components upstream of the sampling rate converter in the echo canceller.
9. The method of claim 8 , further including introducing sampling values with value zero into a signal fed to the sampling rate converter for the conversion of the sampling rate, and calculating the polyphase components according to
Hn
(
z
1
,
z
2
,
…
,
zn
)
=
∑
i
1
L
-
1
∑
i
2
L
-
1
…
∑
in
L
-
1
Hn
i
1
,
i
2
,
…
,
in
(
z
1
L
,
z
2
L
,
…
,
zn
L
)
·
z
1
-
i
1
z
2
-
i
2
…
zn
-
in
wherein Hn(z 1 ,z 2 , . . . ,zn) is the z-transform of the respective homogeneous component of n th order, L is a factor by which the conversion of the sampling rate is carried out, Hn i1,i2, . . . ,in (z 1 L ,z 2 L , . . . zn L ) are the polyphase components, and z 1 −i1 ,z 2 −i2 . . . zn −in are delay components, and wherein those polyphase components in which the indices i 1 ,z 2 , . . . ,in are not all identical are deleted.
10. The method according to claim 8 , wherein the filter is a non-linear Volterra filter, wherein each homogeneous component of n th order of the Volterra filter (2, 120) is resolved according to
Hn
(
z
1
,
z
2
,
…
,
zn
)
=
∑
i
1
L
-
1
∑
i
2
L
-
1
…
∑
in
L
-
1
Hn
i
1
,
i
2
,
…
,
in
(
z
1
L
,
z
2
L
,
…
,
zn
L
)
·
z
1
-
i
1
z
2
-
i
2
…
zn
-
in
wherein Hn(z 1 ,z 2 , . . . ,zn) is the z-transform of the respective homogeneous component of n th order, L is a factor by which the conversion of the sampling rate is carried out, Hn i1, i2, . . . ,in (z 1 L ,z 2 L , . . . zn L ) are the polyphase components z 1 −i1 ,z 2 −i2 . . . zn −in are delay components, wherein an identity is used for the interchange of the polyphase components with the sampling rate converters according to which a polyphase component of the form Hn i1,i2, . . . ,in (z 1 ,z 2 , . . . ,zn) connected downstream of the sampling rate converter is identical to a polyphase component with the z-transform Hn i1,i2, . . . , in (z 1 ,z 2 , . . . ,zn) with sampling rate converters connected downstream.
11. The method of claim 10 , wherein for i 1 =i 2 = . . . =in the factors z 1 −i1 , z 2 −2 , . . . , zn −in are in each case condensed to a separate delay element z −i1 .
12. A method of implementing a filter arrangement in an echo canceller in a communication system, comprising:
reducing a sampling rate of a signal to be fed to a sampling rate converter connected downstream of a non-linear filter;
forming, with a processor, the non-linear filter;
resolving, with the processor, the non-linear filter into a summation of polyphase components;
reducing the computational complexity of the non-liner filter by:
modifying the polyphase components; and
interchanging positions of the modified polyphase components with said sampling rate converter so that said sampling rate converter is upstream of the modified polyphase components; and
implementing the filter arrangement with the sampling rate converter upstream of the modified polyphase components in the echo canceller.
13. The method of claim 12 , wherein the filter is a non-linear Volterra filter, wherein each homogeneous component of n th order of the Volterra filter is resolved according to
Hn
(
z
1
,
z
2
,
…
,
zn
)
=
∑
i
1
L
-
1
∑
i
2
L
-
1
…
∑
in
L
-
1
Hn
i
1
,
i
2
,
…
,
in
(
z
1
L
,
z
2
L
,
…
,
zn
L
)
·
z
1
-
i
1
z
2
-
i
2
…
zn
-
in
wherein Hn(z 1 ,z 2 , . . . ,zn) is the z-transform of the respective homogeneous component of n th order, L is a factor by which the conversion of the sampling rate is carried out, Hn i1,i2, . . . ,in (z 1 L , Z 2 L , . . . zn L ) are the polyphase components, and z 1 −i1 ,z 2 −i2 . . . zn in are delay components, and wherein for i 1 =i 2 = . . . =in the factors z 1 −i1 ,z 2 −i2 , . . . ,zn −in are in each case condensed to a separate delay element of the form z 1 −i1 ,z 2 −i2 , . . . ,zn −in .
14. The method of claim 12 , wherein the filter is a non-linear Volterra filter, wherein each homogeneous component of n th order of the Volterra filter is resolved according to
Hn
(
z
1
,
z
2
,
…
,
zn
)
=
∑
i
1
L
-
1
∑
i
2
L
-
1
…
∑
in
L
-
1
Hn
i
1
,
i
2
,
…
,
in
(
z
1
L
,
z
2
L
,
…
,
zn
L
)
·
z
1
-
i
1
z
2
-
i
2
…
zn
-
in
wherein Hn(z 1 ,z 2 , . . . ,zn) is the z-transform of the respective homogeneous component of n th order, L is a factor by which the conversion of the sampling rate is carried out, Hn i1,i2, . . . ,in (z 1 L ,z 2 L , zn L ) are the polyphase components, and z 1 −i1 ,z 2 −i2 , . . . ,zn −in are delay components, and wherein for polyphase components in which not all indices i 1 ,i 2 , . . . ,in are equal, the factors z 1 −i1 ,z 2 −i2 , . . . ,zn −in are used as delay elements z 1 −i1 ,z 2 −i2 , . . . ,zn −in before inputs of the respective polyphase component.
15. The method of claim 12 , wherein the filter is a non-linear Volterra filter, wherein each homogeneous component of n th order of the Volterra filter is resolved according to
Hn
(
z
1
,
z
2
,
…
,
zn
)
=
∑
i
1
L
-
1
∑
i
2
L
-
1
…
∑
in
L
-
1
Hn
i
1
,
i
2
,
…
,
in
(
z
1
L
,
z
2
L
,
…
,
zn
L
)
·
z
1
-
i
1
z
2
-
i
2
…
zn
-
in
wherein Hn(z 1 ,z 2 , . . . ,zn) is the z-transform of the respective homogeneous component of n th order, L is a factor by which the conversion of the sampling rate is carried out, Hn i1, i2, . . . ,in (z 1 L ,z 2 L , . . . ,zn L ) are the polyphase components z 1 −i1 ,z 2 −i2 . . . zn −in are delay components, wherein the interchange of the polyphase components with the sampling rate converter is carried out utilising an identity according to which a polyphase component of the form Hn i1,i2, . . . ,in (z 1 L ,z 2 L , . . . ,zn L ) with a sampling rate converter connected downstream corresponds to the sampling rate converter with polyphase component of the form Hn i1,i2, . . . ,in (z 1 ,z 2 , . . . ,zn) connected downstream.
16. A method of implementing a filter arrangement in an echo canceller in a communication system, comprising:
increasing a sampling rate of a signal fed to a first sampling rate converter by a first factor;
connecting a non-linear filter downstream of the first sampling rate converter;
connecting a second sampling rate converter downstream of the non-linear filter;
reducing a sampling rate of a signal to be fed to the second sampling rate converter by a second factor;
reducing, with a processor, a computational complexity of a first section of the filter arrangement comprising the first sampling rate converter and the non-linear filter by:
forming a form of the non-linear filter suitable for reducing the computational complexity;
resolving the non-linear filter into a summation of polyphase components;
modifying the polyphase components; and
interchanging the modified polyphase components with the first sampling rate converter so that the first sampling rate converter is downstream of the modified polyphase components of the first section; and
implementing the filter arrangement with the first sampling rate converter downstream of the modified polyphase components of the first section in the echo canceller.
17. The method of claim 16 , comprising:
reducing, with the processor, a computational complexity of a second section of the filter arrangement comprising the non-linear filter and the second sampling rate converter by:
forming a form of the non-linear filter suitable for reducing the computational complexity;
resolving the non-linear filter into a summation of polyphase components;
modifying the polyphase components; and
interchanging the modified polyphase components with the second sampling rate converter so that the second sampling rate converter is upstream of the modified polyphase components of the second section; and
implementing the filter arrangement with the second sampling rate converter upstream of the modified polyphase components of the second section.
18. The method of claim 16 , wherein the first factor is an integral multiple of the second factor, and wherein the first sampling rate converter and the second sampling rate converter are combined to form a single sampling rate converter.
19. The method of claim 16 , wherein the second factor is an integral multiple of the first factor, and wherein the first sampling rate converter and the second sampling rate converter are combined to form a single sampling rate converter.
20. The method of claim 19 , wherein the single sampling rate converter is interchanged before the filter by forming a form of the non-linear filter suitable for reducing the computational complexity by resolving the filter into polyphase components in such a way that the polyphase components can be interchanged with said single sampling rate converter, and by interchanging the polyphase components with said single sampling rate converter.
21. The method of claim 19 , wherein polyphase components that are coupled to delays are removed from the filter arrangement.
22. The method of claim 16 , wherein the first factor and the second factor are relatively prime, wherein the computational complexity of the section comprising the first sampling rate converter and the non-linear filter is reduced by forming a form of the filter suitable for reducing the computational complexity by resolving the filter is resolved into polyphase components in such a way that the polyphase components can be interchanged with said first sampling rate converter, and by interchanging the polyphase components with the first sampling rate converter, and wherein the computational complexity of sections of the thereby formed filter arrangement comprising in each case one of the polyphase components and the second sampling rate converter, are reduced by forming a form of the respective polyphase component suitable for reducing the computational complexity by resolving the polyphase component into further polyphase components in such a way that the further polyphase components can be interchanged with said second sampling rate converter, and by interchanging the further polyphase components with the second sampling rate converter.
23. A method of implementing a filter arrangement in an echo canceller in a communication system, comprising:
increasing a sampling rate of a signal to be fed to the filter arrangement, including a first sampling rate converter, by a first factor;
connecting a first linear filter downstream of the first sampling rate converter;
connecting a static non-linearity downstream of the first linear filter;
connecting a second linear filter downstream of the static non-linearity;
connecting a second sampling rate converter downstream of the second linear filter for reducing a sampling rate of a signal to be emitted by the second linear filter by a second factor;
resolving, with a processor, the first linear filter and the second linear filter into polyphase components;
modifying the polyphase components of first linear filter and the second linear filter;
interchanging the modified polyphase components of the first linear filter with the first sampling rate converter such that the first sampling rate converter is downstream of modified polyphase components of the first linear filter; and
interchanging the modified polyphase components of the second linear filter with the second sampling rate converter such that the second sampling rate converter is upstream of the polyphase components of the second linear filter; and
implementing the filter arrangement with the first sampling rate converter downstream of modified polyphase components of the first linear filter and the second sampling rate converter upstream of the polyphase components of the second linear filter in the echo canceller.
24. The method of claim 23 , further including interchanging the static non-linearity with the first sampling rate converter, and combining the first sampling rate converter and the second sampling rate converter.
25. The method of claim 23 , wherein the first linear filter is a line.
26. The method of claim 23 , wherein the second linear filter is a line.
27. The method of claim 23 , wherein the polyphase components of at least one of the first linear filter and of the second linear filter are calculated according to
h
11
[
n
]
=
h
1
[
L
·
n
]
h
12
[
n
]
=
h
1
[
L
·
n
+
1
]
⋮
h
1
,
L
-
1
[
n
]
=
h
1
[
L
·
n
+
L
-
1
]
wherein hl is an impulse response of the first linear filter or of the second linear filter, respectively, n is a sampling index, h 11 ,h 12 , . . . ,h 1 ,L are the polyphase components of the first non-linear filter or of the second non-linear filter, and L is the first factor or the second factor.