Cambridge AS & A Level9608

Data representation (3.1)

Computer Science 9608 Chapter Notes

What this chapter covers

Data representation
ShareWhatsAppPost
Data representation (3.1) notes

Unable to load PDF

The notes viewer could not load. Please refresh the page.

Read online free. Download a watermarked copy with a free account.

Read the notes

The full Data representation (3.1) notes as text: skim, search, and jump between subtopics.

~15 min read

In this chapter

  1. 1User-Defined Data Types
  2. 2File Organisation and Access Methods
  3. 3Floating-Point Binary Representation
  4. 4Normalisation of Floating-Point Numbers
  5. 5Range, Precision, and Conversion
  6. 6Floating-Point Overflow and Underflow

1. User-Defined Data Types

While programming languages come with built-in (primitive) data types like Integer, Real, and Boolean, they are often not sufficient to model complex real-world data. User-defined data types (UDTs) allow a programmer to create their own data structures. They can be non-composite, representing a single piece of data in a new way, or composite, grouping together existing data types into a new, larger type. This makes code more readable, maintainable, and better at representing the problem being solved.

Key term

Composite Data Type: A data type constructed from other existing data types, capable of holding multiple, often different, pieces of data as a single unit.

Examiner insight

Examiners reward students who can not only define a user-defined type but also justify why it is a more appropriate choice than using separate variables for a given scenario.

Common pitfall

Confusing a record (which can hold items of different data types) with an array (which holds items of the same data type).

Worked example 14 marks

A school needs to store data for its students, including their ID (integer), name (string), and average grade (real number). Define a suitable composite user-defined data type in pseudocode to represent a student. Then, declare a variable to store the details of one student.

  1. 1
    1. Identify the need for a composite type because multiple different data items (ID, name, grade) need to be grouped for each student.
  2. 2
    1. Choose a 'record' or 'structure' as the appropriate UDT. In pseudocode, this is often done using TYPE...ENDTYPE.
  3. 3
    1. Define the structure with the specified fields and their corresponding primitive types: StudentID as INTEGER, StudentName as STRING, AverageGrade as REAL.
  4. 4

    TYPE TStudent

  5. 5

    DECLARE StudentID : INTEGER

  6. 6

    DECLARE StudentName : STRING

  7. 7

    DECLARE AverageGrade : REAL

  8. 8

    ENDTYPE

  9. 9
    1. Declare a variable of this new type using the DECLARE keyword.
  10. 10

    DECLARE NewStudent : TStudent

Recap

  • User-defined types (UDTs) allow programmers to create custom data types.
  • Non-composite UDTs, like enumerated types, define a variable that can only take one of a predefined set of values.
  • Composite UDTs, like records or classes, group multiple data items together.
  • Records are a common composite type for storing related information of different types.
  • Using UDTs makes programs easier to understand and manage.

Quick check

  1. Is a record a composite or non-composite data type? Explain why.2 marks
  2. Give an example of a non-composite user-defined data type.1 mark

2. File Organisation and Access Methods

How data is stored in a file on secondary storage is crucial for system performance. File organisation refers to the way records are physically arranged. Serial organisation stores records one after another in the order they are added. Sequential organisation stores records sorted in order based on a key field. Direct (or random) organisation stores records at a specific address, calculated from the record's key using a hashing algorithm. The organisation method determines the possible access methods. Sequential access means reading records in order from the beginning. Direct access allows the program to jump straight to a specific record without reading others.

Key term

Direct Access: A method of retrieving a record from a storage device by calculating its physical address and accessing it directly, without reading the records before it.

Examiner insight

Marks are often awarded for justifying the choice of file organisation with specific reference to the application's needs, such as 'batch processing' versus 'real-time transaction processing'.

Common pitfall

Confusing file organisation (the physical layout on the disk) with the file access method (how the program reads the data). While related, they are distinct concepts.

Worked example 13 marks

A bank is developing software for its ATM network. Customers need to be able to check their balance instantly by inserting their card and entering a PIN. The customer records are stored in a large file.(a) What is the most appropriate method of file organisation and access for this system?(b) Justify your choice.

  1. 1

    (a) The most appropriate method is direct file organisation with direct access.

  2. 2

    (b) Justification: When a customer uses an ATM, their record needs to be retrieved almost instantly. The system cannot afford to search through millions of records from the beginning (sequential access) as this would be far too slow.

  3. 3

    With direct access, the customer's account number (the key field) can be used to calculate the exact location of their record in the file.

  4. 4

    This allows the system to jump straight to the required data, providing the fast response time necessary for an interactive system like an ATM.

Worked example 23 marks

A company processes its employee payroll once a month. A file containing all employee details is read from start to finish to calculate and issue payments. What file organisation would be suitable? Justify your answer.

  1. 1

    A suitable method is sequential file organisation (with sequential access).

  2. 2

    Justification: The task involves processing every single record in the file. There is no need to jump to specific records.

  3. 3

    Sequential access is perfectly efficient for this 'batch processing' task, as the program will read the first record, then the second, and so on, until the end of the file.

  4. 4

    Storing the records sorted by employee ID (the key) would make the process predictable and easy to manage. Direct access would be unnecessarily complex and offer no speed advantage.

Recap

  • File organisation is how records are physically arranged in a file.
  • The three main types of file organisation are serial, sequential, and direct.
  • File access is how records are read from a file.
  • Sequential access involves reading records in order from the start.
  • Direct access involves jumping straight to a specific record.
  • The choice of organisation and access depends on the application's requirements for speed and processing method.

Quick check

  1. If you need to process every record in a file, which access method is most efficient?1 mark
  2. What is needed to find a record in a file using direct access?1 mark

3. Floating-Point Binary Representation

Computers need a way to store real numbers (numbers with a fractional part), not just integers. Floating-point representation is the solution, analogous to scientific notation (e.g., 1.23 x 10^5). A number is split into three parts: a sign bit (1 for negative, 0 for positive), a mantissa (the significant digits of the number), and an exponent (how far and in which direction to shift the binary point). Both the mantissa and exponent are stored as binary numbers, often using two's complement to represent negative values. This system allows a very wide range of numbers, both large and small, to be stored in a fixed number of bits.

Denary Value = Mantissa × 2 ^ Exponent

Key term

Mantissa: The part of a floating-point number that represents the significant digits of that number.

Common pitfall

Forgetting that the exponent itself is a binary number and also needs to be converted from its denary value (e.g., +3) into the correct binary format (e.g., 0011).

Fun fact

The IEEE 754 standard, which defines floating-point formats, is one of the most important standards in computing, ensuring calculations on different machines produce the same results.

Worked example 15 marks

A floating-point system uses an 8-bit mantissa and a 4-bit exponent. Both are in two's complement. Represent the denary number 5.75 in this system.

  1. 1
    1. Convert the denary number to fixed-point binary: 5 is 101. 0.75 is 0.5 + 0.25, which is .11 in binary. So, 5.75 is 101.11.
  2. 2
    1. The binary point is currently after the third digit from the left. We need to move it to represent this in the mantissa. Let's place the point at the start: .10111.
  3. 3
    1. To get from .10111 back to 101.11, we must shift the point 3 places to the right. This means the exponent is +3.
  4. 4
    1. Convert the mantissa and exponent to the specified binary format. The mantissa is positive, so we represent .10111. In an 8-bit two's complement format, this is 0.1011100. (The first bit is 0 for positive, followed by the digits).
  5. 5
    1. The exponent is +3. In 4-bit two's complement, this is 0011.
  6. 6
    1. Combine them: Mantissa = 01011100, Exponent = 0011.

Recap

  • Floating-point representation stores real numbers using a mantissa and an exponent.
  • The sign of the number is stored in the most significant bit of the mantissa.
  • The mantissa holds the number's significant digits.
  • The exponent determines the position of the binary point.
  • Two's complement is used to represent negative mantissas and exponents.

Quick check

  1. In a floating-point number, what do the mantissa and exponent represent?2 marks
  2. If a floating-point number has a mantissa starting with '1' and uses two's complement, what does this signify?1 mark

4. Normalisation of Floating-Point Numbers

For any given floating-point number, there can be multiple ways to represent it. For example, 0.5 x 2^3 is the same as 0.25 x 2^4. To ensure a number is stored with the maximum possible precision and has a unique representation, we use normalisation. The process involves shifting the bits in the mantissa and adjusting the exponent until a standard format is reached. For positive numbers, the mantissa must start with '0.1'. For negative numbers (in two's complement), the mantissa must start with '1.0'. You shift the mantissa bits to the left and decrement the exponent for each shift until the number is in its normalised form.

Key term

Normalisation: The process of adjusting a floating-point number so that its mantissa is in a specific, standard range to maximise precision for the given number of bits.

Examiner insight

Examiners look for a clear, step-by-step demonstration of the normalisation process. Simply writing the final answer without showing the shifts and exponent adjustments will lose marks.

Common pitfall

Applying the positive normalisation rule (0.1...) to a negative number, or the negative rule (1.0...) to a positive number. The sign bit is key.

Worked example 14 marks

A floating-point number has a positive mantissa 00011000 and an exponent of 0101. The mantissa is 8 bits and the exponent is 4 bits, both in two's complement. Normalise this number.

  1. 1
    1. State the current values. Mantissa: 0.0011000, Exponent: 0101 (which is +5).
  2. 2
    1. Identify the rule for normalisation. Since the number is positive (starts with 0), the normalised mantissa must start '0.1'.
  3. 3
    1. The current mantissa is 0.0011000. It needs to be shifted left to become 0.1... .
  4. 4
    1. Shift 1: Mantissa becomes 0.0110000. The exponent must be decremented. Exponent becomes 0100 (+4).
  5. 5
    1. Shift 2: Mantissa becomes 0.1100000. The exponent is decremented again. Exponent becomes 0011 (+3).
  6. 6
    1. The mantissa now starts with '0.1'. The number is normalised.
  7. 7
    1. Final normalised number: Mantissa = 01100000, Exponent = 0011.

Worked example 24 marks

Normalise the negative floating-point number with mantissa 11101000 and exponent 1000. Use 8-bit mantissa and 4-bit exponent.

  1. 1
    1. State the current values. Mantissa: 1.1101000, Exponent: 1000 (which is -8).
  2. 2
    1. Identify the rule for normalisation. Since the number is negative (starts with 1), the normalised mantissa must start '1.0'.
  3. 3
    1. The current mantissa is 1.1101000. It needs to be shifted left to become 1.0... .
  4. 4
    1. Shift 1: Mantissa becomes 1.1010000. Exponent is decremented. Exponent becomes 0111 (+7). Wait, this is wrong. Let's re-evaluate. The exponent is -8 (1000). Decrementing it gives -9 (0111 is +7, 1001 is -7). Decrementing -8 gives -9. In 4-bit two's complement, this is not representable. Let's assume the starting exponent was different, e.g. 0100 (+4).
  5. 5

    Correction: Let's restart with a better example. Mantissa: 11101000, Exponent: 0100 (+4).

  6. 6
    1. Mantissa: 1.1101000, Exponent: 0100 (+4). The number is negative.
  7. 7
    1. Normalised negative numbers must start '1.0'.
  8. 8
    1. Shift left: Mantissa becomes 1.1010000. Decrement exponent. Exponent becomes 0011 (+3).
  9. 9
    1. Shift left again: Mantissa becomes 1.0100000. Decrement exponent. Exponent becomes 0010 (+2).
  10. 10
    1. The mantissa now starts with '1.0'. The number is normalised.
  11. 11
    1. Final normalised number: Mantissa = 10100000, Exponent = 0010.

Recap

  • Normalisation ensures a unique and maximally precise representation for a floating-point number.
  • The process involves shifting the mantissa and adjusting the exponent.
  • For positive numbers, the normalised mantissa begins '0.1'.
  • For negative numbers (in two's complement), the normalised mantissa begins '1.0'.
  • For every left shift of the mantissa, the exponent is decremented by 1.

Quick check

  1. What are the first two bits of a normalised positive floating-point number's mantissa?1 mark
  2. If you shift a mantissa two places to the left during normalisation, what happens to the exponent?1 mark

5. Range, Precision, and Conversion

In a floating-point system, there's a trade-off between the range of numbers you can store and their precision. The range is the difference between the largest and smallest possible numbers, determined by the number of bits for the exponent. More exponent bits mean a larger range. Precision is the level of detail or accuracy of the number, determined by the number of bits for the mantissa. More mantissa bits mean higher precision. Converting a binary floating-point number to denary involves first finding the denary value of the exponent, then calculating the denary value of the mantissa (remembering it's a fraction and could be negative), and finally applying the formula: Denary = Mantissa × 2^Exponent.

Denary Value = Mantissa_Value × 2 ^ Exponent_Value

Key term

Precision (Floating-Point): The number of significant digits with which a value can be represented, determined by the number of bits allocated to the mantissa.

Examiner insight

Students who clearly separate the conversion of the mantissa and exponent before combining them are less likely to make errors and are easier for examiners to award partial marks to.

Common pitfall

Incorrectly calculating the denary value of a negative (two's complement) fractional mantissa. Remember the most significant bit has a negative weight (e.g., -1).

Worked example 15 marks

A floating-point number is represented by a 10-bit mantissa and a 6-bit exponent, both in two's complement. Convert the following binary number to its denary equivalent: Mantissa = 1011000000, Exponent = 000100.

  1. 1
    1. Convert the exponent to denary. The exponent is 000100. This is a positive number. The place values are 32, 16, 8, 4, 2, 1. So, 000100 = 4. The exponent value is +4.
  2. 2
    1. Convert the mantissa to denary. The mantissa is 1011000000. This is a negative number (starts with 1). It is a fraction. The place values are -1, 0.5, 0.25, 0.125, etc.
  3. 3
    1. The value is -1 + 0.25 + 0.125 = -0.625. (The '1' in the MSB has a weight of -1, the third bit has a weight of +0.25, the fourth has a weight of +0.125).
  4. 4
    1. Apply the formula: Denary Value = Mantissa_Value × 2 ^ Exponent_Value.
  5. 5
    1. Calculation: -0.625 × 2^4 = -0.625 × 16.
  6. 6
    1. Final Answer: -10.

Recap

  • More bits for the exponent increases the range of representable numbers.
  • More bits for the mantissa increases the precision of representable numbers.
  • There is always a trade-off between range and precision for a fixed total number of bits.
  • Converting from binary floating-point to denary requires converting the mantissa and exponent separately first.
  • Binary floating-point numbers are often only an approximation of the true denary value, leading to rounding errors.

Quick check

  1. To increase the precision of a floating-point system, should you allocate more bits to the mantissa or the exponent?1 mark
  2. What is the consequence of binary representation often being an approximation of a real number?1 mark

6. Floating-Point Overflow and Underflow

Because floating-point numbers are stored in a fixed number of bits, there are limits to what can be represented. Overflow occurs when the result of a calculation is too large to be stored. This happens when the exponent of the result is larger than the maximum possible value for the given number of exponent bits. For example, multiplying two very large positive numbers. Underflow occurs when a number is too small (i.e., too close to zero) to be represented. This happens when the exponent of the result is more negative than the minimum possible value. For example, dividing a very small number by a very large one. Both are types of error that can halt a program or produce invalid results.

Key term

Underflow: An error that occurs when the result of a calculation is too small in magnitude (too close to zero) to be represented in the allocated bit representation.

Examiner insight

Examiners appreciate answers that link overflow/underflow back to the limits of the exponent bits, showing a deeper understanding of the cause.

Common pitfall

Confusing overflow with a rounding error. A rounding error means the number is imprecise but within the representable range. An overflow error means the number is outside the representable range entirely.

Worked example 14 marks

A floating-point system uses a 4-bit exponent in two's complement.(a) What is the largest positive exponent that can be stored?(b) Describe a calculation that could cause an overflow error in this system.

  1. 1

    (a) With a 4-bit two's complement exponent, the largest positive value is represented by 0111. The place values are -8, 4, 2, 1. So, 0111 = 4 + 2 + 1 = 7. The largest positive exponent is +7.

  2. 2

    (b) An overflow would occur if a calculation produced a result with an exponent greater than +7.

  3. 3

    For example, consider two numbers: Number A with exponent +5 (0101) and Number B with exponent +4 (0100).

  4. 4

    If we multiply A and B, the exponents are added. The resulting exponent would be 5 + 4 = 9.

  5. 5

    Since 9 is greater than the maximum representable exponent of 7, this calculation would cause an overflow error.

Recap

  • Overflow is when a number is too large in magnitude to be stored.
  • Underflow is when a number is too small in magnitude (close to zero) to be stored.
  • Overflow is caused by the resulting exponent being too large and positive.
  • Underflow is caused by the resulting exponent being too large and negative.
  • These errors highlight the finite limits of computer number representation.

Quick check

  1. What is the difference between overflow and underflow?2 marks
  2. A calculation results in a number with an exponent that is too negative to be stored. What is this error called?1 mark

End-of-chapter exercise

Test yourself on the whole chapter. Work through these before moving on.

  1. Explain the difference between a composite and a non-composite user-defined data type, giving a clear example of each.4 marks
  2. A national census database will store records for millions of citizens. The data will be collected over several weeks and then processed in one large batch to produce statistics. Recommend and justify a suitable file organisation method.3 marks
  3. A floating-point system uses a 10-bit two's complement mantissa and a 6-bit two's complement exponent. Convert the denary number -24.5 into a normalised floating-point binary number. Show your working.6 marks
  4. A programmer is designing a scientific simulation. They must choose between allocating more bits to the mantissa or the exponent. Explain the consequence of each choice on the numbers that can be represented.4 marks
  5. A floating-point number is stored with the following binary representation: Mantissa = 0101010000, Exponent = 111101. The mantissa is 10 bits and the exponent is 6 bits, both in two's complement. Calculate the denary value of this number.5 marks
  6. What is meant by 'normalisation' in the context of floating-point numbers, and why is it necessary?3 marks
  7. Describe the conditions that lead to (i) an overflow error and (ii) an underflow error in floating-point arithmetic.4 marks
  8. A number is represented in a floating-point system as: Mantissa = 11110000, Exponent = 0110. The system uses an 8-bit mantissa and a 4-bit exponent. Normalise this number, showing each step of the process.4 marks
  9. Explain why a stored floating-point value is often an approximation of a real number and state one consequence of this.3 marks
  10. A floating-point system has a 12-bit mantissa and a 4-bit exponent, both in two's complement. Calculate the denary value of the most negative number that can be represented in this system in normalised form.5 marks

Go deeper

Practise and revise with member-only material for this chapter.

Workbook

Exam-style practice questions with full worked solutions.

Unlock with a plan

Chapter at a Glance

A single-page summary of every key idea for fast revision.

Unlock with a plan

Free notes are just the start.

Unlock every Workbook and Chapter at a Glance, and generate your own worksheets and predicted papers.

Explore plans

Related chapters

Data representation (1.1)Communication and Internet technologiesHardwareProcessor fundamentalsSystem software (1.5)Security, privacy and data integrity