Computer Science – Information Theory
Scientific paper
2008-06-28
Computer Science
Information Theory
39 pages
Scientific paper
A malleable coding scheme considers not only compression efficiency but also the ease of alteration, thus encouraging some form of recycling of an old compressed version in the formation of a new one. Malleability cost is the difficulty of synchronizing compressed versions, and malleable codes are of particular interest when representing information and modifying the representation are both expensive. We examine the trade-off between compression efficiency and malleability cost under a malleability metric defined with respect to a string edit distance. This problem introduces a metric topology to the compressed domain. We characterize the achievable rates and malleability as the solution of a subgraph isomorphism problem. This can be used to argue that allowing conditional entropy of the edited message given the original message to grow linearly with block length creates an exponential increase in code length.
Goyal Vivek K.
Kusuma Julius
Varshney Lav R.
No associations
LandOfFree
Malleable Coding: Compressed Palimpsests does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Malleable Coding: Compressed Palimpsests, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Malleable Coding: Compressed Palimpsests will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-258980