The Nonlinear Network Coding and Its Application in Error-Correcting Codes | Wireless Personal Communications Skip to main content
Springer Nature Link
Log in

The Nonlinear Network Coding and Its Application in Error-Correcting Codes

  • Published:
Wireless Personal Communications Aims and scope Submit manuscript

Abstract

Nonlinear network coding is researched here. For determined network, Jaggi–Sanders algorithm is generalized to its nonlinear form for the the multicast network. Precise details of the algorithm implementation and the proof on the algorithm existence are given. The error-correcting codes for determined network coding is also proposed based on the traditional error-correcting codes for network coding. For random network, the nonlinear network coding scheme is proposed. It shows the nonlinear network coding has advantages in solving the so-called “all-or-nothing” problem caused by errors. Some interesting mathematical concepts such as shared agreements, composite functions and n-dimensional maximal independent set based on combinatorics are proposed. These new concepts may offer beneficial lessons for further research on nonlinear network coding.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Abbreviations

F :

The finite field used

n :

The block length of the original codes, i.e., the dimension of original messages

m :

The number of leading edges of a intermediate node and \(m\ge 1\)

\(C_{noline}\) :

Cardinality of maximal independent set of nonlinear coding functions

nMIS:

A n-dimensional maximal independent set

\(\phi _{e}\) :

The local coding function for edge e which is a outgoing edge of intermediate t. This function is in the variables which are the messages of leading edges of intermediate node t

\(\phi _{e}(X,Y)\) :

A special case of \(\phi _{e}\) which is in the variables X, Y, i.e., there are two edges in node t

\(K_{T_{1}x_{2}}\) :

A special case of \(\phi _{e}\) where edge e is specialized as the second imaginary outgoing edge

\(x_{2}\) of the sink \(T_{1}\) :

It is also the decoding function for messages \(x_{2}\) in sink node \(T_{1}\)

\(K_{f_{1}f_{2}}(x,y)\) :

The arithmetic result of composite the function \(K[f_{1}(x,y),f_{2}(x,y)]\)

\(f_{e}\) :

Global coding function for edge e in the variables of original messages \(x_{1},\ldots ,x_{n}\)

(q, i):

Two-tuple to represent the \(i^{\prime}\)th edge-disjoint path of the \(q^{\prime}\)th sink

\(e_{(q,i)}\) :

The predecessor edge e of on a path

\(P_{q,i}\) :

Denote the path that the \(i^{\prime}\)th edge-disjoint path of the \(q^{\prime}\)th sink

\(V^{n}\) :

All the mappings in n variables in field F where one of these mappings can be uniquely represented by a polynomial with coefficients in the field F and with degree in each variable at most \(n-1\). It is the generalization of the vector space concept

\(\left\langle \{ f_{1},\ldots ,f_{m} \} \right\rangle \) :

The spanning function space which is a subspace of \(V^{n}\)

t :

A intermediate node

\(V_{t}\) :

The spanning function space of node t, and it is a alternative representation of \(\left\langle \{ f_{1},\ldots ,f_{m} \} \right\rangle \)

\(dim\{ f_{1},\ldots ,f_{m} \} \) :

The rank of collection of functions \( f_{1},\ldots ,f_{m} \), and it is the generalization of the rank of vectors set concept

\(share\{ f_{1},\ldots ,f_{m} \} \) :

The shared agreements of collection of functions \(f_{1},\ldots ,f_{m}\)

\(A_{f_{e}}\) :

All the agreements of function \(f_{e}\)

\(A_{ C_{|F|^{n}}^{2} }\) :

All the agreements of all the functions where there are n variables in the finite field F

\(\phi \) :

The number of sinks

q :

The sequence number to denote the \(q^{\prime}\)th sink of \(\phi \) sinks

E :

The set of edges

\(f_{i}(x_{1},\ldots ,x_{n})_{(x_{1},\ldots ,x_{m})}\) :

To denote the function degraded from functions \(f_{i}\) with variables \(x_{1},x_{2},\ldots ,x_{n}\) and \(f_{i}(x_{1},\ldots ,x_{n})_{(x_{1},\ldots ,x_{m})}\) just depend on the variables of \(x_{1},x_{2},\ldots ,x_{m}\)

References

  1. Dougherty, R., Freiling, C., & Zeger, K. (2005). Insufficiency of linear coding in network information flow. Information Theory, IEEE Transactions, 51(8), 2745–2759.

    Article  MathSciNet  MATH  Google Scholar 

  2. Kobayashi, H., Le Gall, F., Nishimura, H., & Rotteler, M. (2011). Constructing quantum network coding schemes from classical nonlinear protocols. In Information theory proceedings (ISIT), 2011 IEEE international symposium on IEEE (pp. 109–113).

  3. Blasiak, A., Kleinberg, R., & Lubetzky, E. (2011). Lexicographic products and the power of non-linear network coding. In Foundations of computer science (FOCS), 2011 IEEE 52nd annual symposium on IEEE (pp. 609–618).

  4. Shadbakht, S., & Hassibi, B. (2010). MCMC methods for entropy optimization and nonlinear network coding. In Information theory proceedings (ISIT), IEEE international symposium on IEEE (pp. 2383–2387).

  5. Li, Q., Ting, S. H., & Ho, C. K. (2009). Nonlinear network code for high throughput broadcasting with retransmissions. In Information theory, 2009. ISIT 2009 IEEE international symposium on IEEE (pp. 2853–2857).

  6. Wernersson, N., & Skoglund, M. (2009). Nonlinear coding and estimation for correlated data in wireless sensor networks. IEEE Transactions on Communications, 57(10), 2932–2939.

    Article  Google Scholar 

  7. Dougherty, R., Freiling, C., & Zeger, K. (2006). Unachievability of network coding capacity. Information Theory IEEE Transactions, 52(6), 2365–2372.

    Article  MathSciNet  MATH  Google Scholar 

  8. Langberg, M., & Sprintson, A. (2008). On the hardness of approximating the network coding capacity. In Information theory, 2008. ISIT 2008 IEEE international symposium (pp. 1008–1014)

  9. Lehman, A. R., & Lehman, E. (2004). Complexity classification of network information flow problems. In Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms (pp. 142–150). Society for Industrial and Applied Mathematics.

  10. Medard, M., & Koetter, R. (2002). Beyond routing: An algebraic approach to network coding. Proceedings of IEEE INFOCOM, 1(5), 122–130.

    Google Scholar 

  11. Sanders, P., Egner, S., & Tolhuizen, L. (2003). Polynomial time algorithms for network information flow. In ACM symposium on parallel algorithms and architectures (pp. 286–294).

  12. Li, L., & Long, D. (2008). Nonlinear network coding: A case study. Computer Science, 7, 020.

    Google Scholar 

  13. Guang, X., Fu, F. W., & Zhang, Z. (2010). Construction of network error correction codes in packet networks. IEEE Transactions on Information Theory, 59(2), 1030–1047.

    Article  MathSciNet  MATH  Google Scholar 

  14. Bachmann, O., Greuel, G. M., Lossen, C., Pfister, G., & Schönemann, H. A. (2007). Singular introduction to commutative algebra. Berlin: Springer.

    Google Scholar 

  15. Fengkeqin, L. (2011). The finite field and its application. Dalian: Dalian University of Technology Press.

    Google Scholar 

  16. ZongpengLi, J. (2012). Network coding principles. Islamabad: National Defence Industry Press.

    Google Scholar 

  17. Yang, S., Yeung, R. W., & Chi, K. N. (2011). Refined coding bounds and code constructions for coherent network error correction. IEEE Transactions on Information Theory, 57(3), 1409–1424.

    Article  MathSciNet  MATH  Google Scholar 

  18. Guang, X., Fu, F. W., & Zhang, Z. (2013). Construction of network error correction codes in packet networks. IEEE Transactions on Information Theory, 59(2), 1030–1047.

    Article  MathSciNet  MATH  Google Scholar 

  19. Matsumoto, R. (2006). Construction algorithm for network error-correcting codes attaining the singleton bound. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 90(9), 1729–1735.

    Article  Google Scholar 

Download references

Acknowledgements

This work is supported by Suihua technology office program (SHKJ2015-015), the fundamental research funds for Heilongjiang provincial universities (The study on error spreading depression in network coding), Suihua technology office program (SHKJ2015-014), National Science foundation of China (61571150), Education Office of Heilongjiang province science and technology program(Study on integrated network application in smart factory), Suihua university program (K1502003).

Author information

Author notes

  1. Guangzhi Zhang, Shaobin Cai and Dongqiu Zhang have contributed equally to this work and should be considered as co-first authors.

Authors and Affiliations

  1. Computer Science Department, Harbin Engineering University, Harbin, China

    Guangzhi Zhang & Shaobin Cai

  2. Suihua University, Suihua, China

    Guangzhi Zhang

  3. School of Education, Nanjing Normal University, Nanjing, China

    Dongqiu Zhang

Authors
  1. Guangzhi Zhang
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Shaobin Cai
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Dongqiu Zhang
    View author publications

    You can also search for this author inPubMed Google Scholar

Contributions

GZ conceived the idea and design this algorithm of the experiment. SC organized this work and wrote this paper. DZ analyzed the results.

Corresponding author

Correspondence to Guangzhi Zhang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, G., Cai, S. & Zhang, D. The Nonlinear Network Coding and Its Application in Error-Correcting Codes. Wireless Pers Commun 102, 831–860 (2018). https://doi.org/10.1007/s11277-017-5109-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11277-017-5109-z

Keywords