Study guide: Data Storage and Processing

📋 Course Outline

1. Course Goals and Structure
2. Algorithms and Problem Solving
3. Abstraction and Black Boxes
4. Bits and Boolean Circuits
5. Working Memory and Capacity
6. Mass Storage Technologies
7. Representing Text and Media
8. Binary Numbers and Precision
9. Data Compression
10. CPU and Computer Architecture
11. Machine Language and Instructions
12. Program Execution Cycle
13. Peripheral Devices and Data Transfer

📖 1. Course Goals and Structure

🔑 Key Concepts & Definitions

• Information system: A sociotechnical system that collects, processes, and stores data and provides users with information.
• Business informatics: The study of how information systems can support the management of organizations and the performance of their activities.

📝 Essential Points

• The course has a theory part during the first three teaching weeks and a programming part delivered in guided sessions using Python in Dodona.

• The evaluation consists of two non-period programming tests worth 2/20, a period theory exam worth 12.6/20, and a period practical test worth 5.4/20.

📖 2. Algorithms and Problem Solving

🔑 Key Concepts & Definitions

• Algorithm: A general solution for a type of problem, expressed as an unambiguous sequence of executable instructions that transforms well-described input into output.
• Program: An algorithm represented in a form that a computer can execute.
• Software: The collective term for programs and the algorithms they represent.

📝 Essential Points

• Euclid’s algorithm finds the greatest common divisor by repeatedly dividing the larger value by the smaller, replacing the pair with the smaller value and the remainder, and stopping when the remainder is zero; the last nonzero divisor is the GCD.

💡 Memory Hook

Follow the path from input, through instructions, to output.

📖 3. Abstraction and Black Boxes

🔑 Key Concepts & Definitions

• Abstraction: A way to show a system’s external properties while hiding its internal operation and structure, separating essential features from details relative to a goal.

★ Must-know

📌 A computer can solve only problem types for which an executable algorithm can be found; without an algorithm, the computer cannot solve the problem.

Further detail

• In an algorithm, the solution-finding intelligence is embodied in the instructions, so the computer can execute them without understanding why they solve the problem.

💡 Memory Hook

The black box exposes external behavior while hiding internal structure.

📖 4. Bits and Boolean Circuits

🔑 Key Concepts & Definitions

• Bit: A binary digit with value 0 or 1 and a symbol used in computing for representing data.
• Boolean algebra: A mathematical theory of operations on Boolean values such as true and false, which can be represented as 1 and 0.
• Flip-flop: A circuit built from gates that stores one bit and has two input lines and one output line.

📝 Essential Points

• Binary uses base 2, whereas the decimal numeral system uses base 10.

• ASCII represents the exclamation mark with the bit pattern 00100001.

• The operators covered are:
  • AND
  • XOR
  • NOT
  • inclusive OR

📖 5. Working Memory and Capacity

🔑 Key Concepts & Definitions

• Byte: A group of eight bits stored in a memory cell with a unique address.

★ Must-know

📌 A memory cell’s address identifies where data is stored, whereas the cell’s contents are the bit pattern stored there.

📌 CPU registers and cache are very small and fast memory on or in the CPU, RAM temporarily stores programs and data in current use, and SSDs or hard disks permanently store files and programs.

Further detail

📌 Endianness describes the order in which the bits or bytes of a multi-part value are arranged; big-endian and little-endian are alternative arrangements.

• A 16-bit pattern can be stored in two consecutive memory cells of eight bits each.

• A nibble is 4 bits, a byte is 8 bits, and a byte can be written as two hexadecimal digits.

• Decimal storage units use 1 KB = 1,000 bytes, 1 MB = 1,000,000 bytes, 1 GB = 1,000,000,000 bytes, and 1 TB = 1,000,000,000,000 bytes.

• Binary units use powers of 2: 1 KiB is 1,024 bytes, 1 MiB is 1,048,576 bytes, and 1 GiB is 1,073,741,824 bytes.

📖 6. Mass Storage Technologies

🔑 Key Concepts & Definitions

• Flash memory: Non-volatile mass storage without moving mechanical components that supports random access and can be damaged by frequent rewriting.

★ Must-know

📌 Working memory is typically volatile, whereas mass storage is non-volatile, usually has greater total capacity and lower cost per stored bit, and is often removable or exchangeable.

Further detail

• Mechanical disk access time can include:
  • Head-seek time
  • Rotational latency
  • Data-transfer time

• Magnetic disk tracks are concentric, and formatting lays down tracks and sectors.

• A CD stores about 700 MB, a DVD stores several gigabytes, and a Blu-ray disk can store about five times as much as a DVD.

📖 7. Representing Text and Media

🔑 Key Concepts & Definitions

• Bitmap: A sequence of bits that encodes an image’s pixels; an uncompressed black-and-white image uses one bit per pixel.

📝 Essential Points

• ASCII uses 7 bits and can represent 128 patterns, while the course describes Unicode as using 16 bits for 65,536 patterns.

• A common color-image representation uses three bytes per pixel for red, green, and blue intensity.

• Digital audio can be sampled 44,100 times per second, and each sample can be stored with 16 bits.

• One minute of uncompressed 44,100-sample-per-second, 16-bit stereo audio requires 60 × 44,100 × 16 × 2 = 84,672,000 bits, or about 10 MB.

📖 8. Binary Numbers and Precision

🔑 Key Concepts & Definitions

• Two’s complement: A representation of signed integers using a fixed number of bits, with the most significant bit indicating the sign.
• Floating-point notation: A representation that divides a fixed-width bit pattern into a mantissa, an exponent, and a sign bit; the exponent specifies the radix-point position using excess notation.

★ Must-know

• 🔄 Convert a positive decimal integer to binary by:
  1. Divide the integer by 2 and record the remainder.
  2. Continue dividing the quotient by 2 and recording remainders until the quotient is 0.
  3. Read the remainders from last to first.

Further detail

• With 32-bit two’s-complement notation, the representable range is −2,147,483,648 to 2,147,483,647.

• 🔄 Negate a value by:

  1. Complement all bits.
  2. Add 1.
  3. Keep the same fixed bit width.

• In the course’s eight-bit floating-point example, 2.75 is represented as 01101011.

• The course’s single-precision format uses 32 bits: 1 sign bit, 8 exponent bits, and 23 mantissa bits.

📖 9. Data Compression

🔑 Key Concepts & Definitions

• Compression: A reduction in the storage space required for data; lossless compression preserves all information, whereas lossy compression discards some information.
• Run-length encoding: Run-length encoding compresses repeated symbols by recording the symbol and its repetition count, as in xxxxxxxyyxxyyy becoming 7x2y2x3y.

📝 Essential Points

• ZIP files, FLAC, and PNG are examples of lossless compression, whereas MP3 and MP4 are examples of lossy compression.

• Dictionary encoding stores a catalog of frequent longer patterns and then refers to those patterns rather than repeating them.

• Lossy compression can exploit perceptual properties, such as reducing blue-image detail, compressing high sound frequencies more, or avoiding duplicate video regions that remain nearly unchanged.

💡 Memory Hook

Lossless compression preserves information; lossy compression sacrifices some information.

📖 10. CPU and Computer Architecture

🔑 Key Concepts & Definitions

• CPU: The Central Processing Unit contains circuits that process data and coordinate the computer’s operations.
• Arithmetic/Logic Unit: The unit that performs mathematical and logical operations on data.
• Control Unit: The unit that coordinates the activities of the computer.
• Register: A memory cell used to store data temporarily while it is being processed.
• Bus: A collection of connections that transfers bit patterns between the CPU and working memory.
• Von Neumann architecture: An architecture that stores programs in working memory in the same way as data, allowing a computer to be programmed and enabling programs to be treated as data.

📝 Essential Points

📌 Reading copies data from working memory to the CPU using a memory-cell address and a read signal, whereas writing transfers data from the CPU to working memory using an address and a write signal.

📖 11. Machine Language and Instructions

🔑 Key Concepts & Definitions

• Machine instruction: An instruction encoded as a bit pattern that a CPU can recognize and execute.
• Machine language: The set of machine-instruction types recognized by a CPU.

★ Must-know

📌 RISC defines a small set of simple, fast, and efficient instructions, whereas CISC defines a larger set of more complex and powerful instructions.

Further detail

• Machine instructions include:

  • Data transfer, such as LOAD and STORE
  • Arithmetic and logic, such as ADD and AND
  • Control, such as STOP and JUMP

• In the illustrative machine language, instructions are 2 bytes long and contain a 4-bit opcode followed by a 12-bit operand field.

📌 A LOAD instruction can copy the contents of a memory cell into a register, whereas another LOAD form can place a literal bit pattern directly into a register.

📖 12. Program Execution Cycle

🔑 Key Concepts & Definitions

• Program counter: A control-unit register that holds the address of the next instruction to be executed.
• Instruction register: The register that holds the bit pattern of the instruction currently being executed.

★ Must-know

• The machine cycle repeatedly fetches one machine instruction, decodes it, and executes it; execution then returns to fetching the next instruction unless a jump changes the sequence.

Further detail

• In the illustrative machine, each instruction is 16 bits and occupies two consecutive 8-bit memory cells, so the program counter increases by 2 for each sequential instruction.

• Clock speed is measured in hertz, with one hertz corresponding to one machine cycle per second; computer clock speeds are commonly in the range of one to several gigahertz.

💡 Memory Hook

The CPU repeatedly fetches, decodes, and executes an instruction.

📖 13. Peripheral Devices and Data Transfer

🔑 Key Concepts & Definitions

• Controller: A component that connects the CPU or memory bus to a peripheral, responds to addressed commands, and can place data on the bus.
• USB: A standard for communication with peripherals, with the USB controller translating between internal computer signals and USB signals.

★ Must-know

📌 I/O addressing uses special addresses or machine instructions for peripherals, whereas memory-mapped I/O assigns controller registers addresses in the same address space as memory so the CPU can use ordinary LOAD and STORE instructions.

• With Direct Memory Access, the CPU gives a controller the source location, destination, and transfer size, after which the controller transfers data directly between a peripheral and RAM while the CPU can do other work.

Further detail

• Because multiple components share a bus, hardware coordinates access so that only one component sends data over it at a time.

📊 Synthesis Tables

Memory and Storage Roles