A Generalized Shift Register

An issue of extension of hardware for designing discrete devices with memory is considered. A device (generalized shift register) is proposed that substantially increases the capability of a unidirectional shift register with the series input and parallel output, which is implemented as a series connection of triggers. When a clock pulse is supplied, the trigger (at the next moment of time) can transfer from any state to the state depending on the input value. However the n-digit shift register in the alphabet with cardinality M at any n ≥ 2 can transfer at the next moment only to M states. This shift register is noted to have Mⁿ states. The devices, in the circuit of which all memory elements are in the same shift register, are known to implement a narrow class of images. It is shown that any sequential device can be implemented as a circuit of functional elements and a single generalized shift register.

References

[1] Wakerly J.F. Digital Design: Principles and Practices. 3rd Ed. Prentice Hall, 1999. 949 p. (Russ. Ed.: Dzhon F. Ueykerli. Proektirovanie tsifrovykh ustroystv. V 2 t. Moscow, POSTMARKET Publ., 2002. 543 p. (vol. 1), 528 p. (vol. 2).

[2] Trakhtenbrot B.A. An asymptotic estimate of the complexity of logical networks with memory. Dokl. Akad. Nauk SSSR [Proc. Acad. Sci. USSR], 1959, vol. 127, no. 2, pp. 281-284 (in Russ.).

[3] Trakhtenbrot B.A. On the complexity of circuits implementing multiparameter families of operators. Sb. "Problemy kibernetiki" [Collect. Pap. "Cybernetics problems"]. Moscow, Nauka Publ., 1964. iss. 12, pp. 99-112 (in Russ.).

[4] Orlov V.A. Algorithmic undecidability of the detecting problem of the asymptotic behavior of the Shannon function in implementing bounded-deterministic operators using schemes in an certain basis. Dokl. Akad. Nauk SSSR [Proc. Acad. Sci. USSR], 1971, vol. 196, no. 5, pp. 1036-1039 (in Russ.).

[5] Orlov V.A. Singularities of Shannon functions in the case of automation bases. Matematicheskie zametki [Mathematical Notes, pp. 48-53], 1972, vol. 11, no. 1, pp. 73-82 (in Russ.).

[6] Orlov V.A. On the functions implementation by circuits and formulas in functionally complete basis Dokl. RAN [Proc. Russ. Acad. Sci.], 1999, vol. 365, no. 6, pp. 734-735 (in Russ.).