List Decoding of Polar Codes
(2017) EITM01 20171Department 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:
http://lup.lub.lu.se/student-papers/record/8927968
- author
- Johansson, Emilia LU
- supervisor
- organization
- course
- EITM01 20171
- year
- 2017
- 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}},
language = {{eng}},
note = {{Student Paper}},
title = {{List Decoding of Polar Codes}},
year = {{2017}},
}