リングカウンタ
From Wikipedia, the free encyclopedia
.svg)
| ストレート・リングカウンタ | ジョンソンカウンタ | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 状態 | Q0 | Q1 | Q2 | Q3 | 状態 | Q0 | Q1 | Q2 | Q3 | |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
| 2 | 0 | 0 | 1 | 0 | 2 | 1 | 1 | 0 | 0 | |
| 3 | 0 | 0 | 0 | 1 | 3 | 1 | 1 | 1 | 0 | |
| 0 | 1 | 0 | 0 | 0 | 4 | 1 | 1 | 1 | 1 | |
| 1 | 0 | 1 | 0 | 0 | 5 | 0 | 1 | 1 | 1 | |
| 2 | 0 | 0 | 1 | 0 | 6 | 0 | 0 | 1 | 1 | |
| 3 | 0 | 0 | 0 | 1 | 7 | 0 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
特性
リングカウンタは、有限オートマトンを作るためにハードウェアの設計（例えば、ASICとFPGA）でよく使用される。 2進数カウンタは、加算器回路を要求する。加算器はリングカウンタよりもかなり複雑であり、ビット数が増える度に伝搬遅延が大きくなる。一方、リングカウンタの伝搬遅延は、符号のビット数に関係なくほぼ一定になる。
ストレート・リングカウンタとジョンソンカウンタは、異なる特性を持つ。相対的な長所と短所がある。
リングカウンタの一般的な短所は、状態番号を2進符号化したときよりも符号の密度が低いことである。 2進数カウンタは、の状態を表現できる。ここでNは符号のビット数である。一方、ストレート・リングカウンタは、N個の状態しか表現できない。ジョンソンカウンタは、2N個の状態しか表現できない。 このことは、レジスタが組み合わせロジックよりも高価なハードウェアの実装において重要な検討事項になるかもしれない[訳注 1]。
ジョンソンカウンタは、好まれることがある。シフトレジスタのビット数の2倍のカウント状態を表現できるからである。ジョンソンカウンタは、全0状態から自己初期化することが可能なので、開始時に外部から注入される第一ビットを要求することはない。 ジョンソンカウンタは、隣接する状態が1ビットだけ異なる符号を生成する（ハミング距離が1である）。グレイコードと同様であり、ビットパターンが非同期的にサンプリングされる場合に役立つ[1]。
カウンタ状態の完全に復号された表現、あるいはOne-hotによる表現が必要とされるとき、いくつかのシーケンスコントローラーと同様にストレート・リングカウンタが好まれる。 One-hotは、符号の集合の最小ハミング距離が2という特性があるので[2]、あらゆる1ビットエラーを検出できる（1ビットをオンして1ビットをオフする以外のあらゆるエラーパターンも同様に検出できる）。
双方向あるいはアップダウン・リングカウンタを作るために双方向シフトレジスタが使われることがある（左右の隣接したフリップフロップから各フリップフロップのための入力を得るためにマルチプレクサを使用する）[3]。
論理回路図
ストレート・リングカウンタは、ここに示す論理構造になっている。
初期状態のOne-hotパターンを設定するリセット信号線の代わりにストレート・リングカウンタは、最後の出力を除く全出力を通じて分布帰還型ゲート（distributed feedback gate）を使うことによって自己初期化を行うこともある。その結果、最後のステージを除いた全てのステージに1が存在しないときに入力に1が提供されることになる[4]。
ジョンソンカウンタ（ロバート・ロイス・ジョンソンにちなんで命名）は、出力反転を伴ったリングである。4ビットのジョンソンカウンタをここに示す。
シフトレジスタの最後のQ信号に描かれている小さな丸は、信号の反転を意味することに注意するべきである。そして、反転した信号は最初のD入力に帰還されている。それによってこの回路はジョンソンカウンタとなっている。
歴史
デジタル計算の時代以前にデジタルカウンタがランダムな事象の割合を測定するために使われていた。例えば、放射性物質がアルファ粒子やベータ粒子へ崩壊するようなことである。 高速な「分周」カウンタは、ランダムな事象の割合をより扱いやすく、より一般的なものとした。 1940年以前、10のべき乗のスケーラーを作るために2で除算するスケーラーと一緒に5ステート・リングカウンタが使われた。例えば、C.E.ウィン・ウィリアムズによって開発されたものである[5]。
初期のリングカウンタは、ステージ毎に一つだけの能動素子（真空管あるいはトランジスタ）を使っていた。One-hot状態以外の状態を抑制するために局所的な双安定性フリップフロップではなく全体的な帰還に依存して動作していた。例えば、NCRのロバート・E・ムンマによって出願された1941年の特許にそのことが記されている[6]。 ウィルコックス・P・オーバーベックは、一本の真空管の中に複数のアノードを利用したリングカウンタを発明した[7][8]。 彼の功績が認められたので、リングカウンタは「オーバーベックリング」（Overbeck rings）と呼ばれることもある[9][10]（ウィキペディアが2006年から2018年までこの用語を使ったので、2006年以降「オーバーベックカウンタ」と呼ばれることもある）。
ENIACは、10ステートワンホットリングカウンタで実装された10進数を使っていた。NCRのムンマとMITのオーバーベックの業績は、特許庁によって審査された先行技術の一つである。特許庁は、ENIAC技術に関するジョン・プレスパー・エッカートとジョン・モークリーの特許を無効にした[11]。
1950年代までに2つの真空管あるいは2つの三極真空管から構成される一つのフリップフロップをステージ毎に使ったリングカウンタが登場した[12]。
ロバート・ロイス・ジョンソンは、最も簡潔な帰還論理回路で異なった数の状態を作ることを狙ってシフトレジスタで実装した多くの異なるカウンタを開発した。そして、1953年に特許を申請した[13]。 ジョンソンカウンタは、それらの中で最も簡潔なものである。