Fault-tolerant cube graphs and coding theory

被引：6

作者：

Bruck, J ^{[1
]}

Ho, CT ^{[1
]}

机构：

[1] IBM CORP,ALMADEN RES CTR,SAN JOSE,CA 95120

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 1996年 / 42卷 / 06期

关键词：

fault tolerance; parallel computing; interconnection networks; hypercubes; omega networks; error-correcting codes;

D O I：

10.1109/18.556609

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Hypercubes, meshes, tori, and Omega networks are well-known interconnection networks for parallel computers. The structure of those graphs can be described in a more general framework called cube graphs. The idea is to assume that every node in a graph with q(l) nodes is represented by a unique string of l symbols over GF(q). The edges are specified by a set of offsets, those are vectors of length l over GF (q), where the two endpoints of an edge are an offset apart. We study techniques for tolerating edge faults in cube graphs that are based on adding redundant edges. The redundant graph has the property that the structure of the original graph can be maintained in the presence of edge faults. Our main contribution is a technique for adding the redundant edges that utilizes constructions of error-correcting codes and generalizes existing ad hoc techniques.

引用

页码：2217 / 2221

页数：5

共 11 条

[1]

ADAMS GB, 1982, IEEE T COMPUT, V31, P443, DOI 10.1109/TC.1982.1676021

[2] AN UPDATED TABLE OF MINIMUM-DISTANCE BOUNDS FOR BINARY LINEAR CODES [J].