王浩奔，鄒德財(cái)，盧曉春

?

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

王浩奔1,2，鄒德財(cái)1,3，盧曉春1,3

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

1 LDPC碼的BP譯碼算法

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

1）初始化：

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

圖2 初始化消息傳遞圖

2）迭代處理過程：

（3）

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

圖3 校驗(yàn)節(jié)點(diǎn)消息傳遞圖

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

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

4）嘗試譯碼判決：

對(duì)所有碼字中的每一位按式（7）進(jìn)行判決：

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

2 所選用的軟硬件平臺(tái)

2.1 硬件平臺(tái)

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

2.2 軟件平臺(tái)

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

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

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

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

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

3.1 輸入界面顯示模塊

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

圖6 輸入界面

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

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

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

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

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

由于EditView只能接收字符數(shù)據(jù)，所以輸入的字符首先要先轉(zhuǎn)換成Integer型或Double型，才可以進(jìn)行后面的計(jì)算，在校驗(yàn)矩陣中，輸入的是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ù)處理模塊采用的是對(duì)數(shù)似然比置信傳播譯碼算法（LLR BP），該算法已在第一部分做了詳細(xì)的描述，實(shí)現(xiàn)的過程包括以下5個(gè)步驟：①初始化，②校驗(yàn)節(jié)點(diǎn)更新，③變量節(jié)點(diǎn)更新，④判決，⑤停止。譯碼流程如圖8所示。

圖8 譯碼算法程序流程圖

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

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

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

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

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

{

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

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

//對(duì)每個(gè)變量節(jié)點(diǎn)求其傳遞給與其相鄰的校驗(yàn)節(jié)點(diǎn)的可靠性信息

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

}

}

3.3.2 校驗(yàn)節(jié)點(diǎn)信息更新

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

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

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

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

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

3.4 輸出顯示模塊

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

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

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

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

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

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

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

圖13 測(cè)試軟件界面

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

圖14 譯碼軟件性能測(cè)試過程圖

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

5 結(jié)語

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

[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實(shí)現(xiàn)[D]. 蘭州: 蘭州大學(xué), 2009.

[5] 張霖, 趙旦峰, 薛睿, 等. 基于BP算法的QC_LDPC譯碼器的DSP實(shí)現(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)下的研究與實(shí)現(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

國(guó)家自然科學(xué)基金資助項(xiàng)目（11203027）

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