On achievability of an ( r , l ) fractional linear network code

Niladri Das; Brijesh Kumar Rai

On achievability of an ( r , l ) fractional linear network code

View Fulltext

Author(s): Niladri Das ¹ and Brijesh Kumar Rai ¹
- Affiliations: 1: Department of Electronics and Electrical Engineering, Indian Institute of Technology Guwahati, Guwahati, Assam, India
Source: Volume 6, Issue 3, May 2017, p. 54 – 61
DOI: 10.1049/iet-net.2016.0094 , Print ISSN 2047-4954, Online ISSN 2047-4962

Received 27/10/2016, Accepted 15/02/2017, Revised 02/02/2017, Published 17/02/2017

It is known that there exists a network, called as the M-network, which is not scalar linearly solvable but has a vector linear solution for message dimension two. Recently, a generalisation of this result has been presented where it has been shown that for any integer $m ≥ 2$ , there exists a network which has an (m, m) vector linear solution, but does not have a (w,w) vector linear solution for w < m. This study presents a further generalisation. Specifically, the authors show that for any positive integers k,n, and $m ≥ 2$ , there exists a network which has a (mk,mn) fractional linear solution, but does not have a (wk,wn) fractional linear solution for w < m.

References

1. 1)
  - 9. Sun, Q.T., Yang, X., Long, K., et al: ‘On vector linear solvability of multicast networks’, Arxiv:1605.02635.
2. 2)
  - 7. Koetter, R., Medard, M.: ‘Beyond routing: an algebraic approach to network coding’. Proc. of the IEEE INFOCOM, 2002.
3. 3)
  - 5. Ebrahimi, J.B., Fragouli, C.: ‘Algebraic algorithms for vector network coding’, IEEE Trans. Inf. Theory, 2011, 57, (2), pp. 996–1007.
4. 4)
  - 19. Muralidharan, V.T., Rajan, B.S.: ‘Linear network coding, linear index coding and representable discrete polymatroids’, IEEE Trans. Inf. Theory, 2016, 62, (7), pp. 4096–4119.
5. 5)
  - 1. Ahlswede, R., Cai, N., Li, S.R., et al: ‘Network information flow’, IEEE Trans. Inf. Theory, 2000, 46, (4), pp. 1204–1216.
6. 6)
  - 18. Kim, A., Médard, M.: ‘Scalar-linear solvability of matroidal networks associated with representable matroids’. Proc. 6th Int. Symp. on Turbo Codes and Iterative Information Processing (ISTC), 2010.
7. 7)
  - 3. Li, S.R., Yeung, R.W., Cai, N.: ‘Linear network coding’, IEEE Trans. Inf. Theory, 2003, 49, (2), pp. 371–381.
8. 8)
  - 2. Das, N., Rai, B.K.: ‘On the message dimensions of vector linearly solvable networks’, IEEE Commun. Lett., 2016, 20, (9), pp. 1701–1704.
9. 9)
  - 13. Connelly, J., Zeger, K.: ‘Linear network coding over rings, Part I: scalar codes and commutative alphabets’, Arxiv:1608.01738.
10. 10)
  - 15. Dougherty, R., Freiling, C., Zeger, K.: ‘Unachievability of network coding capacity’, IEEE Trans. Inf. Theory, 2006, 52, (6), pp. 2365–2372.
11. 11)
  - 10. Dougherty, R., Freiling, C., Zeger, K.: ‘Insufficiency of linear coding in network information flow’, IEEE Trans. Inf. Theory, 2005, 51, (8), pp. 2745–2759.
12. 12)
  - 14. Connelly, J., Zeger, K.: ‘Linear network coding over rings, Part II: vector codes and non-commutative alphabets’, Arxiv:1608.01737.
13. 13)
  - 8. Dougherty, R., Freiling, C., Zeger, K.: ‘Linearity and solvability in multicast networks’, IEEE Trans. Inf. Theory, 2004, 50, (10), pp. 2243–2256.
14. 14)
  - 16. Dougherty, R., Freiling, C., Zeger, K.: ‘Linear network codes and systems of polynomial equations’, IEEE Trans. Inf. Theory, 2008, 54, (5), pp. 2303–2316.
15. 15)
  - 17. Dougherty, R., Zeger, K.: ‘Nonreversibility and equivalent constructions of multiple-unicast networks’, IEEE Trans. Inf. Theory, 2006, 52, (11), pp. 5067–5077.
16. 16)
  - 11. Médard, M., Effros, M., Karger, D., et al: ‘On coding for non-multicast networks’. Proc. 41st Annu. Allerton Conf. Communication Control and Computing, Monticello, IL, 2003.
17. 17)
  - 20. Harvey, N.J.A., Kleinberg, R., Lehman, A.R.: ‘On the capacity of information networks’, IEEE Trans. Inf. Theory, 2006, 52, (6), pp. 2345–2364.
18. 18)
  - 6. Riis, S.: ‘Linear versus non-linear Boolean functions in network flow’. Proc. 38th Annual Conf. on Information Sciences and Systems (CISS), 2004.
19. 19)
  - 12. Dougherty, R., Freiling, C., Zeger, K.: ‘Networks, matroids, and non-shannon information inequalities’, IEEE Trans. Inf. Theory, 2007, 53, (6), pp. 1949–1969.
20. 20)
  - 4. Jaggi, S., Sanders, P., Chou, P.A., et al: ‘Polynomial time algorithms for multicast network code construction’, IEEE Trans. Inf. Theory, 2005, 51, (6), pp. 1973–1982.

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

On achievability of an ( r , l ) fractional linear network code

References

Related content