A universal interconnection network implements arbitrary interconnections among n terminals. This paper considers a problem to realize such a network using contact switches. When n=2, it can be implemented with a single switch. The number of different connections among n terminals is given by the Bell number B(n). The Bell number shows the total number of methods to partition n distinct elements. For n=2, 3, 4, 5 and 6, the corresponding Bell numbers are 2, 5, 15, 52, and 203, respectively. This paper shows a method to realize an n terminal universal interconnection network with $rac {3}{8}(n^2-1)$ contact switches when n=2m+1≥5, and $rac {n}{8}(3n+2)$ contact switches, when n=2m≥6. Also, it shows that a lower bound on the number of contact switches to realize an n-terminal universal interconnection network is ⌈log 2B(n)⌉, where B(n) is the Bell number.
Tsutomu SASAO
Meiji University
Takashi MATSUBARA
National Defence Academy
Katsufumi TSUJI
Fujitsu Limited
Yoshiaki KOGA
National Defence Academy
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Tsutomu SASAO, Takashi MATSUBARA, Katsufumi TSUJI, Yoshiaki KOGA, "Realization of Multi-Terminal Universal Interconnection Networks Using Contact Switches" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 8, pp. 1068-1075, August 2021, doi: 10.1587/transinf.2020LOP0001.
Abstract: A universal interconnection network implements arbitrary interconnections among n terminals. This paper considers a problem to realize such a network using contact switches. When n=2, it can be implemented with a single switch. The number of different connections among n terminals is given by the Bell number B(n). The Bell number shows the total number of methods to partition n distinct elements. For n=2, 3, 4, 5 and 6, the corresponding Bell numbers are 2, 5, 15, 52, and 203, respectively. This paper shows a method to realize an n terminal universal interconnection network with $rac {3}{8}(n^2-1)$ contact switches when n=2m+1≥5, and $rac {n}{8}(3n+2)$ contact switches, when n=2m≥6. Also, it shows that a lower bound on the number of contact switches to realize an n-terminal universal interconnection network is ⌈log 2B(n)⌉, where B(n) is the Bell number.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020LOP0001/_p
Copy
@ARTICLE{e104-d_8_1068,
author={Tsutomu SASAO, Takashi MATSUBARA, Katsufumi TSUJI, Yoshiaki KOGA, },
journal={IEICE TRANSACTIONS on Information},
title={Realization of Multi-Terminal Universal Interconnection Networks Using Contact Switches},
year={2021},
volume={E104-D},
number={8},
pages={1068-1075},
abstract={A universal interconnection network implements arbitrary interconnections among n terminals. This paper considers a problem to realize such a network using contact switches. When n=2, it can be implemented with a single switch. The number of different connections among n terminals is given by the Bell number B(n). The Bell number shows the total number of methods to partition n distinct elements. For n=2, 3, 4, 5 and 6, the corresponding Bell numbers are 2, 5, 15, 52, and 203, respectively. This paper shows a method to realize an n terminal universal interconnection network with $rac {3}{8}(n^2-1)$ contact switches when n=2m+1≥5, and $rac {n}{8}(3n+2)$ contact switches, when n=2m≥6. Also, it shows that a lower bound on the number of contact switches to realize an n-terminal universal interconnection network is ⌈log 2B(n)⌉, where B(n) is the Bell number.},
keywords={},
doi={10.1587/transinf.2020LOP0001},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - Realization of Multi-Terminal Universal Interconnection Networks Using Contact Switches
T2 - IEICE TRANSACTIONS on Information
SP - 1068
EP - 1075
AU - Tsutomu SASAO
AU - Takashi MATSUBARA
AU - Katsufumi TSUJI
AU - Yoshiaki KOGA
PY - 2021
DO - 10.1587/transinf.2020LOP0001
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2021
AB - A universal interconnection network implements arbitrary interconnections among n terminals. This paper considers a problem to realize such a network using contact switches. When n=2, it can be implemented with a single switch. The number of different connections among n terminals is given by the Bell number B(n). The Bell number shows the total number of methods to partition n distinct elements. For n=2, 3, 4, 5 and 6, the corresponding Bell numbers are 2, 5, 15, 52, and 203, respectively. This paper shows a method to realize an n terminal universal interconnection network with $rac {3}{8}(n^2-1)$ contact switches when n=2m+1≥5, and $rac {n}{8}(3n+2)$ contact switches, when n=2m≥6. Also, it shows that a lower bound on the number of contact switches to realize an n-terminal universal interconnection network is ⌈log 2B(n)⌉, where B(n) is the Bell number.
ER -