Computer Data Representation Quiz

Data Storage

• Data stored in a computer is represented by bit patterns
• Bits (binary digits) can represent different values, for example numeric values (1 or 0), boolean values (true or false) or voltage (high or low)
• Data patterns can represent numbers, text characters, images, sound, or anything else
• Boolean operations manipulate true/false values, often used as logical operations on bits
• Boolean operations include AND, OR, XOR (exclusive OR), and NOT
• Gates are electronic circuits that perform Boolean operations on input values, acting as fundamental building blocks of computers
• Flip-flops are circuit devices, built from gates, that can store one bit of data
• A byte is typically 8 bits
• Main memory acts as a central storage unit in a computer system, storing programs and data during operations utilizing semiconductor integrated circuits
• Each memory unit (cell) is assigned a unique address
• Main memory is divided into banks and cells, with each cell represented in an organized array
• Data in RAM is volatile, while data in ROM is non-volatile
• Mass storage systems are non-volatile and usually much larger than main memory, performing slower read/write operations compared to main memory
• Mass storage systems include magnetic systems (disks, tapes) and optical systems (CDs, DVDs)
• Flash technology (flash drives, SD cards) is also a mass storage method
• A file is the unit of data stored on a mass storage system
• Logical records are natural groups within a file
• Key fields hold identifier keys within a logical record
• Physical records are blocks of data that fit the characteristics of the storage device
• Buffers are memory areas used for temporarily storing data

Representing Data

• Data is coded to be read and understood by a system (internally or externally), through coding systems
• Information is coded for internal computations, presentation purposes (text, graphics, sound), and long-term storage (databases, archives)
• Coding ensures that data can be recognized later in the system
• External representation: (for people) is typically a visually understandable format, like handwritten, graphical, etc...
• Internal representation: (for computing machines) is a sequence of 0s and 1s
• For numeric data we use positional formats (e.g. decimal, binary, octal, hexadecimal)

Representing Non-numeric Data

• Computing devices code letters and special symbols independently
• Common coding schemes for symbols are ASCII and EBCDIC

Representing Strings in ASCII

• A 'string' is a sequence of bytes (characters) in ASCII
• Strings typically contain text characters
• Strings can have any number of characters
• The end of a string needs to be identified

Representing Numeric Data

• Internal number representation is always a sequence of 0's and 1's (binary)
• External representation uses various notations like Roman Numerals and positional notations (decimal, binary, octal, hexadecimal)
• Internal number representations can cause overflow when a number is too large to be stored

Representing Data Externally

• Non-positional notations include Roman Numerals, where digit position does not carry weights. The meaning of digits depends on the context.
• Positional notations depend on the position of the digits in the number. Decimal, binary, octal and hexadecimal are examples of positional notations.

Octal Encoding

• Octal encoding is a way to represent bits in groups of three

Representing Images

• Bit map techniques represent images as collections of dots (pixels)
• Pixel values are either 0 or 1 (binary) for black and white images and range from 0-255 for grayscale images, or colour images using RGB
• Vector techniques represent images as sets of lines and curves (circles, polygons).

Colour Depth

• Colour depth of images is determined by the available palette size
• Image formats like PNG, BMP, PIC, GIF, JPEG and TIFF are common
• 1-bit images have 2 colours (e.g., black and white)
• 8-bit images support 256 grey levels
• 24-bit images support 16 million colours

Representing Numeric Values

• Binary notation uses bits to represent numbers in base two.
• Limitations of computer representations of numeric values can include overflow, which happens when a number is too big to be represented within the available bits

Binary Representation

• Base ten system uses positions to define quantities and the position (e.g. hundred, ten, one), and their respective quantities
• Base two system uses positions to define quantities and positions (e.g. eight, four, two, one) and their respective quantities

Decoding Binary Representation

• The procedure to decode a binary number can involve evaluating the contribution of each bit based on its positional weight and converting it to the decimal equivalent

Positive Integer in Binary Notation

• An algorithm to find a positive integer's binary representation involves repeatedly dividing the value by two and recording the remainder, until a quotient of zero is obtained. The binary representation consists of the remainders from right to left

Binary Addition

• Binary addition follows rules that include addition of bits and carry forward when the sum of any two bits is greater than 1.

Fractions in Binary

• Binary fractions can be decoded according to the positional weight of each bit, allowing their representation to be converted to a decimal representation.
• To encode binary fractions, repeatedly subtract successive negative powers of 2, recording the success (1) or failure (0) of each subtraction from the radix point until the result is 0.

Representing Integers

• Unsigned integers, represented in base two and occupying 4 bytes, range from 0 to 4294967295
• Integers occupy 2n bytes in memory (usually 1, 2, or 3)

Signed Integers

• Signed integers are whole numbers that can be positive or negative, with ranges from -2147483648 to 2147483647
• These are represented in ways like sign-magnitude notation, one's complement notation, or two's complement notation.

Representing Integers (Internally) 

• Sign-magnitude, one's complement, and two's complement notations allow to represent both positive and negative values. The choice of representation influences the way negative values are codified

Representing Integers (Internally) Complement Notations

• One's complement involves subtracting each bit from 1
• Two's complement involves subtracting each bit from 1 and adding 1 to the result.

Ranges of Values of N bits 

• 1's complement has a range of values that can be represented in n bits from -2^n-1 + 1 to 2^n-1 -1. For one byte (n=8), the range is from -127 to +127
• 2's complements have a range from -2^n-1 to 2^n-1 -1. For one byte (n=8), the range is from -128 to +127

Two's Complement

• Two's complement is a notation to represent both positive and negative integer values. There is only one zero in two's complement (00000000)
• Negating a number in two's complement involves inverting all the bits and adding 1 to the result.
• Two's complement addition is the same as adding two unsigned numbers but there is a need to detect overflow.

Excess-N Representation

• Excess-N representation encodes values by adding a constant offset (N) to the intended value.
• This system is typically used to represent signed numbers in cases where the representation system avoids the additional complexity associated with sign representation.

Data Compression

• Data compression reduces the amount of data needed for storage and transfer
• Compression Ratios describe the ratio of the original data size to the compressed size, e.g. 14:1

Lossy vs Lossless Compression

• Lossy compression discards some data permanently, while the decompressed data differs from the original
• Lossless compression preserves all data in the original file, such that if the file is decompressed the resulting file is identical to the original

Generic Data Compression Techniques

• Run-length encoding identifies repeated binary patterns and represents them with a single instance of the pattern and a count
• Relative encoding records differences between consecutive data units, rather than representing each unit completely

Frequency-Dependent Encoding

• Huffman coding uses variable-length bit patterns to represent data items, with frequent items having shorter codes, which is commonly used during text compression.

Adaptive Dictionary Encoding

• Adaptive dictionary encoding (e.g., Lempel-Ziv encoding) constructs a dictionary of previously encountered blocks and encodes subsequent instances using a reference to that block in the dictionary. The dictionary can change during encoding.

Compressing Images

• GIF uses lossy compression to limit colours to 256 and dictionary encoding
• JPEG encompasses several compression techniques.

Communication Errors

• Data bits may be corrupted during transmission or retrieval from storage
• Errors can occur due to factors such as dirt or damage on a disc surface, circuit malfunctions or static electricity on transmission path.

Parity Bits

• Parity refers to the oddness or evenness of the number of bits in a pattern. Odd parity requires each pattern to contain an odd number of 1s; even parity requires an even number of 1s.
• Parity bits are extra bits to ensure odd or even parity in a message sequence, allowing the reader to detect errors in the message. 

Error-Correcting Codes

• Error-correcting codes are used to detect and correct errors in data transmission
• Hamming Distance measures the difference between two bit patterns. The greater the Hamming Distance between two different patterns the less likely they are to overlap (allowing for error detection and correction).