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.

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
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.
Subject Keywords:Burst error, cluster, cycle, file placement, interleaving, multicluster interleaving (MCI), path
Record Number:JIAieeetit05
Persistent URL:
Alternative 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:26 Dec 2012 08:39

Repository Staff Only: item control page