Jump to content

Ring counter: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
→‎References: improved ref
CE, added and improved refs
Line 4: Line 4:
There are two types of ring counters:
There are two types of ring counters:
*{{anchor|Straight ring counter|Overbeck counter}} 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.
*{{anchor|Straight ring counter|Overbeck counter}} 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.
*{{anchor|Twisted ring counter|Switch-tail ring counter|Walking ring counter|Johnson counter|Möbius counter|Libaw–Craig code|Johnson code}} A '''twisted ring counter''', also called '''switch-tail ring counter''', '''walking ring counter''', '''Johnson counter''', or '''[[Möbius band|Möbius]] counter''', connects the complement of the output of the last shift register to the input of the first register and circulates a stream of ones followed by zeros around the ring. It uses the so called ''Libaw–Craig code''<ref name="Dokter_1973"/><ref name="Dokter_1975"/><ref name="Steinbuch_1962"/><ref name="Steinbuch_1967"/><ref name="Steinbuch-Weber_1974"/> aka ''Johnson code''.
*{{anchor|Twisted ring counter|Switch-tail ring counter|Walking ring counter|Johnson counter|Möbius counter|Libaw–Craig code|Johnson code}} A '''twisted ring counter''', also called '''switch-tail ring counter''', '''walking ring counter''', '''Johnson counter''', or '''[[Möbius band|Möbius]] counter''', connects the complement of the output of the last shift register to the input of the first register and circulates a stream of ones followed by zeros around the ring. It uses the so called ''Libaw–Craig code''<ref name="Dokter_1973"/><ref name="Dokter_1975_1"/><ref name="Dokter_1975_2"/><ref name="Steinbuch_1962"/><ref name="Steinbuch_1967"/><ref name="Steinbuch-Weber_1974"/> aka ''Johnson code''.


== Four-bit ring-counter sequences ==
== Four-bit ring-counter sequences ==
Line 68: Line 68:
A general disadvantage of ring counters is that they are lower density codes than normal [[binary encoding]]s of state numbers. A binary counter can represent 2^N states, where N is the number of bits in the code, whereas a straight ring counter can represent only N states and a Johnson counter can represent only 2N states. This may be an important consideration in hardware implementations where registers are more expensive than combinational logic.
A general disadvantage of ring counters is that they are lower density codes than normal [[binary encoding]]s of state numbers. A binary counter can represent 2^N states, where N is the number of bits in the code, whereas a straight ring counter can represent only N states and a Johnson counter can represent only 2N states. This may be an important consideration in hardware implementations where registers are more expensive than combinational logic.


Johnson counters are sometimes favored, because they offer twice as many count states from the same number of shift registers, and because they are able to self-initialize from the all-zeros state, without requiring the first count bit to be injected externally at start-up. The Johnson counter generates a code in which adjacent states differ by only one bit (that is, have a [[Hamming distance]] of 1), as in a [[Gray code]], which can be useful if the bit pattern is going to be asynchronously sampled.<ref>{{cite book |last1=Pedroni |first1=Volnei A. |title=Finite State Machines in Hardware: Theory and Design |date=2013 |publisher=[[MIT Press]] |isbn=9780262019668 |page=50 |url=https://books.google.co.uk/books?id=SSkTDgAAQBAJ&pg=PA50#v=onepage&q&f=false}}</ref>
Johnson counters are sometimes favored, because they offer twice as many count states from the same number of shift registers, and because they are able to self-initialize from the all-zeros state, without requiring the first count bit to be injected externally at start-up. The Johnson counter generates a code in which adjacent states differ by only one bit (that is, have a [[Hamming distance]] of 1), as in a [[Gray code]], which can be useful if the bit pattern is going to be asynchronously sampled.<ref name="Pedroni_2013"/>


When a fully decoded or [[one-hot]] representation of the counter state is needed, as in some sequence controllers, the straight ring counter is preferred. The one-hot property means that the set of codes are separated by a [[minimum Hamming distance]] of 2,<ref>{{cite book |title=Integrated Circuit and System Design. Power and Timing Modeling, Optimization and Simulation: 13th International Workshop, PATMOS 2003, Torino, Italy, September 10–12, 2003, Proceedings, Volume 13 |date=2003 |publisher=Springer Science & Business Media |page=35 | url = https://books.google.com/books?id=JEEmfObxnrAC&pg=PA35#v=onepage&q&f=false | chapter = State Encoding for Low-Power FSMs in FPGA | author = Mengibar, Luis, Luis Entrena, Michael G. Lorenz, and Raúl Sánchez-Reillo}}</ref> so any single-bit error is detectable (as is any error pattern other than turning on one bit and turning off one bit).
When a fully decoded or [[one-hot]] representation of the counter state is needed, as in some sequence controllers, the straight ring counter is preferred. The one-hot property means that the set of codes are separated by a [[minimum Hamming distance]] of 2,<ref name="Mengibar_2003"/> so any single-bit error is detectable (as is any error pattern other than turning on one bit and turning off one bit).


Sometimes bidirectional shift registers are used (using multiplexors to take the input for each flip-flop from its left or right neighbor), so that bidirectional or up–down ring counters can be made.<ref>{{cite journal |last1=Stan |first1=Mircea R |title=Synchronous up/down counter with clock period independent of counter size |journal=Proceedings 13th IEEE Symposium on Computer Arithmetic |date=1997 |pages=274–281 |url=http://www.acsel-lab.com/arithmetic/arith13/papers/ARITH13_Stan.pdf}}</ref>
Sometimes bidirectional shift registers are used (using multiplexors to take the input for each flip-flop from its left or right neighbor), so that bidirectional or up–down ring counters can be made.<ref name="Stan_1997"/>


==Logic diagrams==
==Logic diagrams==
Line 78: Line 78:
The straight ring counter has the logical structure shown here:
The straight ring counter has the logical structure shown here:


[[File:Overbeck Counter 4bit.svg|400px|border|4-bit ring counter using four [[Flip-flop (electronics)#D flip-flop|D-Type Flip Flops]]. Synchronous clock and reset line shown.]]
[[File:Overbeck Counter 4bit.svg|400px|border|4-bit ring counter using four [[Flip-flop (electronics)#D flip-flop|D-type flip flops]]. Synchronous clock and reset line shown.]]


Instead of the reset line setting up the initial [[one-hot]] pattern, the straight ring is sometimes made self-initializing by the use of a distributed feedback gate across all of the outputs except that last, so that a 1 in presented at the input when there is no 1 in any stage but the last.<ref>{{cite book | author =Brian Holdsworth and Clive Woods |title = Digital Logic Design |date=2002 |isbn =9780080477305 |pages=191–192 |url =https://books.google.com/books?id=o7enSwSVvgYC&pg=PA192}}</ref>
Instead of the reset line setting up the initial [[one-hot]] pattern, the straight ring is sometimes made self-initializing by the use of a distributed feedback gate across all of the outputs except that last, so that a 1 in presented at the input when there is no 1 in any stage but the last.<ref name="Holdsworth_2002"/>


A Johnson counter, named for [[Robert Royce Johnson]], is a ring with an inversion; here is a 4-bit Johnson counter:
A Johnson counter, named for [[Robert Royce Johnson]], is a ring with an inversion; here is a 4-bit Johnson counter:


[[File:Johnson Counter 4bit.svg|400px|border|4-bit Johnson counter using four [[Flip-flop (electronics)#D flip-flop|D-Type Flip Flops]]. Synchronous clock and reset line shown.]]
[[File:Johnson Counter 4bit.svg|400px|border|4-bit Johnson counter using four [[Flip-flop (electronics)#D flip-flop|D-type flip flops]]. Synchronous clock and reset line shown.]]


Note the small bubble indicating inversion of the Q signal from the last shift register before feeding back to the first D input, making this a Johnson counter.
Note the small bubble indicating inversion of the Q signal from the last shift register before feeding back to the first D input, making this a Johnson counter.
Line 90: Line 90:
==History==
==History==


Before the days of digital computing, digital counters were used to measure rates of random events such as radioactive decays to alpha and beta particle. Fast "pre-scaling" counters reduced the rate of random events to more manageable and more regular rates. Five-state ring counters were used along with divide-by-two scalers to make decade (power-of-ten) scalers before 1940, such as those developed by [[C. E. Wynn-Williams]].<ref name="lewis">{{cite book |last1=Lewis |first1=W. B. |title=Electrical Counting: With Special Reference to Counting Alpha and Beta Particles |date=1942 |publisher=Cambridge University Press |page=90 |url=https://books.google.com/books?id=5B5CDAAAQBAJ&pg=PA90}}</ref>
Before the days of digital computing, digital counters were used to measure rates of random events such as radioactive decays to alpha and beta particle. Fast "pre-scaling" counters reduced the rate of random events to more manageable and more regular rates. Five-state ring counters were used along with divide-by-two scalers to make decade (power-of-ten) scalers before 1940, such as those developed by [[C. E. Wynn-Williams]].<ref name="Lewis_1942"/>


Early ring counters used only one active element (vacuum tube, valve, or transistor) per stage, relying on global feedback rather than local bistable flip-flops, to suppress states other than the one-hot states, for example in the 1941 patent filing of [[Robert E. Mumma]] of the [[National Cash Registor Company]].<ref>[https://www.google.com/patents/US2405096 "Electronic accumulation", Robert E. Mumma's US Patent No. 2405096, filed in 1941]</ref> [[Wilcox P. Overbeck]] invented a version using multiple anodes in a single vacuum tube,<ref name=overbeck_patent>[https://www.google.com/patents/US2427533 "Electronic switching device", Wilcox P. Overbeck's US Patent No. 2427533, filed in 1943]</ref><ref>[http://daytoncodebreakers.org/depth/42_res_rpt/ Dayton Codebreakers: 1942 Research Report, mentioning "A new high speed counter by Mr. Overbeck, January 8, 1942"]</ref> In recognition of his work, ring counters are sometimes referred to as "Overbeck rings"<ref>[http://www.ed-thelen.org/RAMAC/IBM-227-3534-0-305-RAMAC-r.pdf "RAMAC 305"], IBM Customer Engineering Manual of Instruction (1959),
Early ring counters used only one active element (vacuum tube, valve, or transistor) per stage, relying on global feedback rather than local bistable flip-flops, to suppress states other than the one-hot states, for example in the 1941 patent filing of [[Robert E. Mumma]] of the [[National Cash Registor Company]].<ref name="Mumma_1941"/> [[Wilcox P. Overbeck]] invented a version using multiple anodes in a single vacuum tube,<ref name="Overbeck_1943"/><ref name="Dayton"/> In recognition of his work, ring counters are sometimes referred to as "Overbeck rings"<ref name="RAMAC_1959"/><ref name="US_1960"/> (and after 2006, sometimes as "Overbeck counters", since Wikipedia used that term from 2006 to 2018).
"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..."
</ref><ref>[https://books.google.com/books?id=0zoUAAAAIAAJ&q=%22overbeck+ring%22&dq=%22overbeck+ring%22&hl=en&sa=X&ved=0ahUKEwj3v5nYuMnbAhWC5lQKHWh_CVIQ6AEINDAC ''Technical Education Program Series''], United States. Division of Vocational and Technical Education, 1960, p. 52</ref> (and after 2006, sometimes as "Overbeck counters", since Wikipedia used that term from 2006 to 2018).


The [[ENIAC]] used decimal arithmetic based on 10-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 in invalidated the patents of [[J. Presper Eckert]] and [[John Mauchly]] for the ENIAC technology.<ref>{{cite book |editor=Nicholas Metropolis |author=B. Randall | chapter = The Origins of Digital Computers: Supplementary Bibliography |title=History of Computing in the Twentieth Century |date=2014 |publisher=Elsevier |pages=651–652 |url=https://books.google.com/books?id=AsvSBQAAQBAJ&pg=PA652}}</ref>
The [[ENIAC]] used decimal arithmetic based on 10-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 in invalidated the patents of [[J. Presper Eckert]] and [[John Mauchly]] for the ENIAC technology.<ref name="Randall_2014"/>


By the 1950s, ring counters with a two-tube or twin-triode flip-flop per stage were appearing.<ref>William A Higinbotham , [https://patents.google.com/patent/US2536808A/en "Fast impulse circuits"], US Patent No. 2536808</ref>
By the 1950s, ring counters with a two-tube or twin-triode flip-flop per stage were appearing.<ref name="Higinbotham"/>


[[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.<ref>Robert R. Johnson, [https://patents.google.com/patent/US3030581A/en "Electronic counter"], US Patent No. 3030581</ref> The Johnson counter is the simplest of these.
[[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.<ref name="Johnson_1953"/> The Johnson counter is the simplest of these.


==Applications==
==Applications==


Early applications of ring counters were as frequency prescalers (e.g. for [[Geiger counter]] and such instruments)<ref name=lewis/>, as counters to count pattern occurrences in cryptanalysis (e.g. in the [[Heath Robinson (codebreaking machine)|Heath Robinson codebreaking machine]] and the [[Colossus computer]]),<ref>{{cite book |last1=Copeland |first1=B. Jack |title=Colossus: The Secrets of Bletchley Park's Code-breaking Computers |date=2010 |publisher=[[Oxford University Press]] |isbn=978-0-19957814-6 |pages=123–128}}</ref> and as accumulator counter elements for decimal arithmetic in computers and calculators, using either [[bi-quinary coded decimal|bi-quinary]] (as in the Colossus) or ten-state one-hot (as in the [[ENIAC]]) representations.
Early applications of ring counters were as frequency prescalers (e.g. for [[Geiger counter]] and such instruments),<ref name="Lewis_1942"/> as counters to count pattern occurrences in cryptanalysis (e.g. in the [[Heath Robinson (codebreaking machine)|Heath Robinson codebreaking machine]] and the [[Colossus computer]]),<ref name="Copeland_2010"/> and as accumulator counter elements for decimal arithmetic in computers and calculators, using either [[bi-quinary coded decimal|bi-quinary]] (as in the Colossus) or ten-state one-hot (as in the [[ENIAC]]) representations.


Straight ring counters generate fully decoded one-hot codes to that are often used to 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.<ref>{{cite book | author=Gideon Langholz, Abraham Kandel, and Joe L. Mott | title=Foundations of Digital Logic Design |date=1998 | publisher=World Scientific |isbn=9789810231101 | pages=525–526 | url=https://books.google.com/books?id=4sX9fTGRo7QC&pg=PA525}}</ref><ref>Johnson counter circuits with single states decoded in this way can be found in the original IBM MDA and CGA video display adapter designs, in the timing sequencer logic: one or two 74x174 hex D-type flip-flop ICs are wired as a shift register, fed back with inversion to form a Johnson counter, and 2-input NAND gates (in the MDA) or XOR gates (in the CGA) are used to decode states used as signals such as +RAS (Row Address Strobe [to DRAM]) and S/-L (Shift / NOT Load). Source: 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.</ref>
Straight ring counters generate fully decoded one-hot codes to that are often used to 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.<ref name="Langholz_1998"/><ref group="nb" name="NB1"/>


Besides being an efficient alternative way to generate one-hot codes and frequency pre-scalers, a Johnson counter is also a simple way to encode a cycle of states that can be asynchronously sampled without glitching, since only one bit changes at a time, as in a [[Gray code]]. Early [[computer mice]] used up–down (bidirectional) 2-bit Johnson or Gray encodings to indicate motion in each of the two dimensions, though in mice those codes were not usually generated by rings of flip-flops (but instead by electro-mechanical or optical [[quadrature encoder]]s).<ref>Richard F. Lyon (1981), [http://www.bitsavers.org/pdf/xerox/parc/techReports/VLSI-81-1_The_Optical_Mouse.pdf "The Optical Mouse, and an Architectural Methodology for Smart Digital Sensors"], Xerox PARC report. "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)."</ref> Note that 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.
Besides being an efficient alternative way to generate one-hot codes and frequency pre-scalers, a Johnson counter is also a simple way to encode a cycle of states that can be asynchronously sampled without glitching, since only one bit changes at a time, as in a [[Gray code]]. Early [[computer mice]] used up–down (bidirectional) 2-bit Johnson or Gray encodings to indicate motion in each of the two dimensions, though in mice those codes were not usually generated by rings of flip-flops (but instead by electro-mechanical or optical [[quadrature encoder]]s).<ref name="Lyon_1981"/> 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.


== See also ==
== See also ==
Line 125: Line 113:
* [[Linear-feedback shift register]]
* [[Linear-feedback shift register]]
* {{ill|Libaw–Craig code|de|Libaw-Craig-Code}}<!-- link with possibilities -->
* {{ill|Libaw–Craig code|de|Libaw-Craig-Code}}<!-- link with possibilities -->

== Notes ==
{{reflist|group="nb"|refs=
<ref group="nb" name="NB1">Johnson counter circuits with single states decoded in this way can be found in the original IBM MDA and CGA video display adapter designs, in the timing sequencer logic: one or two 74x174 hex D-type flip-flop ICs are wired as a shift register, fed back with inversion to form a Johnson counter, and 2-input NAND gates (in the MDA) or XOR gates (in the CGA) are used to decode states used as signals such as +RAS (Row Address Strobe [to DRAM]) and S/-L (Shift / NOT Load). Source: 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.</ref>
}}


== References ==
== References ==
{{reflist|refs=
{{reflist|refs=
<ref name="Dokter_1973">{{cite book |title=Digital Electronics |author-first1=Folkert |author-last1=Dokter |author-first2=Jürgen |author-last2=Steinhauer |chapter= |date=1973-06-18 |series=Philips Technical Library (PTL) / Macmillan Education |publisher=[[The Macmillan Press Ltd.]] / [[N. V. Philips' Gloeilampenfabrieken]] |edition=Reprint of 1st English |location=Eindhoven, Netherlands |sbn=333-13360-9 |isbn=978-1-349-01419-4 |doi=10.1007/978-1-349-01417-0 |pages= |chapter-url= |url=https://books.google.com/books?id=hlRdDwAAQBAJ |access-date=2020-05-11 |url-status=live |archive-url= |archive-date=}} (270 pages)</ref>
<ref name="Dokter_1973">{{cite book |title=Digital Electronics |author-first1=Folkert |author-last1=Dokter |author-first2=Jürgen |author-last2=Steinhauer |date=1973-06-18 |series=Philips Technical Library (PTL) / Macmillan Education |publisher=[[The Macmillan Press Ltd.]] / [[N. V. Philips' Gloeilampenfabrieken]] |edition=Reprint of 1st English |location=Eindhoven, Netherlands |sbn=333-13360-9 |isbn=978-1-349-01419-4 |doi=10.1007/978-1-349-01417-0 |page=43 |url=https://books.google.com/books?id=hlRdDwAAQBAJ |access-date=2020-05-11 |url-status=live |archive-url= |archive-date=}} (270 pages)</ref>
<ref name="Dokter_1975">{{cite book |author-first1=Folkert |author-last1=Dokter |author-first2=Jürgen |author-last2=Steinhauer |title=Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik |chapter= |language=de |series=Philips Fachbücher |publisher=[[Deutsche Philips GmbH]] |publication-place=Hamburg, Germany |volume=I |date=1975 |orig-year=1970 |edition=improved and extended 5th |isbn=3-87145-272-6 |pages=}} (xii+327+3 pages)</ref>
<ref name="Dokter_1975_1">{{cite book |author-first1=Folkert |author-last1=Dokter |author-first2=Jürgen |author-last2=Steinhauer |title=Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik |language=de |series=Philips Fachbücher |publisher=[[Deutsche Philips GmbH]] |publication-place=Hamburg, Germany |volume=I |date=1975 |orig-year=1969 |edition=improved and extended 5th |isbn=3-87145-272-6 |pages=52, 58, 98}} (xii+327+3 pages)</ref>
<ref name="Dokter_1975_2">{{cite book |author-first1=Folkert |author-last1=Dokter |author-first2=Jürgen |author-last2=Steinhauer |title=Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Anwendung der digitalen Grundschaltungen und Gerätetechnik |language=de |series=Philips Fachbücher |publisher=[[Deutsche Philips GmbH]] |publication-place=Hamburg, Germany |volume=II |date=1975 |orig-year=1970 |edition=4th |isbn=3-87145-273-4 |page=169}} (xi+393+3 pages)</ref>
<ref name="Steinbuch_1962">{{cite book |title=Taschenbuch der Nachrichtenverarbeitung |language=de |editor-first=Karl W. |editor-last=Steinbuch |editor-link=Karl W. Steinbuch |date=1962 |edition=1 |publisher=[[Springer-Verlag OHG]] |location=Karlsruhe, Germany |publication-place=Berlin / Göttingen / New York |lccn=62-14511 |pages=}}</ref>
<ref name="Steinbuch_1962">{{cite book |title=Taschenbuch der Nachrichtenverarbeitung |language=de |editor-first=Karl W. |editor-last=Steinbuch |editor-link=Karl W. Steinbuch |date=1962 |edition=1 |publisher=[[Springer-Verlag OHG]] |location=Karlsruhe, Germany |publication-place=Berlin / Göttingen / New York |lccn=62-14511 |pages=71–72, 74}}</ref>
<ref name="Steinbuch_1967">{{cite book |title=Taschenbuch der Nachrichtenverarbeitung |language=de |editor-first1=Karl W. |editor-last1=Steinbuch |editor-link1=Karl W. Steinbuch |editor-first2=Siegfried W. |editor-last2=Wagner |date=1967 |orig-year=1962 |edition=2 |publisher=[[Springer-Verlag OHG]] |location=Berlin, Germany |id=Title No. 1036 |lccn=67-21079 |pages=}}</ref>
<ref name="Steinbuch_1967">{{cite book |title=Taschenbuch der Nachrichtenverarbeitung |language=de |editor-first1=Karl W. |editor-last1=Steinbuch |editor-link1=Karl W. Steinbuch |editor-first2=Siegfried W. |editor-last2=Wagner |date=1967 |orig-year=1962 |edition=2 |publisher=[[Springer-Verlag OHG]] |location=Berlin, Germany |id=Title No. 1036 |lccn=67-21079 |pages=}}</ref>
<ref name="Steinbuch-Weber_1974">{{cite book |title=Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen |language=de |editor-first1=Karl W. |editor-last1=Steinbuch |editor-link1=Karl W. Steinbuch |editor-first2=Wolfgang |editor-last2=Weber <!-- |editor-link2=:de:Wolfgang Weber (Ingenieur)? --> |editor-first3=Traute |editor-last3=Heinemann |date=1974 |orig-year=1967 |edition=3 |volume=2 |work=Taschenbuch der Nachrichtenverarbeitung |publisher=[[Springer Verlag]] |location=Berlin, Germany |isbn=3-540-06241-6 |id={{ISBN|978-3-540-06241-7}} |lccn=73-80607 |pages=}}</ref>
<ref name="Steinbuch-Weber_1974">{{cite book |title=Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen |language=de |editor-first1=Karl W. |editor-last1=Steinbuch |editor-link1=Karl W. Steinbuch |editor-first2=Wolfgang |editor-last2=Weber <!-- |editor-link2=:de:Wolfgang Weber (Ingenieur)? --> |editor-first3=Traute |editor-last3=Heinemann |date=1974 |orig-year=1967 |edition=3 |volume=2 |work=Taschenbuch der Nachrichtenverarbeitung |publisher=[[Springer Verlag]] |location=Berlin, Germany |isbn=3-540-06241-6 |id={{ISBN|978-3-540-06241-7}} |lccn=73-80607 |pages=}}</ref>
<ref name="Pedroni_2013">{{cite book |author-last1=Pedroni |author-first1=Volnei A. |title=Finite State Machines in Hardware: Theory and Design |date=2013 |publisher=[[MIT Press]] |isbn=978-0-26201966-8 |page=50 |url=https://books.google.com/books?id=SSkTDgAAQBAJ&pg=PA50}}</ref>
<ref name="Mengibar_2003">{{cite book |title=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 |chapter=State Encoding for Low-Power FSMs in FPGA |author-first1=Luis |author-last1=Mengibar |author-first2=Luis |author-last2=Entrena |author-first3=Michael G. |author-last3=Lorenz |author-first4=Raúl |author-last4=Sánchez-Reillo |volume=13 |date=2003 |publisher=[[Springer Science & Business Media]] |page=35 |url=https://books.google.com/books?id=JEEmfObxnrAC&pg=PA35}}</ref>
<ref name="Stan_1997">{{cite journal |author-last=Stan |author-first=Mircea R. |title=Synchronous up/down counter with clock period independent of counter size |journal=Proceedings 13th IEEE Symposium on Computer Arithmetic |date=1997 |pages=274–281 |url=http://www.acsel-lab.com/arithmetic/arith13/papers/ARITH13_Stan.pdf}}</ref>
<ref name="Holdsworth_2002">{{cite book |title=Digital Logic Design |author-first1=Brian |author-last1=Holdsworth |author-first2=Clive |author-last2=Woods |edition=4 |date=2002 |publisher=[[Newnes Books]] / [[Elsevier Science]] |isbn=0-7506-4588-2<!-- this ISBN is faulty, but actually printed in the book --> |ignore-isbn-error=true |id={{ISBN|978-0-08047730-5}} |pages=191–192 |url=https://books.google.com/books?id=o7enSwSVvgYC&pg=PA192 |access-date=2020-04-19 |url-status=live |archive-url= |archive-date=2020-04-19}} (519 pages) [https://web.archive.org/web/20200419213939/http://s2.bitdownload.ir/Ebook/Electronics/Holdsworth%20-%20Digital%20Logic%20Design%204e%20HQ%20(Newnes,%202002).pdf]</ref>
<ref name="Lewis_1942">{{cite book |author-last=Lewis |author-first=W. B. |title=Electrical Counting: With Special Reference to Counting Alpha and Beta Particles |date=1942 |publisher=[[Cambridge University Press]] |page=90 |url=https://books.google.com/books?id=5B5CDAAAQBAJ&pg=PA90}}</ref>
<ref name="Mumma_1941">[https://www.google.com/patents/US2405096 "Electronic accumulation", Robert E. Mumma's US Patent No. 2405096, filed in 1941]</ref>
<ref name="Overbeck_1943">[https://www.google.com/patents/US2427533 "Electronic switching device", Wilcox P. Overbeck's US Patent No. 2427533, filed in 1943]</ref>
<ref name="Dayton">[http://daytoncodebreakers.org/depth/42_res_rpt/ Dayton Codebreakers: 1942 Research Report, mentioning "A new high speed counter by Mr. Overbeck, January 8, 1942"]</ref>
<ref name="RAMAC_1959">{{cite book |title=RAMAC 305 - IBM Customer Engineering Manual of Instruction |publisher=[[IBM]] |date=1959 |url=http://www.ed-thelen.org/RAMAC/IBM-227-3534-0-305-RAMAC-r.pdf |quote=[…] 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 […]}}</ref>
<ref name="US_1960">{{cite book |title=Electrical Technology - A Suggested 2-Year Post High School Curriculum |series=Technical Education Program Series |publisher=United States, Division of Vocational and Technical Education |date=1960 |issue=1–5 |page=52 |url=https://books.google.com/books?id=0zoUAAAAIAAJ&q=%22overbeck+ring%22&dq=%22overbeck+ring%22&hl=en&sa=X&ved=0ahUKEwj3v5nYuMnbAhWC5lQKHWh_CVIQ6AEINDAC}}</ref>
<ref name="Randall_2014">{{cite book |editor-first=Nicholas |editor-last=Metropolis |author-first=B. |author-last=Randall |chapter=The Origins of Digital Computers: Supplementary Bibliography |title=History of Computing in the Twentieth Century |date=2014 |publisher=Elsevier |pages=651–652 |url=https://books.google.com/books?id=AsvSBQAAQBAJ&pg=PA652}}</ref>
<ref name="Higinbotham">William A. Higinbotham, [https://patents.google.com/patent/US2536808A/en "Fast impulse circuits"], US Patent No. 2536808</ref>
<ref name="Johnson_1953">Robert R. Johnson, [https://patents.google.com/patent/US3030581A/en "Electronic counter"], US Patent No. 3030581</ref>
<ref name="Copeland_2010">{{cite book |author-last1=Copeland |author-first1=B. Jack |title=Colossus: The Secrets of Bletchley Park's Code-breaking Computers |date=2010 |publisher=[[Oxford University Press]] |isbn=978-0-19957814-6 |pages=123–128}}</ref>
<ref name="Langholz_1998">{{cite book |author-first1=Gideon |author-last1=Langholz |author-first2=Abraham |author-last2=Kandel |author-first3=Joe L. |author-last3=Mott |title=Foundations of Digital Logic Design |date=1998 |publisher=World Scientific |isbn=978-9-81023110-1 |pages=525–526 |url=https://books.google.com/books?id=4sX9fTGRo7QC&pg=PA525}}</ref>
<ref name="Lyon_1981">{{cite |title=The Optical Mouse, and an Architectural Methodology for Smart Digital Sensors |author-first=Richard F. |author-last=Lyon |author-link=Richard F. Lyon |date=August 1981 |id=VLSI 81-1 |type=Report |publisher=[[Xerox Corporation]] |location=Palo Alto Research Center, Palo Alto, California, USA |url=http://www.bitsavers.org/pdf/xerox/parc/techReports/VLSI-81-1_The_Optical_Mouse.pdf |access-date=2020-05-23 |url-status=live |archive-url=https://web.archive.org/web/20200523093939/http://www.bitsavers.org/pdf/xerox/parc/techReports/VLSI-81-1_The_Optical_Mouse.pdf |archive-date=2020-05-23 |quote=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)</ref>
}}
}}


Revision as of 10:42, 23 May 2020

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 twisted ring counter, also called switch-tail ring counter, walking ring counter, Johnson counter, or Möbius counter, connects the complement of the output of the last shift register to the input of the first register and circulates a stream of ones followed by zeros around the ring. It uses the so called Libaw–Craig code[1][2][3][4][5][6] aka Johnson code.

Four-bit ring-counter sequences

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

Ring counters are often used in hardware design (e.g. ASIC and FPGA design) to create finite-state machines. A binary counter would require an adder circuit which is substantially more complex than a ring counter and has higher propagation delay as the number of bits increases, whereas the propagation delay of a ring counter will be nearly constant regardless of the number of bits in the code.

The straight and twisted forms have different properties, and relative advantages and disadvantages.

A general disadvantage of ring counters is that they are lower density codes than normal binary encodings of state numbers. A binary counter can represent 2^N states, where N is the number of bits in the code, whereas a straight ring counter can represent only N states and a Johnson counter can represent only 2N states. This may be an important consideration in hardware implementations where registers are more expensive than combinational logic.

Johnson counters are sometimes favored, because they offer twice as many count states from the same number of shift registers, and because they are able to self-initialize from the all-zeros state, without requiring the first count bit to be injected externally at start-up. The Johnson counter generates a code in which adjacent states differ by only one bit (that is, have a Hamming distance of 1), as in a Gray code, which can be useful if the bit pattern is going to be asynchronously sampled.[7]

When a fully decoded or one-hot representation of the counter state is needed, as in some sequence controllers, the straight ring counter is preferred. The one-hot property means that the set of codes are separated by a minimum Hamming distance of 2,[8] so any single-bit error is detectable (as is any error pattern other than turning on one bit and turning off one bit).

Sometimes bidirectional shift registers are used (using multiplexors to take the input for each flip-flop from its left or right neighbor), so that bidirectional or up–down ring counters can be made.[9]

Logic diagrams

The straight ring counter has the logical structure shown here:

4-bit ring counter using four D-type flip flops. Synchronous clock and reset line shown.

Instead of the reset line setting up the initial one-hot pattern, the straight ring is sometimes made self-initializing by the use of a distributed feedback gate across all of the outputs except that last, so that a 1 in presented at the input when there is no 1 in any stage but the last.[10]

A Johnson counter, named for Robert Royce Johnson, is a ring with an inversion; here is a 4-bit Johnson counter:

4-bit Johnson counter using four D-type flip flops. Synchronous clock and reset line shown.

Note the small bubble indicating inversion of the Q signal from the last shift register before feeding back to the first D input, making this a Johnson counter.

History

Before the days of digital computing, digital counters were used to measure rates of random events such as radioactive decays to alpha and beta particle. Fast "pre-scaling" counters reduced the rate of random events to more manageable and more regular rates. Five-state ring counters were used along with divide-by-two scalers to make decade (power-of-ten) scalers before 1940, such as those developed by C. E. Wynn-Williams.[11]

Early ring counters used only one active element (vacuum tube, valve, or transistor) per stage, relying on global feedback rather than local bistable flip-flops, to suppress states other than the one-hot states, for example in the 1941 patent filing of Robert E. Mumma of the National Cash Registor Company.[12] Wilcox P. Overbeck invented a version using multiple anodes in a single vacuum tube,[13][14] In recognition of his work, ring counters are sometimes referred to as "Overbeck rings"[15][16] (and after 2006, sometimes as "Overbeck counters", since Wikipedia used that term from 2006 to 2018).

The ENIAC used decimal arithmetic based on 10-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 in invalidated the patents of J. Presper Eckert and John Mauchly for the ENIAC technology.[17]

By the 1950s, ring counters with a two-tube or twin-triode flip-flop per stage were appearing.[18]

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.[19] The Johnson counter is the simplest of these.

Applications

Early applications of ring counters were as frequency prescalers (e.g. for Geiger counter and such instruments),[11] as counters to count pattern occurrences in cryptanalysis (e.g. in the Heath Robinson codebreaking machine and the Colossus computer),[20] and as accumulator counter elements 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.

Straight ring counters generate fully decoded one-hot codes to that are often used to 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.[21][nb 1]

Besides being an efficient alternative way to generate one-hot codes and frequency pre-scalers, a Johnson counter is also a simple way to encode a cycle of states that can be asynchronously sampled without glitching, since only one bit changes at a time, as in a Gray code. Early computer mice used up–down (bidirectional) 2-bit Johnson or Gray encodings to indicate motion in each of the two dimensions, though in mice those codes were not usually generated by rings of flip-flops (but instead by electro-mechanical or optical quadrature encoders).[22] 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.

See also

Notes

  1. ^ Johnson counter circuits with single states decoded in this way can be found in the original IBM MDA and CGA video display adapter designs, in the timing sequencer logic: one or two 74x174 hex D-type flip-flop ICs are wired as a shift register, fed back with inversion to form a Johnson counter, and 2-input NAND gates (in the MDA) or XOR gates (in the CGA) are used to decode states used as signals such as +RAS (Row Address Strobe [to DRAM]) and S/-L (Shift / NOT Load). Source: 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.

References

  1. ^ Dokter, Folkert; Steinhauer, Jürgen (1973-06-18). Digital Electronics. Philips Technical Library (PTL) / Macmillan Education (Reprint of 1st English ed.). Eindhoven, Netherlands: The Macmillan Press Ltd. / N. V. Philips' Gloeilampenfabrieken. p. 43. doi:10.1007/978-1-349-01417-0. ISBN 978-1-349-01419-4. SBN 333-13360-9. Retrieved 2020-05-11.{{cite book}}: CS1 maint: url-status (link) (270 pages)
  2. ^ Dokter, Folkert; Steinhauer, Jürgen (1975) [1969]. Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik. Philips Fachbücher (in German). Vol. I (improved and extended 5th ed.). Hamburg, Germany: Deutsche Philips GmbH. pp. 52, 58, 98. ISBN 3-87145-272-6. (xii+327+3 pages)
  3. ^ Dokter, Folkert; Steinhauer, Jürgen (1975) [1970]. Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Anwendung der digitalen Grundschaltungen und Gerätetechnik. Philips Fachbücher (in German). Vol. II (4th ed.). Hamburg, Germany: Deutsche Philips GmbH. p. 169. ISBN 3-87145-273-4. (xi+393+3 pages)
  4. ^ Steinbuch, Karl W., ed. (1962). Written at Karlsruhe, Germany. Taschenbuch der Nachrichtenverarbeitung (in German) (1 ed.). Berlin / Göttingen / New York: Springer-Verlag OHG. pp. 71–72, 74. LCCN 62-14511.
  5. ^ Steinbuch, Karl W.; Wagner, Siegfried W., eds. (1967) [1962]. Taschenbuch der Nachrichtenverarbeitung (in German) (2 ed.). Berlin, Germany: Springer-Verlag OHG. LCCN 67-21079. Title No. 1036.
  6. ^ Steinbuch, Karl W.; Weber, Wolfgang; Heinemann, Traute, eds. (1974) [1967]. Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen (in German). Vol. 2 (3 ed.). Berlin, Germany: Springer Verlag. ISBN 3-540-06241-6. LCCN 73-80607. ISBN 978-3-540-06241-7. {{cite book}}: |work= ignored (help)
  7. ^ Pedroni, Volnei A. (2013). Finite State Machines in Hardware: Theory and Design. MIT Press. p. 50. ISBN 978-0-26201966-8.
  8. ^ Mengibar, Luis; Entrena, Luis; Lorenz, Michael G.; Sánchez-Reillo, Raúl (2003). "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. Vol. 13. Springer Science & Business Media. p. 35.
  9. ^ 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.
  10. ^ Holdsworth, Brian; Woods, Clive (2002). Digital Logic Design (4 ed.). Newnes Books / Elsevier Science. pp. 191–192. ISBN 0-7506-4588-2. ISBN 978-0-08047730-5. Retrieved 2020-04-19. {{cite book}}: |archive-date= requires |archive-url= (help); Check |isbn= value: checksum (help); Unknown parameter |ignore-isbn-error= ignored (|isbn= suggested) (help)CS1 maint: url-status (link) (519 pages) [1]
  11. ^ a b Lewis, W. B. (1942). Electrical Counting: With Special Reference to Counting Alpha and Beta Particles. Cambridge University Press. p. 90.
  12. ^ "Electronic accumulation", Robert E. Mumma's US Patent No. 2405096, filed in 1941
  13. ^ "Electronic switching device", Wilcox P. Overbeck's US Patent No. 2427533, filed in 1943
  14. ^ Dayton Codebreakers: 1942 Research Report, mentioning "A new high speed counter by Mr. Overbeck, January 8, 1942"
  15. ^ RAMAC 305 - IBM Customer Engineering Manual of Instruction (PDF). 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 […]
  16. ^ 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.
  17. ^ Randall, B. (2014). "The Origins of Digital Computers: Supplementary Bibliography". In Metropolis, Nicholas (ed.). History of Computing in the Twentieth Century. Elsevier. pp. 651–652.
  18. ^ William A. Higinbotham, "Fast impulse circuits", US Patent No. 2536808
  19. ^ Robert R. Johnson, "Electronic counter", US Patent No. 3030581
  20. ^ 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.
  21. ^ Langholz, Gideon; Kandel, Abraham; Mott, Joe L. (1998). Foundations of Digital Logic Design. World Scientific. pp. 525–526. ISBN 978-9-81023110-1.
  22. ^ Lyon, Richard F. (August 1981), The Optical Mouse, and an Architectural Methodology for Smart Digital Sensors (PDF) (Report), Palo Alto Research Center, Palo Alto, California, USA: Xerox Corporation, VLSI 81-1, archived (PDF) from the original on 2020-05-23, retrieved 2020-05-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)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ring_counter&oldid=958358820"