リングカウンタ

リングカウンタは、シフトレジスタを形成するように接続されたフリップフロップから構成されるカウンタ回路の一種である。最後のフリップフロップの出力を最初のフリップフロップの入力へ与えるので、「循環」あるいは「リング」構造を形成する。 リングカウンタには2種類ある。 ストレート・リングカウンタ（ワンホットカウンタとしても知られている）は、シフトレジスタの最後の出力をシフトレジスタの最初の入力へ接続し、リング内で単一の1の値のビット（One-hot）あるいは、単一の0の値のビット（One-cold）を循環させる。 ジョンソンカウンタ（ツイステッド・リングカウンタ、スイッチテイル・リングカウンタ、ウォーキング・リングカウンタ、あるいはメビウスカウンタとも呼ばれる）は、シフトレジスタの最後の出力を反転させて、シフトレジスタの最初の入力へ接続し、リング内で0000の後に1111が続くような流れを循環させる（後述）。 リングカウンタは、有限オートマトンを作るためにハードウェアの設計（例えば、ASICとFPGA）でよく使用される。 2進数カウンタは、加算器回路を要求する。加算器はリングカウンタよりもかなり複雑であり、ビット数が増える度に伝搬遅延が大きくなる。一方、リングカウンタの伝搬遅延は、符号のビット数に関係なくほぼ一定になる。 ストレート・リングカウンタとジョンソンカウンタは、異なる特性を持つ。相対的な長所と短所がある。 リングカウンタの一般的な短所は、状態番号を2進符号化したときよりも符号の密度が低いことである。 2進数カウンタは、 2 N {\displaystyle 2^{N}} の状態を表現できる。ここでNは符号のビット数である。一方、ストレート・リングカウンタは、N個の状態しか表現できない。ジョンソンカウンタは、2N個の状態しか表現できない。 このことは、レジスタが組み合わせロジックよりも高価なハードウェアの実装において重要な検討事項になるかもしれない。 ジョンソンカウンタは、好まれることがある。シフトレジスタのビット数の2倍のカウント状態を表現できるからである。ジョンソンカウンタは、全0状態から自己初期化することが可能なので、開始時に外部から注入される第一ビットを要求することはない。 ジョンソンカウンタは、隣接する状態が1ビットだけ異なる符号を生成する（ハミング距離が1である）。グレイコードと同様であり、ビットパターンが非同期的にサンプリングされる場合に役立つ。 カウンタ状態の完全に復号された表現、あるいはOne-hotによる表現が必要とされるとき、いくつかのシーケンスコントローラーと同様にストレート・リングカウンタが好まれる。 One-hotは、符号の集合の最小ハミング距離が2という特性があるので、あらゆる1ビットエラーを検出できる（1ビットをオンして1ビットをオフする以外のあらゆるエラーパターンも同様に検出できる）。 双方向あるいはアップダウン・リングカウンタを作るために双方向シフトレジスタが使われることがある（左右の隣接したフリップフロップから各フリップフロップのための入力を得るためにマルチプレクサを使用する）。 ストレート・リングカウンタは、ここに示す論理構造になっている。 初期状態のOne-hotパターンを設定するリセット信号線の代わりにストレート・リングカウンタは、最後の出力を除く全出力を通じて分布帰還型ゲート（distributed feedback gate）を使うことによって自己初期化を行うこともある。その結果、最後のステージを除いた全てのステージに1が存在しないときに入力に1が提供されることになる。 ジョンソンカウンタ（ロバート・ロイス・ジョンソン（英語版）にちなんで命名）は、出力反転を伴ったリングである。4ビットのジョンソンカウンタをここに示す。 シフトレジスタの最後のQ信号に描かれている小さな丸は、信号の反転を意味することに注意するべきである。そして、反転した信号は最初のD入力に帰還されている。それによってこの回路はジョンソンカウンタとなっている。 デジタル計算の時代以前にデジタルカウンタがランダムな事象の割合を測定するために使われていた。例えば、放射性物質がアルファ粒子やベータ粒子へ崩壊するようなことである。 高速な「分周」カウンタは、ランダムな事象の割合をより扱いやすく、より一般的なものとした。 1940年以前、10のべき乗のスケーラーを作るために2で除算するスケーラーと一緒に5ステート・リングカウンタが使われた。例えば、C.E.ウィン・ウィリアムズ（英語版）によって開発されたものである。 初期のリングカウンタは、ステージ毎に一つだけの能動素子（真空管あるいはトランジスタ）を使っていた。One-hot状態以外の状態を抑制するために局所的な双安定性フリップフロップではなく全体的な帰還に依存して動作していた。例えば、NCRのロバート・E・ムンマ（英語版）によって出願された1941年の特許にそのことが記されている。 ウィルコックス・P・オーバーベック（英語版）は、一本の真空管の中に複数のアノードを利用したリングカウンタを発明した。 彼の功績が認められたので、リングカウンタは「オーバーベックリング」（Overbeck rings）と呼ばれることもある（ウィキペディアが2006年から2018年までこの用語を使ったので、2006年以降「オーバーベックカウンタ」と呼ばれることもある）。 ENIACは、10ステートワンホットリングカウンタで実装された10進数を使っていた。 NCR[要曖昧さ回避]のムンマとMITのオーバーベックの業績は、特許庁によって審査された先行技術の一つである。特許庁は、ENIAC技術に関するジョン・プレスパー・エッカートとジョン・モークリーの特許を無効にした。 1950年代までに2つの真空管あるいは2つの三極真空管から構成される一つのフリップフロップをステージ毎に使ったリングカウンタが登場した。 ロバート・ロイス・ジョンソンは、最も簡潔な帰還論理回路で異なった数の状態を作ることを狙ってシフトレジスタで実装した多くの異なるカウンタを開発した。そして、1953年に特許を申請した。 ジョンソンカウンタは、それらの中で最も簡潔なものである。 初期のリングカウンタの応用は、周波数分周器（例えば、ガイガーカウンタとそのような測定器）、暗号解読においてパターンの出現を数えるためのカウンタ（例えば、ヒース・ロビンソン暗号解読機（英語版）とコロッサス計算機）、そして、コンピューターと計算機内部の10進数用アキュムレータであった。そのアキュムレータは、二五進法（コロッサス計算機）、あるいは10ステートワンホット（ENIAC）のどちらかを使った。 ストレート・リングカウンタは、完全に復号されたワンホット符号を生成する。周期的な制御サイクルの各状態において特定の動作を可能とするためによく使われた。 ワンホット符号は、ジョンソンカウンタでも復号することができる。各状態毎に一つのゲートを使用する。 リングカウンタは、ワンホット符号を生成する効率的な代替手法や周波数分周器になるだけではない。ジョンソンカウンタは、状態の偶数番号のサイクルを符号化する単純な方法でもある。グレイコードと同様に一度に1ビットだけ変化するので、誤動作せずに非同期的にサンプルされることが可能である 。 初期のコンピューターマウスは、二次元のそれぞれの動きを示すためにアップダウン（双方向）2ビット・ジョンソン符号化あるいは2ビット・グレイ符号化を使った。しかし、それらの符号がフリップフロップのリングによって生成されることはなかった（その代わり、電子機械式あるいは光学直交エンコーダー（英語版）によって生成された） 。 2ビット・グレイコードと2ビット・ジョンソン符号は、同一であるが、3ビット以上のグレイコードとジョンソン符号は異なる。 5ビットにおいて、ジョンソン符号は、10進数を表現するためのリバウ・クレイグ符号（ドイツ語版）と同一である。 ウォーキング・リングカウンタは、ジョンソンカウンタとも呼ばれ、抵抗器とローパスフィルタを付けると、誤りのない近似のサイン波を生成することができる。 調整可能なプリスケーラー（英語版）（分周器）と組み合わせると、最も単純な数値制御発振器になるかもしれない。 2つのウォーキング・リングカウンタは、DTMFと初期のモデムで使われた連続位相周波数偏移変調（英語版） (CPFSK)を生成する最も単純な方法かもしれない。