一种基于模运算和扩展欧几里得定理的喷泉码

doi:10.3969/j.issn.0372-2112.2017.04.013

电子学报 ›› 2017, Vol. 45 ›› Issue (4): 855-862.DOI: 10.3969/j.issn.0372-2112.2017.04.013

一种基于模运算和扩展欧几里得定理的喷泉码

朱文杰^1,2, 易本顺^1,2, 甘良才¹, 姚渭箐^1,2

1. 武汉大学电子信息学院, 湖北武汉 430072;
2. 武汉大学深圳研究院, 广东深圳 518000

收稿日期:2015-05-12 修回日期:2016-05-22 出版日期:2017-04-25 发布日期:2017-04-25
作者简介:朱文杰 男,1984年出生于湖北孝昌县,武汉大学博士研究生,研究方向为无线通信,信道编码.E-mail:wenjie8408@163.com;易本顺 男,1965出生于湖北武汉,武汉大学教授,博士生导师,主要研究方向为多媒体通信,无线网络.E-mail:yibs@whu.edu.cn
基金资助:
国家自然科学基金（No.61371125，No.61072041）；深圳市基础研究项目（No.JCYJ20150630153917254）

Novel Fountain Codes Based on Modulo and Extended Euclidean

ZHU Wen-jie^1,2, YI Ben-shun^1,2, GAN Liang-cai¹, YAO Wei-qing^1,2

1. School of Electronic Information, Wuhan University, Wuhan, Hubei 430072, China;
2. Shenzhen Institute of Wuhan University, Shenzhen, Guangdong 518000, China

Received:2015-05-12 Revised:2016-05-22 Online:2017-04-25 Published:2017-04-25

摘要/Abstract

摘要：

针对中国剩余定理在模运算喷泉码译码过程中的固有不足，本文提出一种全新的基于扩展欧几里德定理的译码算法.该算法采用合并线性同余方程组，避免分解因子非互质情况下求解乘率因子失败的问题.模运算喷泉码将信息数据编码为自然数分解因子和相对应的模余数的数据包，接收方只要获取一定数目的编码数据包就能成功解码.基于扩展欧几里得定理的译码算法扩展了模运算喷泉码的分解因子范围，提高了编译码效率.本文通过理论分析和数值仿真证实了这种编译码算法的可行性.

关键词: 喷泉码, 中国剩余定理, 扩展欧几里德定理, 余数变换码, 线性同余方程

Abstract:

Aiming at the intrinsic problems of Chinese Remainder Theorem in fountain decoding process with modular arithmetic,this paper proposes a decoding algorithm based on extended Euclidean theorem.The linear congruence equations are merged in the extended Euclidean decoding algorithm,which avoids the failure of solving the rate factor when the decomposition factors are non-coprime.In the modular arithmetic fountain encoding process,the original packet is continuously decomposed by the factor,which is randomly selected from the natural number,into the encoded packets consisting of the residues and the factors.When a certain amount of packets are received,it can be achieved to decode successfully.The codec efficiency has been improved as the algorithm has extended the range of the modular arithmetic factor.Through theoretical analysis and numerical simulation,the effectiveness of this decoding algorithm of modular arithmetic fountain code has been proved.

Key words: fountain codes, Chinese remainder theorem, extended Euclidean, remainder transform codes, linear congruence equations

中图分类号:

TN911.2

朱文杰, 易本顺, 甘良才, 姚渭箐. 一种基于模运算和扩展欧几里得定理的喷泉码[J]. 电子学报, 2017, 45(4): 855-862.

ZHU Wen-jie, YI Ben-shun, GAN Liang-cai, YAO Wei-qing. Novel Fountain Codes Based on Modulo and Extended Euclidean[J]. Acta Electronica Sinica, 2017, 45(4): 855-862.

参考文献

[1] LUBY M,WATSON M,GASIBA T,STOCKHAMMER T.Mobile data broadcasting over MBMS trade offs in forward error correction[A].ACM International Conference Proceeding Series[C].New York:ACM,2006.10-20.
[2] MIRREZAEI S M,FAEZ K,YOUSEFI S.Analysis and design of a new fountain codec under belief propagation[J].IET Communications,2014,8(1):27-40.
[3] NESSA A,KADOCH M,BO Rong.Joint network channel fountain scheme for reliable communication in wireless networks[A].International Conference on Computing,Networking and Communications[C].Iguazu Falls:IEEE,2014.206-210.
[4] HAO Niu,IWAI M,SEZAKI K.Exploiting fountain codes for secure wireless delivery[J].IEEE Communications Letters,2014,18(5):777-780.
[5] HUANG Wei,LU Zhufei,DING Lianghui.Television broadcast using unequal fountain codes[A].IEEE International Symposium on Broadband Multimedia Systems and Broadcasting[C].Beijing:IEEE,2014.1-6.
[6] SHIRVANIMOGHADDAM,LI Yonghui,VUCETIC B.Sparse event detection in wireless sensor networks using analog fountain codes[A].IEEE Global Communications Conference[C].Austin:IEEE,2014.3520-3525.
[7] ALEXANDRE P,VIEIRA J,NAVARRO A.Data broadcasting over DAB/DMB with Fountain codes and auxilliary mobile data channels[A].The 16th International Telecommunications Network Strategy and Planning Symposium[C].Funchal:IEEE,2014.1-6.
[8] 慕建君,焦晓鹏,曹训志.数字喷泉码及其应用的研究进展与展望[J].电子学报,2009,37(7):1571-1577. MU Jian-jun,JIAO Xiao-peng,CAO Xun-zhi.A survey of digital fountain codes and its application[J].Acta Ecectronica Sinica,2009,37(7):1571-1577.(in Chinese)
[9] CHANG Shih-Ying,CHIAO Hsin-Ta,HUNG Yu-Hsiang.Ideal forward error correction codes for high-speed rail multimedia communications[J].IEEE Transactions on Vehicular Technology,2014,63(8):3517-3529.
[10] SHIH Pei-Yu,SU Wen-Ku,LIN Tsung-Ching,TRUONG Trieu-Kien.Modified decoding of binary quadratic residue codes by using euclidean algorithm[A].Proceedings of the 11th International Conference on Advanced Communication Technology[C].Gangwon-Do:IEEE,2009.1398-1402.
[11] DILIP V,YAN Sarwate Zhiyuan.Modified euclidean algorithms for decoding reed-solomon codes[J].Proceedings of IEEE International Symposium on Information Theory,Seoul,Korea:IEEE,2009.1398-1402.
[12] KAMPF Sabine,WACHTER Antonia,BOSSERT Martin.A method for soft-decision decoding of reed-solomon codes based on the extended Euclidean algorithm[A].Proceedings of International ITG Conference on Source and Channel Coding[C].Ulm:IEEE,2010.1-6.
[13] ZEH Alexander,LI Wenhui.Decoding reed-solomon codes up to the sudan radius with the euclidean algorithm[A].Proceedings of International Symposium on Information Theory and its Applications[C].Austin:IEEE,2010.986-990.
[14] 陈代梅,范希辉,朱静,汪玉美.基于同余方程和中国剩余定理的混淆算法[J].计算机应用研究,2015,32(2):485-488. CHEN Dai-mei,FAN Xi-hui,ZHU Jing,WANG Yu-mei.Obfuscation algorithms based on congruence equation and Chinese remainder theorem[J].Application Research of Computers,2015,32(2):485-488.(in Chinese)
[15] LUO Xiaofeng,XU Qiaozhi,ZHANG Junxing.A digital watermarking algorithm based on Chinese remainder theorem[A].The 10th International Conference on Communications[C].Bucharest:IEEE,2014.1-4.
[16] 杨阳,朱晓玲,丁凉.基于中国剩余定理的无可信中心可验证秘密共享研究[J].计算机工程,2015,41(2):122-128. YANG Yang,ZHU Xiaoling,DING Liang.Research on verifiable secret sharing without trusted center based on chinese remainder theorem[J].Computer Engineering,2015,41(2):122-128.(in Chinese)
[17] 陈泽文,张龙军,王育民,黄继武,黄达人.一种基于中国剩余定理的群签名方案[J].电子学报,2004,32(7):1062-1065. CHEN Ze-wen,ZHANG Long-jun,WANG Yu-min,HUANG Ji-wu,HUANG Da-ren.A group signature scheme based on chinese remainder theorem[J].Acta Ecectronica Sinica,2004,32(7):1062-1065.(in Chinese)
[18] MOSTAFA Mohamed,MARTIN H Bossert.A chase-like decoding algorithm for reed-solomon codes based on the extended euclidean algorithm[A].Proceedings of the 10th International ITG Conference on Systems,Communications and Coding[C].Hamburg:IEEE,2015.1-4.
[19] YANG Jun-jian,WANG Yun.An extended euclid algorithm for rational reconstruction[A].IEEE Symposium on Electrical & Electronics Engineering[C].Kuala Lumpur:IEEE,2012.422-424.
[20] ZENG Meng,CALDERBANK Robert,CUI Shuguang.On design of rateless codes over dying binary erasure channel[J].IEEE Transactions on Communications,2012,60(4):889-894.
[21] CHEN Guo-tai,CAO Lei,ZHAO Fei-long.Analysis of robust soliton distribution for LT code[A].Proceedings of the IEEE 11th International Conference on Signal Processing[C].Beijing:IEEE,2012.1546-1549.
[22] 祝开艳,王洪玉,孙文珠,牛芳琳.一种分布式喷泉码在协作通信中的应用[J].电子学报,2014,42(7):1249-1255. ZHU Kai-yan,WANG Hong-yu,SUN Wen-zhu,NIU Fang-lin.A distributed fountain code for cooperative Communications[J].Acta Ecectronica Sinica,2014,42(7):1249-1255.(in Chinese)

一种基于模运算和扩展欧几里得定理的喷泉码

Novel Fountain Codes Based on Modulo and Extended Euclidean

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

[1]	宋鑫, 程乃平, 廖育荣, 倪淑燕, 雷拓峰. 具有逆向边增长结构LT码的设计与分析[J]. 电子学报, 2022, 50(5): 1201-1210.
[2]	牛芳琳, 李宝明, 陈付亮, 王洪玉, 祝开艳. 一种改进的基于部分信息喷泉码度分布设计[J]. 电子学报, 2016, 44(2): 295-300.
[3]	牛芳琳, 王洪玉, 陈雷, 祝开艳. 基于LT码的LBCMP迭代纠错方法[J]. 电子学报, 2016, 44(1): 27-32.
[4]	雷维嘉, 张梦, 谢显中. 基于度分布合并和可译集优化的LT码度分布设计方案[J]. 电子学报, 2015, 43(4): 800-805.
[5]	祝开艳, 王洪玉, 孙文珠, 牛芳琳. 一种分布式喷泉码在协作通信中的应用[J]. 电子学报, 2014, 42(7): 1249-1255.
[6]	孙文珠, 王洪玉, 祝开艳, 王洁, 唐震洲. 一种规则变量节点度LTCodes编码方案[J]. 电子学报, 2014, 42(10): 1918-1924.
[7]	雷维嘉;谢显中;李广军. 采用数字喷泉码的无线协作中继方案及其性能分析[J]. 电子学报, 2010, 38(1): 228-233.
[8]	慕建君;焦晓鹏;曹训志. 数字喷泉码及其应用的研究进展与展望[J]. 电子学报, 2009, 37(7): 1571-1577.
[9]	李凤华;王巍;马建峰. 适用于传感器网络的分级群组密钥管理[J]. 电子学报, 2008, 36(12): 2405-2411.
[10]	李俊;崔国华;刘志远. 一个群签名方案的密码学分析与改进[J]. 电子学报, 2007, 35(4): 778-781.
[11]	陈泽文;张龙军;王育民;黄继武;黄达人. 一种基于中国剩余定理的群签名方案[J]. 电子学报, 2004, 32(7): 1062-1065.
[12]	卿斯汉;蒙杨;刘克龙. 分布式应用中的多级安全密钥管理[J]. 电子学报, 2001, 29(2): 269-271.