# Cyclic Sequence Generators as Program Counters for High-Speed FPGA-based
Processors

P. A. Suggate  R. W. Ward  T. C. A. Molteno<EMAIL_ADDRESS>Department of Physics, University of Otago, P.O. Box 56, Dunedin, New Zealand

###### Abstract

This paper compares the performance of conventional radix-2 program counters
with program counters based on Feedback Shift Registers (FSRs), a class of
cyclic sequence generator. FSR counters have constant time scaling with bit-
width, $N$, whereas FPGA-based radix-2 counters typically have $O(N)$ time-
complexity due to the carry-chain. Program counter performance is measured by
synthesis of standalone counter circuits, as well as synthesis of three FPGA-
based processor designs modified to incorporate FSR program counters. Hybrid
counters, combining both an FSR and a radix-2 counter, are presented as a
solution to the potential cache-coherency issues of FSR program counters.
Results show that high-speed processor designs benefit more from FSR program
counters, allowing both greater operating frequency and the use of fewer logic
resources.

###### keywords:

FPGA-Processor , FSR , LFSR , Feedback Shift Register , Cyclic Sequence
Generator , Program Counter

††journal: Reconfigurable Computing

###### Contents

  1. 1 Introduction
  2. 2 Program Counters
  3. 3 Formal framework for counters
  4. 4 Radix-2 Counters
    1. 4.1 Cyclic Sequence Generators
    2. 4.2 Hybrid PCs
  5. 5 FPGA Synthesis of Simple Counter Circuits
  6. 6 FPGA Synthesis of Complete PC Circuits
    1. 6.1 PC Circuit Results
  7. 7 Processor Design Examples
    1. 7.1 aeMB
    2. 7.2 TTA16
    3. 7.3 RISC16: A Small 16-bit RISC Processor
  8. 8 Discussion
    1. 8.1 FSR Program Counters
      1. 8.1.1 Relative Instruction Addressing
      2. 8.1.2 Cache Coherency
    2. 8.2 Hybrid Program Counters
  9. 9 Conclusions
    1. 9.1 Future Work

##  1 Introduction

A Program Counter (PC) circuit [10] generates the address of the next
instruction to be fetched for execution. The greatest contributor to total PC
circuit latency in an FPGA-based processor can be due to the counter that is
used to increment the current PC value. This is because conventional radix-2
counters implemented within FPGAs can have long carry chains. Pipelining can
be used to obtain a higher operating frequency but also increases logic usage,
and likely increases the branch penalty.

Non-radix-2 cyclic sequence generators can be used to generate the next
instruction address, for example a maximum-cycle Feedback Shift Register (FSR)
[5, 13, 6], and can lead to a reduction in total PC latency. This is because
FSR counters can be designed where the maximum depth of combinatorial logic
required is only one gate [7] therefore the PC latency is constant with bit-
width $N$. We explore how this reduction in PC circuit complexity can affect
maximum processor operating frequency for three FPGA processor designs.

The sequence of instruction addresses generated by a PC circuit using a
maximum-cycle FSR is pseudo-random. For a processor fetching instructions from
a small embedded memory this presents no problem. For processors that feature
an instruction cache an FSR PC will have poor cache-coherency behaviour. As as
solution we present a hybrid PC architecture. The hybid-PC is the
concatenation of two smaller counters. The hybrid PC uses a small radix-2
counter to step through instructions within a cache line, and a FSR counter
that cycles between cache line. When implemented within FPGA processors, this
hybrid approach has low latency and avoids cache-coherency problems.

##  2 Program Counters

Stan et al. [14] list the properties of generic up/down-counters but not all
of these properties are required for PC circuits. A program counter must be
`RESET`able, increment once every clock cycle as long as an `ENABLE` line is
asserted, and sometimes has its value changed by branch instructions (so it
needs to be `LOAD`able, and have `IN` lines). The value also needs to be
readable every clock cycle (using the `OUT` lines) in order to access the
memory address to fetch the next instruction. There is no need to support
other common counter features [14], such as being reversible, or any terminal
count operations. A black box diagram for a generic PC circuit is shown in
Figure 1.

Figure 1: Black box program counter model showing the required control
signals. The LOAD, ENABLE, and RESET actions all occur on the positive edge of
the clock (CLOCK).

##  3 Formal framework for counters

In order to investigate structures that can be used for program counters, it
is worth setting up some formalism.

A conventionial radix-2 counter can take on a range of values from 0 to
$2^{n}-1$ where $n$ is the number of bits. The next value of the counter is
obtained by incrementing the current value using radix-2 arithmetic. We will
show there is a isomorphism between this counter architecture and a family of
other counter architectures. We consider only finite counters, as all counters
implemented in digital logic will have a finite number of states.

We will start by defining a counter as finite and closed. Closed is not
necessary for a program counter (all we need is a sufficent sequence of states
to put the program in), but give us some nice properties.

We will then set up a ‘ordinary’ counter $\mathbf{C}_{n}$ which is a cycle of
length $n$. We will use isomorphism to this.

Lemma 3.1 is a useful grab bag of properties. Note that from Lemma 3.1(4,5),
any state can be used as a generator.

Lemma 3.4 states that all $n$-cyclic counters are isomorphic to
$\mathbf{C}_{n}$ (no suprises).

Corollary 3.6 states that all counters have a $n$-cyclic subcounter form some
$n$. Just find the limit cycle. Note that the limit cycle may have only one
element in it.

The central theorem is Theorem 3.7, that all counters have a sub-counter that
is isomorphic to $\mathbf{C}_{n}$ for some $n$. This ties these new counters
to counters with known behaviour.

Theorem 3.8 lets us join counters together to form hybrid counters.

Figure 2: Types of Program Counter

  * Definition

Consider a finite set of states $\mathbb{S}$ and an increment operator
$\sigma:\mathbb{S}\mapsto\mathbb{S}$. For the purposes of this paper we define
a counter as a pair $(\mathbb{S},\sigma)$ with the following property:

$\displaystyle\forall s\in\mathbb{S},\sigma(s)\in\mathbb{S}$ (1)

This (closure) is one of Peano’s axioms for the natural numbers [15] – we
don’t need the other four axioms for our purposes.

A useful special case is a modulo arithmetic counter, with the ordinary
increment operator.

  * Definition

Let $\mathbf{C}_{n}$ be the counter $(\mathbb{Z}_{n},f_{n})$ where
$f_{n}(x)=x+1\text{ mod }n$.

The conventional radix-2 counter with $m$ bits is now simply
$\mathbf{C}_{2^{m}}$.

  * Definition

We also define $\sigma^{n}(s)$ as $n$ successive applications of $\sigma$, so

$\displaystyle\sigma^{0}(s)=s$ (2) $\displaystyle\forall
n>0,\sigma^{n}(s)=\sigma(\sigma^{n-1}(s))$ (3)

  * Definition

Given a counter $(\mathbb{S},\sigma)$, $(\mathbb{T},\sigma)$ is a subcounter
of $(\mathbb{S},\sigma)$ if $(\mathbb{T},\sigma)$ is a counter and
$\mathbb{T}\subseteq\mathbb{S}$.

  * Definition

A counter $(\mathbb{S},\sigma)$ is $n$-cyclic if $|\mathbb{S}|=n$, $\exists
s_{0}\in\mathbb{S},\mathbb{S}=\\{\sigma^{i}(s_{0})|i\geq 0\\}$, and $\exists
m>0,\sigma^{m}(s_{0})=s_{0}$. $s_{0}$ is a _generator_ for the counter.

###### Lemma 3.1

Given an $n$-cyclic counter $(\mathbb{S},\sigma)$, then for any element
$s\in\mathbb{S}$

  1. 1.

$\forall t\in\mathbb{S},\exists i\geq 0,\sigma^{i}(s)=t$,

  2. 2.

$\sigma^{i}(s)\neq s$ for $0<i<n$,

  3. 3.

$\forall i,j,0\leq i,j<n,i\neq j\Rightarrow\sigma^{i}(s)\neq\sigma^{j}(s)$,

  4. 4.

$\\{\sigma^{i}(s)|0\leq i<n\\}=\\{\sigma^{i}(s)|i\geq 0\\}=\mathbb{S}$,

  5. 5.

$\sigma^{n}(s)=s$.

  * Proof

For (1), $s=\sigma^{j}(s_{0})$ and $t=\sigma^{k}(s_{0})$. If $j\leq k$,
$t=\sigma^{k}(s_{0})=\sigma^{k-j}(\sigma^{j}(s_{0}))=\sigma^{k-j}(s)$. If
$j>k$, we know that $\exists m>0,\sigma^{m}(s_{0})=s_{0}$, so choose $x$ such
that $mx>j-k$. $\sigma^{mx}(s_{0})=s_{0}$, so
$t=\sigma^{k}(s_{0})=\sigma^{k+mx}(s_{0})=\sigma^{k+mx-j}(\sigma^{j}(s_{0}))=\sigma^{k+mx-j}(s)$.

For (2), assume the contrary. If $\sigma^{i}(s)=s$ for some $0<i<n$, then
consider the set of states $\mathbb{T}=\\{\sigma^{j}(s)|0\leq j<i\\}$. For any
$t\in\mathbb{T}$, $t=\sigma^{j}(s)$ for some $0\leq j<i$. If $j<i-1$, then
$\sigma(t)=\sigma(\sigma^{j}(s))=\sigma^{j+1}(s)\in\mathbb{T}$. If $j=i-1$,
$\sigma(t)=\sigma(\sigma^{j}(s))=\sigma^{i}(s)=s\in\mathbb{T}$. Hence
$\mathbb{T}$ is closed under $\sigma$. However $|\mathbb{S}|=n$ and
$|\mathbb{T}|=i<n$, so $\exists u\in\mathbb{S}\setminus\mathbb{T}$. However,
$\mathbb{T}$ is closed under $\sigma$, so $\nexists p\geq 0,\sigma^{p}(s)=u$,
contradicting (1). Hence $\sigma^{m}(s)\neq s$ for $0<i<n$.

For (3), If $\sigma^{i}(s)=\sigma^{j}(s)$ for some $0\leq i<j<n$ (assuming
w.l.o.g. that $i<j$), then
$\sigma^{i}(s)=\sigma^{j}(s)=\sigma^{j-i}(\sigma^{i}(s))$ where $j-i<n$, which
violates (2).

For (4), $\sigma^{i}(s)$ where $0\leq i<n$ are elements of $\mathbb{S}$ and
from (3) these values are distinct, so $|\\{\sigma^{i}(s)|0\leq
i<n\\}|=n=|\mathbb{S}|$. $\exists j,s=\sigma^{j}(s_{0})$ so
$\\{\sigma^{i}(s)|0\leq i<n\\}=\\{\sigma^{i}(\sigma^{j}(s_{0}))|0\leq
i<n\\}=\\{\sigma^{i}(s_{0})|j\leq i<n+j\\}\subseteq\mathbb{S}$ (since
{$\mathbb{S},\sigma\\}$ is closed) hence $\\{\sigma^{i}(s)|0\leq
i<n\\}=\mathbb{S}$. Also, $\mathbb{S}=\\{\sigma^{i}(s)|0\leq
i<n\\}\subseteq|\\{\sigma^{i}(s)|0\leq i\\}=|\\{\sigma^{i}(s_{0})|j\leq
i\\}\subseteq\mathbb{S}$, so $\\{\sigma^{i}(s)|i\geq 0\\}=\mathbb{S}$.

For (5), we use (4) to give $\sigma^{n}(s)=\sigma^{i}(s)$ for some $0\leq
i<n$. Now
$\sigma^{n}(s)=\sigma^{n-i}(\sigma^{i}(s))=\sigma^{n-i}(\sigma^{n}(s))$. If
$n-i<n$ then (2) is contradicted, and $i\geq 0$, so $n-i=n$ and $i=0$. Hence
$\sigma^{n}(s)=\sigma^{0}(s)=s$.

###### Lemma 3.2

$\mathbf{C}_{n}$ is $n$-cyclic.

  * Proof

Just let $s_{0}=0$. $|\mathbb{Z}_{n}|=n$,
$\mathbb{Z}_{n}=\\{f_{n}^{i}(x)|i\geq 0\\}$ and $f_{n}^{n}(0)=0$.

###### Lemma 3.3

If $(\mathbb{S},\sigma)\cong(\mathbb{T},\tau)$, then $(\mathbb{S},\sigma)$ is
$n$-cyclic iff $(\mathbb{T},\tau)$ is $n$-cyclic.

  * Proof

Assume $(\mathbb{S},\sigma)$ is $n$-cyclic.
$(\mathbb{S},\sigma)\cong(\mathbb{T},\tau)$ so there exists a mapping
$g:\mathbb{S}\mapsto\mathbb{T}$ such that $\forall
s\in\mathbb{S},g(\sigma(\mathbb{s}))=\tau(g(\mathbb{s}))$ that is bijective.
If $i\geq 0$,
$g(\sigma^{i+1}(\mathbb{S}))=g(\sigma(\sigma^{i}(\mathbb{S})))=\tau(g(\sigma^{i}(\mathbb{S})))$,
hence it can easily be seen by induction that $\forall i\geq
0,g(\sigma^{i}(\mathbb{s}))=\tau^{i}(g(\mathbb{s}))$.

$|\mathbb{T}|=|\mathbb{S}|=n$ (from the bijection of $g$). Given
$s_{0}\in\mathbb{S},\mathbb{S}=\\{\sigma^{i}(s_{0})|i\geq 0\\}$, then
$\\{\tau^{i}(g(s_{0}))|i\geq 0\\}=\\{g(\sigma(s_{0}))|i\geq
0\\}=\\{g{s}|s\in\mathbb{S}\\}=\mathbb{T}$, since $g$ is bijective.
$\tau^{m}(g(s_{0}))=g(\sigma^{m}(s_{0}))=g(s_{0})$ (from the definition of
$n$-cyclic), so $(\mathbb{T},\tau)$.

If $(\mathbb{T},\tau)$ is $n$-cyclic, the proof that $(\mathbb{S},\sigma)$ is
$n$-cyclic follows from using the same argument with $g^{-1}$.

###### Lemma 3.4

A counter is $n$-cyclic iff it is isomorphic to $\mathbf{C}_{n}$. In
particular, if $(\mathbb{S},\sigma)$ is $n$-cyclic,
$g:\mathbb{Z}_{n}\mapsto\mathbb{S}$ as $g(i)=\sigma^{i}(s_{0})$ is an
isomorphism for any $s_{0}\in\mathbb{S}$.

Figure 3: Homomorphism between $C_{n}$ and $(\mathbb{S},\sigma)$ as used in
the proof for Lemma 3.4

  * Proof

Firstly we show that of a counter $n$-cyclic, then it is is isomorphic to
$\mathbf{C}_{n}$. We construct an a mapping $g$ and show it is an isomorphism.
Given an $n$-cyclic counter $(\mathbb{S},\sigma)$, pick any element
$s_{0}\in\mathbb{S}$. Define the mapping $g:\mathbb{Z}_{n}\mapsto\mathbb{S}$
as $g(i)=\sigma^{i}(s_{0})$. Given any $j$ such that $0\leq j<n$, there are
two cases. If $j<n-1$ then
$g(f_{n}(j))=g(j+1)=\sigma^{j+1}(s_{0})=\sigma(\sigma^{j}(s_{0}))=\sigma(g(j))$.
If $j=n-1$ then $g(f_{n}(j))=g(0)=s_{0}=\sigma^{n}(s_{0})\text{ (using
lemma~{}\ref{lemma_cycle_full}(5))
}=\sigma(\sigma^{n-1}(s_{0}))=\sigma(g(j))$. Hence $g$ is a homomorphism as
shown in Figure 3. From lemma 3.1(3) $g$ is an injection, and from lemma
3.1(4) $g$ is a surjection, hence $g$ is an isomorphism, and
$(\mathbb{S},\sigma)\cong\mathbf{C}_{n}$.

Going the other way, if a counter is isomorphic to $\mathbf{C}_{n}$, it is
$n$-cyclic from lemmata 3.2 and 3.3.

######  Theorem 3.5 (Generator)

Given a counter $(\mathbb{S},\sigma)$, $s\in\mathbb{S}$ and an integer $n$
such that $\sigma^{m}(s)\neq s$ for $0<m<n$ and $\sigma^{n}(s)=s$, then
$(\\{\sigma^{i}(s)|0\leq i<n\\},\sigma)$ is an $n$-cyclic subcounter of
$(\mathbb{S},\sigma)$.

  * Proof

Let $\mathbb{T}=\\{\sigma^{i}(s)|0\leq i<n\\}$. First we show that
$(\mathbb{T},\sigma)$, $s\in\mathbb{S}$ is a subcounter of
$(\mathbb{S},\sigma)$. Consider any element $t\in\mathbb{T}$.
$t=\sigma^{k}(s_{0})$ for some $0\leq k<n$.
$\sigma(t)=\sigma(\sigma^{k}(s))=\sigma^{k+1}(s)$. If $k<n-1$ then $k+1<n$, so
$\sigma(s)\in\mathbb{T}$. If $k=n-1$,
$\sigma(t)=\sigma^{n}(s)=\sigma(s)=\sigma^{0}(s)\in\mathbb{T}$, so equation 1
is satisfied, making $\mathbb{T}$ a counter. It is a subcounter of
$(\mathbb{S},\sigma)$ because $\mathbb{T}\subseteq\mathbb{S}$.

We need to show that the cardinality of $|\mathbb{T}|=n$. Clearly
$|\mathbb{T}|\leq n$ by the construction. If $|\mathbb{T}|<n$, then there
would be at least one repeated state, so $\exists 0\leq k,l<n,k\neq
l,\sigma^{k}(s)=\sigma(l)$. Assume w.l.o.g that $k<l$. Now
$s=\sigma^{n}(s)=\sigma^{n-l}(\sigma^{l}(s))=\sigma^{n-l}(\sigma^{k}(s))=\sigma^{n+k-l}s$.
$0<n+k-l<n$ which $\sigma^{m}(s)\neq s$ for $0<m<n$, so $|\mathbb{T}|=n$.

Consider any $\sigma^{i}(s),i\geq 0$. Let $j=i\text{ mod }n$, so $\exists
x,i=j+nx$. Now $\sigma^{i}(s)=\sigma^{i-nx}\sigma^{nx}(s)=\sigma^{j}(s)$. So
$\\{\sigma^{i}(s)|0\leq i<n\\}=\\{\sigma^{i}(s)|i\geq 0\\}$.

Putting this together, $|\mathbb{T}|=n$, $\exists
s\in\mathbb{T},\mathbb{T}=\\{\sigma^{i}(s)|i\geq 0\\}$, and $\sigma^{n}(s)=s$,
so $(\mathbb{T},\sigma)$ is an $n$-cyclic subcounter of $(\mathbb{S},\sigma)$.

  * Remark

It is worth noting (although we do not use or prove the result) that any
element $s$ of an $n$-cyclic counter $(\mathbb{S},\sigma)$can be used to
generate the counter in this way.

###### Corollary 3.6

All counters have an $n$-cyclic subcounter for some $n$.

  * Proof

This can be done by construction. Consider any counter $(\mathbb{S},\sigma)$.
$\mathbb{S}$ is defined to be finite, so let $m$ be the cardinality of
$\mathbb{S}$. Now pick any element $s_{0}\in\mathbb{S}$ and define a sequence
$<\sigma^{0}(s_{0}),\sigma^{1}(s_{0}),\sigma^{2}(s_{0}),\ldots,\sigma^{m-1}(s_{0}),\sigma^{m}(s_{0})>$.
Because of equation 1, all members of this sequence are elements of
$\mathbb{S}$, and the sequence has $m+1$ members. Therefore there must be at
least one value that occurs more than once in this sequence, so we can find
two integers $i$ and $j$ such that $\sigma^{i}(s_{0})=\sigma^{j}(s_{0})$ where
w.l.o.g. $i<j$ and for all $k$ such that
$i<k<j,\sigma^{j}(s_{0})\neq\sigma^{k}(s_{0})$ (if there was such a $k$ we
could choose $k$ instead of $j$ for the second value).

Let $\mathbb{T}=\\{\sigma^{k}(s_{0})|i\leq k<j\\}$.
$\\{\sigma^{k}(s_{0})|i\leq k<j\\}=\\{\sigma^{k}(\sigma^{i}(s_{0}))|0\leq
k<j-i\\}$, so by theorem3.5, $(\mathbb{T},\sigma)$ is an $n$-cyclic subcounter
of $(\mathbb{S},\sigma)$ where $n=j-i$.

###### Theorem 3.7

All counters have a sub-counter that is isomorphic to $\mathbf{C}_{n}$ for
some $n$.

  * Proof

This follows directly from lemma 3.4 and corollary 3.6.

  * Definition

Given two counters $(\mathbb{T},\tau)$, $(\mathbb{S},\sigma)$ and an element
$s_{0}\in\mathbb{S}$, we define
$(\mathbb{T},\tau)\oplus_{s_{0}}(\mathbb{S},\sigma)$ as the structure
$(\mathbb{T}\otimes\mathbb{S},\tau\oplus_{s_{0}}\sigma)$ where

$\tau\oplus_{s_{0}}\sigma((t,s))=\begin{cases}(\tau(t),\sigma(s))&s=s_{0}\\\
(t,\sigma(s))&s\neq s_{0}\\\ \end{cases}$ (4)

$(\mathbb{T},\tau)\oplus_{s_{0}}(\mathbb{S},\sigma)$ is clearly a counter, as
equation 1 is satisfied trivially.

###### Theorem 3.8

If $(\mathbb{T},\tau)$ is an $n$-cyclic counter and $(\mathbb{S},\sigma)$ is
an $m$-cyclic counter, then for any
$(\mathbb{T},\tau)\oplus_{s_{0}}(\mathbb{S},\sigma)$ is an $mn$-cyclic
counter.

  * Proof

We construct a mapping in $g:\mathbf{C}_{m}\mapsto\mathbb{S}$ as
$g(i)=\sigma^{i}(s_{0})$ and $h:\mathbf{C}_{n}\mapsto\mathbb{T}$ as
$h(i)=\tau^{i}(t_{0})$ for some $t_{0}\in\mathbb{T}$. These are isomorphisms
from lemma 3.4. Now consider $\mathbf{C}_{n}\oplus_{m-1}\mathbf{C}_{m}$, and a
map $p:\mathbb{Z}_{n}\otimes\mathbb{Z}_{m}\mapsto\mathbf{Z}_{mn}$ defined as
$p((j,i))=jm+i$. $p((f_{n}\oplus_{m-1}f_{m})((j,m-1))=p((j+1\text{ mod
}n,0))=(j+1\text{ mod }n)m=jm+m\text{ mod }mn$, and $\forall 0\leq
i<m-1,p((f_{n}\oplus_{m-1}f_{m})((j,i))=p((j,i+1))=jm+i+1=jm+i+1\text{ mod
}mn$ (since $jm+i+1<mn$), so $\forall 0\leq
i<m,p((f_{n}\oplus_{m-1}f_{m})((j,i))=p((j,i+1))=jm+i+1\text{ mod
}mn=p((j,i))+1\text{ mod }mn$. Hence $p$ is a homomorphism from
$\mathbf{C}_{n}\oplus_{m-1}\mathbf{C}_{m}$ to $\mathbf{C}_{mn}$. It is also
clearly a bijection and a surjection, hence an isomorphism. …

There is one operation other than increment that may be performed on a Program
Counter - the `LOAD` operation (`RESET` is simply a special case of this).
There are two forms of `LOAD` that are currently used:

A program might perform an absolute jump (or `LOAD`). This simply loads the
counter with a new value that has been calculated when the program is created,
and is of no difficulty for any sort of counter.

The other form, which is worth examining in some detail, is where the new
address is calculated as some offset $b$ from the current one by ‘adding’ it
to the current value of the program counter. Our system doesn’t have addition
defined, so we define one:

  * Definition

Given an counter $(\mathbb{S},\sigma)$, $s\in\mathbb{S}$ and an integer $b\geq
0$ then $s+b=\sigma^{b}(s)$.

In the case of $\mathbf{C}_{n}$, $s+b=f_{n}^{b}(s)=s\text{ `plus' }b\text{ mod
}n$, where ‘plus’ is the usual defintion of modulo addition.

##  4 Radix-2 Counters

Synchronous radix-2 counters are conventionally used for Program Counters,
however there is a trade-off between speed and size because of carry
propagation from low-order to higher-order bits [14].

The simplest radix-2 counter is a ripple-carry counter based on an adder [14].
This is slow ($O(N)$ combinatorial delay with increasing bit-width $N$) but
cheap in logic ($O(N)$). Xilinx FPGAs use carry-chains to provide the logic
for this. This can be improved to $O(\log N)$ combinatorial delay using a
carry-lookahead design [9] at the expense of extra logic.

An approach that allows increment in constant time is a redundant format [8]
which allows what is called ‘carry-free’ addition, but that has two issues. A
redundant representation needs twice as many latches and therefore consumes
more FPGA resources. Another problem is that a redundant output is unsuitable
for providing an address to access instructions. The output first needs to be
converted to a non-redundant format during each clock cycle, which is going to
require $O(\log N)$ propagation delay and extra logic for an adder. Some work
has been done using hybrid redundant number systems [11] to reduce the number
of extra registers, but there is still a substantial propagation delay
converting that to a usable format.

Another approach to designing an $O(1)$ delay counter is to use a cascade [9]
that begins with a short and fast counter, and continues with longer counters
that only need to be incremented occasionally and don’t need to be as fast.
However, this requires the slower counters to have their increments to be
precomputed [14] which makes the `LOAD` operation much more difficult.

###  4.1 Cyclic Sequence Generators

A cyclic sequence generator is a synchronous circuit that iterates through a
cyclic sequence of states. For a program counter, it is desirable to have a
simple circuit and a cyclic sequence that includes most of the possible
states. A good candidate for this is a maximum cycle feedback shift register.

A Feedback Shift Register (FSR) is a shift register that satisfies the
condition that the current state is generated by a linear function of its
previous state. There are many types of these, but the ones considered here
are linear (use XOR gates), and have a constant maximum combinatorial path,
therefore constant time performance ($O(1)$) with increasing bit width $N$
(see Figure 4 for some examples of these). This compares favourably with
radix-2 counters as described in Section 4. A well-known example of an FSR is
a Linear Feedback Shift Register [5, 6] (LFSR) that are widely used in
cryptography [6], communications systems [12] and for built-in self-test
systems [1]. A few of the types of FSR are:

(a) |
---|---
(b) |
(c) |
(d) |
Figure 4: 8 bit counters with a cycle size of 255. (a) Fibonacci LFSR, (b)
Galois LFSR, (c) Ring Generator, (d) MFSR

Fibonacci LFSR

takes the output of several of the registers and XORs them together to feed to
the input of the first register as shown in Figure 4a.

Galois LFSR

takes the output of the last register and XORs it with several of the register
inputs as shown in Figure 4b.

Ring Generators [7]

rearrange the shift register into a ring, and arranges the feedback
connections so that they only involve a small amount of routing, as shown in
Figure 4c.

MFSR [19]

(Multiple Feedback Shift Register) are a generalisation of ring generators,
allowing any output to be XORed with any input, but limits the fan-in and fan-
out to 2, as shown in Figure 4d.

Also worth considering are cellular automata [3]. These are not Feedback Shift
Registers but have similar properties. A cellular automaton has each bit set
from the XOR of the previous value of that bit and neighbouring bits, which
require more XOR gates than FSRs but keeps the routing very local.

An $N$-stage linear FSR is maximum-cycle when all $2^{N}\\!-\\!1$ non-zero
states occur as the FSR is iterated. Note that a cycle of $2^{N}$ cannot be
achieved as the all zero state will always map to the all zero state. Any
linear FSR can be represented as an $N\times N$ matrix $\mathbf{M}$ over the
field $GF(2)$, and this will be maximum cycle if and only of the
characteristic polynomial $p(x)=|M-xI|$ is primitive. Lists of primitive
characteristic polynomials and counters with maximum cycles can easily be
found [6, 2, 18] or generated.

All these structures are very fast, as described above, and have a relatively
small amount of logic ($O(N)$ which will mostly be the registers to store the
bits), and a pseudo-random sequence. They will have similar performance, due
to all having a maximum combinatorial part of just one XOR gate (In Fibonacci
this may be 4 gates, but this is still only one LUT on an FPGA). Slight
variations in performance may depend on required LUTs and routing in any
particular FPGA technology choice and application. The worst case number of
XOR gates, fan in and fan out is shown in Table 1. As the sequence is pseudo-
random, the bits may also reordered to search for small routing improvements.

FSR counters meet the counter requirements for PC circuit described in Section
2. They are easily loadable, support an enable, and the register can be read
directly. One disadvantage to using FSRs is that the maximal cycle size is
$2^{n}-1$, instead of the $2^{n}$ cycle of radix-2 counters. We refer to the
address not generated in the $2^{n}-1$ cycle as the “zero address”. While the
zero address does not represent a significant fraction of the address space,
this can be addressed with extra logic as used by Wang and McCluskey [17], but
this brings the propagation delay back to $O(\log N)$.

For the rest of this work we use MFSR counters. They have good fan-in, fan-
out, and a low gate count. Other FSRs could be used and would have very
similar results (see Figure 4).

Structure | XOR gates | Fan-in | Fan-out
---|---|---|---
Fibonacci LFSR | 1 | 4 | 2
Galois LFSR | 3 | 2 | 4
Ring Generator | 3 | 2 | 2
MFSR | 2 | 2 | 2
Cellular Automata | $N$ | 3 | 3
Table 1: Worst case XOR gate count, Fan-in and Fan-out for several types of
Feedback Shift Register with $N$ bits

###  4.2 Hybrid PCs

The instruction fetch order of FSR PCs may lead to poor run-time performance
for processor designs that contain an instruction cache. It is desirable to
have a PC that increments through all of the instructions within a cache line
before fetching a new cache line. For a cache line-size of 32 bytes, and a
fixed instruction-width of 32 bits, there will be eight instructions within a
cache line. Ideally, and in the absence of branching instructions, each of
these eight instructions should be fetched from the cache before fetching
another cache line from system memory.

The solution presented here is to combine two counters into one PC, a radix-2
counter for the three least-significant bits and a MFSR for the most-
significant bits. Since the Spartan-3 contains four-input Look-Up Tables
(LUTs), and the Virtex-5 has six input LUTs, a 3-bit radix-2 counter can be
built with just one layer of logic. When the upper count value is reached, the
MFSR portion of the PC is then incremented.

##  5 FPGA Synthesis of Simple Counter Circuits

Performance of the synthesised radix-2 and FSR counters are shown in Figure 5.
As the bit-width $N$ increases radix-2 counters show a linear increase in
latency, this is $O(N)$ time-complexity. The results show that for radix-2
counters of more than 6 bits, latency can be estimated as $2.9+0.064\times N$
ns. The FSR counters have $O(1)$ time complexity and a smaller constant of
only $1.8$ ns, compared with the radix-2 counters.

Figure 5: Counter circuit performance vs. counter size when synthesised for a
Spartan-3 FPGA. The radix-2 counter implementation used was the default
generated by the Xilinx ISE 9.2 tools. This implementation uses the hardware
carry-chain present in Spartan-3 devices.

##  6 FPGA Synthesis of Complete PC Circuits

A simple PC circuit was used when investigating the effect of counter-type on
PC performance. Figure 6 is a block diagram of the circuit used for testing
and the counter used was one of FSR, radix-2, or a hybrid where the lowest 3
bits are radix-2. Bit widths ranging from 8 to 32 bits were used.

Figure 6: Block diagram of the PC circuit used for the counter comparison
tests. The counter type was either a FSR, radix-2, or a FSR-radix-2 hybrid.

###  6.1 PC Circuit Results

The results of the PC circuit synthesis are shown in Figure 7. As with the
previous counter tests, the radix-2 circuits scale linearly with increasing
bit-width. Again though, the latencies of FSR-based circuits are lower than
radix-2 and both the FSR and hybrid PCs have $O(1)$ scaling with increasing
bit-width. Due to the Xilinx synthesiser using the carry-chain logic for the
radix-2 counters, and FSRs having a gate depth of just one, this is as
expected.

To demonstrate that the behaviour observed when synthesising for a Spartan-3
FPGA is not unique, Figure 8 also shows synthesis results for a Xilinx
Virtex-5 FPGA. The latency scaling with increasing bit-width is similar but
the Virtex-5 is clearly a faster architecture.

Figure 7: Xilinx Spartan-3 FPGA synthesis results of PC circuit performance
vs. counter size. PCs with three counter types are compared: FSR, radix-2, and
a FSR-radix-2 hybrid (Lower 3 bits radix-2, upper bits FSR). Figure 8: Xilinx
Virtex-5 FPGA synthesis results show that these devices are faster than
Spartan-3 FPGAs. The latency is lower but the comparative differences between
counter types is still very similar. The Virtex-5 FPGA is from the Xilinx
performance range of FPGAs. The Virtex-5 was used to demonstrate that the
Spartan-3 results can apply to other FPGAs.

##  7 Processor Design Examples

Three FPGA processors were synthesised and evaluated to show the effects of
different PC circuits on maximum clock frequency. The three processor logic
cores used are aeMB, TTA16, and RISC16. aeMB was designed to use a
conventional radix-2 PC whereas RISC16 and TTA16 were designed to use a PC
circuit based on either a FSR or radix-2 counter.

This is to examine if substituting a FSR-based PC into an existing processor
design leads to any performance gains of the processor as a whole, and if
there is a detrimental effect of adding a radix-2-based PC to a processor
designed for a FSR-based PC. A Xilinx Spartan-3 FPGA was again the synthesis
target and Xilinx ISE 9.2 was the synthesis tool.

###  7.1 aeMB: A MicroBlaze Compatible RISC Processor

The aeMB processor logic core is 32-bit, Harvard architecture, RISC processor
with a three-stage pipeline. It is an open source project that was designed to
be instruction compatible with the MicroBlaze core [20]. When the aeMB
processor core was synthesised for a Spartan-3 FPGA it used about 2600 logic
elements.

The critical path of aeMB, as determined from the Xilinx place-and-route
timing report, is the instruction-cache look-up path. Total routing resources
used were 515643 paths with the original radix-2 PC. The source code was
modified, substituting a FSR PC for the radix-2 PC, and resynthesised. This
was a straight PC-logic substitution and did not address any potential
problems with relative branching and cache coherency.

Maximum operating frequency increased slightly, as is shown in Table 2, logic
resource utilisation was similar, but the FSR degign used only 503608 paths.
This is a large change in pathing resources used for a small change to the
total degign. This large difference in pathing resources, caused only by the
change to the PC circuit, was not observed with the other processor cores.

CPU | PC Size | FSR | Radix-2 | Pipeline
---|---|---|---|---
(Name) | (Bits) | (MHz) | (MHz) | Stages
TTA16 | 10 | 192 | 157 | 3
RISC16 | 10 | 143 | 141 | 5
aeMB | 30 | 84 | 80 | 3
Table 2: Three different processor designs were synthesised, each with a FSR
PC and with a radix-2 PC. Gains are negligible except when the PC circuit is
the critical path, as with TTA16.

###  7.2 TTA16

TTA16 is a 16-bit, Transport Triggered Architecture [4] (TTA) processor
optimised for Xilinx Spartan-3 FPGAs. It is an open-source, Harvard
architecture processor and was designed for the high-throughput, data-
processing tasks of the Open Video Graphics Adapter (OpenVGA) project [16].
TTA processors have very simple instruction word formats and require only very
simple instruction decoders resulting in smaller processor cores. The TTA16 PC
circuit is similar to that shown in Figure 6 and contains source code for both
types of PC, FSR or radix-2, and can be synthesised with either one.

TTA16 was the processor that showed the greatest frequency improvement with an
FSR PC (see Table 2), the FSR counter has 22% greater clock frequency than
with the radix-2 counter. TTA16 configured to use the FSR PC is substantially
faster than with the radix-2 PC because TTA16 was designed to use a low-
latency PC circuit. When TTA16 is synthesised with a radix-2 counter the PC
circuit becomes the critical path limiting maximum frequency. We speculate
that adding an additional pipeline stage to the radix-2 PC circuit may improve
maximum processor frequency, but this would also increase branch latency and
FPGA resources required.

###  7.3 RISC16: A Small 16-bit RISC Processor

RISC16 was also designed for OpenVGA [16], for comparison with TTA16, and
shares many design elements. The RISC16 core is has five pipeline stages
arranged so that each has similar latency. Decreasing the latency of one small
component, the PC circuit, would not be expected to have a big effect on
overall performance. Table 2 shows that there were no substantial difference
between the FSR and radix-2 PC implementations of the RISC16 processor core.

##  8 Discussion

Radix-2 counters are the conventional counters used for the processors PC.
These have been studied and used extensively. Memories, including caches,
often support linear, burst transfers assuming a radix-2 count order. Current
software tools, like assemblers and compilers, assume a radix-2 count order as
well. FPGAs, like the Xilinx Spartan-3 and Virtex-5 families, contain carry-
chains to support radix-2 counters as well.

Traditional assemblers will generate object code suitable only for the radix-2
PC increment sequence. For processors with FSR-based PCs, an assembler is
needed that will use a description of the FSR to correctly re-order the
processor instruction. An assembler was developed for this purpose and reads
an XML-encoded complete processor description prior to generating the assembly
output. The assembler supports FSR and radix-2, as well as hybrid PCs
consisting of a concatenation of an arbitrary number of FSR and radix2
counters. For each FSR counter used the tap sequence describing the FSR is
also encoded within the processor description file.

###  8.1 FSR Program Counters

The FSR counters are very fast (see Figure 6) leading to a substantially
lower-latency PC circuit (see Figure 5). This in turn leads to notable gains
in maximum processor operating frequency for the processor with the highest
operating frequency, TTA16 (see Table 2). Because a maximal-cycle FSR count
cycle is different from a radix-2 counter this has effects on tools,
instruction encoding, and cache coherency.

####  8.1.1 Relative Instruction Addressing

The instruction set of many processors contain branch instructions that store
an offset that is added to the current value of the PC. These instructions are
called PC-relative branch instructions. When the offset is encoded with a bit-
width narrower than the PC, this branching is difficult to do with FSRs.

PC-relative branching with small offsets is widely used in contemporary
processors [10] as it allows a subset of addresses, those that are close to
the current instruction, to be encoded within an instruction. The simplest
approach with FSR-based PCs is to not support PC relative branching. This
problem is more easily resolved using Hybrid PCs (see Section 8.2).

####  8.1.2 Cache Coherency

For processor designs featuring an instruction cache, a FSR-based PC will lead
to poor performance. A single FSR-based PC circuit will traverse program
memory in a pseudo-random count cycle. Caches are typically designed to fetch
multiple words from sequential adresses, called cache lines. A FSR PC circuit
may only execute one instruction from this cache line, and then the cache may
need to fetch another. A solution to this problem is introduced in Section 4.2
and then issues are discussed in Section 8.2.

###  8.2 Hybrid Program Counters

The synthesis results, shown in Figures 7 and 8, for the hybrid PCs described
in Section 4.2 show that performance is greater than radix-2 PCs at all tested
bit-widths. They are therefore a good solution to the cache coherency problems
of FSRs. Figures 7 and 8 show that hybrid PCs have only slightly higher
latency than pure FSR PCs and with the same constant-latency behaviour with
increasing $N$. Hybrid PCs can also be used to solve problems with relative
branching and position independent code, though this is future work.

With a hybrid-PC, the FSR portion will not increment when its value is zero,
so there is one entire cache line which will not be accessed by the count
cycle. This need not be a disadvantage because the first cache line could be
used to store other information, for example the interrupt vector table.

##  9 Conclusions

We have designed PC circuits that can allow some FPGA-based processors to
operate at higher frequencies. This is because FSR-based counters have very
low latency, a depth of just one logic gate, and PC circuits utilising FSRs
can have substantially lower latency when implemented in FPGAs. Due to the
constant-time behaviour, with increasing bit-width $N$, FSR counters have an
even greater advantage, relative to radix-2 counters, when $N$ is large.

For small embedded FPGA processors executing instructions stored in local
SRAMs, the pseudo-random count cycle of FSRs is no significant problem either
as long as the user has the necessary tools to generate code. We have also
presented hybrid PCs to solve the FSR cache-coherency issues for processors
that use an instruction cache to reduce average latency for instruction
fetching.

###  9.1 Future Work

There can be many possible maximal-cycle FSRs for a particular bit-width. Some
FSRs, due to each having a slightly different circuit, may be faster for a
specific implementation than other FSRs. Testing was not performed to find the
fastest available FSR circuit for a particular implementation. A future
project might be searching amongst the many possible FSRs to find the lowest
latency circuit.

Modern compilers can generate position independent code making use of relative
branching that is not practicable with a pure FSR-based PC. Further work
exploring hybrid program counters, consisting of three or more smaller
counters, could probably be used to solve the FSR relative addressing
problems.

The emphasis of this work is on FPGA-based processors. Due to their very low
gate depth and reduced logic complexity FSR and FSR-radix-2 hybrid PCs may
also prove useful with some very low gate-count, or very high clock frequency
processors realised in Silicon.

## References

  * [1] V.D. Agrawal, C.R. Kime, and K.K. Saluja.  A Tutorial on Built-in Self-Test. I. Principles.  IEEE Design & Test, 10(1):73–82, 1993.
  * [2] Peter Alfke.  Application Note: Efficient Shift Registers, LFSR Counters, and Long Pseudo- Random Sequence Generators.  Technical report, Xilinx Inc., San Jose, CA, 1996.  App. note XApp052.
  * [3] T. Chang, I. Song, J. Bae, and K.S. Kim.  Maximum length cellular automaton sequences and its application.  Signal Processing, 56(2):199–203, 1997.
  * [4] H. Corporaal.  Transport triggered architectures examined for general purpose applications.  In Sixth Workshop on Computer Systems, pages 55–71, 1994.
  * [5] S.W Golomb.  Shift Register Sequences.  Aegean Park Press, Laguna Hills, CA, USA, 1981.
  * [6] A. Menezes, P. van Oorschot, and S. Vanstone.  Handbook of Applied Cryptography.  CRC Press, Boca Raton, 1997.
  * [7] G. Mrugalski, N. Mukherjee, J. Rajski, and J. Tyszer.  High Performance Dense Ring Generators.  IEEE Transactions on Computers, pages 83–87, 2006.
  * [8] B. Parhami.  Systolic up/down counters with zero and sign detection.  In Proc. Symp. Comput. Arithmetic, pages 174–178, 1987.
  * [9] B. Parhami.  Computer arithmetic.  Oxford University Press, 2000.
  * [10] B. Parhami.  Computer Architecture: From Microprocessors to Supercomputers (Oxford Series in Electrical and Computer Engineering).  Oxford University Press, Inc. New York, NY, USA, 2005.
  * [11] DS Phatak and I. Koren.  Hybrid signed-digit number systems: a unified framework forredundant number representations with bounded carry propagation chains.  IEEE Transactions on computers, 43(8):880–891, 1994.
  * [12] R. Pickholtz, D. Schilling, and L. Milstein.  Theory of Spread-Spectrum Communications–A Tutorial.  Communications, IEEE Transactions on [legacy, pre-1988], 30(5 Part 2):855–884, 1982.
  * [13] M.J.B. Robshaw.  Stream Ciphers.  RSA Labratories, 25, 1995.
  * [14] M.R. Stan, A.F. Tenca, and M.D. Ercegovac.  Long and Fast Up/Down Counters.  IEEE Transactions on Computers, 47(7):722–735, 1998.
  * [15] R.R. Stoll.  Set theory and Logic.  W H Freeman, 1963.
  * [16] P. Suggate.  OpenVGA: An Open-Source PCI Graphics Adapter.  Master’s thesis, University of Otago, 2009.
  * [17] L.T. Wang and E.J. McCluskey.  Hybrid designs generating maximum-length sequences.  Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 7(1):91–99, 1988.
  * [18] R. W. Ward and T.C.A. Molteno.  Table of multiple feedback shift registers.  Technical Report 2009-1, University of Otago, 2009.
  * [19] Roy W. Ward and T.C.A. Molteno.  Counter Representations in Microprocessors.  In ENZCon06 Conference Precedings. ENZCon, 2006.
  * [20] Xilinx Inc.  Microblaze processor reference guide, 2008.


# The Effect of Ground Truth Accuracy on the Evaluation of Localization
Systems

Chen Gu  Google, USA
<EMAIL_ADDRESS>Ahmed Shokry  Alexandria University, Egypt
<EMAIL_ADDRESS>Moustafa Youssef  AUC and Alexandria University,
Egypt
<EMAIL_ADDRESS>
###### Abstract

The ability to accurately evaluate the performance of location determination
systems is crucial for many applications. Typically, the performance of such
systems is obtained by comparing ground truth locations with estimated
locations. However, these ground truth locations are usually obtained by
clicking on a map or using other worldwide available technologies like GPS.
This introduces ground truth errors that are due to the marking process, map
distortions, or inherent GPS inaccuracy.

In this paper, we present a theoretical framework for analyzing the effect of
ground truth errors on the evaluation of localization systems. Based on that,
we design two algorithms for computing the real algorithmic error from the
validation error and marking/map ground truth errors, respectively. We further
establish bounds on different performance metrics.

Validation of our theoretical assumptions and analysis using real data
collected in a typical environment shows the ability of our theoretical
framework to correct the estimated error of a localization algorithm in the
presence of ground truth errors. Specifically, our marking error algorithm
matches the real error CDF within 4%, and our map error algorithm provides a
more accurate estimate of the median/tail error by 150%/72% when the map is
shifted by 6m.

###### Index Terms:

Localization, Real error, Validation error, Marking error, Map error, Rayleigh
distribution, Rice distribution

##  I Introduction

Location determination technologies have gained momentum recently with a
number of outdoor and indoor applications such as directions finding, directed
ads, E911, driverless cars, among others. Typically, the performance of
location determination systems is quantified through some measures, e.g. the
full error CDF, or a single-value metric such as median, mean, or different
percentiles. To do that, a ground truth data set is usually collected tagged
with the actual user location to compare the estimated location against. This
ground truth location can be entered manually, by a user clicking on the map
where he/she is standing, or automatically; by using a higher accuracy
tracking technology; e.g. using GPS or GNSS systems as ground truth for
cellular-based localization technologies [32, 28, 11, 15, 2, 22].

These methods for ground truth collection are inherently noisy and may lead to
inaccuracy in the reported evaluation results of a particular localization
system [31, 1, 18, 30, 2, 3, 16, 12, 36]. In particular, a human ground truth
collector may click on the map in the wrong location when marking his/her
position. This is especially true in open areas, when there are no landmarks
to help determine where the user is standing, or when the user marks the
location on the limited mobile device screen. Moreover, in many cases, ground
truth locations may be marked at a lower granularity to reduce the collection
overhead, e.g. by marking the start and end location of a trace and
interpolating the ground truth points between them [22, 5]. Furthermore, the
map used for marking the ground truth locations may contain errors itself,
e.g. have an offset or scale error (Figure 1), an error whose possibility
increases with a worldwide deployment. All of these factors could affect the
reported accuracy of a localization system, which can be significant when the
current state-of-the-art is trying to squeeze the errors in their systems.

In this paper, we present a theoretical framework for analyzing the effect of
ground truth errors on the evaluation of localization systems. Using this
framework, we design two algorithms for computing the real algorithmic error
from the validation error and marking/map ground truth errors, respectively.
These algorithms can be used to adjust the reported accuracy on the different
metrics of a given localization system to account for ground truth collection
issues, as well as to prioritize which factors should be handled more
carefully. Specifically, our analysis shows interesting findings: (a) The
impact of marking error on evaluation accuracy is quadratic; (b) As the
accuracy of the localization system gets better, the impact of error in ground
truth grows; (c) The 95%-tail error is at least twice of the median/mean
errors; (d) Marking error has more impact than map error on the mean and
median, but less impact on the tail.

We validate our assumptions and analysis on a real indoor WiFi dataset. The
results show the ability of our theoretical framework to correct the estimated
error of a localization algorithm to obtain a more realistic error in the
presence of ground truth errors. In particular, our marking error algorithm
matches the real error within 4% in all percentiles. Moreover, our map error
algorithm provides a more accurate estimate of the median/tail error by more
than 20%/5% when the map is shifted by 1m in X and Y directions. This
enhancement increases to 150%/72% when the map is shifted by 6m.

To the best of our knowledge, this is the first work that quantifies the
effect of ground truth accuracy on the performance of location determination
systems.

The rest of the paper is organized as follows: Section II presents the
mathematical model formulation and notation used in the paper. Section III
gives the details of our theoretical analysis followed by the experimental
validation of the theoretical results in Section IV. Section V discusses
related work. Finally, we conclude the paper in section VI.

Figure 1: Map error example. The human-marked ground truth locations (green
circles) inside a railway station differ by a consistent offset of about 30
meters in the northeast direction. This is because the used map system had an
incorrect alignment of the building.

##  II Fundamental Mathematical Model

In this section, we introduce the mathematical model used for evaluating the
performance of a general location determination system and state the problems
we study in this paper.

###  II-A Types of Ground Truth Errors

First, we define two types of ground truth error: marking error and map error.
In Figure 2(a), the user is at the green circle but marks his/her location at
the blue triangle on an accurate map. In this case, we call the ground truth
error as marking error. For example, this can be due to the lack of landmarks
for the user to determine his/her exact location accurately on an open space
on the map of the small screen of a mobile device, or simply due to a mistake
from the user.

In Figure 2(b), the user would mark his/her location at the blue triangle if
an accurate map is used. However, he/she actually marks location at the orange
diamond due to using an incorrect map (as in Figure 1). In this case, we call
this second ground truth error as map error.

###  II-B System Model and Problem Statement

Next, consider a localization algorithm which returns a user’s 2D location
$X^{algo}$. Let $X^{gt}$ be the user’s actual (real) ground truth location and
$\widehat{X}^{gt}$ be the human-marked ground truth location. Ideally we would
like to calculate the algorithm’s real error $Err^{real}=X^{gt}-X^{algo}$.
However, due to the ground truth error $Err^{gt}=\widehat{X}^{gt}-X^{gt}$, the
validation error actually used to evaluate the algorithm’s performance in
literature and many practical systems is

$Err^{val}=\widehat{X}^{gt}-X^{algo}=Err^{real}+Err^{gt}$

Clearly, we are more interested in the location accuracy $|Err^{real}|$,
rather than $|Err^{val}|$ which is impacted by the ground truth error. Once
there is enough evaluation data ($\\{X^{algo},\widehat{X}^{gt}\\}$), we can
know the cumulative distribution function of $|Err^{val}|$. Furthermore,
instead of using the full distribution, the accuracy is commonly expressed
using high-level summary statistics, e.g. “some inexpensive GPS receivers can
locate positions to within 10 meters for approximately 95 percent of
measurements [13].” In this paper, we consider three major summary statistics
that are commonly used in literature and practical systems to quantify a
localization algorithm performance:

  * •

The mean error $|Err^{val}|_{mean}$

  * •

The 50%-median error $|Err^{val}|_{median}$

  * •

The 95%-tail error $|Err^{val}|_{tail}$ 111We select 95% as it is most
commonly used for confidence intervals [40]. But in theory any level can be
selected for the tail error such as 90% or 99%.

The mean and median reflects the average user experience, while the tail
reflects the worst user experience.

We again emphasize that, since we are more interested to know
$|Err^{real}|_{mean}$ instead of $|Err^{val}|_{mean}$, we define the impact of
ground truth error

$\Delta_{mean}=|Err^{val}|_{mean}-|Err^{real}|_{mean}$ (1)

as the difference between the validation error and the real error, i.e. how
much of the validation error is caused by the ground truth error. The notions
of $\Delta_{median}$ / $\Delta_{tail}$ are similar to (1).

Figure 2: Ground truth errors. (a) A marking error between actual ground truth
location (green circle) and human-marked ground truth location on an accurate
map (blue triangle). (b) An additional map error between human-marked ground
truth location on an accurate map (blue triangle) and that on an incorrect map
(orange diamond).

To summarize, in this paper we propose and answer the following questions:

  1. 1.

Given the summary statistics on the validation error $|Err^{val}|_{mean}$ and
the ground truth (marking/map) error $|Err^{gt}|_{mean}$, how can one computes
the real algorithmic error $|Err^{real}|_{mean}$?

  2. 2.

What is the relation between the impact $\Delta_{mean}$ and the ground truth
(marking/map) error $|Err^{gt}|_{mean}$?

  3. 3.

Can we answer the above two questions for other metrics such as the median or
95%-tail error, or more generally for any $q$-th quantile?

  4. 4.

Which ground truth error has a larger impact on the evaluation of a
localization system? Marking error or map error?

###  II-C Application Example

Given a localization algorithm with validation error $|Err^{val}|_{mean}=6m$
(which is the main metric commonly used in literature). The human-marked
ground truth is collected on an incorrect map with an offset $|Err^{map}|=2m$,
and we estimate there is an average marking error $|Err^{mark}|_{mean}=3m$.

First, we use Algorithm 2 (Section III-B) to remove the map error, which gives
a new validation error $|Err^{val}|_{mean}=5.79m$ on an accurate map. Next, we
use Algorithm 1 (Section III-A) to remove the marking error and end up with a
real error $|Err^{real}|_{mean}=4.95m$. This final error is a more
realistic/accurate reflection of the algorithm performance in real time after
removing the inaccuracy in ground truth collection.

##  III Theoretical Results

Mathematically, instead of giving the summary statistics $|Err^{val}|_{mean}$
and $|Err^{gt}|_{mean}$, even if we know the full distribution of $Err^{val}$
and $Err^{gt}$, it is still hard to solve the distribution of $Err^{real}$
such that $Err^{val}=Err^{real}+Err^{gt}$. This is because the real
algorithmic error and the ground truth error are independent, but the
validation error and the ground truth error are not; and we do not know the
correlation between them.

To make the problem mathematically tractable, we assume that the algorithmic
and marking errors follow the most widely used normal distributions. We also
further consider the map error of a constant translation.

We start by analyzing the marking error in Section III-A and map error in
Section III-B. We then compare these two errors in Section III-C, and discuss
the map scale error in Section III-D. All assumptions are validated in Section
IV.

###  III-A Marking Error

Algorithm 1 Compute the real error from validation error and marking error.
This algorithm uses mean but can be extended to any $q$-th quantile ($0<q<1$).

0: validation error mean $u=|Err^{val}|_{mean}$, marking error mean
$v=|Err^{mark}|_{mean}$, $u>v$

0: real error mean $|Err^{real}|_{mean}$

return $|Err^{real}|_{mean}=\sqrt{u^{2}-v^{2}}$

Assume that both the real algorithmic error and the marking error follow 2D
Gaussian distributions222We write $diag[{\sigma}^{2}]$ for short to represent
a matrix that has ${\sigma}^{2}$ on all diagonal entries and zero otherwise.
$Err^{real}\sim\mathcal{N}(0,diag[(\sigma^{real})^{2}])$,
$Err^{mark}\sim\mathcal{N}(0,diag[(\sigma^{mark})^{2}])$. We also assume that
both error distributions are symmetric in 2D (do not have any orientation
bias), so that they have zero mean and the errors in X and Y directions are
independent and identically distributed. In this setting, the validation error
is also a 2D Gaussian

$Err^{val}=Err^{real}+Err^{mark}\sim\mathcal{N}(0,diag[(\sigma^{val})^{2}])$

where $(\sigma^{val})^{2}=(\sigma^{real})^{2}+(\sigma^{mark})^{2}$.

For the 1D error norm, it is known that for a Gaussian variable
$X\sim\mathcal{N}(0,diag[{\sigma}^{2}])$, its norm $|X|$ follows a
distribution $|X|\sim Rayleigh(\sigma)$ [25] with a probability density
function $p(x|\sigma)=\frac{x}{\sigma^{2}}e^{-\frac{x^{2}}{2\sigma^{2}}}$,
$x\geq 0$ and its mean $|X|_{mean}$ is equal to
$Rayleigh(\sigma)_{mean}=\sigma\sqrt{\pi/2}$.

Thus $|Err^{mark}|$, $|Err^{real}|$ and $|Err^{val}|$ are all Rayleigh
distributions. Since the mean is linear in $\sigma$,

$\displaystyle|Err^{real}|_{mean}$
$\displaystyle=\sigma^{real}\sqrt{\pi/2}=\sqrt{\left((\sigma^{val})^{2}-(\sigma^{mark})^{2}\right)\pi/2}$
$\displaystyle=\sqrt{|Err^{val}|_{mean}^{2}-|Err^{mark}|_{mean}^{2}}$ (2)

Algorithm 1 shows how to obtain the real error mean given the validation and
marking error means. It also applies to the median and 95%-tail, because for
any $q$-th quantile ($0<q<1$),
$Rayleigh(\sigma)_{q\text{-th}}=\sigma\sqrt{-2\ln{(1-q)}}$ is always linear in
$\sigma$.

Figure 3: Impact of marking error $\Delta_{mean}$ as a function of
$|Err^{val}|_{mean}$ and $|Err^{mark}|_{mean}$. The figures for
$\Delta_{median}$ / $\Delta_{tail}$ are similar.

######  Theorem 1.

The impact of marking error ($\Delta_{mean}$):

$\frac{|Err^{mark}|_{mean}^{2}}{2|Err^{val}|_{mean}}<\Delta_{mean}<\frac{|Err^{mark}|_{mean}^{2}}{2|Err^{val}|_{mean}-|Err^{mark}|_{mean}}$

This also holds if we replace the mean by any $q$-th quantile (e.g.
$\Delta_{median}$ and $\Delta_{tail}$).

###### Proof.

From (2),
$|Err^{val}|_{mean}-|Err^{mark}|_{mean}<|Err^{real}|_{mean}<|Err^{val}|_{mean}$.

$\displaystyle\Delta_{mean}$
$\displaystyle=|Err^{val}|_{mean}-|Err^{real}|_{mean}$
$\displaystyle=\frac{|Err^{val}|_{mean}^{2}-|Err^{real}|_{mean}^{2}}{|Err^{val}|_{mean}+|Err^{real}|_{mean}}$
$\displaystyle=\frac{|Err^{mark}|_{mean}^{2}}{|Err^{val}|_{mean}+|Err^{real}|_{mean}}$
$\frac{|Err^{mark}|_{mean}^{2}}{2|Err^{val}|_{mean}}<\Delta_{mean}<\frac{|Err^{mark}|_{mean}^{2}}{2|Err^{val}|_{mean}-|Err^{mark}|_{mean}}$

∎

Theorem 1 gives us a direct quantitative measure on the impact of marking
error on location accuracy (see Figure 3):

  1. 1.

$\Delta$ is quadratic in $|Err^{mark}|$. This means that a small error in the
collected ground truth has a magnified (quadratic) impact on the error in the
reported algorithm accuracy.

  2. 2.

$\Delta$ is inversely proportional to $|Err^{val}|$, i.e. when a localization
algorithm does not perform well on validation, the impact of marking error is
not significant. As the algorithm improves to have better accuracy, the
quality of ground truth data becomes more and more important.

######  Theorem 2.

Relations between the real error mean, median, and 95%-tail.

$\frac{|Err^{real}|_{tail}}{|Err^{real}|_{median}}=2.07~{}\textrm{and}~{}\frac{|Err^{real}|_{tail}}{|Err^{real}|_{mean}}=1.95$

These also hold if we replace $|Err^{real}|$ by $|Err^{val}|$.

###### Proof.

$\displaystyle\frac{|Err^{real}|_{tail}}{|Err^{real}|_{median}}$
$\displaystyle=\frac{\sigma^{real}\sqrt{-2\ln{(1-0.95)}}}{\sigma^{real}\sqrt{-2\ln{(1-0.5)}}}=2.07$
$\displaystyle\frac{|Err^{real}|_{tail}}{|Err^{real}|_{mean}}$
$\displaystyle=\frac{\sigma^{real}\sqrt{-2\ln{(1-0.95)}}}{\sigma^{real}\sqrt{\pi/2}}=1.95$

∎

Theorem 2 gives us an approximation on the average/worst user experience on
location accuracy, e.g. if a GPS receiver has an accuracy of 10 meters for 95%
of the time, we would expect that it can localize within 5 meters for 50% of
the time.

###  III-B Map Error (Translation)

Figure 4: $\Delta_{mean}(v,1)$ approximation function. $\Delta(v,1)$ values
are calculated by using the numerical Bessel function [29]. $\delta(v,1)$
values are calculated by using the algebraic approximation function. The
figures for $\Delta_{median}$ / $\Delta_{tail}$ are similar.

Again, we assume that $Err^{real}\sim\mathcal{N}(0,diag[(\sigma^{real})^{2}])$
but $Err^{map}=V$ is a constant 2D vector. For now we assume that there is no
marking error (see Section II-C when both marking and map errors exist). In
this setting, the validation error is also a 2D Gaussian but with a non-zero
mean

$Err^{val}=Err^{real}+Err^{map}\sim\mathcal{N}(V,diag[(\sigma^{real})^{2}])$

For simplicity, let $\sigma=\sigma^{real}$ since there is only one variance
parameter in this section (as the map error is a constant), and $v=|V|$ be the
norm of the map error vector. The 1D error norm $|Err^{real}|\sim
Rayleigh(\sigma)$, $|Err^{map}|=v$.

For a non-zero mean Gaussian variable
$X\sim\mathcal{N}(V,diag[{\sigma}^{2}])$, its norm $|X|$ follows a
distribution $|X|\sim Rice(v,\sigma)$ [26] with a probability density function
$p(x|v,\sigma)=\frac{x}{\sigma^{2}}e^{-\frac{x^{2}+v^{2}}{2\sigma^{2}}}I_{0}\left(\frac{xv}{\sigma^{2}}\right)$,
$x\geq 0$ where $I_{0}(z)=\sum_{k=0}^{\infty}\frac{(z/2)^{2k}}{(k!)^{2}}$ is
the modified Bessel function of the first kind with order zero. Note that when
$v=0$, $Rice(v,\sigma)$ is the same as $Rayleigh(\sigma)$.

Finally, the impact of map error is

$\displaystyle\Delta_{mean}(v,\sigma)$
$\displaystyle=|Err^{val}|_{mean}-|Err^{real}|_{mean}$
$\displaystyle=Rice(v,\sigma)_{mean}-Rice(0,\sigma)_{mean}$

and similarly for $\Delta_{median}$ / $\Delta_{tail}$.

####  III-B1 $\Delta(v,\sigma)$ Approximation Function

TABLE I: Constants $\alpha$, $\beta$ for $\delta(v,1)$ approximation function and root-mean-square error on $|\Delta(v,1)-\delta(v,1)|$. | $\alpha$ | $\beta$ | $RMSE~{}|\Delta-\delta|$
---|---|---|---
Mean | 1.2392 | 2.3064 | 0.0052
Median | 1.1471 | 2.3384 | 0.0032
Tail | 0.7870 | 1.9452 | 0.0038
TABLE II: Constant $\gamma$ for $Rice(0,1)/Rayleigh(1)$. | $\gamma$
---|---
Mean | $\sqrt{\pi/2}=1.2533$
Median | $\sqrt{-2\ln{(1-0.5)}}=1.1774$
Tail | $\sqrt{-2\ln{(1-0.95)}}=2.4477$

Unlike Rayleigh distribution, the mean/quantile statistics of Rice
distribution have no closed-form expressions. This is because in general,
Bessel functions cannot be expressed as a finite algebraic combination of
elementary functions [27]. To make the analysis easier, we give an algebraic
approximation function for computing the impact $\Delta(v,\sigma)$.

We start with analysis on the mean error. By scaling a factor of $1/\sigma$,
we have

$\displaystyle\Delta(v,\sigma)$
$\displaystyle=Rice(v,\sigma)_{mean}-Rice(0,\sigma)_{mean}$
$\displaystyle=\sigma\left(Rice(v/\sigma,1)_{mean}-Rice(0,1)_{mean}\right)$
$\displaystyle=\sigma\Delta(v/\sigma,1)$ (3)

Consider the function

$\Delta(v,1)=Rice(v,1)_{mean}-Rice(0,1)_{mean}$

where $Rice(0,1)_{mean}=Rayleigh(1)_{mean}=\sqrt{\pi/2}$.

It has the following two properties:

  * •

$\Delta(0,1)=0$

  * •

$\lim_{v\to\infty}\frac{\Delta(v,1)}{v}=1$ 333As $v\to\infty$, if v increases
by 1, the norm $|X|$ of every sample $X\sim Rice(v,1)$ increases by an amount
that also converges to 1. Thus $\Delta(v,1)$ is linear in $v$ with slope 1.

We next construct an algebraic approximation function

$\delta(v,1)=(v^{\beta}+\alpha^{\beta})^{\frac{1}{\beta}}-\alpha$ (4)

with two rational number constants $\alpha>0$, $\beta>1$. Here $\alpha$ sets
the difference between $v$ and $\delta(v,1)$ as $v\to\infty$, and $\beta$
controls how $\delta(v,1)$ varies for small $v$. One can verify that
$\delta(v,1)$ has two similar properties:

  * •

$\delta(0,1)=0$

  * •

$\lim_{v\to\infty}\frac{\delta(v,1)}{v}=1$

Figure 4 shows a comparison of $\Delta(v,1)$ and its approximation
$\delta(v,1)$. The $\Delta(v,1)$ values are computed by generating the
probability density function using numerical calculations of the Bessel
function [29], and the approximation $\delta(v,1)$ values are computed from
the closed-form expression (4). The constants $\alpha$ and $\beta$ are
optimized to minimize the root-mean-square error on
$|\Delta(v,1)-\delta(v,1)|$ (see Table I).

Once we have $\delta(v,1)$, similar to (3)

$\delta(v,\sigma)=\sigma\delta(v/\sigma,1)=\sigma\left(\left((v/\sigma)^{\beta}+\alpha^{\beta}\right)^{\frac{1}{\beta}}-\alpha\right)$

####  III-B2 Numerical Algorithm for Computing the Real Error (Algorithm 2)

Algorithm 2 Compute the real error from validation error and map error. This
algorithm uses mean but can be extended to any $q$-th quantile ($0<q<1$).

0: validation error mean $u=|Err^{val}|_{mean}$, map error $v=|Err^{map}|$,
$u>v$

0: real error mean $|Err^{real}|_{mean}$

Find $\alpha,\beta$ for mean error in Table I, and $\gamma$ in Table II

Set $\sigma_{min}=(u-v)/\gamma$, $\sigma_{max}=(u-v)/(\gamma-\alpha)$

Set $\epsilon$ for convergence

while $\sigma_{max}-\sigma_{min}>\epsilon$ do

$\sigma=(\sigma_{min}+\sigma_{max})/2$

if $(u/\sigma+\alpha-\gamma)^{\beta}-(v/\sigma)^{\beta}-\alpha^{\beta}<0$ then

$\sigma_{max}=\sigma$

else

$\sigma_{min}=\sigma$

end if

end while

return $|Err^{real}|_{mean}=\sigma\gamma$

Using the $\Delta(v,\sigma)$ approximation function, we can obtain the real
error mean as follows:

Let $u=|Err^{val}|_{mean}$, $\gamma=Rice(0,1)_{mean}=\sqrt{\pi/2}$. By
definition of $\Delta_{mean}$,

$\displaystyle|Err^{val}|_{mean}$
$\displaystyle=|Err^{real}|_{mean}+\Delta(v,\sigma)$ $\displaystyle u$
$\displaystyle=\sigma\gamma+\sigma\left(\left((v/\sigma)^{\beta}+\alpha^{\beta}\right)^{\frac{1}{\beta}}-\alpha\right)$

This is equivalent to solving the equation

$f(\sigma)=(u/\sigma+\alpha-\gamma)^{\beta}-(v/\sigma)^{\beta}-\alpha^{\beta}=0$
(5)

Let $\sigma_{min}=\frac{u-v}{\gamma}$,
$\sigma_{max}=\frac{u-v}{\gamma-\alpha}$.

$\displaystyle f(\sigma_{min})$
$\displaystyle=(v/\sigma_{min}+\alpha)^{\beta}-(v/\sigma_{min})^{\beta}-\alpha^{\beta}>0$
$\displaystyle f(\sigma_{max})$ $\displaystyle=-\alpha^{\beta}<0$

and $\forall{\sigma<\sigma_{max}}$,

$f^{\prime}(\sigma)=-\beta\left((u/\sigma+\alpha-\gamma)^{\beta-1}-(v/\sigma)^{\beta-1}\right)\Big{/}{\sigma^{2}}<0$

Therefore, we can binary search on $\sigma\in(\sigma_{min},\sigma_{max})$ to
solve $f(\sigma)=0$. Finally, $|Err^{real}|_{mean}=\sigma\gamma$.

Figure 5 shows the impact of map error $\Delta(v,\sigma)$, which seems to
increase slower (comparing to marking error) until when the map error $v$ is
close to the validation error $u$. Intuitively, this can be explained as
follows: Let the real error be a zero mean Gaussian centered at the origin
$O$, and we add a map error $V=(v,0)$, where $v>0$. For any sample $X$, its
error increases $|X-V|>|X-O|$ if and only if $X$ lies on the left side of the
line $x=v/2$. Since the Gaussian has zero mean, there are more samples on the
left side of the line $x=v/2$, so the overall mean error will increase. But it
increases slowly as the changes on two sides may cancel each other, until for
sufficiently large $v$ where a significant majority of samples are on the left
side of the line $x=v/2$.

Similarly, Algorithm 2 can be applied to any $q$-th quantile ($0<q<1$). Table
I and II also list $\alpha$, $\beta$, and $\gamma$ values for the median and
95%-tail.

Note that unlike marking error, for map error, Theorem 2 only holds for the
real error $\frac{|Err^{real}|_{tail}}{|Err^{real}|_{median}}>2$, but not for
the validation error as
$\lim_{v\to\infty}\frac{|Err^{val}|_{tail}}{|Err^{val}|_{median}}=\lim_{v\to\infty}\frac{|Err^{real}|_{tail}+\Delta_{tail}(v,\sigma)}{|Err^{real}|_{median}+\Delta_{median}(v,\sigma)}=1$,
because $\lim_{v\to\infty}\frac{\Delta(v,\sigma)}{v}=1$.

Figure 5: Impact of map error $\Delta_{mean}$ as a function of
$|Err^{val}|_{mean}$ and $|Err^{map}|$. These curves are similar to Fig. 3 on
the marking error, but values are smaller.

###  III-C Comparing the Impact of Marking and Map Errors

In Section III-B, we briefly explained that the impact of map error is less
than marking error on $\Delta_{mean}$, when the map error is equal to the
marking error mean. Now we formally prove this result.

######  Theorem 3.

Given the validation error $u=|Err^{val}|_{mean}$ and the ground truth error
$v=|Err^{gt}|_{mean}$ (either marking or map error), $u>v$. Let
$\Delta_{mean}^{mark}$ be the impact of marking error when $v$ is
$|Err^{mark}|_{mean}$, and $\Delta_{mean}^{map}$ be the impact of map error
when $v$ is $|Err^{map}|$. With similar definitions on $\Delta_{median}$ /
$\Delta_{tail}$, we have

$\displaystyle\Delta_{mean}^{mark}>\Delta_{mean}^{map},~{}\forall{v/u<0.9995}$
$\displaystyle\Delta_{median}^{mark}>\Delta_{median}^{map},~{}\forall{v/u<0.9970}$
$\displaystyle\Delta_{tail}^{mark}<\Delta_{tail}^{map}$

###### Proof.

We start with $\Delta_{mean}$. From Algorithm 1,
$\Delta_{mean}^{mark}=u-\sqrt{u^{2}-v^{2}}$. From Algorithm 2,
$\Delta_{mean}^{map}=u-\sigma^{*}\gamma$ where
$\sigma^{*}\in(\sigma_{min},\sigma_{max})$ is the solution for $f(\sigma)=0$
in (5).

So $\Delta_{mean}^{mark}>\Delta_{mean}^{map}$ if and only if

$\sigma^{*}>\sqrt{u^{2}-v^{2}}\Big{/}\gamma$ (6)

Let $s=\sqrt{\frac{u+v}{2}}$, $t=\sqrt{\frac{u-v}{2}}$, $\lambda=t/s<1$.

Then $u=s^{2}+t^{2}$, $v=s^{2}-t^{2}$,
$\frac{v}{u}=\frac{1-\lambda^{2}}{1+\lambda^{2}}$.

(a) When $\lambda=\frac{t}{s}\leq\frac{\gamma-\alpha}{\gamma}$, i.e.
$\frac{v}{u}\geq\frac{1-\left(\frac{\gamma-\alpha}{\gamma}\right)^{2}}{1+\left(\frac{\gamma-\alpha}{\gamma}\right)^{2}}=0.9997$,

$\frac{\sqrt{u^{2}-v^{2}}}{\gamma}=\frac{2st}{\gamma}\geq\frac{2t^{2}}{\gamma-\alpha}=\frac{u-v}{\gamma-\alpha}=\sigma_{max}>\sigma^{*}$

In this case, $\Delta_{mean}^{mark}<\Delta_{mean}^{map}$.

(b) When $\lambda=\frac{t}{s}>\frac{\gamma-\alpha}{\gamma}$, i.e.
$\frac{v}{u}<0.9997$,

$\sqrt{u^{2}-v^{2}}\Big{/}\gamma<\sigma_{max},~{}\sigma^{*}<\sigma_{max}$

Since $\forall{\sigma<\sigma_{max}}$, $f^{\prime}(\sigma)<0$. (6) is
equivalent to

$f\left(\sqrt{u^{2}-v^{2}}\Big{/}\gamma\right)>f(\sigma^{*})=0$
$\left(\frac{u}{\frac{\sqrt{u^{2}-v^{2}}}{\gamma}}+\alpha-\gamma\right)^{\beta}-\left(\frac{v}{\frac{\sqrt{u^{2}-v^{2}}}{\gamma}}\right)^{\beta}-\alpha^{\beta}>0$

Replace $(u,v)$ by $(s,t)$,

$\left(\frac{s^{2}+t^{2}}{2st}+\frac{\alpha}{\gamma}-1\right)^{\beta}-\left(\frac{s^{2}-t^{2}}{2st}\right)^{\beta}-\left(\frac{\alpha}{\gamma}\right)^{\beta}>0$

Using $\lambda=t/s$,

$\displaystyle g(\lambda)$
$\displaystyle=\left(1+2\lambda(\alpha/\gamma-1)+\lambda^{2}\right)^{\beta}-(1-\lambda^{2})^{\beta}-(2\lambda\alpha/\gamma)^{\beta}$
$\displaystyle>0$ (7)

Figure 6 plots the algebraic function $g(\lambda)$ and its derivative
$g^{\prime}(\lambda)$ on $0\leq\lambda\leq 1$. They satisfy

$\displaystyle g(0)=0,~{}g^{\prime}(0)=2\beta(\alpha/\gamma-1)<0$
$\displaystyle
g(1-\alpha/\gamma)=-(2\alpha(\gamma-\alpha)/\gamma^{2})^{\beta}<0$
$\displaystyle g(1)=0,~{}g^{\prime}(1)=0$

From $g^{\prime}(\lambda)$, we know there exists a root $g(\lambda^{*})=0$
such that $\forall{0<\lambda<\lambda^{*}}$, $g(\lambda)<0$ and
$\forall{\lambda^{*}<\lambda<1}$, $g(\lambda)>0$. Therefore, we can binary
search $g(\lambda)=0$ for a numerical solution $\lambda^{*}=0.0160$. So in
this case, (7) holds if and only if $\lambda>\lambda^{*}$, i.e.
$v/u<\frac{1-{\lambda^{*}}^{2}}{1+{\lambda^{*}}^{2}}=0.9995$.

Combining (a) and (b), $\Delta_{mean}^{mark}>\Delta_{mean}^{map}$ if and only
if $v/u<0.9995$.

The proof for $\Delta_{median}$ is similar. $\lambda^{*}=0.0390$ and
$\Delta_{median}^{mark}>\Delta_{median}^{map}$ if and only if $v/u<0.9970$.

$\Delta_{tail}$ is different. As shown in Figure 6, $\forall{0<\lambda<1}$,
$g(\lambda)<0$. So (7) never holds and
$\Delta_{tail}^{mark}<\Delta_{tail}^{map}$. ∎

Although theoretically there are examples
$\Delta_{mean}^{mark}<\Delta_{mean}^{map}$ (e.g.
$\lambda=\frac{\gamma-\alpha}{\gamma}$). In practice, $v/u>0.99$ should never
happen (ground truth error being more than 99% of validation error). Thus, we
conclude that marking error has a larger impact on the mean and median, while
map error has a larger impact on the tail.

Figure 6: Algebraic function $g(\lambda)$ and its derivative
$g^{\prime}(\lambda)$.

###  III-D Map Error (Scale)

Besides the translation error, another type of map error is the scale error,
which can be modeled by a linear transform $\widehat{X}^{gt}=SX^{gt}+V$ where
$S=diag[s_{x},s_{y}]$ is a scaling matrix without rotation, and $V$ is a
translation vector. Then

$Err^{map}=\widehat{X}^{gt}-X^{gt}=(S-I)X^{gt}+V$

where $I$ is an identity matrix. For $S=I$, this reduces to the model we
discussed in Section III-B.

Note that in this paper, our analysis only relies on the error distribution
$Err^{gt}$. It does not require the distribution of ground truth location
$X^{gt}$ (i.e. where the data is collected). With the scale error ($S\neq I$),
the distribution of $Err^{map}$ depends on the distribution of $X^{gt}$.
Unless $X^{gt}$ also follows a normal distribution and $s_{x}=s_{y}$, we
cannot apply the same analysis in this paper. This additional distribution of
$X^{gt}$ makes the model more complicated. We leave this as a topic for future
work.

##  IV Experimental Validation

In this section, we validate the theoretical assumptions and results on a real
dataset collected in a typical environment. We start by describing the
environment and the localization technique. We then validate the error
distributions assumptions. Finally, we compare our theoretical results with
experimental results obtained directly from the real data.

###  IV-A Experimental Setup

Without loss of generality, we use a probabilistic WiFi fingerprinting
localization system in our experiments similar to [38, 39]. To collect the
necessary data for validation, we deploy the localization system in a floor in
our university campus building with a 37m x 17m area containing labs, offices,
meeting rooms as well as corridors (Figure 7). We use the already installed
WiFi infrastructure in the building, mainly four APs installed in the same
floor in addition to 12 APs overheard from other floors. We obtain the real
ground truth (without marking or map errors) based on the landmarks in the
environment such as doors and fixed access points locations. We collect the
WiFi scans by a Samsung S4 cell phone that scans for the WiFi access points at
different 24 discrete reference locations that cover the entire area of
interest uniformly.

Figure 7: Indoor testbed used for experimental validation.

###  IV-B Validating Error Distributions Assumptions

####  IV-B1 Marking Error

We start by getting the marking error distribution by comparing the marked
ground truth locations, which are obtained by clicking on the map, with the
real ground truth locations from the floor landmarks. Our results show that
the error in X follows a normal distribution with $\mu=-0.04$ and
$\sigma=0.16$, i.e. $\mathcal{N}(-0.04,0.16^{2})$, while the error in Y
follows a normal distribution $\mathcal{N}(-0.03,0.09^{2})$. The mean values
in both distributions are small around zero which matches our theoretical
assumptions that the marking errors in X and Y follow normal distributions
with mean zero. The quantile-quantile plot in Figure 8 shows that the marking
error norm fits a Rayleigh distribution with $\sigma=0.14$ very well. This
also matches our theoretical analysis.

####  IV-B2 Validation Error

The validation error distribution is obtained by comparing the system
estimated location with the marked (not real) ground truth locations. Our
results show that the error in X follows a normal distribution
$\mathcal{N}(0.84,3.86^{2})$, while the error in Y follows a normal
distribution $\mathcal{N}(0.41,1.54^{2})$. In our analysis, we assume that the
error distributions in X and Y are identical. However, in our experiments, the
validation error in X direction is higher than in Y direction. This is due to
the geometry of the building (e.g. the building width is larger than its
height, leading to more errors in the X direction), making the validation
error norm possibly deviate from the Rayleigh distribution.

Figure 9 shows the validation error norm distribution and its best fit using a
Rayleigh distribution with $\sigma=2.81$. Since in our experiments the error
distributions in X and Y are not identical, Rayleigh distribution does not
lead to the best fit and other distributions, e.g. the exponential
distribution in Figure 9(c), could be a better choice. Nonetheless, Rayleigh
distribution still fits most percentiles, except for very large tail errors.

(a) Marking error distribution.

(b) Rayleigh distribution test.

Figure 8: Marking error norm distribution with Q-Q plot vs. Rayleigh
distribution.

(a) Validation error distribution.

(b) Rayleigh distribution test.

(c) Exponential distribution test.

Figure 9: Validation error norm distribution with Q-Q plot vs. Rayleigh and
exponential distributions. The figures for real error norm distribution are
similar.

####  IV-B3 Real Error

The real error distribution is obtained by comparing the system estimated
location with the real ground truth locations in the collected dataset
(obtained based on the landmarks in the environment). Similar to the
validation error, the real error distributions in X and Y follow normal
distributions $\mathcal{N}(0.80,3.89^{2})$ and $\mathcal{N}(0.39,1.53^{2})$,
respectively. The real error norm also fits a Rayleigh distribution with
$\sigma=2.78$ except at the tail. Similarly, this is due to the error
distributions in X and Y being not identical.

####  IV-B4 Validation Map Error

To get the validation map error distribution, we shift the real ground truth
locations in the evaluation dataset in X and Y directions, simulating offset
errors in the provided map. Figure 10 shows the validation error norm
distribution after shifting the map by 3m in both X and Y directions. The
validation error norm fits the Rice distribution with $v=4.65$ and
$\sigma=3.29$ better than other distributions most of the time, except at the
tail (asymmetric X/Y distribution). Note that when the map error exists,
although the exponential distribution gives larger tail errors, it does not
perform well at the lower percentiles.

(a) Validation error distribution.

(b) Rice distribution test.

(c) Exponential distribution test.

Figure 10: Validation error norm distribution after shifting the map by 3m in
both X and Y directions with Q-Q plot vs. Rice and exponential distributions.

###  IV-C Theoretical vs Experimental Real Error

####  IV-C1 Marking Error

Figure 11 presents a CDF comparison between the theoretical and experimental
real errors. The theoretical real error is obtained from the marking and
validation errors by applying Algorithm 1. The experimental real error is
obtained directly from the data. The figure shows that the theoretical real
error matches the experimental one within 4% in all percentiles. Table III
further shows the summary statistics of the results.

On Theorem 2, the ratio of the validation error tail to the median is
$\frac{8.05}{2.47}=3.26$, and the ratio of the validation error tail to the
mean is $\frac{8.05}{3.41}=2.36$. Similarly, the ratio of the real error tail
to the median is $\frac{7.99}{2.37}=3.37$ and the ratio of the real error tail
to the mean is $\frac{7.99}{3.39}=2.36$. These show that in practice, the
95%-tail error is more than twice of the median/mean errors. Again, these
higher ratios are because of the larger tail errors from asymmetric X/Y
distribution.

Figure 11: A comparison between experimental and theoretical real error norm
CDFs (from Algorithm 1).

####  IV-C2 Map Error

To study the effect of applying Algorithm 2 on the localization accuracy, we
shift the real ground truth locations with different values from 1m to 6m in X
and Y directions, simulating offset errors in the provided map. Figure 12
compares the validation error norm, theoretical real error norm, and
experimental real error norm for the different map shift values. The
validation error is obtained by comparing the system estimated location with
the shifted ground truth locations in the collected dataset. Hence, it
increases with the increase of the map shift. The experimental real error is
obtained by comparing the system estimated location with the real ground truth
locations in the collected dataset. Finally, the theoretical real error is
obtained from Algorithm 2 given the map shift value and the validation error
statistics.

The figure shows that the calculated theoretical real error is closer to the
experimental real error than the validation error norm which is typically used
to evaluate the localization algorithms. In particular, Algorithm 2 does
provide a more accurate estimate of the median and tail localization error by
more than 20% and 5%, respectively, when the map is shifted by 1m in X and Y
directions. This enhancement increases to 150% and 72%, respectively, when the
map is shifted by 6m. Therefore, this algorithm can be used to obtain a more
realistic quantification of the localization system error.

TABLE III: Summary statistics for the different error metrics. The experimental results are calculated directly from the data while the theoretical real error is calculated from Algorithm 1. Metric | Marking error | Real error | Real error
---|---|---|---
Type | Experimental | Experimental | Theoretical
Mean | 0.17 | 3.39 |  3.40 (0.3%)
0.25 Q | 0.11 | 2.00 |  2.02 (1.0%)
Median | 0.15 | 2.37 |  2.46 (3.8%)
0.75 Q | 0.24 | 3.60 |  3.70 (2.8%)
0.95 Q | 0.30 | 7.99 |  8.04 (0.6%)

(a) Mean.

(b) Median.

(c) Tail.

Figure 12: A comparison between the validation error norm, theoretical real
error norm (from Algorithm 2), and experimental real error norm for the
different map shift values.

##  V Related Work

In this section, we present a brief overview of the previous work on
evaluating the accuracy of localization systems that is most relevant.

###  V-A AP Density Analysis

In literature, there are studies that focus on the effect of access points
(APs) number and position on the localization accuracy [17, 34]. In [17], the
authors proposed the theoretical error analysis for WiFi-based localization.
It is shown that the Cramer-Rao lower bound (CRLB) [33, 35] is inversely
proportional to the number of the RSS measurements available from APs. They
show that it is not necessary to leverage all the available APs to achieve the
best accuracy. In [34], authors proposed an algorithm that searches for the
optimal APs and beacons placement that maximizes the localization accuracy.
They tackle the problem of optimizing AP and beacon placement, which is NP-
Complete, by proposing a heuristic differential evolution algorithm based on
the widely used CRLB.

On the other hand, in this work, our goal is different: to get the real error
statistics from the marking and map errors. Moreover, unlike these studies,
which are limited to APs-based localization systems, our analysis is general
for any localization system.

###  V-B Error Bounds Analysis

Another set of studies put bounds on the localization error. Examples include
time-of-arrival [24], time-difference-of-arrival [7], angle-of-arrival [7],
and the RSS fingerprinting [4, 37, 23]. The CRLB is widely used in these
studies to put a bound on localization error [4, 24, 14]. In [4], authors
studied the CRLB for anchored and anchor-free localization using noisy range
measurements. They gave a method to compute the CRLB in terms of the geometry
of the sensor network. In [24], the authors investigate the improvement in
positioning accuracy if all multipath delays are processed (instead of using
the first path). The authors show that using the first arrival only is
sufficient for optimal localization when there is no prior information about
the non-line-of-sight delays. When such prior information is available, the
multipath delays can improve the localization accuracy. The best achievable
accuracy is evaluated in terms of CRLB and the generalized-CRLB. In [14], the
authors analyze the CRLB of localization using signal strength difference as
location fingerprint.

In contrast, our target is not to put a bound on the localization error only,
but to establish bounds on different metrics between the localization error
and ground truth errors.

###  V-C Localization Confidence Estimation

Recently, different confidence estimation techniques are proposed for
different localization systems. Examples include GPS [8, 20], GNSS [21] and
indoor localization techniques such as [19, 20, 6]. Confidence estimation for
the GPS is typically derived from the geometric dilution of precision which
measures the confidence as a function of error caused by the geometry of the
GPS satellites [8, 20, 21, 6]. Authors of [8, 21] further analyze the error
characteristics of GPS and GNSS localization systems and derive an error model
to estimate the localization error based on a combination of the number of
satellites, dilution of precision, received signal strength and receiver
speed. In [6], authors maintain a database of locations and their
corresponding error measurement to estimate the localization accuracy. In
[21], authors proposed a technique that identifies the dominant noise types
and builds an error source model to estimate the GNSS positioning error based
on the Allen variance method [9]. In [10], authors estimate the indoor
localization confidence by assuming that the error in user location follows a
Gaussian distribution. They proposed a system that can work in real-time to
get the confidence in the estimated location from the history of the previous
estimated locations.

In comparison to these systems, which do not consider the marking and map
errors, we provide a general framework to handle both kinds of ground truth
errors.

##  VI Conclusions

In this paper, we presented a theoretical framework for analyzing the effect
of ground truth errors on the evaluation of localization systems. We designed
two algorithms for computing the real algorithmic error from the validation
error and marking/map ground truth errors, respectively. We showed that the
impact of marking error is quadratic in its ground truth error, and inversely
proportional to validation error. We further established bounds on different
performance metrics: that the 95%-tail error is at least twice of the
median/mean errors and proved that marking error has more impact than map
error on the mean and median, but less impact on the tail.

We validated our theoretical assumptions and analysis on a real indoor WiFi
dataset. Our experiments show the ability of our analysis to obtain a more
realistic localization error in the presence of ground truth errors.
Specifically, we showed that Algorithm 1 matches the real error within 4% in
all percentiles, and Algorithm 2 provides a more accurate estimate of the
median and tail errors by more than 150% and 72%, respectively, when the map
is shifted by 6m.

For future work, we are extending our analysis to address map scale errors and
modifying the model to handle asymmetric X/Y error distributions.

## Acknowledgment

The authors wish to thank Patrick Robertson for proposing the initial
questions to be considered in this paper.

## References

  * [1] M. Abbas, M. Elhamshary, H. Rizk, M. Torki, and M. Youssef.  WiDeep: WiFi-based accurate and robust indoor localization system using deep learning.  In IEEE International Conference on Pervasive Computing and Communications, 2019.
  * [2] H. Aly, A. Basalamah, and M. Youssef.  Accurate and energy-efficient GPS-less outdoor localization.  ACM Transactions on Spatial Algorithms and Systems, 3(2):1–31, 2017\.
  * [3] H. Aly and M. Youssef.  Dejavu: an accurate energy-efficient outdoor localization system.  In ACM International Conference on Advances in Geographic Information Systems, 2013.
  * [4] C. Chang and A. Sahai.  Estimation bounds for localization.  In IEEE Conference on Sensor and Ad Hoc Communications and Networks, 2004.
  * [5] P. Cherntanomwong, J.-i. Takada, and H. Tsuji.  Signal subspace interpolation from discrete measurement samples in constructing a database for location fingerprint technique.  IEICE Transactions on Communications, 92(9):2922–2930, 2009.
  * [6] D. Dearman, A. Varshavsky, E. De Lara, and K. N. Truong.  An exploration of location error estimation.  In International Conference on Ubiquitous Computing. Springer, 2007\.
  * [7] A. Dersan and Y. Tanik.  Passive radar localization by time difference of arrival.  In IEEE Military Communications Conference, 2002.
  * [8] N. M. Drawil, H. M. Amar, and O. A. Basir.  GPS localization accuracy classification: A context-based approach.  IEEE Transactions on Intelligent Transportation Systems, 14(1):262–273, 2012.
  * [9] N. El-Sheimy, H. Hou, and X. Niu.  Analysis and modeling of inertial sensors using Allan variance.  IEEE Transactions on Instrumentation and Measurement, 57(1):140–149, 2007.
  * [10] R. Elbakly and M. Youssef.  Cone: Zero-calibration accurate confidence estimation for indoor localization systems.  ArXiv preprint arXiv:1610.02274, 2016.
  * [11] R. Elbakly and M. Youssef.  Crescendo: An infrastructure-free ubiquitous cellular network-based localization system.  In IEEE Wireless Communications and Networking Conference, 2019\.
  * [12] J. Gjengset, J. Xiong, G. McPhillips, and K. Jamieson.  Phaser: Enabling phased array signal processing on commodity WiFi access points.  In International Conference on Mobile Computing and Networking, 2014\.
  * [13] J. Hightower and G. Borriello.  Location systems for ubiquitous computing.  Computer, 34(8):57–66, 2001.
  * [14] A. M. Hossain and W.-S. Soh.  Cramer-Rao bound analysis of localization using signal strength difference as location fingerprint.  In IEEE International Conference on Computer Communications, 2010\.
  * [15] M. Ibrahim and M. Youssef.  CellSense: An accurate energy-efficient GSM positioning system.  IEEE Transactions on Vehicular Technology, 61(1):286–296, 2011\.
  * [16] M. Ibrahim and M. Youssef.  Enabling wide deployment of GSM localization over heterogeneous phones.  In IEEE International Conference on Communications, 2013.
  * [17] B. Jia, B. Huang, H. Gao, W. Li, and L. Hao.  Selecting critical WiFi APs for indoor localization based on a theoretical error analysis.  IEEE Access, 7:36312–36321, 2019.
  * [18] M. Kotaru, K. Joshi, D. Bharadia, and S. Katti.  Spotfi: Decimeter level localization using wifi.  In ACM Conference on Special Interest Group on Data Communication, 2015.
  * [19] H. Lemelson, M. B. Kjærgaard, R. Hansen, and T. King.  Error estimation for indoor 802.11 location fingerprinting.  In International Symposium on Location-and Context-Awareness. Springer, 2009.
  * [20] V. Moghtadaiee, A. G. Dempster, and B. Li.  Accuracy indicator for fingerprinting localization systems.  In IEEE/ION Position, Location and Navigation Symposium, 2012.
  * [21] X. Niu, Q. Chen, Q. Zhang, H. Zhang, J. Niu, K. Chen, C. Shi, and J. Liu.  Using Allan variance to analyze the error characteristics of GNSS positioning.  GPS Solutions, 18(2):231–242, 2014.
  * [22] J. Paek, K.-H. Kim, J. P. Singh, and R. Govindan.  Energy-efficient positioning for smartphones using cell-id sequence matching.  In International Conference on Mobile Systems, Applications, and Services, 2011.
  * [23] N. Patwari and A. O. Hero.  Location estimation accuracy in wireless sensor networks.  In IEEE Asilomar Conference on Signals, Systems and Computers, 2002\.
  * [24] Y. Qi, H. Kobayashi, and H. Suda.  On time-of-arrival positioning in a multipath environment.  IEEE Transactions on Vehicular Technology, 55(5):1516–1526, 2006\.
  * [25] L. Rayleigh.  On the resultant of a large number of vibrations of the same pitch and of arbitrary phase.  The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 10(60):73–78, 1880.
  * [26] S. O. Rice.  Mathematical analysis of random noise.  The Bell System Technical Journal, 23(3):282–332, 1944.
  * [27] P. D. Ritger and N. J. Rose.  Differential Equations with Applications.  McGraw-Hill, New York, 1968.
  * [28] H. Rizk, A. Shokry, and M. Youssef.  Effectiveness of data augmentation in cellular-based localization using deep learning.  In IEEE Wireless Communications and Networking Conference, 2019\.
  * [29] C. Schwartz.  Numerical calculation of Bessel functions.  International Journal of Modern Physics C, 23(12):1250084, 2012\.
  * [30] A. Shokry, M. Elhamshary, and M. Youssef.  The tale of two localization technologies: Enabling accurate low-overhead WiFi-based localization for low-end phones.  In ACM International Conference on Advances in Geographic Information Systems, 2017.
  * [31] A. Shokry, M. M. Elhamshary, and M. Youssef.  DynamicSLAM: Leveraging human anchors for ubiquitous low-overhead indoor localization.  IEEE Transactions on Mobile Computing, 2020.
  * [32] A. Shokry, M. Torki, and M. Youssef.  DeepLoc: A ubiquitous accurate and low-overhead outdoor cellular localization system.  In ACM International Conference on Advances in Geographic Information Systems, 2018.
  * [33] S. T. Smith.  Intrinsic Cramér-Rao bounds and subspace estimation accuracy.  In IEEE Sensor Array and Multichannel Signal Processing Workshop, 2000.
  * [34] Y. Tian, B. Huang, B. Jia, and L. Zhao.  Optimizing AP and Beacon placement in WiFi and BLE hybrid localization.  Journal of Network and Computer Applications, page 102673, 2020\.
  * [35] H. L. Van Trees.  Optimum array processing: Part IV of detection, estimation, and modulation theory.  John Wiley & Sons, 2004.
  * [36] D. Vasisht, S. Kumar, and D. Katabi.  Decimeter-level localization with a single WiFi access point.  In USENIX Symposium on Networked Systems Design and Implementation, 2016.
  * [37] S. Venkatesh and R. M. Buehrer.  Multiple-access insights from bounds on sensor localization.  Pervasive and Mobile Computing, 4(1):33–61, 2008.
  * [38] M. Youssef and A. Agrawala.  The Horus WLAN location determination system.  In International Conference on Mobile Systems, Applications, and Services, 2005.
  * [39] M. A. Youssef, A. Agrawala, and A. U. Shankar.  WLAN location determination via clustering and probability distributions.  In IEEE International Conference on Pervasive Computing and Communications, 2003.
  * [40] J. H. Zar.  Biostatistical analysis (5th Edition).  Prentice Hall, 2007.