Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear Programming
An approach to design protograph-based low-density parity-check (LDPC) codes utilizing mixed integer linear programming (MILP) optimization is presented in this paper. The protograph (base graph) cyclic lifting for a class of quasi-cyclic LDPC codes is considered. In general, the short cycles elimin...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8573763/ |
| _version_ | 1831805794957393920 |
|---|---|
| author | Wojciech Sulek |
| author_facet | Wojciech Sulek |
| author_sort | Wojciech Sulek |
| collection | DOAJ |
| description | An approach to design protograph-based low-density parity-check (LDPC) codes utilizing mixed integer linear programming (MILP) optimization is presented in this paper. The protograph (base graph) cyclic lifting for a class of quasi-cyclic LDPC codes is considered. In general, the short cycles elimination is the primary optimization goal, possibly weighted by a metric of cycles connectivity. A notion of closed walks in the base graph is shown to be a convenient way for representing sources of cycles in the lifted graph. We express the condition for non-existence of a cycle in the lifted graph corresponding to a closed walk in the base graph in the form of a set of linear inequalities. Such inequalities, collected for all closed walks shorter than a desired limit corresponding to girth, form a set of linear constraints. Meanwhile, the longer closed walks can be reflected in a linear objective function of the optimization. The proposed combination of constraints and objective function forms an input to a MILP solver. As a result, a globally optimized code graph can be obtained. The method can be utilized for binary as well as nonbinary LDPC codes. The numerical results show that the constructed codes can outperform similar codes deigned with reference heuristic search methods. |
| first_indexed | 2024-12-22T19:29:39Z |
| format | Article |
| id | doaj.art-ddad0ea6103c47fd89286571ff3d6162 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-22T19:29:39Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-ddad0ea6103c47fd89286571ff3d61622022-12-21T18:15:08ZengIEEEIEEE Access2169-35362019-01-0171424143810.1109/ACCESS.2018.28865278573763Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear ProgrammingWojciech Sulek0https://orcid.org/0000-0003-3462-0657Faculty of Automatic Control, Electronics and Computer Science, Silesian University of Technology, Gliwice, PolandAn approach to design protograph-based low-density parity-check (LDPC) codes utilizing mixed integer linear programming (MILP) optimization is presented in this paper. The protograph (base graph) cyclic lifting for a class of quasi-cyclic LDPC codes is considered. In general, the short cycles elimination is the primary optimization goal, possibly weighted by a metric of cycles connectivity. A notion of closed walks in the base graph is shown to be a convenient way for representing sources of cycles in the lifted graph. We express the condition for non-existence of a cycle in the lifted graph corresponding to a closed walk in the base graph in the form of a set of linear inequalities. Such inequalities, collected for all closed walks shorter than a desired limit corresponding to girth, form a set of linear constraints. Meanwhile, the longer closed walks can be reflected in a linear objective function of the optimization. The proposed combination of constraints and objective function forms an input to a MILP solver. As a result, a globally optimized code graph can be obtained. The method can be utilized for binary as well as nonbinary LDPC codes. The numerical results show that the constructed codes can outperform similar codes deigned with reference heuristic search methods.https://ieeexplore.ieee.org/document/8573763/Low density parity check codesnonbinary codesprotographquasi-cyclic codes |
| spellingShingle | Wojciech Sulek Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear Programming IEEE Access Low density parity check codes nonbinary codes protograph quasi-cyclic codes |
| title | Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear Programming |
| title_full | Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear Programming |
| title_fullStr | Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear Programming |
| title_full_unstemmed | Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear Programming |
| title_short | Protograph Based Low-Density Parity-Check Codes Design With Mixed Integer Linear Programming |
| title_sort | protograph based low density parity check codes design with mixed integer linear programming |
| topic | Low density parity check codes nonbinary codes protograph quasi-cyclic codes |
| url | https://ieeexplore.ieee.org/document/8573763/ |
| work_keys_str_mv | AT wojciechsulek protographbasedlowdensityparitycheckcodesdesignwithmixedintegerlinearprogramming |