Advanced

List Decoding of Polar Codes

Johansson, Emilia LU (2017) EITM01 20171
Department of Electrical and Information Technology
Abstract
Channel coding is an important instrument used in communication to correct errors that occur on channels. It is interesting to find the best-suited channel code for different communication systems.

Polar codes have been in the spotlight lately for their simple structure and performance when in combination with list decoding and cyclic redundancy check code. Polar codes have a recursive structure that makes them interesting to implement in hardware, and they have lately been chosen as a standard for short code communication in 5G to correct bit errors. However, polar codes by themselves are shown to work poorly for practical block lengths, and it is therefore of interest to research them further.

This thesis investigates polar codes... (More)
Channel coding is an important instrument used in communication to correct errors that occur on channels. It is interesting to find the best-suited channel code for different communication systems.

Polar codes have been in the spotlight lately for their simple structure and performance when in combination with list decoding and cyclic redundancy check code. Polar codes have a recursive structure that makes them interesting to implement in hardware, and they have lately been chosen as a standard for short code communication in 5G to correct bit errors. However, polar codes by themselves are shown to work poorly for practical block lengths, and it is therefore of interest to research them further.

This thesis investigates polar codes with a suggested combination of list decoding and CRC. The combination is shown to improve short polar codes enough to compete with the best-known channel codes today for short block lengths. This thesis investigates why this combination works so well with polar codes. The focus lies on the selection of frozen bits in polar codes, in comparison with the similar Reed-Muller codes, and on the size and bit-placement of the CRCs. All investigations focus on codes with length 128 bits and code rate 0.5.

We find that a slightly modified frozen bit selection can result in huge performance changes of polar codes. We also find how the use of a list decoder with a large list size improves Reed-Muller codes such that they challenge polar codes both with and without added CRCs.

We study if a long CRC is preferred, or if the code performance can be improved by dividing it into several shorter CRCs spread out over the polar code. Results from different modifications to polar codes are presented and discussed. (Less)
Popular Abstract
Polar codes have recently been selected as standard to be implemented in 5G for short messages, but they only perform well for short messages after some modifications. This thesis compares variations of those modifications.

Assume that you want to send data between two devices. The optimal outcome would be that the receiver receives your message unmodified. A problem that occurs when data is transmitted is that transmission channels are subject to noise, which can result in bit errors in your data.

Channel codes are used to solve this issue. They add redundancy to your message in shape of more bits before it gets transmitted on the channel, in a way such that the receiver can use these added bits to detect or correct errors that... (More)
Polar codes have recently been selected as standard to be implemented in 5G for short messages, but they only perform well for short messages after some modifications. This thesis compares variations of those modifications.

Assume that you want to send data between two devices. The optimal outcome would be that the receiver receives your message unmodified. A problem that occurs when data is transmitted is that transmission channels are subject to noise, which can result in bit errors in your data.

Channel codes are used to solve this issue. They add redundancy to your message in shape of more bits before it gets transmitted on the channel, in a way such that the receiver can use these added bits to detect or correct errors that occurred on the channel.

Polar codes are recently discovered channel codes. They have many desirable properties, such as low error rates and a low complexity encoder and decoder. They are fast, do not need much computing power, and are simple to implement in hardware. Unfortunately, the codes do not perform well for short messages of up to a few thousand bits. However, recent research found that this could be changed if the code is combined with a more complex list decoder and another channel code called CRC. The CRC is added to aid the decoder in its last step to find the correct message in a list. Polar codes have recently been selected to be used as a standard in 5G for short messages.

This thesis investigates how this relatively poorly performing code can be improved enough to compete with the best codes for short code communication, focusing on 128-bit codes.

Polar codes polarize channels so that some become reliable and other unreliable. The set of reliable channels is used to send data on, and all other are called frozen. With the improved polar codes, three variables are not uniquely specified. They are the selection of frozen bits, the list decoder size, and the CRC polynomial. We investigate how these three variables change the code performance. The frozen bit selection is compared with that of the similar Reed-Muller code.

Results include the observation that the Reed-Muller codes under some circumstances perform better than polar codes in combination with list decoding and CRC. We also observe that the selection of frozen bits is crucial for finding the best performing short polar code, but not trivial.

The CRC is constructed to detect long burst errors, but we do not know if that is the type of errors that occur in the polar code, and therefore not if a CRC is an optimal code to use in the list decoder. Interesting results show that two shorter CRCs spread out over the decoder sometimes improve the code compared to one stronger CRC at the end.

Results and conclusions can be used when constructing polar codes for implementation in 5G. The divided CRC can, for example, be used to compensate for a lower complexity decoder. Conclusions include that polar codes should be tested and compared before implementation since finding the best polar code is not trivial for short codes. Further research should include a closer look at CRCs. (Less)
Please use this url to cite or link to this publication:
author
Johansson, Emilia LU
supervisor
organization
course
EITM01 20171
year
type
H2 - Master's Degree (Two Years)
subject
keywords
polar codes, Channel coding, list decoding, CRC, Reed-Muller codes, short codes, 5G.
report number
LU/LTH-EIT 2017-607
language
English
id
8927968
date added to LUP
2017-11-07 16:28:29
date last changed
2017-11-07 16:28:29
@misc{8927968,
  abstract     = {Channel coding is an important instrument used in communication to correct errors that occur on channels. It is interesting to find the best-suited channel code for different communication systems.

Polar codes have been in the spotlight lately for their simple structure and performance when in combination with list decoding and cyclic redundancy check code. Polar codes have a recursive structure that makes them interesting to implement in hardware, and they have lately been chosen as a standard for short code communication in 5G to correct bit errors. However, polar codes by themselves are shown to work poorly for practical block lengths, and it is therefore of interest to research them further. 

This thesis investigates polar codes with a suggested combination of list decoding and CRC. The combination is shown to improve short polar codes enough to compete with the best-known channel codes today for short block lengths. This thesis investigates why this combination works so well with polar codes. The focus lies on the selection of frozen bits in polar codes, in comparison with the similar Reed-Muller codes, and on the size and bit-placement of the CRCs. All investigations focus on codes with length 128 bits and code rate 0.5. 

We find that a slightly modified frozen bit selection can result in huge performance changes of polar codes. We also find how the use of a list decoder with a large list size improves Reed-Muller codes such that they challenge polar codes both with and without added CRCs. 

We study if a long CRC is preferred, or if the code performance can be improved by dividing it into several shorter CRCs spread out over the polar code. Results from different modifications to polar codes are presented and discussed.},
  author       = {Johansson, Emilia},
  keyword      = {polar codes,Channel coding,list decoding,CRC,Reed-Muller codes,short codes,5G.},
  language     = {eng},
  note         = {Student Paper},
  title        = {List Decoding of Polar Codes},
  year         = {2017},
}