An Approach to Evaluating the Number of Closed Paths in an All-One Base Matrix
Given an all-one base matrix of size M×N, a closed path of different lengths can be formed by starting at an arbitrary element and moving horizontally and vertically alternatively before terminating at the same “starting” element. When the closed-path length is small...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2018-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8326474/ |
| _version_ | 1818911663463596032 |
|---|---|
| author | Sheng Jiang Francis C. M. Lau |
| author_facet | Sheng Jiang Francis C. M. Lau |
| author_sort | Sheng Jiang |
| collection | DOAJ |
| description | Given an all-one base matrix of size M×N, a closed path of different lengths can be formed by starting at an arbitrary element and moving horizontally and vertically alternatively before terminating at the same “starting” element. When the closed-path length is small, say 4 or 6, the total number of combinations can be evaluated easily. When the length increases, the computation becomes non-trivial. In this paper, a novel method is proposed to evaluate the number of closed paths of different lengths in an all-one base matrix. Theoretical results up to closed paths of length 10 have been derived and are verified by the exhaustive search method. Based on the theoretical work, results for closed paths of length larger than 10 can be further derived. Note that each of such closed paths may give rise to one or more cycles in a low-density parity-check (LDPC) code when the LDPC code is constructed by replacing each “1” in the base matrix with a circulant permutation matrix or a random permutation matrix. Since LPDC codes with short cycles are known to give unsatisfactory error correction capability, the results in this paper can be used to estimate the amount of effort required to evaluate the number of potential cycles of an LDPC code or to optimize the code. |
| first_indexed | 2024-12-19T23:02:17Z |
| format | Article |
| id | doaj.art-f0e3ce7af8ed46aab77cf8202853ab83 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-19T23:02:17Z |
| publishDate | 2018-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-f0e3ce7af8ed46aab77cf8202853ab832022-12-21T20:02:28ZengIEEEIEEE Access2169-35362018-01-016223322234010.1109/ACCESS.2018.28199818326474An Approach to Evaluating the Number of Closed Paths in an All-One Base MatrixSheng Jiang0Francis C. M. Lau1https://orcid.org/0000-0002-8279-0899Department of Electronic and Information Engineering, The Hong Kong Polytechnic University, Hong KongDepartment of Electronic and Information Engineering, The Hong Kong Polytechnic University, Hong KongGiven an all-one base matrix of size M×N, a closed path of different lengths can be formed by starting at an arbitrary element and moving horizontally and vertically alternatively before terminating at the same “starting” element. When the closed-path length is small, say 4 or 6, the total number of combinations can be evaluated easily. When the length increases, the computation becomes non-trivial. In this paper, a novel method is proposed to evaluate the number of closed paths of different lengths in an all-one base matrix. Theoretical results up to closed paths of length 10 have been derived and are verified by the exhaustive search method. Based on the theoretical work, results for closed paths of length larger than 10 can be further derived. Note that each of such closed paths may give rise to one or more cycles in a low-density parity-check (LDPC) code when the LDPC code is constructed by replacing each “1” in the base matrix with a circulant permutation matrix or a random permutation matrix. Since LPDC codes with short cycles are known to give unsatisfactory error correction capability, the results in this paper can be used to estimate the amount of effort required to evaluate the number of potential cycles of an LDPC code or to optimize the code.https://ieeexplore.ieee.org/document/8326474/All-one base matrixclosed pathcycleslow-density parity-check code |
| spellingShingle | Sheng Jiang Francis C. M. Lau An Approach to Evaluating the Number of Closed Paths in an All-One Base Matrix IEEE Access All-one base matrix closed path cycles low-density parity-check code |
| title | An Approach to Evaluating the Number of Closed Paths in an All-One Base Matrix |
| title_full | An Approach to Evaluating the Number of Closed Paths in an All-One Base Matrix |
| title_fullStr | An Approach to Evaluating the Number of Closed Paths in an All-One Base Matrix |
| title_full_unstemmed | An Approach to Evaluating the Number of Closed Paths in an All-One Base Matrix |
| title_short | An Approach to Evaluating the Number of Closed Paths in an All-One Base Matrix |
| title_sort | approach to evaluating the number of closed paths in an all one base matrix |
| topic | All-one base matrix closed path cycles low-density parity-check code |
| url | https://ieeexplore.ieee.org/document/8326474/ |
| work_keys_str_mv | AT shengjiang anapproachtoevaluatingthenumberofclosedpathsinanallonebasematrix AT franciscmlau anapproachtoevaluatingthenumberofclosedpathsinanallonebasematrix AT shengjiang approachtoevaluatingthenumberofclosedpathsinanallonebasematrix AT franciscmlau approachtoevaluatingthenumberofclosedpathsinanallonebasematrix |