Comprehensive Study Notes for IGCSE/O Level Computer Science

DATA REPRESENTATION

Binary Number System

Modern computers use the binary number system (base 2) as their fundamental building block because they are made of millions of tiny electronic switches. These switches can only be in one of two states: ON (represented by 1) or OFF (represented by 0). Any data processed by a computer must be converted into binary format. A bit (binary digit) is the basic computing element, either 0 or 1.

Binary-Denary Conversions

Computers use binary, while humans use denary (base 10). To convert binary to denary, add the value of each column wherever a 1 appears. For a standard 8-bit byte, the column headings are powers of 2: $128, 64, 32, 16, 8, 4, 2, 1$ . For example, binary $11101110$ equals $128 + 64 + 32 + 8 + 4 + 2 = 238$ .

To convert denary to binary, two methods exist. Method 1 involves successive subtraction of the largest possible power of 2 from the number until 0 is reached. Method 2 involves successive division by 2, recording the remainders until the result is 0, and then reading the remainders in reverse order (bottom to top).

Hexadecimal Number System

Hexadecimal (base 16) is used by computer scientists because it is more convenient for humans to read, copy, and remember than long binary strings. It uses sixteen digits: 0-9 and letters A-F ( $A=10, B=11, C=12, D=13, E=14, F=15$ ). One hexadecimal digit represents exactly four binary digits (a nibble).

Common Uses of Hexadecimal:

Error Codes: Automatically generated messages referring to memory locations.
MAC Addresses: A Media Access Control address (e.g., $NN-NN-NN-DD-DD-DD$ ) uniquely identifies a device on a network.
IPv6 Addresses: 128-bit addresses used for IP, written in eight 16-bit chunks as hex.
HTML Colour Codes: Represented by 6 hex digits (#RRGGBB), allowing for $256 \times 256 \times 256 = 16,777,216$ possible colours.

Binary Operations and Shifts

Binary Addition

When adding 8-bit positive binary numbers, follow these rules:

$0 + 0 = 0$
$0 + 1 = 1$
$1 + 0 = 1$
$1 + 1 = 0 \text{ (carry 1)}$
$1 + 1 + 1 = 1 \text{ (carry 1)}$
If an addition generates a 9th bit, an overflow error has occurred, indicating the number is too big for the allocated word size (up to 255 for 8 bits).

Logical Binary Shifts

A logical shift moves bits left or right. Each left shift multiplies the number by 2; each right shift divides the number by 2. Empty positions are filled with 0. If a 1-bit is shifted out of the register, data is lost, causing an error.

Two’s Complement

This notation allows for negative integers. In an 8-bit system, the most significant bit (left-most) is changed from $128$ to $-128$ . The range is $-128$ to $+127$ . To find the binary of a negative number (e.g., $-67$ ), write the positive value ( $01000011$ ), invert all bits ( $10111100$ ), and add 1 ( $10111101$ ).

TEXT, SOUND, AND IMAGES

Text Representation

Computers recognize characters through character sets.

ASCII (American Standard Code for Information Interchange): Standard 7-bit code (0–127) representing English characters and control codes. Extended ASCII uses 8 bits (0–255).
Unicode: A universal standard representing all languages and writing systems (up to 4 bytes per character). The first 128 characters are identical to ASCII.

Sound Representation

Sound is analogue (continuous) and must be sampled via an Analogue-to-Digital Converter (ADC).

Sampling Resolution (Bit Depth): The number of bits per sample. Higher resolution results in better quality but larger files.
Sampling Rate: Number of samples taken per second, measured in hertz (Hz).
File size Calculation: $\text{sampling rate (Hz)} \times \text{sampling resolution (bits)} \times \text{length (s)} \times \text{channels}$ .

Image Representation

Bitmap images consist of a matrix of pixels (picture elements).

Colour Depth: Bits used to represent each pixel's colour (e.g., 24-bit depth permits 16.7 million colours).
Image Resolution: Number of pixels in the X-Y direction (e.g., $1024 \times 512$ ).
File size Calculation: $\text{image resolution (pixels)} \times \text{colour depth (bits)}$ .

DATA STORAGE AND COMPRESSION

Units of Storage

Bit: 1 or 0.
Byte: 8 bits.
Nibble: 4 bits.
IEC Units (Powers of 2): Kibibyte (KiB) = $2^{10}$ , Mebibyte (MiB) = $2^{20}$ , Gibibyte (GiB) = $2^{30}$ , Tebibyte (TiB) = $2^{40}$ .

File Compression

Compression is necessary to save storage space and reduce data transfer time (bandwidth usage).

Lossy Compression: Permanently removes unnecessary data (e.g., sounds humans can't hear in MP3s, or subtle colour changes in JPEGs). The original cannot be reconstructed.
Lossless Compression: No data is lost; the original is perfectly reconstructed.
Run-Length Encoding (RLE): A lossless method that encodes a string of identical, adjacent data items into two values: the count and the item code. For example, 'aaaaabbbb' becomes '05 97 04 98'.

DATA TRANSMISSION

Data Packets

Data sent over long distances is broken into packets (approx. 64 KiB).

Packet Structure: Includes a Header (IPs, sequence number, size), Payload (actual data), and Trailer (end marker and error check like CRC).
Packet Switching: Routers send packets independently along the shortest available paths. They are reassembled at the destination.

Transmission Methods

Direction: Simplex (one way), Half-duplex (both ways, not simultaneous), Full-duplex (both ways simultaneously).
Method: Serial (one bit at a time over one wire - reliable over distance) vs. Parallel (several bits at a time over several wires - fast but prone to skewing over distance).
USB (Universal Serial Bus): An industry standard for serial transmission. Features include automatic recognition of devices and device driver loading.

Error Detection Following Transmission

Parity Check: Uses a parity bit to ensure a byte has an even or odd number of 1s.
Parity Block: A matrix check (horizontal and vertical) that can identify and correct a single bit error.
Checksum: A calculated value sent with a block of data; the receiver recalculates and compares it.
Echo Check: Data is sent back to the sender for comparison (not highly reliable).
ARQ (Automatic Repeat Request): Uses acknowledgements and timeouts; if an error is detected or no reply is received, data is re-sent.
Check Digit: A data entry check (e.g., ISBN, barcodes) calculated from other digits to spot mis-typing.

Encryption

Encryption protects sensitive data by making it unintelligible to eavesdroppers.

Symmetric Encryption: Uses one secret key for both encryption and decryption.
Asymmetric Encryption: Uses a Public Key (available to all) to encrypt and a matching Private Key (kept by the user) to decrypt.

HARDWARE AND ARCHITECTURE

Von Neumann Architecture

John von Neumann developed the "stored program" computer concept. Components include:

Central Processing Unit (CPU): Executing all instructions.
Control Unit (CU): Manages data flow and instructions using the system clock.
Arithmetic & Logic Unit (ALU): Performs calculations and logical shifts.
Registers: Special purpose memories like PC (Program Counter), MAR (Memory Address Register), MDR (Memory Data Register), CIR (Current Instruction Register), and ACC (Accumulator).
Buses: Address Bus (unidirectional), Data Bus (bidirectional), Control Bus (bidirectional).

Fetch-Decode-Execute Cycle

Fetch: Address from PC copied to MAR; instruction from memory copied to MDR, then to CIR; PC incremented.
Decode: Instruction in CIR is interpreted.
Execute: CPU carries out the instruction.

Processing Performance

Factors that affect speed include:

Clock Speed: Number of cycles per second (GHz).
Cores: Multiple ALU/CU units (e.g., dual, quad).
Cache: High-speed Static RAM (SRAM) inside the CPU.
Bus Width: The number of bits a bus can transmit simultaneously.

Embedded Systems

A combination of hardware and software designed for a specific function (e.g., washing machines, vending machines). They often use microcontrollers (CPU, RAM, ROM on one chip).

Input and Output Devices

Input: Barcode/QR scanners, digital cameras, keyboards, microphones, optical mice, 2D/3D scanners, and touch screens (capacitive, resistive, or infrared).
Output: Actuators, light projectors (DLP/LCD), inkjet printers (thermal bubble/piezoelectric), laser printers (toner/static electricity), 3D printers, LED/LCD screens, and loudspeakers.
Sensors: Monitor and control environments (temperature, moisture, light, pH, accelerometer, etc.). Feedback occurs when sensor readings cause a microprocessor to act, which then changes future sensor readings.

Data Storage Technologies

Primary Memory: RAM (volatile, read/write) and ROM (non-volatile, read-only). RAM types include DRAM (needs refreshing) and SRAM (faster, no refreshing).
Secondary Storage: HDD (magnetic, uses spinning platters), SSD (solid state/NAND flash - faster, no moving parts), and Optical (CD, DVD, Blu-ray - uses lasers to read 'lands' and 'pits').
Virtual Memory: Using swap space on a hard drive when RAM is full. Can lead to disk thrashing.
Cloud Storage: Remote data storage on off-site servers.

SOFTWARE AND TRANSLATORS

Types of Software

System Software: Manages the hardware and provides a platform (Operating Systems, Utilities, Device Drivers, Translators).
Application Software: Performs specific user tasks (Spreadsheets, Word Processors, Databases, Video Editors).

Operating Systems (OS)

Key functions: HCI (Command Line Interface vs. Graphical User Interface), memory management, security management, file management, and multitasking. The BIOS (firmware) boots the system.

Interrupts: Signals from hardware or software requiring CPU attention (e.g., printer is out of paper).
Buffers: Temporary storage areas used to compensate for speed differences between devices.

Programming Languages and Translators

High-Level Languages (HLL): Problem-oriented, portable, and easier for humans to read (e.g., Python, Java).
Low-Level Languages (LLL): Architecture-specific. Includes Machine Code (binary) and Assembly Language (uses mnemonics like ADD/LDA).

Translators:

Compiler: Translates HLL to machine code all at once; produces an executable file.
Interpreter: Translates and executes HLL line-by-line; no executable file produced.
Assembler: Translates Assembly Language into machine code.

IDE (Integrated Development Environment): Software providing tools like code editors, debuggers, error diagnostics, and auto-completion to help programmers.

PROBLEM SOLVING AND PROGRAMMING

Algorithm Design

Abstraction: Discarding details not required for the solution.
Decomposition: Breaking a complex problem into smaller, solvable sub-problems.
Structure Diagrams: Hierarchical diagrams showing top-down design.

Validation and Verification

Validation: Automated checking that data is reasonable (Range check, Length check, Type check, Presence check, Format check).
Verification: Checking if data was accurately copied (Double entry, Visual check).

Standard Algorithm Methods

Linear Search: Inspects every item in a list in sequence.
Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order until the list is sorted.
Totalling/Counting: Keeping track of sums or occurrences within loops.

Programming Constructs

Sequence: Ordered steps.
Selection: IF-THEN-ELSE or CASE structures.
Iteration: FOR (count-controlled), WHILE (pre-condition), and REPEAT-UNTIL (post-condition) loops.
Arrays: Data structures holding multiple items of the same type, accessed by an index. Supports 1D and 2D formats.
Subroutines: Procedures (perform tasks) and Functions (perform tasks and return a value). Uses parameters and has variable scope (Local vs. Global).

DATABASES AND LOGIC

Databases

A structured collection of data in tables, comprised of records (rows) and fields (columns). A Primary Key uniquely identifies each record.

SQL (Structured Query Language)

Standard language for querying databases:

SELECT: Choose fields.
FROM: Choose table.
WHERE: Apply conditions using operators like =, >, <, <>, AND, OR, LIKE.
ORDER BY: Sort results.
SUM/COUNT: Aggregate calculations.

Boolean Logic

Logic Gates and Truth Tables:

NOT: Inverts input ( $X = \text{NOT } A$ ).
AND: Output 1 only if all inputs are 1 ( $X = A \cdot B$ ).
OR: Output 1 if any input is 1 ( $X = A + B$ ).
NAND: NOT AND ( $X = \overline{A \cdot B}$ ).
NOR: NOT OR ( $X = \overline{A + B}$ ).
XOR: Output 1 only if inputs are different ( $X = (A \cdot \overline{B}) + (\overline{A} \cdot B)$ ).

Text Representation

Computers recognize characters through character sets:

ASCII (American Standard Code for Information Interchange): Standard 7-bit code (0–127) representing English characters and control codes. Extended ASCII uses 8 bits (0–255), allowing for additional characters.
Unicode: A universal character encoding standard that represents text and symbols from all languages and writing systems. It can use up to 4 bytes per character. The first 128 characters of Unicode are identical to ASCII, making it backward-compatible.

Sound Representation

Sound must be digitized for computers to process it; this involves sampling the continuous analogue signal via an Analogue-to-Digital Converter (ADC):

Sampling Resolution (Bit Depth): This is the number of bits allotted to each sample. A higher bit depth means better sound quality because it allows for finer distinctions between volume levels. Typical bit depths: 16-bit (CD quality) or 24-bit (professional audio).
Sampling Rate: This indicates how many samples of the audio are taken per second, measured in hertz (Hz). Common rates are 44.1 kHz for CDs and up to 192 kHz for high-resolution audio.
File Size Calculation: The size of a digital audio file can be calculated by the formula:
$ext{File Size} = ext{sampling rate (Hz)} imes ext{sampling resolution (bits)} imes ext{length (s)} imes ext{channels}$
This formula accounts for all aspects of the audio file, including length in seconds and number of channels (e.g., stereo has 2 channels).

Image Representation

Images are represented via bitmap format, consisting of a grid of pixels (picture elements):

Colour Depth: This refers to the number of bits used to represent each pixel's colour. A common colour depth is 24 bits (8 bits for each RGB component), which allows for $2^{24}$ (16.7 million) different colours.
Image Resolution: This defines the total number of pixels in the image, often described by width and height in pixels (e.g., $1024 imes 512$ ). A higher resolution means more detail but also results in a larger file size.
File Size Calculation: The total file size can be calculated using:
$ext{File Size} = ext{image resolution (pixels)} imes ext{colour depth (bits)} imes \frac{1}{8}$
(the division by 8 converts bits to bytes).

Understanding text, sound, and image representation is critical as these elements form the basis of all digital content. Efficiently managing these formats allows for better data storage, processing, and transmission. Collectively, they showcase the versatility of modern computing in handling various types of data.