Spinal Codes


July 18, 2014


Kyle Jamieson


University College London


Spinal codes ?(ACM SIGCOMM 2012) ?are a new class of rateless codes that enable wireless ?networks to cope with time-varying channel conditions in a natural way, without requiring any explicit bit rate selection. The key idea in the code is the sequential application of a pseudo-random hash function to the message bits to produce a sequence of coded symbols for transmission.

This encoding ensures that two input messages that differ in even one bit lead to very different coded sequences after the point at which they differ, providing good resilience to noise and bit errors. To decode spinal codes, this paper develops an ap- proximate maximum-likelihood decoder, called the bubble decoder, which runs in time polynomial in the message size and achieves the Shannon capacity over both additive white Gaussian noise (AWGN) and binary symmetric channel (BSC) models. Experimental results obtained from a software implementation of a linear-time decoder show that spinal codes achieve higher throughput than fixed-rate LDPC codes, rateless Raptor codes, and the layered rateless coding approach of Strider, across a range of channel conditions and message sizes.


Kyle Jamieson

Kyle Jamieson is a Senior Lecturer (tenure-track Assoc. Prof.) in the Department of Computer Science at University College London, and Principal Investigator on the European Research Council-funded CHAOSNETS and SmartTap projects. His research interests are in building real-world wirelessly networked systems that cut across the boundary of digital communications and networking. He has published well-cited works including the ArrayTrack indoor location system (NSDI ’13), the Collection Tree Protocol (SenSys ’09), and the SoftRate wireless bit rate adaptation protocol (SIGCOMM ’09). He serves on program committees including ACM MobiCom, USENIX NSDI, and ACM SIGCOMM. He received the PhD in Computer Science in 2008 from the Massachusetts Institute of Technology.