王浩奔，鄒德財，盧曉春

?

一種基于Android平臺的LDPC譯碼軟件的設(shè)計與開發(fā)

王浩奔1,2，鄒德財1,3，盧曉春1,3

（1. 中國科學(xué)院 國家授時中心，西安 710600；2. 中國科學(xué)院大學(xué)，北京 100049；3. 中國科學(xué)院 精密導(dǎo)航定位與定時技術(shù)重點實驗室，西安 710600）

設(shè)計了一種基于Android平臺的LDPC譯碼軟件。使用Smart210作為硬件平臺，利用已有理論基礎(chǔ)(LDPC置信傳播譯碼算法)以及軟件技術(shù)，開發(fā)了一種圖形界面輸入和顯示譯碼結(jié)果的軟件。闡述了Android軟件開發(fā)的相關(guān)步驟和核心概念，最后開發(fā)了相應(yīng)的測試系統(tǒng)對軟件性能和譯碼結(jié)果進行了測試，結(jié)果表明開發(fā)工作是成功的。

Android；LDPC譯碼；軟件開發(fā)

0 引言

本課題依托于中國科學(xué)院國家授時中心承研的國家級項目“北斗高精度廣域增強服務(wù)系統(tǒng)”。該項目旨在建立北斗高精度廣域增強服務(wù)系統(tǒng)平臺，產(chǎn)生經(jīng)LDPC編碼的北斗星基廣域增強服務(wù)信息，將編碼后的信息進行調(diào)制由地面站上行發(fā)射并由轉(zhuǎn)發(fā)式衛(wèi)星載荷播發(fā)，北斗導(dǎo)航增強一體化接收機同時接收、處理北斗導(dǎo)航信息和北斗高精度廣域增強服務(wù)信息，實現(xiàn)分米級或厘米級的北斗高精度廣域增強服務(wù)。

北斗導(dǎo)航增強一體化接收機是北斗高精度廣域增強服務(wù)系統(tǒng)服務(wù)性能的最終體現(xiàn)和驗證手段。北斗導(dǎo)航增強一體化接收機需要接收北斗導(dǎo)航信號和由國家授時中心提供的北斗導(dǎo)航增強信息，用后者實現(xiàn)對北斗導(dǎo)航定位結(jié)果的增強，進行實時PPP定位，實現(xiàn)分米級的高精度位置服務(wù)和在線地圖匹配。

項目要求該接收機需具備操作方便、體積小、可擴展性強等特點，可應(yīng)用于多種場合，并滿足不同用戶的需求。基于項目對接收機的設(shè)計和要求，將北斗導(dǎo)航增強一體化接收機設(shè)計為一款基于Android平臺的高精度可移動導(dǎo)航定位終端，圖1為整個系統(tǒng)的組成框圖，可劃分為4個主要模塊：天線（包括C波段天線和L波段天線）、C波段信道模塊、北斗/GNSS導(dǎo)航信號處理模塊、基于嵌入式Android平臺的高精度定位綜合數(shù)據(jù)處理模塊（含LDPC譯碼單元和數(shù)據(jù)處理單元）。

圖1 北斗導(dǎo)航增強一體化接收機組成框圖

北斗導(dǎo)航增強一體化接收機將接收到的攜帶LDPC編碼增強信息的C波段導(dǎo)航增強信號，經(jīng)C波段信號處理模塊后，通過串口或網(wǎng)口將信號傳輸給嵌入式Android平臺，該平臺將接收到的數(shù)據(jù)流進行LDPC譯碼后恢復(fù)出增強信息，從而實現(xiàn)高精度定位服務(wù)。

LDPC碼由R. Gallager于1962年在博士論文《Low-Density Check-Parity Code》[1]中提出，并且證實了LDPC碼是具有漸近特性的好碼[2]。該碼是一類基于校驗矩陣定義的線性分組碼，在置信傳播譯碼算法下可以取得逼近香農(nóng)限的性能。LDPC碼具有較好的編碼增益，可以改善惡劣環(huán)境下信號的傳輸質(zhì)量，在高速移動通信、無線網(wǎng)絡(luò)高速化、數(shù)字衛(wèi)星發(fā)送方面具有很好的應(yīng)用前景。同時由于具有缺損補償功能、計算量少等優(yōu)點，可以用來作為遺失封包的恢復(fù)[3]。

隨著人們對LDPC碼的不斷深入探究及其成功應(yīng)用在新一代數(shù)字衛(wèi)星信道編碼中，LDPC碼的應(yīng)用價值越來越受到人們的重視，同時LDPC譯碼軟件的設(shè)計也成為了近年來研究的熱點[4-8]。目前，LDPC譯碼軟件多采用FPGA（field programmable gate array）來實現(xiàn)，該方法是通過對硬件電路的設(shè)計來完成的，其優(yōu)點是可以應(yīng)對大量的矩陣運算，執(zhí)行效率高。缺點是其時序難規(guī)劃，掉電后原有邏輯配置會丟失且易用性不強。另一種方式是通過DSP（digital signal processor）來實現(xiàn)，其優(yōu)勢是具有軟件編程的靈活性，運算速度快。缺點是DSP作為專門的微處理器外設(shè)很少，用途較單一。而在實際應(yīng)用中，系統(tǒng)的集成度越來越高，需要處理的事務(wù)也越來越多，在單一平臺上不僅需要較強的運算和執(zhí)行任務(wù)的能力，而且在系統(tǒng)功耗、通用性以及人機交互方面都提出了更高的要求。

本課題正是基于此需求和背景，設(shè)計和開發(fā)了一種基于Android平臺的LDPC譯碼軟件。該譯碼軟件所采用的硬件平臺（smart210）不僅具有高性能的運算能力（每秒運算2億條指令集），滿足譯碼的速度要求；而且具有豐富的外設(shè)和多種接口，可以用來進行多種配套程序的開發(fā)。同時其軟件的研發(fā)是基于Android系統(tǒng)來完成的，與傳統(tǒng)的基于FPGA或DSP的實現(xiàn)方式相比，具有更高的靈活性、可移植性、可操作性和人機交互特性。

本文所研究的內(nèi)容涉及基于Android平臺硬件架構(gòu)的北斗導(dǎo)航增強一體化接收機高精度定位綜合數(shù)據(jù)處理模塊中的LDPC譯碼單元。因此，首先需要對接收到的數(shù)據(jù)進行預(yù)處理，以適應(yīng)譯碼算法的需求；然后編程實現(xiàn)LDPC譯碼算法，對預(yù)處理后的數(shù)據(jù)進行譯碼，恢復(fù)出增強信息；為增強軟件的可操作性和可讀性，設(shè)計開發(fā)了軟件操作輸入界面和輸出界面，便于在接收機界面直接進行相關(guān)操作。

1 LDPC碼的BP譯碼算法

依據(jù)項目總體設(shè)計和論證的結(jié)果，本文采用BP（belief propagation）譯碼算法，其核心思想是所有碼元在校驗節(jié)點和變量節(jié)點之間不停迭代、更新。迭代的過程分為兩步：變量節(jié)點信息處理以及校驗節(jié)點信息處理。每個變量節(jié)點從相近處的校驗節(jié)點接收信息并處理，然后再返還給校驗節(jié)點；校驗節(jié)點也進行相同的過程；最后由變量節(jié)點根據(jù)所收集的信息判決[9]。具體過程如下所述：

1）初始化：

對應(yīng)的消息傳遞過程如圖2所示。

圖2 初始化消息傳遞圖

2）迭代處理過程：

（3）

該更新過程所對應(yīng)的Tanner圖中消息傳遞過程如圖3所示。

圖3 校驗節(jié)點消息傳遞圖

消息傳遞在變量節(jié)點中的過程如圖4所示。

圖4 變量節(jié)點消息傳遞圖

4）嘗試譯碼判決：

對所有碼字中的每一位按式（7）進行判決：

利用Android軟硬件平臺實現(xiàn)該算法時，重點是要實現(xiàn)校驗節(jié)點信息和變量節(jié)點信息的更新，本文針對這兩個環(huán)節(jié)進行了詳細說明。

2 所選用的軟硬件平臺

2.1 硬件平臺

本文選用Smart210作為硬件平臺，Smart210選用三星S5PV210作為主處理器，基于CortexTM-A8內(nèi)核，運行主頻1GHz，配有512M內(nèi)存和512M閃存（SLC），使用單通道32bits數(shù)據(jù)總線，運行頻率可達200MHz。同時搭載有豐富的外設(shè)和各種接口，便于北斗導(dǎo)航增強一體化接收機的其他模塊/單元間進行數(shù)據(jù)通信。

2.2 軟件平臺

譯碼軟件選用的軟件平臺為嵌入式Android操作系統(tǒng)。其系統(tǒng)架構(gòu)分為4層，從下到上依次為：內(nèi)核層、函數(shù)層、應(yīng)用程序框架層以及應(yīng)用程序?qū)?。它采用的這種軟件層疊的方式使得層與層之間相互分離，這種分工保證當其中的某一層發(fā)生改變時，其他層的程序無需作調(diào)整。

本課題選用的版本為較為穩(wěn)定的Android4.0，除保持源碼的開源特性外重新設(shè)計了人性化UI界面。采用Linux3.0的內(nèi)核，使其運行速度比Android3.1提升1.8倍，針對多核處理器進行了專門優(yōu)化，充分發(fā)揮雙核的性能。

3 LDPC譯碼軟件在Android中的實現(xiàn)

本課題所使用的開發(fā)環(huán)境是Eclipse集成開發(fā)環(huán)境，里面集成了Android開發(fā)所需要的SDK，ADT以及NDK等。使用JAVA作為開發(fā)語言。

Android具有完整的軟件架構(gòu)，它采用的是一種層與層之間相互分離的疊層方式進行構(gòu)建。這種架構(gòu)使得層與層之間的耦合度非常低，下層結(jié)構(gòu)的改變不會對上層產(chǎn)生影響。本課題所進行的開發(fā)是在應(yīng)用層進行的。程序主要由輸入界面顯示模塊、數(shù)據(jù)收集和預(yù)處理模塊、數(shù)據(jù)處理模塊、以及顯示模塊等4部分組成。下面分別對這幾部分功能以及實現(xiàn)的方法做介紹。

3.1 輸入界面顯示模塊

輸入界面是該程序的主界面，是進入軟件后首先呈現(xiàn)給用戶的，該部分設(shè)計主要考慮的是用戶的視覺體驗和操作體驗，輸入界面如圖6所示。

圖6 輸入界面

該布局文件采用的是絕對布局與線性布局結(jié)合的方式，所采用的組件有TextView，EditView， Button等。通過EditView來實現(xiàn)數(shù)據(jù)的輸入，EditView是文本編輯框，支持文本輸入。其最重要的屬性為inputType，目前inputType支持的屬性有多種。結(jié)合LDPC譯碼算法、接收數(shù)據(jù)格式、對接收數(shù)據(jù)的處理流程，為保障軟件的運行效率和軟件功能性能的正確性，本文所采用的屬性主要有“number signed”，“text”，“number decimal”等。

Button組件的設(shè)計使用了Android Button Maker工具，Android Button Maker是一個在線生成Android應(yīng)用按鈕代碼的工具。Android的API提供可繪制資源，其中的xml文件定義的幾何形狀，包括顏色、邊框和梯度。這些按鈕是在shape drawable xml代碼基礎(chǔ)上產(chǎn)生的，相比通常的PNG按鈕加載速度更具有更快的加載速度。

3.2 數(shù)據(jù)的收集及預(yù)處理

軟件處理所需的數(shù)據(jù)可由后臺直接通過總線接口輸入，也可由界面手工輸入。為增加演示性，本文采用界面輸入方式。所需要輸入的數(shù)據(jù)有：校驗矩陣、調(diào)制輸入、噪聲標準差以及最大循環(huán)次數(shù)。由于其輸入的數(shù)字類型不同，為避免錯誤的輸入給計算帶來差錯，通過在布局文件中加入android:digits屬性來限制其輸入的字符，例如，在校驗矩陣中加入android:digits="01"屬性，表示其只能輸入0和1。輸入字符后界面的顯示效果如圖7所示。

圖7 輸入數(shù)據(jù)后界面顯示效果圖

由于EditView只能接收字符數(shù)據(jù)，所以輸入的字符首先要先轉(zhuǎn)換成Integer型或Double型，才可以進行后面的計算，在校驗矩陣中，輸入的是1或0，因此需要將其轉(zhuǎn)換成Integer，所用到的方法為：

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

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

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

在噪聲和最大循環(huán)次數(shù)中，由于其輸入都為小數(shù)，所以需要將其轉(zhuǎn)化為Double型，所用到的方法為：

//最大循環(huán)次數(shù)預(yù)處理

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

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

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

//噪聲預(yù)處理

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

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

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

3.3 數(shù)據(jù)處理模塊

該譯碼軟件數(shù)據(jù)處理模塊采用的是對數(shù)似然比置信傳播譯碼算法（LLR BP），該算法已在第一部分做了詳細的描述，實現(xiàn)的過程包括以下5個步驟：①初始化，②校驗節(jié)點更新，③變量節(jié)點更新，④判決，⑤停止。譯碼流程如圖8所示。

圖8 譯碼算法程序流程圖

3.3.1 初始化數(shù)據(jù)

初始化為計算經(jīng)信道傳輸后各變量節(jié)點的初始概率信息，同時對每個變量節(jié)點求傳遞給與其相鄰的校驗節(jié)點的初始概率信息，根據(jù)BP譯碼算法，初始化過程核心代碼如下：

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

Lq[i] = 2.0 * y[i] / sigma; //變量節(jié)點接收從信道傳過來的信息

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

{

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

L_q[i][j] = Lq[j]; //將L_q賦值為一個rows*cols矩陣

//對每個變量節(jié)點求其傳遞給與其相鄰的校驗節(jié)點的可靠性信息

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

}

}

3.3.2 校驗節(jié)點信息更新

校驗節(jié)點的更新就是每個校驗節(jié)點在接收到變量節(jié)點傳遞過來的信息后進行處理，并返回一個新的可靠性信息給與其相鄰的變量節(jié)點，程序?qū)崿F(xiàn)的流程如圖9所示。

圖9 校驗節(jié)點信息更新程序?qū)崿F(xiàn)流程圖

3.3.3 變量節(jié)點信息更新

變量節(jié)點的信息處理就是將變量節(jié)點傳遞給與其相連的校驗節(jié)點的可靠性信息，程序的實現(xiàn)流程如圖10所示。

圖10 變量節(jié)點信息更新程序?qū)崿F(xiàn)流程圖

3.4 輸出顯示模塊

考慮到顯示的視覺效果，將結(jié)果顯示到另一個Activity中，一個Android應(yīng)用通常會包含多個Activity，但只有一個作為程序的入口，當該程序執(zhí)行時會自動啟動并執(zhí)行該Activity。要想啟動其他的Activity，通常都由入口的Activity啟動。

Activity之間通過Intent消息進行數(shù)據(jù)傳遞，Intent是Activity進行數(shù)據(jù)傳遞的方式，實際數(shù)據(jù)封裝在Bundle對象中，Intent只負責(zé)在Activity之間傳遞Bundle對象。它們之間的關(guān)系如圖11所示。

圖11 Activity之間的消息傳遞方式

將譯碼結(jié)果封裝到Intent的Bundle中，傳遞到另一個Activity中，通過getIntent().getIntArrayExtra()，得到譯碼結(jié)果，再通過TV1.setText(Integer.toString())將譯碼結(jié)果轉(zhuǎn)換為字符型數(shù)據(jù)顯示到屏幕上，效果如圖12所示。

圖12 譯碼結(jié)果輸出

4 系統(tǒng)測試及譯碼結(jié)果分析

為了驗證譯碼結(jié)果的準確性，開發(fā)PC端的測試平臺，軟件采用MatlabGUI來編寫，使用串口來實現(xiàn)PC與嵌入式平臺的通信，包含的模塊有串口參數(shù)設(shè)置模塊、信源產(chǎn)生模塊、編碼及信道模塊、譯碼接收模塊、結(jié)果分析模塊。PC端的測試軟件界面如圖13所示。

圖13 測試軟件界面

測試系統(tǒng)使用Matlab函數(shù)庫中的randn()函數(shù)來產(chǎn)生隨機信源，使用高斯消元法編碼，采用BPSK（binary phase shift keying）調(diào)制，通過AWAG（additive white gaussian noise）信道，噪聲方差設(shè)置為0.5，最大循環(huán)次數(shù)設(shè)置為50，對基于Android平臺的譯碼軟件進行性能測試，過程如圖14所示。

圖14 譯碼軟件性能測試過程圖

由測試系統(tǒng)經(jīng)過串口向譯碼軟件發(fā)送已調(diào)序列，之后由譯碼軟件對已調(diào)序列進行譯碼，譯碼結(jié)束后由串口返回判決信息到測試系統(tǒng)進行差錯統(tǒng)計，將統(tǒng)計的結(jié)果顯示在PC上，從而求得譯碼軟件的誤碼率。經(jīng)驗證該譯碼軟件誤碼率小于10-5，與Matlab仿真結(jié)果相同，滿足譯碼軟件設(shè)計的性能要求，說明對BP算法在Android平臺下的設(shè)計和實現(xiàn)是成功的。

5 結(jié)語

本文從項目需求和易用性角度出發(fā)，設(shè)計并開發(fā)了一種基于Android平臺的LDPC譯碼軟件，該譯碼軟件可直接應(yīng)用于北斗導(dǎo)航一體化接收機中的高精度定位綜合數(shù)據(jù)處理模塊中。通過測試表明，該軟件穩(wěn)定、準確、可靠。譯碼軟件可自由設(shè)置譯碼循環(huán)次數(shù)。但還存在局限性，例如參數(shù)設(shè)置位數(shù)固定，軟件的界面難以適應(yīng)不同尺寸屏幕。計劃在后續(xù)的工作中作進一步改進。

[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碼及其應(yīng)用[J]. 通信技術(shù), 2007, 40(9): 11-12, 28.

[4] 陳蓉. LDPC編譯碼的DSP實現(xiàn)[D]. 蘭州: 蘭州大學(xué), 2009.

[5] 張霖, 趙旦峰, 薛睿, 等. 基于BP算法的QC_LDPC譯碼器的DSP實現(xiàn)[J]. 應(yīng)用科技. 2011, 38(3): 34-37.

[6] 黃河. LDPC碼編譯碼技術(shù)及其應(yīng)用研究[D]. 杭州: 杭州電子科技大學(xué), 2012.

[7] 許渤, 丁宏. 一種LDPC碼在光纖通信系統(tǒng)中的性能分析[J]. 光通信研究, 2007, 143(5): 1-3.

[8] 包秋艷. 基于IEEE802.16e協(xié)議的LDPC碼編譯碼算法的研究[D]. 西安: 西安電子科技大學(xué), 2011.

[9] 蘇兆忠. LDPC碼在DMB-TH系統(tǒng)下的研究與實現(xiàn)[D]. 西安: 西安電子科技大學(xué), 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

國家自然科學(xué)基金資助項目（11203027）

王浩奔，男，碩士，主要從事嵌入式技術(shù)研究。