Indexkodierung mit Seitenauskunft

Angeregt durch ein Problem der Übertragung zusätzlicher Daten über Rundfunkkanäle (Birk und Kol, INFOCOM 1998) untersuchen wir folgendes Kodierungsproblem: Ein Sender kommuniziert mit n Empfängern R 1,. . . , R n. Er hält eine Eingabe x ∈ 0, 01l n und möchte eine einzelne Nachricht senden, sodass jeder Empfänger Ri das Bit x i wiederherstellen kann. Jeder R i hat priorisierte Seitenauskunft über x, die durch einen gerichteten Graphen G induziert wird; Ri kennt die Bits von a in den Positionen j | (i, j) eine Kante von G ist. G ist dem Sender und den Empfängern bekannt. Wir nennen Kodierungsverfahren, die dieses Ziel erreichen, INDEXcodes für 0, 1 n mit Seitenauskunftsgraph G. In diesem Papier identifizieren wir ein Maß für Graphen, den Minrank, der genau die minimale Länge von linearen und bestimmten Typen von nichtlinearen INDEX-Codes charakterisiert. Wir zeigen, dass für natürliche Klassen von Seitenauskunftsgraphen, einschließlich gerichteter azyklischer Graphen, perfekter Graphen, ungerader Löcher und ungerader Antilöcher, der Minrank die optimale Länge willkürlicher INDEX-Codes ist. Für willkürliche INDEX-Codes und willkürliche Graphen erhalten wir eine untere Grenze in Bezug auf die Größe des maximalen azyklischen induzierten Teilgraphen. Diese Grenze gilt sogar für randomisierte Codes, es wurde jedoch gezeigt, dass sie nicht eng ist.