Random flip-flop

Add links
From Wikipedia, the free encyclopedia

Random flip-flop (RFF) is a theoretical concept of a non-sequential logic circuit capable of generating true randomness. By definition, it operates as an "ordinary" edge-triggered clocked flip-flop, except that its clock input acts randomly and with probability p = 1/2.[1] Unlike Boolean circuits, which behave deterministically, random flip-flop behaves non-deterministically. By definition, random flip-flop is electrically compatible with Boolean logic circuits. Together with them, RFF makes up a full set of logic circuits capable of performing arbitrary algorithms, namely to realize Probabilistic Turing machine.

Symbol[edit]

Figure 1. Variety of random flip-flops

Random flip-flop comes in all varieties in which ordinary, edge triggered clocked flip-flop does, for example: D-type random flip-flop (DRFF). T-type random flip-flop (TRFF), JK-type random flip-flop (JKRFF), etc. Symbol for DRFF, TRFF and JKRFF are shown in the Fig. 1.

Figure 2. Emulation of TRFF by DRFF and vice versa.

While varieties are possible, not all of them are needed: a single RFF type can be used to emulate all other types. Emulation of one type of RFF by the other type of RFF can be done using the same additional gates circuitry as for ordinary flip-flops. Examples are shown in the Fig. 2.

Practical realization of random flip-flip[edit]

By definition, action of a theoretical RFF is truly random. This is difficult to achieve in practice and is probably best realized through use of physical randomness. A RFF, based on quantum-random effect of photon emission in semiconductor and subsequent detection, has been demonstrated to work well up to a clock frequency of 25 MHz.[1] At a higher clock frequency, subsequent actions of the RFF become correlated. This RFF has been built using bulk components and the effort resulted only in a handful of units. Recently, a monolithic chip containing 2800 integrated RFFs based on quantum randomness has been demonstrated[2][3] in Bipolar-CMOS-DMOS (BCD) process.

Applications and prospects[edit]

Figure 3. Random number generators by use of RFF. A RFF can work up to a certain Request (clock) rate. One can use N RFFs to enhance bit production rate by factor N.

One straightforward application of a RFF is generation of random bits, as shown in the Fig. 3.

Since each RFF operates independent of all others, N RFFs can generate N bits per clock, thus the overall generation throughput of a random number generator is only limited by the number of available RFFs and their maximum operating clock frequency.

The biggest difference between a RFF and a true random number generator is that a plethora of RFFs can work concurrently, independently of each other, with or without any synchronicity among them. This is useful in stochastic computing,[4][5][6][7][8] also known as Random Pulse Computing (RPC)[1] , where many information-processing circuits work in parallel. RFF could also find its use in: prosthetic implants such as artificial cochlear or prosthetic limbs using, near-sensor image processing[9] as well as in artificial intelligence processors.[10][11][12][13] Furthermore, having in mind its high speed, a single RFF can be used to generate on the order of hundred thousand 256-bit cryptographic keys per second, or nonce data, without requiring any special or proprietary protocol to communicate with, making it potentially indispensable piece of security hardware such as IoT devices, smart cards, car keys, as well as of any computer or digital communication device.

While the technology of realizing a RFF on a chip is young,[2] it is conceivable that in the future RFF as an electronic element will appear in universal logic chips (such as 7400-series integrated circuits), in Application Specific Integrated Circuits (ASIC), and in Field-Programmable Gate Array (FPGA) chips, thus facilitating designs that could benefit from it.

References[edit]

  1. ^ a b Stipčević, Mario (March 2016). "Quantum random flip-flop and its applications in random frequency synthesis and true random number generation". Review of Scientific Instruments. 87 (3): 035113. arXiv:1308.5719. Bibcode:2016RScI...87c5113S. doi:10.1063/1.4943668. ISSN 0034-6748. PMID 27036825. S2CID 24089028.
  2. ^ a b Keshavarzian, Pouyan; Ramu, Karthick; Tang, Duy; Weill, Carlos; Gramuglia, Francesco; Tan, Shyue Seng; Tng, Michelle; Lim, Louis; Quek, Elgin; Mandich, Denis; Stipčević, Mario; Charbon, Edoardo (2022-09-11). "A 3.3 Gbps SPAD-Based Quantum Random Number Generator". arXiv:2209.04868 [cs.CR].
  3. ^ Keshavarzian, Pouyan; Ramu, Karthick; Tang, Duy; Weill, Carlos; Gramuglia, Francesco; Tan, Shyue Seng; Tng, Michelle; Lim, Louis; Quek, Elgin; Mandich, Denis; Stipčević, Mario; Charbon, Edoardo (2023). "A 3.3-Gb/s SPAD-Based Quantum Random Number Generator". IEEE Journal of Solid-State Circuits. 58 (9): 2632–2647. Bibcode:2023IJSSC..58.2632K. doi:10.1109/JSSC.2023.3274692. ISSN 0018-9200. S2CID 258793632.
  4. ^ Von Neumann, John (1995). The Neumann compendium. F. Bródy, Tibor Vámos. Singapore: World Scientific. ISBN 981-02-2201-7. OCLC 32013468.
  5. ^ Alaghi, Armin; Qian, Weikang; Hayes, John P. (August 2018). "The Promise and Challenge of Stochastic Computing". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 37 (8): 1515–1531. doi:10.1109/TCAD.2017.2778107. ISSN 1937-4151. S2CID 5990686.
  6. ^ Alaghi, Armin; Hayes, John P. (2013-05-01). "Survey of Stochastic Computing". ACM Transactions on Embedded Computing Systems. 12 (2s): 92:1–92:19. doi:10.1145/2465787.2465794. ISSN 1539-9087. S2CID 4689958.
  7. ^ Qian, Weikang; Li, Xin; Riedel, Marc D.; Bazargan, Kia; Lilja, David J. (January 2011). "An Architecture for Fault-Tolerant Computation with Stochastic Logic". IEEE Transactions on Computers. 60 (1): 93–105. doi:10.1109/TC.2010.202. ISSN 1557-9956. S2CID 9969218.
  8. ^ Stipčević, Mario; Batelić, Mateja (2022-01-07). "Entropy considerations in improved circuits for a biologically-inspired random pulse computer". Scientific Reports. 12 (1): 115. Bibcode:2022NatSR..12..115S. doi:10.1038/s41598-021-04177-9. ISSN 2045-2322. PMC 8741937. PMID 34997140.
  9. ^ Lee, Vincent T.; Alaghi, Armin; Hayes, John P.; Sathe, Visvesh; Ceze, Luis (March 2017). "Energy-efficient hybrid stochastic-binary neural networks for near-sensor computing". Design, Automation & Test in Europe Conference & Exhibition (DATE), 2017. pp. 13–18. arXiv:1706.02344. doi:10.23919/DATE.2017.7926951. ISBN 978-3-9815370-8-6. S2CID 1557449.
  10. ^ Widrow, Bernard; Kim, Youngsik; Park, Dookun; Perin, Jose Krause (2019-01-01), Kozma, Robert; Alippi, Cesare; Choe, Yoonsuck; Morabito, Francesco Carlo (eds.), "Nature's Learning Rule", Artificial Intelligence in the Age of Neural Networks and Brain Computing, Academic Press, pp. 1–30, doi:10.1016/b978-0-12-815480-9.00001-3, ISBN 978-0-12-815480-9, S2CID 125516633, retrieved 2023-04-27
  11. ^ Canals, Vincent; Morro, Antoni; Oliver, Antoni; Alomar, Miquel L.; Rosselló, Josep L. (March 2016). "A New Stochastic Computing Methodology for Efficient Neural Network Implementation". IEEE Transactions on Neural Networks and Learning Systems. 27 (3): 551–564. doi:10.1109/TNNLS.2015.2413754. ISSN 2162-2388. PMID 25915963. S2CID 3452994.
  12. ^ Ren, Ao; Li, Zhe; Wang, Yanzhi; Qiu, Qinru; Yuan, Bo (October 2016). "Designing reconfigurable large-scale deep learning systems using stochastic computing". 2016 IEEE International Conference on Rebooting Computing (ICRC). pp. 1–7. doi:10.1109/ICRC.2016.7738685. ISBN 978-1-5090-1370-8. S2CID 738155.
  13. ^ Cheng, Zengguang; Ríos, Carlos; Pernice, Wolfram H. P.; Wright, C. David; Bhaskaran, Harish (September 2017). "On-chip photonic synapse". Science Advances. 3 (9): e1700160. Bibcode:2017SciA....3E0160C. doi:10.1126/sciadv.1700160. ISSN 2375-2548. PMC 5617375. PMID 28959725.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Random_flip-flop&oldid=1191229988"