introductory stuff
If you aren't familiar with the term, 'bit', it may help you to think of the definition of a 'digit.' [B(inary) (dig)IT] A bit can have the value 0 or 1, just as a digit can have the value 0, 1, 2, ..., or 9. Here are three dictionary1 defintions for a bit:
- A single character of a language having just two characters, as either of the binary digits 0 or 1.
- A unit of information equivalent to the choice of either of two equally likely alternatives.
- A unit of information storage capacity, as of a computer memory.
Registers are a component of a computer, used to store temporary results and certain control information. They are characterized by being small and high-speed (compared to other types of memory.) A register can hold a fixed number of bits. In this example, the register can hold 11 bits. (Notice that the counting starts with 0. This is standard in computer science.) The adjective 'feedback' is used to describe systems in which the next state is determined at least in part by the current state. In other words, the output is connected to the input.
A example typically used to explain 'feedback' is that of a simple thermostat programmed with the following algorithm (an algorithm is a step-by-step solution to a problem.) Assume that a certain temperature has already been determined. (Assumptions that must be true in order for an algorithm to operate correctly are called pre-conditions.)
- Measure the current temperature
- If the current temperature is too high, turn off the heat
- If the current temperature is too low, increase the heat
- repeat
This is a feedback system, because the next 'state' of temperature is determined based on the present state.
In a linear feedback shift register, the values in the register change at each time step. Depending on the direction of the shift, the i-th bit changes to the value of either its left (i+1) or right (i-1) neighboring bit.
XOR is shorthand for 'exclusive or.' We'll talk about XOR more in precept later on in the semester. The '^' is used on this slide as an abreviation for XOR. If you aren't familiar with boolean formulas (like (a^b)^b = a^(b^b)), don't worry about that now.
In this example, the values in the register shift to the left. Notice that when you shift, the bit to the left 'gets lost,' since there's no 'bit #11' of the register. At the same time, it isn't obvious which value the rightmost bit should get. In this example, the rule is that bit 0 should get the XOR of bits 3 and 10. So, if bits 3 and 10 are different, bit 0 gets the value 1. If bits 3 and 10 are the same, bit 0 gets the value 0.
The bit code for each letter is its number in the alphabet (a = 1, b = 2, c = 3, ...) in its binary form. You will learn how to convert from decimal (1,2,3,...) to binary (1, 10, 11,...) and vice-versa in this course.
This slide gives you an application for which XOR may be used.
This slide continues the discussion started in slide 7.
The main point is that, in principle, it is possible to write a C program that can simulate the actions of a LFBSR. Since you probably don't know C yet (and if you do, you may not have seen some of the operators), this slide probably doesn't help you understand the LFBSR. Furthermore, if binary numbers are new to you, the explanation of the operators probably doesn't make sense to you. Don't worry, soon you will be able to understand such programs (and even write them).
This slide has a lot of important information, introduced without too much explanation. You should make a note of the things you don't know yet, but don't worry about learning them right away. Concentrate on getting comfortable with programming in C first; then worry about learning the more general concepts.
1. American Heritage Dictionary, Second College Edition, 1982.