Browse Prior Art Database

Wildcard Dimensions, Coding Theory and Fault Tolerant Meshes and Hypercubes

IP.com Disclosure Number: IPCOM000109911D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 1 page(s) / 33K

Publishing Venue

IBM

Related People

Bruck, J: AUTHOR [+3]

Abstract

Disclosed is an efficient method for tolerating link faults in a d-dimensional mesh, based on the technique of the so-called wildcard dimensions and error correcting codes theory.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 100% of the total text.

Wildcard Dimensions, Coding Theory and Fault Tolerant Meshes and Hypercubes

      Disclosed is an efficient method for tolerating link faults in
a d-dimensional mesh, based on the technique of the so-called
wildcard dimensions and error correcting codes theory.

      It is known that a hypercube can be extended by one wildcard
dimension resulting in a folded hypercube, which has better fault
tolerance and communication capabilities.  Also, a d-dimensional
torus having n nodes can be extended by up to n-d+1 wildcard
dimensions.  Using techniques from error correcting codes,
specifically a Maximum Distance Separable (MDS) code such as the
extended Reed-Solomon codes and an extension of the Vandermonde
matrix, we construct a d-dimensional fault-tolerant mesh which has
degree 2s and can tolerate 2s - 2d+1 edge faults, for any d < s
< n+1, regardless of the faults distribution.  The faults are
tolerated in the sense that the remaining (fault-free) network still
guaranteed to contain a d-dimensional mesh of the same size as a
subgraph.  Thus, programs designed for the original mesh can be run
on the fault-tolerant mesh without slowdown, even after up to 2s -
2d+1 link failures.

      Disclosed anonymously.