Linear network coding

Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, w...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2003-02, Vol.49 (2), p.371-381
Main Authors: Li, S.-Y.R., Yeung, R.W., Ning Cai
Format: Article
Language:English
Subjects:
Channel capacity
Communication networks
Communication switching
Conferences
Cryptography
Information rates
Information theory
Network coding
Routing
Spread spectrum communication
Vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c317t-898fd9319568b9ecfb0dbd2c449d5df6733c704dec8f85fc202624492ace9b503
cites cdi_FETCH-LOGICAL-c317t-898fd9319568b9ecfb0dbd2c449d5df6733c704dec8f85fc202624492ace9b503
container_end_page 381
container_issue 2
container_start_page 371
container_title IEEE transactions on information theory
container_volume 49
creator Li, S.-Y.R.
Yeung, R.W.
Ning Cai
description Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.
doi_str_mv 10.1109/TIT.2002.807285
format article
fullrecord <record><control><sourceid>proquest_ieee_</sourceid><recordid>TN_cdi_proquest_journals_195889284</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>1176612</ieee_id><sourcerecordid>28343132</sourcerecordid><originalsourceid>FETCH-LOGICAL-c317t-898fd9319568b9ecfb0dbd2c449d5df6733c704dec8f85fc202624492ace9b503</originalsourceid><addsrcrecordid>eNpdkE1LAzEQhoMoWKtH8eClePC2bTJJdidHKX4UCl7qOewmE9na7takRfz3pqwgeBqGed6Z4WHsRvCpENzMVovVFDiHKfIKUJ-wkdC6Kkyp1SkbcS6wMErhObtIaZ1bpQWM2PWy7aiOk472X338mLjet937JTsL9SbR1W8ds7enx9X8pVi-Pi_mD8vCSVHtCzQYvJHC6BIbQy403DcenFLGax_KSkpXceXJYUAdHHAoIQ-hdmQazeWY3Q97d7H_PFDa222bHG02dUf9IVlAqaSQkMG7f-C6P8Qu_2bzdUQDqDI0GyAX-5QiBbuL7baO31Zwe3RksyN7dGQHRzlxOyRaIvqjRVWWAuQPON9f8Q</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>195889284</pqid></control><display><type>article</type><title>Linear network coding</title><source>IEEE Electronic Library (IEL) Journals</source><creator>Li, S.-Y.R. ; Yeung, R.W. ; Ning Cai</creator><creatorcontrib>Li, S.-Y.R. ; Yeung, R.W. ; Ning Cai</creatorcontrib><description>Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.</description><identifier>ISSN: 0018-9448</identifier><identifier>EISSN: 1557-9654</identifier><identifier>DOI: 10.1109/TIT.2002.807285</identifier><identifier>CODEN: IETTAW</identifier><language>eng</language><publisher>New York: IEEE</publisher><subject>Channel capacity ; Communication networks ; Communication switching ; Conferences ; Cryptography ; Information rates ; Information theory ; Network coding ; Routing ; Spread spectrum communication ; Vectors</subject><ispartof>IEEE transactions on information theory, 2003-02, Vol.49 (2), p.371-381</ispartof><rights>Copyright Institute of Electrical and Electronics Engineers, Inc. (IEEE) Feb 2003</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c317t-898fd9319568b9ecfb0dbd2c449d5df6733c704dec8f85fc202624492ace9b503</citedby><cites>FETCH-LOGICAL-c317t-898fd9319568b9ecfb0dbd2c449d5df6733c704dec8f85fc202624492ace9b503</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/1176612$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,54796</link.rule.ids></links><search><creatorcontrib>Li, S.-Y.R.</creatorcontrib><creatorcontrib>Yeung, R.W.</creatorcontrib><creatorcontrib>Ning Cai</creatorcontrib><title>Linear network coding</title><title>IEEE transactions on information theory</title><addtitle>TIT</addtitle><description>Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.</description><subject>Channel capacity</subject><subject>Communication networks</subject><subject>Communication switching</subject><subject>Conferences</subject><subject>Cryptography</subject><subject>Information rates</subject><subject>Information theory</subject><subject>Network coding</subject><subject>Routing</subject><subject>Spread spectrum communication</subject><subject>Vectors</subject><issn>0018-9448</issn><issn>1557-9654</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2003</creationdate><recordtype>article</recordtype><recordid>eNpdkE1LAzEQhoMoWKtH8eClePC2bTJJdidHKX4UCl7qOewmE9na7takRfz3pqwgeBqGed6Z4WHsRvCpENzMVovVFDiHKfIKUJ-wkdC6Kkyp1SkbcS6wMErhObtIaZ1bpQWM2PWy7aiOk472X338mLjet937JTsL9SbR1W8ds7enx9X8pVi-Pi_mD8vCSVHtCzQYvJHC6BIbQy403DcenFLGax_KSkpXceXJYUAdHHAoIQ-hdmQazeWY3Q97d7H_PFDa222bHG02dUf9IVlAqaSQkMG7f-C6P8Qu_2bzdUQDqDI0GyAX-5QiBbuL7baO31Zwe3RksyN7dGQHRzlxOyRaIvqjRVWWAuQPON9f8Q</recordid><startdate>200302</startdate><enddate>200302</enddate><creator>Li, S.-Y.R.</creator><creator>Yeung, R.W.</creator><creator>Ning Cai</creator><general>IEEE</general><general>The Institute of Electrical and Electronics Engineers, Inc. (IEEE)</general><scope>RIA</scope><scope>RIE</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SP</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>200302</creationdate><title>Linear network coding</title><author>Li, S.-Y.R. ; Yeung, R.W. ; Ning Cai</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c317t-898fd9319568b9ecfb0dbd2c449d5df6733c704dec8f85fc202624492ace9b503</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2003</creationdate><topic>Channel capacity</topic><topic>Communication networks</topic><topic>Communication switching</topic><topic>Conferences</topic><topic>Cryptography</topic><topic>Information rates</topic><topic>Information theory</topic><topic>Network coding</topic><topic>Routing</topic><topic>Spread spectrum communication</topic><topic>Vectors</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Li, S.-Y.R.</creatorcontrib><creatorcontrib>Yeung, R.W.</creatorcontrib><creatorcontrib>Ning Cai</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 1998-Present</collection><collection>IEEE/IET Electronic Library</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics &amp; Communications Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>IEEE transactions on information theory</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Li, S.-Y.R.</au><au>Yeung, R.W.</au><au>Ning Cai</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Linear network coding</atitle><jtitle>IEEE transactions on information theory</jtitle><stitle>TIT</stitle><date>2003-02</date><risdate>2003</risdate><volume>49</volume><issue>2</issue><spage>371</spage><epage>381</epage><pages>371-381</pages><issn>0018-9448</issn><eissn>1557-9654</eissn><coden>IETTAW</coden><abstract>Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.</abstract><cop>New York</cop><pub>IEEE</pub><doi>10.1109/TIT.2002.807285</doi><tpages>11</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0018-9448
ispartof IEEE transactions on information theory, 2003-02, Vol.49 (2), p.371-381
issn 0018-9448
1557-9654
language eng
recordid cdi_proquest_journals_195889284
source IEEE Electronic Library (IEL) Journals
subjects Channel capacity
Communication networks
Communication switching
Conferences
Cryptography
Information rates
Information theory
Network coding
Routing
Spread spectrum communication
Vectors
title Linear network coding
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T09%3A52%3A42IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_ieee_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Linear%20network%20coding&rft.jtitle=IEEE%20transactions%20on%20information%20theory&rft.au=Li,%20S.-Y.R.&rft.date=2003-02&rft.volume=49&rft.issue=2&rft.spage=371&rft.epage=381&rft.pages=371-381&rft.issn=0018-9448&rft.eissn=1557-9654&rft.coden=IETTAW&rft_id=info:doi/10.1109/TIT.2002.807285&rft_dat=%3Cproquest_ieee_%3E28343132%3C/proquest_ieee_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c317t-898fd9319568b9ecfb0dbd2c449d5df6733c704dec8f85fc202624492ace9b503%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=195889284&rft_id=info:pmid/&rft_ieee_id=1176612&rfr_iscdi=true