Theory: Data Rep Flashcards
List and define each number system
-N is natural numbers or Z+, positive integers
-Z is all integers, positive and negative
-Q is all rational numbers, numbers that can be represented as a proper/improper fraction Q = {a/b|a,b ∈ Z , b != 0}
-R is the set of real numbers, all rational and irrational numbers, algebraic numbers
-C is complex or imaginary numbers. C ={ a+bi| a,b ∈ R , b != 0}
What set of numbers is used to describe the location of a number relative to another number?
Ordinal numbers
Which number base is used by humans for counting?
Base 10/decimal/denary
Which number base can be denoted with a subscript 16?
Hexadecimal
What is the decimal equivalent of the hexadecimal digit E?
14
Which number base is useful as a shorthand representation for binary?
Hexadecimal
What is the decimal equivalent of the binary number 0101?
5
What is the binary equivalent of the hexadecimal number A3?
10100011
What is the binary equivalent of the decimal number 14?
1110
Describe what is meant by a bit
A bit is the smallest and fundamental unit of information which can either take the value 1 or 0
How many bits are there in a byte?
8
How many bits are there in a nybble?
4
How many nybbles are there in a byte?
2
How many values can be represented with 4 bits?
16, 0-15
How many values can be represented with 20 bits?
2^20= 1048576, 0-1048575
How many bytes are there in a mebibit
2^20 = 1048576
How many bytes in a kibibyte?
2^10= 1024
Describe the uses of hexadecimals.
-third most commonly used number system, large values can be represented using fewer characters. Also easier to interpret than binary.
-colour values
-mac addresses
List the names for bit values and how many bits they represent.
-bit: smallest value, one digit
-nibble: four bits
-byte: eight bits
-(kibibyte
-
In binary multiplication, what are the respective names for the number being multiplied and what it’s being multiplied by?
-multiplicand and multiplier
Describe the concept of two’s complement
Binary numbers beginning with 1 are negative numbers, those beginning with 0 are positive
The range of possible values that can be represented:
Define the Caeser cypher and Polyalphabetic encryption.
A caeser cypher uses a given numerical key eg. 4 and each letter in a message is shifted along the alphabet by that number. Eg A becomes E.
When used with Polyalphabetic encryption, each letter of the message uses a different key.
Is 0 included in the set of natural numbers?
Yes
Every natural number greater than 1 can be written as a product of what?
Prime numbers
Calculate the highest number that can be represented with:
-16 bits
-20 bits
Where n is the number of bits, (2^n)-1
-65535
-1048575
How many bits is a hex digit equivalent to?
4 bits
eg. 1101 =13 = D
Here is an example of a MAC address; b4:f7:a1:8c:8e:d3 what is the length in bits of the mac address?
48 bits
What is the difference between a kilobyte (kB) and a kibibyte (KiB) or a gigabyte (GB) and a gibibyte (GiB)?
Kilobyte, megabyte, gigabyte etc was historically used as a less accurate representation of storage capacity. It uses base ten with the exponent increasing in powers of three to show the number of BYTES in each measurement eg. kB has 10^3 bytes, a megabyte has 10^6 bytes and a gigabyte has 10^9 bytes.
Kibibyte, mebibyte and gibibyte use base two with the exponent increasing in powers of 10 for a more accurate measurement. eg. A Kibibyte has 2^10 bytes, a mebibyte has 2^20 bytes.
How many values can be represented with
-16 bits
-20 bits
Where n is the number of bits, 2^n values can be represented
-65536
-1048576
What is word size?
The maximum number of bits that a CPU can process at one time
Add the unsigned numbers: 01001011 and 01111000
11000011
Revise subtraction with binary, borrowing
Give two situations in which overflow errors caused issues.
- 4th June 1996
A calculation for the sideways velocity of a crewless rocket carrying scientific satellites resulted in an overflow error which initiated a self destruct sequence. £240 mil damage - December 2014
Number of views on gangnam style exceeded the value that could be stored with 32 bits.
What is the place value of the MSB in a two’s complement representation?
-2^n-1 where n is the number of bits
What is 00111010 in denary (2s complement)?
Positive 58
What is 11001010 in denary (2s complement)?
Negative 54
What is 00111100 in denary?
60
Convert 11010101 into denary (2s complement).
-43
Describe the two methods of converting positive two’s complement numbers into.
- flip all bits and add 1
- flip all bits to the left of the least significant 1 (quicker)(don’t flip most significant 1)
Count up in increasing powers of 2 until 2^12
2^0 = 1
2^1 = 2
2^2 = 4
2^3= 8
2^4=16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1024
2^11 = 2048
2^12= 4096
Convert positive 25, 00011001 to -25.
11100111
How do you know the smallest number that can be stored in 2s complement?
Just the MSB place value. Eg. For eight bits the smallest number is -128
Using sign and magnitude, what number is 10011110?
-30 (first one just tells us the number is negative)
What is a downside of using sign and magnitude?
There is a positive and a negative value for 0, eg. 10000000 or 00000000
How to calculate the range of values when using two’s complement?
Both the negative and the positive values.
What is the range of denary values that can be represented using 16 bit twos complement?
-32768—–>65535
-2^15 to (2^16)–1
What does the binary weighting line look like for decimal values?
2^-1, 2^-2, 2^-3 etc
Where n is the number of bits, state what the formula is used to calculate.
2^n
(2^n)-1
2^n = number of bit patterns
(2^n)-1= highest representable number
2^n-1
Where n is the number of bits, state what the formula is used to calculate.
2^n
(2^n)-1
2^n = number of bit patterns
(2^n)-1= highest representable number
2^n-1
Define the set of natural numbers
Symbol: N , Set of numbers containing all positive whole numbers and zero
Define the set of Integers
Symbol: Z , Set of positive and negative whole numbers
Define the set of rational numbers
Symbol: Q (quotient) , Set includes positive or negative numbers that can have a fractional part (includes 0) eg 71 can be written 71/1.
Define the set of irrational numbers
-Positive or negative numbers that cannot be written as a fraction.
-Has no symbol
Eg pi, e ,root 2, root 3
Define the set of Real numbers
Symbol: R , Set includes all possible real world quantities, includes all irrational numbers and rational numbers (which in turn includes the set of integers and the set of natural numbers)
Define the set of ordinal numbers
Integers that indicate/describe a numerical position of an object in relation to another eg 1st 2nd etc
For counting and measuring, with number set is used?
-For counting, natural numbers (whole positive numbers)
-For measuring, values may not be whole so real numbers (any real world value)
Define each of the number bases
Decimal:
-uses the ten digits 0-9
Binary:
-uses two digits 0-1
-values can be represented using high or low current
Hex:
-uses ten digits 0-9 and six letters A-F
Which is the most {compact} base and why?
Hexadecimal. Represents the same number with far fewer digits. Each 1 digit in Hex is 4 digits in binary. Hexadecimal is useful as a {shorthand representation for binary}
Convert 178 into hex
= 10110010
= 1011 0010
1011= 11
0010 = 2
11= B
2 = 2
So B2 in hex
Convert C9 into decimal
C= 12
9 = 9
9 x 16^0 = 9
12 x 16^1 = 192
= 192 + 9 = 201
Define a byte
A group of 8 bits
What is the number of values you can represent with n bits
2^n (0-2^n-1)
List the power of two binary prefixes and their values
kibi, Ki = 2^10 bytes
mebi, Mi = 2^20 bytes
gibi, Gi = 2^30 bytes
tebi, Ti = 2^40 bytes
List the power of ten decimal prefixes
kilo, k = 10^3 bytes
mega M = 10^6 bytes
giga G = 10^9 bytes
tera T = 10^12 bytes
A bit is the…..
FUNDAMENTAL UNIT OF INFORMATION. CAN ONLY TAKE TWO VALUES, REPRESENTABLE USING HIGH OR LOW CURRENTS
In a byte there are…..
8 BITS
In a nibble there are…
4 BITS
How is bit and byte notated?
bit has lowercase “b” byte has uppercase “B”
How is kibibyte etc notated?
KiB, GiB, MiB, TiB
How is kilobyte etc notated?
kB, MB, GB, TB
How can you tell if a binary number is signed or unsigned?
You can’t tell, the computer needs to be told
Convert 17.5 to floating point and fixed point
010001.1
0.100011 | 0101
Convert 0.046875 or 3/64 into fixed point and floating point
00.000011
0.1100000 | 1100
Convert -29.25 to fixed and floating point.
100010.11
1.0001011 | 0101
Describe what a rounding error is.
Some decimals cannot be represented exactly in binary. For example, 1/3 or 0.3 recurring. Numbers like this can only be approximately represented. As there are so many numbers that cannot be accurately represented, both fixed point and floating point representations may be inaccurate
Define an absolute error
The amount by which a number is incorrect, the difference between the given value and the actual value.
Calculate the absolute error given that 14.6 is represented as 1110.1
1110.1 = 14.5. 14.6-14.5 = 0.1. Therefore the absolute error is 0.1
Define a relative error and give the equation
It is a measure of uncertainty in a given value compared to the actual value, relative to the size of the given value. Relative error = absolute error/actual value. This gives the value as a decimal but can be given as a percentage when multiplied by 100
Calculate the relative error for: 12.4 is represented by 1100.011. Calculate the relative error as a percentage
1100.011 is equal to 12.375. The absolute error is 12.4- 12.375= 0.025. 0.025 divided by 12.4 = 0.0020161
x 100 = 0.2016%
Give the pros and cons of floating point
Pros-
Allows wider range of numbers to be represented for a given number of bits. This is because the exponent can be adjusted in size and either positive or negative. With a large exponent and a small mantissa a wide range of values can be represented.
A small exponent and a large mantissa can also allow for high precision.
Cons-
When the exponent is large to achieve a wide range, precision is low
When the mantissa is large for precision, a small range can be achieved.
Give pros and cons of fixed point
Pros-
If the binary point is placed close to the left, high precision can be achieved
If the binary point is placed close to the right, the range is increased
Cons-
If the range is increased, precision is lower
If the precision is increased, range is lower
Lower range than floating point
Define normalisation
You know
Define underflow
When a binary number is very small and not enough bits are there to represent it. Eg. 0.015625 is 0.000001. If only six bits are available it would be represented as 0.00000 which is 0
Define overflow
When working with numbers that are larger than can be represented. Eg 127 + 1 = 128. In binary, 01111111 + 00000001, when the addition happens, 10000000 is the result, but in twos complement this is -128 which is incorrect
What does ASCII stand for
American standard code for information interchange
How many bits does ASCII use?
7 bits (128 options) plus 1 bit for error checking
What is the range of Unicode?
Uses 8-48 bits (1-6 bytes) per character (2.8 x 10^14 options)
Why is unicode used and when was it introduced?
1991, meant other alphabets could be represented as well as emojis.
What is the purpose of error checking?
To reduce the chances of incorrect data being used
List the error checking techniques
Parity bits
Majority voting
Checksums
Check digits
Explain how parity bits are used to detect errors
-a parity bit is a bit that is added onto the data being transmitted.
-it can be either odd or even parity
-for an even parity, the value of the parity bit makes the number of ones in the transmitted data even.
-an odd parity is the opposite, the value makes the number of ones odd
-a parity check is carried out when data is recieved
What is the main issue with parity checking
If an even number of bits are corrupted, the parity check will not detect an error even though there are errors
Describe majority voting
Each bit of data is transmitted multiple times. The most commonly occurring value is then taken
What is the advantage of majority voting?
It detects the error, and corrects it. There is no need for re-transmission. Can correct errors even when multiple bits have been corrupted
What is the disadvantage of majority voting?
Hugely increased volume of data being transmitted. Significantly increase time taken to transmit data
Describe checksum error checking
-the value that is added to the original data is determined by the data itself
-a simple algorithm can be carried out on the data to determine the checksum
-eg. Mod 8
-the value is appended to the data
-the receiver checks if the appended value matches when they perform the same calculation.
-if it doesn’t the value is re-transmitted
Explain check digits in error checking
A type of checksum that generates only a single digit to be appended to the data. The number of different algorithms that can be used is fewer so the variety of errors it can detect is lower.
What is the difference between analogue and digital data?
Analogue data is continuous, there is no limit to the value the data can take. Analogue signals can take any value and change as frequently as required.
Digital data is discrete, it can only take certain values. Digital signals must take one of a specified range of values and change at specific intervals
Explain digital to analogue conversion.
- DAC is used.
-device reads a bit pattern representing analogue signals, and outputs an alternating analogue electric current (signal).
Describe analogue to digital conversion
-hardware like a microphone or temperature sensor outputs an analogue signal.
-an ADC is then used to convert the analogue signal into a digital bit pattern.
-this works by taking a reading of the analogue signal at regular intervals and recording the value. (Sampling)
Describe samples taken in analogue to digital conversion
Samples are taken at a frequency given in hertz, this is the number of samples taken per second, or the sampling rate. A high sampling rate means better quality sound (more accurate reproduction of analogue signals)
What is the resolution of an image?
Can refer to the number of pixels per square inch, or the number of pixels in an image in total
Define colour depth
The number of bits assigned to each pixel. A greater colour depth means more colours can be represented, so a more accurate image. With n bits, 2^n colours can be represented
How do you calculate the size of an image?
Number of pixels (width x height) x colour depth
How do you calculate the size of an audio file
Sample resolution (number of bits) x sampling rate x time (s)
Why is the calculation of the file size most likely not correct?
It is the minimum value, there is likely also metadata
How do vector graphics work?
Represents images using geometric objects. The properties of each shape is stored in a list
What are the advantages of vector graphics over bitmapped images?
-can be scaled without losing quality, bitmap becomes blurry/pixelated
-good for simple images
-use less storage space
What is an advantage of bitmap over vector?
-vector is no good for photographs
Define the Nyquist theorem
States that the sampling rate of the audio file must be at least twice the frequency of the sound. If the sampling rate is below the sound will not be accurately represented
What is MIDI
Musical Instrument Digital interface
Describe MIDI
Is used with electronic musical instruments that connect to computers. It doesn’t take samples, but stores sound as a series of event messages, each represents an event in the piece. Like a series of instructions that can be used to recreate a piece of music.
What information could be in an event message?
-duration of a note
-Instrument used
-how loud it is
-if a note should be sustained
What are the advantages of MIDI?
-Allows easy manipulation of music without loss of quality
-notes can be transposed (switch places) and the duration altered
-smaller file size
-lossless
What are disadvantages of MIDI?
-can’t be used with speech
-can result in less realistic sound
Why are files compressed?
To reduce file size. Smaller files can be transferred faster
What are the categories of compression?
Lossy, lossless
What is lossy compression?
-some information is lost in compression
-eg. Reducing resolution of an image or removing undetectable frequencies from audio files
What is lossless compression?
-no data is lost in compression
-file size is reduced without a loss in quality.
-eg .wav is lossless compression for audio
What are the two methods of lossless compression?
RLE (run length encoding) and dictionary based methods
How does RLE work?
Removes repeated information by replacing it with one occurrence of the repeated data followed by the number of repetitions. This only fails when there is no repeated information
Describe dictionary methods of compression
Works like a dictionary: when compressed, a dictionary containing repeating information is appended to the file. A disadvantage of this is that the dictionary needs to be stored in the file which will initially increase file size, especially if there is no repeating data
What is a disadvantage of lossless?
The amount a file can be compressed is limited, where its unlimited with lossy
Why is encryption done?
To keep data secure during transmission
What are key encryption terms?
Unencrypted information = plaintext
Encrypted information = ciphertext
(Cipher is encryption method)
What is a substitution caeser cipher?
The letters are randomly replaced in the ciphertext
What is the disadvantage of caeser ciphers?
Shift ciphers can be easily cracked by looking at the frequency by which certain characters occur, once one character is discovered, the entire ciphertext can be decoded
Describe a vernam cipher
A ONE TIME PAD cipher, the key is only used ONCE. the key must be random and at least as long as the plaintext.
Explain each step of a vernam cipher.
-align the character codes (bitcodes) of the plaintext and the key.
-perform a XOR operation on each pair of character codes.
-convert the resulting bit patterns into their corresponding characters. This is the ciphertext
What is the advantage of vernam cipher?
As the key, and therefore the ciphertext are random, the vernam cipher is mathematically proven to be completely secure
What is the disadvantage of the vernam cipher?
The key must be exchanged between the sender and the recipient in some way, then destroyed.
All ciphers other than the Vernam cipher…..
Are, in theory, crackable. However not within a reasonable timeframe for current computing power. Ciphers relying on this form of security, relying on COMPUTATIONAL SECURITY
