Section 5 - Data Representation (copy)

Rational Numbers (Q)

Rational Numbers (Q)

Can be written as a fraction between two integers, where the denominator is non-zero

Integers (Z)

Natural numbers is a subset of Integers. All integers are rational numbers

Natural (N)

All positive whole numbers. Includes 0 and is any number that is used for counting.

Irrational Numbers (R)

Can’t be expressed as a fraction and has an endless series of repeating digits. (e.g. pi or e)

Cardinal Numbers

one, two, three …

Ordinal Numbers

Used to tell the position of an object when objects are placed in order

Benefits of hexadecimal

Takes up less space on the screen, less error prone, easier to understand by a human; easier to debug

Examples of Uses of hexadecimal

Colour codes in HTML; memory dumps; MAC addresses; error codes

Tera

x10^12

Giga

x10^9

Mega

x10^6

Kilo

x10^3

Mili

x10^-3

Tebi

x1024^4

Gibi

x1024^3

Fixed point

Total of 8 bits, 5 before binary point and 3 after binary point (assume unsigned)

Floating point

Floating point normalised. Always in twos complement

Rounding error

When a given number cannot be represented completely accurately (e.g. 1/3)

Absolute error

The difference between the number you need to store and the number you CAN store

Relative error

A calculation in % of the absolute error out of the actual number

What does the effect/impact of an error depend on? (numbers)

Its size relative to the number that is/should be represented. Absolute error is more significant the smaller the number that is/should be represented

Disadvantages of Fixed Point

Limited range of numbers can be represented

Character Sets

Collection of character and symbols that can be represented by a computer.

Underflow

Result of a calculation is a number too small to be represented in the number of bits available

Overflow

Result of a calculation is a number too large to be represented in the number of bits available

ASCII

coding system used to represent all keyboard characters and their combinations, uses 7 bits (128 characters) or 8 bits (256 characters) for ASCII extended

Unicode

Uses 16 bit codes (UTF-16) which equals to 4 hex digits which is enough for most languages on the planet

Check Digit

Additional digit at the end of a string of numbers, designed to check for mistakes in input or transmission. Is calculated with some algorithm usually modulo 10 or modulo 11

Examples for uses of check digits

Used in barcodes, ISBN or EAN

Parity Bits

appended in MSB to binary string before transmitted. Sender and receiver agree on odd or even parity. The sender counts the number of 1s in the binary string and compares its parity with its own parity type. If the same, parity bit = 0, if different parity bit = 1. Receiver counts number of 1s, same parity then assume successful transmission, else, signal error and request retransmission

Disadvantage of parity bits

If an even number of bits gets corrupted, this method can’t detect the error

Majority Voting

Each bit is sent 3 times and the receiver analyses each group of 3 consecutive bits. If there is any discrepancy, it assumes that the most frequently occured bit is correct.

Disadvantage of Majority Voting

Volume of data sent is tripled, slows everything down

Advantage of Majority Voting

Can detect and correct the error

Checksum

Sender totals all bytes in data using algorithm. Sum is sent with the data. Receiver recalculates checksum using same algorithm. Compares with received checksum. If the same, assume successful transmission, if different signal error and request retransmission.

Negative Binary

This uses two’s compliment where if the first digit is a 1 it tells the computer it is negative.

The Negative Range

-(2^(n-1)) . . . 2^(n-1) -1

Greatest Decimal

15.9375

Bitmaps

Images made of pixels

Disadvantage of bitmaps

Larger file size

Pixel

the smallest addressable picture element; contains ONE colour

Process of capturing an image with a digital camera

1. Camera breaks up what it ‘sees’ through its lens into a grid of pixels

2. A light sensor (CMOS or CCD) measures its intensity of colour in each pixel

3. Each measurement is converted to digital using an ADC

Types of bitmap file types

.bmp, .jpg, .gif, .png, .tiff

Resolution

number of pixels used to make the bitmap; width x height (in pixels); sometimes measured in dpi (dots per inch)

Colour Depth

The number of bits allocated to represent the colour of a pixel

File Size

Resolution x Colour Depth

Vector Graphics

Created using lists of objects and coordinates. Made of primitives (points, lines, curves)

Uses of vector graphics

CAD packages, 2D and 3D animation programs; chart, logo, map, plan, clipart

Advantages of Vector Graphics

• individual objects of the image can be manipulated independently

• can be easily scaled without loss of quality

• if an object is deleted the software knows what is behind it so no hole is left in the image

• vector graphics are resolution independent

• images saved as vector graphics typically take up less storage space

Advantages of bitmap images

• Can represent images with complex textures

• Can represent images that are not composed of regular shapes

• Scanned images are naturally represented as bitmaps because of the way they are taken

Principles of operation for an Analogue to Digital Converter

• Analogue signal is sampled at regular time intervals

• Amplitude of sound wave at each sample point is measured

• Measurement coded into a fixed number of bits

Bit Depth/Resolution (SOUND)

Maximum bit amplitude of the waves for each sample. Provides 2^n amplitude

Sample Rate/Frequency (SOUND)

Number of samples per second

File Size (SOUND)

resolution x frequency x length (seconds)

To improve sound quality:

• Increase sample frequency

• Increasing bit-depth, amplitudes can be recorded closer to actual values

Nyquist’s Theorem

To faithfully recreate the analogue signal, a sample should be taken at least twice the highest frequency. The reason for doubling the frequency is to ensure that the sample covers the complete range of peaks and troughs in the analogue signal, which then allows for a faithful reproduction of the sound

MIDI

Music Instrument Digital Interface; a protocol that allows computers, musical instruments and other hardware to communicate, a communication standard that allows digital music gear to speak the same language

How is music represented in MIDI

Represented as a sequence of MIDI event messages. Playback of music is the combination of event messages with a specific ordering. Data in a message may be: note on/off, velocity, pitch, volume, key pressure. MIDI messages usually 2-3 bytes long. First byte of each message is a status byte

How long are MIDI messages

Usually 2 to 3 bytes long. First byte is status byte others are data byte. Status bytes are divided into a command and a channel number

Advantages of MIDI

• More compact representation

• Easy to edit notes

• Simple method to compose algorithmically

• Musical score can be generated directly from a MIDI file

• No data lost about musical notes through sampling

Lossy compression

Insignificant parts are removed to permanently decrease the file size. → Sound, images and videos.

Lossless compression

Repeated sections or phrases are saved under the same variable, decreasing the file size (not as much as lossy) but still smaller than the original. → Word documents.

Run Length Encoding (RLE)

A run is a sequence of pixels of the same colour which includes a run length and the colour of the pixels in the run

Disadvantages of RLE for a photograph

not save much space because runs will be of shorter length as images may contain a lot of different colours. Additional run length data may cancel out or outweigh reduction in storage of colour data

Dictionary Based Compression

Compression algorithm search through messages + collects all terms to create its own dictionary. Each value is assigned to a binary and decimal value. This allows for the location of the words to be sent alongside the dictionary. This reduces data for transmission unless the dictionary is sent with it.

Computationally secure

cipher that is theoretically breakable but not when using current technology in a timeframe that would be useful

Caesar Cipher

Shifting letters in the alphabet to change the letters in the message all by a certain amount. Simple to break as frequencies of letters can be used.

Weaknesses of Caesar Cipher

• Each character always encrypted to the same letter

• Characters in ciphertext will have the same frequency as corresponding characters in plaintext (easy to work out shift)

• Ciphertext susceptible to frequency analysis

Why a substitution cipher is harder to crack than Caesar

• More possible keys

• Not possible to work out how other characters have been encrypted directly from the knowledge of one encrypted character

• No pattern in letter replacements

Vernam Cipher

The Vernam cipher is an example of a one-time pad cipher. This means that each key should only ever be used once. Additionally, the Vernam cipher requires the key to be random and at least as long as the plaintext that is to be encrypted.

Key used in Vernam Cipher

Sequence of letters that should be at least as long as the plaintext that is being encoded

One-time pad

• Provides perfect security.

• Can only be used once.

• The sender and recipient must meet in person, share the key then destroy it after decryption.

Bitwise Exclusive XOR

The binary for each character (in binary) is run through an XOR gate alongside a random characters binary. This random character is generated by the one-time pad. Each character will then form a new character which’ll be the cipher text.

Normalising Floating Point

Removing redundant 0s or 1s after the binary point

Why normalising floating point is important

Allows number representation with maximum level of precision for a given number of bits. Unique representation of each number

Why floating point is better than fixed point

Allows a far greater range of numbers for the same number of bits. Can represent very large and very small numbers. Precision is also increased by comparison with fixed point

Character code

A unique number used to represent a character

Why Unicode was introduced

Support a larger range of characters, requirement to use additional symbols and facilitate interchange of documents between countries

Metadata

data about data; creation date, width/height, colour depth