＞トップ
加算器の高速桁上げの方式の一つである、キルバーン加算器について、解説などがあまりないようなので書いてみます。
考案者はコンピュータのパイオニアのひとりである、トム・キルバーン氏で、陰極線管（ブラウン管）を記憶装置に利用するウィリアムズ管の共同発明者などの功績やマンチェスタ大学での活躍で知られています。詳細はウィキペディアの人物記事などを参照してください。ACMの学会誌CACMの2014年5月号にも記事があります。（加算器への言及は37ページ（3ページ目）の右のカラム中央付近のパラグラフに「Kilburn was not only responsible for the management of the project but also played a part in the circuit design, including work on an adder with a fast carry path.」とあります。）
(某月某日ちょっと修正)
このマンチェスタ大学のAtlasコンピュータプロジェクト（仮想記憶、特に単一レベル記憶の祖先として有名。余談だがこういった歴史により、同大学の研究や教育はある種フルスタック的だそうである）で開発された高速桁上げ方式の桁上げを指して、マンチェスタキャリー連鎖と呼ぶようですが、同様の考え方にもどづく少し違う構成のものも指すこともあるようです。原理的に、リレーのような信号の方向に制限が無く、H と L の他に無接続状態（いわゆる「Hi-Z」）もあるような素子以外では、実装的なトリックが必要であるため、何らかのアレンジが必然であるために、用語が指すものがはっきりしない、という側面があると言えるでしょう。本稿では「キルバーン加算器」で通します。
初出として参照に挙げられる文献は A parallel arithmetic unit using a saturated-transistor fast-carry circuit, T. Kilburn, Proceedings of the IEE Part B: Electronic and Communication Engineering(1960),107(36):573 のようですが、そちらは読めていません。米国特許（US 3,053,452と思われます）が参照可能ですが、特許の通例で簡単に読める表現にはなっていません。CMOS ICを使って簡単に実装した報告の A Fast-Carry Adder with CMOS Transmission Gates が良くまとまっていてわかりやすいと思います。
(某月某日加筆)なお、本稿の「キルバーン加算器」という表現の典拠ですが、英語のフレーズ "Kilburn adder" が、文献 A Fast-Carry Adder with CMOS Transmission Gates 中や米国特許 US 3,906,211 や US 3,932,734 にあるので、オーソライズされているものと考えてよいのではないかと思っています。
某月某日に、『情報処理』の第1巻第1号（！）の「マンチェスタ大学の高速桁上げ回路の追試と二,三の考察」という記事に気付きました。いろいろ興味深いことが書かれていたのですが、いまのところ本稿に反映できていません。(加筆ここまで)
高速桁上げは、普通は複数桁をまとめて扱いますが、ここでは特定のひと桁に注目します。
いわゆる高速加算器の桁上げはどれも、次のような3分岐による処理をどのように実装するか、という目的で作られているものと見ることができます。この3分岐がどれになるかの決定は、自分自身の入力ビットのみに依存し、下の桁からの桁上げの影響を受けないというのが、高速化のキモです（桁上げそのものは影響される）。
入力 (a, b) のうち、1のビットが、
普通はこれを普通の論理ゲートをごしゃごしゃやって実装するわけですが、3対1の切り替えスイッチのようなものを使って直接実装する、という実装方法も考えられます。それがキルバーン加算器です。最悪の場合のキャリー伝搬（最下位のキャリーが最上位まで通り抜けるような場合）が、演算ゲートではなく、あらかじめ伝達側にセットされた（伝達側への決定は桁毎に独立なので）スイッチを通り抜けるだけという点で高速化が期待できます。
論文のタイトルにあるように、原実装は飽和トランジスタを使ったものとみられます（飽和トランジスタとは、何らかの特別なトランジスタではなく、ベース電流を十分に流していわゆるスイッチング動作と言われている動作をさせるもので、TTL方式などにおける一般的な手法です）。バイポーラトランジスタは通常、双方向性ではないので、伝搬状態の実装についてはなんらかの工夫が必要だったはずです。
原理的には、理想的な素子はリレーです（最後の余談も参照）。ただしリレーは普通、無接続（Hi-Z）を0として扱いますので、その場合以下のCMOSの議論とは異なります。ここでは、参考にした文献でも使っているCMOS論理とCMOSスイッチを組み合わせたものを使います。
普通に使っているだけではあまり意識しませんが、FET(JFET)は双方向性の素子で、ドレインとソースは逆にしても同様に機能します（バイポーラトランジスタも基本構造としては対称だが、実用的に動作させるには事実上片方向になる）。
MOS FETは3本足のパッケージを使っている限りではバルク（あるいはサブストレート等）と呼ばれている電極がソース電極と共通の端子になっていて、寄生ダイオードの影響があるため（というより、その構造によりドレインとソースが区別されている）単方向素子になってしまっていますが、ICの内部ではバルクは独立していてソースとは別に電源線ないしグランド線に接続されているため（なのでMOS ICの内部を説明する図では、バルクが他に接続される特殊な構造の場合でなければ、バルクを省略した記号が使われることが多い）、MOS ICにより双方向性のあるアナログなスイッチを作ることができ、論理ゲートとしてはtransmissionゲートなどと呼ばれています（余談ですが、ネットにある回路図ではディスクリートのMOS FETとして、バルク電極が省略された記号が使われているのを見かけるが、良くないと思う）。
ここで（正電源、正論理とします）、NチャネルMOS FETは電源に近い電圧の信号は通しにくく、PチャネルMOS FETはグランドに近い電圧の信号は通しにくい、という性質があります。そのため両方の極性を使う必要があるので、実装にはCMOSが必要になります。
4066などの製品があり、記号にする場合は左のように書かれますが、中身は右のようになっています。なおこの回路の通りの中身だったのは4066で代替される前の4016（メーカーによっては別機能の製品に同じ番号を付番しているので注意）の場合で、4066という型番の製品はおおむねオン抵抗を下げた改良型になっています。
Pチャネル側はオンオフが負論理になるため、NOTゲートが入っています。ICの内部の回路の説明では、このような構造を反映して、「蝶ネクタイ」が1個ではなく2個並んでいて、反対側には反転の小丸の付いた制御入力端子が生えている記号が使われていることもあります。本稿では微妙な点の説明のため、この図の左のような省略記法は以降では使いません。
このスイッチの利用は他にもXORの省トランジスタ実装などに使われる他、電子制御の（機械的な接点の無い）オーディオセレクタや、なかにはJH2CLV OMによるRF変調・復調器の試作例といったものもあります。0Vを中心に正負に振る信号を通したい場合は、正負ともに電源電圧でクリップするので、正負両電源にする必要があります（バークレー版の無印SPICEでパーツを記述する場合に、引数となる端子の番号に 0 を使うとグローバルのグランド（基準電圧）に直結されてしまうので注意。NXPが配布している論理ゲート類のSPICE記述の中に、これ絡みでグランドと負電源が別だと顕在化するバグが入っているものがあります）。
IC内のMOS FETを表現する略記法（ノーマリーオフ型だが電極を破線にしない、バルク電極は省略、Pチャネルは電極に丸を付けて表現）を使っています。
参考資料 A Fast-Carry Adder with CMOS Transmission Gates の Fig. 3 を参考にしましたが、スイッチまわりは詳細になるよう書き直しています。後述のSPICE記述ではNAND・NORゲートを1段目のXORのための回路と共用していますので、XORを既にあるものとして書いているのは、実装を省略しています。
うまいことに、キャリーが1になる場合の反転はNANDに、キャリーが0になる場合はNORになるので、CMOS正論理では最小限のトランジスタで実装できます。また、0の側も1の側も、両極性を通す必要が無いので、片方だけで済ますことができます。
高速桁上げとは無関係ですが、スイッチの駆動のために右の1個目のXORについてはその反転も作っているので、それを2個目のXORの実装のために使うこともできるでしょう。
SPICEでシミュレーションするための記述ファイルも置いておきます。
富士通のリレーを使った計算機は十進方式ですので、この回路と直接は関係ありませんが、池田敏雄氏の伝記などによれば、後によく知られるようになった高速化回路方式の多くが、リレーによる計算方式の考察中に考え出されていた、という話がありますので、この回路もその中にあるやもしれません。