On Sequence Lengths of Some Special External Exclusive OR Type LFSR Structures – Study and Analysis

A Ahmad, A Al Maashri

Abstract


The study of the length of pseudo-random binary sequences generated by Linear- Feedback Shift Registers (LFSRs) plays an important role in the design approaches of built-in selftest, cryptosystems, and other applications. However, certain LFSR structures might not be appropriate in some situations. Given that determining the length of generated pseudo-random binary sequence is a complex task, therefore, before using an LFSR structure, it is essential to investigate the length and the properties of the sequence. This paper investigates some conditions and LFSR’s structures, which restrict the pseudo-random binary sequences’ generation to a certain fixed length. The outcomes of this paper are presented in the form of theorems, simulations, and analyses. We believe that these outcomes are of great importance to the designers of built-in self-test equipment, cryptosystems, and other applications such as radar, CDMA, error correction, and Monte Carlo simulation.

 


Keywords


LFSR, Pseudo-random binary sequence, Seed, Feedback connection, Periodicity, Exclusive OR.

Full Text:

PDF

References


Ahmad A (1994), Critical role of polynomial seeds on the effectiveness of an LFSRbased testing technique. International Journal of Electronics 77:127–137.

Ahmad A (1997), Achievement of higher testability goals through the modification of shift register in LFSR based testing. International Journal of Electronics 82:249–260.

Ahmad A (2002), Constant error masking behavior of an internal XOR type signature analyzer due to the changed polynomial seeds. Journal of Computers & Electrical Engineering 28:577–589.

Ahmad A (2005a), Testing of complex integrated circuits (ICs)–The bottlenecks and solutions. Asian Journal of Information Technology4:816–822.

Ahmad A (2005b), Development of state model theory for external exclusive-NOR type LFSR structures. World Enformatika Society-Transactions on Engineering, Computing and Technology 10:12–19.

Ahmad A (2012), Better PN generators for CDMA application–A Verilog-HDL implementation approach. International Journal of Information Engineering 2:6– 11.

Ahmad A (2013a), Development realization of a better signature analysis scheme by adding a bit to the size of 8k. International Journal of Information Engineering 3:122–128.

Ahmad A, Al-Busaidi SS, Al-Maashri A, Awadalla M, Rizvi MAK, Mohanan N

(2013b), Computing and listing of possible number of m-sequence generators of order n. Indian Journal of Science and Technology10:5359–5369.

Ahmad A, Al-Busaidi SS, Al-Mushrafi MJ (2013c), On properties of PN sequences generated by LFSR—A generalized study and simulation modeling. Indian Journal of Science and Technology10:5351–5358.

Ahmad A, Al-Maashri A (2008), Investigating some special sequence lengths generated in an external exclusive-NOR type LFSR. Journal of Computers and Electrical Engineering 34:270–280.

Ahmad A, Al-Musharafi MJ, Al-Busaidi S (2002), 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 7:147–156.

Ahmad A, Al-Musharafi MJ, Al-Busaidi S, Al-Naamany A, Jervase JA (2001), An NLFSR based sequence generation for stream ciphers. Proceeding International Conference on Sequences and their Applications, Bergen, Norway, May 13- 17, 11–12.

Ahmad A, Elabdalla AM (1997), 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 International Journal 23:33–39.

Ahmad A, Nanda NK, Garg K (1997), Are primitive polynomials always best in signature analysis? IEEE Design & Test of Computers 7:36–38.

Ayinala M, Parhi K (2011), High-speed parallel architectures for linear feedback shift registers. IEEE Transactions on Signal Processing 59(9):4459–4469.

Bardell PH, McAnney WH, Savir J (1987), Built-in-test for VLSI. New York: John Wiley.

Chunqiang H, Xiaofeng L, Xiuzhen (2012), Verifiable multi-secret sharing based on LRSR sequences. Journal of Theoretical Computer Science 445:52-62.

Golomb SW (1981), Shift register sequence. Walnut Creek, CA: Aegean Park Press.

Hell M, Johansson T, Maximov A, Meier W (2008), New stream cipher designs—The eSTREAM finalists, Springer 4986:179– 190.

Hu CQ, Liao XF, Cheng XH (2012), Verifiable multi-secret sharing based on LFSR sequences. Journal of Theoretical Computer Science (Elsevier) 45:52–62.

Jamil T, Ahmad A (2002), An Investigation into the Application of Linear Feedback Shift Registers for Steganography. Proceeding IEEE Southeast Con, SC, USA. April 2002.

Kao MH (2013), On the optimality of extended maximal length linear feedback shift register sequences. Journal Statistics & Probability Letters 83:1479–1483.

Knuth D (1997), The art of computer programming, Semi numerical algorithms. Reading, MA: Addison- Wesley 2.

Krishnaswamy S, Pillai HK (2012), On the number of linear feedback shift registers with a special structure. IEEE Transactions on Information Theory 58(3):1783–1790.

McCluskey EJ (1985), Built-in self-test techniques. IEEE Design & Test of Computers 2(2):21–28.

Ming-Hung K (2013), On the optimality of extended maximal length linear feedback shift register sequences. Journal of Statistics and Probability Letters 83(6):1479-1483.

Mukherjee N, Rajski J, Mrugalski G, Pogiel A (2011), Ring generator: An ultimate linear feedback shift register. IEEE Computer 44(6):64–71.

Nanda NK, Ahmad A, Gaindhar VC (1989), Shift register modification for multipurpose use in combinational circuit testing. International Journal of Electronics 66(6):875–878.

Peinado A, Fuster-Sabater A (2013), Generation of pseudorandom binary sequences by means of linear feedback shift registers (LFSRs) with dynamic feedback. Mathematical and Computer Modeling 57(6): 2596–2604.

Peterson WW, Weldon EJ Jr (1984), Errorcorrecting codes. 2nd ed., Cambridge, MA: Massachusetts Institute of Technology Press.

Williams TW (1984), VLSI testing. IEEE Computer C-17(10):126–136.

Williams TW, Daehn W, Gruetzner M, Starke CW (1988), Bounds and analysis of aliasing errors in linear feedback shift registers. IEEE Trans. Computer Aided- Design CAD-7(1):75–83.




DOI: http://dx.doi.org/10.24200/tjer.vol11iss2pp1-14

Refbacks

  • There are currently no refbacks.




Copyright (c) 2017 A Ahmad, A Al Maashri

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

TJER 2017-CC BY-ND

This journal and its content is licensed under a Attribution-NoDerivatives 4.0 International.

Flag Counter