LEE DISTANCE AND TOPOLOGICAL PROPERTIES OF K-ARY N-CUBES

In this paper, we consider various topological properties of a k-ary n-cube (Q(n)(k)) using Lee distance. We feel that Lee distance is a natural metric for defining and studying a Q(n)(k). After defining a Q(n)(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(n)(k) is considered. Using a k-ary Gray code, we show the embedding of a k(n1) x k(n2) x ... x k(nm)-dimensional mesh into a Q(n)(k) where n = Sigma(i=1)(m)n(i). Then using a single digit, 4-ary reflective Gray code, we demonstrate embedding a Q(n) into a Q([n/2]) (4). We look at how Lee distance may be applied to the problem of resource placement in a Q(n)(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(n)(k). In this section we present two single-node broadcasting algorithms that are optimal when single-port and multi-port I/O is used.