A Caltech Library Service

Multicluster interleaving on paths and cycles

Jiang, Anxiao (Andrew) and Bruck, Jehoshua (2005) Multicluster interleaving on paths and cycles. IEEE Transactions on Information Theory, 51 (2). pp. 597-611. ISSN 0018-9448. doi:10.1109/TIT.2004.840893.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Interleaving codewords is an important method not only for combatting burst errors, but also for distributed data retrieval. This paper introduces the concept of multicluster interleaving (MCI), a generalization of traditional interleaving problems. MCI problems for paths and cycles are studied. The following problem is solved: how to interleave integers on a path or cycle such that any m (m/spl ges/2) nonoverlapping clusters of order 2 in the path or cycle have at least three distinct integers. We then present a scheme using a "hierarchical-chain structure" to solve the following more general problem for paths: how to interleave integers on a path such that any m (m/spl ges/2) nonoverlapping clusters of order L (L/spl ges/2) in the path have at least L+1 distinct integers. It is shown that the scheme solves the second interleaving problem for paths that are asymptotically as long as the longest path on which an MCI exists, and clearly, for shorter paths as well.

Item Type:Article
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:“© 2005 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.” Manuscript received August 17, 2003; revised July 29, 2004. This work was supported in part by the Lee Center for Advanced Networking at the California Institute of Technology, and by the National Science Foundation under Grant CCR-TC-0209042. The material in this paper was presented in part at the 7th International Symposium on Communication Theory and Applications, Ambleside, Lake District, UK, July 2003. Communicated by K. A. S. Abdel-Ghaffar, Associate Editor for Coding Theory. The authors would like to thank the Associate Editor for his great diligence and the anonymous reviewers for their very helpful comments.
Funding AgencyGrant Number
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:Burst error, cluster, cycle, file placement, interleaving, vmulticluster interleaving (MCI), path
Issue or Number:2
Record Number:CaltechAUTHORS:JIAieeetit05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:268
Deposited By: Archive Administrator
Deposited On:14 May 2005
Last Modified:08 Nov 2021 19:01

Repository Staff Only: item control page