Optimal Interleaving on Tori

Jiang, Anxiao (Andrew) and Cook, Matthew and Bruck, Jehoshua (2004) Optimal Interleaving on Tori. Technical Report. California Institute of Technology. [CaltechPARADISE:2004.ETR059]

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

We study t-interleaving on two-dimensional tori, which is defined by the property that any connected subgraph with t or fewer vertices in the torus is labelled by all distinct integers. It has applications in distributed data storage and burst error correction, and is closely related to Lee metric codes. We say that a torus can be perfectly t-interleaved if its t-interleaving number — the minimum number of distinct integers needed to t-interleave the torus — meets the spherepacking lower bound. We prove the necessary and sufficient conditions for tori that can be perfectly t-interleaved, and present efficient perfect t-interleaving constructions. The most important contribution of this paper is to prove that the t-interleaving numbers of tori large enough in both dimensions, which constitute by far the majority of all existing cases, is at most one more than the sphere-packing lower bound, and to present an optimal and efficient t-interleaving scheme for them. Then we prove some bounds on the t-interleaving numbers for other cases, completing a general picture for the t-interleaving problem on 2-dimensional tori.

EPrint Type:	Monograph (Technical Report)
Additional Information:	[Alternate URL: http://www.paradise.caltech.edu/papers/etr059.pdf]
Subjects:	All Records
ID Code:	81
Deposited By:	INVALID USER
Deposited On:	20 April 2004
Record Number:	CaltechPARADISE:2004.ETR059
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:2004.ETR059
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record