一种基于Android平台的LDPC译码软件的设计与开发

王浩奔，邹德财，卢晓春



一种基于Android平台的LDPC译码软件的设计与开发

王浩奔1,2，邹德财1,3，卢晓春1,3

（1. 中国科学院 国家授时中心，西安 710600；2. 中国科学院大学，北京 100049；3. 中国科学院 精密导航定位与定时技术重点实验室，西安 710600）

设计了一种基于Android平台的LDPC译码软件。使用Smart210作为硬件平台，利用已有理论基础(LDPC置信传播译码算法)以及软件技术，开发了一种图形界面输入和显示译码结果的软件。阐述了Android软件开发的相关步骤和核心概念，最后开发了相应的测试系统对软件性能和译码结果进行了测试，结果表明开发工作是成功的。

Android；LDPC译码；软件开发

0 引言

本课题依托于中国科学院国家授时中心承研的国家级项目“北斗高精度广域增强服务系统”。该项目旨在建立北斗高精度广域增强服务系统平台，产生经LDPC编码的北斗星基广域增强服务信息，将编码后的信息进行调制由地面站上行发射并由转发式卫星载荷播发，北斗导航增强一体化接收机同时接收、处理北斗导航信息和北斗高精度广域增强服务信息，实现分米级或厘米级的北斗高精度广域增强服务。

北斗导航增强一体化接收机是北斗高精度广域增强服务系统服务性能的最终体现和验证手段。北斗导航增强一体化接收机需要接收北斗导航信号和由国家授时中心提供的北斗导航增强信息，用后者实现对北斗导航定位结果的增强，进行实时PPP定位，实现分米级的高精度位置服务和在线地图匹配。

项目要求该接收机需具备操作方便、体积小、可扩展性强等特点，可应用于多种场合，并满足不同用户的需求。基于项目对接收机的设计和要求，将北斗导航增强一体化接收机设计为一款基于Android平台的高精度可移动导航定位终端，图1为整个系统的组成框图，可划分为4个主要模块：天线（包括C波段天线和L波段天线）、C波段信道模块、北斗/GNSS导航信号处理模块、基于嵌入式Android平台的高精度定位综合数据处理模块（含LDPC译码单元和数据处理单元）。

图1 北斗导航增强一体化接收机组成框图

北斗导航增强一体化接收机将接收到的携带LDPC编码增强信息的C波段导航增强信号，经C波段信号处理模块后，通过串口或网口将信号传输给嵌入式Android平台，该平台将接收到的数据流进行LDPC译码后恢复出增强信息，从而实现高精度定位服务。

LDPC码由R. Gallager于1962年在博士论文《Low-Density Check-Parity Code》[1]中提出，并且证实了LDPC码是具有渐近特性的好码[2]。该码是一类基于校验矩阵定义的线性分组码，在置信传播译码算法下可以取得逼近香农限的性能。LDPC码具有较好的编码增益，可以改善恶劣环境下信号的传输质量，在高速移动通信、无线网络高速化、数字卫星发送方面具有很好的应用前景。同时由于具有缺损补偿功能、计算量少等优点，可以用来作为遗失封包的恢复[3]。

随着人们对LDPC码的不断深入探究及其成功应用在新一代数字卫星信道编码中，LDPC码的应用价值越来越受到人们的重视，同时LDPC译码软件的设计也成为了近年来研究的热点[4-8]。目前，LDPC译码软件多采用FPGA（field programmable gate array）来实现，该方法是通过对硬件电路的设计来完成的，其优点是可以应对大量的矩阵运算，执行效率高。缺点是其时序难规划，掉电后原有逻辑配置会丢失且易用性不强。另一种方式是通过DSP（digital signal processor）来实现，其优势是具有软件编程的灵活性，运算速度快。缺点是DSP作为专门的微处理器外设很少，用途较单一。而在实际应用中，系统的集成度越来越高，需要处理的事务也越来越多，在单一平台上不仅需要较强的运算和执行任务的能力，而且在系统功耗、通用性以及人机交互方面都提出了更高的要求。

本课题正是基于此需求和背景，设计和开发了一种基于Android平台的LDPC译码软件。该译码软件所采用的硬件平台（smart210）不仅具有高性能的运算能力（每秒运算2亿条指令集），满足译码的速度要求；而且具有丰富的外设和多种接口，可以用来进行多种配套程序的开发。同时其软件的研发是基于Android系统来完成的，与传统的基于FPGA或DSP的实现方式相比，具有更高的灵活性、可移植性、可操作性和人机交互特性。

本文所研究的内容涉及基于Android平台硬件架构的北斗导航增强一体化接收机高精度定位综合数据处理模块中的LDPC译码单元。因此，首先需要对接收到的数据进行预处理，以适应译码算法的需求；然后编程实现LDPC译码算法，对预处理后的数据进行译码，恢复出增强信息；为增强软件的可操作性和可读性，设计开发了软件操作输入界面和输出界面，便于在接收机界面直接进行相关操作。

1 LDPC码的BP译码算法

依据项目总体设计和论证的结果，本文采用BP（belief propagation）译码算法，其核心思想是所有码元在校验节点和变量节点之间不停迭代、更新。迭代的过程分为两步：变量节点信息处理以及校验节点信息处理。每个变量节点从相近处的校验节点接收信息并处理，然后再返还给校验节点；校验节点也进行相同的过程；最后由变量节点根据所收集的信息判决[9]。具体过程如下所述：

1）初始化：

对应的消息传递过程如图2所示。

图2 初始化消息传递图

2）迭代处理过程：

（3）

该更新过程所对应的Tanner图中消息传递过程如图3所示。

图3 校验节点消息传递图

消息传递在变量节点中的过程如图4所示。

图4 变量节点消息传递图

4）尝试译码判决：

对所有码字中的每一位按式（7）进行判决：

利用Android软硬件平台实现该算法时，重点是要实现校验节点信息和变量节点信息的更新，本文针对这两个环节进行了详细说明。

2 所选用的软硬件平台

2.1 硬件平台

本文选用Smart210作为硬件平台，Smart210选用三星S5PV210作为主处理器，基于CortexTM-A8内核，运行主频1GHz，配有512M内存和512M闪存（SLC），使用单通道32bits数据总线，运行频率可达200MHz。同时搭载有丰富的外设和各种接口，便于北斗导航增强一体化接收机的其他模块/单元间进行数据通信。

2.2 软件平台

译码软件选用的软件平台为嵌入式Android操作系统。其系统架构分为4层，从下到上依次为：内核层、函数层、应用程序框架层以及应用程序层。它采用的这种软件层叠的方式使得层与层之间相互分离，这种分工保证当其中的某一层发生改变时，其他层的程序无需作调整。

本课题选用的版本为较为稳定的Android4.0，除保持源码的开源特性外重新设计了人性化UI界面。采用Linux3.0的内核，使其运行速度比Android3.1提升1.8倍，针对多核处理器进行了专门优化，充分发挥双核的性能。

3 LDPC译码软件在Android中的实现

本课题所使用的开发环境是Eclipse集成开发环境，里面集成了Android开发所需要的SDK，ADT以及NDK等。使用JAVA作为开发语言。

Android具有完整的软件架构，它采用的是一种层与层之间相互分离的叠层方式进行构建。这种架构使得层与层之间的耦合度非常低，下层结构的改变不会对上层产生影响。本课题所进行的开发是在应用层进行的。程序主要由输入界面显示模块、数据收集和预处理模块、数据处理模块、以及显示模块等4部分组成。下面分别对这几部分功能以及实现的方法做介绍。

3.1 输入界面显示模块

输入界面是该程序的主界面，是进入软件后首先呈现给用户的，该部分设计主要考虑的是用户的视觉体验和操作体验，输入界面如图6所示。

图6 输入界面

该布局文件采用的是绝对布局与线性布局结合的方式，所采用的组件有TextView，EditView， Button等。通过EditView来实现数据的输入，EditView是文本编辑框，支持文本输入。其最重要的属性为inputType，目前inputType支持的属性有多种。结合LDPC译码算法、接收数据格式、对接收数据的处理流程，为保障软件的运行效率和软件功能性能的正确性，本文所采用的属性主要有“number signed”，“text”，“number decimal”等。

Button组件的设计使用了Android Button Maker工具，Android Button Maker是一个在线生成Android应用按钮代码的工具。Android的API提供可绘制资源，其中的xml文件定义的几何形状，包括颜色、边框和梯度。这些按钮是在shape drawable xml代码基础上产生的，相比通常的PNG按钮加载速度更具有更快的加载速度。

3.2 数据的收集及预处理

软件处理所需的数据可由后台直接通过总线接口输入，也可由界面手工输入。为增加演示性，本文采用界面输入方式。所需要输入的数据有：校验矩阵、调制输入、噪声标准差以及最大循环次数。由于其输入的数字类型不同，为避免错误的输入给计算带来差错，通过在布局文件中加入android:digits属性来限制其输入的字符，例如，在校验矩阵中加入android:digits="01"属性，表示其只能输入0和1。输入字符后界面的显示效果如图7所示。

图7 输入数据后界面显示效果图

由于EditView只能接收字符数据，所以输入的字符首先要先转换成Integer型或Double型，才可以进行后面的计算，在校验矩阵中，输入的是1或0，因此需要将其转换成Integer，所用到的方法为：

android:id="@+id/editText1";

EditText ET1=(EditText)findViewById(R.id.editText1);

H[0][0]=Integer.parseInt(ET1.getText().toString());

在噪声和最大循环次数中，由于其输入都为小数，所以需要将其转化为Double型，所用到的方法为：

//最大循环次数预处理

android:id="@+id/editText41";

EditText ET42=(EditText)findViewById(R.id.editText42);

imax=Integer.parseInt(ET42.getText().toString());

//噪声预处理

android:id="@+id/editText42";

EditText ET41=(EditText)findViewById(R.id.editText41);

sigma=Double.parseDouble(ET41.getText().toString());

3.3 数据处理模块

该译码软件数据处理模块采用的是对数似然比置信传播译码算法（LLR BP），该算法已在第一部分做了详细的描述，实现的过程包括以下5个步骤：①初始化，②校验节点更新，③变量节点更新，④判决，⑤停止。译码流程如图8所示。

图8 译码算法程序流程图

3.3.1 初始化数据

初始化为计算经信道传输后各变量节点的初始概率信息，同时对每个变量节点求传递给与其相邻的校验节点的初始概率信息，根据BP译码算法，初始化过程核心代码如下：

for (int i = 0; i < cols; i++)

Lq[i] = 2.0 * y[i] / sigma; //变量节点接收从信道传过来的信息

for (int i = 0; i < rows; i++)

{

for (int j = 0; j < cols; j++) {

L_q[i][j] = Lq[j]; //将L_q赋值为一个rows*cols矩阵

//对每个变量节点求其传递给与其相邻的校验节点的可靠性信息

L_q[i][j] = L_q[i][j] * H[i][j];

}

}

3.3.2 校验节点信息更新

校验节点的更新就是每个校验节点在接收到变量节点传递过来的信息后进行处理，并返回一个新的可靠性信息给与其相邻的变量节点，程序实现的流程如图9所示。

图9 校验节点信息更新程序实现流程图

3.3.3 变量节点信息更新

变量节点的信息处理就是将变量节点传递给与其相连的校验节点的可靠性信息，程序的实现流程如图10所示。

图10 变量节点信息更新程序实现流程图

3.4 输出显示模块

考虑到显示的视觉效果，将结果显示到另一个Activity中，一个Android应用通常会包含多个Activity，但只有一个作为程序的入口，当该程序执行时会自动启动并执行该Activity。要想启动其他的Activity，通常都由入口的Activity启动。

Activity之间通过Intent消息进行数据传递，Intent是Activity进行数据传递的方式，实际数据封装在Bundle对象中，Intent只负责在Activity之间传递Bundle对象。它们之间的关系如图11所示。

图11 Activity之间的消息传递方式

将译码结果封装到Intent的Bundle中，传递到另一个Activity中，通过getIntent().getIntArrayExtra()，得到译码结果，再通过TV1.setText(Integer.toString())将译码结果转换为字符型数据显示到屏幕上，效果如图12所示。

图12 译码结果输出

4 系统测试及译码结果分析

为了验证译码结果的准确性，开发PC端的测试平台，软件采用MatlabGUI来编写，使用串口来实现PC与嵌入式平台的通信，包含的模块有串口参数设置模块、信源产生模块、编码及信道模块、译码接收模块、结果分析模块。PC端的测试软件界面如图13所示。

图13 测试软件界面

测试系统使用Matlab函数库中的randn()函数来产生随机信源，使用高斯消元法编码，采用BPSK（binary phase shift keying）调制，通过AWAG（additive white gaussian noise）信道，噪声方差设置为0.5，最大循环次数设置为50，对基于Android平台的译码软件进行性能测试，过程如图14所示。

图14 译码软件性能测试过程图

由测试系统经过串口向译码软件发送已调序列，之后由译码软件对已调序列进行译码，译码结束后由串口返回判决信息到测试系统进行差错统计，将统计的结果显示在PC上，从而求得译码软件的误码率。经验证该译码软件误码率小于10-5，与Matlab仿真结果相同，满足译码软件设计的性能要求，说明对BP算法在Android平台下的设计和实现是成功的。

5 结语

本文从项目需求和易用性角度出发，设计并开发了一种基于Android平台的LDPC译码软件，该译码软件可直接应用于北斗导航一体化接收机中的高精度定位综合数据处理模块中。通过测试表明，该软件稳定、准确、可靠。译码软件可自由设置译码循环次数。但还存在局限性，例如参数设置位数固定，软件的界面难以适应不同尺寸屏幕。计划在后续的工作中作进一步改进。

[1] GALLAGER R. Low-density parity-check codes[D]. Boston: MIT Press, 1963: 70-81.

[2] GALLAGER R. Low-density parity-check codes[J]. IRE Trans on Information Theory, 1962, 8(1): 21-28.

[3] 袁李林, 李贵勇. LDPC码及其应用[J]. 通信技术, 2007, 40(9): 11-12, 28.

[4] 陈蓉. LDPC编译码的DSP实现[D]. 兰州: 兰州大学, 2009.

[5] 张霖, 赵旦峰, 薛睿, 等. 基于BP算法的QC_LDPC译码器的DSP实现[J]. 应用科技. 2011, 38(3): 34-37.

[6] 黄河. LDPC码编译码技术及其应用研究[D]. 杭州: 杭州电子科技大学, 2012.

[7] 许渤, 丁宏. 一种LDPC码在光纤通信系统中的性能分析[J]. 光通信研究, 2007, 143(5): 1-3.

[8] 包秋艳. 基于IEEE802.16e协议的LDPC码编译码算法的研究[D]. 西安: 西安电子科技大学, 2011.

[9] 苏兆忠. LDPC码在DMB-TH系统下的研究与实现[D]. 西安: 西安电子科技大学, 2011.

Design and development of LDPC decoding software based on Android platform

WANG Hao-ben1,2, ZOU De-cai1,3, LU Xiao-chun1,3

(1. National Time Service Center, Chinese Academy of Sciences, Xi’an 710600, China;2. University of Chinese Academy of Sciences, Beijing 100049, China;3. Key Laboratory of Precision Navigation and Timing Technology, National Time Service Center, Chinese Academy of Sciences, Xi’an 710600, China)

A piece of LDPC decoding software based on Android platform was designed. The Smart210 was used as the hardware platform, the existing theory (LDPC BP algorithm) and software technology were used to develop a piece of software with graphical interface input and decoding result display. The relevant steps and core concepts for the Android software development are described in this paper. The performance and decoding results for the decoding software were tested by a developed test system, and the result shows that the development is successful.

Android; LDPC decoding; software development

TN919.3+2

A

1674-0637(2017)01-0053-11

10.13875/j.issn.1674-0637.2017-01-0053-11

2016-05-12

国家自然科学基金资助项目（11203027）

王浩奔，男，硕士，主要从事嵌入式技术研究。