リングカウンタ
.svg)
リングカウンタは、シフトレジスタを形成するように接続されたフリップフロップから構成されるカウンタ回路の一種である。最後のフリップフロップの出力を最初のフリップフロップの入力へ与えるので、「循環」あるいは「リング」構造を形成する。
リングカウンタには2種類ある。
- ストレート・リングカウンタ（ワンホットカウンタとしても知られている）は、シフトレジスタの最後の出力をシフトレジスタの最初の入力へ接続し、リング内で単一の1の値のビット（One-hot）あるいは、単一の0の値のビット（One-cold）を循環させる。
- ジョンソンカウンタ（ツイステッド・リングカウンタ、スイッチテイル・リングカウンタ、ウォーキング・リングカウンタ、あるいはメビウスカウンタとも呼ばれる）は、シフトレジスタの最後の出力を反転させて、シフトレジスタの最初の入力へ接続し、リング内で0000の後に1111が続くような流れを循環させる（後述）。
4ビット・リングカウンタのシーケンス[編集]
| ストレート・リングカウンタ | ジョンソンカウンタ | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 状態 | 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]。 ジョンソンカウンタは、それらの中で最も簡潔なものである。
応用[編集]
初期のリングカウンタの応用は、周波数分周器（例えば、ガイガーカウンタとそのような測定器）[5]、暗号解読においてパターンの出現を数えるためのカウンタ（例えば、ヒース・ロビンソン暗号解読機とコロッサス計算機）[14]、そして、コンピューターと計算機内部の10進数用アキュムレータであった。そのアキュムレータは、二五進法（コロッサス計算機）、あるいは10ステートワンホット（ENIAC）のどちらかを使った。
ストレート・リングカウンタは、完全に復号されたワンホット符号を生成する。周期的な制御サイクルの各状態において特定の動作を可能とするためによく使われた。 ワンホット符号は、ジョンソンカウンタでも復号することができる。各状態毎に一つのゲートを使用する[15][注釈 1]。
リングカウンタは、ワンホット符号を生成する効率的な代替手法や周波数分周器になるだけではない。ジョンソンカウンタは、状態の偶数番号のサイクルを符号化する単純な方法でもある[訳注 2]。グレイコードと同様に一度に1ビットだけ変化するので、誤動作せずに非同期的にサンプルされることが可能である[16] 。 初期のコンピューターマウスは、二次元のそれぞれの動きを示すためにアップダウン（双方向）2ビット・ジョンソン符号化あるいは2ビット・グレイ符号化を使った。しかし、それらの符号がフリップフロップのリングによって生成されることはなかった（その代わり、電子機械式あるいは光学直交エンコーダーによって生成された）[17] 。 2ビット・グレイコードと2ビット・ジョンソン符号は、同一であるが、3ビット以上のグレイコードとジョンソン符号は異なる。 5ビットにおいて、ジョンソン符号は、10進数を表現するためのリバウ・クレイグ符号と同一である[18][19][20][21][22][23][24][25]。
ウォーキング・リングカウンタは、ジョンソンカウンタとも呼ばれ、抵抗器とローパスフィルタを付けると、誤りのない近似のサイン波を生成することができる[26][訳注 3]。 調整可能なプリスケーラー（分周器）と組み合わせると、最も単純な数値制御発振器になるかもしれない。 2つのウォーキング・リングカウンタは、DTMFと初期のモデムで使われた連続位相周波数偏移変調 (CPFSK)を生成する最も単純な方法かもしれない[27]。
|
|
|
|
|
|
|
|
脚注[編集]
注釈[編集]
- ^ この方法で復号された単一の状態を扱うジョンソンカウンタ回路は、オリジナルのIBM MDAビデオカードとCGAグラフィックスカードの設計の中に見つけることができる。タイミングシーケンサーロジックにおいて、1つまたは２つの74x1746回路D型フリップフロップICがシフトレジスタとして結線されており、ジョンソンカウンタを形成するために反転した帰還を行っている。そして、2入力NANDゲート（MDAで使用）あるいはXORゲート（CGAで使用）は、+RAS（DRAMへのRow Address Strobe）とS/-L（Shift / NOT Load）のような信号として使われる状態を復号するために使われる。情報源：IBM Personal Computer Options & Adapters Technical Reference, Monochrome Display and Printer Adapter, logic diagrams; IBM Personal Computer Options & Adapters Technical Reference, Color Graphics Monitor Adapter, logic diagrams.
訳注[編集]
- ^ 原文は、"This may be an important consideration in hardware implementations where registers are more expensive than combinational logic."であった。"registers"が2進数のレジスタ？"combinational logic"がリングカウンタ？レジスタはリングカウンタよりも高価ということであろうか。
- ^ 原文は、"a Johnson counter is also a simple way to encode a cycle of an even number of states that can be asynchronously sampled without glitching, since only one bit changes at a time, as in a Gray code."であった。"a cycle of an even number of states"が何を意味しているのか不明。
- ^ 原文は"A walking ring counter, also called a Johnson counter, and a few resistors can produce a glitch-free approximation of a sine wave."であった。"walking ring counter"と"Johnson counter"を区別する基準は不明である。抵抗器だけでサイン波を出すのは無理なので、ローパスフィルタが必要なことを追記した。
出典[編集]
- ^ Finite State Machines in Hardware: Theory and Design. MIT Press. (2013). p. 50. ISBN 978-0-26201966-8
- ^ “State Encoding for Low-Power FSMs in FPGA”. Integrated Circuit and System Design. Power and Timing Modeling, Optimization and Simulation: Proceedings of the 13th International Workshop, PATMOS 2003, Torino, Italy, 10–12 September 2003. 13. Springer Science & Business Media. (2003). p. 35. ISBN 9783540200741
- ^ “Synchronous up/down counter with clock period independent of counter size”. Proceedings 13th IEEE Symposium on Computer Arithmetic: 274–281. (1997).
- ^ Digital Logic Design (4 ed.). Newnes Books / Elsevier Science. (2002). pp. 191–192. ISBN 0-7506-4582-2 2020年4月19日閲覧。 (519 pages) [1]
- ^ a b Electrical Counting: With Special Reference to Counting Alpha and Beta Particles. Cambridge University Press. (1942). p. 90. ISBN 9781316611760
- ^ "Electronic accumulation", Robert E. Mumma's US Patent No. 2405096, filed in 1941
- ^ "Electronic switching device", Wilcox P. Overbeck's US Patent No. 2427533, filed in 1943
- ^ Dayton Codebreakers: 1942 Research Report, mentioning "A new high speed counter by Mr. Overbeck, January 8, 1942"
- ^ RAMAC 305 - IBM Customer Engineering Manual of Instruction. IBM. (1959). "[…] The Overbeck ring is used to supply timed pulses within computer circuits much as cam operated circuit breakers supply timed pulses on mechanical machines. It consists of a set of triggers with a common input from the ring drive line which carries pulses supplied by the process drum. […] Initially the triggers are reset OFF with the exception of the home trigger, which is ON. Each negative input pulse will turn OFF the trigger that is ON. The fall of the voltage at pin 10 of the trigger being turned OFF will grid flip the next trigger ON. This continues through a closed ring […]"
- ^ Electrical Technology - A Suggested 2-Year Post High School Curriculum. Technical Education Program Series. United States, Division of Vocational and Technical Education. (1960). p. 52
- ^ Metropolis, Nicholas, ed (2014). “The Origins of Digital Computers: Supplementary Bibliography”. History of Computing in the Twentieth Century. Elsevier. pp. 651–652. ISBN 9781483296685
- ^ William Alfred Higinbotham, "Fast impulse circuits", US Patent No. 2536808, filed in 1949
- ^ Robert Royce Johnson, "Electronic counter", US Patent No. 3030581, filed in 1953
- ^ Colossus: The Secrets of Bletchley Park's Code-breaking Computers. Oxford University Press. (2010). pp. 123–128. ISBN 978-0-19957814-6
- ^ Foundations of Digital Logic Design. World Scientific. (1998). pp. 525–526. ISBN 978-9-81023110-1
- ^ “Digital dividers with symmetrical outputs - The author uses Johnson counters with controlled feedback to give symmetrical even and odd-numbered divisions of a clock pulse.”. Wireless World (Sutton, Surrey, UK: IPC Business Press Ltd.) 88 (1559): 43–46. (August 1982). ISSN 0043-6062. オリジナルの2021-02-21時点におけるアーカイブ。 2021年2月20日閲覧。. [2] [3] (4 pages)
- ^ The Optical Mouse, and an Architectural Methodology for Smart Digital Sensors (Report), Palo Alto Research Center, Palo Alto, California, USA: Xerox Corporation, (August 1981), VLSI 81-1, オリジナルの2020-05-23時点におけるアーカイブ。 2020年5月23日閲覧, "The counters needed for X and Y simply count through four states, in either direction (up or down), changing only one bit at a time (i.e., 00, 01, 11, 10). This is a simple case of either a Gray-code counter or a Johnson counter (Moebius counter)." (41 pages)
- ^ “A Photoelectric Decimal-Coded Shaft Digitizer”. Transactions of the I.R.E. Professional Group on Electronic Computers EC-2 (3): 1–4. (October 1953). doi:10.1109/IREPGELC.1953.5407731. ISSN 2168-1740 2020年5月26日閲覧。. (4 pages)
- ^ “Codes particularly useful for analogue to digital conversions”. A short note on useful codes for Fluidic Control Circuits. Cranfield, UK: The College of Aeronautics, Department of Production Engineering. (June 1968). p. 10. CoA Memo 156. オリジナルの2020-12-15時点におけるアーカイブ。 2020年12月15日閲覧。 (18 pages) (NB. The paper names the Glixon code modified Gray code and misspells Richard W. Hamming's name.)
- ^ Digital Electronics. Philips Technical Library (PTL) / Macmillan Education (Reprint of 1st English ed.). Eindhoven, Netherlands: The Macmillan Press Ltd. / N. V. Philips' Gloeilampenfabrieken. (1973-06-18). p. 43. doi:10.1007/978-1-349-01417-0. ISBN 978-1-349-01419-4 2020年5月11日閲覧。 (270 pages)
- ^ (ドイツ語) Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik. Philips Fachbücher. I (improved and extended 5th ed.). Hamburg, Germany: Deutsche Philips GmbH. (1975). pp. 52, 58, 98. ISBN 3-87145-272-6 (xii+327+3 pages)
- ^ (ドイツ語) Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Anwendung der digitalen Grundschaltungen und Gerätetechnik. Philips Fachbücher. II (4th ed.). Hamburg, Germany: Deutsche Philips GmbH. (1975). p. 169. ISBN 3-87145-273-4 (xi+393+3 pages)
- ^ Steinbuch, Karl W., ed (1962). written at Karlsruhe, Germany (ドイツ語). Taschenbuch der Nachrichtenverarbeitung (1 ed.). Berlin / Göttingen / New York: Springer-Verlag OHG. pp. 71–72, 74. LCCN 62--14511
- ^ (ドイツ語) Taschenbuch der Nachrichtenverarbeitung (2 ed.). Berlin, Germany: Springer-Verlag OHG. (1967). LCCN 67--21079. Title No. 1036
- ^ (ドイツ語) Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen. 2 (3 ed.). Berlin, Germany: Springer Verlag. (1974). ISBN 3-540-06241-6. LCCN 73--80607
- ^ “walking ring sine wave generator”. https://stackexchange.com. StackExchange (2015年1月3日). 2023年2月13日閲覧。
- ^ Don Lancaster. "TV Typewriter Cookbook". (TV Typewriter). 1976. pp. 180-181.