How polar codes work

Polar codes break the wheel somewhat in the field of channel coding with an unorthodox approach that resembles some of the operations more conventionally seen in the standard communication chains between the baseband and radio front ends.

5g wireless mobile data connection
Thinkstock

One of the biggest surprises in 5G standardization so far has been the acceptance of polar codes as an official channel coding technology. Such decisions are of course complex ones that are often as much about political persuasion as technology virtue. Regardless, the feat achieved by this relatively nascent technology is remarkable. It was only a short time ago that the popular belief was that turbo codes would never be eclipsed. So, what makes polar codes different and how do they work?

The basics of channel coding

Polar codes are a channel coding technology and all channel coding technology works in basically a quite similar way. Communication links are susceptible to errors due to random noise, interference, device impairments, etc. that corrupt the original data stream at the receiving end. Channel coding basically employs a set of algorithmic operations on the original data stream at the transmitter, and another set of operations on the received data stream at the receiver to correct these errors. In channel coding terminology, the entirety of these operations at the transmitter and receiver are respectively denoted as encoding and decoding operations. The focus of channel coding research may be stated quite simply: develop high performance channel codes that mitigate the effect of the errors in a communication link (bit-error-rate is the common performance measure used here). However, the real challenge here is doing this in a manner of sufficiently low complexity that allows practical implementation into the silicon technology of the day. The complexity of a code determines everything, e.g. how much power it consumes, how much memory it needs, how much computation power it requires, and how much latency it incurs, all of which at the end of the day determine whether a code is good for any particular use case.

Channel coding methods broadly fall under two classes: block codes and convolutional codes. Block codes work on a block of data/bits with fixed size and apply the manipulation to this block at the transmitter and receiver. Reed-Solomon codes, commonly used on the hard disks of computers, are one example of this type of code. Convolutional codes, on the other hand, work on streams of data with more arbitrary numbers of data/bits. These codes apply a sliding window method that provides a substantial decoding benefit. Simple Viterbi codes are an example of this type of code.

As you might suspect, considerable productive research has been done over the years into the concatenation of block and convolutional codes to combine the benefits of both. For example, the RSV code, which was the best performing code until turbo codes, was a hybrid of the Reed-Solomon code, which is a block code, with a Viterbi convolutional code.      

So how do turbo codes work

Turbo coding is an example of a concatenated code technique. The performance gains compared to other such codes are shockingly huge. They were the first set of codes to approach the Shannon capacity limit with a relatively moderate level of complexity. Turbo codes combine two convolutional type encoders, two serial decoders and an interleaver. Turbo codes get their name from the novel feedback loop they employ that, conceptually, at least resembles the same mechanism by which turbo exhaust systems work in cars. The real innovation in turbo codes lies in the smarts surrounding how soft information is used. Prior systems required hard knowledge about the bits (e.g. 0’s or 1’s) being received. However, turbo codes only require a probabilistic measure of each bit to be decoded correctly. This basically allows a lot more data to be successfully conveyed over turbo coded channels.     

How are polar codes different?

Polar codes break the wheel somewhat in the field of channel coding. Polar codes operate on blocks of symbols/bits and are therefore technically members of the block code family. The construction of these codes follow a very unorthodox approach compared to more traditional approaches like turbo codes. In many ways, the methods resemble some of the operations that are mostly used in standard communication chains between the baseband and radio ends, primarily the family of Fast Fourier Transform (FFT) like techniques that anybody with a communications or signal processing background will be quite familiar with.

The transformation involves two key operations called channel combining and channel splitting. The channel combining process reminds me of the bit manipulations and sub-block mapping in OFDM waveform configuration, as is used in conventional radio modulation schemes. That is, at the encoder, channel combining initially assigns/maps carefully curated combinations of bits/symbols to specific channels (e.g. as in sub-blocks in an OFDM symbol).

The channel splitting that follows performs an implicit transformation operation (analogous to frequency domain to time domain as performed by an IFFT operation), translating these bit/symbol combinations into decoder-ready, time domain vectors. The decoding operation at the receiver, in symmetry with the encoding, tries to estimate these time domain bit streams by using a conventional successive-cancellation decoding technique, analogous to spectral domain estimation.

The real magic in polar codes lies in the clever bit manipulations and mappings to the channels at the encoder. The original technique, in combination with channel splitting, and successive-cancellation decoding, is shown to essentially convert a block of bits, and their associated channels between the encoder and decoder, into a polarized bit stream at the receiver. That is a received bit and its associated channel ends up being either a “good channel” or “bad channel” pole/category. It has been mathematically proven that as the size of the bit block increases, the received bit stream polarizes in a way that the number of “good channels” approaches Shannon capacity. This phenomenon is what gives polar codes their name and makes them the first and only explicitly proven capacity-achieving practical channel codes ever conceived.    

The astonishing characteristic of this coding technique is that the implementation complexity, especially the decoding part, is considerably less when compared to existing turbo codes. Moreover, polar codes and their emerging array of variants and hybrids are shown to out-perform turbo codes in terms of error-correction performance in a wide range of use-cases. The better error-correction performance along with lower implementation and operation complexities make polar codes a genuine step up on turbo code technology.  

What is next for this technology?

Polar codes have so far replaced turbo codes in 5G eMBB (enhanced Mobile Broadband) control channels and on the physical broadcast channel. While these channels typically only operate at low data rates, the reduced complexity of polar codes has made them a more attractive choice than turbo codes. Two more uses are still to be addressed in 5G: URLLC (ultra-reliable low latency communications) and MMTC (massive machine-type communications). These use cases, particularly URLLC, have comparable data rate requirements to control channels. The excellent error-correction capability of polar codes certainly makes them a strong contender in this race in progress.

Looking to the future, for polar codes to be crowned as the universal coding method, the main challenge is to break the data rate barrier, while retaining error-correction performance as well as the low-complexity advantages. Data channels typically operate in much higher data rates than control channels. 5G peak mobile broadband data rates are expected to be around 20Gbps. Beyond-5G systems are expected to operate at Terabit/s data rates. Today’s most advanced polar code implementations currently deliver only around 5Gbps. There is however a solid theoretical framework underlying polar codes that will be built on and should not prevent them from full ascension over time.

This article is published as part of the IDG Contributor Network. Want to Join?

Related:
How to handle Windows 10 updates
Shop Tech Products at Amazon