Construct the Systematic Binary Quasi-cyclic Codes with Rate 1/p Based on Variable Matroid Search Algorithm

ZHANG Shuiping; LIN Pingping; WU Guangfu; JIANG Linwei

doi:10.11999/JEIT160074

Volume 38 Issue 11

Dec. 2016

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2016 > 38(11): 2916-2921

ZHANG Shuiping, LIN Pingping, WU Guangfu, JIANG Linwei. Construct the Systematic Binary Quasi-cyclic Codes with Rate 1/p Based on Variable Matroid Search Algorithm[J]. Journal of Electronics & Information Technology, 2016, 38(11): 2916-2921. doi: 10.11999/JEIT160074

Citation:

ZHANG Shuiping, LIN Pingping, WU Guangfu, JIANG Linwei. Construct the Systematic Binary Quasi-cyclic Codes with Rate 1/p Based on Variable Matroid Search Algorithm[J]. Journal of Electronics & Information Technology, 2016, 38(11): 2916-2921. doi: 10.11999/JEIT160074

Citation:

PDF( 221 KB)

Construct the Systematic Binary Quasi-cyclic Codes with Rate 1/p Based on Variable Matroid Search Algorithm

doi: 10.11999/JEIT160074 cstr: 32379.14.JEIT160074

Funds:

The National Natural Science Foundation of China (11461031, 61562037), The Natural Science Foundation of Jiangxi Province (20151BAB217016)

Received Date: 2016-01-19
Rev Recd Date: 2016-06-15
Publish Date: 2016-11-19

Abstract

Abstract

Because the matroid search algorithm is very complicated and the local matroid search algorithm can not search all optimal codes, this paper proposes a variable matroid search algorithm to search the quasi-cyclic codes by researching matroid search algorithm. The algorithm reduces the computational complexity by reducing the repeated search. Based on this algorithm, the systematic binary quasi-cyclic codes of which the rate is 1/p are constructed. With the change of integer p, the optimal codes of rate 1/p can be obtained by the generator matrix reducing or adding a loop matrix. Through experiments, two new codes of which the minimum distance is larger than the existing optimal codes are worked out, which indicate the feasibility and superiority of the algorithm.
- Matroid theory,
- Quasi-cyclic codes,
- Minimum distance,
- Variable matroid sear

FullText(HTML)

References(23)

References

TOWNSEND R and WELDON E. Self-orthogonal quasi-cyclic codes[J]. IEEE Transactions on Information Theory, 1967, 13(2): 183-195. doi: 10.1109/TIT.1967. 1053974.

CHEN Z. New results on binary quasi-cyclic codes[C]. Proceedings of IEEE International Symposium on Information Theory, Sorrento Italy, 2000: 151-154.

HEIJNEN P, VAN T H, VERHOEFF T, et al. Some new binary quasi-cyclic codes[J]. IEEE Transactions on Information Theory, 1998, 44(5): 1994-1996. doi: 10.1109/ 18.705580.

张轶, 达新宇, 苏一栋. 利用等差数列构造大围长准循环低密度奇偶校验码[J]. 电子与信息学报, 2015, 37(2): 394-398. doi: 10.11999/JEIT140538.

ZHANG Yi, DA Xinyu, and SU Yidong. Construction of quasi-cyclic low-density parity-check codes with a large girth based on arithmetic progression[J]. Journal of Electronics Information Technology, 2015, 37(2): 394-398. doi: 10.11999/JEIT140538．

郭锐, 刘春于, 张华, 等. 分簇无线传感器网络中根校验全分集LDPC码设计与能效分析[J]. 电子与信息学报, 2015, 37(7): 1580-1585. doi: 10.11999/JEIT141294.

GUO Rui, LIU Chunyu, ZHANG Hua, et al. Full diversity LDPC codes design and energy efficiency analysis for clustering wireless sensor networks[J]. Journal of Electronics Information Technology, 2015, 37(7): 1580-1585. doi: 10.11999/JEIT141294.

陈震华, 许肖梅, 陈友淦, 等. 浅海水声信道中原模图LDPC码的设计及性能分析[J]. 电子与信息学报, 2016, 38(1): 153-159. doi: 10.11999/JEIT150415．

CHEN Zhenhua, XU Xiaomei, CHEN Yougan, et al. Design and analysis of Protograph-based LDPC codes in shallow water acoustic channels[J]. Journal of Electronics Information Technology, 2016, 38(1): 153-159. doi: 10.11999/ JEIT150415.

兰亚柱, 杨海钢, 林郁. 动态自适应低密度奇偶校验码译码器的FPGA实现[J]. 电子与信息学报, 2015, 37(8): 1937-1943. doi: 10.11999/JEIT141609.

LAN Yazhu, YANG Haigang, and LIN Yu. Design of dynamic adaptive LDPC decoder based on FPGA[J]. Journal of Electronics Information Technology, 2015, 37(8): 1937-1943. doi: 10.11999/JEIT141609.

WHITNEY H. On the abstract properties of linear dependence[J]. The American Mathematical Society, 1935, 57(1): 509-533. doi: 10.1007/978-1-4612-2972-8_10.

GREENE C. Weight enumeration and the geometry of linear codes[J]. Studies in Applied Mathematics, 1976, 55(55): 119-128. doi: 10.1002/sapm1976552119.

BARG A. The matroid of supports of a linear code[J]. Applicable Algebra in Engineering Communication Computing, 1997, 8(2): 165-172. doi: 10.1007/s 002000050060.

KASHYAP N. A decomposition theory for binary linear codes[J]. IEEE Transactions on Information Theory, 2008, 54(7): 3035-3058. doi: 10.1109/TIT.2008.924700.

巫光福, 王琳. 一种短的高码率LDPC码设计[J].应用科学学报, 2013, 31(6): 559-563. doi: 10.3969/j.issn.0255-8297. 2013.06.002.

WU Guangfu and WANG Lin. Design of a short high rate LDPC code[J]. Journal of Applied Sciences, 2013, 31(6): 559-563. doi: 10.3969/j.issn.0255-8297.2013.06.002.

WU Guangfu, WANG Lin, and TRUONG T K. Use of matroid theory to construct a class of good binary linear codes[J]. IET Communications, 2014, 8(6): 893-898. doi: 10.1049/iet-com.2013.0671.

WU Guangfu, Chang H C, WANG Lin, et al. Constructing rate 1/p systematic binary quasi-cyclic codes based on the matroid theory[J]. Designs Codes and Cryptography, 2014, 71(1): 47-56. doi: 10.1007/s10623-012-9715-1.

WU Guangfu, LI Yong, ZHANG Shuiping, et al. A random local matroid search algorithm to construct good rate 1/p systematic binary Quasi-Cyclic codes[J]. IEEE Communications Letters, 2015, 19(5): 699-702. doi: 10.1109/ LCOMM.2015.2401572.

OXLEY J. Matroid Theory [M]. Oxford U K, Oxford University Press, 2011: 5-26．

TILBURG H C A V. On quasi-cyclic codes with rate 1/m [J]. IEEE Transactions on Information Theory, 1978, 24(5): 628-629. doi: 10.1109/TIT.1978.1055929.

GULLIVER T A and BHARGAVA V K. An updated table of rate 1/p binary quasi-cyclic codes[J]. Applied Mathematics Letters, 1995, 8(5): 81-86. doi: 10.1016/0893-9659 (95)00071-W.

Relative Articles

Supplements(0)

Cited By

Proportional views