| Item type |
SIG Technical Reports(1) |
| 公開日 |
2020-03-09 |
| タイトル |
|
|
タイトル |
BDDを用いたソーティングネットワークの生成 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
A computation method of minimum-comparison sorting network using BDD |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
東海大学 |
| 著者所属 |
|
|
|
国立情報学研究所 |
| 著者所属(英) |
|
|
|
en |
|
|
Tokai University |
| 著者所属(英) |
|
|
|
en |
|
|
National Institute of Informatics |
| 著者名 |
大西, 建輔
宇野, 毅明
|
| 著者名(英) |
Kensuke, Onishi
Takeaki, Uno
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
ソーティングネットワークは，チャンネルと2個のチャンネルを結ぶ比較器からなる構造である．チャンネルには値を入力することができ，比較器で大小関係に応じて値を交換する．この交換を繰り返しおこなうことで，どのような値が入力されてもソーティングネットワークは，ソートされた値を出力する．我々は，ソーティングネットワークを，二分決定グラフ BDD を用いて生成する手法について提案する．また，提案手法を実装し，チャンネル数が 8 以下の比較器数が最小のソーティングネットワークを生成した． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Sorting network consists of channels and comparators connecting two channels. Each channel has a value. A comparator exchanges two values of channels when the value of upper channel is smaller than that of lower. Any values of channels is sorted by the comparators of sorting network. We propose a computing method of sorting network using binary decision diagram (BDD). We implement the method and generate sorting network with smallest number of comparators for 8 or less channels. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2020-AL-177,
号 8,
p. 1-6,
発行日 2020-03-09
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL20177008.pdf (1.2 MB)
