Development of State Model Theory for External Exclusive NOR Type LFSR Structures

Authors: Afaq Ahmad

Abstract:

Using state space technique and GF(2) theory, a simulation model for external exclusive NOR type LFSR structures is developed. Through this tool a systematic procedure is devised for computing pseudo-random binary sequences from such structures.

Keywords: LFSR, external exclusive NOR type, recursivebinary sequence, initial state - next state, state transition matrix.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1075814

References:

[1] N. Zierler & J. Brillhart, "On Primitive Trinomials (Mod 2)," Information and Control 13, pp. 541-554, 1968
[2] N. Zierler & J. Brillhart, "On Primitive Trinomials (Mod 2), II," Information and Control 14, pp. 566-569, 1969
[3] S. W. Golomb, "Shift Register Sequence", Second Edition - Holden- Day, 1982
[4] R.E. Blahut, "Theory and Practice of Error Control Codes", Addison- Wesley, MA, 1983
[5] W. W. Peterson and E. J. Weldon, Jr., "Error-Correcting Codes", Second Edition - The MIT Press, 1984
[6] P. H. Bardell, "Design Considerations for Parallel Pseudorandom Pattern Generators," JETTA, Vol. 1, No. 1, pp. 73-87, Feb. 1990
[7] P.H. Bardell, "Design considerations for parallel pseudorandom pattern generators," Journal of Electronic Testing and Applications, Vol. 1, No. 1, pp. 73-87, 1990
[8] A Ahmad, A. Al-Lawati, "Reducing Test Time Via An Optimal Selection of LFSR Feedback Taps", IEEE Proceedings - IEEE Catalog 01EX467C (ISSPA-01- Malaysia), August, pp. 1-4, 2001
[9] A. Ahmad, Z. Nadir, F. A.Khan, "FPGA Based Design Of Faster PN Generators For The Use Of CDMA Applications" Proceedings Wireless and Optical Communications Networks (WOCN 2004), IFIP TC6/ IEEE, June 7 - 9, pp 272 - 275, 2004
[10] L.T. Wang and E.J. McCluskey, "Linear feedback shift register design using cyclic codes," IEEE Transactions on Computers, Vol. C-37, No. 10, pp. 1302-1306, 1987
[11] T.W. Williams, W. Daehn, M. Gruetzner and C.W Starke, "Bounds and Analysis of Aliasing Errors in Linear Feedback Shift Registers", IEEE Trans. Computer Aided-Design, Vol. CAD-7 No. 1, Jan., pp. 75-83, 1988
[12] N. K Nanda., A. Ahmad and V.C. Gaindhar, (1989) ÔÇÿShift register modification for multipurpose use in combinational circuit testing,- International Journal of Electronics (UK), vol.66, no.6, pp.875-878, 1989
[13] A. Ahmad, N. K. Nanda and K Garg, "Are Primitive Polynomials Always Best in Signature Analysis?", IEEE Design & Test of Computers, Vol. 7, No. 4, Aug. 1990, pp. 36-38.
[14] S. Hellebrand, S. Tarnick, J. Rajski and B. Courtois, "Generation of vector patterns through reseeding of multiple-polynomial linear feedback shift registers," in Proceedings of IEEE International Test Conference, , pp. 120-129, 1992
[15] J. Savir and W.H. McAnney, "A multiple seed linear feedback shift register," IEEE Transaction on Computers, Vol. 41, No. 2, pp. 250-252, 1992
[16] A. Ahmad, "Critical role of polynomial seeds on the effectiveness of an LFSR-based testing technique," International Journal of Electronics (UK), vol.77, no.2, pp.127-137, 1994
[17] A. Ahmad, "Achievement of higher testability goals through the modification of shift register in LFSR based testing," International Journal of Electronics (UK), vol. 82, no. 3, pp. 249-260, 1997
[18] A. Ahmad, M. J. Al-Musharafi, S. Al-Busaidi, "Study And Implementation Of Properties Of m-Sequences In MATLABSIMULINK - A Pass/Fail Test Tool For Designs Of Random Generators", SQU Journal of Scientific Research - Science and Technology, vol. 7, part 1, June 2002, pp. 147 -156.
[19] C. V. Krishna, A. Jas, N. A. Touba, "Achieving high encoding efficiency with partial dynamic LFSR reseeding", ACM Transactions on Design Automation of Electronic Systems, Volume 9 , Issue 4 (October), pp. 500 - 516, 2004
[20] A. Guha and L.L. Kinney, "Relating the cyclic behavior of linear and intra-inverted feedback shift registers," IEEE Transactions on Computers, Vol. C-41, No. 9, 1992, pp. 1088-1100.
[21] R.A. Frohwerk, "Signature analysis: A new digital field service method," Hewlett-Packard Journal, Vol. 28, No. 9, pp. 2-8, 1977
[22] B. Konemann, J. Mucha and G. Zwiehoff, "Built-in logic block observation technique," Digest of Papers 1979 Test Conference, pp. 37- 41,1979
[23] .J.E. Smith, "Measures of the effectiveness of fault signature analysis," IEEE Transactions on Computers, Vol. C-29, No. 6, pp. 510-514, 1980
[24] Z. Barzilai, D. Coppersmith and A.L. Rosenberg, "Exhaustive generation of bit patterns with applications to VLSI self-testing," IEEE Transactions on Computers, Vol. C-32, No. 2, pp. 190-194, 1983
[25] T. W. Williams, "VLSI Testing", IEEE Computer, Vol. C-17, No. 10, Oct., pp. 126-136, 1984
[26] S.B. Akers, "On the use of linear sums in exhaustive testing," Digest of Papers 15th Annual International Fault-Tolerant Computing Symposium, pp. 148-153, 1985
[27] E. J. McCluskey, "Built-In Self-Test Techniques", IEEE Design & Test of Computers, Vol. 2, No. 2, April 1985, pp. 21-28.
[28] C.L. Chen, "Linear dependencies in linear feedback shift registers," IEEE Transactions on Computers, Vol. C-35, No. 12, pp. 1086-1088, 1986
[29] P.H. Bardell, W.H. McAnney and J. Savir, Built-in Test for VLSI: Pseudorandom Techniques, Wiley, New York, 1987
[30] P. H. Bardell, W.H. McAnney, and J. Savir, Built-In-Test for VLSI, New York: John Wiley, 1987
[31] W.B. Jone and C.A. Papachristou, "A coordinated approach to partitioning and test pattern generation for pseudo-exhaustive testing," in Proceedings of 26th ACM/IEEE Design Automation Conference, pp. 525-530, 1989
[32] M. Abramovici, M.A. Breuer and A.D. Friedman, Digital Systems Testing and Testable Design, Computer Science Press, New York, 1990.
[33] R. Raina and P.N. Marinos, "Signature analysis with modified linear feedback shift registers (M-LFSRs)," in Proceedings of Fault-Tolerant Computing: 21st International Symposium, pp. 88-95, 1991
[34] S. Venkataraman, J. Rajski, S. Hellebrand and S. Tarnick, "An efficient BIST scheme based on reseeding of multiple polynomial linear feedback shift registers," in Proceedings of ICCAD-93, pp. 572-577, 1993
[35] R. Srinivasan, S.K. Gupta and M.A. Breuer, "Novel test pattern generators for pseudo-exhaustive testing," in Proceedings IEEE International Test Conference, pp. 1041-1050, 1993
[36] S. Venkataramann, J. Rajski, S. Hellebrand, and S. Tamic, "An Efficient BIST Scheme Based on Reseeding of Multiple Polynomial Linear Feedback Shift Register", Proc. Int'l. Conf. on Computer -Aided Design (ICCAD), pp. 572-577, 1993
[37] C.A. Chen and S.K. Gupta, "A methodology to design efficient BIST test pattern generators," in Proceedings of IEEE International Test Conference, pp. 814-823, 1995
[38] C.A. Chen and S.K. Gupta, "BIST test pattern generators for two-pattern testing - theory and design algorithms," IEEE Transactions on Computers, Vol. 45, No. 3, pp. 257-269, 1996
[39] N. A. Touba and E. J. McCluskey, "RP-SYN: Synthesis of Random- Pattern Testable Circuits with Test Point Insertion", IEEE Trans. Computer- Aided Design, Vol. CAD-18, No. 8, Aug. 1999, pp. 1202- 1213.
[40] A. Ahmad, "Constant Error Masking Behavior of An Internal X-OR Type Signature Analyzer Due To The Changed Polynomial Seeds", Journal Of Computers & Electrical Engineering (PERGAMON, Elsevier Science), Vol. 28, No. 6, pp. 577 - 588, 2002
[41] A. Ahmad, M. J. Al-Musharafi., S. Al-Busaidi, "Design and study of a Strong Stream Crypto-System Model for e-Commerce", International Council for Computer Communication Publishers - Washington DC, USA (The ACM Library), pp. 619 - 630, 2002
[42] T. Jamil, A. Ahmad, (April 2002) "An Investigation in to the Application of Linear Feedback Shift Registers for Steganography", Proceedings IEEE SoutheastCon2002, April, pp. 239-244, 2002
[43] A. Ahmad, A. M Elabdalla, "An efficient method to determine linear feedback connections in shift registers that generate maximal length pseudo-random up and down binary sequences," Computer & Electrical Engineering -An Int-l Journal (USA), vol. 23, no. 1, pp. 33-39, 1997