フレドキンゲートとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > フレドキンゲートの意味・解説 

フレドキンゲート

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/09/07 09:31 UTC 版)

フレドキンゲート: Fredkin gate)は、エドワード・フレドキンが提案した可逆論理ゲートである。単独でfunctional completeness (en:Functional completeness) を有しているので、任意の論理演算をフレドキンゲートだけを使って構成できる。

基本フレドキンゲートは、3つの入力 (C, I1, I2) と3つの出力 (C, O1, O2) を写像する「制御付き交換ゲート」である。入力 C はそのまま出力 C に対応する。C = 0 の場合交換はなされず、I1O1 に、I2O2 に対応する。そうでない場合2つの出力は交換され、I1O2 に、I2O1 にマッピングされる。入力と出力を入れ替えても同じに動作することから、この回路が可逆性であることは容易に示すことができる。これをさらに一般化した n×n フレドキンゲートは、最初の n-2 個の入力をそのまま対応する出力に出力し、残る2つは最初の n-2 個の入力が全て1の場合だけ交換して出力する。

入力 出力
C I1 I2 C O1 O2
 0   0   0   0   0   0 
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 0 1
1 1 1 1 1 1

フレドキンゲートは可逆3ビットゲートであり、最初のビットが1の場合に残る2ビットを交換して出力する。真理値表を右に示す。

0と1の個数が保存されるという便利な特性があり、ビリヤードボールモデルで入力されたボールの数と出力ボール数が同じになるのと同じである。これは物理学における質量保存の法則にもうまく対応し、このモデルが無駄ではないことを示す助けにもなっている。

XORゲートとANDゲートによる論理関数

フレドキンゲートをXORゲートANDゲートで構成する場合、次のようになる。

  • O1 = I1 XOR S
  • O2 = I2 XOR S
  • S = (I1 XOR I2) AND C

関連項目




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「フレドキンゲート」の関連用語

フレドキンゲートのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



フレドキンゲートのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのフレドキンゲート (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS