On random-access data compaction

F.M.J. Willems; T.J. Tjalkens; P.A.J. Volf

doi:10.1109/ITCOM.1999.781428

On random-access data compaction

F.M.J. Willems, T.J. Tjalkens, P.A.J. Volf

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

Abstract

Consider a binary i.i.d. sequence that consists of K=2/sup J/ blocks of length T. We are looking for a universal compaction method that allows us to decode a certain block by looking only at certain segments in the code sequence. We have investigated a hierarchical method that encodes the source sequence into a code sequence that consists of 2/sup J+1/ variable-length segments. For decoding a certain block only J+2 segments need to be accessed. During decoding it is always clear where the next segment that needs to be accessed appears in the code sequence. The cumulative individual redundancy that is achieved by this method, is optimal in the sense that 1/2 log/sub 2/ N behavior is obtained where N=2/sup J/T. An additional increase of at most one bit per code-segment is possible however.

Original language	English
Title of host publication	Proceedings of the 1999 IEEE Information Theory and Communications Workshop
Editors	F. Swarts, J. Swarts
Publisher	Institute of Electrical and Electronics Engineers
Pages	97-97
Number of pages	1
ISBN (Print)	0-7803-5268-8
DOIs	https://doi.org/10.1109/ITCOM.1999.781428
Publication status	Published - 1999
Event	Information Theory and Communications Workshop, IEEE 1999, Kruger National Park, S. Africa, 20-25 June 1999 - Kruger National Park, South Africa Duration: 20 Jun 1999 → 25 Jun 1999

Conference

Conference	Information Theory and Communications Workshop, IEEE 1999, Kruger National Park, S. Africa, 20-25 June 1999
Country/Territory	South Africa
Period	20/06/99 → 25/06/99
Other	Information Theory and Communications Workshop, IEEE 1999

Access to Document

10.1109/ITCOM.1999.781428

Cite this

@inproceedings{b43fac38792d4a1084b2dc44a5b744a6,

title = "On random-access data compaction",

abstract = "Consider a binary i.i.d. sequence that consists of K=2/sup J/ blocks of length T. We are looking for a universal compaction method that allows us to decode a certain block by looking only at certain segments in the code sequence. We have investigated a hierarchical method that encodes the source sequence into a code sequence that consists of 2/sup J+1/ variable-length segments. For decoding a certain block only J+2 segments need to be accessed. During decoding it is always clear where the next segment that needs to be accessed appears in the code sequence. The cumulative individual redundancy that is achieved by this method, is optimal in the sense that 1/2 log/sub 2/ N behavior is obtained where N=2/sup J/T. An additional increase of at most one bit per code-segment is possible however.",

author = "F.M.J. Willems and T.J. Tjalkens and P.A.J. Volf",

year = "1999",

doi = "10.1109/ITCOM.1999.781428",

language = "English",

isbn = "0-7803-5268-8",

pages = "97--97",

editor = "F. Swarts and J. Swarts",

booktitle = "Proceedings of the 1999 IEEE Information Theory and Communications Workshop",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "Information Theory and Communications Workshop, IEEE 1999, Kruger National Park, S. Africa, 20-25 June 1999 ; Conference date: 20-06-1999 Through 25-06-1999",

}

Willems, FMJ, Tjalkens, TJ & Volf, PAJ 1999, On random-access data compaction. in F Swarts & J Swarts (eds), Proceedings of the 1999 IEEE Information Theory and Communications Workshop., 781428, Institute of Electrical and Electronics Engineers, pp. 97-97, Information Theory and Communications Workshop, IEEE 1999, Kruger National Park, S. Africa, 20-25 June 1999, South Africa, 20/06/99. https://doi.org/10.1109/ITCOM.1999.781428

On random-access data compaction. / Willems, F.M.J.; Tjalkens, T.J.; Volf, P.A.J.
Proceedings of the 1999 IEEE Information Theory and Communications Workshop. ed. / F. Swarts; J. Swarts. Institute of Electrical and Electronics Engineers, 1999. p. 97-97 781428.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On random-access data compaction

AU - Willems, F.M.J.

AU - Tjalkens, T.J.

AU - Volf, P.A.J.

PY - 1999

Y1 - 1999

N2 - Consider a binary i.i.d. sequence that consists of K=2/sup J/ blocks of length T. We are looking for a universal compaction method that allows us to decode a certain block by looking only at certain segments in the code sequence. We have investigated a hierarchical method that encodes the source sequence into a code sequence that consists of 2/sup J+1/ variable-length segments. For decoding a certain block only J+2 segments need to be accessed. During decoding it is always clear where the next segment that needs to be accessed appears in the code sequence. The cumulative individual redundancy that is achieved by this method, is optimal in the sense that 1/2 log/sub 2/ N behavior is obtained where N=2/sup J/T. An additional increase of at most one bit per code-segment is possible however.

AB - Consider a binary i.i.d. sequence that consists of K=2/sup J/ blocks of length T. We are looking for a universal compaction method that allows us to decode a certain block by looking only at certain segments in the code sequence. We have investigated a hierarchical method that encodes the source sequence into a code sequence that consists of 2/sup J+1/ variable-length segments. For decoding a certain block only J+2 segments need to be accessed. During decoding it is always clear where the next segment that needs to be accessed appears in the code sequence. The cumulative individual redundancy that is achieved by this method, is optimal in the sense that 1/2 log/sub 2/ N behavior is obtained where N=2/sup J/T. An additional increase of at most one bit per code-segment is possible however.

U2 - 10.1109/ITCOM.1999.781428

DO - 10.1109/ITCOM.1999.781428

M3 - Conference contribution

SN - 0-7803-5268-8

SP - 97

EP - 97

BT - Proceedings of the 1999 IEEE Information Theory and Communications Workshop

A2 - Swarts, F.

A2 - Swarts, J.

PB - Institute of Electrical and Electronics Engineers

T2 - Information Theory and Communications Workshop, IEEE 1999, Kruger National Park, S. Africa, 20-25 June 1999

Y2 - 20 June 1999 through 25 June 1999

ER -

On random-access data compaction

Abstract

Conference

Access to Document

Fingerprint

Cite this