Performance Analysis of Binary Chirp Decoding

Binary Chirp (BC) codebooks consist of ${N^{\left( {{{\log }_2}N + 3} \right)/2}}$ lines in ${\mathbb{C}^N}$, equivalent up to overall phase rotations. Exploiting the underlying algebraic structure, the BCs allow suboptimal decoders with complexity N(logN)², based on autocorrelations between the received signal and its permuted versions. We analyze the performance of these decoders in additive white Gaussian noise channels, providing lower bounds of decoding error probability, which are tight in the limits of low and high signal-to-noise ratio. Due to the autocorrelation nature of the receiver, the error probability becomes a function of order statistics of χ²-distributed random variables. Our results can be used when dimensioning communication systems where BCs are used as component codes.

I. Introduction

CODEBOOKS of binary chirps (BCs) are highly structured Grassmannian line codebooks with high cardinality, and are invariant with respect to absolute phase and amplitude [1]. BCs represent subspaces of unit norm complex projective lines which have many desirable algebraic and geometrical features and are of interest in many applications in communication and information processing, e.g., compressed sensing [2]–[5], network coding [6], [7], random access [8], [9], Grassmannian quantization [10], etc. Also, the BCs are stabilizer states in the quantum computing [10]. Codebooks of BCs can be understood as exponentiated 2nd-order Reed-Muller codebooks, constructed based on m binary objects in m dimensions [1], [5], with the resulting codebooks having elements in N = 2^m-dimensional complex space.