A low complexity cross-correlation interference mitigation technique for GNSS

The finite length Gold codes used in satellite navigation systems limit their dynamic range, resulting in the introduction of unwanted peaks that can mask out signals of interest. In this paper, a novel cross-correlation interference mitigation technique dealing with this issue is introduced. A brief overview of the multiple access interference problem inherent in satellite navigation systems using the code division multiple access technique is followed by the details of the proposed method. Simulation case studies and analyses of the results detailing weak signal scenarios, carried out entirely using the Global Navigation System Scope, are presented. A comparison of the results is given in the conclusions section along with remarks on the performance of the proposed method and future work to be carried out.

Preconditioning 2D Integer Data for Fast Convex Hull Computations

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.