On the Capacity ofNon-Coherent Network Coding

bits. However, this resultassumes that the receivers know perfectly the operations thatthe network nodes perform. In practical networks, where suchdeterministic knowledge is not sustainable, the most popularapproach is to append coding vectors at the headers of thepackets to keep track of the linear combinations of the sourcepackets they contain. This results in a loss of information ratewith respect to the min-cut value. In a sense, this is akin totraining symbols to learn the transformation induced by thenetwork. Recently, algebraic subspace coding constructionshave been proposed as a method that allows to achieve higherinformation rates by dispensing of the need for the codingvector overheads [3]. In this paper we examine what are theinformation theoretical rates that can be achieved in a networkwhere the intermediate node operations are unknown.We consider a network where neither the source nor thereceivers have knowledge of the network topology or of thelinear coding operations the network nodes perform. In [6] weproposed a model to capture this communication, where thesource inserts in the network m packets of length T over somefinite field IF