New construction of a near-optimal partial Fourier codebook using the structure of binary m-sequences

A codebook, or equivalently a frame, has many applications in communications, signal processing, and quantum computing. In the applications, it is required that the maximum magnitude of inner products between a pair of distinct code vectors should meet the Welch bound equality strictly or asymptotically. In this paper, a new (N, K) codebook is constructed from a K×N partial Fourier matrix with N = K² -1 and K=2^k for a positive integer k, where each code vector is equivalent to a column of the matrix. To obtain the K×N partial Fourier matrix, K rows are selected from the N ×N inverse discrete Fourier transform matrix, where a set of the selected row indices is determined from the structure of binary m-sequences of period N. Through a theoretical study, it is found that the magnitude of inner products between distinct code vectors is two-valued, and its maximum nearly achieves the Welch bound equality. The new near-optimal codebook, equivalent to a nearly equiangular tight frame, can find its potential applications in deterministic compressed sensing.