About Priority Encoding Transmission Stéphane Boucheron, Member, IEEE, and

Abstract—Recently, Albanese et al. introduced priority encoding trans-mission (PET) for sending hierarchically organized messages over lossy packet-based computer networks [1]. In a PET system, each symbol in the message is assigned a priority which determines the minimal number of codeword symbols that is required to recover that symbol. This note re-visits the PET approach using tools from network information theory. We first outline that priority encoding transmission is intimately related with the broadcast erasure channel with degraded message set. Using the infor-mation spectrum approach, we provide an informational characterization of the capacity region of general broadcast channels with degraded message set. We show that the PET inequality has an information-theoretical coun-terpart: The inequality defining the capacity region of the broadcast era-sure channel with degraded message sets. Hence the PET approach which consists in time-sharing and interleaving classical erasure-resilient codes achieves the capacity region of this channel. Moreover, we show that the PET approach may achieve the sphere packing exponents. Finally, we ob-serve that on some simple nonstationary broadcast channels, time-sharing may be outperformed. The impact of memory on the optimality of the PET approach remains elusive. Index Terms—Broadcast channels, coding exponents, erasure-resilient codes, information spectrum, priority encoding transmission. I