Benefiting from Disorder: Source Coding for Unordered Data

Simple item page
dc.creatorVarshney, Lav R.
dc.creatorGoyal, Vivek K.
dc.date2007-08-17
dc.date.accessioned2026-07-07T08:24:04Z
dc.date.available2026-07-07T08:24:04Z
dc.descriptionThe order of letters is not always relevant in a communication task. This paper discusses the implications of order irrelevance on source coding, presenting results in several major branches of source coding theory: lossless coding, universal lossless coding, rate-distortion, high-rate quantization, and universal lossy coding. The main conclusions demonstrate that there is a significant rate savings when order is irrelevant. In particular, lossless coding of n letters from a finite alphabet requires Theta(log n) bits and universal lossless coding requires n + o(n) bits for many countable alphabet sources. However, there are no universal schemes that can drive a strong redundancy measure to zero. Results for lossy coding include distribution-free expressions for the rate savings from order irrelevance in various high-rate quantization schemes. Rate-distortion bounds are given, and it is shown that the analogue of the Shannon lower bound is loose at all finite rates.
dc.description35 pages
dc.identifierhttps://arxiv.org/abs/0708.2310
dc.identifierhttp://arxiv.org/abs/0708.2310
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/136219
dc.subjectInformation Theory
dc.titleBenefiting from Disorder: Source Coding for Unordered Data
dc.typetext

Files

Collections

arXiv