logo

SCIENCE CHINA Information Sciences, Volume 60, Issue 10: 102301(2017) https://doi.org/10.1007/s11432-016-9011-8

Fast degree-distribution optimization for BATS codes

More info
  • ReceivedSep 26, 2016
  • AcceptedNov 30, 2016
  • PublishedJul 4, 2017

Abstract

Batched sparse (BATS) codes have been proposed for communication through networks with packet loss. BATS codes include a matrix generalization of fountain codes as the outer code and random linear network coding at the intermediate network nodes as the inner code. BATS codes, however, do not possess a universal degree distribution that achieves an optimal rate for any distribution of the transfer matrix ranks. Therefore, it is important to have a fast degree-distribution optimization approach for finite-length BATS codes. In this paper, we propose the concept of batch release probability (BRP), and demonstrate some characteristics of BRPs from the degree distributions achieving nearly optimal performance. Based on these BRP characteristics, we propose a novel degree-distribution optimization approach that achieves the similar decoding performance with a much shorter optimization time, compared with the previous approach. Moreover, the universality of BRPs observed in this paper can further simplify the degree-distribution optimization of BATS codes.


Acknowledgment

This work was supported by Delay/Disruption Tolerant Communication Technology of the Chinese Academy of Sciences (Grant No. 2015AA703405A), and National Natural Science Foundation of China (Grant No. 61471215).


References

[1] Yang S H, Yeung R W. Coding for a network coded fountain. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Saint-Petersburg, 2011. 2647--2651. Google Scholar

[2] Yang S, Yeung R W. Batched Sparse Codes. IEEE Trans Inform Theor, 2014, 60: 5322-5346 CrossRef Google Scholar

[3] Luby M. LT codes. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Los Alamitos, 2002. 271--280. Google Scholar

[4] Shokrollahi A. Raptor codes. IEEE/ACM Trans Netw, 2006, 14: 2551--2567. Google Scholar

[5] Li S-Y R, Yeung R W, Cai N. Linear network coding. IEEE Trans Inf Theory, 2003, 49: 371--381. Google Scholar

[6] Ho T, Medard M, Koetter R. A random linear network coding approach to multicast. IEEE Trans Inform Theor, 2006, 52: 4413-4430 CrossRef Google Scholar

[7] Lee S, Ma X. Eigenvector-based initial ranging process for OFDMA uplink systems. EURASIP J Adv Signal Process, 2015, 2015: 1-13 CrossRef ADS Google Scholar

[8] Mahdaviani K, Ardakani M, Bagheri H, et al. Gamma codes: a low-overhead linear-complexity network coding solution. In: Proceedings of International Symposium on Network Coding, Cambridge, 2012. 125--130. Google Scholar

[9] Yang S, Tang B. From LDPC to chunked network codes. In: Proceedings of IEEE Information Theory Workshop, Hobart, 2014. 406--410. Google Scholar

[10] Huang Q, Sun K, Li X, et al. Just FUN: a joint fountain coding and network coding approach to loss-tolerant information spreading. In: Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing Philadelphia, 2014. 83--92. Google Scholar

[11] Xu X, Praveen Kumar M S G, Guan Y L. Two-Phase Cooperative Broadcasting Based on Batched Network Code. IEEE Trans Commun, 2016, 64: 706-714 CrossRef Google Scholar

[12] Xu X, Guan Y L. Reliable broadcast to a user group with limited source transmissions. In: Proceedings of IEEE International Conference on Communications, London, 2015. Google Scholar

[13] Yang S, Yeung R W, Cheung J H F, et al. BATS: network coding in action. In: Proceedings of the 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2015. 1204--1211. Google Scholar

[14] Yang S, Ng T C, Yeung R W. Finite-length analysis of BATS codes. In: Proceedings of International Symposium on Network Coding (NetCod), Calgary, 2013. Google Scholar

[15] Smith N A, Tromble R W. Sampling uniformly from the unit simplex. Johns Hopkins University, Tech. Rep, 2004. http://www.cs.cmu.edu/~nasmith/papers/smith+tromble.tr04.pdf. Google Scholar

  • Figure 1

    (Color online) $\boldsymbol{~V}_d$ with different degrees. (a) $d=13,16,20,25,50,150$, and $K=256$; (b) $d=20,\ldots,150$, $K=256$.

  • Figure 2

    (Color online) Example of the linear combination of $\boldsymbol{~V}_d$, (a) $d=17$; (b) $d=17,23$; (c) $d=17,23,33$; (d) $d=17,23,33,50$.

  • Figure 3

    (Color online) Results of Algorithm 1for two given $\boldsymbol{~L}$. The curves without rhombus express the given $\boldsymbol{~L}$. The rhombus curves are the BRP distributions $\boldsymbol{~L}$ of the degree distributions obtained from the Algorithm 1. (a) A horizontal $\boldsymbol{~L}$; (b) BRP distribution of a random degree distribution.

  • Figure 4

    BRP distribution of the robust soliton distribution for the LT code with $K=1024$.

  • Figure 5

    (a) Rank distribution $\boldsymbol{~h}'_1$; (b) rank distribution $\boldsymbol{~h}'_2$; (c) BRP distribution of the degree distribution obtained by the greedy approach for rank distribution $\boldsymbol{~h}'_1$, $K=256$, $M=16$; (d) BRP distribution of the degree distribution obtained by the greedy approach for rank distribution $\boldsymbol{~h}'_2$, $K=256$, $M=16$; (e) the approximate BRP vector of the degree distribution from the greedy approach.

  • Figure 6

    Error probability ${P_{\rm~err}}(n)$ of GE-BP decoding for three degree distributions $\boldsymbol{~\varPsi}^{\mathrm{~asy}}$, $\boldsymbol{~\varPsi}^{\mathrm{~asy}}$ and $\boldsymbol{~\varPsi}^{\mathrm{~asy}}$. (a) $n$ from $1$ to $150$; (b) zoom-in with $n$ from $20$ to $50$.

  • Figure 7

    Expected number of inactive symbols for different degree distributions $\boldsymbol{~\varPsi}^{\mathrm{~asy}}$, $\boldsymbol{~\varPsi}^{\mathrm{~asy}}$ and $\boldsymbol{~\varPsi}^{\mathrm{~asy}}$. (a) $n$ from $1$ to $150$; (b) zoom-in with $n$ from $20$ to $40$.

  • Figure 8

    Some numerical results to demonstrate the universality of the $(v_1,v_2)$. (a) The expected number of inactive symbols for three degree distributions $\boldsymbol{~\varPsi}^{\mathrm{~g\_I^*}}$, $\boldsymbol{~\varPsi}^{\mathrm{~g\_I^*}}$ and $\boldsymbol{~\varPsi}^{\mathrm{~g\_I^*}}$; (b) the empirical distributions of performance ratio $\alpha$ for $2000$ different rank distributions for $(0.015,~0.02)$.

  •   

    Algorithm 1 Transformation from a distribution vector to a degree distribution

    Require:

    • $K,N,M,\boldsymbol{~h}$ are the number of input symbols, number of batches, batch size, and rank distribution, respectively.

    • $\boldsymbol{~L}$ is a length-$K$ distribution vector.

    • $E_1$, $E_2$ are two threshold parameters.

    Output:

    for $d=K$ to $1$

    $\varPsi_d~\Leftarrow~1$

    for $t=0$ to $K-1$

    if $r(t,d)$ $\geq$ $E_1$ and $\boldsymbol{~L}[t]$ $\geq$ $E_1$ then

    $\varPsi_d~\Leftarrow~\min\{\varPsi_d,~\boldsymbol{~L}[t]/r(t,d)~\}$

    end if

    end for

    if $\mathop{\max}_t(\varPsi_d~r(t,d)-\boldsymbol{~L}[t])\geq~E_2$ then

    $\varPsi_d\Leftarrow~0$

    else

    $\boldsymbol{~L}\Leftarrow~\boldsymbol{~L}-\varPsi_d~\boldsymbol{~L}_d$

    end if

    end for

    return $\boldsymbol{~\varPsi}~=~(\varPsi_1,\ldots,\varPsi_k)$

  •   

    Algorithm 2 Obtaining a degree distribution from $v_1$ and $v_2$

    Require:

    • $K,N,M,\boldsymbol{~h}$ are the number of input symbols, number of batches, batch size, and rank distribution, respectively.

    • $v_1$, $v_2$ are two positive real numbers that $v_1+v_2~<~1$.

    Output:

    Initialize $\boldsymbol{~L}_1$ using Equation eq:l1

    Compute $\boldsymbol{~\varPsi}^1$ using $\boldsymbol{~\varPsi}_1$ by Algorithm 1

    Initialize $\boldsymbol{~\varPsi}^2$ using Equation 13

    $\boldsymbol{~\varPsi}\Leftarrow~\boldsymbol{~\varPsi}^1+\boldsymbol{~\varPsi}^2$

    Normalize $\boldsymbol{~\varPsi}$

    return $\boldsymbol{~\varPsi}$

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1