{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,15]],"date-time":"2025-11-15T10:25:12Z","timestamp":1763202312591},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T00:00:00Z","timestamp":1576281600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T00:00:00Z","timestamp":1576281600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sign Process Syst"],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The most challenging aspect of particle filtering hardware implementation is the resampling step. This is because of high latency as it can be only partially executed in parallel with the other steps of particle filtering and has no inherent parallelism inside it. To reduce the latency, an improved resampling architecture is proposed which involves pre-fetching from the weight memory in parallel to the fetching of a value from a random function generator along with architectures for realizing the pre-fetch technique. This enables a particle filter using <jats:italic>M<\/jats:italic> particles with otherwise streaming operation to get new inputs more often than 2<jats:italic>M<\/jats:italic> cycles as the previously best approach gives. Results show that a pre-fetch buffer of five values achieves the best area-latency reduction trade-off while on average achieving an 85<jats:italic>%<\/jats:italic> reduction in latency for the resampling step leading to a sample time reduction of more than 40%. We also propose a generic division-free architecture for the resampling steps. It also removes the need of explicitly ordering the random values for efficient multinomial resampling implementation. In addition, on-the-fly computation of the cumulative sum of weights is proposed which helps reduce the word length of the particle weight memory. FPGA implementation results show that the memory size is reduced by up to 50%.<\/jats:p>","DOI":"10.1007\/s11265-019-01489-y","type":"journal-article","created":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T03:03:22Z","timestamp":1576292602000},"page":"555-568","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Improved Particle Filter Resampling Architectures"],"prefix":"10.1007","volume":"92","author":[{"given":"Syed Asad","family":"Alam","sequence":"first","affiliation":[]},{"given":"Oscar","family":"Gustafsson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,12,14]]},"reference":[{"key":"1489_CR1","unstructured":"Alam, S.A., & Gustafsson, O. (2015). Generalized resampling architecture and memory structure for particle filters. In Proc. Europ. Conf. Circuit Theory Design. Trondheim."},{"key":"1489_CR2","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.apacoust.2019.04.018","volume":"154","author":"N Ansari","year":"2019","unstructured":"Ansari, N., & Chamnongthai, K. (2019). Particle filtering with adaptive resampling scheme for modal frequency identification and dispersion curves estimation in ocean acoustics. Applied Acoustics, 154, 90\u201398.","journal-title":"Applied Acoustics"},{"issue":"2","key":"1489_CR3","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1109\/78.978374","volume":"50","author":"MS Arulampalam","year":"2002","unstructured":"Arulampalam, M.S., Maskell, S., Gordon, N., Clapp, T. (2002). A tutorial on particle filters for online nonlinear\/non-Gaussian Bayesian tracking. IEEE Transactions on Signal Processing, 50(2), 174\u2013188.","journal-title":"IEEE Transactions on Signal Processing"},{"issue":"17","key":"1489_CR4","doi-asserted-by":"publisher","first-page":"2888","DOI":"10.1155\/ASP.2005.2888","volume":"2005","author":"A Athalye","year":"2005","unstructured":"Athalye, A., Boli\u0107, M., Hong, S., Djuri\u0107, P.M. (2005). Generic hardware architectures for sampling and resampling in particle filters. EURASIP Journal on Advances in Signal Processing, 2005(17), 2888\u20132902.","journal-title":"EURASIP Journal on Advances in Signal Processing"},{"issue":"3","key":"1489_CR5","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1145\/355900.355907","volume":"6","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L., & Saxe, J.B. (1980). Generating sorted lists of random numbers. ACM Transactions on Mathematical Software, 6(3), 359\u2013364.","journal-title":"ACM Transactions on Mathematical Software"},{"key":"1489_CR6","unstructured":"Boli\u0107, M. (2004). Architectures for efficient implementation of particle filters PhD thesis. The Graduate School of Electrical Engineering, Stony Brook University."},{"key":"1489_CR7","unstructured":"Boli\u0107, M., Athalye, A., Djuri\u0107, P.M., Hong, S. (2004). Algorithmic modification of particle filters for hardware implementation. In: Proc. Europ. signal process. conf. (pp. 1641\u20131644)."},{"issue":"15","key":"1489_CR8","doi-asserted-by":"publisher","first-page":"2267","DOI":"10.1155\/S1110865704405149","volume":"2004","author":"M Boli\u0107","year":"2004","unstructured":"Boli\u0107, M., Djuri\u0107, P.M., Hong, S. (2004). Resampling algorithms for particle filters: a computational complexity perspective. EURASIP Journal on Advances in Signal Processing, 2004(15), 2267\u20132277.","journal-title":"EURASIP Journal on Advances in Signal Processing"},{"issue":"8","key":"1489_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1109\/MAES.2005.1499276","volume":"20","author":"F Daum","year":"2005","unstructured":"Daum, F. (2005). Nonlinear filters: beyond the Kalman filter. IEEE Aerospace and Electronic Systems Magazine, 20(8), 57\u201369.","journal-title":"IEEE Aerospace and Electronic Systems Magazine"},{"key":"1489_CR10","doi-asserted-by":"crossref","unstructured":"Douc, R., & Capp\u00e9, O. (2005). Comparison of resampling schemes for particle filtering. In Proc. Int. symp. image signal process. analysis (pp. 64\u201369).","DOI":"10.1109\/ISPA.2005.195385"},{"issue":"6","key":"1489_CR11","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1109\/MSP.2005.1550195","volume":"22","author":"A Doucet","year":"2005","unstructured":"Doucet, A., & Wang, X. (2005). Monte Carlo methods for signal processing: a review in the statistical signal processing context. IEEE Signal Processing Magazine, 22(6), 152\u2013170.","journal-title":"IEEE Signal Processing Magazine"},{"issue":"3","key":"1489_CR12","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1023\/A:1008935410038","volume":"10","author":"A Doucet","year":"2000","unstructured":"Doucet, A., Godsill, S., Andrieu, C. (2000). On sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing, 10(3), 197\u2013208.","journal-title":"Statistics and Computing"},{"key":"1489_CR13","doi-asserted-by":"crossref","unstructured":"Doucet, A., de Freitas, N., Gordon, N (Eds.). (2001). Sequential Monte Carlo methods in practice. New York: Springer.","DOI":"10.1007\/978-1-4757-3437-9"},{"issue":"2","key":"1489_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1049\/ip-f-2.1993.0015","volume":"140","author":"NJ Gordon","year":"1993","unstructured":"Gordon, N.J., Salmond, D.J., Smith, A.F.M. (1993). Novel approach to nonlinear\/non-Gaussian Bayesian state estimation. IEE Processing Radar Signal Process, 140(2), 107\u2013113.","journal-title":"IEE Processing Radar Signal Process"},{"issue":"2","key":"1489_CR15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1109\/78.978396","volume":"50","author":"F Gustafsson","year":"2002","unstructured":"Gustafsson, F., Gunnarsson, F., Bergman, N., Forssell, U., Jansson, J., Karlsson, R., Nordlund, P.J. (2002). Particle filters for positioning, navigation, and tracking. IEEE Transaction on Signal Process, 50(2), 425\u2013437.","journal-title":"IEEE Transaction on Signal Process"},{"key":"1489_CR16","first-page":"22","volume":"2010","author":"G Hendeby","year":"2010","unstructured":"Hendeby, G., Karlsson, R., Gustafsson, F. (2010). Particle filtering: the need for speed. EURASIP Journal on Advances in Signal Processing, 2010, 22.","journal-title":"EURASIP Journal on Advances in Signal Processing"},{"key":"1489_CR17","doi-asserted-by":"crossref","unstructured":"Hol, J.D., Sch\u00f6n, T.B., Gustafsson, F. (2006). On resampling algorithms for particle filters. In Proc. IEEE Nonlinear stat. signal process. workshop (pp. 79\u201382).","DOI":"10.1109\/NSSPW.2006.4378824"},{"issue":"1\u20132","key":"1489_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s11265-006-5919-9","volume":"44","author":"S Hong","year":"2006","unstructured":"Hong, S., Chin, S.S., Djuri\u0107, P, Bolic, M. (2006). Design and implementation of flexible resampling mechanism for high-speed parallel particle filters. Journal of VLSI Signal Processing Systems, 44(1\u20132), 47\u201362.","journal-title":"Journal of VLSI Signal Processing Systems"},{"key":"1489_CR19","unstructured":"Hong, S, Shi, Z, Chen, K. (2008). Compact resampling algorithm and hardware architecture for paticle filters. In Proc. Int. conf. comm. circuits syst. (pp. 886\u2013890)."},{"issue":"1","key":"1489_CR20","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s00034-009-9117-4","volume":"28","author":"SH Hong","year":"2010","unstructured":"Hong, S.H., Shi, Z.G., Chen, J.M., Chen, K.S. (2010). A low-power memory-efficient resampling architecture for particle filters. Circuits, Systems and Signal Processing, 28(1), 155\u2013167.","journal-title":"Circuits, Systems and Signal Processing"},{"issue":"11","key":"1489_CR21","doi-asserted-by":"publisher","first-page":"4917","DOI":"10.1109\/TVT.2014.2382644","volume":"64","author":"R Hostettler","year":"2015","unstructured":"Hostettler, R., & Djuri\u0107, P.M. (2015). Vehicle tracking based on fusion of magnetometer and accelerometer sensor measurements with particle filtering. IEEE Transactions on Vehicular Technology, 64(11), 4917\u20134928.","journal-title":"IEEE Transactions on Vehicular Technology"},{"issue":"99","key":"1489_CR22","first-page":"1","volume":"PP","author":"Z Jiang","year":"2017","unstructured":"Jiang, Z., Zhou, W., Li, H., Ni, W., Hang, Q. (2017). A new kind of accurate calibration method for robotic kinematic parameters based on extended Kalman and particle filter algorithm. IEEE Transactions on Industrial Electronic, PP(99), 1\u20131.","journal-title":"IEEE Transactions on Industrial Electronic"},{"key":"1489_CR23","doi-asserted-by":"crossref","unstructured":"Joo, Y., & McKeown, N. (1998). Doubling memory bandwidth for network buffers. In Proc. IEEE joint conf. IEEE comput. comm. soc., (Vol. 2 pp. 808\u2013815).","DOI":"10.1109\/INFCOM.1998.665104"},{"issue":"3","key":"1489_CR24","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1109\/MSP.2014.2330626","volume":"32","author":"T Li","year":"2015","unstructured":"Li, T., Boli\u0107, M., Djuri\u0107, P.M. (2015). Resampling methods for particle filtering: classification, implementation and strategies. IEEE Signal Processing Magazine, 32(3), 70\u201386.","journal-title":"IEEE Signal Processing Magazine"},{"issue":"11","key":"1489_CR25","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1049\/iet-ipr.2014.0666","volume":"9","author":"SD Lin","year":"2015","unstructured":"Lin, S.D., Lin, J.J., Chuang, C.Y. (2015). Particle filter with occlusion handling for visual tracking. IET Image Processing, 9(11), 959\u2013968.","journal-title":"IET Image Processing"},{"key":"1489_CR26","volume-title":"Beyond the Kalman filter: particle filters for tracking applications","author":"B Ristic","year":"2004","unstructured":"Ristic, B., Arulampalam, M.S., Gordon, N. (2004). Beyond the Kalman filter: particle filters for tracking applications. Artech House: Norwood."},{"issue":"5","key":"1489_CR27","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1109\/TIP.2008.920760","volume":"17","author":"AC Sankaranarayanan","year":"2008","unstructured":"Sankaranarayanan, A.C., Srivastava, A., Chellappa, R. (2008). Algorithmic and architectural optimizations for computationally efficient particle filtering. IEEE Transactions on Image Processing, 17(5), 737\u2013748.","journal-title":"IEEE Transactions on Image Processing"},{"issue":"2","key":"1489_CR28","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1109\/TVT.2010.2099676","volume":"60","author":"J Scharcanski","year":"2011","unstructured":"Scharcanski, J., de Oliveira, A.B., Cavalcanti, P.G., Yari, Y. (2011). A particle-filtering approach for vehicular tracking adaptive to occlusions. IEEE Transactions on Vehicular Technology, 60(2), 381\u2013389.","journal-title":"IEEE Transactions on Vehicular Technology"},{"issue":"6","key":"1489_CR29","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1007\/s00034-008-9062-7","volume":"27","author":"ZG Shi","year":"2008","unstructured":"Shi, Z.G., Hong, S.H., Chen, J.M., Chen, K.S., Sun, Y.X. (2008). Particle filter-based synchronization of chaotic colpitts circuits combating AWGN channel distortion. Circuits Syst Signal Process, 27(6), 833\u2013845.","journal-title":"Circuits Syst Signal Process"},{"key":"1489_CR30","doi-asserted-by":"crossref","unstructured":"Thomas, D.B., & Luk, W. (2008). Sampling from the exponential distribution using independent bernoulli variates. In Proc. Int. conf. field-programmable logic applicat. (pp. 239\u2013244).","DOI":"10.1109\/FPL.2008.4629938"},{"key":"1489_CR31","unstructured":"Thomas, D.B., Howes, L., Luk, W. (2009). A comparison of CPUs, GPUs, FPGAs, and massively parallel processor arrays for random number generation. In Proc. ACM\/SIGDA int. symp. field-programmable gate arrays FPGA \u201909 (pp. 63\u201372). New York: ACM."},{"key":"1489_CR32","doi-asserted-by":"crossref","unstructured":"Tian, M., Bo, Y., Chen, Z., Wu, P, Yue, C. (2019). Multi-target tracking method based on improved firefly algorithm optimized particle filter. Neurocomputing Available online.","DOI":"10.1016\/j.neucom.2019.06.003"}],"container-title":["Journal of Signal Processing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11265-019-01489-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11265-019-01489-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11265-019-01489-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T00:25:02Z","timestamp":1607819102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11265-019-01489-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,14]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["1489"],"URL":"https:\/\/doi.org\/10.1007\/s11265-019-01489-y","relation":{},"ISSN":["1939-8018","1939-8115"],"issn-type":[{"value":"1939-8018","type":"print"},{"value":"1939-8115","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,14]]},"assertion":[{"value":"8 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}