Reliable, Spectrally Efficient Communication via Sparse Hadamard Codes

Lead Research Organisation: University of Cambridge
Department Name: Engineering


Modern wireless networks are constantly growing in size, speed and sophistication. These networks will have huge demands will be placed on them in the coming years due to bandwidth-hungry applications such as mobile video and machine-to-machine communication (e.g., data transmitted by sensors and wearable devices). To support the rapid growth in traffic, there is a pressing need to develop communication schemes that are both reliable and spectrally efficient, i.e., deliver the maximum data rate per unit bandwidth. Further, it is essential that these schemes have low computational complexity so that they can be easily implemented in hardware.

This project addresses the problem of constructing fast, reliable, spectrally-efficient schemes for communication channels with Gaussian noise. The Gaussian channel is widely used to model both wireless and wired communication links. We propose to design coding schemes for this channel using the framework of sparse linear regression. We call these codes Sparse Hadamard Codes since each sequence of data bits is mapped to a codeword (a long vector) constructed from a Hadamard design matrix.

We will first develop a fast message-passing decoder for these codes whose complexity and memory requirement grows slowly with the code length. A software implementation of the decoder will be used to compare the performance of sparse Hadamard codes with state-of-the-art coding schemes for the Gaussian channel. We will provide rigorous theoretical guarantees on the performance of the decoder, and show that it (asymptotically) achieves the maximum spectral efficiency for a Gaussian channel. The codes will also be extended to multi-user scenarios in which there are multiple transmitters or receivers (Such channels are used to model wireless networks). In the final phase of the project, will develop GPU and FPGA implementations of the sparse Hadamard decoder.

In summary, the project will develop a suite of fast communication schemes for the Gaussian channel that optimally utilise scarce network resources such as radio spectrum and power to reliably deliver near-optimal data rates.

The novel algorithms developed in the project are also relevant to applications beyond communications. One such example is compressed sensing MRI, where the goal is to reconstruct an image from a small number of MRI measurements. The small number of measurements (compared to a typical MRI scan) reduces the time a patient has to spend inside the scanner. The message passing algorithms developed in this project can be applied to this setting to recover the MRI image. It can also be readily adapted to other compressed sensing settings where are measurements are made via Fourier/Hadamard matrices. Such applications will be explored towards the end of the project.

Planned Impact

Wireless communication is a technology that is rapidly transforming many parts of our society and economy including healthcare, infrastructure, and entertainment. Fast, spectrally-efficient coding schemes will play a key role in realising the promise of wireless technology in all these sectors. A key motivation of this project is to develop easily implementable coding schemes that are clearly superior to those currently used in industry, offering significantly higher data rates for a given amount of spectrum. We aim to make our coding schemes an attractive option for next generation standards such as 5G. With the help of Cambridge Enterprise, we will explore technology transfer and commercialisation opportunities for the codes developed in this project.

Beyond the goal of fast and reliable communication, the novel message passing algorithms developed in this project can also be used in compressed sensing. Compressed sensing is a signal acquisition and recovery framework that has had a big societal impact through several biomedical and engineering applications including MRI, microscopy, spectroscopy, and computer vision. For example, compressed sensing MRI uses a lot fewer measurements than a typical MRI scan, which translates to the patient spends significantly less time inside the scanner. The approximate message passing algorithms developed in this project can be used to recover the image from compressed sensing MRI measurements. The algorithms can also be applied to other compressed sensing set-ups such as microscopy where Fourier/Hadamard measurement matrices are used.

The UK needs highly-skilled engineers and innovative researchers to fully exploit the potential of emerging wireless and information processing technologies. The project will help provide valuable training for the postdoctoral researcher, helping build a range of theoretical and algorithm design skills that can be applied in several different fields including signal processing, statistics, and machine learning. The project will thus serve as a launchpad for a strong career in academic or industrial research.


10 25 50
publication icon
Greig A (2018) Techniques for Improving the Finite Length Performance of Sparse Superposition Codes in IEEE Transactions on Communications

publication icon
Pavan Srinath K (2019) Empirical Bayes estimators for high-dimensional sparse vectors in Information and Inference: A Journal of the IMA

publication icon
Rush C (2018) Finite Sample Analysis of Approximate Message Passing Algorithms in IEEE Transactions on Information Theory

publication icon
Srinath K (2018) Cluster-Seeking James-Stein Estimators in IEEE Transactions on Information Theory

Description "Sparse superposition codes" are a promising class of codes for communication over noisy channels. These codes had been shown to be theoretically optimal ("capacity-achieving") in the limit of large block lengths. In this research, we investigated their performance under the realistic (practical) assumption of finite block length. We first designed and implemented a low-complexity decoder for these codes. Using this, we showed that they were competitive with other state-of-the-art coded modulation techniques. We proposed a number of ways to optimize the performance of these codes: these include novel power allocation algorithms, guidelines to optimally choose the code parameters, and techniques to speed up implementation.
Exploitation Route This research makes sparse superposition codes attractive for wireless and optical communication systems. Other research groups from academia and industry have already developed hardware implementations of these codes based on our results and the techniques we proposed.
Sectors Digital/Communication/Information Technologies (including Software)

Description Isaac Newton Trust Research Award
Amount £34,284 (GBP)
Organisation University of Cambridge 
Department Isaac Newton Trust
Sector Academic/University
Country United Kingdom
Start 08/2017 
End 06/2018
Description Collaboration with Dr Cynthia Rush at Columbia University 
Organisation Columbia University
Department Department of Statistics
Country United States 
Sector Academic/University 
PI Contribution This has been an ongoing collaboration with Dr Cynthia Rush on AMP-decoded sparse regression codes. In the most recent work, submitted to the IEEE International Symposium on Information Theory, Dr Ramji Venkataramanan defined the research problem (error exponents of AMP-decoded sparse regression codes), obtained preliminary results and helped write the paper .
Collaborator Contribution Dr Cynthia Rush from Columbia University developed some of the techniques used to derive the error exponents of AMP-decoded sparse regression codes.
Impact C. Rush, A. Greig, and R. Venkataramanan, "Capacity-achieving Sparse Superposition Codes with Approximate Message Passing Decoding", IEEE Transactions on Information Theory, vol. 63, no. 3, pp. 1476-1500, March 2017. C. Rush, and R. Venkataramanan, "Finite Sample Analysis of Approximate Message Passing", Proc. IEEE Int. Symp. on Information Theory (ISIT), 2016. C. Rush, and R. Venkataramanan, "Error Exponent of Sparse Regression Codes with AMP decoding", submitted to IEEE Int. Symp. on Information Theory (ISIT), 2017.
Start Year 2014