A lower bound on the encoding length in lossy transmission

Network heterogeneity has become a major issue and multi-media applications have to cope with interconnected networks consisting of many subnetworks o f unevenly distributed resources. Information is transmitted in the form of packets of bits over a lossy media, such that transmitted packets may get lost. In order to solve the packet loss problem over heterogeneous networks we analyze a model in which a subset of packets and a threshold correspond to each message, in such a way that a message can be recovered from a numb er of packets greater than or equal to the threshold in the corresponding s ubset. In particular we prove a lower bound on the encoding length in such a model, when two messages are transmitted. (C) 1999 Published by Elsevier Science Inc. All rights reserved.