ASICのリバースエンジニアリング

ASICのリバースエンジニアリング

1. 1 GDSとは何か
2. 2 回路の復元
3. 3 回路の機能推測

Kjartan van Driel & Leander Post

Per aspera ad astra

Jane Streetは最近、ASICチップをリバースエンジニアリングし、その機能を解明して解答を提出することを目的としたパズルを公開しました。私は友人のLeanderに声をかけ、一緒に解けるかどうか試してみました。その過程で、解決への道のりは特に美しい形で図示できることに気づいたので、ここに私の試みを示します。

この記事は、私たちの解決策に沿ったもので、チャレンジにスケジュールを合わせられなかった方のために書かれています。まずGDS形式を調べ、次にシミュレーション可能な回路を復元し、最後にどのような入力が受け入れられるかを解明します。

Part I/III

GDSとは何か

GDSファイルはチップの物理レイアウトを記述します。そのレイヤーとセルが回路コンポーネントをどのように表現しているかを見ていくことから始めます。

2つのファイル

ウォームアップパズル（ぜひ試してみてください）を除くと、パズルは2つのファイル、puzzle.gdsとexample_inputs.vcdのみで構成されています。パズルの中心はGraphic Data System、すなわちGDSファイルです。例の入力は、単純なテストケースとして提供されています。1つの入力と、チップがそれに対して生成すべき出力が含まれています。

レイヤー

KLayoutのような専用プログラムでGDSファイルを開くと、その構造をすぐに確認できます。レイヤーによって示されるさまざまな種類のポリゴン（多角形）のレイアウトが記述されています。また、アノテーションも含まれており、最初にファイルを開いたときは全体がごちゃごちゃしているように見えます。

セル

GDSファイル形式では、ポリゴンをセルにグループ化できます。そのようなセルは一度定義すれば、何度も配置できます。これらは通常、ロジックゲートを定義し、それらがレジスタや計算ユニットなどを構成します。このような階層構造により、チップの設計がより管理しやすくなります。ただし、この階層構造は通常、Verilogでの高レベルな記述の結果であり、最終的にこのレイアウトに変換されます。セル境界は、元のVerilogがなくても、私たちが作業できる構造の一部を提供してくれます。

単なるレイアウト

GDSはレイアウトを定義しますが、それだけではそのレイアウトが実際に何を意味するのかについてはほとんど語りません。右側の図でさえ、レイヤーに色や太さを既に与えているため、ある程度示唆的です。ファイルだけを見ても、どのレイヤーが金属で、どれがシリコンで、製造プロセスがどのようにして動作するチップにそれらを変換するのかを知ることはできません。

それらを理解するには、チップが設計された製造プロセスを知る必要があります。各プロセスには、レイヤー番号が何を意味するのかについての独自の規則があります。これらは、プロセスデザインキット（PDK）のドキュメントとともに、さまざまな材料をどのように使用できるかのルールとともに文書化されています。したがって、回路の多くを読み取る前に、どのプロセスを見ているのかを知る必要があります。

プロセスの特定

幸いなことに、ロジックセルの名前が比較的直接的な手がかりを与えてくれます。それらは sky130_fd_sc_hd__ で始まり、これはSkyWater 130 nmプロセスの標準セルライブラリを識別します。標準セルライブラリは、チップ設計者が各ゲートをトランジスタから描画することなく使用できる、ロジックゲートやフリップフロップなどの既製のコンポーネントのコレクションです。

このプロセスとライブラリのドキュメントは公開されているため、レイヤーの意味とセルが何をするべきかの両方を調べることができます。これは、ポリゴンからすべてを自分で理解するよりもはるかに便利です。

レイヤー

そのドキュメントがあれば、レイヤーに名前を付け始めることができます。下部近くの nwell、diff、poly はトランジスタの部分を定義します。これらは後ほど詳しく見ます。そのすぐ上にあるのは li1 で、ローカルインターコネクトの略で、セル内でトランジスタを接続します。

その上には5つのメタルレイヤー、met1 から met5 があり、セルを配線したり、チップ全体に信号を伝達したりするために使用されます。複数のレイヤーがあることで、ワイヤが接触せずに交差できます。あるレイヤーのワイヤを次のレイヤーに接続するには、その間の絶縁材料を通る接続、つまりビアが必要です。カットレイヤー（/44で終わるもの）は、それらの接続がどこに行くかを指定します。

この区別は、ワイヤをたどろうとするときに重要になります。2つのポリゴンは、電気的に接続されていなくてもトップダウンビューで重なることがあるため、形状だけでなくレイヤーも追跡する必要があります。

レイヤー間の断面図。接続が示されています。厚さと間隔は、構造を見やすくするために調整されています。スケールは正確ではありません。

入出力

ファイルには、一部のレイヤーにテキストラベルも含まれています。トップレベルでは、これらはチップの入出力に名前を付けているため、どのように対話すべきかについてのアイデアをすでに得ることができます。

左側にはクロックの clk、rst_n、enable、I があります。右側には8ビットの O と、独立した success 出力があります。パズルは、success をハイにする入力を探すことを求めています。それがどのような入力になるかはまだわかりませんが、少なくともどこに送信し、どこで結果を確認すればよいかはわかっています。

セルのピン

ロジックセルの1つにズームインすると、別のラベルセットが見つかります。これらは、セルのどの部分が周囲の配線に論理的に接続されているかを示します。見ているセルはXORゲートで、2つの入力AとB、および出力Xがあります。

また、電源とグラウンド接続である VPWR と VGND もあります。これらはセルの上部と下部を走り、隣接するセルが共有できるようにします。ラベル自体は単なるアノテーションです。接続を形成するのは、各ラベルの下にある導電性材料です。後で、これらの位置を使用して、ゲートがどのように配線されているかを把握できます。

トランジスタ

私たちがこれまで見てきたロジックゲートは、トランジスタから作られています。私たちの目的のために、トランジスタを電気的に制御されるスイッチと考えることができます。1つの端子（ゲートと呼ばれる）にかかる電圧が、他の2つの端子（ソースとドレイン）間の電流の流れを決定します。

レイアウトでは、ポリシリコンのストリップが拡散領域を横切っている場所を認識できます。ポリシリコンはゲートを形成し、その下のシリコンからは薄い絶縁層によって分離されています。両側の拡散がソースとドレインを形成します。したがって、これらの形状は描画で重なっていても、ゲートはそれ自体がその下の材料に直接接続されていません。

p基板 n+ ソース n+ ドレイン 空乏層 ポリゲート酸化膜 ソース ドレイン ゲート チャネル ゲートにかかる電圧は酸化膜の下にチャネルを引き寄せ、ソースからドレインへ電流が流れます。

トランジスタの断面図：ゲートは薄い絶縁層の上にあり、ソースとドレインはその両側にあります。

これらのセルには2種類のトランジスタがあります。nMOSとpMOSです。大まかに言えば、nMOSはゲートが高いときに導通し、pMOSはゲートが低いときに導通します。これもまた単純化ですが、ここでどのように使用されているかを追跡するには十分です。この2つを組み合わせることで、入力に応じて出力を電源またはグラウンドに接続する回路を作成できます。

ゲート ドレイン ソース nMOS：ゲートが高いときに導通します ゲート ソース ドレイン pMOS：ゲートが低いときに導通します

nMOSとpMOSトランジスタのシンボル。pMOSゲートの小さな円は、ゲートが低いときに導通することを示しています。

右側の例は、セルから1つのトランジスタを抜き出しています。これは、GDSの形状が何を表しているかを理解するのに役立ちます。ただし、分析のためには、それらが形成するロジックゲートで作業できます。

XORゲート

XORゲートは簡単な例です。2 2つの入力 A と B、および1つの出力 X があります。入力が異なれば、出力は1です。同じであれば、出力は0です。内部でどのように実装されているかに関わらず、セル全体をこの1つの操作として扱うことができます。

レイアウトでは、A、B、X というラベルが li1 上の入力と出力接続を示しています。したがって、ゲートが何をするか、そしてどこに接続されているかを知っています。2つの入力ワイヤの値がわかれば、出力ワイヤの値を計算し、それが接続されているどのゲートにも渡すことができます。これらのセルを使用してチップをシミュレートする方法です。

XOR回路図と、そのレイアウトの薄いコピー。

フリップフロップ

ほとんどのセルは多かれ少なかれ直接的です。その出力は、現在入力にあるものに関数です。フリップフロップは少し異なり、回路が値を記憶できるようにします。

データ入力 D、出力 Q、そして重要なクロック入力 CLK があります。クロックがローからハイに変わるエッジで、D の値が Q の新しい値になり、それ以降は次の立ち上がりエッジまでそこに留まります。それまでの間に D に何が起こっても関係ありません。

クロック、データ、および格納されたビット。Q は、クロックの立ち上がりエッジでのみ D の値を取り、次のエッジまで保持します。

これは多くのニュアンスを無視しています。実際のフリップフロップにはセットアップ時間とホールド時間があり、クロックはすべての場所に正確に同時に到達するわけではなく、これらの遷移は実際には瞬時ではありません。しかし、私たちがやろうとしていることにとっては、それらのどれもあまり重要ではありません。チップの論理的な動作だけが重要なので、立ち上がりクロックエッジを、すべてのフリップフロップが更新する1つの正確な瞬間として扱うことができます。

ここに示されているフリップフロップには、アクティブローリセットである RESET_B もあります。これをローにすると、クロックエッジを待たずに Q がゼロに強制されます。

チップには92個のフリップフロップがあります。したがって、回路が時間とともに連続的に変化することを考える代わりに、それを92ビットの状態として考えることができ、クロックは通常の操作中にそれらのビットがいつ更新されるかを決定します。

クロックバッファ

バッファはあまり面白くありません。それらは単にクロック信号を長距離伝送するためだけに存在します。物理的には、小さなゲートが長いワイヤや他の多くのゲートを十分に速く駆動できない場合があるため、バッファが間に配置されて信号を駆動するのを助ける必要があります。

私たちにとっては、これらはほとんど無視できます。クロックを追跡するだけで十分です。

チップ全体に戻る

セルを実装されているコンポーネントの種類で色分けすると、チップの大部分が同じ少数のビルディングブロックからできていることがわかります。レイアウトは依然として圧倒的ですが、今では何を見ているのかについてのアイデアを得ることができました。

チップ全体が何をするのかを理解するには、それらのコンポーネントがどのように接続されているかを知る必要があります。これは、ワイヤをたどることを意味し、パート2でそれを行います。

注釈

1. 混乱を招くことに、「ゲート」はトランジスタの制御端子と、このXORのようなロジックゲートの両方を指すことがあります。XORゲートは、それぞれ独自のゲート端子を持つ複数のトランジスタを含む完全な回路です。↩

Part II/III

回路の復元

セルの機能がわかったら、それらがどのように接続されているかを決定する必要があります。これにより、シミュレーションして提供された例と比較できるネットリストが得られます。

セルの抽象化

パズルの目的のために、個々のトランジスタをシミュレートする必要はありません。セルの名前からsky130プロセスを特定したのと同じように、セルの機能も名前から推測できます。各セル名はそのコンポーネントを説明しています。xor2 はXORゲート、and4bb は2つの入力が反転された4入力ANDゲートなどです。

これを知っていれば、チップ上の各セルをそれが表す論理コンポーネントとして扱うことができます。唯一の問題は、どのコンポーネントが互いに接続されているか、そしてどのように接続されているかを直接知らないことです。

セルの接続先

コンポーネントを接続するには、2つのことを知る必要があります。セルのどの部分が論理的にゲートのどの部分に対応するか？そして、どの導電性ワイヤが2つのセルを接続するか？

最初の質問は、レイヤー 67/5、別名 li1 label で答えられます。そこで、セルへの入力と出力のアタッチメントが見られます。XORゲートの場合、これらは入力用の A と B、出力用の X です。電源とグラウンドラベル VPWR と VGND は、68/5、つまりmet1 labelレイヤーにあります。

これらのラベル自体は導電しません。信号ラベルは、その下にある導電性材料、レイヤー 67/20、つまりセル間の配線に使用される最も低い配線レイヤーである li1 drawing を参照します。各信号ピンラベルは、その下の li1 コンダクタを識別します。同じコンダクタレイヤーで重なる形状は接続されています。別のレイヤーへの接続には、適切なコンタクトまたはビアが必要です。

コンポーネントの接続

当然、2つのセルは導電パスがある場合に接続され、何がコンダクタと見なされるかは、チップの製造に使用されている技術によって定義されます。sky130の場合、再び図を参照します。met レイヤー（および li1）は長距離を導通します。これらのレイヤーはビアによって接続されており、レイヤーからレイヤーへと導通します。

同じ導電レイヤーで重なるポリゴンは接続されています。コンタクトまたはビアが隣接するレイヤーを接続します。図は概略図であり、スケールは正確ではありません。

ワイヤの追跡

次に、接続されたコンダクタをたどって各ワイヤをトレースするだけです。

すべてをまとめ、コンポーネントを追跡することで、ネットリストが得られます。

ネットリストの導出

これらの接続をたどると、ゲートのリストとどのピンがワイヤを共有しているかがわかります。これがネットリストです。各ゲートについて、そのセルタイプを保持して機能を知り、各ピンについて、どのワイヤに接続されているかを記録します。

1つのワイヤが複数のゲートに接続される可能性があり、それが到達する特定のピンを追跡する必要があります。フリップフロップのデータ入力 D に接続することは、クロック入力 CLK に接続することとは大きく異なります。たとえ両方の接続が同じコンポーネントに到達してもです。

その情報があれば、回路をグラフとして描画できます。コンポーネントはもはやダイ上の配置場所に座っている必要はありません。接続をたどりやすくするために配置できます。また、ゲートの論理的な動作を計算する際に供給を固定値として扱うため、電源ラインはこのビューから除外しています。

バッファの無視

クロック配線も簡略化できます。クロックバッファは同じ論理信号を繰り返すため、それらをたどってどのクロックが各フリップフロップを駆動しているかを確認できます。このチップでは、すべて同じ立ち上がりエッジで更新されます。シミュレーションでは、これをすべての格納ビットが更新される1つの瞬間として扱うことができます。

それらの更新の間、フリップフロップは Q 上の現在の値を保持します。チップ入力とともに、これらは計算を開始するために必要な値を提供します。ゲートのすべての入力がわかれば、その出力を計算し、それに接続されているゲートで使用できます。チップ出力と、すべてのゲートの D 入力上の値が得られるまで続けます。

次に、すべてのフリップフロップを一度に更新し、各 D 値を対応する Q にコピーします。リセットまたはセットがアサートされていない限り。これは重要です。なぜなら、すべての新しい値はクロックティック前の状態から計算されているはずだからです。これで92個の格納ビットの次のセットが得られ、次のサイクルの計算を繰り返すことができます。これは回路を実行するのに十分です。

回路のテスト

これで、提供されたもう1つのファイル、example_inputs.vcd に戻り、シミュレータが実際に機能するかどうかを確認できます。VCDファイルは、信号が時間とともにどのように変化するかを記録します。まず信号の名前をリストし、次にタイムスタンプとそこで変化する値を与えます。この場合、チップに送信された入力と、チップが生成した出力の両方が含まれているため、比較対象があります。

例は、チップをリセットするために3クロックサイクルで rst_n をローに保持することから始まります。次に enable をハイに設定し、I を介して121ビットを送信します（サイクルごとに1ビット）。それらが送信されると、enable はローになり、O から出力が読み取れます。シミュレータでまったく同じシーケンスをたどり、O と success が記録と一致するかどうかを確認できます。記録全体で、比較可能な730個の出力ビット値はすべて一致します。これは、すべての接続を正しく復元したことを証明するものではありませんが、シミュレートしている回路が期待どおりに動作することへのある程度の信頼を与えてくれます。

O の出力は8ビット幅であり、それらのバイトをASCIIとして解釈すると TRY AGAIN になります。シミュレータに関しては安心できますが、チップが何を求めているかについてはあまりわかりません。それを知るには、回路が実際に何をするのかを見る必要があります。

Part III/III

回路の機能推測

これで、回路を任意の入力で実行できます。受け入れられる入力を探すには、それが何をチェックしているかを理解する必要があります。パズルは、コンポーネントの位置が意味を持つことを示しているので、レイアウトを使用して回路を小さな部分に分割し、それらの動作を調べます。

レイアウトの確認

ヒントに従って、コンポーネントを場所ごとにグループ化します。右側の長い領域の先端から出力ライターを分割すると、合計11の領域が得られます。出力ライターをR11と呼びます。これは、別個に考慮できるというヒントに従っています。

信号を伝達するセルの中で、これらの領域の外側にあるものはクロックバッファです。領域図からは除外しますが、どのクロックがフリップフロップを駆動しているかは追跡します。

これらの境界を描画することで、各領域のロジックを分離し、独自の入出力を持つサブコンポーネントとして扱うことができます。

私たちの分析は、各コンポーネントの動作を調べるだけで済みます。おそらく、さまざまな入力の下でのメモリビットの動作や、領域内の構造を調べることになるでしょう。

では、どの領域を選択すべきでしょうか？

領域の接続方法

これに答えるには、ネットリストを使用して領域が互いにどのように接続されているかを確認する必要があります。領域の機能が、そこに流れる情報の意味を知ることで、より簡単に理解できるかもしれません。一部の領域は出力の近くにあります。例えば、success ビットを提供するR10や、O を書き込むR11です。多くの入力、出力、メモリビットを持つ領域（R5、R7など）や、入力が少ない領域（R1など）もあります。

領域の順序付け

これで、領域をグラフとして描画し、情報がそれらの間でどのように渡されるかに従って配置できます。

次に、領域が情報フローのどこに位置するかを見るために、各コンポーネントの栄養段階を確認できます。これは生態学の尺度で、食物網における位置を、獲物から捕食者まで大まかに定義します。私たちにとっては、入力から出力までの意味になります。

栄養段階を考慮して描画された領域は、どこから始めるべきかを示唆しています。領域1が食物連鎖の底辺にあり、下流に供給する傾向があることがわかります。

この順序、R1からR11で領域を調べます。フィードバックにより、一部の後続領域が先行領域に供給するため、有用な方向性が得られます。

途中、機能が判明したら、領域に説明的な名前を付けます。

R1

最初の領域、領域1は、底辺にあるだけでなく、偶然にも（完全にではないですが）最も単純です。クロックとリセットを除くと、入力ビットは1つだけで、これは領域3から来ます。

この場合、入力ビットがオフの場合にメモリビットの動作と出力をクロックが進むにつれて単純に確認できます。

結果は単純です。入力がオフの場合、メモリビットは何も起こりません。オンになると、ティックごとに遷移が見られます：0001、1000、1001、0010、0011、1010、1011、0100、0101、1100、0000、そして0001に戻ります。11個の異なる値があり、その後繰り返されます。これらの値は正確にバイナリでカウントしているわけではありませんが、それは問題ではありません。

また、前のセクションから、入力は合計121ビットであり、これはすでに非常に示唆に富むので、11x11グリッド上の121ビットのそれぞれについてカウンターの値を視覚化できます。

グリッドの各セルは、そのビットが到着したときにカウンターが保持していた値で色付けされています。11個の値があり、11列が見えます。

グリッドの各列に一意の値があるため、これを列カウンターと呼びます。

出力ワイヤも確認する必要があります。4つはメモリに格納されている情報を単に渡します。また、11回のカウントの各ラウンドを完了するティックでパルスするもう1つのビットがあります。3つの領域がそのワイヤを読み取ります。そのうちの1つが次のR2です。

R2

2番目の領域は、列カウンターと同じ入力を持ち、11回のカウントのラウンドの終了を示す追加ビットがあります。

再び、領域3からのビットがオフである限り、何も起こらないことを観察します。同様に、列カウンターからのパルスがオフである限り、何も起こらないことに気づきます。これは11回のカウントのラウンドの終わりにオンになります。

両方がオンの場合、内部メモリ状態が変化し、再び11個の異なる値でサイクルすることがわかります。

グリッドをこのカウンターの値で色付けした同じグリッド。これは11ビットずつ保持されるため、縞模様は反対方向に走ります。

再びグリッドでこれを視覚化すると、列カウンターの回転バージョンが見えます。行があり、行カウンターができます。これら2つを組み合わせることで、11x11グリッド上の点の座標が得られます。

ここでは、出力ワイヤは同じです。カウンターの値を渡す4ビット、そして121ビットの入力が完了したときにオンになるもう1つのビットです。

R3

次に、両方のカウンターに供給する小さなボックスが登場します。1つのメモリビットがあります。入力は enable ポートと、両方のカウンターからの2つのラウンドパルスです。2つの出力があります。1つは入力ビットが受け入れられるかどうかを制御します。もう1つはR10に入力が完了したことを伝えます。

入力ゲートは、enable がハイで、121ビット未満が受け入れられたときにオンになります。メモリビットは、両方のカウンターが入力の完了を記録します。その後、別の試みにはリセットが必要です。

したがって、このワイヤは、入力ビットが現在カウントされているかどうかを、入力を読み取っているボックスに伝えます。

R4

次のボックスにはメモリビットがまったくありません。列カウンターの4ビットと行カウンターの4ビットを読み取り、4本のワイヤを先に書き込みます。

メモリがないため、出力は2つのカウンターの固定関数であり、クロックさえ必要ありません。カウンターを121個の位置すべてに設定し、4本のワイヤを読み取ります。

それらは11個の異なる値を取ります。グリッドをこれらの値で色付けすると、同じ値を持つセルはパッチを形成し、サイズが4セルから28セルまで、かなり奇妙な輪郭を持つ11個のパッチが得られます。

4本のワイヤで色付けされたグリッド。11の値、11のパッチ、そして同じものはありません。

結果をグリッド位置からパッチ番号へのルックアップテーブルとして記述できます。この実装は147個のゲートを使用しています。現在のセルがどのパッチに属するかを示します。これをパッチマップと呼びます。

R5

最初の大きなボックス、22個のメモリビットがあります。実行する前に、配線方法を確認します。ボックス内に留まるワイヤだけをたどると、バッファを除外した後、残りの96個のセルが11個の別個の部分に分かれ、それぞれに2つのメモリビットと1つの出力ワイヤがあり、それらの部分はまったく互いに通信しないことがわかります。したがって、これは1つの小さなマシンの11個のコピーであり、1つだけ理解すれば十分です。

各部分は、列カウンター、入力ゲート、および I を読み取ります。行カウンターからの信号はありません。したがって、すべての行で同じように動作するはずです。

1つの部分を取り、実行します。2ビット、4つの状態。入力ゲートがオンで、I が1で、列カウンターが特定の値にある場合にのみ変化し、その後00、01、10、11と進み、11で停止します。出力ワイヤは状態10でのみオンになります。

1つの部分を4つの状態として示します。1はそれを先に進め、0はそのままにし、3でカウントを停止し、出力は2でのみオンになります。

したがって、各部分は1つの列の1の数を数え、3で停止し、ちょうど2で「はい」と言います。与えられた入力では、最初の部分は11で終了します。なぜなら、その列には4つの1があるからです。11個の「はい」ワイヤは、次の大きなボックスにまとめて送られます。

これを列カウントと呼びます。

R6

次のボックスは再び小さく、3つのメモリビットがあります。列カウンターとそのラウンドパルス、入力ゲート、および I を読み取ります。2本のワイヤがR8に、1本がR10に送られます。

そのセルは4つの部分を形成しますが、そのうち3つは単一のセルです。2つのORゲートがR8に現在の列がグリッドのどちらかの端にあるかどうかを伝え、1つのタイセルが定数を供給します。重要な部分は15個のセルとすべての3つのメモリビットを持っています。

2つのビットは現在の行の1の数を数え、3で停止します。行の終わりにカウントがリセットされます。

3番目のビットはフラグです。オンになると、オンのままになります。与えられた入力で実行すると、最初の行の最後のセルでオンになり、その行には3つの1があります。列カウンターを読み取るため、行の終了位置を知っています。フラグは「行が間違った数の1で終了した」を意味します。

これを行チェックと呼びます。

R7

このボックスは再び列カウントですが、入力が1つ交換されています。列カウンターの代わりに、パッチマップの4本のワイヤを読み取ります。再び11個の通信しない部分があります。

1つの部分を実行すると、同じ4つの状態とルールが得られますが、パッチ内の1の数で先に進みます。各部分はちょうど2つの1をそのパッチでチェックします。11個の「はい」ワイヤは、次のボックスにまとめて送られます。

これをパッチカウントと呼びます。

R8

このボックスには13個のメモリビットがあります。内部ワイヤをたどると、2つの部分が見つかります。メモリのない4つのゲートからなる小さな部分と、13個すべてのビットを持つ29個のセルからなる大きな部分です。

列カウントの11個の「はい」ワイヤが入力され、1本のワイヤが出力され、4つのゲートはANDツリーです。すべての11個がオンの場合にのみ出力がオンになります。これは「すべての列に2つある」ことを意味し、最後のボックスの直前に送られます。

より大きな部分では、12個のメモリビットがシフトレジスタを形成します。入力ゲートがオンの間、最初のビットは I を格納し、後続の各ビットは前のビットをコピーします。それらは前の12個の受け入れられた入力ビットを保持します。

入力は一度に1行ずつ到着する11x11グリッドであるため、これらの遅延に位置を与えることができます。前の入力ビットは、左隣のセルです。11ビット前は真上のセル、10ビットと12ビット前は右上と左上です。これらの4つの遅延は、存在する以前の隣接セルを識別します。R6からの2つの信号は、グリッドの左端または右端を横切る比較をマスクします。

前の12個の入力ビットと、比較に使用される4つの隣接位置。グリッドエッジでの比較はマスクされます。

残りのゲートは、それらの4つのビットと到着した I を組み合わせます。入力ゲートがオンの間、新しいビットが1であり、有効な以前の隣接セルも1である場合、13番目のメモリビットが設定されます。その後、それ自体にフィードバックされるため、一度設定されると、入力の残りの間は設定されたままになります。

それらの4つの比較も十分です。セルの他の4つの隣接セルは、右または下側にあり、まだ到着していません。それらが到着すると、現在のセルはそれらの4つの以前の隣接セルのいずれかになります。したがって、隣接するペアは1回だけチェックすれば十分です。

これは、エッジまたはコーナーに沿って2つの1が接触するかどうかをチェックします。これを隣接チェックと呼びます。

R9

次のボックスには8個のメモリビットがあり、前のボックスと同様に2つの部分があります。メモリのない4つのゲートと、8ビットすべてを持つ35個のセルです。

4つのゲートは以前と同じANDツリーで、今回はパッチカウントの11個の「はい」ワイヤに対してです。「すべてのパッチに2つある」ことを意味します。

もう一方の部分は、入力ゲートがオンの間 I をカウントします。実行すると、ビットはゼロで保持され、1で変化します。変化を追跡すると、256個の1が通過するまで値は戻りません。したがって、8ビットは、プレーンなバイナリではないコードで、到着するすべての1をカウントします。カウントが22のときにのみ1つの出力ワイヤがオンになります。与えられた入力には38個の1があるため、このワイヤは入力終了時にオフになります。

これを合計カウントと呼びます。

R10

このボックスは success ポートを駆動します。6本のワイヤを読み取ります。入力完了フラグ、行チェック、隣接チェック、「すべての列に2つ」、「すべてのパッチに2つ」、および合計カウントです。3つの信号が出力ライターに送られます。そのうちの1つが success ポートも駆動します。

ポートから戻ると、小さなゲートネットワークによって駆動されるメモリビットが見つかります。入力が完了した次のティックで、すべてのチェックがパスしたかどうかを記録します。その後、リセットされるまでその結果を保持します。与えられた入力では、ゼロのままです。

したがって、チップは、行ごとに2つ、列ごとに2つ、領域ごとに2つ、接触しない、合計22個の1を持つグリッドに「はい」と言います。これが成功ビットです。

長方形にはさらに2つのメモリビットがあります。1つは入力終了後に読み出しを開始します。もう1つは、すべてのカウントがパスしたが隣接チェックが失敗した場合を記録するため、出力ライターは異なるメッセージを選択できます。

ルール

一歩引いて、すべての領域とその機能をマッピングしました。要約すると、成功条件は次のとおりです。

• 行あたり2つ
• 列あたり2つ
• 領域あたり2つ
• 接触しない
• 合計22個

もし私があなたよりも注意深ければ、これらが2つのスターゲームのルールであることにすでに気づいているかもしれません。これはスターバトルです。チップはスターバトルバリディエーターであり、R4によってデコードされた11個のパッチがそのボードを分割します。

ソリューション

R11

これは出力ライター、無視できると言われたボックスであり、すべての中で最大です。12個のメモリビットと200以上のセルがあります。R10からの3本のワイヤ、合計カウントからの2本、入力ゲートと I を読み取り、8つの O ワイヤを書き込みます。

ここでは、さまざまな入力の下での動作を単純にチェックし、どのような出力が印刷されるかを確認できます。

謝辞

砂から星へ。

パズルを一緒に解き、ビジュアル作成を手伝ってくれたLeander Post、パズルを提供してくれたJane Street、カラーマップを提供してくれたFabio Crameriに感謝します。5

ClaudeとAstraにも感謝します。

注釈

1. 混乱を招くことに、「ゲート」はトランジスタの制御端子と、このXORのようなロジックゲートの両方を指すことがあります。XORゲートは、それぞれ独自のゲート端子を持つ複数のトランジスタを含む完全な回路です。↩