Because I don’t feel right posting this semester’s Crammer’s Guides without having posted all of last semesters, I’ve got this for you. Note that it’s a bit incomplete, because I have neither the time nor the drive to fix it, but I think it’s good enough that someone might find it useful. Also, If you see any inaccuracies, let me know in comments, so I can fix them up. So if you do, congratulations, and you’re welcome; otherwise, I’m sorry…
This one’s about Computer System Fundamentals. This subjects covers CPU cycles, binary, digital logic, RAM allocation and programming in assembly language.
CPU Basics
Here are the main components of a CPU:
- Arithmetic Logic Unit (ALU) – the brain of the CPU, it performs arithmetic and logic functions .
- Registers – high speed ‘scratch pad’ memory slots to store data currently being processed.
- Memory Buffer Register (MBR) – stores data just received from, or about to be written to memory.
- Memory Access Register (MAR) – stores the address of memory to be accessed next.
- Program Counter (PC) – stores the address of next instruction.
The CPU instruction cycle, known as fetch, decode & execute, goes like this:
Fetch
- PC contents copied to MAR. Read/write line set to read
- Memory address accessed
- Contents of addressed memory copied to Data Bus, moved to Instruction Decoder
Decode
- Instruction Decoder decodes instruction, uses control lines to ready CPU for execution (clocking data into registers, selecting ALU functions etc.)
Execute
- ALU executes instruction
- PC incremented
Boolean algebra
Boolean algebra is pretty straight forward, but there are a few rules that are handier than others:
Absorption Law – A AND (A OR ANYTHING) = A
A = AB + A = A(A + B) = A + ABC
2’s Complement is a way to represent negative numbers in binary. The number in the first position, also known as the most significant bit (MSB), is made to represent the negative value of what it would normally represent. This usually means -128, because you usually deal with 8 bits at a time, but it possible this could be changed for the sake of demonstration. When a number is in 2’s Complement form it is also known as signed.
When a number is in signed form, it must be treated differently in operations. When you operate on a signed number, you will sometimes get an answer which is inaccurate due to the carry conditions which have occurred.
Overflow Signed = X Unsigned = X |
Underflow Signed = X Unsigned = OK |
Carry Out Signed = OK Unsigned = X |
|
10000000 + 10000000 1 00000000 |
01000000 + 01000000 10000000 |
01000000 + 11000000 1 00000000 |
|
Signed |
-128+ -128
– 256
|
64+ 64
– 128 Wrong! |
64 + 192 – 64 Wrong! |
Unsigned |
128+ 128
256 |
64+ 64
128 Correct! |
64 + 192 256 |
Hamming Code and SECDED
This stuff can be really hard to understand at first, but the method below should hopefully make it easier to understand. So, Hamming code is a system for detecting if a message transmitted in binary has been corrupted in transmission. It can only detect and repair errors if they affect 1 bit, i.e. one bit is flipped (0->1,1->0). The way it does this is by interspersing a number of additional bits through the message, which check specific message bits. The number of added bits depends on the number of message bits. The formula to work out how many check bits you need is:
2^P >= M + P + 1
The table below will show you which bits check which:
Bit 12 |
Bit 11 |
Bit 10 |
Bit 9 |
Bit 8 |
Bit 7 |
Bit 6 |
Bit 5 |
Bit 4 |
Bit 3 |
Bit 2 |
Bit 1 |
BITS |
M8 |
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
Order |
X |
X |
X |
X |
X |
O |
<– C1 |
||||||
X |
X |
X |
X |
X |
O |
<– C2 |
||||||
X |
X |
X |
X |
O |
<– C3 |
|||||||
X |
X |
X |
X |
O |
<– C4 |
The example above is done right-to-left, because that’s how I learnt, but it works exactly the same left-to-right.
Each bit is checked by a unique combination of check bits, so that you can tell which bit has changed. You know if a bit has changed if, when you add up all the bits it checks it should be an odd or even number, depending on if you’re working with odd or even parity.
Until Next Time,
Nitemice
Related articles
- Crammer’s Guide – Y01S01: Maths for Computing (nitemice.com)
- Crammer’s Guide – Y01S01: Java Programming 1 (nitemice.com)
- Crammer’s Guide – Y01S01: Database Theory (nitemice.com)
Pingback: Crammer’s Guide – Y01S02: Network Technologies | Nitemice
Pingback: Crammer’s Guide – Y01S01: Java Programming 1 | Nitemice
Pingback: Crammer’s Guide – Y01S01: Database Theory | Nitemice
Pingback: Crammer’s Guide – Y01S02: Java Programming 2 | Nitemice