Low-Complexity Grassmannian Quantization Based on Binary Chirps

We consider autocorrelation-based low-complexity decoders for identifying Binary Chirp codewords from noisy signals in N = 2^m dimensions. The underlying algebraic structure enables dimensionality reduction from N complex to m binary di- mensions, which can be used to reduce decoding complexity, when decoding is successively performed in the m binary dimensions. Existing low-complexity decoders suffer from poor performance in scenarios with strong noise. This is problematic especially in a vector quantization scenario, where quantization noise power cannot be controlled in the system. We construct two improvements to existing algorithms; a geometrically inspired algorithm based on successive projections, and an algorithm based on adaptive decoding order selection. When combined with a breadth-first list decoder, these algorithms make it possible to approach the performance of exhaustive search with low complexity.

I. Introduction

Subspaces of unit norm complex valued vectors modulo overall phase rotations are of interest in many information processing tasks, ranging from non-coherent wireless communication [1], [2], [3] and activity detection [4] to vector quantization of Channel State Information (CSI) [5], [6], [7], [8] and deep learning [9], while also being the fundamental objects of interest in finite dimensional quantum mechanics [10]. For communication [2], [3], quantization [5], [7], [8] and quantum coding [11] scenarios, codebook based approaches are essential.