5: Fundamentals of Data Representation Flashcards
1
Q
Natural Numbers
A
N = {0, 1, 2, 3, …}
2
Q
Integers
A
Z = {…, -3, -2, -1, 0, 1, 2, 3, …}
3
Q
Rational Numbers
A
Q - the set of numbers that can be written as a fraction (includes integers)
4
Q
Irrational Numbers
A
The set of numbers that can’t be written as a fraction
5
Q
Real Numbers
A
R - the set of all possible real world quantities (includes natural, rational & irrational numbers)
6
Q
Ordinal Numbers
A
Describe the numerical position of an object in a list
7
Q
Counting & Measurement
A
Natural numbers are used for counting and real for measurement
8
Q
Number Bases (3)
A
- Decimal (base 10)
- Binary (base 2)
- Hexadecimal (base 16)
9
Q
Benefits of using Hexadecimal as Shorthand for Binary (4)
A
- Numbers are more compact when displayed
- It is easier for people to understand and read
- There is a lower likelihood of an error when typing in data
- It saves the programmer time when typing in data
10
Q
Bit
A
Fundamental unit of information (0 or 1)
11
Q
Byte
A
A group of 8 bits
12
Q
Binary Values Representable with n Bits
A
2ⁿ
13
Q
Binary Prefixes (4)
A
- Kibi, Ki – x2^10
- Mebi, Mi – x2^20
- Gibi, Gi – x2^30
- Tebi, Ti – x2^40
14
Q
Decimal Prefixes (4)
A
- Kilo, k – x10^3
- Mega, M – x10^6
- Giga, G – x10^9
- Tera, T – x10^12
15
Q
Unsigned vs Signed Binary
A
Unsigned binary can only represent positive numbers (has a sign bit of 0) whereas signed binary can represent both positive & negative
16
Q
Minimum & Maximum Values in Unsigned Binary
A
For n bits: 0, 2ⁿ - 1
17
Q
Unsigned Binary Arithmetic (2)
A
- Add two integers
- Multiply two integers
18
Q
Two’s Complement
A
A possible coding scheme for signed binary
19
Q
Signed Binary Operations (2)
A
- Represent negative and positive integers
- Perform subtraction
20
Q
Minimum & Maximum Values in Signed Binary using Two’s Complement
A
For n bits: -2ⁿ⁻¹, 2ⁿ⁻¹ - 1
21
Q
Convert Signed Binary to Decimal (4)
A
- Flip bits
- Add 1
- Convert to decimal as unsigned binary
- Flip the sign
22
Q
Convert Negative Decimal to Signed Binary (4)
A
- Flip sign
- Convert to unsigned binary
- Flip bits
- Add 1
23
Q
Perform Binary Subtraction (2)
A
- Convert the number, which is being subtracted, into signed binary
- Add the two binary numbers ignoring the overflow bit
24
Q
Fixed Point Form
A
Numbers with a fractional part can be represented using fixed point form in binary, where the binary point is programmed into the system not stored in the data
25
Numbers with a Fractional Part Conversions (2)
- Decimal to binary in a given number of bits
- Binary to decimal in a given number of bits
26
Convert 0011 1001₂ to Decimal (4 Bits Before & After Binary Point)
8x0 + 4x0 + 2x1 + 1x1 + 0.5x1 + 0.25x0 + 0.125x0 + 0.0625x1
= 2 + 1 + 0.5 + 0.0625
= 3.5625₁₀
27
Convert 3.5625₁₀ to 8-bit binary (4 bits before and after binary point)
3.5625 - 2 = 1.5625
1.5625 - 1 = 0.5625
0.5625 - 0.5 = 0.0625
0.0625 - 0.0625 = 0
0011 1001₂
28
Differentiation between Decimal Digit Representations
Can be represented as a character code or pure binary (e.g., 65₁₀ is 'A' in ASCII but 01000001₂ in binary)
29
ASCII (3)
- Uses 7 bits to encode characters
- Can represent 128 different characters
- Extended ASCII has been developed, which uses 8 bits to encode characters
30
Unicode (3)
- Introduced to support a larger range of characters than ASCII
- Due to increased international communication and use of files in multiple countries
- Each character code is always interpreted as the same character
31
Error Checking & Correction Methods (4)
- Parity bits
- Majority voting
- Checksums
- Check digits
32
Parity Bits (3)
- Two types of systems: even & odd parity
- Transmitting computer attaches a parity bit to start of binary to make number of 1s in binary odd / even (e.g., for even: 0101 → 00101 & 0100 → 10100)
- Receiving computer checks there are odd / even number of 1s in binary
33
Parity Bits Disadvantages (2)
- Cannot detect all errors (e.g., if two bits change)
- Doesn't show where error is, only that error has occurred
34
Majority Voting (2)
- Each bit is transmitted multiple times
- The receiver checks the bits it has received and if they are not all the same it assumes the one it received the most copies of is the correct value for the bit
35
Majority Voting Disadvantages (3)
- If there are multiple errors in a group of 3 bits, the receiving computer will correct the final bit wrongly and assume that is correct
- Transmission time is 3 times longer
- Increased processing time
36
Checksums (3)
- Checksum is a number which is calculated from the data in the packet
- Checksum is recalculated when packet is received
- If the checksum received in packet matches the recalculated checksum then data has been received correctly
37
Checksums Disadvantages (2)
- Multiple bits can change without changing the checksum value resulting in an undetected error in the data
- Doesn't tell the receiver how to correct the error
38
Check Digits (4)
- A check digit consists of a digit calculated using an algorithm from the other digits in the input sequence
- The digit is added to the end of the data and then transmitted
- The receiving computer applies the same algorithm
- If the two check digits are the same, the data is deemed as correct
39
Check Digits - (2)
- Increased transmission length
- Increased processing time
40
Bit Patterns
Can represent various forms of data (e.g., text, numbers, graphics & sound) by storing and reading data as a string of binary numbers
41
Analogue Data (2)
- Wave is recorded in its original form and continuously varying quantities are measured
- Uses a continuous range of values to represent information
42
Digital Data (2)
- Waves are sampled at intervals, converted to a discrete set of numbers and stored
- Quantities are counted and it uses discrete values to represent information
43
Analogue Signal
A continuous signal, which represents a physical wave
44
Digital Signal
A discrete signal generated at regular time intervals
45
Analogue to Digital Converter – ADC (3)
- Analogue signal sampled at regular time intervals
- Amplitude of signal measured at each sample point
- Measurement coded into a fixed number of bits
46
Digital to Analogue Converter – DAC (3)
- Takes a binary value
- Converts the digital data to an analogue signal
- DACs are speakers
47
Representation of Bitmaps
Represented by lots of pixels (the smallest addressable element of a picture), whose colours are represented by binary codes
48
Bitmap Resolution
Number of dots (pixels) per inch; determines image quality and sometimes used to describe the size of an image
49
Colour Depth
Number of bits stored per pixel; determines the number of different colours each pixel can represent
50
Bitmap Size in Pixels
Width of image in pixels x Height of image in pixels
51
Storage Requirements for Bitmapped Images
Size in pixels x Colour depth
52
Typical Metadata for Bitmap Image File (5)
- Width
- Height
- Colour depth
- File type
- File size
53
Digital Representation of Sound (4)
- Microphone picks up sound
- ADC samples sound at regular time intervals
- Samples are quantised – approximated to an integer value
- Binary value representing sample is stored
54
Sample Rate
Number of samples per second – measured in Hertz (Hz)
55
Sample Resolution
Number of bits used to store each sample (usually 16 bits)
56
Higher Sample Rate & Resolution (2)
- Better quality / resolution
- Larger file size
57
Nyquist Theorem (3)
- To properly measure all frequencies, the sample rate must be double the highest frequency in the original sound
- Humans can hear frequencies from 20 Hz to 20 kHz
- Hence, most recordings have a sample rate of 44.1 kHz
58
Sound Sample Size
Sample rate x Sample resolution x Time (s)
59
Musical Instrument Digital Interface (1, 1:4, 6)
- Music represented as sequence of MIDI event messages
- Examples of data in event messages:
• Channel
• Note on / note off
• Pitch
• Volume / loudness
- MIDI messages are usually two or three bytes long
- First byte of each MIDI message is a status byte and others are data bytes
- Bit rate is 3 250 bits per second
- MSB value of 1 indicates status byte, 0 indicates data bytes
- Status bytes are divided into a command and a
channel number (4 bits for each)
- Sixteen channels are supported
60
Advantages of MIDI File over Conventional Sound File (8)
- More compact representation
- Easy to modify notes
- Easy to change instruments
- Simple method to compose algorithmically
- Musical score can be generated directly from a MIDI file
- No data lost about musical notes
- The MIDI file can be directly output to control a device
- MIDI records the musician’s inputs rather than the sound produced
61
Reasons for Compressing Image & Sound Files (3)
- Take up less storage space
- Faster transmission times
- To fit within certain system restrictions (such as, e-mail attachment restrictions)
62
____ can also be compressed
Other files, such as text files
63
Lossless Compression
No data is lost about the original image in compression
64
Lossy Compression
Data is lost about the original image in compression
65
Lossless Compression +/- (4)
+ The file can be reproduced exactly as it was originally
+ The quality of image / sound / video would not be reduced
- Less effective at reducing file size than lossy
Used for executable and text files
66
Lossy Compression +/- (4)
+ Much lower file sizes
- Loss in quality of image / sound / video
- Lossy compression cannot be reversed
Used for image, video and sound files
67
Techniques for Lossless Compression (2)
- Run length encoding (RLE)
- Dictionary-based methods
68
Run Length Encoding – RLE (3)
- Reduces the size of a run (repeated string)
- Encodes run into two values:
1. Run count: Number of repeated characters in a run
2. Run value: Value of each character
- Does this for every run in data
69
Dictionary-Based Methods (3)
- Variable length strings of symbols (substrings) of original data are represented by single tokens
- A dictionary is formed using the tokens as the keys
- The strings of symbols are used as the entries
70
Encryption
The encoding of a message, converting plaintext to ciphertext, so that other parties cannot read it. The message can only be decrypted by the authorised receiver
71
Cipher
An algorithm that encrypts and decrypts data
72
Plaintext
Unencrypted data
73
Ciphertext
Encrypted data
74
Caesar Cipher (2)
- Each letter in the plaintext is substituted by the letter, which is a set number of places ahead of it in the alphabet / character code tables, to produce the ciphertext
- The set number of places is called the key
75
Why is Caesar Cipher Easily Cracked? (2)
- There are only 26 different values for the key
- You can use frequency analysis to find the most common letter in the ciphertext. This letter's displacement from e (usually the most frequent letter in the plaintext) is likely to be the key
76
Vernam Cipher (4)
- A completely random key (equal in length to the plaintext) is generated
- A bitwise logical XOR operation is performed on the Baudot character codes of each of the corresponding characters of the plaintext and key
- The string of characters represented by the resultant character codes is the ciphertext
- To decrypt, perform the same steps with the same key but using the ciphertext instead of the plaintext
77
Why does Vernam Cipher have Perfect Security?
Frequency analysis does not provide any clues to the ciphertext
78
Vernam Cipher vs Computationally Secure Ciphers (4)
- Vernam cipher (if implemented correctly) is unbreakable
- Frequency analysis of ciphertext reveals nothing about plaintext
- More possible keys
- Vernam cipher does not always translate a ciphertext character to the same plaintext character
79
Convert 01101011 to Decimal (floating point form: 5-bit mantissa, 3-bit exponent)
Exponent: 3
Mantissa: 0.1101 -> 0110.1 = 6.5
80
Convert 10101110 to Decimal (floating point form: 5-bit mantissa, 3-bit exponent)
Exponent: -2
Mantissa: 1.0101 -> -0.1011 -> -0.001011 = -0.171875
81
Rounding Errors (3)
- To represent a decimal number in binary, the fractional part needs to be broken down into a sum of fractions with denominators of powers of two (binary fractions)
- This is not always possible for some fractional parts or there are not enough bits to do so
- Hence, fixed and floating point representations of decimal numbers may be inaccurate
82
Fixed Point vs Floating Point (3)
- Floating point form has a larger range of possible numbers than fixed point form if more bits are used in the exponent
- Floating point form has a larger precision than fixed point form if more bits are used in the mantissa
- Calculations using floating point form are slower than calculations using fixed point form
83
Normalising Floating Point Numbers + (2)
* Maximises precision for given number of bits
* Unique representation of each number
84
A normalised positive number starts as ____
0.1
85
A normalised negative numbers starts as ____
1.0
86
Overflow (2)
- Occurs when the result of a calculation is too large to be represented with the available number of bits
- Can arise due to addition of two numbers of the same sign
87
Underflow (2)
- Occurs when the result of a calculation is too close to 0 to be represented with the available number of bits
- Can arise from subtracting two numbers with similar values and the same sign
88
Vector Graphics
Images made up of a drawing list of geometric objects / shapes whose properties are stored as a list
89
Examples of Typical Properties of Objects in Vector Graphics (5)
- Centre of a circle
- Radius of a circle
- Fill colour of a shape
- Position of a shape
- Side length of a square
90
Vectors Graphics + (4)
- Can be scaled without loss of quality
- Small file sizes
- Easy to manipulate the objects
- If an object is deleted, the software knows what is behind it
91
Bitmap Graphics + (2)
- Can represent a wide range of images
- Can depict any level of complexity and detail
92
Uses of Vector & Bitmap Graphics (1:4, 1)
- Vector:
• Illustrations
• Cartoons
• Logos
• Web designs
- Photographs are always stored as bitmaps
