Architectures for Particle Filtering - Signal Processing Systems - page 634

3 Parallel Resampling for Fast Particle Filtering

3.1 Weight Quantization Scheme

A weight of each particle, denoted as w , is computed

and these weights are normalized so that the sum of all weights is equal to one.
This computation is done in the PEs before resampling. During the resampling,
normalized particles are replicated according to the values of their weights in
decimal representation. The most critical issue in replication of particles is that
replicating exactly M particles with fixed-point processing is not guaranteed with
traditional quantization and rounding [ 24 ] .
As discussed in [ 24 ] , these weights are quantized with K bits (excluding the sign
bit), where K

( m ) for m =[ 0 ··· M − 1 ]

= log 2 ( M )+ 2. Thus, each weight is represented by

b 1 b 0 b 1 b 2 . w = b K − 1 b K − 2 ··· (4)

Two additional bits, b 1 b 2 are used to simplify the rounding and truncation
operations called tagging . The tagging is performed according to Table 2 . Thus,
when tagging is employed, rounding by any hardware is not necessary. When a
particle is tagged, the particle is additionally replicated. This simplifies hardware
complexity and speeds up the resampling process. Moreover, the tagging ensures
that the total number of replicated particles be always larger than or equal to M .
In the table, the entries of the first column are the last three bits of the binary
representation of a weight, the entries of the second column represent the used
rounding scheme, and the entries of the third column are the results due to rounding.
After rounding, the last two bits are no longer used. The entries of the fourth
column represent the tag status. Notice that the bit pattern 111 is not rounded but
tagged. Without tagging, an adder is needed to incorporate carry propagation to the
most significant bit. The tagging maintains the final replication factor without such
hardware. However, the bit pattern 011 is rounded where a simple bit reversal is
sufficient. The particles with 001 and 101 are also tagged.

Tabl e 2 Rounding/truncation scheme and tagging method
Last Three Bits ( b 0 b 1 b 2 ) Rounding Scheme Final Bit ( b 0 ) Tag Status

0 00 Truncate 0 none

0 01 Truncate 0 tag

0 10 Truncate 0 tag

0 11 Round 1 none

1 00 Truncate 1 none

1 01 Truncate 1 tag

1 10 Truncate 1 tag

1 11 Truncate 1 tag

The scheme divides resampled particles into two sets of particle, R and T