Download Share Views 1170
Related Presentations


Shift Registers and Counters  Presentation Transcript

1. Shift Registers and Counters

2. What is an LFSR?

 Linear Feedback Shift Register

 An N-bit LFSR counts through all non-zero bit patterns in a pseudo-random order.

 Useful for the Project!!!

 Random Number Generator for collision back-off

 Error Checking

3. Tips on LFSR…

 Things to do  Place a linear array of D Flip Flops and feedback the last output to the first. (FF(N-1) output to FF(0) input)

 For an N-bit LFSR look at the table in Page 6 for a polynomial starting with x^N.

 For every term x^K in the polynomial compute an XOR of outputs of FF(N-1) and FF(K-1) and feed it to FF(K) as input (FF numbered from 0 to N-1)

 Things NOT to worry about

 What is a Galois Field?

 What is an irreducible polynomial?

4. An Example 5-bit LFSR

5. Parity Computation

6. Magic Error Checking

 Consider a 4-bit LFSR

 Serial Input:11001000111 (Note 11= 15-4 bits)

 11001000111 0000 ->1010

 11001000111 1010 ->0000

 Introduce error in 7th bit

11000000111 1010 ->0111

 00001000000 1010 ->0111 

 Isn’t 0111 equal to 7?

7. What to do in the lab?

8. Modes of Operation

 Mode 1:

 LFSR would shift 256 bits

 Display final parity in 8 LEDs

 Mode 0:

 Process sequence until pattern in DIP switch is equal to parity bits

 Final counter will be displayed in LEDs (position of error)

 If output is “0” then no errors in message

Mode controlled by SPARE button

9. Things to do

Run MODE=1 with all DIP switches set to 0. Compute parity bits as shown in LEDs.

 Enter parity bits on the switches, run MODE=1 and observe the output. Is it 0?

 Introduce only one error in the ROM –modify ROM schematic

 Use MODE=1 operation to detect the error.

 Use MODE=0 operation to find position of error.

10. Control FSM 

 Want Extra Credit! Do this logic as pre-lab. 

 3 inputs: TC output of counter, comparator and MODE from SPARE button

 2 states:

 ACTIVE state: upon RESET, enables the counter and LFSR  Waits until either TC from counter or PAR=LED signal from comparator(if MODE=0) and enters DONE state

 DONE state: Can leave this state only thru RESET

 Hooray!!! Need only 1 FF for the FSM

11. Things to know

 The last 8 bits of the ROM are set to 0 and are always read from the DIP switches

 Galois fields knowledge is useless for the lab!

 Xchecker cable clock runs at 1Mhz makes it difficult to observe what’s going on. Use of 16-bit counter to divide clock by 65536!

 Want to observe cycle-by-cycle, use Apply button in Hardware Debugger but should bypass the 2^16 bit counter

 To change ROM contents use INIT attribute by clicking on a ROM block

12. Before you Wake up! 

 Do Control FSM logic as pre-lab

Learn how to build an 8-bit LFSR

 Read the lab sheet twice before starting the lab

 Get your understanding about parity bits and error correction clear

Related Reports

Related Notes

Powered by

Stay Connected

copyright © 2012. All right reserved.
Designed and Developed by BVM SOLUTION