Slide Number 1Rotate Shift RegisterRotate Shift RegisterLinear Feedback Shift Register (LFSR)3-bit LFSR Example3-bit LFSR Example3-bit LFSR Example3-bit LFSREffect of Changing ConfigurationLFSRXNOR vs. XORLFSR Seed ValuesImplementation OptionsApplication of LFSR CryptologyCryptologyLFSR Application: EncryptionLFSR Application: CRC Error CheckingLFSR Application: CRC Error CheckingLFSR Application: CRC Error CheckingOther Error Checking ApproachesLFSR Application: BISTLFSR Application: BISTDepartment of Electrical and Computer EngineeringMississippi State UniversitySherif Abdelwahed Linear Feedback Shift RegistersComputer Aided Digital Systems Design - EE 4743/6743Rotate Shift RegisterShiftRegister (shift left)NDoutShift InParallel InNDout(N)Produces sequence of N different wordsRotate Shift RegisterProduces sequence of N different words Dout Shift In Decimal Value00001111 0 15 (seed)00011110 0 3000111100 0 6001111000 0 12011110000 1 24011100001 1 22511000011 1 19510000111 1 13500001111 0 15 (repeats)Linear Feedback Shift Register (LFSR)A Linear Feedback Shift Register can be used a pseudo-random sequence which can be used as test vectors for design.ShiftRegister(shift left)XOR of particular bitsNDoutShift InParallel InNCan also use XNOR3-bit LFSR Example3-bit ShiftRegisterXOR of bits 2,13Dout(2:0)Shift InFor a 3 bit register, ShiftIn = Dout(1) ⊕ Dout(2)Seed(2:0)N3-bit LFSR ExampleActual DesignThe taps in this example are at bit 0 and bit 1, and can be referenced as [1,2]. 203-bit LFSR Example Always have 1 and xnterms in polynomial Binary Vector Equation:X0 (t+ 1)X1 (t+ 1)X2 (t+ 1)010101100X0 (t)X1 (t)X2 (t)=3-bit LFSRProduces sequence of 2N-1 different words For 3-bit case: sequence of 7Dout Shift In Decimal Value111 0 7 (seed)011 0 3001 1 1100 0 4010 1 2101 1 5110 1 6111 0 7 (repeats)Effect of Changing ConfigurationLFSR For an N-bit shift register, the maximum length sequence that can be generated is 2N-1 ¾ Sequence will repeat after this¾ Must use specific sets of bits to XOR Following set of bits produces maximal sequence:¾ ShiftIn = Q(1) ⊕ Q(2) ⊕ Q(3) ⊕ Q(7) (tap [1,2,3,7])¾ ShiftIn = Q(3) ⊕ Q(4) ⊕ Q(5) ⊕ Q(7) (tap [3,4,5,7])¾ ShiftIn = Q(2) ⊕ Q(4) ⊕ Q(6) ⊕ Q(7) (tap [2,4,6,7]) Each of the above feedback arrangements produces a different sequence, but still maximalXNOR vs. XORNever outputs a “000”Never outputs a “111”LFSR Seed Values Can start in a different place using a different seed¾ Will still have the same sequence Must start with a non-zero seed for XOR-style LFSRs¾ 0 ⊕ 0 = 0¾ Will never leave the zero seed value Opposite is true for XNOR-style LFSR¾ 1 ⊕ 1 = 1¾ Start in a non-all-one seedImplementation OptionsApplication of LFSR Encryption and decryption,  Cyclic redundancy checks (CRCs),  Data compression,  Built-in self-test (BIST),  Pseudo-random number generation.Cryptology A is original data (A ⊕ B) to encrypt the data which is sent xor B again to decrypt¾ (A ⊕ B) ⊕ B = A B must be the same on each end¾ Called a KEY However, the key can change, as long as both ends change the same wayXOR XORAA XOR BAB Bsecure secureunsecureCryptology Using LFSRs, the key changes every clock The seed must be the same¾ Then will proceed through the same sequenceXOR XORAA XOR BAsecure secureunsecureLFSR LFSRseed seedLFSR Application: Encryption Large N LFSRs can produce very long sequences¾ N=64 has sequence length of 1.8x1019¾ At a clock rate of 1GHz, will take 18 million seconds to progress through the entire sequence¾ or, 213 days¾ Only takes 64 flip-flops to implement¾ N=70 would take 37 years This is why there are bit-length restrictions on encryptionLFSR Application: CRC Error Checking LFSRs can also be used to check long sequences of data for errors¾ Cyclic Redundancy Check (CRC) is a common method An input is included in the XOR feedback path After the entire sequence of data is processed, a small number is produced¾ Usually called a checksum This number will be drastically different if there have been any errorsLFSR Application: CRC Error CheckingThe likelihood of generating a correct CRC with random errors in the data is practically zeroLFSR Application: CRC Error Checking CRC calculators typically use a minimum of 16-bits providing 65,536 unique values.  Standard communications protocols specify the number of bits employed in their CRC calculations and the taps to be used.  The taps are selected such that an error in a single data bit will cause the maximum possible disruption to the resulting checksum value.  Thus, in addition to being referred to as maximal-length, these LFSRs may also be qualified as maximal-displacement. CRCs is also applied to detect computer viruses.Other Error Checking Approaches Parity¾ One bit output¾ Counts the number of 1’s¾ Outputs 1 for an odd number of 1’s, 0 for an even number of 1’s¾ One bit toggled can easily be found, but multiple errors may not Two-of-five¾ Ensured in every 5 bit block, only two 1’s would occur¾ Multiple errors still uncovered Redundancy¾ Send data multiple times or doubly encode data¾ More resistant to multiple errors Other codes can do error-recovery ¾ Hamming codes, Reed-Soloman codes, Reed-Muller codes, Binary Golay codes, convolution codes, turbo codesLFSR Application: BIST One test strategy which may be employed in complex integrated circuits is that of built-in self-test (BIST).  Devices using BIST contain special test generation and result gathering circuits.  A multiplexer is used to select between the standard inputs and those from the test generator.  A second multiplexer selects between the standard outputs and those from the results gatherer.  Both the test generator and results gatherer can be implemented using LFSRsLFSR Application: BISTThe standard inputs and outputs along with theirmultiplexers have been omittedThe LFSR for test generator is used to create a sequence of test patterns,The LFSR for results gatherer is used to capture the results. The results-gathering LFSR features modifications that allow it to accept parallel