JPS60262242A - Ｆｉｆｏ回路 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 産業上の利用分野 本発明は非同期式先入れ・先出しくＦｉｒｓｔ−ＩｎＦ
ｉｒｓｔ−Ｏｕｔ：ＦＩＦＯ）回路に関し、特に、満杯
状態や空状態を検出する機構を極めて単純化し、ノ・−
ドウエアを激減させると共に、非同期性を完全にしたＦ
ＩＦＯ回路に関するもので、大型計算器やマイクロ・プ
ロセッサのキュー（Ｑｕｅｕｅ）レジスタや、データ転
−送に使われるＦ工ＦＯバッファなど、゛その利用範囲
は極めて広い。

従来例の°構成とその問題点 従来、ＦＩＦＯ回路の実現方法は２通りあシ、その第１
はシフトレジスタ方式、第２はメモリ方式である。シフ
トレジスタ方式は先入れ先出しの物理モデルに近く、書
き込まれたデータがレジスタの中を出力段に向って伝搬
（バブル・スルー）し、前回に書き込まれたデータの次
の段で停止し、読み出しを実行すると書き込まれたデー
タが出力段方向に１段シフトする方式である。この方式
は、大量のシフトレジスタとデータ伝搬を制御するレジ
スタ・コントロール・ロジックの多大なハードウェアを
必要とするだけでなく、バブル・スルーに要する時間が
大きく（例えば６４ワードの場合、３μＳ　程度）なり
、データの受け渡しに支障が生じる。このため、長い（
１２８ワ一ド以上）スタックのＦ、ＩＦＯを実現するの
は実用上難しい。次に、メモリ方式は２ボート・メモリ
、ライト・ポインタ（カラ／り）、リード・ポインタ（
カウンタ）。

それに書き込まれたデータのワード数を管理しアップ／
ダウン・カウンタとで構成され、ライト信号（シフト・
イン信号ともいう）でライト・ポインタをインクリメン
トし、アップ／ダウン・カウンタをカウント・アップす
る。リード信号（シフト・アウト信号ともいう）でリー
ド・ポインタをインクリメントし、アップ／ダウン・カ
ウンタをカウントダウンする。この方式はスタック数（
ワード数）が多くなってもバブル・スル一時間Ｕ　一定
（書き込み時間と各種カウンタ変化時間）であるという
メリットがあるが、一方、ライト信号とリード信号が同
時に来たとき正常に動作しないという欠点があった。

発明の目的 本発明は上述した従来例の欠点を改善すべく成されたも
ので、スタック数（ワード数）の多いＦＩＦＯに適した
メモリ方式を採用し、満杯（フル）や空（エンプティ）
状態を検出する機構を極めてシンプルにし′、ノ１−ド
ウエアを激減させると同時に完全な非同期性を有するＦ
ＩＦＯ回路を提供することを目的とする。

発明の構成 本発明ｄ、書き込みポインタと読み出しポインタとに２
Ｎ進カウンタ（最上位ビットにフリップ・フロップを、
以下のビットにはＮ進カウンタを配置した構成）を用い
、最上位ビット同志、Ｎ進カウンタの出力同志を各々一
致判定することによってフル／エンプティ検出を実現す
ることによシ、ＦＩＦＯ回路のハードウェアを惨めで単
純化することを可能にするものである。

実施例の説明 第１図に本発明の実施例を示す。本実施例は０ＭＯ８）
ランジスタで構成した８ワード×８ビツトのＦＩＦＯ回
路の例である。

１は８ワード×８ビツト、２ポートの記憶回路であり、
８本のライト・ワード・ラインＷ１７〜ＷＲ０により選
択されたメモリ・セルに入力データＤ７〜Ｄｏが吾き込
まれ、８本のリード・ワード・ラインＨＤ７〜ＲＤ０に
よシ選択されたメモリ・セルのデ−夕が読み出され、保
持されて出力データ０７〜Ｑｏを出力する。第２図に記
憶回路１の実施例の詳細な回路図を示す。

１０−００〜１０−７７は全く同様の６４個のメモリ・
セルである。１０２はＮチャネル・トランジスタで構成
されたライト用トランスファ・ゲートであり、１０３は
同様のリード用トランスン７・ゲートである。１００と
１０１は０ＭＯ３）ランジスタで構成されたインバータ
であり、フリップ・フロップを構成している。インバー
ター０１のドライブ能力は、インバーター００やインバ
ータ１２−０〜１２−７のそれに比べて十分に小さ−１
１−０〜１１−７は入力バッフ７用のインバータであり
、１２−０〜１２−７はドライブ能力の大きい書き込み
用のインバータである。１３−〇〜１３〜７と１４−０
〜１４−７は０ＭＯ３構成の、、：：　インバータであ
り、１３−ｎと１４−ｎ（ｎ＝。

〜７）とで７リツプ・７ｏツグを構成し、センス・アン
プ兼出力データ・レジスタの機能を果している。インバ
ーター３−０〜１３−７のドライブ能力はメモリーセル
（１０−００〜１０−’７７）内のインバータ１００の
ドライブ能力に比べて十分に小さ、い。

ライト；ワード・ラインＷＲ７〜ＷＲ０は各メモリ・セ
ルのライト用トランスファ・ゲートのゲート電極に接続
（ライン１本につき８個）されておシ、８不全てロー・
レベル（低論理レベル）か、又は８本のうち１本のみが
ハイ・レベル（高論理レベル）の体感となる。リード・
ワード・ラインＲＤ。

〜ＲＤｏは各メモリ・セルのリード用トランスファ・ゲ
ートのゲート電極に接続（ライン１１本につき８個）さ
れており、８不全てロー・レベルか、又は８本のうち１
本のみがハイ・レベルの状態となる。すなわち、ＷＲ７
〜ＷＲｏのうちの選択された１本ＷＲｎに接続された８
個のメモリ・セル１ｏ−７ｎ〜１Ｏ−Ｏｎにメ、カデー
タＤ７〜Ｄ０が書き込まれ、ＲＤ７〜ＲＤ０のうちの選
択された１本ＲＤｎ　に接続された８個のメモリ・セル
１Ｏ−７ｎ〜１Ｏ−Ｏｎのデータが読み出され、出力デ
ータ・レジスタ（１３−７と１４−７）〜（１ａ−ｏと
１４−０）　にラッチされ、出力データＱ７〜Ｑ０とな
る。

さて、第１図に戻り、２は書き込みアドレスを一出力す
る書き込みポインタであり、ここでは４ビツト・カウン
タ２０で構成されている。４ビツト・カウンタ２０は、
書き込み信号Ｗ−Ｒをインバータ７で反転した信号の立
ち上が９エツジでカウントアツプする。書き込みアドレ
スは４ビツト・カウンタ２０の下位ビット出力ｗ２〜Ｗ
ｏである。４は読み出しアドレスを出力する読み出しポ
インタであり、ここでは４ビツト・カウンタ４ｏで構成
されている。４ビツト・カウンタ４０は、読み出し信号
ＨＤをインバータ８で反転した信号の立ち上がりエツジ
でカウントアツプする。読み出しアドレスは４ビツト・
カウンタ４ｏの下位３ビツト出力Ｒ２〜ＲＯである。２
ｏと４ｏは全く同様のカウンタである。両者とも初期設
定用のクリア信号ＣＬＲでクリアされる。

３は、書き込み信号ＷＲに同期して、書き込みポインタ
２から出力される書き込みアドレスに対応したメモリ・
セルに入力データＤ７〜Ｄ０を書き込む書き込み回路で
ある。３の具体的な実施例を第３図に示す。３ｏは３ラ
インー８ライン・デコーダであり、書き込みポインタ２
から供給される３ビツトの書き込みアドレスＷ２〜Ｗｏ
を、どれか１本のみがハイ・レベルとなる８本のライン
Ｙ７〜Ｙｏにデコードする。３１−７−３１−０はＮＡ
ＮＤゲートで６．？、３２−７〜３２−０はそれぞれラ
イト・ワード・ラインＶＶＲ７〜ｗＲｏをドライブする
ためのインバータである。ＷＲ７〜ＷＲ０は書き込み信
号ＷＲでゲートされて出力する。第１図の５は読み出し
信号ｆｌＤに同期して、読み出しポインタ４から出力さ
れる読み出し”アドレスに対応したメモリ・セルからデ
ータを読み出す読み出し回路である。５の具体的な実施
例を第４図に示す。

５ｏは３ラインー８ライン・デコーダであシ、読み出し
ポインタ４から供給される３ビツトの読み出しアドレス
Ｒ２〜ＲＯをどれか１本のみがハイ・レベルとなる８本
のラインＹ７〜ＹＯにデコードする。５１−７〜５１−
０はＮＡＮＤゲートであり、５２−７〜５２−０はそれ
ぞれリード・ワード・ラインＲＤ７〜ｆＬＤ０をドライ
ブするためのインバータである。ＲＤ７〜ＲＤｏは読み
出し信号ＨＤでゲートされて出力する。さて、第１図の
６は、記憶回路１にデータが満杯（フル）に書き込まれ
ている状態か、データがすべて読み出されて空（エンプ
ティ）の状態にあるかを検出するフル／ユングティ検出
回路であり、具体的実施例の回路図を第５図に示す。６
０〜６３はＥＸＯＲ（排他的論理和）ゲート、６４は３
人、１７０８ゲート、６５はインバータ、６６ｔｒｉＡ
ＮＤゲート、６７ＪｄＮＯＲゲートである。簡単なロジ
ックであるから説明は省くが、書き込みポインタ２の出
力Ｗ３〜Ｗｏと読み出しポインタ４の出力Ｒ３〜ＲＯが
完全に一致している場合にのみＥＭＰＴＹ信号が出力さ
れ、下位３ビツトＷ２〜Ｗｏ（書き込みアドレスと同じ
）とＲ２〜ｎｏ　（読み出しアドレスと同じ）とが一致
し、かつ鼓上位ビットＷ３とＲ３が不一致のとｉ：　き
にのみＦＵＬＬ信号が出力される。

さて、第１図に戻って動作を説明する。初期設定時にク
リア信号ＣＬＲが印加されてカウンタ２０と４Ｑがクリ
アされオール″Ｏ″となる。これによシンル／エングテ
ィ検出回路６からＥＭＰＴＹ信号が出力され、空状態で
あ゛るからリードしてはいけないことを外部に知らせる
。以下、第６図に示す各種信号のタイム・チャートに従
って説明してゆく。これはＤ（１）〜Ｄ（３）の３個の
データをライトし、続けて同じデータを順にリードして
、次にＤ（４）〜Ｄ（１１）の９個のデ〜りをライト、
Ｄ（４）、し６）をリードして、Ｄ　（１２）をライト
、最後にＤ（６）をリードした場合の図である。書き込
みポインタ２の出力Ｗ３〜ＷＯと読み出しポインタ４の
出力Ｒ３〜ＲＯの状態を下部に示しである。Ｗ３〜Ｗｏ
。

）ｔ３〜ＲＯ共にＷＲ，ＲＤ倍信号後縁で変化する。

時刻ｔ１　でＥＭＰＴＹ信号がロー・レベルになるのは
、ＤＯ）をライトしてカウンタ２ｏがカウント・アソグ
してＷ３−’Ｗｏ（ｏｏｏｌ　）（Ｒ３−Ｒ。

（００００）となるためである。１２〜ｔ３では’Ｗ３
〜ＶＶＯ（００１１）＝Ｒ３−ＲＯ（００１１）となる
ためＥＭＰＴ’Ｙｉ号が立つ。ｔ４〜ｔ６　ではＷ３〜
ＷＯ（１ｏ１１）とＲ３−ＲＯ（００１１）の関係が、
Ｗ３＼Ｒ３かツＷ２−Ｗ’Ｏ＝　Ｒ２−Ｒ。

となるだめＦＬＩＬＬ信号が立つ。このとき、記憶回路
１の中には未リードの８個のデータＤ（４）〜Ｄ（１１
）が存在するため、これ以上ライトしてはいけないこと
を示している。′＝１：た、記憶回路に２ポートメモリ
を用いているため、動作中、区間Ｔ１やＴ２に見られる
様にＷｌ（とＲＤのオーバー・ラップが原理的に可能で
ある。即ち、ライトとリードが全く非同期に実行できる
。

次に、フル／エンプティ検出の原理を第７図を用いて説
明する。円内の４ビツト数は書き込みポインタ２の出力
（Ｗａ〜Ｗｏ）、又は読み出しポインタ４の出力Ｒ３〜
ＲＯを表わす。初期状態では、両ポインタとも（２）の
位置にいる。１回のライト動作で時計回りに１つ進む。

３個のデータをライトすればＷ３〜Ｗ　Ｏ（３）の位置
にくる。この状態で１ＶＶ３〜ＷＯ’４Ｒ３〜ｆＬｏで
あるからフルでもエスグティでもない。３回リードすれ
ばＲ３〜ＲＯも（３）の位置に「追いつき」、エンプテ
ィとなる。

これから８回ライトすることで、Ｗ３〜ＷＯは（１１）
の位置となるが、このとき満杯状態であって、両ポイン
タの状態を見るとＶｖ　３　（１）−Ｒｓ　（ｏ）、か
つＷ’２〜Ｗｏ（ｏｌｌ）＝Ｒ２〜Ｒｏ（ｏｌｌ）とな
ってい不。即ち、対角線上に位置し、「最も引き離され
た」状態にある。両ポインタは常に「ライト」が先行し
、「リード」が後から追いかけてゆくというパターンで
第７図のサークルを時計回りに回るのである。

従って、「ライト」と「リード」が同じポイントにきた
とき、すなわち空状態では、Ｗ３〜Ｗｏ＝Ｒ３〜ＲＯと
なり、「ライト」と「リード」が対角線上の位置にきた
（ライトとリードの差は８である）とき、すなわち満杯
状態では、Ｗ３＼Ｒ３かつＷ２〜ＷＯ−Ｒ２〜Ｒｏとな
る。

さて、第１図の実施例は８ワードというように２のべき
乗ワードの場合のＦＩＦＯ回路であるが、ワード数が２
のべき乗ワードでない場合にでも同様に実施できる。例
えば、５ワードのＦＩＦＯ回路の場合には、第１図の４
ビツト・カウンタ２０の代わ９に、Ｗ２〜ＷＯを出力す
る６進カウ／り（３ビット・カウンタで構成できる）と
この５進カウンタがフルカウントする毎に反転する、Ｗ
３を受けもつノリノブ・フロップとで構成した１０進カ
ウンタを用いる。読み出し側の４ビツト・カウンタ４０
についても全く同様の回路で置換する。こ　Ａの１０進
カウンタは、下位３ビツトがサイクリックに折り返し、
Ｗ３〜ＷＯ（又はＲ３〜ＲＯ）は００００→ＯＯＯ１−
＋−・−＋０１　００−＋１　０００−＋１００１→・
・・→１１００→ｏｏｏｏと遷移する。

第８図に第７図と同様な状態遷移図を示す。対角線上の
、２つの状態を見れば同様に実現できることが容易に理
解できる。

本発明は第１図の実施例に限定されることなく、例えば
４０９６ワード×３２ビツトの如き深いスタックのＦＩ
ＦＯ回路も同様に実現できる。

発明の効果 以上述べたように、本発明によれば、フルやエンプティ
状態を検出する機構を極めて単純化し、ハードウェアと
検出時間を激減させると共に、非同期性を完全にしたＦ
ＩＦＯ回路を得ることができ、データ転送のだめのＦＩ
ＦＯバッファやキュー・レジスタなど信号処理、データ
処理、コンピュータなどの分野で極めて高い効果を発揮
するものである。

【図面の簡単な説明】

第１図は本発明のＦＩＦＯ回路の一実施例を示すブロッ
ク図、第２図は第１図の１の具体的実施例を示す回路図
、第３図は第１図の３の具体的実施例を示す回路図、第
４図は第１図の５の具体的実施例を示す回路図、第５図
は第１図の６の具体的実施例を示す回路図、第６図は第
１図の各部信号のタイム・チャー１・、第７図は第１図
の書き込Ｖ読み出しポインタの状態遷移図、第８図はワ
ード数６の場合のポインタの状態遷移図である。 １・・・・・・記憶回路、２・・・・・・書き込みポイ
ンタ、３・・・・・・書き込み回路、４・・・・・・読
み出しポインタ、５・・・・・・読み出し回路、６・・
・・・・フル／エンプティ検出回路、ＷＲ・・・・・・
書き込み信号、ｌ（Ｄ・・・・・・読み出し信号。 代理人の氏名　弁理士　中　尾　敏　男　ほか１名第３
図 拓４図 に２＋／に０ 第５図

Claims (2)

【特許請求の範囲】
1. （１）Ｎワードのデータを記憶する記憶回路と、書き込
   み信号をカウントする第１のＮ進カウンタと該第１のＮ
   進カウンタがＮ個の上記書き込み信号をカウントする毎
   に反転する第１のフリップ・フロップとで構成され、上
   記第１のＮ進カウンタの出力を上記記憶回路の書き込み
   アドレスとして出力する書き込みポインタと、上記書き
   込み信号に同期して上記記憶回路の書き込みアドレスに
   入力データを記憶させる書き込み回路と、読み出し信号
   をカウントする第２のＮ進カウンタと該第２のＮ進カウ
   ンタがＮ個の上記読み出し信号をカウントする毎に反転
   する第２の７リツプ・７０ツブとで構成され、上記第２
   のＮ進カウンタの出力を上記記憶回路の読み出しアドレ
   スとして出力する読み出しポインタと、上記読み出し信
   号に同期して、上記記憶回路の読み出しアドレスのデー
   タを出力データとして読み出す読み出し回路と、上記第
   １ＯＮ進カウンタの出力と上記第２のＮ進カウンタの出
   力との一致／不一致を検出する第１の一致検出回路と、
   上記第１のフリップ・フロッグの出力と上記第２のフリ
   ップ・フロップの出力との一致／不一致を検出する第２
   の一致検出回路を有し、上記第１．第２の一致検出回路
   が共に一致を検出したときにエンプティ信号を出力し、
   上記第１゜第２の一致検出回路がそれぞれ一致、不一致
   を検出したときにフル信号を出力するフル／エンプティ
   検出回路とを具備したことを特徴とするＦＩＦＯ回路。
2. （２）　ワード数Ｎが２のＭ乗であり、書き込みポイン
   タが第１のＭ＋１ビット・カウンタで構成され、上記第
   １のＭ＋１ビット・カウンタの下位Ｍビットの出力を上
   記記憶回路の書き込みアドレスとして出力し、上記読み
   出しポインタが第２のＭ＋１ビット・カウンタで構成さ
   れ、上記第２のＭ＋１ビット・カウンタの下位Ｍビット
   の出力を上記記憶回路の読み出しアドレスとして出力し
   、上記フル／エンプティ検出回路が上記第１のＭ＋１ビ
   ット・カウンタの下位Ｍビットの出力と上記第２のＭ＋
   １ビット・カウンタの下位Ｍビットの出力との一致／不
   一致を検出する第３の一致検出回路と、上記第１のＭ＋
   １ビット・カウンタの最上位ビット出力と上記第２のＭ
   ＋１ビット・カウンタの最上位ビット出力との一致／不
   一致を検出する第４の一致検出回路をＭし、上記第１．
   第２の一致検出回路が共に一致を検出したときにエンプ
   ティ信号を出力し、上記第１．第２の一致検出回路がそ
   れぞれ一致、不一致を検出したときにフル信号を出力す
   ることを特徴とする特許請求の範囲第１項記載のＦＩＦ
   Ｏ回路。