A level computer science p1

Learning Objectives

  • Understanding binary magnitudes and differences between binary and decimal prefixes.

  • Understanding the basis of different number systems.

  • Performing binary addition and subtraction.

  • Describing practical applications of Binary Coded Decimal (BCD) and Hexadecimal.

  • Representing character data in its internal binary form based on the character set.

  • Understanding how data for a bitmapped image is encoded.

  • Estimating file size for a bitmap image.

  • Understanding the effects of changing bitmap image elements on image quality and file size.

  • Understanding how data for a vector graphic is encoded.

  • Justifying the use of bitmap or vector graphics for a given task.

  • Understanding how sound is represented and encoded.

  • Understanding the impact of sampling rate and resolution.

  • Understanding the need for and examples of compression.

  • Understanding lossy and lossless compression and justifying their use.

  • Understanding how text files, bitmap images, vector graphics, and sound files can be compressed.

1.01 Number Systems

/

  • Denary Numbers: Base-10 number system using digits 0-9.

  • When a number is written, its value is determined by the place values of the digits.

  • Example: 346 = (3 \times 10^2) + (4 \times 10^1) + (6 \times 10^0)

  • Binary Numbers: Base-2 number system using bits 0 and 1.

  • A bit is a binary digit.

  • Example: 1011102 = (1 \times 2^5) + (0 \times 2^4) + (1 \times 2^3) + (1 \times 2^2) + (1 \times 2^1) + (0 \times 2^0) = 32 + 8 + 4 + 2 = 46{10}

  • Computers use binary because they operate using two states: on and off.

  • Binary codes, often in groups of eight bits (a byte), are used to represent various data.

  • Byte: A group of eight bits.

  • Nibble: A group of four bits.

  • Hexadecimal Numbers: Base-16 number system using digits 0-9 and letters A-F.

  • A represents 10, B is 11, C is 12, D is 13, E is 14, and F is 15.

  • Example: 2A6{16} = (2 \times 16^2) + (10 \times 16^1) + (6 \times 16^0) = 512 + 160 + 6 = 678{10}

  • Hexadecimal is used because each nibble can be represented by one hexadecimal digit, and each byte by two hexadecimal digits.

  • Example: Binary 00001010 = Hexadecimal 0A = Denary 10; Binary 11111111 = Hexadecimal FF = Denary 255.

  • Hexadecimal representations are seen in memory dumps and character code charts.

  • Octal Numbers: Base-8 numbers; less common in computer science and can be ignored.

Converting Between Binary and Denary Numbers

  • Binary to Denary: Sum the place values for every digit that has a value of 1.

  • Alternative method: Start at the most significant bit, successively multiply by two and add the result to the next digit.

  • Denary to Binary: Identify the largest power of 2 that is less than the denary number, write down the binary representation of this power of 2 value (1 followed by zeros). Subtract this power of two value from the denary number then repeat, replacing zeros in the binary representation with ones until the denary number is fully accounted for.

  • Alternative approach: Successive division by two with the remainder written down at each stage. The converted number is then given as the set of remainders in reverse order.

Conversions for Hexadecimal Numbers

  • Convert Hexadecimal to Denary by multiplying the digit by its place value:
    678 = (2 \times 16^2) + (10 \times 16^1) + (6 \times 16^0) = 512 + 160 + 6

  • The sensible approach is to first convert the hexadecimal number to a binary number, which can then be converted to denary.

  • To convert a hexadecimal number to binary, each digit is treated separately and converted into a 4-bit binary equivalent (e.g., F converts to 1111).

  • To convert a binary number to hexadecimal, start with the four least significant bits and convert them to one hexadecimal digit. Proceed upwards towards the most significant bit, successively taking groupings of four bits, converting each grouping to the corresponding hexadecimal digit.

1.02 Numbers and Quantities

  • Types of Numbers:

    • Integer: Whole number (e.g., 3, 47).

    • Signed Integer: Integer with a sign (+ or -) (e.g., -3, +47).

    • Fraction: Number expressed as a ratio (e.g., 2/3, 52/17).

    • Decimal: Number with a whole part and a fractional part (e.g., -37.85, 2.83).

    • Exponential Notation: Number expressed as a value × 10exponent (e.g., -3.6 × 108, 4.2 × 10-9).

  • Large values can be written in exponential notation or with a prefix to the unit to define its magnitude (e.g. 23 567 m, 23.567 × 103 m, 23.567 km).

  • Decimal Prefixes: Prefixes representing factors of 10.

    • kilo (k) = 10^3

    • mega (M) = 10^6

    • giga (G) = 10^9

    • tera (T) = 10^{12}

  • Binary Prefixes: Prefixes used to define magnitudes as powers of 2.

    • kibi (Ki) = 2^{10} = 1024

    • mebi (Mi) = 2^{20}

    • gibi (Gi) = 2^{30}

    • tebi (Ti) = 2^{40}

  • When presenting numbers, use either one or two denary digits before the decimal point.

  • If performing calculations with values quoted with different magnitude factors, convert them to the same factor first.

1.03 Internal Coding of Numbers

  • Focus is on coding integer values. Non-integer numeric values (real numbers) are covered elsewhere (Chapter 16).

  • Coding for Integers:

    • Simple positive integers are stored as binary numbers, determining the number of bytes to be used.

    • Two bytes (16 bits) can represent values from 0 to 2^{16} – 1, which is 0 to 65,535.

  • Signed Integers:

    • ‘Sign and magnitude representation: Binary code for the value with an extra bit to define the sign (0 for +, 1 for -).

    • Signed integers are commonly stored as two’s complement form.

    • One’s complement: Obtained by subtracting each digit in a binary number from 1 (switching each 0 to 1 and vice versa).

    • Two’s complement: The one’s complement of a binary number, plus 1.

  • Converting to Two’s Complement:

    • Quick method: Start at the least significant bit and move left ignoring any zeros up to the first 1, which you also ignore. Change any remaining bits from 0 to 1 or from 1 to 0.

  • Representing Denary Integer Values as Two’s Complement:

    • Positive: Convert the denary value to a binary value and add a leading 0.

    • Negative: Disregard the sign, convert the denary value to a binary value, add a 0 in front of this binary value, and convert this binary value to its two’s complement form.

  • Converting a Two’s Complement Binary Number to Denary:

    • Positive: Ignore the leading zero and convert the remaining binary to denary.

    • Negative: Method 1: Convert the two’s complement to the corresponding positive binary number, then convert to denary before adding the minus sign.

    • Method 2: Sum the individual place values but treat the most significant bit as a negative value (e.g., if leading bit is a 1, treat it as -128 instead of +128).

Points to note about two’s complement representation:
* There is only one representation of zero.
* Adding 1 to an all-ones code rolls over to an all-zero code.
* Adding a leading zero to an unsigned binary value converts it to the two’s complement representation of the corresponding positive number.
* Two’s complement values are self-complementary.
* Add any number of leading zeros to a representation of a positive value without changing the value, or add any number of leading ones to a representation of a negative value.

Binary Arithmetic

  • Binary Addition Rules:

    • 0 + 0 = 0

    • 0 + 1 = 1

    • 1 + 1 = 0 with a carry of 1

    • 1 + 1 + 0 = 0 with a carry of 1

    • 1 + 1 + 1 = 1 with a carry of 1

  • Binary Subtraction Rules:

    • 0 – 0 = 0

    • 0 – 1 = 1 after a borrow

    • 1 – 0 = 1

    • 1 – 1 = 0

  • Overflow: Occurs when the result of a calculation is too large to fit into the defined number of bits for storage.

    • When values in a computer system are stored using two’s complement, there is a danger of overflow causing the answer to be interpreted incorrectly.

    • Overflow can occur when two positive values or two negative values are added.

    • The processor needs to detect overflow and output an error message.

  • Two’s complement representation simplifies subtraction.

  • To subtract one number from another, convert the number being subtracted to its two’s complement form, and then add it to the other number.

1.05 Binary Coded Decimal (BCD)

  • Binary coded decimal (BCD) is used in applications where single denary digits need to be stored or transmitted.

  • Each digit is represented by a nibble (4 bits), with codes 1010 to 1111 having no meaning.

  • Denary numbers with more than one digit require a group of four bits for each denary digit to be converted to BCD.
    Simple scheme: The digits are coded as the binary values from 0000 to 1001. Options for BCD storage include storing one BCD code in one byte (leaving four bits unused) or packed BCD where two 4-bit codes are stored in one byte.

  • Applications include displaying denary digits (e.g., on a calculator) and representation of currency values.

  • BCD arithmetic, like addition or subtraction requires additional steps because the result of simply binary addition is different (using a correction value to perform BCD addition).

  • Binary coded decimal (BCD): storage of a binary value representing one denary digit in a nibble

    • Packed BCD: when two BCD nibbles are stored in one byte

1.04 Internal Coding of Text

  • A coding scheme is needed to provide a unique binary code for each distinct individual component item of the text, such a code is referred to as a character code

  • ASCII (American Standard Code for Information Interchange): *A 7-bit version of the code (often referred to as US ASCII) was standardised many years ago by ANSI (American National Standards Institute).

    • Key facts about ASCII:
      *A limited number of the codes represent non-printing or control characters
      *The majorirty of the codes are for characters that would be found in an English text and which are available on a standard keyboard
      *These include upper- and lower-case letters, punctuation marks, denary digits and arithmetic symbols
      *The codes are in sequence.

  • Extended ASCII:

    • Code that uses all eight bits in a byte (e.g., ISO Latin-1 for accented characters).

  • Unicode:

    • UTF-8: Aims to represent any possible text in code form, including all languages.

    • Contains codes defined by one byte (reproducing 7-bit ASCII), two bytes, three bytes, and four bytes.

    • A character code in Unicode is referred to as a ‘code point’.

1.05 Images

  • Vector Graphics:

    • Images are created by drawing packages or CAD packages, and each component is an individual drawing object.

    • Data is stored as a drawing list containing commands for each object in the image, each command list of attributes that define a property of the object.

    • Properties are geometric data (e.g., position of the center and radius for a circle), thickness and style of a line, the colour of a line, and the colour that fills the shape.

    • Vector graphic: a graphic consisting of drawing objects defined in a drawing list

  • Drawing object: a component defined by geometric formulae and associated properties

  • Drawing list: contains one set of values for each drawing object

  • Property: defines one aspect of the appearance of the drawing object

  • Images are scalable without distortion.

  • Bitmaps:

    • Images are stored as a bitmap, often capturing existing images by scanning or taking a screen-shot.

    • Picture element (pixel) is the smallest identifiable component of an image. The image is stored as a two-dimensional matrix of pixels

    • Has a position in the matrix and it has a colour

  • Bit depth: the number of bits used to represent each of the red, green and blue colours

  • Image resolution: the number of pixels in the bitmap file defined as the product of the width and the height values

  • Screen resolution: the product of width and height values for the number of pixels that the screen can display

  • Picture element (pixel): the smallest identifiable component of a bitmap image, defined by just two properties: its position in the bitmap matrix and its colour

  • Colour depth: the number of bits used to represent one pixel

  • File size is always an issue with an image file. A large file occupies more memory space and takes longer to display or to be transmitted across a network. File header: a set of bytes at the beginning of a bitmap file which identifies the file and contains information about the coding used
    Justifying the use of either a bit map or a vector graphic for a specific task:

    • A vector graphic is chosen if a diagram is needed to be constructed for part of an architectural, engineering or manufacturing design.

  • A digital camera automatically produces a bitmap

  • A bitmap file is the choice for insertion of an image into a document, publication or web page.

1.06 Sound

  • Natural sound consists of variations in pressure detected by the ear. An analogue sound signal is converted to a binary code by a sound encoder having a band-limiting filter and an analogue-to-digital converter (ADC).

  • an Analogue is a measurement which can have any value from a continuous range of values whereas digital data has been stored as a binary value which can have one of a discrete range of values.

  • Sampling: taking measurements at regular intervals and storing the value.

  • Amplitude of the wave is sampled at regular intervals and is approximated with the closest defined amplitudes.

  • Sampling * resolution, which is the number of bits we will use to store the amplitude values.

  • Sampling rate should be in accordance with Nyquist’s theorem which states that sampling must be done at a frequency at least twice the highest frequency of the sound in the sample
    *Analogue data: data obtained by measurement of a physical property which can have any value from a continuous range of values
    *Digital data: data that has been stored as a binary value which can have one of a discrete range of values
    *Sampling: taking measurements at regular intervals and storing the value

  • Sampling resolution: the number of bits used to store each sample
    *Sampling rate: the number of samples taken per second

  • an increased sampling rate and an increased sampling resolution will both cause an increase in file size

1.07 Compression Techniques

  • Larger files require larger storage capacity, but more importantly, larger files have lower transmission or download rates.
    *Lossless compression: coding techniques that allow subsequent decoding to recreate exactly the original file

  • Lossy compression: coding techniques that cause some information to be lost so that the exact original file cannot be recovered in subsequent decoding

  • Lossless compression where the file size is reduced but no information is lost and Lossy compression where the file size is reduced with some loss of information.

  • A common lossless compression technique is run-length encoding. This works particularly well with a bitmap file.

  • Run-length encoding converts sequences of the same byte value into a code that defines the byte value and the number of times it is repeated.
    *If a file contains text, then compression must be lossless because any loss of information would lead to errors in the text.

  • Huffman coding is used for compressing a sound file because some amplitude values occur far more often than others.

  • If a vector graphic file needs to be compressed, it is best converted to a Scalable Vector Graphics format. This uses a markup language description of the image, which is suitable for lossless compression.
    Lossy compression can be used in circumstances where a sound file or an image file can have some of the detailed coding removed or modified.

  • An alternative is to convert the sampled amplitudes that represent time domain data and transform them to a frequency domain representation.

  • For a bitmap, lossy compression establishes a coding scheme with reduced color depth, changing each pixel’s code to the one in the new scheme which represents the closest color.