Channel and question
- Input
- Binary packets on directed links with specified nonnegative rate budgets.
- Output
- Incoming packets at each designated sink.
- Law
- Every link transmits its packet without error. Nodes process incoming packets in topological order.
- Quantity
- Noiseless single-source multicast network capacity \(C\), measured in bits per channel use.
Criterion. Vanishing average block error, with the constraints specified in the model.
- The finite vertex order is acyclic and vertex zero is the unique source.
- There is at least one designated sink and the source is not a sink.
- An n-use code sends exactly floor(n r_e) bits on edge e. Packet lengths and schedules convey no information.
- Only the source observes the message. Other nodes use only incoming packets.
- All designated sinks decode the same uniform message.
Current status
\[C=\min_{t\in T}\min_{S:0\in S,\ t\notin S}\sum_{e\in\delta^+(S)}r_e\]
| Result | Relation | Method | Year |
|---|---|---|---|
| Exact | \(C=\min_{t\in T}\min_{S:0\in S,\ t\notin S}\sum_{e\in\delta^+(S)}r_e\) | Linear network coding and a cut-set converse. | 2000 |
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
- Single-source topological processing on a finite noiseless acyclic network.
operational-capacity· exact capacity · solved · Formally stated · v1
Lean declarations (1)
CapacityAtlas.Claims.multicastclaim · operational-capacity
lean/CapacityAtlas/Claims/Multicast.lean — Single-source topological processing on a finite noiseless acyclic network.
References
- Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, and Raymond W. Yeung (2000). Network Information Flow. IEEE Transactions on Information Theory. DOI 10.1109/18.850663.