5 - Fundamentals of Data Representation Flashcards
1
Q
What is a natural number?
A
Natural numbers are positive whole numbers, including 0.
N = {0, 1, 2, 3, 4, …}
2
Q
What is an integer?
A
Integers are positive and negative whole numbers including 0.
Z = {…, -3, -2, -1, 0, 1, 2, 3, …}
3
Q
What is a rational number?
A
A rational number is any number that can be written as a fraction where the numerator and denominator are integers. (include values that can be expressed as fractions or ratios).
This includes integers and values with recurring values.
ℚ = {…, 2/1, 2/2, 2/3, 2/4, …}ℚ = {…, 2, 1, 0.6̇, 0.5, …}
4
Q
What is an irrational number?
A
An irrational number is any number that cannot be represented as a fraction (or ratio), for example √2 or pi.
5
Q
What are real numbers?
A
If a number is either rational, (an integer or a fraction) or irrational, it is considered to be a real number ℝ
Used for measurement.
R is the set of all “possible real world quantities”
6
Q
What is an ordinal number?
A
Ordinal numbers are used to label the positions of objects in a list, ordered set or sequence of objects.
If we have the set S = {“a”, “b”, “c”, “d”}, then “a” is the 1st object, “b” is the second object, and so on.
7
Q
What is a cardinal number?
A
A cardinal number identifies the size of something. For example, the size of a list.
8
Q
What are natural numbers used for?
A
Natural numbers are used for counting (enumeration).
9
Q
What are real numbers used for?
A
Real numbers are used for measurement.
10
Q
What is binary?
A
Binary represents numbers using 2 digits, 0 and 1. Binary is base 2.
11
Q
What is hexadecimal?
A
Hexadecimal represents numbers using 16 digits, the numbers 0 - 9 and the letters A - F. Hexadecimal is base 16.
12
Q
What is decimal?
A
Decimal represents numbers using 10 digits, 0 - 9. Decimal is base 10.
13
Q
What is a number base?
A
The number of symbols used to construct values eg. base 2, 10, 16.
14
Q
How do you convert from Decimal to Binary?
eg.119₁₀
A
Set up the column headings and move from left to right putting a 1 under the combination of numbers that make up the decimal value.
eg.119 - 64 = 55 55 - 32 = 23 23 - 16 = 7 7 - 4 = 3 3 - 2 = 1 1 - 1 = 0
1286432168421
01110111
119₁₀→01110111₂
15
Q
How do you convert from Binary to Decimal?
eg.11010111₂
A
Add up the column headings with a 1 under them.
eg.1286432168421
11010111
128 + 64 + 16 + 4 + 2 + 1 = 215
11010111₂→215₁₀
16
Q
How do you convert from Decimal to Hexadecimal?
eg.527₁₀
A
Divide the decimal number by 16 (treating as integer division). Write down the remainder (in hexadecimal). Then repeat with the result of the division until the result is 0. The number in hexadecimal is the sequence of remainders in reverse order.
eg.527 DIV 16 = 32 527 MOD 16 = 1515 → F 32 DIV 16 = 2 32 MOD 16 = 0 2 DIV 16 = 0 2 MOD 16 = 2
256161
20F
527₁₀→20F₁₆
17
Q
How do you convert from Hexadecimal to Decimal?
eg.C7F₁₆
A
Multiple each of the column headings by the value under them. The total is the decimal value.
eg.256161
C7F
256 * 12 + 16 * 7 + 1 * 15 = 3199
C7F₁₆→3199₁₀
18
Q
How do you convert from Binary to Hexadecimal?
eg.10111110₂
A
Split the binary number into nibbles and find the hexadecimal value that represents each nibble.
eg.84218421
10111110
→B→E
10111110₂→BE₁₆
19
Q
How do you convert from Hexadecimal to Binary?
eg.7D₁₆
A
Find the binary value that represents each digit of the hexadecimal number and join them together.
eg.↓7↓D
84218421
011111 01
7D₁₆→01111101₂
20
Q
Why is hexadecimal used as a shorthand for binary?
A
- A hexadecimal value is much easier to read and remember than a string of binary digits
- Writing numbers in hexadecimal form is less error prone than writing the same numbers in binary.
- It is quicker to write or type, since a hex digit takes up only one character, not four.
- It can be displayed in less space.
21
Q
What is hexadecimal used for?
A
- To define memory locations.
- To represent MAC addresses.
- To define colours on web pages.
22
Q
What is a bit?
A
A bit is the fundamental unit of information. It is an abbreviation of binary digit. A bit can be either a 0 or a 1.
23
Q
What is a byte?
What is a nibble?
A
A byte is a group of 8 bits.
A nibble is a group of 4 bits.
24
Q
How many different values can be represented with n bits.
A
2ⁿ different values.
25
What are the quantities of bytes using binary prefixes?
Kibibyte - KiB - 2¹⁰ bytes
Mebibyte - MiB - 2²⁰ bytes
Gibibyte - GiB - 2³⁰ bytes
Tebibyte - TiB - 2⁴⁰ bytes
26
What are the quantities of bytes using decimal prefixes?
Kilobyte - kB - 10³ bytes
Megabyte - MB - 10⁶ bytes
Gigabyte - GB - 10⁹ bytes
Terabyte - TB - 10¹² bytes
27
What symbol is used to represent bits?
What symbol is used to represent bytes?
b
B
28
What is the minimum and maximum values that can be represented n bits (using unsigned binary)
Minimum = 0
Maximum = 2ⁿ - 1
29
How do you add two unsigned binary integers?
eg. 01001101 + 01101010
Align the binary numbers and perform column addition.
```
eg. 0 1 0 0 1 1 0 1
0 1 1 0 1 0 1 0 +
──────────
1 0 1 1 0 1 1 1
──────────
¹ ¹
```
30
How do you multiply two unsigned binary integers?
eg. 11011 x 11
Align the binary numbers and perform long multiplication.
```
eg. 1 1 0 1 1
1 1 x
───────
1 1 0 1 1
1 1 0 1 1 0 +
─────────
1 0 1 0 0 0 1
─────────
¹ ¹ ¹ ¹ ¹
```
31
What is two's complement?
A method of working with signed numbers using fixed-width binary where the most significant (left most) bit is the sign bit. (used to represent negative values).
32
Signed vs Unsigned Binary
The "signed" indicator means that the item can hold positive or negative values. "Unsigned" doesn't distinguish between positive and negative values.
The first bit (MSB) is used to show whether number is positive or negative in signed binary (so number represented goes to 127) whereas in unsigned it isn't so the number represented can go up to 255 (assumed positive).
33
How do you convert from decimal to signed binary (using two's complement)?
eg. -97₁₀
Find the positive in binary, flip the bits and add one.
(another way to do it below)
If the number is negative, place a 1 under the MSB then add a 1 under the column headings which, when added to the value of the MSB, give the number.
```
eg. -128 + 16 = -112
-112 + 8 = -104
-104 + 4 = -100
-100 + 2 = -98
-100 + 1 = -97
```
-128 64 32 16 8 4 2 1
1 0 0 1 1 1 1 1
-97₁₀ → 10011111₂
34
How do you convert from signed binary to decimal (using two's complement)?
eg. 10011010₂
Add up the column heading with a 1 under them (where the MSB is negative).
eg. -128 64 32 16 8 4 2 1
1 0 0 1 1 0 1 0
-128 + 16 + 8 + 2 = -102
10011010₂ → -102₁₀
35
How do you perform binary subtraction using two's complement?
eg. 0101₂ - 0011₂
Turn the value that is being subtracted into a negative using twos complement, then add the two values.
eg. 0101₂ - 0011₂
→ 0101₂ + (-0011₂)
→ 0101₂ + 1101₂
→ (1)0010₂
a carry is generated which is ignored
0101₂ - 0011₂ → (1)0010₂
36
What is the range of values that can be represented using two's complement with n bits.
the range is -2ⁿ⁻¹ to 2ⁿ⁻¹ - 1
37
What is fixed point binary?
Fixed point binary is a method of representing numbers with a fractional part, where the binary point is in a fixed position.
38
How do you convert from fixed point binary to decimal?
eg. 0110.0110₂
Set up the correct column headings according to where the point is positioned. Then add up the values of the column headings with a 1 under them.
eg. 8 4 2 1 . ½ ¼ ⅛ ¹⁄₁₆
0 1 1 0 . 0 1 1 0
4 + 2 + ¼ + ⅛ = 6.375₁₀
0110.0110₂ → 6.375₁₀
39
How do you convert from decimal to fixed point binary?
eg. 10.6875₁₀ (8 bits where the binary point is between the 4th and 5th bits)
```
eg. 10.6875 - 8 = 2.6875
2.6875 - 2 = 0.6875
0.8675 - ½ = 0.1875
0.1875 - ⅛ = 0.0625
0.0625 - ¹⁄₁₆ = 0
```
8 4 2 1 . ½ ¼ ⅛ ¹⁄₁₆
1 0 1 0 . 1 0 1 1
10.6875₁₀ → 1010.1011₂
40
What is ASCII?
ASCII (American Standard Code for Information Interchange) is a standard binary coding system for characters and numbers. In ASCII, the symbols corresponding to the letters of the alphabet (uppercase and lowercase), punctuation marks, special symbols and the decimal digits 0 to 9 are assigned different 7-bit binary codes according to a look up table.
41
What is Unicode?
Unicode is a standard binary coding system that has superseded ASCII. Unicode also includes international characters for over 20 countries and even includes conversions of classical and ancient characters. Can use 16 bits to represent far more characters.
42
Why was Unicode introduced?
Widespread use of the web made it more important to have a universal international coding system. ASCII only allows you to represent a small amount of characters (128 for standard ASCII or 256 for extended ASCII). This is not sufficient to represent all of the languages and scripts of the world, and all the possible numbers and symbols.
43
State two reasons why the unicode character coding system was introduced as an alternative to ASCII.
To enable the representation of a greater range of characters.
So that more languages can be represented.
To improve portability of documents, in ASCII representations could vary depending on the code page used.
44
How can transmission errors occur?
Electrical interference
Power surges
Synchronisation issues
Wear and tear on the cable or connectors
These errors can cause bits to flip from 1s to 0s and 0s to 1s.
45
Explain how the majority voting system works in the context of data transmission.
eg.
Each bit is sent an odd number of times, such as 3. The receiver checks the bits it has received and if they are not the same it assumes the one it received the most copies of is the correct value for the bit.
46
How do you convert from floating point binary to decimal?
eg. 0100100100 000100
Convert the exponent and move the binary point accordingly (adding preceding 1s for negative mantissa and 0s for positive mantissa for negative exponents). Then convert to decimal.
eg. exponent → 4
0.100100100 → 01001.00100 → 9.125
47
How do you convert from decimal to floating point binary?
eg. 12.125
Convert to fixed point binary move the binary point so that it's normalised (when the first two bits are different) and convert the exponent to binary.
```
eg. -16 8 4 2 1 . ½ ¼ ⅛
0 1 1 0 0 . 0 0 1
01100.001 → 0.1100001
exponent = 4 → 000100
→ 01100001 000100
```
48
How do you calculate the absolute error?
| approximate value - original value |
49
How do you calculate the relative error?
Absolute error ÷ original value
| Then converted to a percentage
50
What is underflow and when does it occur?
Underflow occurs when the result of a calculation is too small, i.e. too close to zero, to be represented with the available number of bits.
51
What is overflow and when does it occur?
Overflow occurs when the result of a calculation is too large to be represented with the available number of bits. Computers usually use a fixed number of bits so this can cause problems.
52
Explain the effects of using less bits to store the mantissa and more bits to store the exponent.
There is an increased range of numbers that can be represented, but there is reduced precision.
53
What are the advantages of using a normalised representation for floating point numbers?
* Maximises precision for a given number of bits
| * There is a unique representation of each number
54
How could a floating point system be modified to allow a more accurate representation of a number?
Adjust the mantissa to use more bits.
55
What are the advantages of floating point over fixed point?
* Floating point can maximise the available precision of fractional numbers for a given number if bits.
* Floating point form provides a much larger range of possible numbers that can be represented.
56
What are the disadvantages of floating point over fixed point?
In general, calculations that involve floating point numbers take longer than calculations involving fixed point numbers.
57
How do you normalise un-normalised floating point numbers?
eg. 00001011 0101
Move the binary point so that the first two bits are different. Then adjust the exponent to reflect the movement of the binary point.
eg. 0.0001011 → 0.1011
old exponent = 5
new exponent = 5 - 3 = 2 → 0010
→ 01011000 0010
58
Explain why the Vernam cipher is a better choice than the Caesar cipher when encrypting a sensitive message.
The Vernam cipher is harder to crack. Unlike the Caesar cipher, frequency analysis of ciphertext reveals nothing about the plaintext.
59
What are the conditions that must be met for the Vernam cipher to offer perfect security.
* The key must be as long as the plaintext
* The key must not be reused
* They must be truly random
* The key must not be revealed
Shared with the recipient by hand, independently of the message and destroyed immediately after use
60
Explain what it means for a cipher to be described as being computationally secure.
The cipher cannot be cracked in a reasonable amount of time.
61
What does MIDI stand for?
Musical Instrument Digital Interface
62
Describe the purpose of MIDI and how it works.
MIDI is used to produce and manipulate music. A MIDI file consists of a list of instructions or event messages that can represent music and be used to produce sound. A message may contain pitch or volume.
63
Describe the use of event messages in MIDI. Include examples of event messages.
MIDI uses event messages to control various properties of the sound which are typically encoded in binary and provide better communication between a MIDI device and the processor.
An event message may contain data on timing a note to play with other notes and sounds and what pitch or volume a note is.
64
Describe the advantages of using MIDI files for representing music.
* A MIDI file is a more compact representation than an equivalent sampled recording.
* The performance data be easily manipulated, for example, it's easy to change instruments or change the pitch or duration of a note.
* MIDI supports a very wide range of instruments providing more choices for music production.
65
If the most significant bit in 00111001 is a parity bit, explain how the value of a parity bit was be calculated by the sending device before it was transmitted.
The number of 1s has been counted and there is even number of 1s so the parity bit has been set to 0 to keep the number of 1s even.
66
Explain how the majority voting system works.
Each bit is sent multiple times. The receiver checks the bits it has received and if they are not all the same it assumes the one it receives the most copies of is the correct value for the bit.
67
What are the advantages of using majority voting over a parity and explain how this advantage is achieved.
* Majority voting can detect multiple bit errors as each triplet of bits represents one bit of data and can identify an error on that bit.
* Majority voting can correct as well as identify errors due to the majority bits being taken as the correct value and ignoring the minority bit.
* Majority voting is more efficient at detecting errors as parity bit systems may miss errors if an even number of bits are corrupted.
68
Explain how the even parity system works. Include a description of the roles of the sending device and the receiving device during transmission.
The sender counts the number of 1s in the bit pattern and adds an extra bit to ensure even number of 1s.
The receiver counts the number of 1s in the bit pattern received and if there are an odd number of 1s it identifies that an error has occurred.
69
Each packet of data transmitted around the LAN includes a checksum which is used for error detection. Describe how the checksum is used for error detection.
Checksum is a value (total sum of all bytes in a transmission of data) which is calculated from the data in the packet before it is transmitted. The checksum is recalculated when the packet is received. If the checksum received in the packet matches recalculated checksum then the data was received correctly. Can be used with credit card numbers.
70
Explain what the term pixel means.
A pixel is picture element which is the smallest addressable element of a picture.
71
Explain what is meant by lossy compression.
Lossy compression results in lost data from the original version.
Non-essential data is permanently removed to reduce file size, for example, different shades of the same colour in an image or frequencies of sound outside the range of human hearing
72
What information might be contained within the metadata for an image?
* Data/time information
* Camera settings
* Thumbnail
* Copyright information
73
What properties that could be stored about an object with vector graphics?
* Co-ordinates
* Object type
* Fill colour
* Edge colour
* Line width
* Line style
* Fill pattern
74
Describe the advantages and limitations of vector graphics when compared to the use of bitmap graphics.
Advantages:
• Less storage space likely to be needed
• Will load faster from secondary storage
• Will download faster
• Can be resized without distortion
• Image can be more easily searched for particular objects
• Can more easily manipulate individual objects in an image
Limitations:
• Only appropriate for images made of geometric shapes
• Unsuitable if colour of each pixel is likely to vary
• Some drawing tools are unlikely to be available when using vector graphics (eg spray paint, blurring)
• Can take longer to render an image for complex images
75
How do you calculate the minimum amount of storage required to store an image?
file size (in bits) = width × height × colour depth
Image quality comes at the expense of file size
76
How do you calculate the minimum amount of storage required to store a sound file?
storage requirement (in bits) = sampling rate × seconds × sample resolution
77
Describes the steps the ADC goes through when a song is being recorded using a microphone plugged into the sound car of a computer.
The ADC takes samples of the analogue signal at regular intervals. The samples are quantised and each sample is encoded as a binary value.
78
Why might it be appropriate for a song to be saved using lossless compression rather than using lossy compression?
No data is lost during the compression process using a lossless format. Therefore, the song can be reproduced identically to the original with no loss of quality.
79
What is meant by the resolution of a bitmapped graphic image?
The number of pixels per inch.
80
What is meant by the colour depth of a bitmapped graphic image?
The number of bits used to represent the colour of a single pixel.
81
Describe the principle used by RLE to compress a file and explain why RLE is an appropriate compression method for compressing images such as icons.
RLE works by identifying sequences of identical data values and represents these as one data value together with a count of how many such values are in the sequence.
Icons often contain sequences of pixels that are the same colour. Also, RLE is a lossless compression method, so the quality of the image will not be affected.
82
What is the check digit for error checking?
A check digit is an additional digit at the end of a string of other numbers designed to check for mistakes in input or transmission
Used for books and barcodes. Can be calculated using the Modulo 10 system.
83
How is the check digit calculated?
84
What is resolution?
The number of pixels used to make up a bitmap image is defined by the resolution.
width x height (this doesnt define the actual physical size of image as pixels may have to increase in size to match resolution).
85
What is bit depth and what does a higher bit depth mean?
A pixel is attributed a number of n bits
The number of combinations (2n) dictates the bit depth and therefore the number of colours that can be represented
A higher bit depth gives a greater range of colour and a better quality of image
86
Analogue vs Digital Signals
Analogue signals are continuous, whereas digital signals are discrete
87
How does Analogue to digital conversion happen?
Analogue sound samples are recorded via an amplifier
Each sample is quantised to measure its wave height and translate this into an integer value
The integer value is then converted and stored digitally as a binary value
To output a sound, the reverse happens
88
What is sampling rate?
The number of samples taken in one second measured in Hertz.
89
What is sampling resolution?
the number of bits per sample
90
What is Nyquist Theorem?
Because sound is made up of many components each at different frequencies, samples must be twice the highest frequency in order to replicate the original sound wave
This concept is known as the Nyquist Theorem:
fs > 2fmax
91
What is the Nyquist Rate?
Nyquist rate -- For lossless digitization, the sampling rate should be at least twice the maximum frequency responses. Indeed many times more the better.
92
What is the Nyquist Frequency?
½ the original frequency
93
Explain how MIDI represents music and the advantages of using MIDI for representing music instead of using sampled sound.
Music is represented as a sequence of MIDI event messages. Examples of data that might be contained in a message are channel, volume and note envelope.
Advantages:
• More compact representation
• Easy to modify the music, such as change the instrument
• Musical score can be generated directly from a MIDI file
94
What is MIDI?
The MIDI standard (Musical Instrument Digital Interface) creates sounds as requested either from an instrument of piece of software
It is not a live recording, but a synthesised sound
95
MIDI Benefits
With this system the full sound signal does not need to be transmitted, only the instructions to play the sound
It is up to the instrument to create the sound
This significantly reduces the amount of data transferred
As sounds are synthesised, they may be less realistic
96
Event Messages
A sound processor can be linked to several instruments or computers
This can send a timed sequence of event messages to:
Synchronise tempo
Control pitch
Change volume
Introduce and silence other instruments in a digital orchestra
97
What does reducing the amount of data ensure?
Data is sent more quickly
Less bandwidth is used as transfer limits may apply
Buffering on audio and video streams is less likely to occur
Less storage is required
98
Explain what is meant by lossless compression.
Patterns in the data are spotted and summarised in a shorter format without permanently removing any information
99
What is dictionary compression?
Spots regularly occurring data and stores it separately in a dictionary
The reference to the entry in the dictionary is stored in the main file thereby reducing the original data stored
Even though the dictionary produces additional overheads the space saving negates this problem
100
What is encryption?
A way of making sure data cannot be understood if you don’t possess the means to decrypt it
101
What is the caesar cipher?
The Caesar cipher is most basic type of encryption and the most insecure
Letters of the alphabet are shifted by a consistent amount
102
What is a brute force attack?
A brute force attack attempts to apply every possible key to decrypt ciphertext until one works.
103
What is the Vernam cipher?
The encryption key, also known as the one-time pad, is the only cipher proven to be unbreakable.
