Computer Science resources | Online Learning area

Cambridge IGCSE and O Level

In this presentation we are going to be looking at Parity checking which is part of the 'Identify methods of error detection and correction' section of the syllabus.

A computer doesn’t read data in the same way as us. A computer reads and transmits data in binary as a series of zeros and ones.

So how do we know that the data a computer transmits and another receives is correct? After all, we’ve all probably received corrupt data in the past, like a garbled email or text message or a broken Word document. So what do we know about data transmission errors?

Well unfortunately, During transmission there is always a chance that data can become corrupted or changed in some way, so that a file can’t be opened or perhaps there is a string of symbols where an image should be. We need to ensure that this doesn’t happen to make sure that the computer is a reliable.

Second, Regardless of the distance of transmission, data can be changed beyond comprehension or minor changes can happen. So whether the data is coming from a memory stick plugged into a computer, or going to your printer along USB cables, or even being sent to a distant country, we need to ensure that the data is not changed. We need to ensure that even minor changes don’t happen. Luckily, To avoid this computers have been programmed to check for errors and correct them where possible.

In this video we’re going to concentrate on one type of error checking computers perform, called parity checking. Narrative as per the slide:

• A parity check is an error detection method used in data transmission from one device, or medium, to another. • For example, if a byte of data is transmitted, it would have a parity bit allocated to it before it was transmitted. • Systems which use odd parity have an odd number of 1-bits. • Systems that use even parity have an even number of 1-bits.

Okay, so that’s good, but what does this actually look like in practice? To get a better idea let us look at these examples.

Let’s say you want to transmit this data, that is the 7 bits from the right, ignoring for now the empty cell on the left, which is where the parity bit will eventually appear.

If even parity is being used, the parity bit would have to be zero, as there is already an even number of 1-bits. This is why the parity bit on the left is a zero.

However, if odd parity was being used instead, the parity bit would be 1, as there is already an even number of 1-bits. So the parity bit on the left becomes 1.

Okay, here are a further two examples to help you understand what the parity bit needs to be, depending on whether you are using odd or even parity.

If odd parity is being used in this example, the parity bit would have to be zero, as we already have an odd number of 1-bits. This can seen as the parity bit is zero.

However, if even parity was being used, the parity bit in this example would have to be 1, as there is already an odd number of 1-bits. So the parity bit becomes a 1.

So, in odd parity checking, if the number of 1-bits is also odd the parity bit will always be zero because the overall number of 1-bits has to be an odd number, otherwise the parity bit will always be 1.

Similarly, in even parity checking, if the number of 1-bits is also even the parity bit will be zero to ensure that the overall number of 1-bits remains an even number, but in all other cases it will be 1.

Okay, so how does parity checking actually work?

• Well, before data is transmitted, the sender and the receiver of the data agree on which type of parity to use. • If a byte of data is sent from the sender to the receiver, and both have agreed on even parity, an error would be flagged if the byte of data had an odd number of 1-bits when it reached its destination. • This error is detected by the receiver checking the parity agreed against the number of 1-bits, including the parity bit, in the byte sent.

So, if the example shown here was sent using even parity, the parity bit would be zero as there are already four 1-bits in the byte. However, if the receiver receives the byte like this, then an error has clearly occurred in the transmission of this byte as there are now only three 1-bits and the parity bit is still zero.

Okay, so that is simple enough, but how does the receiver know which of the bits has been transmitted incorrectly? Well a parity byte can be sent as well, and using this method, even blocks of data can be sent and successfully checked.

Let’s look at how parity checking can show where errors have occurred in the data, and even do this in blocks of data. Here’s a simple example showing a single byte of data to be transmitted. As you can see, odd parity is being used because there are an even number of 1-bits, four in this case, so the parity bit in the byte of data is set to a 1, to make an odd number of 1-bits.

Below the data byte you can see the parity byte which is sent alongside the actual byte of data. The values in the parity byte are set by the 1-bits in the data byte columns above, so because we are using odd parity, if a 1-bit appears in the corresponding data byte column, then the parity byte column will show a zero, so that the number of 1-bits in both the data and parity byte columns remain an odd number. Conversely, data byte columns containing zeros result in a 1 being entered in the corresponding parity byte column to keep the overall number of 1-bits odd.

Okay, so now let’s look at what was received. How can you check that there is an error and more importantly, how can you know where the error is in the data received?

Well first you check the horizontal row for the byte of data, and you can see that there is now an even number of 1-bits, six in total including the parity bit, so there is clearly an error because we are using odd parity.

Now check the parity byte to reveal where the error has occurred. This you know is calculated vertically in the columns.

We are using odd parity in this example, so examining each column, there has to be an odd number of 1-bits in each column. You can see that for 'bit 6' the column contains two 1-bits, so the error must be in bit 6. Now let’s look at an actual block of data so that we can get a better idea of how this works. In this example, even parity is being used and the block of data being sent contains multiple bytes as well as the parity byte.

If you examine each byte row, byte 1 to byte 4, you can see that there is an even number of 1-bits in each row including the parity bit. Now check the columns. Again you can see that the parity byte has been calculated correctly as there are an even number of 1-bits in each column. So everything looks fine.

Next let’s look at what was received. This is what was received, but how do we find where the error is? Can you work it out?

Remember that even parity is being used. So start by examining each byte row and checking for an even number of 1-bits. You can see that bytes 1, 2 and 4 have an even number of 1-bits, but byte 3 has an odd number of 1-bits, so the error must be in byte 3.

Now examine each column for an even number of 1-bits. You can see that for bit 4 there is an odd number of 1-bits, so the error is in byte 3, bit 4.

Let us now look at a typical exam style question. In this example you are shown a block of data and told:

Odd parity is being used, locate the incorrectly transmitted bit. Can you answer the question?

Okay, so as you’ve learnt, first count the number of 1-bits in each row. Here are the totals for each row. Of course, don’t include the parity byte, because the parity byte is calculated from the vertical count.

As you can see, byte 4 is the only byte where there is an even number of 1-bits, and we are expecting odd parity, so the error must be in byte 4. So let’s find which bit it is in byte 4 that is the error. Again count the number of 1-bits in each column, including the parity byte.

Here are the totals for each column. It is clear that the error must be with bit 7 as this is the only one with an even number of 1-bits when we are expecting odd parity. So the error is in byte 4, bit 7.

So you can see that parity checking can be an incredibly useful tool in limiting errors in transmission and receiving of data. Unfortunately though, it has limitations. Can you think what they might be?

Well consider what if you are using odd parity and an odd number of bits have been incorrectly transmitted? Then, there is no way of the receiver knowing that they have received data with errors.

For example, the byte 01110011 containing five 1-bits, could be transmitted as 00010011, containing three 1-bits, with two bits changed. You know by just looking at the two bytes of data that an error has occurred in the transmission of the data. It has been incorrectly transmitted. However, how can the receiver know, as in the first byte there are five 1-bits and in the second byte there are three 1-bits? Both the original byte and the altered byte pass the odd parity check, as they both have an odd number of 1-bits.

This is a limitation of parity checking. And this is why we need to look at other error checking methods. We’ll look at these in another presentation.

Good luck!

Check digits, Checksums, ARQs and Echo checks video transcript

This video follows on from the presentation on Parity checking, and is part of the 'Identify methods of error detection and correction' section of the syllabus.

If you’ve watched the Parity checking video, you’ll know there are limitations with using parity checking on its own. This is because when a transmission is made that contains an error, but the parity check matches, the receiver has no way of knowing where the error is, or even if there is an error in the first place.

So, we’ll now look at some other error checking methods which are; check digits, Checksums, ARQs and Echo checks.

Okay, let’s first look at the check digits error checking method:

In this method, the final digit in a code, called the check digit, is calculated using all the other digits of the code.

Examples where check digits are used include in barcodes and product codes, in International Standard Book Numbers, or ISBNs, and also in Vehicle Identification Numbers or VINs.

Check digits are used for identifying errors in data entry, for example a typo or a scanning error.

They can usually identify • an incorrectly entered digit, • or transposition errors, for example if you were supposed to type in 36875 and you actually typed in 36785 instead, this would be a transposition error. • Check digits can also identify omitted or extra digits, for example if you were supposed to type in a 4 digit PIN, but you typed in 3 or 5 digits instead • And finally, they can identify phonetic errors in speech. For example you said ‘fourteen’ but the computer thought you said forty, this would be a phonetic error.

Okay, so let’s see how the check digit is calculated in a thirteen digit ISBN.

The check digit is the last digit in the ISBN and it’s calculated like this.

First, all the odd position digits in the ISBN are added up.

Then all the even position digits are added up and multiplied by three.

This amount is added to the sum of all the odd position digits to produce a total.

Now this is where the calculation gets interesting. Using a modulus, or mod, 10 calculation a remainder is produced.

Mod is where you obtain the remainder from a division calculation by 10. For example, if you were to divide 33 by 10, you would get 3 with a remainder of 3. So 33 mod 10 would be 3.

Now that the remainder has been calculated the check digit can be calculated in turn. If the remainder is zero, that becomes the check digit in the 13th position of the ISBN. If it’s any other number, then it is subtracted from 10 to produce the check digit.

So the theory is fairly straight forward. Now let’s look at an actual example to demonstrate how the check digit works in an ISBN. Here’s an example of a question you might be asked:

Calculate the check digit for this code: 9 7 8 1 4 7 1 8 0 7 2 1

This is an example of an ISBN code. It contains 12 digits, and you’re going to calculate the check digit, the 13th, or last, digit.

Okay, first add the odd position numbers together, which are 9, 8, 4, 1, 0 and 2. This makes 24. Then you add together the even positioned numbers, 7, 1, 7, 8, 7 and 1 and multiply the sum by 3 to obtain 93. Now you add together the two sums which are 24 and 93, which gives 117, and mod 10. This gives 11 remainder 7. So 117 mod 10 is 7.

Finally, because the remainder isn’t zero, you subtract 7 from 10 to obtain 3. So the check digit is 3.

Let’s look at another example. Why don’t you try this example yourself first, then follow along with the video to check your answer.

In this question you are asked to calculate the check digit for the code 978452417063

As before, put the code into a grid. Now add together all the odd placed digits. This equals 39. Then add together all the even placed digits and multiply the answer by 3. This equals 51. Now add the two answers together and mod 10. This equates to 90 divided by 10, which equals 9, remainder 0. As the remainder is zero, you don’t need to subtract this from 10.

So in this case, the check digit is 0.

Okay, now that you know how the check digit is calculated in an ISBN, how can you check that an existing ISBN check digit is valid?

Well, first you add all the odd placed digits, including the check digit, together. Next you add all the even placed digits together and multiply this answer by three. Finally, you add the two values together and mod the result to obtain the remainder.

The code is valid if the reminder is zero. Let’s give this a try. Here’s a typical question you might be asked: Is this code valid? 4 2 6 8 9 7 9 3 2 1 3 5 9

To determine whether the check digit is valid you first add up all the odd placed digits, including the check digit. So, 4 + 6 +9 + 9 + 2 + 3 + 9 gives 42. Next, add up all the even placed digits and multiply by 3. So, 2 + 8 + 7 + 3 + 1 + 5 multiplied by 3 gives 78. Finally, you add the two sums together and mod 10 to obtain the remainder. So, 42 + 78 mod 10 gives us 120 remainder 0.

As the remainder is 0, the code is valid.

Right, why don’t you have a go at this question first and then follow along with the presentation to check your calculations and answer. Right, in this question you are asked ‘Is this code valid? 9 7 8 0 3 4 0 9 6 6 5 1 2’

You follow exactly the same process as you followed on the previous example. Start by adding together all the odd positioned numbers including the check digit. Then add together all the even positioned numbers and multiply by 3. Add together the two sums and mod 10. In this case there is a remainder of 4, as you can see in the calculations.

As there is a remainder and the result isn’t zero, the code is invalid.

So, now you’ve understood how the check digit method of error correction works, let’s have a look at another.

A checksum is another method of error detection in data transmission. This method is a little more reliable than parity checks which were covered in a previous presentation on error detection and correction. In this method, data is sent in blocks and at the end of each block, another value is added which is the checksum.

So how is a checksum calculated? Well, let's assume that the checksum of a block of data is 1 byte. This gives a maximum decimal value of 255 as shown in the grid here. If the sum of the bytes of the block of data, this can be a little tricky to say!, is less than or equal to 255, then this value is the checksum.

However, if the sum is greater than 255, then the checksum is calculated as shown next Okay, so this is the process for how a checksum is calculated.

First you divide the sum of the blocks of data, which is labelled V, by 256. The result is labelled X. Then you round X down to the nearest integer, or whole number. So even if X had a value, for example of 8.7, you would round it down to 8 NOT up to 9. So basically you remove what is after the decimal point. This is labelled Y. Then you calculate Z, which is Y multiplied by 256.

Then the checksum is the original value V, minus the value of Z.

Let’s look at a worked example.

In this example V equals 1521. First you calculate X, which in this case is 1521 divided by 256. Which gives 5.94. Then you round down to the nearest integer to give Y. So in this example, Y is 5. To calculate Z, multiply 5 by 256, and this gives 1280. Finally, subtract 1280 from your original value V. So, 1521 minus 1280 is 241.

So the checksum is 241, which you can see is less than 255.

Okay, so how are checksums used?

First, before a block of data is transmitted, the checksum is calculated by the sender and is sent to the receiver along with the data. The receiver will then recalculate the checksum of the received data using the same algorithm used by the sender, and compares it with the checksum that was sent with the data.

If the values are the same, there have been no errors in transmission. If they are not the same, the receiver sends a request to the sender to resend the data.

Right, let’s look at a final example of a checksum question. You might want to try this one out yourself and then follow along with the presentation to check your answer.

You are asked to ‘Calculate the checksum of a block of data with the byte sum: 1765’. So remember the algorithm, to calculate X, divide the value, V, by 256. This gives 6.89 for the value X. To calculate Y, round down to the nearest integer. This is 6 in this case. Calculating Z, this is 6 multiplied by 256, giving 1536. Finally, the checksum is the original value 1765 minus 1536 which equals 229. So 229 is the checksum.

Okay, let’s consider another method of error detection. An Automatic Repeat request, or ARQ, is another method of error detection in data transmission. It’s also known as an Automatic Repeat Query. This is how the ARQ method works:

If the receiver detects no errors in the data transmitted, it sends the sender an acknowledgement to notify them that the data has been sent correctly. The acknowledgement is basically a message sent from the receiver to the sender. indicating successful data transmission.

However, if the receiver detects errors in the data, it requests the sender to resend the data.

If the sender does not receive anything back from the receiver before a timeout occurs, the data is automatically resent. A timeout is an agreed or set time that is allowed to elapse before an acknowledgement or request to resend the data is received.

This will keep happening until the sender receives an acknowledgement.

So that’s the ARQ error detection method. Let’s now look at one last additional method. This last error detection method is a very basic process called an Echo check.

Essentially this method is a simple comparison transmission check. When data is sent to a receiver, the receiver resends it back to the sender, which then checks if any errors have occurred during transmission. If there is an error detected, the data will be sent again.

That’s simple enough, but in reality it seems a little ridiculous to check for errors in this way. Can you see what the issues might be?

The problem with the echo check method is that it’s not very reliable, as it can’t be known whether an error occurred when the data was sent to the receiver or when the data was resent back to the sender to check.

Obviously the drawbacks are, if both transmission and resent data are corrupted there is no way of knowing whether an error has occurred in the original transmission or when the data was resent to the sender. Also, there will be a lot of extra data being transmitted if errors occur in data transmission.

So that’s it. In this presentation and the one on parity checking, we’ve covered all the methods of error detection and correction you are required to know. You’ve looked at some worked examples of each error detection method, and hopefully you’ve tried out some yourself. We’ve also considered the benefits and downsides to each method. Why not now take a look at some past paper questions to test your skills further.

Good luck!

Logic gates video transcript

Logic gates, what exactly are they? In basic terms, they are a relatively simple digital electronic circuit. Each gate processes two-state signals according to a logical rule, and has one or more inputs and a single output. A logic gate can be thought of like a light switch, where in one position the output is off or zero, and in another, it is on or one. They are used by electronics engineers as building blocks for more complex circuits of gates or logic circuits, in which the output of a gate forms an input to one or more other gates for further processing. As they process two-state signals, it also makes them suitable for the processing and temporary holding of the binary tnumbers that computers use to represent numbers and text. So, as you have probably guessed, The processor in a PC consists of many thousands of logic gates. For Cambridge IGCSE and O Level Computer Science, you only have to consider and know about the six logic gates shown in this animation. You will need to remember the symbols for each logic gate, and know and be able to produce a truth table for each one. For the examination you need to be able to remember the truth table for a given gate and identify a gate from a given truth table. You will also need to know the logic notation for each gate.

Okay, let’s start with looking at the NOT gate: A NOT gate only has one binary input, A, and a binary output, X. The output is the opposite of its input, so it is also called an ‘inverter’. The output has the value True only when the input does not have the value True, in other words, when the input has a value False. This can be seen here in a truth table, where True is represented by 1 and False is represented by 0. A truth table is used to show the output of a logic gate circuit for all possible combinations of input values. Even though it is called a ‘truth’ table, we usually use the binary values 1 and 0 as shorthand for ‘True’ and ‘False’. For the Cambridge IGCSE and O Level Computer Science you only have to consider gates with a maximum of two inputs, except the NOT gate of course which only has one input. Here is the logic notation for the NOT gate.

Right, let’s take a look at the AND gate: An AND gate has at least two inputs. The output has the value True only when its first input and its second input have the value True. This is shown in this truth table, where the only occurrence of the output X having the value True, or 1, is where both inputs, A and B, both have the value True (1) . Here is the logic notation for the AND gate.

Here is the OR gate; An OR gate has at least two inputs. The output has the value True when either the first input or the second input, or any other input or combination of inputs, has the value True; in other words, one or more of its inputs has the value True. This can be seen in the truth table where the output (X) has the value True in all cases except where both inputs have the value False. The logic notation for this gate is shown here.

Okay, let’s take a look at the NAND gate: A NAND gate is an AND gate followed by a NOT gate. The output has the value False only when all its inputs have the value True. This is the same as saying that its output has the value True only when not all of its inputs have the value True. This can be seen in this truth table where the only occurrence of where the output has the value False is where both inputs have the value True. If you look back at the AND gate truth table you will see that the outputs for the NAND gate are the exact opposite to the outputs for the AND gate. The logic notation for the NAND gate is show here.

Ok, next; the NOR gate: A NOR gate is an OR gate followed by a NOT gate. The output has the value False only when one or more of its inputs has the value True. Or, to put in another way, its output only has the value True when none of its inputs has the value True. This can be seen in this truth table where the output has the value True only where both inputs have the value False. Again, if you look back at the truth table for the OR gate the outputs are the exact opposite to the outputs for the NOR gate. Here is the logic notation of the NOR gate.

The XOR gate: An XOR, or exclusive-OR gate acts in the same way as the logical ‘either/or.’ The output is True if either, but not both, of the inputs are True. Therefore, the output is False if both inputs are False or if both inputs are True. You could remember this by observing that the output is True if the inputs are different, but False if the inputs are the same. This is seen here in the truth table, where the output is False where both inputs are the same; and conversely the output is True where the inputs are different. Here is the logic notation for the XOR gate.

Remember, for the examination you will to know the six logic gates covered in this video, and also know and produce the corresponding truth table for each gate. Good luck!

Logic circuits video transcript

This presentation follows on from the Logic gates animation. In it we will look at how you go about creating logic circuits and the associated truth tables for the circuits.

Logic gates can be combined to produce one or more outputs from two or more inputs. We call such a combination a logic ‘circuit’, even though we are only referring to the flow of signals from the inputs to one or more outputs. We are not referring to the technical details of a full electronic circuit. In the logic circuit diagram here, input A goes to the AND gate while input B goes to both the AND gate and the NOT gate. For any logic circuit like this with two binary-valued inputs, there are 2 squared possible combinations of values. In other words 4 possible input combinations. In the examination you will need to be able to produce a truth tables for circuits like this, to show the values of an output. To do this we draw a table containing each of the four combinations of input values to show the values of an output, which we will call X in this case.

Since it may be quite hard to think through the behaviour of all the relevant gates to work out the output of a logic circuit, it is usually helpful to include columns in the truth table for the values at each intermediate output between the inputs and one or more outputs. In this example these intermediate outputs are labelled as D and E in the circuit diagram. To show this in the truth table, we include a new column for the values of intermediate output D, which will show the output from the AND gate from inputs A and B. We also include a column for the values of intermediate output E, which will show the output from the NOT gate from input B. D and E form the inputs to the OR gate, for which we need to work out the values for output X. So we adapt the Output X column heading to reflect this. Now, using our knowledge of the behaviour of AND and NOT gates, we first complete the columns for D and E. Then we use our knowledge of the behaviour of OR gates to complete the column for X.

Notice that we can write the words AND, OR, NOT, NAND and NOR as operators in logical equations that express the behaviour of the outputs D, E and X. We can also substitute the expressions for D and E in the logical equation for X, using brackets to indicate that the logical operation within the brackets takes priority. This is our logic statement. So, remembering that 1 is a numerical value representing True, we can read the statement as meaning: X = 1 only if ((A = 1) AND (B = 1)) OR (( NOT B) = 1) Since (NOT B) = 1 means B = 0, we can simplify the condition as: X = 1 only if ((A = 1) AND (B = 1)) OR (B = 0) In plain English this is X is 1 only if A and B are 1 or B is 0. This agrees with the truth table that was produced.

Three inputs and six gates will be the most complex logic circuit for which you need to be able to produce a truth table. Here is an example with three inputs. For any logic circuit with three binary-valued inputs, there are 2 to the power of 3, or 8 possible combinations of values. So we will need 8 rows in the truth table. To work out all 8 combinations and place them in a consistent order in the rows of a truth table, we can count from zero, nought nought nought in binary, to seven, one one one in binary numbers, with input A as the fours column, input B as the twos column and input C as the units column. So let’s look at the truth table for this logic circuit.

As with our first example, we first add columns for each of the inputs, A, B and C and enter the truth values in the correct logical order. Again, we also include columns for the intermediate outputs E and F, to make it easier to see what the final output X should be. We enter the values for these based upon the values in the input columns and our knowledge of the logic gates AND and NOR. Finally, we enter the values for output X, which are determined by the values for intermediate outputs E and F and our knowledge of the OR logic gate.

So you have seen how to produce a truth table and logic statement from a logic circuit diagram, but what if you are asked to draw a logic circuit diagram to represent a logic statement or condition you are given? In this example we have a condition: X = 1 if (A = 1 AND B = 1) OR (A = 1 AND C = 0) We can simplify this to produce this logic statement: X = (A AND B) OR (A AND NOT C) To draw the diagram, start with the brackets first. In this example we start with (A AND B). We use an AND logic gate and join inputs A and B to it. Then we move onto the second bracket (A AND NOT C) We add input C and place a NOT gate after it, joining C to it. Then we add in another AND gate and join input A and NOT C to it, using the appropriate indicator to link input A to the AND gate. We then complete the circuit diagram by adding in the OR gate and joining the two AND gates to it, and including the output X. In an exam you may then be asked to complete a truth table for the completed circuit, so let’s look at that next.

The logic statement will help to remind us what we need to enter into the truth table. To complete the table we first add in all the possible combinations of the inputs, A, B and C. Remember to start with 000 and finish with 111. As a true value for X can happen when both A and B are true, first look for all the combinations of where A and B are true, or 1 in the table, and for those combinations, place a 1 in corresponding row in the X column. In this case there are two possibilities of where A and B are 1, the last two rows. Then look for the combinations of A and NOT C and place a 1 in the x column against those combinations. In this case there is only one combination, the one zero zero row. For all the other outcomes place a 0 in the X column. This completes the truth table for our drawn logic circuit.

Now let’s finish by looking at solving a problem using logic gates. This problem is taken from an exam paper from a few years ago and therefore is in a style that you may get in an exam.

First we write the conditions for when X = 1 into a logic statement, which is X = (G AND NOT C) OR (C AND NOT L) Next, starting first with the brackets, we begin to draw the circuit. In this case (G AND NOT C) is drawn like this, with the input G linking to the AND gate and the input C passing through a NOT gate and then on to the AND gate. Then we draw (C AND NOT L), with both inputs linking to another AND gate and input L first passing through a NOT gate. Finally add the OR gate, linking it to the AND gates and adding output X at the end. The logic circuit diagram is now completed. So let’s now complete the truth table for this circuit, as this is something that you will almost certainly be asked to do in an exam.

The logic statement above the truth table will help to remind us what we need to enter into the table. First we enter the values for each input into the table in the logical order. As before, we then start with the first bracket in the statement, (G AND NOT C), and look for all the combinations where this is true, placing a 1 in the X column against those combinations. In this case rows, one zero zero and one zero one. Then we look at the second bracket in the statement, (C AND NOT L), and do the same. In this case we place a 1 in the rows zero one zeroand one one zero. All the other rows will be 0 as they do not comply with the condition in either bracket, so we place a 0 in those rows. We’ve now completed the truth table as well as the logic circuit diagram.

When practising logic circuits, it can be helpful if you use a program such as Logism to draw the circuits, and then test that you have correctly completed the truth table. However, remember that in your exam you have to be able to draw the logic gates freehand, so make sure that you know the symbol for each gate and can draw them correctly. Good luck!

Cambridge International AS & A Level

Graph traversal video transcript

A graph is an abstract data type, this means that it can store different types of data, that operations can be performed on the data. The data in a graph is stored in nodes, and each node is connected to one or more other nodes by vertices.

In a diagram the nodes are represented by circles, and the vertices by the lines joining the nodes. In this diagram the data is represented by letters.

A common use for graphs is to represent maps. Each node could represent a town, and each vertices the road from one town to another. This is a form of abstraction; the map has been simplified; unnecessary information has been removed.

A graph traversal is an algorithm that states how to move through the graph, visiting the different vertices to reach a destination. Many of these are used to find the shortest distance from one node to another, for example from node A to node H.

The vertices are given values, if we look back at the map example, this could be the distance in kilometres. If you are currently at town A and want to get to town H there are several routes you could take. You could go to B, then C, then F then H. Or A to B to E to G to H. Or even A to B to D to G to E to F to H. These routes all have different values, and you would probably want to take the shortest route.

So how do you find the shortest route? This is where graph traversals come in.

In this worked example we will find the shortest route from node A to node H using Dijkstra’s algorithm. Start with node A and visit each node it is connected to. Record the value.

From node B, visit all nodes that have not already been visited. Add the distance to the total distance. The A in brackets is there to remind you what the previous node was. This will be important later if you visit a node twice.

First visit node C. The total distance is 3, the 2 from A to B, and the 1 from B to C

Then visit node D, and update the Total Distance which is 7, the 2 from A to B added to the 5 from B to D

Finally visit node E. The total distance here is 4.

Now a decision has to be made, whether to continue from node C, D or E. The shortest distance is taken, which is from node C There is only 1 node to visit from C which is F. Add the total to ‘Total Distance’

Ok, we have another decision. Take the shortest distance. This time the route A-B-E has the shortest. There are 2 nodes from E, these are F and G. F has already been visited, but we visit it again in case this route is shorter.

The visit to node F is 5, which is shorter than the previous visit to F, so this can be removed from the table.

Take the shortest distance again. There are 3 that have not been followed yet, and ABEF is the shortest at 5. From F the distance to H is 3 so this is added to the ‘Total Distance’.

F is also connected to node C, the total distance to node C is now 10 which is higher than the previous visit to node C, so it is deleted from the table.

The end node has been found with a value of 8, however there are still nodes with shorter distances that could reach the end with a total less than 8.

The next shortest is ABEG, this has a current total distance of 6, so it needs to be explored.

G has two nodes attached to it, H and D. Each one needs to be explored.

The route to H is 4 so the total is 10. This is higher than the current route to H so the route is removed.

The route to D is 2 to the total is 8. This is higher than the previous visit to node D so the route is removed.

So the A* (‘A star’) algorithm is another method of finding the shortest distance from one node to another. In this case it makes use of heuristics. A heuristic is a value that can be used in a calculation to help the efficiency. In the case of a graph it is an estimate of the distance from the end destination.

Imagine this is a map again, and we want to go from town A to town H. The heuristic could be an estimate of how far each node is from the node H. So node H will be 0 because it is the destination. A value is then added to each one in turn to estimate the distance. You do not need to consider how to assign heuristics to the graphs, you just need to know how to use them.

So starting with node A we want to find the shortest distance to node H. First take the two nodes connected to node A. Add together the distance and the heuristic. The total from A to B is not 9, and the total from A to D is 11.

The decision on where to go next is made the same way as Dijkstra’s. The one with the shortest total

The distance to node B is the shortest, so the next node visited is B.

B only has 1 connection to node C, so we visit node C. This has a distance of 4, a heuristic of 1 which added to the 9 to node B gives a total of 14.

Now select the next shortest node. This is the route A-D. D has 3 connections, C E and F

Node C first has a distance of 3 and a heuristic of 1. Giving a total of 15. This is more than the previous visit to C so it is crossed out.

Node E has a distance of 1 and a heuristic of 5 giving a total of 17.

Node F has a distance of 5 and a heuristic of 5 giving a total of 21.

The next route is the shortest not visited, which is A-B-C C has 3 connections, to H, E and D

Node D has a distance of 3 and a heuristic of 8, giving a total of 25.

Node E has a distance of 2 and a heuristic of 5, giving a total of 21.

Node H has a distance of 3 and a heuristic of 0 because it is the destination, giving a total of 17.

Both the visits to D and E are greater totals than their previous visits, so these are crossed off. The end destination has been found, but it needs to be checked that there cannot be a shorter route. So look for the next smallest value. This is either ADE or ABCH, both are 17. Because ABCH is a solution, no other solution can be shorter, therefore the algorithm can stop.

If, for example, ADE had only been 16 or less, then this route would also be explored until it could be proved that 17 is the shortest route.

So to summarise, you have learnt that a graph is an example of an abstract data type that is made up of nodes (that store the data) and vertices (that connect the nodes). Graph traversals are used to visit the nodes in turn to find a route through to a specific destination. Dijkstra’s algorithm uses the distances on the vertices to total the distances travelled and takes the shortest route. In the A* algorithm each node has a heuristic that estimates the distance from the end point, this is added to the distance to find the shortest route.

Make sure you get lots of practice at using these two traversals so you can implement them in the exam. Good luck!

Linked lists video transcript

Linked lists are an abstract data type. They are a collection of data elements that are stored in a linear method. Let’s take look at how they operate.

A standard list stores each data element that is added in the next location. However, a linked list does not store each element at an adjacent location. This is why it needs the ability to link the data elements in order to know their correct order. Each data element in a linked list is called a node, and each node contains the data stored as well as a pointer. A pointer is data that references where the next data element in the list can be located. This can often be a value to represent where the data is stored.

The last node in the list does not have another data element to point to, so the pointer for this data element is called a null pointer. If data is removed from the list certain actions need to occur. Let take a look at an example;

The second item of data in this list is removed. The pointer is removed from the data element that is removed, and the pointer from the node before the data element removed is changed. It can no longer point to the removed element as it is gone, so it is changed to point to the next item in the list. When data is added to a linked list, it is added to the first available space in the list. This could be at the end of the list. In this case, the pointer from the previous node is changed from null to point to the data just added. The pointer for the data just added is now set to null.

However, if a data element has been removed from the list, this may create an earlier space in the list. For example, if item 2 is removed from the list, this becomes the next available space in the list. Therefore, the data is added to this space, and the pointer of the last item in the list is changed from null to point to the new data element added.

The pointer of the data just added then becomes the null pointer. Okay, let’s look at an example of the operation of a linked list. This linked list stores locations in the world that are part of an around the world trip. The first location in the list is stored in index 0.

The locations stored in the linked list at present are: • New York • London • Paris • Rome • Berlin • Mumbai • Kuala Lumpur • Sydney The travel company updates the trip and some of the locations change.

Berlin needs to be removed as a location and two more locations are added to the trip, Tokyo and Singapore. Tokyo will be visited after Mumbai, before Kuala Lumpur. Singapore will be visited after Kuala Lumpur and before Sydney. This is how the list is amended for the update;

Firstly Berlin is removed, and the pointer from Rome is now changed to point to Mumbai. Secondly, Tokyo is added to the next available space, which is the space left from removing Berlin.

Tokyo will be visited after Mumbai, but before Kuala Lumpur; so, the pointer from Mumbai is changed to point to Tokyo, and the pointer from Tokyo is set to point to Kuala Lumpur. Thirdly, Singapore is added to the list in the next available space, which is after Sydney.

Singapore will be visited after Kuala Lumpur and before Sydney, so, the pointer from Kuala Lumpur is changed to point to Singapore and the pointer from Singapore is set to point to Sydney.

An array can be used to store a linked list. Each item of data in the linked list is stored in an element of the array.

Linked list structures can be useful when storing data in an array, especially if the data needs to be in a certain order. If an item of data is added to the array that needs to appear in the middle of the order, this can be an expensive process in terms of time and resources for the computer. It will need to shift items around in the array to make space for the new data. However, if the data is stored in the array as a linked list, then it will just be the pointers that need to be changed.

Why not try creating some linked lists of your own? Good luck!

Stacks and queues video transcript

Stacks and queues are two abstract data types. Let’s take a look at how they operate. A stack is a collection of data elements that are stored in a linear method. A simple way to view this is as a vertical stack of blocks, like this. There are two main operations that are used to manipulate the data in the stack, these are push and pop. The push operation adds a data element to the stack. The pop operation removes a data element from the stack.

A stack operates as a last in first out structure. This means that the last item that is pushed to the stack when data is added, is the first item that is popped from the stack when data is removed. When data is added to the stack, the push command is used along with the data element that needs to be added to the stack. When data is removed from the stack the pop command is used. That will remove the last element of data added to the stack.

Okay, Let’s take a look at another stack. This stack currently stores the colours red, blue and yellow. Here is a set of commands for the stack: • POP • PUSH Green • PUSH Purple • PUSH Orange • POP • PUSH Pink Let’s follow the commands and see how they affect the stack: • First Yellow is removed from the stack • Then Green, Purple and Orange are added to the stack • Then Orange is removed from the stack • Finally, Pink is added to the stack The size of a stack needs to be defined. This means that the maximum number of data elements in the list needs to be defined. For example, the stack size of this stack is 5. If there are 5 data elements in the stack and the system tries to add another data element, a message is sent to report that the stack is full and the additional data cannot be added. If all the data elements are popped from the stack and the systems tries to remove another data element, a message is sent to report that the stack is empty and that there is no data to be removed. The bottom of the stack will always remain in the same place, it has a static position. The top of the stack however is dynamic and will move each time a data element is pushed to or popped from the stack. One common application of the use of stacks is backtracking. In the backtracking process, a system may need to remove the last actions that have taken place in order to get back to an earlier stage of the process. Therefore, a stack is easy to use in this situation as the items pushed to the stack can be just popped off it.

Okay, now we’ve reviewed stacks, let’s take a look at Queues. A queue is also a collection of data elements that are stored in a linear method. A simple way to view this is as a horizontal line of blocks. A queue uses the same two main operations to manipulate data as a stack; push and pop. A queue operates as a first in first out structure. This means that the first item that is pushed to the queue when data is added, is the first item that is popped from the queue when data is removed.

Let’s look at an example; This queue currently stores the colours red, blue and yellow. Here is a set of commands for the queue: • POP • PUSH Green • PUSH Purple • PUSH Orange • POP • PUSH Pink

Let’s follow the commands and see how they affect the queue: • First red is removed from the front of the queue • Then Green, Purple and Orange are added to the end of the queue • Then Blue is removed from the front of the queue • Finally, Pink is added to the end of the queue

As with stacks, the size of a queue also needs to be defined. This queue has a size of 5. If there are 5 data elements in the queue and the system tries to add another data element, a message is sent to report that the queue is full and the data cannot be added. If all the data elements are popped from the queue and the system tries to remove another data element, a message is sent to report that the queue is empty.

Both the front and end of the queue are dynamic positions in a queue. This is because the front of the queue will move if data is popped from the queue, and the end of the queue will move is data is added to the end of the queue.

One common application of a queue is a job list for a printer. Each time a computer sends a print job to the printer it is placed in a queue. Each time the printer begins to print a job it can be removed from the queue.

An array can be used to implement both a stack and a queue. Each element in the array stores a data element in the stack or queue.

Why not try designing your own stacks and queues? Good luck!

Topic outline