リングカウンター

リングカウンターは、シフト レジスタに接続されたフリップフロップで構成されたカウンターの一種で、最後のフリップフロップの出力が最初のフリップフロップの入力に供給され、「円形」または「リング」構造を形成します。

リングカウンターには次の 2 つの種類があります。

  • ストレートリング カウンター (ワンホットカウンターとも呼ばれる) は、最後のシフト レジスタの出力を最初のシフト レジスタの入力に接続し、リング内で 1 つの 1 (または 0) ビットを循環させます。
  • ツイストリング カウンタ(スイッチ テール リング カウンタ、ウォーキング リング カウンタ、ジョンソン カウンタ、またはメビウスカウンタとも呼ばれる) は、最後のシフト レジスタの出力の補数を最初のレジスタの入力に接続し、1 とそれに続く 0 のストリームをリング内で循環させます。

4ビットリングカウンタシーケンス

ストレートリングカウンタージョンソンカウンター
州Q0質問1質問2第3問州Q0質問1質問2第3問
01000 00000
10100 11000
20010 21100
30001 31110
01000 41111
10100 50111
20010 60011
30001 70001
01000 00000

プロパティ

リングカウンタは、ハードウェア設計（ASICやFPGA設計など）において、有限ステートマシンを作成するためによく使用されます。バイナリカウンタは、リングカウンタよりもはるかに複雑な加算回路を必要とし、ビット数が増加するにつれて伝播遅延が大きくなります。一方、リングカウンタの伝播遅延は、ビット数に関わらずほぼ一定です。

直線形とねじれ形には異なる特性があり、相対的な長所と短所があります。

リングカウンタの一般的な欠点は、状態数の通常のバイナリ符号化よりもコード密度が低いことです。バイナリカウンタは2 N個の状態（Nはコード内のビット数）を表現できますが、ストレートリングカウンタはN個の状態しか表現できず、ジョンソンカウンタは2 N個の状態しか表現できません。これは、レジスタが組み合わせ論理よりも高価になるハードウェア実装において重要な考慮事項となる可能性があります。

ジョンソンカウンタは、同じ数のシフトレジスタから2倍のカウント状態を提供し、起動時に最初のカウントビットを外部から注入する必要がなく、すべてゼロの状態から自己初期化できるため、好まれることがあります。ジョンソンカウンタは、グレイコードのように、隣接する状態が1ビットのみ異なる（つまり、ハミング距離が1である）コードを生成します。これは、ビットパターンを非同期にサンプリングする場合に便利です。[1]

一部のシーケンスコントローラのように、カウンタの状態を完全にデコードした表現、またはワンホット表現で表現する必要がある場合は、ストレートリングカウンタが適しています。ワンホット特性とは、コードセットが最小ハミング距離2 [2]で区切られていることを意味し、そのため、単一ビットエラー（1ビットのオンとオフ以外のエラーパターンも同様）を検出できます。

双方向シフトレジスタ（マルチプレクサを使用して各フリップフロップの入力を左または右の隣接フリップフロップから取得する）が使用されることもあり、これにより双方向またはアップダウンリングカウンタを作成できます。[3]

論理図

ストレート リング カウンターの論理構造は次のとおりです。

4つのD型フリップフロップを使用した4ビットリングカウンタ。同期クロックとリセットラインを示しています。

リセットラインで最初のワンホットパターンを設定する代わりに、最後の出力を除くすべての出力に分散フィードバックゲートを使用することで、ストレートリングを自己初期化するようにすることがあります。これにより、最後のステージ以外のどのステージにも1がない場合でも、入力に1が表示されます。[4]

ジョンソン カウンターは、ロバート ロイス ジョンソンにちなんで名付けられた、反転を持つリングです。以下は 4 ビットのジョンソン カウンターです。

4つのD型フリップフロップを使用した4ビットジョンソンカウンタ。同期クロックとリセットラインを示しています。

最後のシフト レジスタからの Q 信号が最初の D 入力にフィードバックされる前に反転していることを示す小さなバブルに注目してください。これはジョンソン カウンターになります。

歴史

デジタル計算機が登場する以前は、デジタルカウンタは放射性崩壊によるアルファ粒子やベータ粒子への変化といったランダム事象の発生率を測定するために使用されていました。高速な「プリスケーリング」カウンタは、ランダム事象の発生率をより扱いやすく、より規則的な速度にまで低減しました。1940年以前には、5状態リングカウンタと2分周スケーラを組み合わせて、C.E.ウィン＝ウィリアムズが開発したような10進（10の累乗）スケーラが作られました。[5]

初期のリングカウンタは、ステージごとに1つの能動素子（真空管、バルブ、またはトランジスタ）のみを使用し、ローカル双安定フリップフロップではなくグローバルフィードバックに依存して、ワンホット状態以外の状態を抑制していました。これは、National Cash Registor Companyの Robert E. Mumma による1941年の特許出願に見られるとおりです。[6] Wilcox P. Overbeck は、1つの真空管に複数のアノードを使用するバージョンを発明しました。 [7] [8]彼の功績を称え、リングカウンタは「オーバーベックリング」と呼ばれることがあります[9] [10]（2006年以降は「オーバーベックカウンタ」と呼ばれることもあります。これは、Wikipedia が2006年から2018年までこの用語を使用していたためです）。

ENIACは10状態ワンホットリングカウンタに基づく10進演算を採用していました。NCRのムンマとMITのオーバーベックの研究成果は、特許庁が審査した先行技術文献の中に含まれており、ENIAC技術に関するJ・プレスパー・エッカートとジョン・モークリーの特許は無効とされました。 [ 11 ]

1950年代には、ステージごとに2つの真空管またはツイン三極管フリップフロップを備えたリングカウンタが登場しました。[12]

ロバート・ロイス・ジョンソンは、可能な限り単純なフィードバックロジックで異なる数の状態を作ることを目的として、シフトレジスタベースのさまざまなカウンターを開発し、1953年に特許を申請しました。 [13]ジョンソンカウンターはこれらの中で最も単純なものです。

アプリケーション

リングカウンタの初期の用途としては、周波数分周器（ガイガーカウンタなどの計測器用など）[5] 、暗号解読におけるパターン発生をカウントするカウンタ（ヒース・ロビンソン暗号解読機やコロッサスコンピュータなど）[14] 、およびコンピュータや計算機における10進演算用の累算器カウンタ要素（ 25進数（コロッサスなど）または10状態ワンホット（ENIACなど）表現を使用）などがあります。

ストレートリングカウンタは、周期制御サイクルの各状態において特定のアクションを実行するためによく使用される、完全にデコードされたワンホットコードを生成します。ワンホットコードは、各状態ごとに1つのゲートを使用することで、ジョンソンカウンタからもデコードできます。[15] [注 1]

ジョンソンカウンタは、ワンホットコードや周波数プリスケーラを生成するための効率的な代替手段であるだけでなく、グレイコードのように一度に1ビットしか変化しないため、グリッチなしで非同期サンプリング可能な偶数状態サイクルをエンコードする簡単な方法でもあります。[16]初期のコンピュータマウスは、上下（双方向）の2ビットジョンソンまたはグレイエンコードを使用して、2次元それぞれの動きを示していましたが、マウスではこれらのコードは通常、フリップフロップのリングではなく、電気機械式または光学式の直交エンコーダによって生成されていました。[17] 2ビットジョンソンコードと2ビットグレイコードは同一ですが、3ビット以上の場合、グレイコードとジョンソンコードは異なります。5ビットの場合、ジョンソンカウンタのコードは、 10進数のLibaw-Craigコード [de]（「非計数10進コード付きシャフトデジタイザ」に由来）と同じです。[18] [19] [20] [ 21] [ 22 ] [23] [24] [25]

ウォーキングリングカウンタ（ジョンソンカウンタとも呼ばれる）と数個の抵抗器で、グリッチのない正弦波の近似値を生成することができます。調整可能なプリスケーラと組み合わせることで、おそらく最もシンプルな数値制御発振器となります。このようなウォーキングリングカウンタを2つ使用すれば、デュアルトーン・マルチ周波数信号や初期のモデムトーン で使用されている連続位相周波数偏移変調（CPSK）を生成する最もシンプルな方法と言えるでしょう。[26]

小数点
 
0
1
2
3
4
5
6
7
8
9
1ビット
1
0
1
0
1
0
1
0
1
0
1
2ビット
21
00
01
11
10
00
01
11
10
00
01
3ビット
321
000
001
011
111
110
100
000
001
011
111
4ビットジョンソン
4321
0000
0001
0011
0111
1111
1110
1100
1000
0000
0001
リボー・クレイグ
54321
00000
00001
00011
00111
01111
11111
11110
11100
11000
10000
1-2-1
54321
10001
00001
00011
00010
00110
00100
01100
01000
11000
10000
10件中1件
10987654321
0000000001
0000000010
0000000100
0000001000
0000010000
0000100000
0001000000
0010000000
0100000000
1000000000

参照

注記

  1. ^ このように単一の状態をデコードするジョンソン カウンター回路は、オリジナルのIBM MDAおよびCGAビデオ ディスプレイ アダプターの設計のタイミング シーケンサー ロジックに見られます。1 つまたは 2 つの74x174 16 進 D タイプ フリップフロップ IC がシフト レジスタとして配線され、反転フィードバックされてジョンソン カウンターを形成し、2 入力NAND ゲート(MDA 内) またはXOR ゲート(CGA 内) を使用して、+RAS (行アドレス ストローブ [ DRAMへ]) や S/-L (シフト / NOT ロード) などの信号として使用される状態をデコードします。出典: IBM パーソナル コンピューター オプションおよびアダプター テクニカル リファレンス、モノクロ ディスプレイおよびプリンター アダプター、ロジック図、IBM パーソナル コンピューター オプションおよびアダプター テクニカル リファレンス、カラー グラフィックス モニター アダプター、ロジック図。

参考文献

  1. ^ Pedroni, Volnei A. (2013). ハードウェアにおける有限ステートマシン：理論と設計. MIT Press . p. 50. ISBN 978-0-26201966-8。
  2. ^ Mengibar, Luis; Entrena, Luis; Lorenz, Michael G.; Sánchez-Reillo, Raúl (2003). 「FPGAにおける低消費電力FSMの状態符号化」. Integrated Circuit and System Design. 電力およびタイミングモデリング、最適化、シミュレーション：第13回国際ワークショップPATMOS 2003の議事録、イタリア、トリノ、2003年9月10～12日. 第13巻. Springer Science & Business Media . 35ページ. ISBN 9783540200741。
  3. ^ Stan, Mircea R. (1997). 「カウンタサイズに依存しないクロック周期を持つ同期アップ/ダウンカウンタ」(PDF) . Proceedings 13th IEEE Symposium on Computer Arithmetic : 274– 281.
  4. ^ ホールズワース, ブライアン; ウッズ, クライヴ (2002). デジタルロジックデザイン (第4版).ニューネスブックス/エルゼビアサイエンス. pp.  191– 192. ISBN 0-7506-4588-2. 2020年4月19日閲覧。{{cite book}}: CS1 メンテナンス: ISBN エラーを無視 (リンク)（519ページ）[1]
  5. ^ ab Lewis, Wilfrid Bennett (1942). 電気的計数：アルファ粒子とベータ粒子の計数に関する特別参照. Cambridge University Press . p. 90. ISBN 9781316611760。 {{cite book}}:ISBN / 日付の非互換性（ヘルプ）
  6. ^ 「電子蓄積」、ロバート・E・ママの米国特許番号2405096、1941年出願
  7. ^ 「電子スイッチングデバイス」、ウィルコックス・P・オーバーベックの米国特許番号2427533、1943年出願
  8. ^ デイトン暗号解読者：1942年の研究報告書、「オーバーベック氏による新型高速カウンター、1942年1月8日」について言及
  9. ^ RAMAC 305 - IBM カスタマー・エンジニアリング・マニュアル(PDF) . IBM . 1959. […] オーバーベック・リングは、カム式回路遮断器が機械装置にタイミングパルスを供給するのと同様に、コンピュータ回路内にタイミングパルスを供給するために使用されます。これは、プロセスドラムから供給されるパルスを伝送するリング駆動ラインからの共通入力を持つ一連のトリガーで構成されています。 […] 初期状態では、ホームトリガー（ON）を除いてトリガーはOFFにリセットされています。負の入力パルスが発生するたびに、ONになっているトリガーがOFFになります。OFFになっているトリガーのピン10の電圧が低下すると、次のトリガーがONになります。この動作は、閉じたリングを通して継続されます。 […]
  10. ^ 電気技術 - 高校卒業後2年間のカリキュラム案。技術教育プログラムシリーズ。アメリカ合衆国職業技術教育局。1960年。52ページ。
  11. ^ ブライアン・ランドール（2014年）「デジタルコンピュータの起源：補足文献」メトロポリス、ニコラス（編）『20世紀のコンピュータ史』エルゼビア、  651～ 652頁。ISBN 9781483296685。
  12. ^ ウィリアム・アルフレッド・ヒギンボサム、「高速インパルス回路」、米国特許第2536808号、1949年出願
  13. ^ ロバート・ロイス・ジョンソン、「電子カウンタ」、米国特許第3030581号、1953年出願
  14. ^ コープランド、B・ジャック（2010年）『コロッサス：ブレッチリー・パークの暗号解読コンピューターの秘密』オックスフォード大学出版局、  123～ 128頁。ISBN 978-0-19957814-6。
  15. ^ Langholz, Gideon; Kandel, Abraham; Mott, Joe L. (1998). デジタルロジック設計の基礎. World Scientific. pp.  525– 526. ISBN 978-9-81023110-1。
  16. ^ van Holten, Cornelius (1982年8月). オランダ、デルフト工科大学にて執筆。「対称出力を持つデジタル分周器 - 著者は、制御されたフィードバックを備えたジョンソンカウンタを用いて、クロックパルスの対称的な偶数および奇数分割を実現しています」(PDF)。Wireless World . 第88巻、第1559号。英国サリー州サットン：IPC Business Press Ltd. pp.  43– 46. ISSN 0043-6062. 2021年2月21日時点のオリジナルより アーカイブ(PDF) 。 2021年2月20日閲覧。[2] [3] （4ページ）
  17. ^ Lyon, Richard F. (1981年8月)、「光学式マウスとスマートデジタルセンサー向けのアーキテクチャ手法」(PDF) (レポート)、Palo Alto Research Center、Palo Alto、カリフォルニア州、米国: Xerox Corporation 、VLSI 81-1、 2020年5月23日のオリジナルからのアーカイブ(PDF) 、 2020年5月23日取得、XとYに必要なカウンターは、4つの状態をどちらの方向 (上または下) でもカウントし、一度に1ビットだけ (つまり、00、01、11、10) 変化させます。これは、グレイコードカウンターまたはジョンソンカウンター (メビウスカウンター) の単純な例です。（41ページ）
  18. ^ Libaw, William H.; Craig, Leonard J. (1953年10月) [1953年9月]. 「光電式10進コードシャフトデジタイザー」. Transactions of the IRE Professional Group on Electronic Computers . EC-2 (3): 1– 4. doi :10.1109/IREPGELC.1953.5407731. eISSN  2168-1759. ISSN  2168-1740 . 2020年5月26日閲覧。（4ページ）
  19. ^ Powell, E. Alexander (1968年6月). 「アナログからデジタルへの変換に特に有用なコード」. 流体制御回路に有用なコードに関する短いメモ(PDF) . クランフィールド、英国：航空大学、生産工学科. p. 10. S2CID  215864694. CoAメモ156. 2020年12月15日時点のオリジナルからアーカイブ(PDF) . 2020年12月15日閲覧。(18 ページ) (注: この論文では、グリクソン コードを改良グレイ コードと名付けており、リチャード W. ハミングの名前のスペルが間違っています。)
  20. ^ ドクター、フォルカート;シュタインハウアー、ユルゲン (1973-06-18)。デジタルエレクトロニクス。 Philips Technical Library (PTL) / Macmillan Education (英語第 1 版の再版)。オランダ、アイントホーフェン: The Macmillan Press Ltd. / NV Philips の Gloeilampenfabrieken。 p. 43.土井：10.1007/978-1-349-01417-0。ISBN 978-1-349-01419-4. SBN 333-13360-9. 2020年5月11日閲覧。（270ページ）
  21. ^ ドクター、フォルカート;スタインハウアー、ユルゲン (1975) [1969]。Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik。フィリップス・ファッハビュッヒャー（ドイツ語）。 Vol. I (改良および拡張された第 5 版)。ハンブルク、ドイツ: Deutsche Philips GmbH。 52、58、98ページ。ISBN 3-87145-272-6。（xii+327+3ページ）
  22. ^ ドクター、フォルカート;スタインハウアー、ユルゲン (1975) [1970]。Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Anwendung der digitalen Grundschaltungen und Gerätetechnik。フィリップス・ファッハビュッヒャー（ドイツ語）。 Vol. II（第4版）。ハンブルク、ドイツ: Deutsche Philips GmbH。 p. 169.ISBN​ 3-87145-273-4。（xi+393+3ページ）
  23. ^ シュタインブーフ、カール W.編（1962年）。ドイツのカールスルーエで書かれました。Taschenbuch der Nachrichtenverarbeitung (ドイツ語) (第 1 版)。ベルリン / ゲッティンゲン / ニューヨーク: Springer-Verlag OHG。 pp   . 71–72、74。LCCN 62-14511 。
  24. ^ カール・W・シュタインブーフ;ワーグナー、ジークフリート W. 編（1967）[1962]。Taschenbuch der Nachrichtenverarbeitung (ドイツ語) (第 2 版)。ベルリン、ドイツ: Springer-Verlag OHG。LCCN  67-21079。タイトルNo.1036。
  25. ^ カール・W・シュタインブーフ;ウェーバー、ヴォルフガング。ハイネマン、トラウテ編。 （1974年）[1967年]。Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen (ドイツ語)。 Vol. 2 (第 3 版)。ドイツ、ベルリン: Springer Verlag。ISBN 3-540-06241-6。LCCN  73-80607。 {{cite book}}:|work=無視されました (ヘルプ)
  26. ^ ドン・ランカスター著『TVタイプライター・クックブック』( TVタイプライター社)、1976年、180-181頁。
「https://en.wikipedia.org/w/index.php?title=リングカウンター&oldid=1314325467#メビウスカウンター」より取得