単項演算に対する局所計算可能な符号化

• Item type: Journal(1)
• 公開日: 1990-05-15
• タイトル: 単項演算に対する局所計算可能な符号化
• タイトル / 言語: en
• タイトル: Locally Computable Coding for Unary Operations
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文（論文賞受賞）
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: ハードウェアアルゴリズム
• 著者所属: 京都大学工学部電子工学科
• 著者所属(英): en
• 著者所属(英): Department of Electronics, Facully of Enginnering, Kyoto University
• 著者名: 安浦, 寛人
• 著者名(英): Yasuura, Hiroto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 並列アルゴリズムの設計において 符号化は重要な役割を担っている.ある符号化において 実現したい演算の結果の符号の各桁が オペランドの符号の一部の桁だけの情報から計算できるとき 局所計算可能であるという.局所計算可能性と符号の冗長性の間には密接な関係があることが知られており 冗長符号化を利用した優れた並列アルゴリズムも幾つか知られている.実現の対象となる集合演算の代数的な性質と局所計算可能性の関係を調べる問題は 並列アルゴリズムの設計に関する基本的な問題である.ここでは 複数の単項演算が定義された有限集合に対する符号化について 冗長性と局所計算可能性の基本的な関係を議論する.まず 非冗長的な符号では 一般的には局所計算可能性できないことを示す.さらに 任意集合とその上の複数の単項演算に対して 結果の各桁がオペランドの2桁だけから決まるような局所計算可能な符号化は 任意の順序機械に対して パイプライン化した順序回路を構成する冗長な状態割当てが存在することを示している.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 31, 号 5, p. 740-747, 発行日 1990-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764