Linear Programming Decoding of Non-Linear Sparse-Graph Codes

Gleb Balitskiy, Alexey Frolov, Pavel Rybin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

In modern coding theory, linear code constructions are mainly used. Their properties and fundamental theoretical limits are well studied, and they are successfully applied to different classes of problems. Until now, non-linear codes did not attract much attention from specialists because linear structures have coped with their tasks and have the required research tools developed earlier. But in a series of works devoted to the study of codes with graceful degradation, H. Roozbehani, and Y. Polyanskiy proposed the construction of non-linear low-density majority codes (LDMC) and effective encoding and decoding algorithms for them. Moreover, they showed that LDMC has a lower bit error rate (BER) than any linear code in the error-reducing regime for the binary erasure channel (BEC). Given this motivation, we consider non-linear sparse-graph codes (a generalized version of LDMC) and investigate their performance in the AWGN channel. For this class of codes, we proposed efficient generalized BP-based and LP-based decoding algorithms. We accurately estimated BER under ML decoding of non-linear codes based on the LP-based decoder. Also, by simulation, we carried out the analysis and comparison of performances of various non-linear codes.

Original languageEnglish
Title of host publication2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages149-154
Number of pages6
ISBN (Electronic)9781665433082
DOIs
Publication statusPublished - 2021
Event17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021 - Moscow, Russian Federation
Duration: 25 Oct 202129 Oct 2021

Publication series

Name2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021

Conference

Conference17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021
Country/TerritoryRussian Federation
CityMoscow
Period25/10/2129/10/21

Fingerprint

Dive into the research topics of 'Linear Programming Decoding of Non-Linear Sparse-Graph Codes'. Together they form a unique fingerprint.

Cite this