A ring counter is a type of counter composed of flip-flops connected into a shift register, with the output of the last flip-flop fed to the input of the first, making a "circular" or "ring" structure.
There are two types of ring counters:
- A straight ring counter, also known as a one-hot counter, connects the output of the last shift register to the first shift register input and circulates a single one (or zero) bit around the ring.
- A Johnson counter, also called twisted ring counter, switch-tail ring[1], walking ring counter[1], or Möbius counter[citation needed], connects the last shift register's complemented output to the input of the first register and circulates a stream of ones followed by zeros around the ring.
Four-bit ring-counter sequences
edit| Straight ring counter | Johnson counter | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| State | Q0 | Q1 | Q2 | Q3 | State | 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 | |
Properties
editRing counters are often used as state sequencers in larger finite-state machines. Unlike binary counters, whose propagation delays grow as the number of bits increase, the propagation delays within a ring counter are constant regardless of the number of bits, thus allowing them to operate at higher clock frequencies.
Ring counters have a smaller modulus than binary counters. A binary counter has 2N states, where N is the number of flip-flops. In contrast, a straight ring counter has N states and a Johnson counter has 2N states. This may be an important consideration in hardware implementations where registers are more expensive than combinational logic or vice versa.
A Johnson counter is able to self-initialize from the all-zeros state. It generates a Gray code in which adjacent states differ by only one bit (i.e., have a Hamming distance of 1), which can be useful if the bit pattern will be asynchronously sampled.[2]
A straight ring counter is typically used when a one-hot representation of the counter state is needed, as in some sequence controllers. A bidirectional counter may be implemented by adding a multiplexer at the input of each flip-flop, to select the output of its left or right neighbor,[3] at the expense of increased propagation delay.
Logic diagrams
editA straight ring counter is a circular shift register, as shown in the example below. The initial one-hot pattern is established by setting one flip-flop and clearing all others upon reset. Alternatively, the counter can be made self-initializing by ANDing the complements all of flip-flop outputs except the last, so that a 1 is applied to the first flip-flop input when there is no 1 in any stage but the last.[4]
A Johnson counter, named for Robert Royce Johnson, is a circular shift register in which the final output is inverted, as shown in this 4-bit Johnson counter:
History
editBefore the days of digital computing, ring counters were used in Geiger counters as frequency prescalers to reduce the event rate (of radioactive decay to alpha and beta particles) to more manageable frequencies.[5] Five-state ring counters were used with divide-by-two scalers to make decade (power-of-ten) scalers before 1940, such as those developed by C. E. Wynn-Williams.[5] Other early applications of ring counters include pattern occurrence counters in cryptanalysis (e.g. in the Heath Robinson codebreaking machine and Colossus computer),[6] and as count accumulators for decimal arithmetic in computers and calculators, using either bi-quinary (as in the Colossus) or ten-state one-hot (as in the ENIAC) representations.
Early ring counters used only one active element (vacuum tube, valve, or transistor) per stage, relying on global feedback to suppress states other than one-hot states. For example, in the 1941 patent filing of Robert E. Mumma of the National Cash Register Company.[7] Wilcox P. Overbeck invented a version using multiple anodes in a single vacuum tube.[8][9] In recognition of his work, ring counters are sometimes called Overbeck rings.
The ENIAC used decimal arithmetic based on ten-state, one-hot ring counters. The works of Mumma at NCR and Overbeck at MIT were among the prior art works examined by the patent office that invalidated the patents of J. Presper Eckert and John Mauchly for the ENIAC technology.[10]
By the 1950s, ring counters with a two-tube or twin-triode flip-flop per stage were appearing.[11]
Robert Royce Johnson developed a number of different shift-register-based counters with the aim of making different numbers of states with the simplest possible feedback logic, and filed for a patent in 1953.[12] The Johnson counter is the simplest of these.
Applications
editStraight ring counters are often used to generate one-hot signals that enable a specific action in each state of a cyclic control cycle. One-hot codes can also be decoded from a Johnson counter, using one gate for each state.[13]
Johnson counters are commonly used to generate a cycle with an even number of states, which are directly encoded as a Gray code and thus can be asynchronously sampled without causing glitches.[14] A 2-bit Johnson code and a 2-bit Gray code are identical, while for 3 or more bits Gray and Johnson codes are different. In the 5-bit case, the Johnson counter's code is the same as the Libaw–Craig code for decimal digits, from "a non-counting decimal-coded shaft digitizer".[15][16]
A Johnson counter and a few resistors can produce a glitch-free approximation of a sine wave having an output frequency determined solely by the counter's clock frequency.[17]
|
|
|
|
|
|
|
|
See also
editReferences
edit- 1 2 Lancaster, Don (1974). TTL Cookbook. Prentice Hall Computer Publishing. ISBN 0672210355.
- ↑ Pedroni, Volnei A. (2013). Finite State Machines in Hardware: Theory and Design. MIT Press. p. 50. ISBN 978-0-26201966-8.
- ↑ Stan, Mircea R. (1997). "Synchronous up/down counter with clock period independent of counter size" (PDF). Proceedings 13th IEEE Symposium on Computer Arithmetic: 274–281.
- ↑ Holdsworth, Brian; Woods, Clive (2002). Digital Logic Design (4 ed.). Newnes Books / Elsevier Science. pp. 191–192. ISBN 0-7506-4588-2. Retrieved 2020-04-19.
{{cite book}}: CS1 maint: ignored ISBN errors (link) (519 pages) - 1 2 Lewis, Wilfrid Bennett (1942). Electrical Counting: With Special Reference to Counting Alpha and Beta Particles. Cambridge University Press. p. 90. ISBN 9781316611760.
{{cite book}}: ISBN / Date incompatibility (help) - ↑ Copeland, B. Jack (2010). Colossus: The Secrets of Bletchley Park's Code-breaking Computers. Oxford University Press. pp. 123–128. ISBN 978-0-19957814-6.
- ↑ "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"
- ↑ Randall, Brian (2014). "The Origins of Digital Computers: Supplementary Bibliography". In Metropolis, Nicholas (ed.). 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
- ↑ Langholz, Gideon; Kandel, Abraham; Mott, Joe L. (1998). Foundations of Digital Logic Design. World Scientific. pp. 525–526. ISBN 978-9-81023110-1.
- ↑ van Holten, Cornelius (August 1982). Written at Delft Technical University, Delft, Netherlands. "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" (PDF). Wireless World. Vol. 88, no. 1559. Sutton, Surrey, UK: IPC Business Press Ltd. pp. 43–46. ISSN 0043-6062. Archived (PDF) from the original on 2021-02-21. Retrieved 2021-02-20. (4 pages)
- ↑ Libaw, William H.; Craig, Leonard J. (October 1953) [September 1953]. "A Photoelectric Decimal-Coded Shaft Digitizer". Transactions of the I.R.E. Professional Group on Electronic Computers. EC-2 (3): 1–4. doi:10.1109/IREPGELC.1953.5407731. eISSN 2168-1759. ISSN 2168-1740. Retrieved 2020-05-26. (4 pages)
- ↑ Powell, E. Alexander (June 1968). "Codes particularly useful for analogue to digital conversions". A short note on useful codes for Fluidic Control Circuits (PDF). Cranfield, UK: The College of Aeronautics, Department of Production Engineering. p. 10. S2CID 215864694. CoA Memo 156. Archived (PDF) from the original on 2020-12-15. Retrieved 2020-12-15. (18 pages) (NB. The paper names the Glixon code modified Gray code and misspells Richard W. Hamming's name.)
- ↑ Don Lancaster. "TV Typewriter Cookbook". (TV Typewriter). 1976. p. 180-181.