A ring counter is a type of counter composed of flip-flops connected into a

shift register A shift register is a type of digital circuit using a cascade of flip-flops where the output of one flip-flop is connected to the input of the next. They share a single clock signal, which causes the data stored in the system to shift from one loc ...

, 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 In digital circuits and machine learning, a one-hot is a group of bits among which the legal combinations of values are only those with a single high (1) bit and all the others low (0). A similar implementation in which all bits are '1' except ...

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.

Four-bit ring-counter sequences

Properties

Ring counters are often used in hardware design (e.g.

ASIC An application-specific integrated circuit (ASIC ) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use, such as a chip designed to run in a digital voice recorder or a high-efficien ...

and

FPGA A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware de ...

design) to create

finite-state machines A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

. 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 In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...

of 1), as in a

Gray code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representati ...

, which can be useful if the bit pattern is going to be asynchronously sampled. When a fully decoded or

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, 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.

Logic diagrams

The straight ring counter has the logical structure shown here: Overbeck Counter 4bit

Instead of the reset line setting up the initial

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 is presented at the input when there is no 1 in any stage but the last. A Johnson counter, named for Robert Royce Johnson, is a ring with an inversion; here is a 4-bit Johnson counter: Johnson Counter 4bit

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 Charles Eryl Wynn-Williams (5 March 1903 – 30 August 1979), was a Welsh physicist, noted for his research on electronic instrumentation for use in nuclear physics. His work on the scale-of-two counter contributed to the development of the moder ...

. 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 NCR Corporation, previously known as National Cash Register, is an American software, consulting and technology company providing several professional services and electronic products. It manufactures self-service kiosks, point-of-sale termin ...

Wilcox P. Overbeck Wilcox Pratt Overbeck (1912–1980) was an electrical and nuclear engineer who built instrumentation for the first nuclear reactor, the Chicago Pile-1, and went on to work at other United States Department of Energy national laboratories. He pre ...

invented a version using multiple anodes in a single vacuum tube, In recognition of his work, ring counters are sometimes referred to as "Overbeck rings" (and after 2006, sometimes as "Overbeck counters", since Wikipedia used that term from 2006 to 2018). The

ENIAC ENIAC (; Electronic Numerical Integrator and Computer) was the first programmable, electronic, general-purpose digital computer, completed in 1945. There were other computers that had these features, but the ENIAC had all of them in one packa ...

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 John Adam Presper Eckert Jr. (April 9, 1919 – June 3, 1995) was an American electrical engineer and computer pioneer. With John Mauchly, he designed the first general-purpose electronic digital computer (ENIAC), presented the first course in c ...

and

John Mauchly John William Mauchly (August 30, 1907 – January 8, 1980) was an American physicist who, along with J. Presper Eckert, designed ENIAC, the first general-purpose electronic digital computer, as well as EDVAC, BINAC and UNIVAC I, the first co ...

for the ENIAC technology. By the 1950s, ring counters with a two-tube or twin-triode flip-flop per stage were appearing. 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. The Johnson counter is the simplest of these.

Applications

Early applications of ring counters were as frequency prescalers (e.g. for

Geiger counter A Geiger counter (also known as a Geiger–Müller counter) is an electronic instrument used for detecting and measuring ionizing radiation. It is widely used in applications such as radiation dosimetry, radiological protection, experimental ph ...

and such instruments), as counters to count pattern occurrences in cryptanalysis (e.g. in the Heath Robinson codebreaking machine and the

Colossus computer Colossus was a set of computers developed by British codebreakers in the years 1943–1945 to help in the cryptanalysis of the Lorenz cipher. Colossus used thermionic valves (vacuum tubes) to perform Boolean and counting operations. Colossus ...

), 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

) 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. 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 an even number of states that can be asynchronously sampled without glitching, since only one bit changes at a time, as in a

. Early

computer mice A computer mouse (plural mice, sometimes mouses) is a hand-held pointing device that detects two-dimensional space, two-dimensional motion relative to a surface. This motion is typically translated into the motion of a pointer (user interface ...

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 An incremental encoder is a linear or rotary electromechanical device that has two output signals, ''A'' and ''B'', which issue pulses when the device is moved. Together, the ''A'' and ''B'' signals indicate both the occurrence of and direction o ...

s). 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 code is the same as the for decimal digits. A walking ring counter, also called a Johnson counter, and a few resistors can produce a glitch-free approximation of a sine wave. When combined with an adjustable

prescaler A prescaler is an electronic counting circuit used to reduce a high frequency electrical signal to a lower frequency by integer division. The prescaler takes the basic timer clock frequency (which may be the CPU clock frequency or may be some high ...

, this is perhaps the simplest

numerically-controlled oscillator A numerically-controlled oscillator (NCO) is a digital signal generator which creates a synchronous (i.e. clocked), discrete-time, discrete-valued representation of a waveform, usually sinusoidal. NCOs are often used in conjunction with a digital- ...

. Two such walking ring counters are perhaps the simplest way to generate the

continuous-phase frequency-shift keying Continuous phase modulation (CPM) is a method for modulation of data commonly used in wireless modems. In contrast to other coherent digital phase modulation techniques where the carrier phase abruptly resets to zero at the start of every symbol (e ...

used in

dual-tone multi-frequency signaling Dual-tone multi-frequency signaling (DTMF) is a telecommunication signaling system using the voice-frequency band over telephone lines between telephone equipment and other communications devices and switching centers. DTMF was first developed ...

and early

modem A modulator-demodulator or modem is a computer hardware device that converts data from a digital format into a format suitable for an analog transmission medium such as telephone or radio. A modem transmits data by Modulation#Digital modulati ...

tones. Don Lancaster
"TV Typewriter Cookbook"
(

TV Typewriter The TV Typewriter is a video terminal that could display two pages of 16 lines of 32 upper case characters on a standard television set. The design, by Don Lancaster, appeared on the cover of ''Radio-Electronics'' magazine in September 1973. The ...

). 1976. p. 180-181.

Notes

References

{{reflist, refs= {{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. Macmillan Publishers (occasionally known as the Macmillan Group; formally Macmillan Publishers Ltd and Macmillan Publishing Group, LLC) is a British publishing company traditionally considered to be one of the 'Big Five' English language publi ...

/ 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 (270 pages) {{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 Koninklijke Philips N.V. (), commonly shortened to Philips, is a Dutch Multinational corporation, multinational Conglomerate (company), conglomerate corporation that was founded in Eindhoven in 1891. Since 1997, it has been mostly headquartered ...

, location=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) {{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=

, location=Hamburg, Germany , volume=II , date=1975 , orig-year=1970 , edition=4th , isbn=3-87145-273-4 , page=169 (xi+393+3 pages) {{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 Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 in ...

, location=Karlsruhe, Germany , publication-place=Berlin / Göttingen / New York , lccn=62-14511 , pages=71–72, 74 {{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=

, location=Berlin, Germany , id=Title No. 1036 , lccn=67-21079 {{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-first3=Traute , editor-last3=Heinemann , date=1974 , orig-year=1967 , edition=3 , volume=2 , work=Taschenbuch der Nachrichtenverarbeitung , publisher=

Springer Verlag Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 in ...

, location=Berlin, Germany , isbn=3-540-06241-6 , lccn=73-80607 {{cite book , author-last1=Pedroni , author-first1=Volnei A. , title=Finite State Machines in Hardware: Theory and Design , date=2013 , publisher=

MIT Press The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts (United States). It was established in 1962. History The MIT Press traces its origins back to 1926 when MIT publish ...

, isbn=978-0-26201966-8 , page=50 , url=https://books.google.com/books?id=SSkTDgAAQBAJ&pg=PA50 {{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 Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 ...

, page=35 , isbn=9783540200741 , chapter-url=https://books.google.com/books?id=JEEmfObxnrAC&pg=PA35 {{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 {{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 Elsevier () is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its products include journals such as ''The Lancet'', ''Cell'', the ScienceDirect collection of electronic journals, '' Trends'', the ...

, isbn=((0-7506-4588-2)) , pages=191–192 , url=https://books.google.com/books?id=o7enSwSVvgYC&pg=PA192 , access-date=2020-04-19 , url-status=live , archive-date=2020-04-19 (519 pages

/ref> {{cite book , author-last=Lewis , author-first=Wilfrid Bennett , author-link=Wilfrid Bennett Lewis , title=Electrical Counting: With Special Reference to Counting Alpha and Beta Particles , date=1942 , publisher=

Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press A university press is an academic publishing hou ...

, page=90 , isbn=9781316611760 , url=https://books.google.com/books?id=5B5CDAAAQBAJ&pg=PA90 "Electronic accumulation", Robert E. Mumma's US Patent No. 2405096, filed in 1941
/ref> "Electronic switching device", Wilcox P. Overbeck's US Patent No. 2427533, filed in 1943
/ref> Dayton Codebreakers: 1942 Research Report, mentioning "A new high speed counter by Mr. Overbeck, January 8, 1942"
/ref> {{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 ��} {{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 {{cite book , editor-first=Nicholas , editor-last=Metropolis , author-first=Brian , 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 , isbn=9781483296685 , chapter-url=https://books.google.com/books?id=AsvSBQAAQBAJ&pg=PA652 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 {{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 Oxford University Press (OUP) is the university press of the University of Oxford. It is the largest university press in the world, and its printing history dates back to the 1480s. Having been officially granted the legal right to print books ...

, isbn=978-0-19957814-6 , pages=123–128 {{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 {{citation , 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 Xerox Holdings Corporation (; also known simply as Xerox) is an American corporation that sells print and digital document products and services in more than 160 countries. Xerox is headquartered in Norwalk, Connecticut (having moved from Stam ...

, 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) {{cite journal , title=A Photoelectric Decimal-Coded Shaft Digitizer , author-first1=William H. , author-last1=Libaw , author-first2=Leonard J. , author-last2=Craig , date=October 1953 , orig-year=September 1953 , journal= Transactions of the I.R.E. Professional Group on Electronic Computers , issn=2168-1740 , eissn=2168-1759 , volume=EC-2 , issue=3 , pages=1–4 , doi=10.1109/IREPGELC.1953.5407731 , url=https://www.researchgate.net/publication/224112055 , access-date=2020-05-26 (4 pages) {{cite book , title=A short note on useful codes for Fluidic Control Circuits , chapter=Codes particularly useful for analogue to digital conversions , author-first=E. Alexander , author-last=Powell , date=June 1968 , id=CoA Memo 156 , publisher= The College of Aeronautics, Department of Production Engineering , publication-place=Cranfield, UK , s2cid=215864694 , page=10 , url=https://dspace.lib.cranfield.ac.uk/bitstream/handle/1826/9559/COA_Memo_156_June_1968.pdf , access-date=2020-12-15 , url-status=live , archive-url=https://web.archive.org/web/20201215124905/https://dspace.lib.cranfield.ac.uk/bitstream/handle/1826/9559/COA_Memo_156_June_1968.pdf , archive-date=2020-12-15 (18 pages) (NB. The paper names the

Glixon code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representati ...

''modified Gray code'' and misspells Richard W. Hamming's name.) {{cite magazine , title=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. , author-first=Cornelius , author-last=van Holten , location=Delft Technical University, Delft, Netherlands , magazine=

Wireless World ''Electronics World'' (''Wireless World'', founded in 1913, and in September 1984 renamed ''Electronics & Wireless World'') is a technical magazine in electronics and RF engineering aimed at professional design engineers. It is produced monthly in ...

, issn=0043-6062 , publisher= IPC Business Press Ltd. , publication-place=Sutton, Surrey, UK , volume=88 , number=1559 , date=August 1982 , pages=43–46 , url=https://worldradiohistory.com/hd2/IDX-UK/Technology/Technology-All-Eras/Archive-Wireless-World-IDX/80s/Wireless-World-1982-08-OCR-Page-0024.pdf , access-date=2021-02-20 , url-status=live , archive-url=https://web.archive.org/web/20210221205532/https://worldradiohistory.com/hd2/IDX-UK/Technology/Technology-All-Eras/Archive-Wireless-World-IDX/80s/Wireless-World-1982-08-OCR-Page-0024.pdf , archive-date=2021-02-21}

(4 pages) Digital circuits Digital registers