3.5 Fundamentals of data representation

3.5.1 Number systems

3.5.1.1 Natural numbers

Content

Additional information

Be familiar with the concept of a natural number and the set ℕ of natural numbers (including zero).

ℕ = {0, 1, 2, 3, … }

3.5.1.2 Integer numbers

Content

Additional information

Be familiar with the concept of an integer and the set ℤ of integers.

ℤ = { …, -3, -2, -1, 0, 1, 2, 3, … }

3.5.1.3 Rational numbers

Content

Additional information

Be familiar with the concept of a rational number and the set ℚ of rational numbers, and that this set includes the integers.

ℚ is the set of numbers that can be written as fractions (ratios of integers). Since a number such as 7 can be written as 7/1, all integers are rational numbers.

3.5.1.4 Irrational numbers

Content

Additional information

Be familiar with the concept of an irrational number.

An irrational number is one that cannot be written as a fraction, for example √2.

3.5.1.5 Real numbers

Content

Additional information

Be familiar with the concept of a real number and the set ℝ of real numbers, which includes the natural numbers, the rational numbers, and the irrational numbers.

ℝ is the set of all 'possible real world quantities'.

3.5.1.6 Ordinal numbers

Content

Additional information

Be familiar with the concept of ordinal numbers and their use to describe the numerical positions of objects.

When objects are placed in order, ordinal numbers are used to tell their position. For example, if we have a well-ordered set S = {‘a’, ‘b’, ‘c’, ‘d’}, then ‘a’ is the 1st object, ‘b’ the 2nd, and so on.

3.5.1.7 Counting and measurement

Content

Additional information

Be familiar with the use of:

  • natural numbers for counting
  • real numbers for measurement.
 

3.5.2 Number bases

3.5.2.1 Number base

Content

Additional information

Be familiar with the concept of a number base, in particular:

  • decimal (base 10)
  • binary (base 2)
  • hexadecimal (base 16).

Students should be familiar with expressing a number’s base using a subscript as follows:

Base 10: Number10, eg 6710

Base 2: Number2, eg 100110112

Base 16: Number16, eg AE16

Convert between decimal, binary and hexadecimal number bases.

 

Be familiar with, and able to use, hexadecimal as a shorthand for binary and to understand why it is used in this way.

 

3.5.3 Units of information

3.5.3.1 Bits and bytes

Content

Additional information

Know that:

  • the bit is the fundamental unit of information
  • a byte is a group of 8 bits.

A bit is either 0 or 1.

Know that the 2n different values can be represented with n bits.

For example, 3 bits can be configured in 23 = 8 different ways.

000, 001, 010, 011, 100, 101, 110, 111

3.5.3.2 Units

Content

Additional information

Know that quantities of bytes can be described using binary prefixes representing powers of 2 or using decimal prefixes representing powers of 10, eg one kibibyte is written as 1KiB = 210 B and one kilobyte is written as 1 kB = 103 B.

Know the names, symbols and corresponding powers of 2 for the binary prefixes:
  • kibi, Ki - 210
  • mebi, Mi - 220
  • gibi, Gi - 230
  • tebi, Ti - 240
Know the names, symbols and corresponding powers of 10 for the decimal prefixes:
  • kilo, k - 103
  • mega, M - 106
  • giga, G - 109
  • tera, T - 1012

Historically the terms kilobyte, megabyte, etc have often been used when kibibyte, mebibyte, etc are meant.

3.5.4 Binary number system

3.5.4.1 Unsigned binary

Content

Additional information

Know the difference between unsigned binary and signed binary.

Students are expected to be able to convert between unsigned binary and decimal and vice versa.

Know that in unsigned binary the minimum and maximum values for a given number of bits, n, are 0 and 2n -1 respectively.

 

3.5.4.2 Unsigned binary arithmetic

Content

Additional information

Be able to:

  • add two unsigned binary integers
  • multiply two unsigned binary integers.
 

3.5.4.3 Signed binary using two’s complement

Content

Additional information

Know that signed binary can be used to represent negative integers and that one possible coding scheme is two’s complement.

This is the only representation of negative integers that will be examined. Students are expected to be able to convert between signed binary and decimal and vice versa.

Know how to:

  • represent negative and positive integers in two’s complement
  • perform subtraction using two’s complement
  • calculate the range of a given number of bits, n.
 

3.5.4.4 Numbers with a fractional part

Content

Additional information

Know how numbers with a fractional part can be represented in:

  • fixed point form in binary in a given number of bits.
 

Be able to convert for each representation form:

  • decimal to binary of a given number of bits
  • binary to decimal of a given number of bits.
 

3.5.5 Information coding systems

3.5.5.1 Character form of a decimal digit

Content

Additional information

Differentiate between the character code representation of a decimal digit and its pure binary representation.

 

3.5.5.2 ASCII and Unicode

Content

Additional information

Describe ASCII and Unicode coding systems for coding character data and explain why Unicode was introduced.

 

3.5.5.3 Error checking and correction

Content

Additional information

Describe and explain the use of:

  • parity bits
  • majority voting
  • check digits.
 

3.5.6 Representing images, sound and other data

3.5.6.1 Bit patterns, images, sound and other data

Content

Additional information

Describe how bit patterns may represent other forms of data, including graphics and sound.

 

3.5.6.2 Analogue and digital

Content

Additional information

Understand the difference between analogue and digital:

  • data
  • signals.
 

3.5.6.3 Analogue/digital conversion

Content

Additional information

Describe the principles of operation of:

  • an analogue to digital converter (ADC)
  • a digital to analogue converter (DAC).
 

3.5.6.4 Bitmapped graphics

Content

Additional information

Explain how bitmaps are represented.

 

Explain the following for bitmaps:

  • resolution
  • colour depth
  • size in pixels.

The size of an image is also alternatively sometimes described as the resolution of an image.

Size of an image in pixels is width of image in pixels x height of image in pixels.

Resolution is expressed as number of dots per inch where a dot is a pixel.

Colour depth = number of bits stored for each pixel.

Calculate storage requirements for bitmapped images and be aware that bitmap image files may also contain metadata.

Ignoring metadata,

storage requirements = size in pixels x colour depth

where size in pixels is width in pixels x height in pixels.

Be familiar with typical metadata.

eg width, height, colour depth.

3.5.6.5 Digital representation of sound

Content

Additional information

Describe the digital representation of sound in terms of:

  • sample resolution
  • sampling rate and the Nyquist theorem.
 

Calculate sound sample sizes in bytes.

 

3.5.6.6 Musical Instrument Digital Interface (MIDI)

Content

Additional information

Describe the purpose of MIDI and the use of event messages in MIDI.

 

Describe the advantages of using MIDI files for representing music.

 

3.5.6.7 Data compression

Content

Additional information

Know why images and sound files are often compressed and that other files, such as text files, can also be compressed.

 

Understand the difference between lossless and lossy compression and explain the advantages and disadvantages of each.

 

Explain the principles behind the following techniques for lossless compression:

  • run length encoding (RLE)
  • dictionary-based methods.
 

3.5.6.8 Encryption

Content

Additional information

Understand what is meant by encryption and be able to define it.

Students should be familiar with the terms cipher, plaintext and ciphertext.

Caesar and Vernam ciphers are at opposite extremes. One offers perfect security, the other doesn’t. Between these two types are ciphers that are computationally secure – see below. Students will be assessed on the two types. Ciphers other than Caesar may be used to assess students' understanding of the principles involved. These will be explained and be similar in terms of computational complexity.

Be familiar with Caesar cipher and be able to apply it to encrypt a plaintext message and decrypt a ciphertext.

Be able to explain why it is easily cracked.

 

Be familiar with Vernam cipher or one-time pad and be able to apply it to encrypt a plaintext message and decrypt a ciphertext.

Explain why Vernam cipher is considered as a cypher with perfect security.

Since the key k is chosen uniformly at random, the ciphertext c is also distributed uniformly. The key k must be used once only. The key k is known as a one-time pad.

Compare Vernam cipher with ciphers that depend on computational security.

Vernam cipher is the only one to have been mathematically proved to be completely secure. The worth of all other ciphers ever devised is based on computational security. In theory, every cryptographic algorithm except for Vernam cipher can be broken, given enough ciphertext and time.