Flashcards for Data Representation and Basic Computer Organization (Lecture Notes)
Floating-Point Representation
Floating-point representation consists of two parts: mantissa (a signed fixed-point number) and exponent (which designates the radix point position).
General form: N = m \, r^{e} where
m = mantissa (fixed-point, can be fraction or integer, signed)
e = exponent (position of the radix point)
r = radix/base (e.g., 10 for decimal, 2 for binary)
Decimal example (finite-precision floating-point with a fraction and an exponent):
Given: Fraction = +0.6132789, Exponent = +04
Value: N = (+0.6132789) \times 10^{+4} = +6132.789\, (decimal)
Equivalently: +0.6132789 \times 10^{4} = +0.6132789 \times 10^{4}
The representation is equivalent to scientific notation m \times 10^{e} with the mantissa m and exponent e stored in the register (signs included). The radix r and the radix-point position of the mantissa are assumed by convention.
Binary floating-point (base 2) uses exponent base 2 and a binary mantissa.
Example: binary number +1001.11 is represented with an 8-bit fraction and a 6-bit exponent:
Fraction: 01001110
Exponent: 000100 (which equals +4)
The value is equivalent to m \times 2^{e} = (+.1001110) \times 2^{+4} (the binary point of the fraction follows the sign bit but is not shown in the register).
Normalization of floating-point numbers
A number is normalized if the most significant digit of the mantissa is nonzero (for binary, the leftmost bit of m is 1).
Example: decimal 350 is normalized; 00035 is not (leading zeros).
In binary, 8-bit 00011010 is not normalized because of three leading zeros. It can be normalized by shifting left 3 positions to obtain 11010000; to keep the same value, subtract 3 from the exponent (to compensate for the shift).
Normalized numbers provide the maximum possible precision.
Zero cannot be normalized because it lacks a nonzero digit; usually represented by all zeros in mantissa and exponent.
Notes on floating-point arithmetic
Arithmetic on floating-point numbers is more complex and slower than fixed-point arithmetic due to scaling/normalization, but is essential for scientific computations because of wide dynamic range.
Most computers/calculators have built-in floating-point arithmetic; others use software libraries or subroutines.
Other Binary Codes (Binary Encodings)
Gray code
A reflected binary code where adjacent values differ in only one bit, reducing ambiguity during transitions.
Advantage: only a single bit changes between successive numbers, which reduces misreadings when sensing position or analog-to-digital conversion transitions.
Uses: e.g., shaft position encoding where adjacent segments map to adjacent Gray codes to minimize ambiguity around segment boundaries.
Gray code table (4-bit example) maps to decimal values 0–15 with a single-bit change between successive codes. See the table:
0000 -> 0, 0001 -> 1, 0011 -> 2, 0010 -> 3, 0110 -> 4, 0111 -> 5, 0101 -> 6, 0100 -> 7, 1100 -> 8, 1101 -> 9, 1111 -> 10, 1110 -> 11, 1010 -> 12, 1011 -> 13, 1001 -> 14, 1000 -> 15.
Gray-code counters: flip-flops go through the states in the sequence given by Gray code; only one bit changes at a time during transitions.
Other decimal codes (binary-coded decimal and variants)
BCD (8421, weighted) code: each decimal digit is represented by 4 bits, adding weights 8-4-2-1 to form the digit value. Example: 7 is 0111, 5 is 0101, etc. BCD allows straightforward decimal interpretation but can complicate certain arithmetic operations.
2421 code (weighted, self-complementing in some cases): weights 2-4-2-1 that map to decimal digits. It is self-complementing in certain forms, which simplifies computing 9’s complements for signed arithmetic.
Excess-3 code: decimal digit encoded by BCD plus 3 (0011); unweighted code that raises the digit by 3 to avoid negative combinations in some hardware representations.
Gray-coded decimal (excess-3 Gray): a Gray code representation adjusted to decimal digits to improve certain transition properties for decimal data.
Other alphanumeric codes
ASCII: standard 7-bit code for characters; typically transmitted with parity bit, giving 128 characters total (95 graphic characters, 23 format effects, and 10 control-like characters).
EBCDIC: IBM Extended BCD Interchange Code; uses 8 bits per character (plus a parity bit); the bit assignment differs from ASCII but covers the same character set for internal processing.
6-bit alphanumeric codes: compact representation for internal data-processing needs (64 chars: 26 uppercase letters, 10 digits, and up to 28 symbols). Fewer bits save memory at the cost of a smaller character set.
Error Detection Codes
Parity bit (simple error-detection code)
An extra bit appended to a binary message to make the total number of 1’s either odd or even.
Parity types:
P(odd): makes the total number of 1’s odd.
P(even): makes the total number of 1’s even.
Handling during transfer:
Parity bit is generated at the sender, transmitted with the message, and checked at the receiver.
An error is detected if the received parity does not match the chosen parity rule (odd/even).
Parity detects odd numbers of errors (1, 3, 5, …); it cannot detect an even number of errors.
Implementation notes:
Parity generator and parity checker can be built from exclusive-OR (XOR) networks.
For odd parity, the checker’s output is inverted when needed to reflect the odd/even convention.
Practical notes
The parity logic can be designed so that the same circuit can be used both for parity generation and checking by fixing one input (e.g., tying a bit) as needed.
Problems (practice exercises in the text)
A series of exercises (e.g., 3-1 through 3-26) covers converting numbers between bases, computing complements, examining Gray codes, and constructing parity circuits.
4-1 to 4-7: Register Transfer and Microoperations
Key ideas
A digital computer is composed of registers connected by one or more buses; microoperations are elementary operations on data stored in registers.
Register transfer language (RTL) is a symbolic notation to describe microoperation sequences and the control signals that drive them.
Replacement operator: R2 ← R1 denotes transferring content from R1 to R2, leaving R1 unchanged.
A control function (Boolean variable) P may gate a transfer: P: R2 ← R1 (the transfer occurs if P = 1).
Registers and representation
Registers are named (e.g., MAR, PC, IR, R1, R2) with bit-level internal structure shown in diagrams (e.g., 16-bit PC with high/low bytes sometimes labeled PC(H) and PC(L)).
Bit numbering: the rightmost bit is 0, increasing to the left.
Bus and data transfer basics
A common bus reduces wiring complexity by multiplexing several registers onto a shared set of lines. Data from the selected register is placed on the bus, and destination registers load from the bus when their load input is enabled.
A typical bus uses multiplexers (MUX) to select which source register feeds the bus. A 4×1 MUX with 4 inputs (one per register) per bit line is illustrated in the text (for 4-bit example, generalized to n bits).
Selection lines (S1, S0, etc.) choose which register drives the bus; a function table maps bit patterns to the selected register.
Bus of four registers example
With 4 registers A, B, C, D and 4-bit width, the bus uses four 4×1 multiplexers; each MUX chooses one bit-position across the registers.
A common 4-bit bus can be implemented with a three-bit decoder and three-state buffers (see below).
Three-state bus buffers
A three-state buffer has an enable/control input. When enabled, the buffer outputs the input; when disabled, the output goes to a high-impedance state (Z).
Only one buffer may drive the bus at a time to avoid bus contention.
A decoder can ensure that only one buffer is enabled at a time by decoding a single 4-to-1 select value.
Three-state buffers can replace multiplexers in a bus, providing a distinct way to realize bus arbitration.
Memory transfer on a bus
Read: DR ← M[AR] (data from memory word at address AR loaded into DR)
Write: M[AR] ← DR (memory word at AR gets data from DR)
Addressing via a memory address register (AR) feeds the memory address bus
The bus system can also connect to memory data inputs/outputs to facilitate read/write cycles.
4-3: Bus and Memory Transfers (summary)
A common bus with 4 lines can support 4 registers feeding the bus via multiplexers; selection lines choose the source.
The bus can be used to transfer data to memory by driving the bus to memory’s data input during a write cycle, and to load a destination register from memory via DR/M[AR] and AR as the memory address.
4-4 to 4-7: Arithmetic, Logic, and Shift Microoperations / ALU
4-4 Arithmetic microoperations
A set of microoperations can be implemented with a parallel adder (binary adder) and associated circuits.
The basic arithmetic microop uses the form: D = A + Y + Cin, where A and Y are 4-bit (or n-bit) inputs and Cin is the input carry.
A 4-bit adder is built from four full-adders cascaded; input carry C0 enters the least-significant full-adder; the carries propagate to the next full-adder, producing sum bits S0–S3 and final carry C4.
Example: binary addition of A and B (with Cin) can be implemented; the sum can be stored in a destination register, possibly replacing one of the inputs.
4-4 Arithmetic circuit (example) and microoperation table
An arithmetic circuit diagram (Fig. 4-9) shows four full-adders plus MUXes to select inputs for Y and the carry in. The sum output D is produced by the adder and can be routed to a destination register.
The arithmetic circuit table (Table 4-4) lists the eight arithmetic operations (Add, Add with carry, Subtract with borrow, Subtract with borrow + carry, Increment, Decrement, Transfer A, and Transfer A with A unchanged) with the corresponding selector settings (S1, S0, Cin, etc.).
Subtraction is implemented via two’s-complement technique: A − B ≡ A + (¬B) + 1. The adder-subtractor can be configured with a mode input M to select addition or subtraction, and an exclusive-OR gate with B's inputs can implement the complement when necessary (Fig. 4-7).
4-5 Logic microoperations
Logic microoperations operate on bit strings in registers, treating each bit as a binary variable.
Common operators mapped to microoperations include: AND, OR, XOR, complement, and combinations.
The 16 possible two-variable boolean functions (F0–F15) define the set of logic microoperations. Each function corresponds to a specific bitwise operation on registers A and B (A's bit i, B's bit i).
A typical one-stage logic circuit uses a 4×1 MUX to select between logic results (AND, OR, XOR, Complement) bitwise per bit position, controlled by selection lines.
4-6 Shift microoperations
Shifts are used for serial data transfer and for arithmetic/bit-manipulation tasks.
Types of shifts:
Logical shift left (shl): inserts 0 at the least-significant bit; bits shift left, LSB is dropped; represented as R ← shl R.
Logical shift right (shr): inserts 0 at the most-significant bit; bits shift right.
Circular shift left (ciL): rotate left; LSB moves to MSB.
Circular shift right (cir): rotate right; MSB moves to LSB.
Arithmetic shift left (ashl): same as logical shift left for magnitude, but preserves sign bits if implemented in a broader ALU context.
Arithmetic shift right (ashr): preserves the sign bit while shifting; sign bit (leftmost bit) is maintained.
Symbolic designations: shl, shr, cil, cir, ashl, ash r.
A combinational shifter can be built with multiplexers and serial inputs; a bi-directional shifter can be part of an ALU.
4-7 Arithmetic Logic Shift Unit (ALU)
A central unit (ALU) combines arithmetic, logic, and shift operations by feeding appropriate inputs from registers to a common unit and selecting the operation with control signals.
One stage of the ALU uses an input X (A input), Y (B input or complemented B depending on operation), a carry input C_in, and 5 control signals to select: arithmetic operation (A + Y + Cin), logic operation (A op B, where op ∈ {AND, OR, XOR, etc.}), and shift operations (shr/shl). The stage output feeds into the destination register.
An n-bit ALU would replicate the stage n times, with the carry output of stage i feeding the input carry of stage i+1.
The 14 (or 16) operations of Table 4-8/5-xx include eight arithmetic operations, four logic operations, and two shifts; a 4×1 MUX selects which operation's result gets written.
Hardware considerations and design notes
The ALU is frequently centralized; the same unit handles arithmetic, logic, and partial shifts for multiple registers.
The integrative ALU design reduces latency by allowing simultaneous bus data to feed AC via the ALU within a single clock cycle, controlled by the function table and carry signals.
Chapter Five: Basic Computer Organization and Design
5-1 Instruction codes and the stored-program concept
A computer is defined by its internal organization of registers, the transfer of data between registers, and the instruction set that drives the machine.
A program is a sequence of instructions that specify operations, operands, and their order; instructions and data reside in memory.
The stored-program concept: programs stored in memory can be executed by the computer; a program is read, decoded, and executed by a control unit, with microoperations issued to hardware.
An instruction code is typically divided into parts: an operation code (opcode) and operand/address information; the number of bits in each field depends on the machine width and the number of operations supported.
Example: a computer with 64 distinct operations might use a 6-bit opcode; the remainder of the word encodes memory addresses or registers as operands.
5-1 Stored Program Organization (example architecture)
A simple architecture stores both program and data in memory, uses a PC (program counter) to fetch instructions in sequence, and uses a memory address register (AR) to address memory during fetch/execute.
Typical memory: 4096 words × 16 bits; addresses require 12 bits (2^12 = 4096).
If an instruction word is 16 bits, 4 bits can specify the opcode and 12 bits specify the address; the I bit distinguishes direct vs indirect addressing.
Example: Direct addressing uses the address field as the location of the operand; indirect addressing uses the address field to point to memory that stores the actual address of the operand.
5-2 Computer registers
Registers used in the basic computer example (from the memory/register bus model):
DR (data register, 16 bits): holds memory operand
AR (address register, 12 bits but extended to 16 bits in bus): holds memory address
AC (accumulator, 16 bits): main processing register
IR (instruction register, 16 bits): holds current instruction
PC (program counter, 12 bits but extended to 16 on the bus): holds address of next instruction
TR (temporary register, 16 bits): holds temporary data
INPR (input register, 8 bits): holds input character
OUTR (output register, 8 bits): holds output character
The memory unit contains 4096 words × 16 bits.
AR and PC are 12-bit registers for addressing memory; when their values are placed on the common bus, their upper bits are zeroed; when loaded from the bus, only the 12 least-significant bits are transferred.
5-3 Computer instructions and formats
Three instruction formats exist in the basic computer:
Memory-reference instructions: use 12-bit address part and I mode bit; the opcode is encoded with 3 bits (plus the I bit yields 4 bits in the first nibble of the instruction). Indirect addressing uses I = 1 (first nibble ranges 8–E).
Register-reference instructions: use 16 bits with the leftmost nibble 0111 (hex 7) indicating a register-reference instruction; the remaining 12 bits specify the operation on AC/E or tests.
Input-output instructions: use 16 bits with the leftmost nibble 1111 (hex F); the remaining 12 bits specify I/O operations or tests.
The set of instructions (Table 5-2) includes AND, ADD, LDA, STA, BUN, BSA, ISZ, CLA, CLE, CMA, CME, CIR, CIL, INC, SPA, SNA, SZA, SZE, HLT, INP, OUT, SKI, SKO, ION, and !OF, with corresponding hexadecimal opcodes.
Examples:
AND M to AC: opcode 0 or 8
ADD M to AC (carry to E): opcode 1 or 9
LDA: 2 or A (load AC from M)
STA: 3 or B (store AC into M)
BUN (branch unconditionally): 4 or C
BSA (branch and save return address): 5 or D
ISZ (increment and skip if zero): 6 or E
CLA (clear AC): 7800, etc.
5-4 Timing and Control (hardwired vs microprogrammed)
Two major control organizations exist:
Hardwired control: control logic implemented with gates/decoders; fast but harder to modify.
Microprogrammed control: control memory stores microinstructions (control memory) that define the sequence of microoperations; easier to modify and extend.
The basic hardwired control for the basic computer uses an instruction register (IR) split into fields: I bit, opcode (bits 12–14), and operand bits 0–11; an operation decoder (3×8) decodes opcodes; a sequence counter (SC, 4 bits) and a timing decoder (4×16) generate timing signals T0–T15.
5-5 Instruction cycle (Fetch-Decode-Execute)
The basic instruction cycle consists of fetch, decode, and execute phases; the cycle repeats for each instruction until a HALT is encountered.
Fetch/decode phases use timing signals T0–T2 to move values between PC, AR, IR, and memory; decode assigns the outputs Do…D7 from IR(12–14) to select the next address path; AR gets IR(0–11); I bit is captured in a flip-flop I.
The execute phase uses T3 and beyond (T4, T5, …) to perform the required microoperations depending on the instruction type (memory-reference, register-reference, or I/O).
Indirect addressing requires an additional memory reference to fetch the effective address: e.g., AR ← M[AR].
5-6 Memory-reference instructions and microoperations
For each memory-reference instruction, a precise sequence of microoperations is defined (e.g., AND, ADD, LDA, STA, BUN, BSA, ISZ).
Example microoperations (illustrative):
AND: T4: DR ← M[AR], T5: AC ← AC ∧ DR, SC ← 0
ADD: T4: DR ← M[AR], T5: AC ← AC + DR, E ← C4, SC ← 0
LDA: T4: DR ← M[AR], T5: AC ← DR, SC ← 0
STA: T4: M[AR] ← AC, SC ← 0
BUN: T4: PC ← AR, SC ← 0
BSA: (two-step) T4: M[AR] ← PC, AR ← AR + 1; T5: PC ← AR, SC ← 0
ISZ: T4: DR ← M[AR], T5: DR ← DR + 1, T6: M[AR] ← DR, if DR = 0 then PC ← PC + 1, SC ← 0
5-7 Input-Output and Interrupt
Input (INP) and Output (OUT) instructions move data between AC and I/O devices via INPR and OUTR registers; flags FGI and FGO synchronize with the peripheral interface.
Skips (SKI, SKO) conditionally branch based on input/output flags; ION and !OF enable/disable interrupts; an interrupt cycle stores a return address and jumps to an I/O service routine; interrupts can be enabled/disabled via ION and !OF.
Interrupt handling flow: an interrupt flip-flop R is set when an interrupt condition occurs and IEN = 1; if R = 1, the processor executes an interrupt sequence to store the return address, branch to an I/O service routine, and later return via an indirect branch.
5-8 Complete computer description
Hardware components:
Memory: 4096 words × 16 bits
Registers: AR, PC, DR, AC, IR, TR, OUTR, INPR, SC
Flip-flops: I, S, E, R, IEN, FGI, FGO
Decoders: 3×8 operation decoder, 4×16 timing decoder
16-bit common bus, control logic gates, adder and logic circuit connected to AC
The bus-connectivity and control gating are designed so that any register can place its value on the bus and any destination register can load from the bus in a given clock cycle.
The control unit uses a decoder-based approach to generate the 16 timing signals (T0–T15) and the microoperations associated with each instruction path.
5-9 Design of Basic Computer (summary)
The complete design includes:
A memory unit, nine registers, seven flip-flops, two decoders, a 16-bit common bus, control logic gates, and an ALU connected to AC.
Control logic gates derive from the register-transfer statements; the encoder/decoder structure translates bus select signals into the proper register selections.
5-10 Design of Accumulator Logic
Accumulator logic (AC) requires an adder/logic circuit and gating for LD, INR, and CLR.
Control signals derived from the instruction set generate the micro-operations to:
Load AC (AC ← …), clear AC (AC ← 0), increment AC, complement AC, shift AC (shr/shl), and perform arithmetic operations with DR or INPR inputs via the adder/logic circuit.
The accumulator’s adder/logic circuit includes inputs from AC, DR, and INPR; the outputs are routed to AC. The carry/extended bit E is updated during addition.
The gate structure for AC control is derived from the set of microoperations (the rX signals and p signals that indicate a particular operation in a given timing step).
5-9 Design of the complete controller (brief)
Control gates compute LD/INR/CLR for each register, the read/write signals for memory, and the bus-select logic to route the correct data to the bus.
Chapter Six: Programming the Basic Computer
6-1–6-2 Introduction to machine language and machine-language encoding
A program is a sequence of binary instructions and operands that direct the computer to perform tasks.
Machine instructions can be represented in binary, octal, or hexadecimal; a translation from symbolic (assembly) to binary is done by an assembler.
6-2 Machine Language
The Basic Computer uses a fixed instruction set (25 total) that includes 7 memory-reference instructions and 18 register-reference / I/O instructions.
Memory-reference instructions encode opcode and a 12-bit address, with a mode bit I to distinguish direct vs indirect addressing.
Register-reference and I/O instructions use a 16-bit opcode; the leftmost nibble (for register-reference) is 7 (0x7), and I/O instructions use the leading nibble 0xF.
Example table (partial):
AND M to AC: opcode 0 or 8 (0x0/0x8), etc.
ADD M to AC, carry to E: 1 or 9 (0x1/0x9).
LDA: 2 or A (0x2/0xA).
STA: 3 or B (0x3/0xB).
BUN: 4 or C (0x4/0xC).
BSA: 5 or D (0x5/0xD).
ISZ: 6 or E (0x6/0xE).
CLA: 7800; CLE: 7400; CMA: 7200; CME: 7100; CIR: 7080; CIL: 7040; INC: 7020; SPA: 7010; SNA: 7008; SZA: 7004; SZE: 7002; HLT: 7001.
INP: F800; OUT: F400; SKI: F200; SKO: F100? (text shows SKO F000, FIOO, F080, F040). The key point: INP/OUT are I/O instructions; SKI/SKO skip tests; ION/!OF control interrupts.
6-3 Assembly language
Assembly language provides symbolic representations of machine-language instructions.
Rules of the language (typical): each line has three fields: label (optional), instruction, comment.
Symbolic addresses allow using labels in place of numeric addresses; labels are terminated with a comma in the label field.
Memory-reference instruction lines consist of an MRI mnemonic and an operand, while non-MRI (register-reference or I/O) instructions use a 16-bit encoding with a fixed format.
Pseudoinstructions (ORG, DEC, END) allow arranging code with symbolic addresses and decimal operands for readability and convenience.
6-4 Examples and programming approaches
Example: Binary program to add two numbers (Table 6-2) shows a sequence of binary words (addresses and opcodes) that implement an addition operation.
Hexadecimal representations (Table 6-3) condense the same program into 4-digit hex codes for compact representation.
Symbolic programs (Table 6-4) use mnemonic operation codes and explicit operands (e.g., LDA, ADD, STA, HLT) with hexadecimal addresses representing memory operands.
Assembly language example (Table 6-5) demonstrates an assembly-language program that adds two numbers (LDA A, ADD B, STA C, HLT) and comments to explain the operation.
6-5 Fortran example (Table 6-6)
Fortran source example: INTEGER A, DATA A,8 3 C=A+B END; demonstrates translating a high-level language into machine language via a compiler.
Key takeaways for exam preparation
Understand the relationship between mantissa, exponent, and base in floating-point representation; normalization and zero handling are crucial.
Know Gray code properties and why Gray codes are advantageous for digital sensors and position encoders.
Be comfortable with BCD, Excess-3, 2421, and other encodings, including their self-complementing properties and weighted codes.
Be able to describe error-detection parity bits, both odd and even parity, and how parity circuits use XOR logic.
Understand the RTL notation (R2 ← R1) and control function gating; know the purpose of a common bus and how multiplexers/three-state buffers implement the bus.
Recall the main components of the Basic Computer: memory (4096×16), registers (AR, PC, DR, AC, IR, TR, INPR, OUTR, SC), two decoders (3×8, 4×16), adder/logic, and a 16-bit common bus.
Recognize the three instruction formats (memory-reference, register-reference, I/O) and how fetch-decode-execute is implemented with timing signals T0–T15.
Remember the opcode map for the Basic Computer (memory-reference: AND/ADD/LDA/STA/BUN/BSA/ISZ; register-reference: CLA, CLE, CMA, CME, CIR, CIL, INC, SPA, SNA, SZA, SZE, HLT; I/O: INP, OUT, SKI, SKO, ION, !OF).
Appreciate the role of the interrupt mechanism (ION, !OF, FGI, FGO, interrupt flip-flop R) and the sequence for interrupt handling.
Useful formulas and schemas to memorize
Floating-point general form: N = m \times r^{e} with normalization: the most significant digit of m is nonzero; zero cannot be normalized.
Arithmetic in the 4-bit adder-subtractor (Table 4-4 summary):
Add: D = A + B + Cin (Cin may be 0 or 1)
Subtract with borrow: realized via two’s complement; subroutine uses D = A - B = A + (\overline{B}) + 1 when appropriate.
Logic microoperation core: there are 16 possible two-variable boolean functions; microoperations map to bitwise operations between registers.
ALU function mapping (Table 4-8 summary): eight arithmetic operations, four logic operations, two shifts; one stage combines A, B, and Cin via a multi-input selector to produce D.
References and themes
The materials emphasize a modular design approach: registers defined by their function, microoperation sequences, and a common bus to facilitate data transfers.
The content develops from data representation (binary/gray codes, encodings) to low-level hardware design (RTL and ALU) to machine organization and programming (instruction formats, fetch-decode-execute, and simple programming in machine/assembly/Fortran).