Abstract-Det är känt att varje solvable multicast nätverk har en skalar linjär lösning över ett tillräckligt stort ändligt fält alfabet. Det är också känt att detta resultat inte generaliseras till godtyckliga nätverk. Det finns flera exempel i litteraturen på lösbara nätverk utan någon skalar linjär lösning över något ändligt fält. Varje exempel har dock en linjär lösning för vissa vektordimensioner som är större än ett. Det har blivit förmodat att varje solvable nätverk har en linjär lösning över vissa ändliga fält alfabet och någon vektor dimension. Vi ger ett motexempel på detta antagande. Vi visar också att om ett nätverk inte har någon linjär lösning över något ändligt fält, då har det ingen linjär lösning över någon ändlig pendlingsring med identitet. Vårt motexempel nätverk har ingen linjär lösning ens i den mer allmänna algebraiska kontexten av moduler, som inkluderar som specialfall alla finita ringar och Abeliska grupper. Dessutom visar vi att nätkodningskapaciteten i detta nätverk är strikt större än den maximala linjära kodningskapaciteten över något ändligt fält (exakt £ större), så nätverket är inte ens asymptotiskt linjärt lösbart. Av detta följer att även för mer allmänna versioner av linearitet såsom konvolutionell kodning, filterbankskodning eller linjär tidsdelning, har nätverket ingen linjär lösning.
Det är känt (t.ex. REF ) att för allmänna nät, fraktionerade linjära koder över ändliga fält inte nödvändigtvis uppnå nätverkets kapacitet.
Insufficiency of linear coding in network information flow
{'venue': 'Proceedings. International Symposium on Information Theory, 2005. ISIT 2005.', 'journal': 'Proceedings. International Symposium on Information Theory, 2005. ISIT 2005.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}