CS - Paper 2

Natural numbers

• all positive integers, including 0

• symbol → N

• used for counting

Integer numbers

• all positive and negative integers

• symbol → Z

Rational numbers

• set of numbers that can be written as fractions

• symbol → Q

Irrational numbers

• set of numbers that cannot be written as a fraction

• e.g. root 2 or pi

Real numbers

• set of all possible real world quantities

• symbol → R

• used for measurement

Ordinal numbers

• when objects are placed in an order

• e.g. 1st, 2nd, 3rd

Number bases

• decimal → base 10, subscript 67₁₀

• binary → base 2, subscript 10011011₂

• hexadecimal → base 16, subscript AE₁₆

why is hexadecimal used

• as a shorthand for binary

• easier for humans to read and error check

• e.g. colours

bit

• fundamental unit of information

• either 0 or 1

byte

8 bits

how many values can be represented by n bits

2ⁿ, e.g. 2³=8, can represent 8 different values

Kibi

2¹⁰ → Ki

Mebi

2²⁰ → Mi

Gibi

2³⁰ → Gi

Tebi

2⁴⁰ → Ti

Kilo

10³ → k

Mega

10⁶ → M

Giga

10⁹ → G

Tera

10¹² → T

what is signed binary

when the most significant bit is used as a placeholder for sign rather than a value, 0=+ and 1=-

minimum and maximum number of bits for unsigned binary

minimum → 0

maximum → 2ⁿ-1

two’s complement

most significant bit represent -2^n-1 e.g. 1000₂=8

range from -2^n-1 to 2^n-1-1

fixed point binary

• binary point fixed between a set number of bits

• e.g. 0000.0000

• not as precise

• greater speed of calculation

• only when data is known to be within a certain range

Floating point binary

• binary point can float between number of bits

• mantissa and exponent

• lower speed of calculation

• more memory to store mantissa

• greater precision

• for greater range of values

mantissa

represents value with decimal after first bit

exponent

represents position of point to convert to actual value

why might fixed/floating point binary be inaccurate

• for a real number to be represented exactly by the binary number system it must be capable of being represented by a binary fraction in the given number of bits

• some cannot every be represented exactly, e.g. 0.1₁₀

Absolute error

• difference between the actual number and the binary value

• e.g. 1/3 accurately would be 0.01(recursively), if rep by 4 bits, 0.0101=5/16, absolute error 16/48-15/48=1/16

Relative error

• percentage difference between the actual number and binary value

• using 1/3 and 4 bits = 5/16 divided by 1/3=15/16

Why are floating point numbers normalised

to store a greater range of values, reduces need for repeated binary values

what is normalised binary

• starts with 10 or 01

• uses two’s complement floating point binary

how to normalise floating point binary

1. convert into fixed point

2. adjust exponent accordingly

3. if number starts with >one 1, cut them off (will be added when converted)

underflow

• not enough bits available to represent a number therefore would cut off the least significant bit

• e.g. 0.00001 with only 5 bits would be 0.0000

overflow

• significant when using signed binary as if you were to add 127 and 1 using 8 bits, answer would be -128 hence overflow has occurred

differentiation between character code, decimal digit and pure binary representation

Character code representation (like ASCII) treats digits as symbols (e.g. 5 is 53 in ASCII), while pure binary representation directly converts the digit's value (5 becomes 101 in binary)

ASCII

way of representing characters with seven bits; later extended to eight

Unicode

16 to 32 bits, created to represent more languages and symbols, now have more storage

why error check

bits can change erroneously due to interference, need to verify

Parity bits

• additional bit used to check that the other bits transmitted are likely to be correct, very efficient

• odd or even parity, used to ensure that total number of 1s in each byte (inc. parity) equals an odd or even number e.g. 01010010 → odd parity

Disadvantage:

• if there are two 1’s in an even parity, 4 bits being transmitted would not cause error and if error occurs, need to retransmit data

Majority voting

• data transmitted multiple times, most commonly occurring value taken to be correct

• corrects error - no need for retransmission but volume of data being transmitted increased(takes longer hence less efficient)

checksum

• algorithm applied to data to determine checksum, e.g. modulo to return division remainder

• value appended to original in binary (put on end)

• recipient removes checksum and applies same algorithm to ensure this matches (efficient when algorithm is not complex)

• cannot correct the error, must retransmit

check digit

• type of checksum where only single digit added to transmitted data

• reduces number of different algorithms that could be used, reduces variety of errors that can be detected - efficient

how can bit patterns be used to represent images/sound

• images can be stored using the images height and width in pixels with the colour depth

• sound can be stored as digital samples of the original sound.

analogue data

• continuous and has no limits

analogue signal

• can take any values

• changes frequency as required

digital data

• discrete, represents particular values

digital signal

• takes range of values

• changes frequency at specific intervals

ADC

Analogue to Digital Converter

• samples the data (takes readings at regular intervals and records frequency)

• frequency → no. samples/second, increased better but uses more space as increased number of bits

• used with analogue sensors

  • e.g. temperature sensors or microphones

DAC

Digital to Analogue Converter

• reads bit pattern representation of analogue signal and outputs alternating, analogue, electrical current

• mostly for audio, e.g. speakers

How are bitmaps represented

image broken into pixels, each of which have a binary value assigned

resolution

number of dots per inch, where a dot is a pixel

colour depth

number of bits stored for each pixel

size in pixels

width of image in pixels x height of image in pixels

storage requirements for bitmapped images ignoring metadata

storage requirements = size in pixels x colour depth

typical metadata

• width

• height

• colour depth

• date created

how vector graphics represent images

• uses list of objects containing the properties of each geometric object/shape

typical vector properties of objects, e.g. rectangle

• width

• height

• position

• fill

  • colour

Vector graphics evaluation

• scaled without loss of quality

• better for simple images but worse for photographs

• less storage space

bitmapped graphics evaluation

• enlargement = blurry

• better for photographs

• information stored for each pixel hence more storage space

sample resolution

• number of bits per sample

• higher sample resolution = higher audio quality = greater file size

sample rate

number of samples per second

Nyquist Theorem

sample rate must be at least twice the frequency of the sound or it is not accurately represented

calculate sound sample sizes in bytes

duration of sample x rate x resolution

describe the purpose of MIDI and its use of event messages

• used with electronic musical instruments connected to computers stores sound in event messages

• event messages can hold duration of note, instrument note is played by, volume, if sustained, etc.

Advantages of using MIDI files to represent music

• easy manipulation without loss of quality (instrument can be changed)

• often smaller file size and lossless

• cant be used for storing speech

• often less realistic

why are files often compressed

to reduce file size, hence can be transferred faster

Lossy compression

• some information lost

• can reduce resolution, e.g. image or audio, as extent of reduction unlimited

Lossless compression

• no information lost

• e.g. run length encoding and dictionary based methods

Run Length Encoding

removing repeated information and replacing with one occurrence followed by number of times repeated

e.g. pixels of same colour

dictionary-based methods

dictionary containing repeated data is appended to the file

e.g. for ‘keep calm keep happy’ could be 1213, with ‘keep’ value having a key of 1

encryption

process of scrambling data so it cannot be understood if cannot be understood if intercepted (secure during transmission)

what is needed to decrypt

• method

• key used

ciphertext

encrypted information

plaintext

unencrypted information

Caesar cipher vs Vernam cipher

Caesar → imperfect

Vernam → perfect

opposite extremes of ciphers that are computationally secure

Caesar ciphers

• by replacing characters, cipher kept constant

Shift ciphers:

• each letter shifted by same amount (key) in the alphabet

Substitution cipher

• letters randomly replaced, a little harder to crack, usually based on frequency/logic

The vernam cipher

• key is chosen uniformly at random

• ciphertext distributed uniformly

• key only used one → one-time pad

• mathematically proven to be completely secure

Vernam cipher - method

1. align characters of plaintext and key

2. convert character to binary

3. apply XOR to the two bit patterns

4. convert back to character

Vernam ciphers vs ciphers that depend on computational security

in theory, every cryptographic algorithm except for vernam cipher can be broken, given enough ciphertext and time

hardware

physical components (e.g. hard drive, printer, speaker)

software

sequency of instructions which are executed to perform a task - program code

system software

operates, controls, and maintains the computer and its components

• operating system, utility programs, library, programs, translators

application software

programs that complete specific tasks for the user (e.g. word processor)

operating system

• handles resource management, managing hardware to allocate processors, memories, I/O devices among competing processes, and interrupts

• to hide the complexities of the hardware

utility programs

housekeeping tasks:

• backup

• defragmenting hard drives

• compression

• encryption

libraries

contain useful functions frequently used by programs to simplify process

imported into the program

translators

• translate different types of languages to machine code

• e.g. assemblers, compilers, interpreters

low-level languages

specific to the type of processor

e.g. machine code and assembly language

machine code

binary

• very long and difficult to understand and debug - prone to errors

• direct, not constrained, better for embedded and real-time applications

machine code

mnemonics

• more compact, less error prone

• one to one relation with machine code

high level languages

include imperative high-level language

• not platform specific but needs to be translated by compiler/interpreter before execution

• use English instructions and mathematical symbols

• easier to understand, learn, and debug as it uses named variables and indentation

• built in functions to save time

imperative high level languages

formed from instructions that specify how computer should complete task

declarative description - what

assembler

translates assembly language to machine code

they have a 1:1 relationship so translation quick but platform specific

compilers

high level → machine code (platform specific)

high level taken as source code, checked for errors and code translated at one if no error is detected

once translated, can be run without any other software

interpreter

• high level to machine, line by line

• procedures that can be used to interpret each kind of program instruction

• checks for errors as it goes (can be partially translated until error reached)

• both source and interpreter must be present (poor protection of source)

why is intermediate language (bytecode) produced as the final output by some compilers

Source code (only translated once so it can be executed on a variety of processors) → immediate (often bytecode) →machine code

allows platform independence as it uses a virtual machine to execute on different processors

source code

input to translators

object code

output from translator

logic gates - NOT

NOT(1) = 0

Logic gates - AND

1 AND 0 = 0

1 AND 1 = 1