Computer Science Notes - Data Representation

Flashcards from lecture notes on number systems, data representation, compression, and computer architecture.

Natural Numbers

A whole number that is used in counting. ℕ={0,1,2,3,4,…}

Integer Numbers

Any whole number. ℤ = { …, -3, -2, -1, 0, 1, 2, 3, … }

Rational Numbers

Any value that can be expressed as a ratio, or fraction. Includes integer values (e.g. 15 = 15/1)

Irrational Numbers

Numbers which cannot be expressed as fractions and which have an endless series of non repeating digits. E.g. pi, square root of 2 etc.

Real Numbers

Any natural, rational or irrational number.

Ordinal Numbers

Numbers that describe the numerical position of objects. E.g. first place in a race, second turn on the left.

Denary

Base 10 (e.g. 110, 210, 310)

Binary

Base 2 (e.g. 100100102)

Hexadecimal

Base 16 (e.g. A110)

Why is Hexadecimal used?

As a shorthand for binary, since it’s simple to represent one byte in just 2 digits - Fewer mistakes are likely to be made - Easier for technicians and computer users to write and remember a hex number than a binary number - Often used to represent RGB values

Bit

The fundamental unit of information in the form of either a single 1 or 0. A byte = 8 bits. 2n values can be represented by n bits. For example, 28 values can be represented by 8 bits. This is equal to 256 bits.

Parity bits

An additional bit that is used to check that the other bits transmitted are likely to be correct.

Limitations of parity bit

it cannot tell which bit is corrupted and it cannot detect if 2 bits have been corrupted, as the total would not change from odd to even or from even to odd. Another limitation is that parity bits cannot prevent corrupted bits, only detect them.

Majority Voting

A system that requires each bit to be sent three times. If a bit value is flipped mistakenly during transmission, the recipient would take the most commonly occurring value to be correct.

Checksum

A mathematical algorithm that is applied to a packet of data. Similar to parity bits, it involves adding a value to the transmission of data.

Check Digits

Similar to checksums, check digits are an additional digit at the end of data. Can detect a smaller variety of errors.

Unsigned Binary

Can only represent positive numbers.

Signed binary

Can represent both positive and negative numbers. In two’s complement signed binary, the most significant bit determines whether the number will be positive or negative.

Absolute Error

The difference between the number to be represented and the actual binary number that is the closest approximation in the given number of bits

Relative Error

The absolute error divided by the number trying to be represented. May be expressed as a percentage

Underflow

Occurs when a number is too small to be represented in the allotted number of bits.

Overflow

Occurs when the result of a calculation is too large to be held in the allotted number of bits.

Analogue to Digital Conversion

Microphone converts sound energy into electrical energy, The ADC samples the analogue data at a given frequency, measuring the amplitude of each point of the wave and converting it into binary values according to the resolution used for each sample ADCs are used with analogue sensors The most common use for a DAC is to convert a digital audio signal into an analogue signal.

Analogue Data

Is continuous. There are no limits to the value that the data can take.

Digital Data

Is discrete, meaning it can only take particular values. Accordingly, analogue signals can take any values and can change as frequently as required. Digital signals however, must take one of a specified range of values and can only change value at specified intervals.

Pixel

The smallest identifiable area of an image.

Resolution

Width in pixels x height in pixels.

Colour Depth

Number of bits to a pixel

Metadata

Data about data, including width in pixels, height in pixels, and colour depth.

Sample Resolution

The number of bits allocated to each sample. Higher sample resolution results in greater audio quality but also increased file size

Sampling Rate

The frequency with which you record the amplitude of the sound.

MIDI

A technical standard that describes a protocol, a digital interface and a standard set of connectors. It allows electronic musical instruments to communicate with computers and each other.

Lossless Compression

Compression that works by recording patterns in data rather than the actual data. Using these patterns, the computer can reverse the procedure and assemble data with exact accuracy

Lossy Compression

Compression that works by removing non essential information. Examples include reducing resolution of an image, lowering the sample resolution of a sampled audio file etc.

RLE (Run Length Encoding)

A form of lossless compression, meaning it encodes data which it can then recreate. Ideal for reducing file size of bitmap images. Works by removing repeated info and replacing it with once occurrence of the info followed by the amount of times it is to be repeated.

Dictionary Based Compression Techniques

A compression method that replaces repeated patterns (such as words or sequences) with shorter codes using a dictionary. The algorithm builds a dictionary of commonly occurring data and assigns a unique binary code to each entry.

Encryption

Transformation of data from one form to another to prevent an unauthorised third party from being able to understand it.

Caesar Cipher

A type of substitution cipher that works by shifting the letters of the alphabet by a given number of characters, with the parameter being the key.

Vernam Cipher

A one-time-pad cipher which offers perfect security. A one time pad key means the key can only be used once and then destroyed.

Hardware

The term used to describe the electrical or electr0-mechanical parts of a computer. E.g. CPU, graphics card, monitor

Software

Composed of all programs that are written to make a computer function. E.g. word processor, image editor

Application Software

The programs needed to run the computer’s hardware and application programs. Can be split into general purpose and bespoke software.

System software

Includes operating systems, utility software, libraries and translators

Disk Defragmenter

A program that reorganises a hard disk so that files which have been split up into blocks are recombined in a single series of sequential blocks.

Virus Checker

Checks hard drive, incoming emails and internet downloads for viruses and removes them.

Operating System

A set of programs that lies between applications software and the computer hardware. Its functions include resource management, provision of a user interface and more.

Libraries

Ready-compiled programs which can be run when needed, and which are grouped together in software libraries.

Translators

Programs that translate program code written by a programmer into machine code which can then be run by the computer

Operating System

A set of programs that manages the operations of the computer for a user. The OS is held in permanent storage.

Memory Management

The allocation and management of memory is controlled by the operating system. When the RAM is not large enough to store all programs at once, it can use virtual memory.

Processor Scheduling

When multiple programs are running simultaneously, the OS is in charge of allocating processor time to each one as they compete for the CPU. The scheduler is the OS module responsible for this.

Backing Store Management

When files are loaded, they are transferred from backing storage into memory.

Peripheral management

Orchestrates communication between peripheral devices, and ensures peripherals are allocated to processes without causing conflicts

Address Bus

Unidirectional bus used to transport memory addresses, specifying where data is to be fetched from or sent to.

Data Bus

Bi directional path for moving data and instructions between system components. It actually carries the binary data moving between components.

Control Bus

Bi-directional bus that carries command and control signals to and from every component of the CPU.

I/O Controllers

Pieces of hardware that control the communication of data between the processor and peripheral devices, e.g. mouse, monitor etc.

Processor

Responds to and processes the instructions that drive the computer. Contains the control unit, arithmetic logic unit, and registers. Operates by continuously repeating the fetch-execute cycle.

Main memory

Used to store program instructions and frequently used data. Includes ROM and RAM. Much faster than secondary storage, so storing frequently used data on main memory allows the processor to execute instructions quickly.

Bus

A series of parallel wires that connect internal components of a computer system, allowing signals to be passed between them.

First Computers

The first computers were conceived in the 1940s strictly for military purposes. At the time, the only way of programming a computer was to enter the binary digits that the computer could understand, This was called machine code.

FORTRAN

In the 1960s, John Backus made the first high level language called FORTRAN.

Assembly Language

Each opcode was replaced by a mnemonic, which gave a good clue as to what the operator was actually doing

Imperative high level languages

Are formed from instructions that specify how the computer should complete a task: It lets programmers write code that tells the computer what to do in logical steps without needing to worry about how it’s done in machine code.

Assembler

A program that translates assembly language into equivalent machine code so that it can be executed. The assembler converts each instruction into 0s and 1s of the corresponding machine code instruction.

Instruction Set

The machine code instructions a particular computer can execute. Each computer has an instruction set specific to its hardware, so assembly language and instruction sets of computers differ between computer to computer.

Compiler

A program that translates a high-level language into machine code. They work by checking the source code for any errors, then translating the whole program at once

Interpreters

A type of programming language translator that translates high level language programs into machine code line by line. The interpreter software itself contains subroutines to carry out each high-level instruction.

Bytecode

An intermediate language, which means it is neither high-level or low-level. It is the output of some compilers which do not directly translate source code into machine code, but into an intermediate language first.