Data Representation and Storage

Data Storage

• This chapter explores bit operations, data representation, and data storage on computers
• The types of data examined include text, numbers, images, audio, and video
• Methods for reliable data storage and economical storage use are needed

CS Curriculum 2023: Architecture and Organization (AR) Knowledge Units:

• Digital logic and digital systems cover combinational/sequential logic, register transfer, hardware description languages, SoC design, and physical constraints
• Machine-level data representation includes computer architecture overview, bits, bytes, unsigned/signed integers, two's complement, numerical/non-numerical data representation, records, arrays, and UTF data types
• Memory hierarchy encompasses memory hierarchy structure, primary storage configuration/operation, SSD/HDD, latency, cycle time bandwidth, interleaving, cache memory, virtual memory, error coding, and data compression

Learning Objectives:

• Apply Boolean logic
• Describe the operation of gates and flip-flops
• Represent information using bit patterns
• Describe how to store integers and fractions
• Describe how to compress data
• Detect data communication errors

Learning Content

• Storage of bits
• Primary Storage / Mass Storage
• Information representation using bit patterns
• Binary system
• Storing integers and fractions
• Data compression
• Communication errors

Computer System Hierarchy

• A computer system is structured in layers

Computer Hardware Components:

• Include the CPU, cache memory, RAM memory, disk, network, MMU, DMAC, keyboard, mouse, display, hard disk, printer, and a network device

Bit Storage

• Data/information is expressed as 0s and 1s in binary form. These are referred to as bits (binary digits)
• Numbers, characters (Hangul, alphabets, special characters), images, sounds, etc. are represented as bit patterns
• Bit pattern systems consist of binary, octal, hexadecimal, BCD, ASCII, and Unicode

Boolean Operations:

• Fundamental logic operations like AND, OR, and XOR are used
• Boolean operations have applications in digital circuit design, database searching, search engines, and software algorithms

Logic Gates:

• Logic gates are electronic devices that implement Boolean operations
• Transistors and resistors implement this function
• Represented by voltage levels of "0" and "1" for input values
• Serve as basic units when designing digital circuits

Flip-Flops:

• Flip-flops act as the fundamental unit of computer memory
• Holding either a 0 or 1 as output value, the circuit maintains this value until a pulse signal is received to change it
• They act as the fundamental element of registers and cache memory (SRAM)

Method to make a Flip-Flop Output 1:

• By applying a 1 to the upper input
• This causes the OR gate's output to become 1
• This output makes the AND gate also output 1
• Even if the original upper input reverts to 0, the OR gate continues to maintain output 1

Primary Storage (Memory)

• Primary storage (memory) comprises numerous bit storage locations
• Code and data to be executed are stored there
• The memory subsystem is a component of computer hardware

Memory Organization

• The basic unit of memory amounts to a byte, a collection of 8 bits
• Computer memory is structured into memory cells the size of a byte
• The most significant bit is on the high-order end; conversely, the least significant bit is on the low-order end

Unique address for each memory cell:

• The location is identified within primary computer memory by a unique address
• Numerical addresses begin with zero
• Order assignment occurs in memory cell addresses alongside bits enclosed inside those cells
• Larger bit patterns can be stored
• Memory cell accessing involves performing read/write operations
• Computer primary storage constitutes what is known under the designation of RAM
• Required cells can be accessed randomly and independently in any sequence
• All cells take the equal time to be accessed
• DRAM(Dynamic RAM) and SDRAM (Synchronous DRAM) are used

Measurement of Memory

• Memory capacity is measured using units indicated below:
• Kilobyte (kB): 2^10 or 10^3
• Megabyte (MB): 2^20 or 10^6
• Gigabyte (GB): 2^30 or 10^9
• Terabyte (TB): 2^40 or 10^12
• Petabyte (PB): 2^50 or 10^15
• Exabyte (EB): 2^60 or 10^18
• Zettabyte (ZB): 2^70 or 10^21

Mass Storage Devices

• Mass storage is used as auxiliary storage
• It is a non-volatile storage device that costs less
• Offers the option of being separated from the computer for safekeeping
• Hard Disk Drives (HDD) and flash memory (SSD) are considered to be mass storage
• Disk Cache, Actuator and Spindle are component parts

Hard Disk Configuration

• Tracks consist of concentric circles on surface of platters designated for data savings
• Each track is split into sectors. A sector constitutes smallest increment by that computer can save/retrieve saved data
• All aligned and concentric tracks across platter produce what is referred under the label of cylinder

Parameters for Measuring Disk Drive Performance:

• Seek Time: Duration needed to bring a drive head to a track housing acquired information
• Rotational Latency Time: Once reader reaches target track, the duration of period taken to access particular data region underneath the head
• Data Transfer Rate: Header transfer happens after time that head takes access to all of required bits set onto transmission channel for transport from sector
• Bandwidth: Overall bit-range set in channels or lanes transferring within a component medium with bit-streams from transmitter point up until its reciprocal receiver module

Disk Formatting

• Sectors can range from 512-byte sectors up to 4096-byte sectors on newer drives

Flash Memory

• Electrically records and erases data, is a non-volatile memory

Flash Memory - Page Simple Writing & Page Modification

• Solid state drives use pages and blocks to store data.
• A page in a solid-state drive performs the task of the smallest unit of data, when writing or reading is in progress

Flash Memory Types and Characteristics Comparison:

• NAND-type flash memory offers the ideal storage media for SSDs and USBs because of its high density, lower cost, blocked access for reads and writes, and fast write capability
• NOR-type flash memory provides possible code storage, emulating RAM where cell access is quicker for readable and writable processes. However writing is a lot slower at less density, coupled along higher cost constraints

Bit Patterns to Represent Information

• Data represents facts or figures collected for analyzation. Conversely, information is structured/processed set elements with interpretable structure providing details necessary in making a reasonable decision or to achieve set goals
• An example of data is collected temperatures, like Monday: 20°C, Tuesday: 22°C, Wednesday: 21°C, Thursday: 23°C, etc
• Information examples include patterns or averages in collected temperatures, changes detected throughout these measures, potential trend or if there are high points with related trends

Representing Text

• Each unique character has a unique bit pattern (code) assignment
• The International Standard Coding System eliminates any communication problems stemming from language
• ASCII (American Standard Code for Information Interchange) uses 1 byte
• Unicode uses 2 bytes with, for example, "A": U+0041, "가": U+AC00
• UTF-8 (Unicode Transformation Format 8-bit) uses 1~4 bytes

Representing Numbers

• Binary and hexadecimal are used to represent numerical data
• Sixteen bits using ASCII provides decimal numbers as 99 (0-99 range)
• Sixteen bits as second-level numerals has upper threshold or 65535 ranges

Image Representation: Bitmap Method

• Images are represented using collections of pixels
• Color images use the RGB (Red, Green, Blue) color model for storage
  • Each pixel has an RGB combination (8*3=24bit, approximately 16.7 million colors)
  • Best suited to vibrant colors and flexible drawing like photographs
• Image file formats consist of JPEG, PNG, GIF, BMP and TIFF

Vector Method Image Representation

• Vector Images are made by describing the image using lines and curves that are defined by mathematical equations
• Images can be scaled without losing any quality
• TrueType and PostScript are vector-based image file formats

Sound Representation

• Involves encoding a range of amplitude values extracted at regular intervals along audio waves
• Continuous audio waves are converted into the digital domain by sampling, quantizing, and encoding

Practical audio sampling rates:

• 8,000 samples/second produce what is observed in standard telephonic means for transmission protocols/infrastructure
• CD Music: 44,100 samples/second
• Bits/second Requirements for Storing CD music: 88,200 bytes are needed
• A stereo system using the same bit range requirements has rates doubled because two channels are involved (176,400)

Binary Number System

• The Positional Numeral Notation expresses numerical values by assigning a weight to each digit based on its location and the base (or radix) of the numbering system:
• a{n}r^{n} + a{n-1}r^{n-1} ... a_{1}r^{1} + a_{0}r^{0} + a_{-1}r^{-1} ...:
• The coefficient (a) is a digit between 0 and the base (r) -1
• r is the numbering system base (e.g. 2, 10, 16)
• n represents the digit number from 0 to n
• For example: 1011 = 1 x 2^3 + 0 x 2^2 + 1 x 2^1 + 1 x 2^0
  • Binary: 11 = 1 x 2^1 + 1 x 2^0
  • Decimal: 11 = 1 x 10^1 + 1 x 10^0
  • Hexadecimal: 11 = B x 16^0

Binary Number System:

• The range of naturals representable within eight-bit binary numerals goes up until max limit as 255 after starting low, like the range set amongst standards for (0–255)
• Using n bits to express the range represents all the natural numbers limited under range set, 0 to 2^{n} - 1.

Binary to Decimal Conversion Algorithm

• Begin by dividing given value represented in tens to a new numeral on its own starting with factor 2 and saving remainder as result from first division
• If factor gained from initial factorising does have some significant output for another round, then divide gain as quotient of two, then save remainder as division two. Run successive calculations
• Where gain gives a 0, then list remained elements successively starting backwards gives number in two’s exponent form

Hexadecimal

• Long strings of bits (bitstreams) are unwieldy to handle. For example, 101101010011 is hard to read and comprehend
• Hexadecimal consists of using a symbol from range 0–15 through an established bit system. I.e: 4 digit presentation system, ex) 0xB53

Two's Complement Addition

• Carries happen anytime a bit shifts into the digit beyond the length designated
• Result from an overflow is incorrect
• Full adders add binary numbers and account for values carried in as output

Fractional Two's Complement Notation

• A binary 101.101 is interpreted as: 1 x -(2^2) + 0 x (2^1) + 1 x (2^0) + 1 x (2^-1) + 0 x (2^-2) + 1 x (2^-3)

Storing Integers

• Range representation as: (-anan-1an-2 ... a1a0, 0, anan-1an-2 ... a1a0)
• Integer notation involves a number system or code that clearly indicates if the number is positive or negative
  • Signed Magnitude notation
  • Signed (r-1)'s complement notation
  • Signed r's complement notation
  • Excess notation
• MSB to the LSB

The r's Complement Notation

• Defined by two equations. If N is positive, the r's complement is 0. If N is negative, the r's complement is r^n -N, where r is the radix and n is the number of digits
• Find the two's complement of 101100 -(2^6)2 – (101100)2 = (1000000 – 101100)2 = 010100

r's Complement Representation by Two's Compliment Algorithm

• Two's complement is used for subtraction
• M-N is calculated by adding the two's complement of N to M
• Examine the end carry after completing step one
  • When end-carry does result, remove excess for true answer
  • Find more complements or opposite ends for true answer

Overflow Problems

• Overflow occurs when a calculation produces a number outside the range which a certain number of bits can represent

Excess Notation

• The value to be represented is stored as a bit pattern greater than the numerical value by a fixed amount
• For example, with 4-bit excess 8, -8 to 7 can be represented

Fractional Representation

• Fixed-point notation is employed for 8 bits. It includes seven integer digits and one digit is allocated for representing fraction or decimal portions
• Very large or tiny values must allocate extra number of bits

Floating-Point Notation

• Eight-bit floating point employs exponent set utilizing excess, while four point or portions get allocated
• A 7 6 4 3 0
• Zeroes are preserved by setting all bits

Stored Real Value 10.11

• The values are stored within what the common numerical forms can allocate
• Expressed as: 0.1011 x 22
• In real floating ranges, one element consists inside a set quantity with quantity codes such as set quantities, all as signed or coded numbers: set(0.1011)

Communication Errors

• Original bit patterns are altered during data transmission within computers, in storage, and when transferred to external devices; This alteration is the result of noise, electromagnetism, and dust
• An encoding mechanism is needed that can correct or detect anomalies or glitches

Parity Bit

• Method for error detection using a parity bit
  1. Adding the bits gives the patterns
  2. Following transmission, any mismatched bits signal a system issue
• Odd parity
  • Guarantees the occurrence of anomalies through use of an incorrect set system

Parity Bit Limitations

• If there are duplicate or sets with multiple bit errors, this strategy is redundant for error prevention or troubleshooting

Chapter Exploration & Learning Topics

• Data Compression
  • Is it possible to fit an entire book on a single sheet of paper?
• Error Correction Code
  • Is there a way to automatically fix data errors?