Leading Zero Anticipatory (LZA)は、二進法で表されたNビット符号つき整数A, Bを受け取り、A+Bを直に計算することなしにA+B+1の上位に0が何ビット並ぶか（Leading Zero Count, LZC）を（多少の誤差の範囲で）予測することです。以前の記事（Leading Zero Anticipation (LZA) の勉強 - よーる）では、適宜左右オペランドを交換することでA+Bが常に非負となることを仮定する方式を紹介しました。この方式の欠点は、Aの絶対値とBの絶対値の大小比較というΘ(log N)段の回路の出力を待つ必要がある点です。

よく考えてみると、左右オペランドの交換は不要です。 A+Bと-A-Bを並列に計算しておいて、最後の方でA+Bの符号を見て選択すればよいからです。 LZAの計算もLZC(A+B+1)とLZC(~A+~B+1)の両方を予測しておいて、最後で選択すればよいです。

これに対しIntelは、この二つのLZAの計算には重複する部分があるので同時にやることで回路量を減らせる、という特許を取りました。この特許の方式では、|A+B+1|の上位に0が何ビット並ぶかを（多少の誤差の範囲で）予測します。以下では、この方式を「絶対値のLZA」と呼ぶことにします。

この特許US7024439B2 - Leading Zero Anticipatory (LZA) algorithm and logic for high speed arithmetic units - Google Patentsは2023年8月にExpiredになったようです（でもよく見てみると2018年5月の時点で料金未納により失効している？）。やや旬を過ぎた感がありますが、この方式についても勉強してみます。

※特許については法律の専門家や技術の専門家によく確認することを強く推奨します。

LZAの基本的な考え方

LZAは、基本的に次のアルゴリズムになっています。

AとBを入力とするΘ(1)段の回路で、A+B+1の推定値Eを作成する
LZC(E)を出力する

LZCの計算方法は確立されているため、Eをどのように作るか、という部分がアルゴリズムの重要な点です。

絶対値のLZAであっても、考え方はほぼ同じです。つまり、AとBを入力とするΘ(1)段の回路で|A+B+1|の推定値Eを作り、LZC(E)を出力すればよいです。なお、Intelの特許ではこの推定値はLと呼ばれているので、以下ではLで統一します。

絶対値のLZAのアルゴリズム

この方式では、まず次のX[i], P[i], G[i], N[i], O[i], Z[i]の六つを計算します。

X[i] = A[i] xnor B[i]（xnorのXらしい）
P[i] = A[i] xor B[i]（いわゆるキャリー伝搬条件P）
G[i] = A[i] and B[i]（いわゆるキャリー生成条件G）
N[i] = A[i] nand B[i]（nandのNらしい）
O[i] = A[i] or B[i]（orのOらしい）
Z[i] = A[i] nor B[i]（zeroのZらしい）

次に、L[i]を次のように計算します。

L[0]は1
L[1]は0
2≦i<Nについて、L[i]は次の三つのnandの出力のnand
- nand( X[i], N[i-1] or N[i-2], O[i-1] or O[i-2] )
  - OAIゲートを使うことを想定しているっぽい
- nand( P[i], G[i-1], O[i-2] )
- nand( P[i], Z[i-1], N[i-2] )

このLについて、普通にLZCを求めます。その結果は、LZC(|A+B+1|)に対して-0か-1か-2だそうです。つまり、浮動小数点数の正規化に使う場合は、最後に余計に1bitまたは2bit左シフトする必要がある場合があるということです。

手を動かしてみる

以前に紹介した普通のLZAは、入力の二桁分（A[i]とB[i]とA[i-1]とB[i-1]）からEを生成しています。これに対して符号ビットを追加で考慮しないといけないので、もう一桁見ないといけないというのは直観的にわかります。とはいえ、実際に何をやっているのかは意味不明です。いろいろ実験してみることにします。

正の数と正の数を足す場合

4bit整数同士を足す実験をしてみましょう。そうすると、以下のようになっていることがわかります。

A+B+1が1か15～17か31の時、L[3:2]は00になる
A+B+1が7～9か23～25の時、L[3:2]は10になる
A+B+1が2か14か18か30の時、L[3:2]は01になる
A+B+1が3か13か19か29の時、L[3:2]は01か11になる
それ以外の時、L[3:2]は11になる

和が1になるときと16や31になるときで出力が同じなのを不思議に思うかもしれません。これは、おそらく2bit幅広の加算器が前提だからだと思います。加算した時の繰上りに備えて+1bit、符号ビットで+1bit、で合わせて+2bitです。

これを踏まえると、0～3と0～3を足したときだけがオーバーフローしてないことになります。この範囲では、

両オペランドが0だと、L[3:2]は00
- A+B+1は1なので、LZC-0を出力することになる
それ以外で両オペランドが1以下だと、L[3:2]は01
- A+B+1は2～3なので、LZC-1を出力することになる
それ以外だと、L[3]は1
- A+B+1は3～7なので、LZC-2かLZC-1を出力することになる

となっています。ここから読み取れる基本的な戦略としては、「A[i]とA[i-1]とB[i]とB[i-1]が0でA[i-2]かB[i-2]の少なくとも一方が1であればL[i]を立てる」ということでしょう。 A+B+1が $2^{i-2}$ 以上であることが確定するので、繰上りがなければLZC-2が、繰上りがあればLZC-1が出力されることになります。

特許文献の用語でいえば、ZZPとZZGのパターンになります。

負の数と負の数を足すとき

上述の実験結果は、15を境として対称になっていました。つまりL(A,B)=L(~A,~B)が成り立ちます。言い換えると、AとBを同時に反転しても同じ結果が出力されます。実際、AとBを同時に反転した場合、GとZが入れ替わり、NとOも入れ替わり、XとPは同じままです。回路がこの変換に対して不変であることを確かめるのは容易です。

よって、負の数と負の数を足すときの戦略は、「A[i]とA[i-1]とB[i]とB[i-1]が1でA[i-2]かB[i-2]の少なくとも一方が0であればL[i]を立てる」ということになります。

特許文献の用語で言えば、GGPとGGZのパターンになります。

負の数と正の数を足すとき

一番難しいのがこれです。 0～15に-1～-16を足す実験をしてみると、以下のようになります。

これがどういう法則に従っているかを一言で表すのはかなり難しいです。ただ、本来斜め線で区切らなければいけない範囲を、垂直な線と水平な線を組み合わせて何とか区切ろうと頑張っていることがわかります。また、斜めに走る0から遠くなればなるほど雑に区切っている（すべてのビットを見なくてよい仕組みになっている）こともわかります。

ここから読み取れる戦略としては、

A[i]とB[i]が0、A[i-1]とB[i-1]が1、A[i-2]とB[i-2]の少なくとも一方が0、のときL[i]を立てる
A[i]とB[i]が1、A[i-1]とB[i-1]が0、A[i-2]とB[i-2]の少なくとも一方が1、のときL[i]を立てる
A[i]とB[i]が異なり、A[i-1]とB[i-1]が0、A[i-2]とB[i-2]の少なくとも一方が0、のときL[i]を立てる
A[i]とB[i]が異なり、A[i-1]とB[i-1]が1、A[i-2]とB[i-2]の少なくとも一方が1、のときL[i]を立てる

となるでしょうか。ここで、1.は2.でAとBを同時に反転したもの、3.は4.でAとBを同時に反転したものです。

なお、提案されている回路では追加で以下の場合にもL[i]が立つようです（L[i+1]も立つので特に意味はありません）。これは回路の高速化に貢献しているようです（後述）。

A[i]とB[i]が0、A[i-1]^B[i-1]が1
A[i]とB[i]が1、A[i-1]^B[i-1]が1

特許文献の用語でいえば、1.はZGZとZGP、2.はGZPとGZG、3.はPZZとPZP、4.はPGPとPGG、5.はZPZとZPPとZPG、6.はGPZとGPPとGPGのパターンになります。

よくわかりませんが、Lに1を立てないといけないケースは"PGP, PGG, PZP, PZZ, ZZP, ZZG, ZPZ, ZPP, ZPG, GZP, GZG, GPZ, GPP, GPG, GGZ, GGP, ZGZ, and ZGP"と書かれているので、これで網羅したようです。

なにをやっているのか

3ビットと3ビットとキャリー入力（cin）を加算した結果3ビットの中に、01のパターンまたは10のパターンが必ず出現するかを判定しています。

手を動かしてみる

何も考えないと4³=64通りを考えなければいけませんが、各桁の計算において0+1と1+0を区別する必要はないため桁当たり3通りを考えればよく、3³=27通りを確認すれば十分です。以下では特許文献にならい、各桁の計算が0+0であることをZ、0+1か1+0であることをP、1+1であることをGと表します。 3ビット加算器の入力は、PGZのようにこのアルファベットを並べて表します。以下では、アルファベット3文字のことを局所パターンと呼びます。

ZZZ

000 + 000 + cin の計算です。結果は000か001になります。000であれば、当該パターンは出現しないので不可です。

ZZP

000 + 001 + cin の計算です。結果は001か010になります。条件を満たします。

ZZG

001 + 001 + cin の計算です。結果は010か011になります。条件を満たします。

ZPZ

010 + 000 + cin の計算です。結果は010か011になります。条件を満たします。

この辺まで来て、パターンが見えてきたと思います。結果はtまたはt+1になるのです。よって、tがいくつの場合に条件を満たすかを考えたほうが早いです。

まず、上で見たようにtが000だと当該パターンが出現せず不可です。また、tが110だとt+1は111で当該パターンが出現せず不可です。さらに、tが111の時はt+1が000となりどちらにせよ当該パターンが出現しないので不可です。他の場合は、常に01または10のパターンが出現するので条件を満たします。

よって、

ZZZ→t=0で不可
ZZP→t=1で可
ZZG→t=2で可
ZPZ→t=2で可
ZPP→t=3で可
ZPG→t=4で可
ZGZ→t=4で可
ZGP→t=5で可
ZGG→t=6で不可
PZZ→t=4で可
PZP→t=5で可
PZG→t=6で不可
PPZ→t=6で不可
PPP→t=7で不可
PPG→t=0で不可
PGZ→t=0で不可
PGP→t=1で可
PGG→t=2で可
GZZ→t=0で不可
GZP→t=1で可
GZG→t=2で可
GPZ→t=2で可
GPP→t=3で可
GPG→t=4で可
GGZ→t=4で可
GGP→t=5で可
GGG→t=6で不可

となって、特許文献の主張と一致します。

なぜこれでよいのか

000.....0001や111.....1110などのパターンを発見したいという目的に対して、01のパターンや10のパターンがある場合にLに立てればよい、という説明は直観的にわかりやすいものです。

気になるのは、01のパターンまたは10のパターンがない可能性があれば、本当は01のパターンまたは10のパターンを含むにもかかわらず、Lにビットが立たないことがある点です。つまり、

01/10のパターンが絶対にある場合→Lに1を立てる。よさそう
01/10のパターンが絶対にない場合→Lに1を立てない。よさそう
01/10のパターンがcinによってあったりなかったりする場合→Lに1を立てない。大丈夫かな？🤔

なぜこれで大丈夫のでしょうか。

局所的な説明

本当には01/10のパターンを含むにもかかわらず、Lにビットが立たないことがないことを示します。

GZZ（t=0）の場合

GZZが本当には01のパターンを含むのは、cinが1で答えが001だった場合です。この時、下側のペアが01のパターンを含んでいるので、一つ下の桁の上側のペアも01のパターンを含んでいます。よって、一つ下の桁でLにビットを立てたかを確認します。 GZZZでは下からキャリーが上がってこないので、GZZPかGZZGだったはずです。 ZZP （t=1）もZZG（t=2）もLにビットを立てますから、問題ありません。

PGZ（t=0）の場合

t=0なので、上と同じ状況です。 PGZZでは下からキャリーが上がってこないので、PGZPかPGZGだったはずです。 GZP（t=1）もGZG（t=2）もLにビットを立てますから、問題ありません。

PPG（t=0）の場合

t=0なので同じです。 PPGZでは下からキャリーが上がってこないので、PPGPかPPGGだったはずです。 PGP（t=1）もPGG（t=2）もLにビットを立てますから、問題ありません。

ZZZ（t=0）の場合

t=0なので同じです。 ZZZZでは下からキャリーが上がってこないので、ZZZPかZZZGだったはずです。 ZZP（t=1）もZZG（t=2）もLにビットを立てますから、問題ありません。

ZGG（t=6）の場合

ZGGが本当には10のパターンを含むのは、cinが0で答えが110だった場合です。この時、下側のペアが10のパターンを含んでいるので、一つ下の桁の上側のペアも10のパターンを含んでいます。よって、一つ下の桁でLにビットを立てたかを確認します。 ZGGGでは下からキャリーが上がってきてしまうので、ZGGPかZGGZだったはずです。 GGP（t=5）もGGZ（t=4）もLにビットを立てますから、問題ありません。

PZG（t=6）の場合

t=6なので同じです。 PZGGでは下からキャリーが上がってきてしまうので、PZGPかPZGZだったはずです。 ZGP（t=5）もZGZ（t=4）もLにビットを立てますから、問題ありません。

PPZ（t=6）の場合

t=6なので同じです。 PPZGでは下からキャリーが上がってきてしまうので、PPZPかPPZZだったはずです。 PZP（t=5）もPZZ（t=4）もLにビットを立てますから、問題ありません。

GGG（t=6）の場合

t=6なので同じです。 GGGGでは下からキャリーが上がってきてしまうので、GGGPかGGGZだったはずです。 GGP（t=5）もGGZ（t=4）もLにビットを立てますから、問題ありません。

PPP（t=7）の場合

111 + 000 + cin などの計算なので、結果は111か000になります。01/10パターンを絶対に含まないので、そもそも問題ではありません。

というわけで、01/10のパターンを含むか怪しくてLを立てないケースはcinが絡んで下側のペアに01/10が含まれるかを決定できないパターンのみであることがわかりました。また、その場合は一つ下の桁で正しく処理できているはずなので大丈夫、ということがわかりました。

大域的な説明

各パターンでどういった性質が成り立つのでLを立てて大丈夫、といったことを示します。

LZAのアルゴリズム的に、最上位の1より下のビットはどうでもいいということを多用します。つまり、証明すべきは

必要な位置にビットを立てられるか
必要でない位置にビットを立てないか

の二点です。ビットを立てた位置が必要な位置かどうか（つまり、「逆」）は示さなくていいということです。

ZZPとZZG

議論が全く同じになるので、ZZPで話を進めます。

上の桁まで見てPZZPだった場合はPZZの桁でLが立つので、この桁はどうでもいいです
上の桁まで見てGZZPだった場合はもう一つ上の桁を見ます
- ZGZZPかGGZZPならその桁でLが立つので、この桁はどうでもいいです
- PGZZPならさらにもう一桁上まで見て、ZPGZZPかGPGZZPならその桁でLが立つので、この桁はどうでもいいです
- PPGZZPならさらにもう一桁上まで見て、ZPPGZZPかGPPGZZPならその桁でLが立つので、この桁はどうでもいいです
- この考え方を続けていくと、PPP.....PPPGZZPとなっている場合のみが興味があるということになります
上の桁まで見てZZZPだった場合はもう一つ上の桁を見ます
- PZZZPだった場合はPZZの桁でLが立つので、この桁はどうでもいいです
- GZZZPだった場合は（GZZが同じなので）結局PPP.....PPPGZZZPになっている場合のみが興味があるということになります
- ZZZZPだった場合は（ZZZが同じなので）結局PPP.....PPPGZZZ.....ZZZPになっている場合とZZZ.....ZZZPになっている場合のみに興味があるということになります

というわけで、最後に残るのはPPP.....PPPGZZZ.....ZZZPとZZZ.....ZZZPのパターンです。

この時、次の性質が成り立ちます。

A+B+1は正（上位に0が並ぶので）
A+B+1は最低でも $2^{i-2}+1$ はある（Pの桁由来）
A+B+1は最大でも $3\times2^{i-2}$ より小さい（Pの桁より下の桁の和の最大値は $2(2^{i-2}-1)$ なので）

よって、L[i]を立てておけば、LZC-1かLZC-2が出力されます。

また、ZZGでも話はまったく同様で、次の性質が成り立ちます。

A+B+1は正
A+B+1は最低でも $2\times2^{i-2}+1$ はある（Gの桁由来）
A+B+1は最大でも $4\times2^{i-2}$ より小さい

よって、L[i]を立てておけば、LZC-1が出力されます。

GGPとGGZ

ZZP/ZZGのパターンの反転なのではしょっていきます。 GGPについて同様に興味があるパターンを探索してみると、GGG.....GGGPのパターンとPPP.....PPPZGGG...GGGPのパターンだということがわかります。

この時、以下の性質が成り立ちます（負の数なので直観的ではないですが）。

A+B+1は負（上位に1が並ぶので）
A+B+1は最低でも $-3\times2^{i-2}+1$ はある（GPの桁で111.....1101=-3）
A+B+1は最大でも $-2^{i-2}$ よりは小さい（GGG.....GGGG+1が-1なので、これと比べてGをPにした分だけ小さくなっていると思えばよい）

よって、L[i]を立てておけば、LZC-1かLZC-2が出力されます。

また、GGZの場合も同様に議論すれば、興味あるパターンで次の性質が成り立つことがわかります。

A+B+1は負
A+B+1は最低でも $-4\times2^{i-2}+1$ はある（GZの桁で111.....1100=-4）
A+B+1は最大でも $-2\times2^{i-2}$ よりは小さい（GGG.....GGG+1が-1なので、これと比べてGをZした分だけ小さくなっていると思えばよい）

よって、L[i]を立てておけば、LZC-1が出力されます。

ZGZとZGP

ZGZについて同様に興味あるパターンを探すと、PPP.....PPPZGZのみが該当します。このとき、

A+B+1は負
A+B+1は最低でも $-4\times2^{i-2}+1$ はある（GZの桁で111.....1100=-4）
A+B+1は最大でも $-2\times2^{i-2}$ よりは小さい

よって、L[i]を立てておけば、LZC-1が出力されます。

ZGPの場合はそれよりも $2^{i-2}$ だけ大きい（ゼロに近い）ので、L[i]を立てておけばLZC-1かLZC-2が出力されます。

GZPとGZG

ZGZ/ZGPの反転パターンなので省略します。

PZZとPZP

PZZについて同様に興味あるパターンを探すと、PPP.....PPPZZのみが該当します。このとき、

A+B+1は負
A+B+1は最低でも $-4\times2^{i-2}+1$ ある（ZZの桁で111.....1100=-4）
A+B+1は最大でも $-2\times2^{i-2}$ よりは小さい

よって、L[i]を立てておけば、LZC-1が出力されます。

PZPの場合はそれよりも $2^{i-2}$ だけ大きい（ゼロに近い）ので、L[i]を立てておけばLZC-1かLZC-2が出力されます。

PGPとPGG

PZZ/PZPの反転パターンなので省略します。

ZPZとZPPとZPG

ZPZについて上の桁を見るとZZPZかPZPZかGZPZかになりますが、いずれの場合でも上の桁でLが立つので、この桁はどうでもいいです。

ZPPとZPGの場合もまったく同様です。

GPZとGPPとGPG

GPZについて上の桁を見るとZGPZかPGPZかGGPZかになりますが、いずれの場合でも上の桁でLが立つので、この桁はどうでもいいです。

GPPとGPGの場合もまったく同様です。

念のため：L[n-1:2]=0だった場合

上でほとんどすべての議論が尽くされましたが、Lが全く立たなかったコーナーケースを考える必要があります。少なくとも一番下の3ビットが以下の組み合わせであることが必要であり、そこから上の桁を見ていってもずっとLが立たないパターンを探します。すると、以下の結論を得ます。

ZZZ

Lが全く立たないパターンは、ZZZ.....ZZZとPPP.....PPPGZZZ.....ZZZの二つです。いずれもA+B+1は1であり、L[1:0]=01のおかげでLZC-0が出力されます。

GGG

Lが全く立たないパターンは、GGG.....GGGとPPP.....PPPZGGG.....GGGの二つです。いずれもA+B+1は-1であり、L[1:0]=01のおかげでLZC-0が出力されます。

ZGG

Lが全く立たないパターンは、PPP.....PPPZGGです。A+B+1は-1であり、L[1:0]=01のおかげでLZC-0が出力されます。

GZZ

Lが全く立たないパターンは、PPP.....PPPGZZです。A+B+1は1であり、L[1:0]=01のおかげでLZC-0が出力されます。

PZG

Lが全く立たないパターンは、PPP.....PPPZGです。A+B+1は-1であり、L[1:0]=01のおかげでLZC-0が出力されます。

PGZ

Lが全く立たないパターンは、PPP.....PPPGZです。A+B+1は1であり、L[1:0]=01のおかげでLZC-0が出力されます。

PPZ

Lが全く立たないパターンは、PPP.....PPPZです。A+B+1は-1であり、L[1:0]=01のおかげでLZC-0が出力されます。

PPG

Lが全く立たないパターンは、PPP.....PPPGです。A+B+1は1であり、L[1:0]=01のおかげでLZC-0が出力されます。

PPP

Lが全く立たないパターンは、PPP.....PPPです。A+B+1がちょうど0になるパターンであり、L[1:0]=01のおかげでLZC-1が出力されたことになるのだと思います。

L[1:0]=10でいいのでは？

L[n-1:2]=0だった場合、用意されたL[1:0]=01のおかげでLZC-0かLZC-1が出力されます。一方で、L[n-1:2]≠1の場合、LZC-1かLZC-2が出力されます。つまり、L[1:0]=10とすることでL[n-1:2]=0だった場合にもLZC-1かLZC-2が出力されるようにすれば、出力の誤差範囲を狭くできるはずです。

実際、局所パターンはiビット目とi-1ビット目とi-2ビット目を見ていると考えるのではなく、iビット目とi-1ビット目に加えてその上（符号ビット相当）を見ている、と考えるほうが自然です。この考えのもとでは、上の方式は実はL[n-1:2]ではなくL'[n-2:1]を計算していた、ということになります。この時、L'[n-1]=0とL'[0]=1を合わせるとLZC-0かLZC-1が出力される方式になります。

なぜこうなっていないのかは謎です。

実際にLZC-0かLZC-1しか出力されないことを確かめるコードを以下に示します。

#include <iostream>
#include <cassert>

int get_estimate( int i, int j ) {
        int P = i ^ j;
        int X = ~P;
        int G = i & j;
        int N = ~G;
        int O = i | j;
        int Z = ~O;

        int n = N | N<<1;
        int o = O | O<<1;

        int L = X>>1 & n & o
              | P>>1 & G & O<<1
              | P>>1 & Z & N<<1 ;

        return L & 0x1fffe | 1;
}

long long count[2];

void check( int i, int j ) {
        int abs = std::abs(i + j + 1);
        int est = get_estimate(i, j);
        int diff = __builtin_clzll(abs) - __builtin_clzll(est);
        assert( 0 <= diff && diff <= 1 );
        ++count[diff];
}

int main() {
        for( int i = 0; i < 65536; ++i ) {
                for( int j = 0; j < 65536; ++j ) {
                        check(i,j);
                        check(i,-j);
                        check(-i,-j);
                }
        }
        std::cout << "LZA == LZC   " << count[0] << std::endl;
        std::cout << "LZA == LZC-1 " << count[1] << std::endl;
}

パターンの一覧

局所パターン	t	L[i]	分類	この局所パターンの責任が重大な場合の大域パターン	その時のA+B+1
ZZZ	0	0	L[i]が0	ZZZ.....ZZZ PPP.....PPPGZZZ.....ZZZ	1
ZZP	1	1	正＋正	PPP.....PPPGZZZ.....ZZZPxxx.....xxx ZZZ.....ZZZPxxx.....xxx	$[1\times2^{i-2}+1, 3\times2^{i-2})$
ZZG	2	1	正＋正	PPP.....PPPGZZZ.....ZZZGxxx.....xxx ZZZ.....ZZZGxxx.....xxx	$[2\times2^{i-2}+1, 4\times2^{i-2})$
ZPZ	2	1	正＋負の5	必ずL[i+1]=1となるため、存在しない。 L[i]=1とするのは回路高速化のため。
ZPP	3	1	正＋負の5	必ずL[i+1]=1となるため、存在しない。 L[i]=1とするのは回路高速化のため。
ZPG	4	1	正＋負の5	必ずL[i+1]=1となるため、存在しない。 L[i]=1とするのは回路高速化のため。
ZGZ	4	1	正＋負の1	PPP.....PPPZGZxxx.....xxx	$[-4\times2^{i-2}+1, -2\times2^{i-2})$
ZGP	5	1	正＋負の1	PPP.....PPPZGZxxx.....xxx	$[-3\times2^{i-2}+1, -1\times2^{i-2})$
ZGG	6	0	L[i]が0	PPP.....PPPZGG	-1
PZZ	4	1	正＋負の3	PPP.....PPPZZxxx.....xxx	$[-4\times2^{i-2}+1, -2\times2^{i-2})$
PZP	5	1	正＋負の3	PPP.....PPPZGZxxx.....xxx	$[-3\times2^{i-2}+1, -1\times2^{i-2})$
PZG	6	0	L[i]が0	PPP.....PPPZG	-1
PPZ	6	0	L[i]が0	PPP.....PPPZ	-1
PPP	7	0	L[i]が0	PPP.....PPP	0
PPG	0	0	L[i]が0	PPP.....PPPG	1
PGZ	0	0	L[i]が0	PPP.....PPPGZ	1
PGP	1	0	正＋負の4	PPP.....PPPGPxxx.....xxx	$[1\times2^{i-2}+1, 3\times2^{i-2})$
PGG	2	0	正＋負の4	PPP.....PPPGPxxx.....xxx	$[2\times2^{i-2}+1, 4\times2^{i-2})$
GZZ	0	0	L[i]が0	PPP.....PPPGZZ	1
GZP	1	1	正＋負の2	PPP.....PPPGZPxxx.....xxx	$[1\times2^{i-2}+1, 3\times2^{i-2})$
GZG	2	1	正＋負の2	PPP.....PPPGZGxxx.....xxx	$[2\times2^{i-2}+1, 4\times2^{i-2})$
GPZ	2	1	正＋負の6	必ずL[i+1]=1となるため、存在しない。 L[i]=1とするのは回路高速化のため。
GPP	3	1	正＋負の6	必ずL[i+1]=1となるため、存在しない。 L[i]=1とするのは回路高速化のため。
GPG	4	1	正＋負の6	必ずL[i+1]=1となるため、存在しない。 L[i]=1とするのは回路高速化のため。
GGZ	4	1	負＋負	GGG.....GGGZxxx.....xxx PPP.....PPPZGGG...GGGZxxx.....xxx	$[-4\times2^{i-2}+1, -2\times2^{i-2})$
GGP	5	1	負＋負	GGG.....GGGPxxx.....xxx PPP.....PPPZGGG...GGGPxxx.....xxx	$[-3\times2^{i-2}+1, -1\times2^{i-2})$
GGG	6	0	L[i]が0	GGG.....GGG PPP.....PPPZGGG.....GGG	-1

回路の高速化について

L[i]の生成回路の局所パターン27通りでの動作を確認します。以下では、 $n_i=N_{i-1}+N_{i-2}$ 、 $o_i=O_{i-1}+O_{i-2}$ とします。

局所パターン	i	i-1	i-2	$n_i$	$o_i$	$X_in_io_i$	$P_iG_{i-1}O_{i-2}$	$P_iZ_{i-1}N_{i-2}$	L[i]
ZZZ	X,N,Z	X,N,Z	X,N,Z	1	0	0	0	0	0
ZZP	X,N,Z	X,N,Z	P,N,O	1	1	1	0	0	1
ZZG	X,N,Z	X,N,Z	X,G,O	1	1	1	0	0	1
ZPZ	X,N,Z	P,N,O	X,N,Z	1	1	1	0	0	1
ZPP	X,N,Z	P,N,O	P,N,O	1	1	1	0	0	1
ZPG	X,N,Z	P,N,O	X,G,O	1	1	1	0	0	1
ZGZ	X,N,Z	X,G,O	X,N,Z	1	1	1	0	0	1
ZGP	X,N,Z	X,G,O	P,N,O	1	1	1	0	0	1
ZGG	X,N,Z	X,G,O	X,G,O	0	1	0	0	0	0
PZZ	P,N,O	X,N,Z	X,N,Z	1	0	0	0	1	1
PZP	P,N,O	X,N,Z	P,N,O	1	1	0	0	1	1
PZG	P,N,O	X,N,Z	X,G,O	1	1	0	0	0	0
PPZ	P,N,O	P,N,O	X,N,Z	1	1	0	0	0	0
PPP	P,N,O	P,N,O	P,N,O	1	1	0	0	0	0
PPG	P,N,O	P,N,O	X,G,O	1	1	0	0	0	0
PGZ	P,N,O	X,G,O	X,N,Z	1	1	0	0	0	0
PGP	P,N,O	X,G,O	P,N,O	1	1	0	1	0	1
PGG	P,N,O	X,G,O	X,G,O	0	1	0	1	0	1
GZZ	X,G,O	X,N,Z	X,N,Z	1	0	0	0	0	0
GZP	X,G,O	X,N,Z	P,N,O	1	1	1	0	0	1
GZG	X,G,O	X,N,Z	X,G,O	1	1	1	0	0	1
GPZ	X,G,O	P,N,O	X,N,Z	1	1	1	0	0	1
GPP	X,G,O	P,N,O	P,N,O	1	1	1	0	0	1
GPG	X,G,O	P,N,O	X,G,O	1	1	1	0	0	1
GGZ	X,G,O	X,G,O	X,N,Z	1	1	1	0	0	1
GGP	X,G,O	X,G,O	P,N,O	1	1	1	0	0	1
GGG	X,G,O	X,G,O	X,G,O	0	1	0	0	0	0

ZPZ, ZPP, ZPG（正＋負の5）, GPZ, GPP, GPG（正＋負の6）ではL[i]を何にしてもよいはずですが、L[i]=1とすることで回路が高速化することを見ていきます。 ZPZ, ZPP, ZPG, GPZ, GPP, GPGでL[i]=1とした場合、 $X_in_io_i$ の項は $X_i(N_{i-1}+N_{i-2})(O_{i-1}+O_{i-2})$ となります。これの反転はOAIゲート一段で作ることができます。一方で、L[i]=0とした場合、 $X_i(Z_{i-1}O_{i-2}+G_{i-1}N_{i-2})$ か、同じことですが $X_iZ_{i-1}O_{i-2}+X_iG_{i-1}N_{i-2}$ となります。前者は（反転を許しても）ゲート一段で作ることができないので、遅いです。後者の各項の反転はNANDゲートで作ることができますが、二項になるので、反転出力をORする意味合いで使われている最後のNANDゲートの入力数が増えてしまって、これも遅いです。このような意味合いで、ZPZ, ZPP, ZPG, GPZ, GPP, GPGでL[i]=1とすることは回路の高速化につながっています。

普通のLZAとの比較

以前の記事（Leading Zero Anticipation (LZA) の勉強 - よーる）で紹介した、普通のLZAのアルゴリズム（LZC(|A+B+1|)ではなくLZC(A+B+1)を予測するもの）と比較します。普通のLZAは、今回のZ, P, Gを使った解釈ではどのような動作をしているのでしょうか。

紹介した方式では、 $E_i = \lnot (A_i \oplus B_i) \land (A_{i-1} \lor B_{i-1})$ としていました。つまり、今回の表記に合わせれば、 $E_i = X_iO_{i-1}$ としているということになります。

二桁しか見ていないので、局所パターンは3²=9通りになります。この9通りについて、先と同じ考察をすると、以下のようになります。

局所パターン	t	E[i]	この局所パターンの責任が重大な場合の大域パターン	その時のA+B+1
ZZ	0	0	ZZZ.....ZZZ PPP.....PPPGZZZ.....ZZZ	1
ZP	1	1	ZZZ.....ZZZPxxx.....xxx PPP.....PPPGZZZ.....ZZZPxxx.....xxx	$[1\times2^i+1, 3\times2^i)$
ZG	2	1	ZZZ.....ZZZGxxx.....xxx PPP.....PPPGZZZ.....ZZZGxxx.....xxx	$[2\times2^i+1, 4\times2^i)$
PZ	2	0	必ず上位のどこかでEに1が立つため、存在しない。 E[i]=0とするのは回路単純化のため。
PP	3	0	※
PG	0	0	PPP.....PPPG	1
GZ	0	0	PPP.....PPPGZ	1
GP	1	1	PPP.....PPPGPxxx.....xxx	$[1\times2^i+1, 3\times2^i)$
GG	2	1	PPP.....PPPGGxxx.....xxx	$[2\times2^i+1, 4\times2^i)$

この動作は局所パターン中に1が絶対に含まれるか（00になることが絶対にないか）を判定していると解釈できます。発展版と同じ枠組みで考えてみると面白いですね。

ところで、PZがドントケアであることに注意しなければ、この解釈はできないことも面白いです。絶対値のLZAでもドントケアはあったものの、偶然にも素直に条件を解釈した実装が回路的にも最適でした。普通ののLZAでは、ドントケア部分についてあえて条件の解釈と異なる真理値を設定する方が回路が簡単になります。

※PPP.....PPPは入力を交換している制約から発生しないので、絶対値のLZAの時と同じ表の書き方をすると「責任が重大な場合の大域パターン」は存在しないことになる。実際には、PPP.....PPPxxx.....xxxはA+B+1が $[1, 2^{i-1})$ になるので、「1を立ててはいけない」という責任が常に存在する。 L[i]やE[i]が0になる局所パターンは「責任が重大な場合の大域パターン」として局所パターンが最下位に出現する場合のみ示していたが、実際にはこれとまったく同様に、それより下位にxxx.....xxxが続く場合も含めて常に「1を立ててはいけない」という責任がある。

まとめ

LZC(|A+B+1|)を予測するタイプのLZAのアルゴリズムを紹介し、その仕組みを詳しく明らかにしました。また、予測誤差を小さくできる、ささやかな改良を提案しました。