Diskreta polymatroider är multi-set analog av matroider. I den här artikeln utforskar vi kopplingarna mellan linjär nätverkskodning, linjär indexkodning och representativa diskreta polymatriser. Vi anser att vektor linjära lösningar av nätverk över ett fält F q, med möjligen olika budskap och kant vektor dimensioner, som kallas linjära fraktionerade lösningar. Det är väl känt att en skalar linjär lösning över F q finns för ett nätverk om och endast om nätverket är matroidal med avseende på en matroid som kan representeras över F q. Vi definierar en diskret polymatroidal nätverk och visar att en linjär fraktionering lösning över ett fält F q finns för ett nätverk om och endast om nätverket är diskret polymatroidal med avseende på en diskret polymatroid som kan representeras över F q. En algoritm för att konstruera nätverken från viss klass av diskreta polymatroider tillhandahålls. Varje representation över F q för den diskreta polymatroiden resulterar i en linjär fraktionerad lösning över F q för det konstruerade nätverket. Nästa, vi anser indexkodning problem, vilket innebär en avsändare, som genererar en uppsättning meddelanden X = {x 1, x 2,. .. x k }, och en uppsättning mottagare R, som kräver meddelanden. En mottagare R är specificerad av tuple (x, H), där x X är meddelandet som krävs av R och H X\ {x} är sidan information som innehas av R. Vi visar först att en linjär lösning på ett indexkodningsproblem finns om och endast om det finns en representativ diskret polymatroid, som uppfyller vissa villkor, som bestäms av indexkodning problem beaktas. Rouayheb m.fl. visade att problemet med att hitta en multilinjär representation för en matris kan reduceras till att hitta en perfekt linjär indexkodning lösning för ett indexkodningsproblem som erhållits från den matrisen. Multilinjär representation av en matroid kan ses som ett specialfall av representation av en lämplig diskret polymatroid. Vi generaliserar resultatet av Rouayheb et al., genom att visa att problemet med att hitta en representation för en diskret polymatroid kan reduceras till att hitta en perfekt linjär indexkodning lösning för en indexkodning problem som erhållits från den diskret polymatroid. T HE koncept för nätkodning, som ursprungligen infördes av Ahlswede et al. Under [1], bidrar till att tillhandahålla mer genomströmning i ett kommunikationsnät än vad rena routing lösningar ger. För solvable multicast-nät visades [2] att linjära lösningar finns för tillräckligt stor fältstorlek. Ett algebraiskt ramverk för att hitta linjära lösningar i nätverk infördes [3]. Kopplingen mellan matroider och nätverkskodning studerades av Dougherty et al. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. I [4], Begreppet matroidal nätverk infördes och det visades att om en skalär linjär lösning över F q finns för ett nätverk, då nätverket är matroidal med avseende på en representativ matroid. Omvänt att en skalär linjär lösning finns för ett nätverk om nätverket är matroidal med avseende på en representativ matroid visades i [5]. Ett konstruktionsförfarande gavs i [4] för att få nätverk från matroider, där det resulterande nätverket medger en skalar linjär lösning över F q om matroiden är representativ över F q. Med hjälp av de nät som konstruerats med det konstruktionsförfarande som anges i [4], visades det i [6] att det finns nätverk som inte medger någon skalära och vektor linjär lösning, men medger en icke-linjär lösning. Under [7] konstruerades optimala lösningar för cykliska nätverk från associerade acykliska nätverk som motiverades av resultat från matroiddualitetsteori. Linjära nätverkskoder över cykliska nätverk karakteriserades med hjälp av matriser i [8]. Utvidga begreppet matroidal nätverk till nätverk som medger felkorrigering, visades det i [9] att ett nätverk medger en skaklar linjär felkorrigering nätkod om och endast om det är en matroidal felkorrigering nätverk i samband med en representativ matroid. Konstruktioner av nät från matroider med felkorrigeringsförmåga tillhandahölls under [9] och [10]. Det visades i [11] att det är möjligt för ett icke-skalar linjärt solvbart nätverk att tillåta en vektor linjär lösning, i vilken kanterna bär vektorer över F q vars dimensioner är desamma som meddelandevektorerna. Genom hela detta papper, genom en vektornätverk kodlösning, hänvisar vi till en lösning för vilken alla dimensioner av meddelandevektorer är lika med kantvektordimensionen. Det är möjligt att ett nätverk inte tillåter någon skalära eller vektorlösning, men medger en lösning om alla dimensioner av meddelandevektorerna inte är lika med kantvektordimensionen. Sådana nätkodningslösningar, så kallade Fractional Network Coding (FNC) lösningar, för vilka alla dimensioner av meddelandevektorer inte nödvändigtvis är lika med kantvektordimensionen, har ansetts vara 0018-9448
Det har visat sig att ett nätverk har en (r, l) fraktionerad linjär nätverkskodslösning över F q om och endast om det är ett (r, l)-diskret polymatroidal nätverk med avseende på en diskret polymatroid som kan representeras över F q REF.
Linear Network Coding, Linear Index Coding and Representable Discrete Polymatroids
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}