liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Techniques for Efficient Implementation of FIR and Particle Filtering
Linköpings universitet, Institutionen för systemteknik, Datorteknik. Linköpings universitet, Tekniska fakulteten.ORCID-id: 0000-0002-1509-9678
2016 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
Abstract [en]

FIR filters occupy a central place many signal processing applications which either alter the shape, frequency or the sampling frequency of the signal. FIR filters are used because of their stability and possibility to have linear-phase but require a high filter order to achieve the same magnitude specifications as compared to IIR filters. Depending on the size of the required transition bandwidth the filter order can range from tens to hundreds to even thousands. Since the implementation of the filters in digital domain requires multipliers and adders, high filter orders translate to a large number of these arithmetic units for its implementation. Research towards reducing the complexity of FIR filters has been going on for decades and the techniques used can be roughly divided into two categories; reduction in the number of multipliers and simplification of the multiplier implementation. 

One technique to reduce the number of multipliers is to use cascaded sub-filters with lower complexity to achieve the desired specification, known as FRM. One of the sub-filters is a upsampled model filter whose band edges are an integer multiple, termed as the period L, of the target filter's band edges. Other sub-filters may include complement and masking filters which filter different parts of the spectrum to achieve the desired response. From an implementation point-of-view, time-multiplexing is beneficial because generally the allowable maximum clock frequency supported by the current state-of-the-art semiconductor technology does not correspond to the application bound sample rate. A combination of these two techniques plays a significant role towards efficient implementation of FIR filters. Part of the work presented in this dissertation is architectures for time-multiplexed FRM filters that benefit from the inherent sparsity of the periodic model filters.

These time-multiplexed FRM filters not only reduce the number of multipliers but lowers the memory usage. Although the FRM technique requires a higher number delay elements, it results in fewer memories and more energy efficient memory schemes when time-multiplexed. Different memory arrangements and memory access schemes have also been discussed and compared in terms of their efficiency when using both single and dual-port memories. An efficient pipelining scheme has been proposed which reduces the number of pipelining registers while achieving similar clock frequencies. The single optimal point where the number of multiplications is minimum for non-time-multiplexed FRM filters is shown to become a function of both the period, L and time-multiplexing factor, M. This means that the minimum number of multipliers does not always correspond to the minimum number of multiplications which also increases the flexibility of implementation. These filters are shown to achieve power reduction between 23% and 68% for the considered examples.

To simplify the multiplier, alternate number systems like the LNS have been used to implement FIR filters, which reduces the multiplications to additions. FIR filters are realized by directly designing them using ILP in the LNS domain in the minimax sense using finite word length constraints. The branch and bound algorithm, a typical algorithm to implement ILP problems, is implemented based on LNS integers and several branching strategies are proposed and evaluated. The filter coefficients thus obtained are compared with the traditional finite word length coefficients obtained in the linear domain. It is shown that LNS FIR filters provide a better approximation  error compared to a standard FIR filter for a given coefficient word length.

FIR filters also offer an opportunity in complexity reduction by implementing the multipliers using Booth or standard high-radix multiplication. Both of these multiplication schemes generate pre-computed multiples of the multiplicand which are then selected based on the encoded bits of the multiplier. In TDF FIR filters, one input data is multiplied with a number of coefficients and complexity can be reduced by sharing the pre-computation of the multiplies of the input data for all multiplications. Part of this work includes a systematic and unified approach to the design of such computation sharing multipliers and a comparison of the two forms of multiplication. It also gives closed form expressions for the cost of different parts of multiplication and gives an overview of various ways to implement the select unit with respect to the design of multiplexers.

Particle filters are used to solve problems that require estimation of a system. Improved resampling schemes for reducing the latency of the resampling stage is proposed which uses a pre-fetch technique to reduce the latency between 50% to 95%  dependent on the number of pre-fetches. Generalized division-free architectures and compact memory structures are also proposed that map to different resampling algorithms and also help in reducing the complexity of the multinomial resampling algorithm and reduce the number of memories required by up to 50%.

sted, utgiver, år, opplag, sider
Linköping: Linköping University Electronic Press, 2016. , s. 109
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1716
Emneord [en]
FIR filter, Particle filter, architecture, ASIC, FPGA
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-124195DOI: 10.3384/diss.diva-124195ISBN: 978-91-7685-915-5 (tryckt)OAI: oai:DiVA.org:liu-124195DiVA, id: diva2:896498
Disputas
2016-02-23, Visionen, Hus B, Campus Valla, Linköping, 13:15 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2016-01-25 Laget: 2016-01-21 Sist oppdatert: 2019-10-29bibliografisk kontrollert
Delarbeid
1. A unified approach to the design and implementation of computation sharing multipliers: Computation sharing multipliers
Åpne denne publikasjonen i ny fane eller vindu >>A unified approach to the design and implementation of computation sharing multipliers: Computation sharing multipliers
(engelsk)Manuskript (preprint) (Annet vitenskapelig)
Abstract [en]

A unified approach to the design and implementation of computation sharing multiplier based on Booth and standard high-radix multiplication schemes is presented here. Both of these multiplication schemes have various building blocks and one of which is the pre-computer which can be shared across a number of multiplications if the multiplicand to the multipliers is same, like in a transposed direct form (TDF) finitelength impulse response (FIR) filter. Closed form expressions to estimate the cost of different building blocks based on different schemes have been developed and analyzed in different dimensions. Standalone multipliers and as part of computation sharing in FIR filters and complex multipliers have been realized in hardware and synthesized using standard cell library.

It is shown that apart from word length and filter length, the ratio  between the cost of implementing adders and multiplexers has an effect on the choice of optimal radix. The higher the ratio, the lower is the cost of implementing multiplexers which will benefit high radix. Higher radix will also benefit from computation sharing if the cost of one multiplication for it is less than the lower radix and it is shown that radix-16 Booth multiplier achieves lower area complexity and power consumption by an average of 7% and 17%, respectively.

Emneord
Computation sharing multipliers, standard high-radix multiplier, Booth multiplier, FIR filter
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-124194 (URN)
Tilgjengelig fra: 2016-01-21 Laget: 2016-01-21 Sist oppdatert: 2016-02-02bibliografisk kontrollert
2. On the implementation of time-multiplexed frequency-response masking filters
Åpne denne publikasjonen i ny fane eller vindu >>On the implementation of time-multiplexed frequency-response masking filters
2016 (engelsk)Inngår i: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 64, nr 15, s. 3933-3944Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

The complexity of narrow transition band finite-length impulse response (FIR) filters is high and can be reduced by using frequency-response masking (FRM) techniques. These techniques use a combination of periodic model and, possibly periodic, masking filters. Time-multiplexing is in general beneficial since only rarely does the technology bound maximum obtainable clock frequency and the application determined required sample rate correspond. Therefore, architectures for time-multiplexed FRM filters that benefit from the inherent sparsity of theperiodic filters are introduced in this work.

We show that FRM filters not only reduces the number of multipliers needed, but also have benefits in terms of memory usage. Despite the total amount of samples to be stored is larger for FRM, it results in fewer memory resources needed in FPGAs and more energy efficient memory schemes in ASICs. In total, the power consumption is significantly reduced compared to a single stage implementation. Furthermore, we show that the choice of the interpolation factor which gives the least complexity for the periodic model filter and subsequent masking filter(s) is a function of the time-multiplexing factor, meaning that the minimum number of multipliers not always correspond to the minimum number of multiplications. Both single-port and dual-port memories are considered and the involved trade-off in number of multipliers and memory complexity is illustrated. The results show that for FPGA implementation, the power reduction ranges from 23% to 68% for the considered examples.

sted, utgiver, år, opplag, sider
Institute of Electrical and Electronics Engineers (IEEE), 2016
Emneord
Frequency-response masking, FIR filter, FPGA, ASIC, time-multiplexing, memories
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-124190 (URN)10.1109/TSP.2016.2557298 (DOI)000379699800009 ()
Merknad

Vid tiden för disputation förelåg publikationen som manuskript

Tilgjengelig fra: 2016-01-21 Laget: 2016-01-21 Sist oppdatert: 2017-11-30bibliografisk kontrollert
3. Design of Finite Word Length Linear-Phase FIR Filters inthe Logarithmic Number System Domain
Åpne denne publikasjonen i ny fane eller vindu >>Design of Finite Word Length Linear-Phase FIR Filters inthe Logarithmic Number System Domain
2014 (engelsk)Inngår i: VLSI design (Print), ISSN 1065-514X, E-ISSN 1563-5171, Vol. 2014, nr 217495Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

Logarithmic number system (LNS) is an attractive alternative to realize finite-length impulse response filters because ofmultiplication in the linear domain being only addition in the logarithmic domain. In the literature, linear coefficients are directlyreplaced by the logarithmic equivalent. In this paper, an approach to directly optimize the finite word length coefficients in theLNS domain is proposed. This branch and bound algorithm is implemented based on LNS integers and several different branchingstrategies are proposed and evaluated. Optimal coefficients in the minimax sense are obtained and compared with the traditionalfinite word length representation in the linear domain as well as using rounding. Results show that the proposed method naturallyprovides smaller approximation error compared to rounding. Furthermore, they provide insights into finite word length propertiesof FIR filters coefficients in the LNS domain and show that LNS FIR filters typically provide a better approximation error comparedto a standard FIR filter.

sted, utgiver, år, opplag, sider
Egypt: Hindawi Publishing Corporation, 2014
Emneord
Logarithmic Number System, FIR Filter, Integer Linear Programming, Branch and Bound
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-105861 (URN)10.1155/2014/217495 (DOI)
Tilgjengelig fra: 2014-04-10 Laget: 2014-04-10 Sist oppdatert: 2017-12-05bibliografisk kontrollert
4. Improved particle filter resampling architectures
Åpne denne publikasjonen i ny fane eller vindu >>Improved particle filter resampling architectures
(engelsk)Manuskript (preprint) (Annet vitenskapelig)
Abstract [en]

The most challenging aspect of particle filtering hardware implementation is the resampling step which replicates particles with large weights and discards those with small weights because it has a high latency and can only be partially executed in parallel with the other steps of particle filtering. To reduce the latency, an improved resampling scheme is proposed in this work which involves pre-fetching from the weight memory in parallel to the fetching of a value from a random function generator. Architectures for realizing the pre-fetch technique are also proposed. The trade-off between the latency reduction achieved by increasing the size of the pre-fetch memory and the architectural implementation complexity has been analyzed. Results show that a pre-fetch of five achieves the best area-latency trade-off while on average achieving an 85% reduction in the latency.

We also propose a generic double multiplier architecture for resampling which avoids normalization divisions and makes the architecture equally efficient for non-powers-of-two number of particles as well as removes the need of explicitly ordering the random values for efficient multinomial resampling implementation. It is further improved by computing the cumulative sum of weights on-the-fly which helps in reducing the size of the weight memories by up to 50%.

Emneord
Particle filters, resampling algorithm, resampling architecture
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-124193 (URN)
Tilgjengelig fra: 2016-01-21 Laget: 2016-01-21 Sist oppdatert: 2016-02-02bibliografisk kontrollert

Open Access i DiVA

fulltext(1140 kB)1045 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 1140 kBChecksum SHA-512
e170a554a7d780a1f04ce7d2a8eb68ba9bf8e5f862d57cba7dfffcfa7757e9a1cfc8824f387c678deff57c30d4d84bc7fb3713ebd7ebda3448dbcf57d75086ef
Type fulltextMimetype application/pdf
Errata(90 kB)53 nedlastinger
Filinformasjon
Fil ERRATA01.pdfFilstørrelse 90 kBChecksum SHA-512
de51a240d3dc2d02ed18658b47f847e117258e6c95be94cc7484e03d2add896bf75ce98a5d70575951590fd6b1786cff57cf2aab34a1a32e95c8bddc4c854050
Type errataMimetype application/pdf
omslag(5445 kB)205 nedlastinger
Filinformasjon
Fil COVER01.pdfFilstørrelse 5445 kBChecksum SHA-512
54479932c5e521e883c250823adf733000af57b314d6d6975a9f0356d05b7dbdda2df645d03ad9aab647f91b476c56e4a1261d2504121450e7ebbf54b205a42c
Type coverMimetype application/pdf
Bestill online >>

Andre lenker

Forlagets fulltekst

Personposter BETA

Alam, Syed Asad

Søk i DiVA

Av forfatter/redaktør
Alam, Syed Asad
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 1045 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 3770 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf