基于全局距离最优的抗污染极短纠错码设计

doi:10.11772/j.issn.1001-9081.2021122065

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (2): 630-635.DOI: 10.11772/j.issn.1001-9081.2021122065

所属专题：前沿与综合应用

基于全局距离最优的抗污染极短纠错码设计

刘坚强(), 屈也频, 吕余海

中国人民解放军海军研究院，上海 200436

收稿日期:2021-12-08 修回日期:2022-01-17 接受日期:2022-02-23 发布日期:2022-03-02 出版日期:2023-02-10
通讯作者: 刘坚强
作者简介:刘坚强（1973—），男，江苏丹阳人，高级工程师，硕士，主要研究方向：电子信息系统、航空电子、信息系统标准化
屈也频（1962—），男，湖南岳阳人，研究员，博士生导师，博士，主要研究方向：飞机总体设计、航空电子系统、惯性技术
吕余海（1977—），男，浙江建德人，高级工程师，硕士，主要研究方向：机载任务系统、航空标准化。
基金资助:
“十三五”装备预先研究项目(3020901020101)

Design of very short antipollution error correcting code based on global distance optimization

Jianqiang LIU(), Yepin QU, Yuhai LYU

Naval Research Academy of PLA，Shanghai 200436，China

Received:2021-12-08 Revised:2022-01-17 Accepted:2022-02-23 Online:2022-03-02 Published:2023-02-10
Contact: Jianqiang LIU
About author:LIU Jianqiang， born in 1973， M. S.， senior engineer. His research interests include electronic information system， avionics， information system standardization.
QU Yepin， born in 1962， P.D.， research fellow. His research interests include aircraft overall design， avionics system， inertial technology.
LYU Yuhai， born in 1977， M. S.， senior engineer. His research interests include airborne mission system， aviation standardization.
Supported by:
Equipment Pre-research Project of “the 13th Five-Year Plan”(3020901020101)

摘要/Abstract

摘要：

针对现有二维码在复杂环境中抗污染能力弱、解码速度慢的问题，提出了一种基于全局距离最优的抗污染极短纠错码。首先，构建了表征污染环境的凹凸多边形数学模型；然后，设计了采用3个编码点表示一个目标数据位的极短纠错码；最后，设计了在有限约束域内全局距离最优的编码点的编排方法，并给出了对应的解码算法。对极短纠错码的抗污染能力和识别速度进行了仿真评估，并与经典的BCH码进行了对比。结果表明，当目标数据长度为18、编码点数为63时，极短纠错码在同等污染环境中识别准确率接近BCH码，而解码速度是BCH码的130倍。所提编码还具有结构简洁明确、编码点数适应能力强、易于标准化推广应用等显著优点。

关键词: 纠错码, 抗污染, 污染模型, 最优距离, BCH码, 二维码

Abstract:

The existing two-dimensional codes have the problems of weak antipollution ability and slow decoding speed in complex environment. To solve these problems， a very short antipollution error correcting code based on global distance optimization was proposed. Firstly， a concave-convex polygon mathematical model was constructed to characterize the polluted environment. Then， a very short error correcting code was designed， which uses three coding points to represent one target data bit. Finally， a coding point arrangement method was designed， which optimizes the global distance within a limited constrained domain. The corresponding decoding algorithm was also given. The antipollution ability and recognition speed of very short error correcting code were simulated and analyzed， and the proposed code was compared with the classical Bose-Chaudhuri-Hocquenghem （BCH） codes. The results show that when the target data length is 18 and the number of coding points is 63， the recognition accuracy of very short error correcting code is close to that of BCH codes in the same polluted environment with the decoding speed of 130 times of that of BCH codes. The proposed code also has the obvious advantages of simple and clear structure， strong adaptability of coding points， and being easy to be standardized and popularized.

Key words: error correcting code, antipollution, pollution model, optimal distance, Bose-Chaudhuri-Hocquenghem (BCH) codes, two-dimensional code

中图分类号:

TP301.6

刘坚强, 屈也频, 吕余海. 基于全局距离最优的抗污染极短纠错码设计[J]. 计算机应用, 2023, 43(2): 630-635.

Jianqiang LIU, Yepin QU, Yuhai LYU. Design of very short antipollution error correcting code based on global distance optimization[J]. Journal of Computer Applications, 2023, 43(2): 630-635.

图/表 8

图1 污染区域示例

Fig.1 Example of polluted area

表1 极短纠错码码字组合

Tab.1 Code word combination of very short error correction code

序号	$a 2, a 1, a 0$	$b 2, b 1, b 0$	序号	$a 2, a 1, a 0$	$b 2, b 1, b 0$
1	0，0，0	1，1，1	5	1，0，0	0，1，1
2	0，0，1	1，1，0	6	1，0，1	0，1，0
3	0，1，0	1，0，1	7	1，1，0	0，0，1
4	0，1，1	1，0，0	8	1，1，1	0，0，0

表1 极短纠错码码字组合

Tab.1 Code word combination of very short error correction code

序号	$a 2, a 1, a 0$	$b 2, b 1, b 0$	序号	$a 2, a 1, a 0$	$b 2, b 1, b 0$
1	0，0，0	1，1，1	5	1，0，0	0，1，1
2	0，0，1	1，1，0	6	1，0，1	0，1，0
3	0，1，0	1，0，1	7	1，1，0	0，0，1
4	0，1，1	1，0，0	8	1，1，1	0，0，0

表2 极短码和典型BCH码参数

Tab.2 Parameters of very short code and typical BCH codes

编码序号	编码	编码利用率	纠错能力	编码效能
1	极短码J（3，1，1）	0.333	0.333	0.111
2	BCH（7，4，1）	0.571	0.143	0.082
5	BCH（15，5，3）	0.333	0.200	0.067
9	BCH（31，11，5）	0.355	0.161	0.057
15	BCH（63，36，5）	0.571	0.079	0.045
18	BCH（63，18，10）	0.286	0.159	0.045

图2 极短码和BCH码的编码效能比较

Fig.2 Comparison of coding efficiency between very short code and BCH code

图3 BCH（63，18，10）编码点图

Fig. 3 BCH（63，18，10） coding point diagram

图4 极短码编码点图

Fig. 4 Very short code coding point diagram

图5 随机块状污染情况下的码识别准确率

Fig. 5 Code recognition accuracy in case of random block pollution

图6 解码时间

Fig. 6 Decoding time

参考文献 17

1	金绍港. 基于嵌套二维码的车载旋翼无人机自主跟踪与降落技术研究［D］. 长沙：国防科学技术大学， 2016：32.
	JIN S G. Autonomous tracking and landing for vehicle quadrocopters based on nested 2D tag［D］. Changsha： National University of Defense Technology， 2016：32.
2	周晓伟. 二维条码识别技术研究［D］. 上海：上海交通大学，2007：1.
	ZHOU X W. The research of two-dimension barcode recognition technology［D］. Shanghai： Shanghai Jiao Tong University， 2007：1.
3	屈也频，刘坚强，侯旺. 单目视觉高精度测量中的合作目标图形设计［J］. 光学学报， 2020， 40（13）：124-131. 10.3788/aos202040.1315001
	QU Y P， LIU J Q， HOU W. Graphics design of cooperative targets on monocular vision high precision measurement［J］. Acta Optica Sinica， 2020， 40（13）：124-131. 10.3788/aos202040.1315001
4	冯桂，周林. 信息论与编码［M］. 北京：清华大学出版社， 2016：230.
	FENG G， ZHOU L. Information Theory and Coding［M］. Beijing： Tsinghua University Press， 2016：230.
5	王育民，李晖. 信息论与编码理论［M］. 2版. 北京：高等教育出版社， 2013：250-280.
	WANG Y M， LI H. Information Theory and Coding Theory［M］. 2nd ed. Beijing： Higher Education Press， 2013：250-280.
6	于英政. QR二维码相关技术的研究［D］. 北京：北京交通大学， 2014：1-20. 10.3969/j.issn1672-9722.2014.12.031
	YU Y Z. Research on related technologies of the QR 2-dimensional code［D］. Beijing： Beijing Jiaotong University， 2014：1-20. 10.3969/j.issn1672-9722.2014.12.031
7	冯汉禄，黄颖为，牛晓娇，等. QR码纠错码原理及实现［J］. 计算机应用， 2011， 31（S1）：40-42.
	FENG H L， HUANG Y W， NIU X J， et al. Principle and implementation of error correcting coding of QR code［J］. Journal of Computer Applications， 2011， 31（S1）：40-42.
8	国家质量技术监督局. 快速响应矩阵码：［S］. 北京：中国标准出版社， 2000.
	State Bureau of Quality and Technical Supervision. QR code：［S］. Beijing： Standards Press of China， 2000.
9	廖景辉. 高纠错性能二维码的研究与实现［D］. 杭州：中国计量大学， 2018：10-50. 10.20964/2018.09.44
	LIAO J H. Research and implementation of a novel two-dimensional bar code with high performance error correction［D］. Hangzhou： China Jiliang University， 2018：10-50. 10.20964/2018.09.44
10	甘志坚，方俊彬，官贺元，等. 复杂光照下QR码图像二值化算法研究及应用［J］. 应用光学， 2018， 39（5）：7. 10.5768/jao201839.0502002
	GAN Z J， FANG J B， GUANG H Y， et al. Research and application of binarization algorithm of QR code image under complex illumination［J］. Journal of Applied Optics， 2018， 39（5）：667-673. 10.5768/jao201839.0502002
11	张湘贤，杨涛，魏东梅，等. 并行高效BCH译码器设计及FPGA实现［J］. 计算机应用， 2012， 32（3）：867-869， 873. 10.3724/sp.j.1087.2012.00867
	ZHANG X X， YANG T， WEI D M， et al. Design and FPGA implementation of parallel high-efficiency BCH decoder［J］. Journal of Computer Applications， 2012， 32（3）：867-869， 873. 10.3724/sp.j.1087.2012.00867
12	蔡恒，崔雪楠，孟虹兆，等. BCH编译码器的FPGA设计及SoPC验证［J］. 电子技术应用， 2012， 38（6）：15-17. 10.3969/j.issn.0258-7998.2012.06.008
	CAI H， CUI X N， MENG H Z， et al. FPGA design and SoPC verification of BCH encoder/decoder［J］. Application of Electronic Technique， 2012， 38（6）：15-17. 10.3969/j.issn.0258-7998.2012.06.008
13	任亚博，张健，刘以农，等. 误码条件下BCH码的盲识别方法［J］. 计算机应用， 2014， 34（12）：3618-3620， 3623.
	REN Y B， ZHANG J， LIU Y N， et al. Blind recognition of BCH codes under error conditions［J］. Journal of Computer Applications， 2014， 34（12）： 3618-3620， 3623.
14	吴昭军，张立民，钟兆根，等. 基于平均余弦符合度下的本原BCH码盲识别［J］. 通信学报， 2020， 41（1）：15-24. 10.11959/j.issn.1000-436x.2020022
	WU Z J， ZHANG L M， ZHONG Z G， et al. Blind recognition of primitive BCH code based on average cosine conformity［J］. Journal on Communications， 2020， 41（1）：15-24. 10.11959/j.issn.1000-436x.2020022
15	曹济英. 复杂场景下二维码的高速稳定识别［D］. 南京：南京大学， 2018：10-67.
	CAO J Y. High-speed stable identification of 2D barcode in complex scenes［D］. Nanjing： Nanjing University， 2018：10-67.
16	张多利，姚永彤，宋宇鲲，等. 缩短BCH码的快速编译码方法和硬件优化设计［J］. 合肥工业大学学报：自然科学版， 2019， 42（12）：1655-1670.
	ZHANG D L， YAO Y T， SONG Y K， et al. Fast encoding and decoding method and hardware optimization design for shortened BCH code［J］. Journal of Hefei University of Technology （Natural Science）， 2019， 42（12）：1655-1670.
17	WELCH L， SCHOLTZ R. Continued fractions and Berlekamp’s algorithm［J］. IEEE Transactions on Information Theory， 1979， 25（1）：19-27. 10.1109/tit.1979.1055987

[1]	栾佳宁, 张伟, 孙伟, 张奥, 韩冬. 基于二维码视觉与激光雷达融合的高精度定位算法[J]. 计算机应用, 2021, 41(5): 1484-1491.
[2]	胡章芳, 曾林全, 罗元, 罗鑫, 赵立明. 融入二维码信息的自适应蒙特卡洛定位算法[J]. 计算机应用, 2019, 39(4): 989-993.
[3]	汪月云, 黄微, 王睿. 基于薄云厚度分布评估的遥感影像高保真薄云去除方法[J]. 计算机应用, 2018, 38(12): 3596-3600.
[4]	任方, 郑东. 基于纠错码的健壮性图像信息隐藏算法[J]. 计算机应用, 2015, 35(7): 1903-1907.
[5]	徐玲蒋新志张杰. 手机二维码识别系统的设计与实现[J]. 计算机应用, 2012, 32(05): 1474-1476.
[6]	孔劼蔡皖东. Kad网络的联合污染模型[J]. 计算机应用, 2011, 31(08): 2152-2155.
[7]	张菁. 基于两代树的低密度校验码校验矩阵构造方法[J]. 计算机应用, 2011, 31(04): 945-947.
[8]	沈时军李三立. 基于P2P的视频点播系统的存储设计[J]. 计算机应用, 2011, 31(01): 187-189.

基于全局距离最优的抗污染极短纠错码设计

Design of very short antipollution error correcting code based on global distance optimization

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 17

相关文章 8

编辑推荐

Metrics