Spinal Codes

Worldwide demand for wireless network access is increasing at a tremendous pace. To cope with this demand and provide high throughput and low latency to applications, wireless network protocols need to combat noise, interference from other nodes as well as exogenous sources, and channel fading. These factors cause wireless channel conditions to vary with time, making it challenging to achieve high performance.

A good, perhaps even ideal, solution to this problem -- and an attractive architecture for practical wireless networks -- is to make communication links rateless. In a rateless network, the sender encodes data without any explicit estimation or adaptation, implicitly adapting to the vagaries introduced by noise, interference, or fading. The receiver processes data (symbols or bits) as it arrives, decoding it, until the message is received successfully. If the code is good, then the network can perform well without incurring the complexities and challenges of implementing multiple fixed-rate codes and picking between them, implementing several bits to symbols mappings and picking a suitable one, and last but not least, estimating channel quality and picking well even in face of imperfect and delayed estimates.

Spinal codes are a new family of rateless codes. They apply a random hash function over the message bits to produce pseudo-random bits, which in turn can (optionally) be mapped directly to a dense Gaussian or uniform constellation for transmission. Spinal codes can be decoded effi- ciently. Spinal decoding using a polynomial-time decoder provably achieve Shannon capacity over both additive white Gaussian noise (AWGN) channels and binary symmetric channels (BSC) in a rateless manner. The hardware implementation (FPGA prototype) that we have built decodes at 10Mbps. The software and hardware implementations of spinal codes with several experimental re- sults show that they outperform the state-of-art competing code design. Methodically, spinal codes is an approach to de-randomize and render practical Shannon’s random codebook construction from the 1940s.