CCapacity Atlas
directed-cycle-index-coding

Directed-cycle index-coding problem

Each receiver in a directed cycle knows its successor message and requests its own message.

Index coding Finite alphabet Side information Multiple unicast Nonlinear coding Symmetric capacity Exact

Channel and question

Input
m independent equal-length messages, for m >= 3.
Output
A common noiseless broadcast word together with one local side-information message.
Law
Receiver r requests message r and knows message r+1 modulo m.
Quantity
Directed-cycle index-coding problem capacity \(C_{\mathrm{sym}}\), measured in message symbols per broadcast symbol.

Criterion. Unrestricted zero-error block codes.

  • Zero error is required for every message tuple.
  • Finite alphabets and vector block codes are unrestricted and need not be linear.
  • The symmetric rate is message blocklength divided by broadcast blocklength.

Current status

\[C_{\mathrm{sym}}=1/(m-1)\]
Known results and bounds for Directed-cycle index-coding problem
ResultRelationMethodYear
Exact\(C_{\mathrm{sym}}=1/(m-1)\)A cycle linear code and an acyclic-subgraph converse valid for nonlinear codes.2010

Formal verification

Lean coverageFormally stated

Concrete operational definitions and admitted research statements are present. Existing proofs are preserved. New statements require mathematical review and proof completion.

Claims

  • The directed cycle with k+3 messages has symmetric capacity 1/(k+2), for unrestricted zero-error codes.
    operational-capacity · exact capacity · solved · Formally stated · v1
Lean declarations (1)

References

  1. Anna Blasiak, Robert Kleinberg, and Eyal Lubetzky (2010). Index Coding via Linear Programming. arXiv preprint, revised 2011.

Discussion

Find discussionStart discussion

Related problems

Undirected five-cycle index-coding problem

Each of five receivers knows its two neighbours and asks for its own independent message.

Index coding Finite alphabet Side information Multiple unicast Nonlinear coding Symmetric capacity Exact
Solved \(C_{\mathrm{sym}}=2/5\)
Index coding with at most five messages

The capacity regions of all 9,846 nonisomorphic index-coding instances with at most five messages are covered by a finite classification.

Index coding Finite alphabet Multiple unicast Side information Capacity region Exact Single-letter characterization
Solved \(\mathcal C(G)=\mathcal R_{\mathrm{composite}}(G)\quad\text{for }|V(G)|\le5\)
Sun-Jafar 11-message multiple-unicast index-coding instance SJ11

The linear-encoder symmetric capacity is known, while unrestricted nonlinear capacity remains open.

Index coding Finite alphabet Multiple unicast Non-Shannon inequalities Nonlinear coding Symmetric capacity Bounds only Linear-encoder-only result
Open \(\frac5{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\)
Sun-Jafar six-message groupcast index-coding instance SJ6-GC

A six-message, ten-receiver groupcast instance has linear-encoder capacity 5/13 and a non-Shannon nonlinear upper bound 11/28.

Index coding Finite alphabet Non-Shannon inequalities Nonlinear coding Symmetric capacity Bounds only Linear-encoder-only result
Open \(\frac5{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\)