Double Feedback LFSR Parallel Output Generation

  • Robert Apikyan Institute of Information and Telecommunication Technologies and Electronics, NPUA, Yerevan, Armenia
  • Hovhannes Gomtsyan Institute of Information and Telecommunication Technologies and Electronics, NPUA, Yerevan, Armenia
  • Vahe Bayadyan Tum School of Management, Technical University of Munich, Munich, Germany
Keywords: LFSR, PRN sequences, parallel generation

Abstract

LFSR shift registers provide the mechanism that allows generating PRN (pseudo-random numbers) sequences. LFSR consists of sequentially connected memory cells where each cell can apply one of the two values 0 or 1. These cells are often called flipflops. In each step, the value from the last flipflop is passed to the next one. The first flip-flop in register applies LFSR's feedback value. The feedback value is the modulo addition of current values from specified flipflops in position. The output code of LFSR is a sequence of ones and zeros. Mostly these outputs or PRN sequences are used for signal modulation in CDMA. For example, in GPS, the broadcasting signal from satellites is modulated with unique PRN numbers for each satellite to allow receivers to identify data with broad-casting satellite numbers. The identification process is performed based on the correlation between locally generated PRN numbers and received signals from satellites. The pick of correlation value means that the signal is identified. Also, the LFSR’s are using in cryptography, and the encryption and decryption time depends on LFSR’s output generation time. The parallel generation method will short this time. The PRN code generation is a sequential process, making it parallel will short the overall signal identification and correlation time for CDMA usage and the encryption and decryption time in cryptography . This article as a unit of discussion will be two feedback based on LFSR’s parallel output generation, and the definition of generic formula that will allow us to define upcoming states of double feedback LFSR without sequential processing.

References

Thesis:

James Bao-Yen Tsui, a Wiley Interscience publication “Fundaments of Global Positioning System Receivers: A Software Approach”, 93 –99.

http://twanclik.free.fr/electricity/electronic/pdfdone7/Fundamentals%20of%20Global%20Positioning%20System%20Receivers.pdf

Book:

John F. Brendle Jr. (2000) Pseudorandom Code Generation for Communication and Navigation System Application, 17-23. https://apps.dtic.mil/dtic/tr/fulltext/u2/a336311.pdf

Internet:

Program reference in GitHub - https://github.com/RobertApikyan/GpsGenerator/tree/parallel_lfsr_generation

ParallelTwoFeedbackLFRS.java class reference in GitHub - https://github.com/RobertApikyan/GpsGenerator/blob/parallel_lfsr_generation/src/src/main/ParallelTwoFeedbackLFSR.java

Published
2019-09-26
Section
Articles