Lee Distance and Topological Properties of k-ary n-cubes
Lee Distance and Topological Properties of k-ary n-cubes
复制标题
DOI：
10.1109/12.403718
复制
发表时间：
1995-08
期刊：
影响因子：
--
通讯作者：
B. Bose;Bob Broeg;Younggeun Kwon;Yaagoub Ashir
中科院分区：
文献类型：
--
作者：
B. Bose;Bob Broeg;Younggeun Kwon;Yaagoub Ashir
在本文中，我们使用 Lee 距离考虑 k 元 n 立方体 (Q/sub n//sup k/) 的各种拓扑性质。我们认为 Lee 距离是定义和研究 Q/sub n//sup k/ 的自然度量。使用 Lee 距离定义 Q/sub n//sup k/ 图后，我们展示如何查找任意两个节点之间的所有不相交路径。给定基数k数的序列，给出将该序列映射到格雷码序列的函数，并且该函数用于生成哈密顿循环。考虑将网格图和二元超立方体图嵌入到 Q/sub n//sup k/ 的图中。使用 k 元格雷码，我们展示了将 k(n/sub 1/)/spl times/k(n/sub 2/)/spl times/.../spl times/k(n/sub m/) 维网格嵌入到 Q/sub n//sup k/ 中，其中 n=/spl Sigma//sub i=l//sup m/n/sub i/。然后使用一位 4 进制反射格雷码，我们演示了将 Q/sub n/ 嵌入到 Q/sub [n/2]//sup 4/ 中。我们研究如何通过使用 Lee 距离纠错码将 Lee 距离应用于 Q/sub n//sup k/ 中的资源放置问题。尽管本文的结果只是初步的，但 Lee 距离纠错码之前尚未应用于该问题。最后，我们考虑如何将 Lee 距离应用于 Q/sub n//sup k/ 中的消息路由和单节点广播。在本节中，我们将介绍两种单节点广播算法，它们在使用单端口和多端口 I/O 时是最佳的。 >
In this paper, we consider various topological properties of a k-ary n-cube (Q/sub n//sup k/) using Lee distance. We feel that Lee distance is a natural metric for defining and studying a Q/sub n//sup k/. After defining a Q/sub n//sup k/ graph using Lee distance, we show how to find all disjoint paths between any two nodes. Given a sequence of radix k numbers, a function mapping the sequence to a Gray code sequence is presented, and this function is used to generate a Hamiltonian cycle. Embedding the graph of a mesh and the graph of a binary hypercube into the graph of a Q/sub n//sup k/ is considered. Using a k-ary Gray code, we show the embedding of a k(n/sub 1/)/spl times/k(n/sub 2/)/spl times/.../spl times/k(n/sub m/)-dimensional mesh into a Q/sub n//sup k/ where n=/spl Sigma//sub i=l//sup m/n/sub i/. Then using a single digit, 4-ary reflective Gray code, we demonstrate embedding a Q/sub n/ into Q/sub [n/2]//sup 4/. We look at how Lee distance may be applied to the problem of resource placement in a Q/sub n//sup k/ by using a Lee distance error-correcting code. Although the results in this paper are only preliminary, Lee distance error-correcting codes have not been applied previously to this problem. Finally, we consider how Lee distance can be applied to message routing and single-node broadcasting in a Q/sub n//sup k/. In this section we present two single-node broadcasting algorithms that are optimal when single-port and multi-port I/O is used. >