Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation
Loop distribution of Tanner graph affects the BER performance of low-density parity-check codes(LDPC) decoding.To count short cycles in the Tanner graph efficiently,a side by side recursion algorithm based on matrix computation was proposed.Firstly,5 basic graph structures were defined to realize re...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2017-04-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2017083/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539512085250048 |
|---|---|
| author | Qing ZHU Le-nan WU Yong-biao YANG Jie LI Shi-ming XU |
| author_facet | Qing ZHU Le-nan WU Yong-biao YANG Jie LI Shi-ming XU |
| author_sort | Qing ZHU |
| collection | DOAJ |
| description | Loop distribution of Tanner graph affects the BER performance of low-density parity-check codes(LDPC) decoding.To count short cycles in the Tanner graph efficiently,a side by side recursion algorithm based on matrix computation was proposed.Firstly,5 basic graph structures were defined to realize recursive calculate in the implementation process.Compared with previous works,the algorithm provided many methods for counting the same length of cycles.The same result confirmed the correctness of the algorithm.The new algorithm could not only calculate the total number of cycles,but also gave the number each edge participating in fixed-length cycles.Its complexity was proportional to the product of D and square of N,where D was the average degree of variable nodes,and N denoted the code length.For LDPC codes,D was far less than N.For most of the LDPC codes,the calculation for numbers of cycle-length g、g+2、g+4 was only several seconds. |
| format | Article |
| id | doaj-art-6f222e18098948cc949061f75e18676a |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2017-04-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-6f222e18098948cc949061f75e18676a2025-01-14T07:12:01ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2017-04-0138768559709059Efficient algorithm for calculating short cycles in Tanner graph based on matrix computationQing ZHULe-nan WUYong-biao YANGJie LIShi-ming XULoop distribution of Tanner graph affects the BER performance of low-density parity-check codes(LDPC) decoding.To count short cycles in the Tanner graph efficiently,a side by side recursion algorithm based on matrix computation was proposed.Firstly,5 basic graph structures were defined to realize recursive calculate in the implementation process.Compared with previous works,the algorithm provided many methods for counting the same length of cycles.The same result confirmed the correctness of the algorithm.The new algorithm could not only calculate the total number of cycles,but also gave the number each edge participating in fixed-length cycles.Its complexity was proportional to the product of D and square of N,where D was the average degree of variable nodes,and N denoted the code length.For LDPC codes,D was far less than N.For most of the LDPC codes,the calculation for numbers of cycle-length g、g+2、g+4 was only several seconds.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2017083/Tanner graphlow-density parity-check codes (LDPC)short cyclegirth |
| spellingShingle | Qing ZHU Le-nan WU Yong-biao YANG Jie LI Shi-ming XU Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation Tongxin xuebao Tanner graph low-density parity-check codes (LDPC) short cycle girth |
| title | Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation |
| title_full | Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation |
| title_fullStr | Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation |
| title_full_unstemmed | Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation |
| title_short | Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation |
| title_sort | efficient algorithm for calculating short cycles in tanner graph based on matrix computation |
| topic | Tanner graph low-density parity-check codes (LDPC) short cycle girth |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2017083/ |
| work_keys_str_mv | AT qingzhu efficientalgorithmforcalculatingshortcyclesintannergraphbasedonmatrixcomputation AT lenanwu efficientalgorithmforcalculatingshortcyclesintannergraphbasedonmatrixcomputation AT yongbiaoyang efficientalgorithmforcalculatingshortcyclesintannergraphbasedonmatrixcomputation AT jieli efficientalgorithmforcalculatingshortcyclesintannergraphbasedonmatrixcomputation AT shimingxu efficientalgorithmforcalculatingshortcyclesintannergraphbasedonmatrixcomputation |