9

論理回路を作成して結果を確認するためのアプリケーションを作成する必要があります。これは主にAレベル(英国、一般的に16〜18歳)のコンピューティングコースで使用するためのものです。

私はこのようなアプリケーションを作成したことがないので、回路を保存して結果を評価するための最適な設計がわかりません(1.6Ghzシングルコアコンピューターで100Hzなどの再利用可能な速度で)。

基本的なゲート(and、or、nandなど)から回路を構築するのではなく、これらのゲートを使用して「チップ」を作成し、他の回路内で使用できるようにします(たとえば、8ビットを作成する場合があります)。レジスタチップ、または16ビット加算器)。

問題は、このような回路ではゲートの数が大幅に増えるため、個々のゲートでシミュレーションを実行すると、シミュレーションするゲートが数千になるため、回路に配置できるこれらのコンポーネントを単純化して、次のことができるようにする必要があります。すばやくシミュレートできます。

コンポーネントごとに真理値表を生成することを考えました。シミュレーションでは、ルックアップテーブルを使用して、特定の入力の出力を見つけることができます。そのようなテーブルのサイズが入力とともに大幅に増加するという問題が私に起こりました。チップに32の入力がある場合、真理値表には2^32行が必要です。これは、多くの場合、使用するよりも大量のメモリを使用するため、重要なコンポーネントには実用的ではありません。また、単純なものとして表すことができないため、状態を格納できるチップ(レジスタなど)でも機能しません。入力と出力の表。

レジスターチップのようなものをハードコーディングすることもできますが、これは教育目的であるため、ユーザーが独自のコンポーネントを作成したり、標準の実装を表示および編集したりできるようにしたいと考えています。このようなコンポーネントをコード(dllやスクリプト言語など)を使用して作成および編集できるようにすることを検討しました。これにより、たとえば加算器を「output = inputA + inputB」として表すことができますが、学生が十分なプログラミングを行っていることを前提としています。そのようなプラグインを理解して記述し、回路の結果を模倣できるようにするための言語が与えられていますが、そうではない可能性があります...

シミュレーションでコンポーネントの出力をすばやく決定できるように、ブール論理回路を自動的に単純化する他の方法はありますか?

コンポーネントの格納に関しては、入力にリンクするすべてのコンポーネントが評価された後に各コンポーネントが評価されるように、ある種のツリー構造を格納することを考えていました。

例:AB + Cシミュレータは、最初にANDゲートを評価し、次にANDゲートとCの出力を使用してORゲートを評価します。

しかし、出力が入力に戻ってリンクしている場合、入力がすべて評価されることはないため、デッドロックが発生することに気づきました...プログラムは1つのゲートで1つのゲートしか評価できないため、これを克服するにはどうすればよいですか?時間?

4

8 に答える 8

5

リチャードボウルズのシミュレーターを見たことがありますか?

于 2009-06-10T12:15:51.507 に答える
4

独自の回路シミュレータを構築したいと考えるのは、あなたが初めてではありません ;-)。

私の提案は、プリミティブの最小限のセットに落ち着くことです。私が私の仕事を始めたとき (近日中に再開する予定です...)、2 つのプリミティブがありました。

  • ソース: ゼロ入力、常に 1 の 1 つの出力。
  • トランジスタ: 2 つの入力AB、1 つの出力はA and not Bです。

明らかに、私は用語を少し誤用しており、エレクトロニクスの優れた機能を無視していることは言うまでもありません。2 番目の点については、私が行ったように 1 と 0 を運ぶワイヤに抽象化することをお勧めします。これらからゲートと加算器の図を描くのはとても楽しかったです。それらを回路に組み立てて、(入力と出力を含む) セットの周りにボックスを描くことができたら、乗算器などのより大きなものを構築し始めることができます。

ループが必要な場合は、何らかの遅延を組み込む必要があります。そのため、各コンポーネントはその出力の状態を保存する必要があります。サイクルごとに、上流コンポーネントの現在の状態からすべての新しい状態を更新します。

編集スケーラビリティに関する懸念については、各コンポーネントをその状態と上流の隣人に関してシミュレートする第一原理の方法をデフォルトにするのはどうですか。ただし、サブサーキットを最適化する方法を提供します。

  • S入力A[m]が m < 8 (たとえば、最大 256 行) で出力があり、ループがないサブサーキットがある場合はB[n]、真理値表を生成してSそれを使用します。これは、識別されたサブサーキットに対して自動的に行われる (サブサーキットが複数回出現する場合は再利用される) か、選択によって行うことができます。

  • ループを含むサブサーキットがある場合でも、真理値表を生成できる場合があります。ここで役立つ固定小数点検索方法があります。

  • サブ回路に遅延がある場合 (そしてそれらが含まれている回路にとって重要である場合)、真理値表に状態列を組み込むことができます。たとえば、サブサーキットに入力 A、内部状態 B、および出力 C があり、C <- A および B, B <- A の場合、真理値表は次のようになります。

    AB | 紀元前
    0 0 | 0 0
    0 1 | 0 0
    1 0 | 1 0
    1 1 | 1 1

  • ユーザーが「加算器」などの特定の既知のパターンを実装していると断言するサブサーキットがある場合は、その内部部分をシミュレートする代わりに、そのサブサーキットを更新するためにハードコードされた実装を使用するオプションを提供します。

于 2009-06-10T12:24:48.413 に答える
3

私が回路エミュレーターを作成したとき (悲しいことに、これも不完全でリリースもされていません)、ループをどのように処理したかを以下に示します。

  • 各回路要素はそのブール値を格納します
  • 要素「E0」がその値を変更すると、それに依存するすべての人に (オブザーバー パターンを介して) 通知します
  • 各観察要素はその新しい値を評価し、同様に行います

E0 の変更が発生すると、影響を受けるすべての要素のレベル 1 リストが保持されます。要素がこのリストに既に表示されている場合、その要素は新しいレベル 2 リストに記憶されますが、そのオブザーバーに通知し続けることはありません。E0 が開始したシーケンスが新しい要素の通知を停止すると、次のキュー レベルが処理されます。つまり、最初の要素がレベル 2 に追加された後、次の要素がレベル 2 に追加されます。というように、レベル x のすべてが完了するまで、シーケンスが実行されて完了します。その後、レベル (x+1) に移動します。

これは決して完全ではありません。複数のオシレーターが無限ループを実行している場合、それらをどの順序で実行しても、一方が他方のターンを妨げる可能性があります。私の次の目標は、コンビナトリアルをカスケードするのではなく、クロックベースの同期でステップを制限することでこれを軽減することでしたが、私のプロジェクトではこれまでのところ達成できませんでした。

于 2010-01-26T16:21:44.687 に答える
2

From Nand To Tetris in 12 steps コース ソフトウェアをご覧になることをお勧めします。ユーチューブで話している動画があります。

コースのページは次のとおりです: http://www1.idc.ac.il/tecs/

于 2009-06-10T12:21:36.207 に答える
1

一般的なものをすべてハードコーディングできます。次に、ハードコードされたもの(低レベルのゲートを含む)から独自のものを構築できるようにします。これは、各サブコンポーネントを評価することによって評価されます。最後に、それらの「チップ」の1つにX未満の入力/出力がある場合、ルックアップテーブルに「最適化」することができます。たぶんそれがどれほど一般的であるかを検出し、これを最も使用されているYチップに対してのみ行いますか?このようにして、速度とスペースのトレードオフが適切になります。

あなたはいつでも回路をJITコンパイルすることができます...

あまり考えていなかったので、どのようなアプローチを取るのかよくわかりませんが、ハイブリッド方式の可能性があり、人気のある「チップ」もハードコーディングしたいと思います。

于 2009-06-10T12:16:46.323 に答える
1

カルノー図の概念を紹介することで、真理値を単純化することができます。

于 2009-06-10T12:20:45.317 に答える
1

ループ (入力にリンクする出力) を禁止できる場合は、問題を大幅に単純化できます。その場合、すべての入力に対して、明確な出力が 1 つだけ存在します。ただし、サイクルは出力を決定不能にする可能性があります(というか、常に変化します)。

ループのない回路の評価は簡単です。リストの項目として「ジャンクション」(論理ゲート間の接続) を使用して BFS アルゴリズムを使用するだけです。「未定義」状態のすべてのゲートへのすべての入力から始めます。ゲートのすべての入力が「定義済み」(1 または 0) になるとすぐに、その出力を計算し、その出力ジャンクションを BFS リストに追加します。この方法では、各ゲートと各ジャンクションを 1 回だけ評価する必要があります。

ループがある場合、同じアルゴリズムを使用できますが、回路は決して「静止」せず、一部のジャンクションが常に 1 と 0 の間で変化するように構築できます。

OOps、実際には、ループされたゲート (およびそれらに依存するゲート) が「未定義」のままになるため、このアルゴリズムはこの場合には使用できません。

于 2009-06-10T13:21:51.420 に答える
1

「デジタル回路」シミュレーション環境の作成をいじっていたとき、伝達関数 (つまり、すべての出力、現在の入力に基づく)、「アジェンダ」構造 (基本的には「特定の伝達関数をいつアクティブにするか」のリンクされたリスト)、仮想ワイヤ、およびグローバル クロック。

出力が変化するたびに入力をハード変更するようにワイヤを任意に設定し、任意の回路の入力を変更して、ゲート遅延の後に呼び出される伝達関数をスケジュールします。これが手元にあると、クロックされた回路要素とクロックされていない回路要素の両方に対応できます(クロックされた要素は、その伝達関数が「次のクロック遷移とゲート遅延を加えた」ときに実行されるように設定され、クロックされていない要素はゲート遅延に依存します)。

そのための GUI を実際に作成したことがないので、コードをリリースしたことはありません。

于 2009-06-10T14:05:30.987 に答える