In order for letters and other characters to be stored on computer systems this information must be encoded as binary codes. This is because computers can only actually store 1s and 0s which relate to high and low voltages. Agreed set of codes are used to represent all characters, the most important being standard 7-bit ASCII (American Standard Code for Information Interchange) which 128 possible combinations of 1s and 0s, in addition to Unicode which is 16-bit and as such has 2 to the power of 16 or 65536 combinations.
When using ASCII the binary representations of actual digits (0-9) is different to how those numbers would actually be represented in binary if they were being operated upon or stored. For example, the number 1 would usually be 0000001 in binary, but when being represented as a character it is 0110000 (48).
Some forms of ASCII may have an extra digit used for an extended character set (256 characters), many of which are used for various symbols, mathematical operations and letters from other languages. The extra digit (to make it 8-bit) is most often used for error checking however which is important for receiving text correctly.
ASCII is a very limited character set even with 256 different characters, as it only contains letters from European languages including English and French which use the Latin alphabet originating from the Romans. As such there is no way to represent letters from languages such as Arabic or those based upon the Cyrillic alphabet. So these characters can be represented Unicode must be used. It is 16-bit, and as a result this is sufficient for all characters from all languages, plus mathematical and other symbols.
There are two main types of error checking which are even bit checking, and odd bit checking. These are used because just one incorrect binary digit per character can result in the characters in a passage of text changing and it not being understandable. Both rely upon the use of the 8th bit. In odd bit checking the number of 1s must always be odd, and as such if the 7-bit ASCII code has an even amount of 1s then the check bit will be a 1, making the number of 1s odd. If the number of 1s is not odd when received it will be assumed that the data has been sent incorrectly, or has been interfered with and as such will be requested again.
Even-bit checking is the opposite, as the number of 1s must be even and the check digit is used to achieve a similar outcome, and if the number of 1s is odd when received it will be considered incorrect. Even bit checking is potentially flawed, as if two bits were flipped then the fact that it is incorrect would not necessarily be detected once the code was received.
Error checking refers to superior techniques that may be used in addition to or instead of error detection techniques. The Majority Vote method is the most common of these, which is a process during which a code is sent three times, and the most common value for each bit is used. Therefore if two out of three codes show a 1 in the 4th position, but the third code shows a 0 then it will be assumed that this has been corrupted, and that the correct digit is a 1. This can be used to correct numerous errors, and its only flaws are that a large amount of data has to be sent, in addition to the fact that if a large amount of the codes sent were corrupted then it could receive an incorrect majority, although the chances of this happening are low.
There are two other error correction methods known as Hamming code and Gray code. Hamming code utilises positions of powers of 2 as parity bits, and the other integers as locations for data to be encoded. Depending upon the position of the parity bit, different patterns of checking and skipping are used. The checking method with position n can be summed up however with the checking pattern skip n - 1 bits, then in turn check n bits and skip n bits. It has a number of sets of parity bits (often 4), and in each set there will be an odd number of binary digits initially, but an even parity will be used. As such a check digit is included in the same manner as previously mentioned to make sure the number of 1s is always even.
With Gray code every number in a specific range can be represented, and as such there are no 'in-between' values. It is also considered to be more reliable than standard binary because there is less likely to be an error due to a slow response time. Using Gray code only one digit is changed at a time, whilst when using binary multiple digits could. Gray code counters also use less energy than their binary equivalents. One of their key uses is for passing information between microchips that operate on different frequencies.
Tuesday, 29 March 2011
Wednesday, 23 March 2011
Binary Numbers, Binary Arithmetic and Hexadecimal
Computers store numbers in binary, long sequences of 0s and 1s which correspond to low and high voltages. Each 0 or 1 is known as a Bit, and 8 bits make up a Byte. If Bytes are grouped together they make up what are known as words. Unlike denary which works in base 10 where each place is worth 10 times the one to the right, binary works in base 2 because each digit has twice the value of the one to the right. As such the number 5 in denary would be 101 in binary, because it is (1x1) + (0x2) + (1x4). If converting a binary number to denary one a similar method is used - so 33 is 100001 because it is (32x1) + (16x0) + (8x0) + (4x0) + (2x0) + (1x1).
When adding binary numbers a method of 'carrying' digits is used if there is more than one '1' in a place. As such if there are two 0s the place is 0, a 1 and a 0 would be 1, two 1s would result in a 1 being carried making 10 and three 1s would result in a 1 being carried and a 1 being kept making 11. For example, if one were to add 1101 and 1010, then 10111 would be the result, as the two 1s in the 8 column would be carried, as 2 x 8 = 16, meaning the next column would contain a 1. The next column would contain a 0, whilst the other three would contain 1s because there are two subsequent 1s in the first number, and one in the second number - all in different columns.
Binary multiplication has similarities to denary multiplication, as it is done with respect to place value. If multiplying only by a 1 in the furthest right column then the number does not change, or if there are more 1s it is added to the total. On the other hand if a binary number is multiplied by a number with at least two places (therefore one with a value of at least 2) then the number of places after the 1 is added to the end of the binary number as 0s, meaning that it moves up places. For example, 100 x 101 would be 10000 +100 = 10100. This is because the 101 has merely moved up two places.
Negative numbers can also be represented using binary through utilising Two's Complement. To convert a positive binary number to a negative one the digits are simply inverted, and then 1 is added. The denary number 7 is 0111 in binary, and this is flipped to become 1000, and then 1 is added to make it 1001. This method of 'flipping' the bits is used so that computers are able to store negative numbers. Also worth mentioning are most and least significant bits. Positive numbers have 0 as the MSB, whilst it is 1 with negative numbers. Odd numbers have 1 as the LSB, whilst it is 0 with even numbers.
With this knowledge it is possible to subtract binary numbers. This is most easily done by turning the number into a negative one and then adding it. For example, 7 - 5 would become -5 + 7, or 1011 + 0111, with an answer of two in denary, or 0010 in binary.
Hexadecimal refers to a base 16 number system, which is used for representing numbers shorthand. Each digit/letter is has a value of 16 times what it would have one place to the right. It is often favoured over binary because that will have long chains of 0s and 1s, whilst a number's hexadecimal equivalent will be much shorter. The numbers 0-9 are used in hexadecimal for their respective values in binary, but then the letters A-F are used for the numbers 10 to 15 in denary, and '10' is used for 16 in denary. An example of this would be the number 38. If this number is divided by 16 one gets 2 remainder 6, so a 2 is placed in the column with a value of 16x the digit, and a 6 in the column with a value of 1x the digit- so 38 in denary is 26 in hexadecimal. Letters are only generally used for larger numbers - an example being 173. This is (10 x 16) + 13, making the hexadecimal number AD.
Lastly decimals may also be represented using binary, with use of a binary point. Beyond the binary point are values of 2 to negative powers (or 1 over 2 to powers), each being half the value of the one to the left. For example the number 5.25 would be 101.01 as 101 is 5 in binary, and .01 in binary is zero halves + one quarter. Although processing is quick using this system, there is a limited range of fractions available. As such it would be difficult if possible to represent a denary number like 134.62 in binary.
When adding binary numbers a method of 'carrying' digits is used if there is more than one '1' in a place. As such if there are two 0s the place is 0, a 1 and a 0 would be 1, two 1s would result in a 1 being carried making 10 and three 1s would result in a 1 being carried and a 1 being kept making 11. For example, if one were to add 1101 and 1010, then 10111 would be the result, as the two 1s in the 8 column would be carried, as 2 x 8 = 16, meaning the next column would contain a 1. The next column would contain a 0, whilst the other three would contain 1s because there are two subsequent 1s in the first number, and one in the second number - all in different columns.
Binary multiplication has similarities to denary multiplication, as it is done with respect to place value. If multiplying only by a 1 in the furthest right column then the number does not change, or if there are more 1s it is added to the total. On the other hand if a binary number is multiplied by a number with at least two places (therefore one with a value of at least 2) then the number of places after the 1 is added to the end of the binary number as 0s, meaning that it moves up places. For example, 100 x 101 would be 10000 +100 = 10100. This is because the 101 has merely moved up two places.
Negative numbers can also be represented using binary through utilising Two's Complement. To convert a positive binary number to a negative one the digits are simply inverted, and then 1 is added. The denary number 7 is 0111 in binary, and this is flipped to become 1000, and then 1 is added to make it 1001. This method of 'flipping' the bits is used so that computers are able to store negative numbers. Also worth mentioning are most and least significant bits. Positive numbers have 0 as the MSB, whilst it is 1 with negative numbers. Odd numbers have 1 as the LSB, whilst it is 0 with even numbers.
With this knowledge it is possible to subtract binary numbers. This is most easily done by turning the number into a negative one and then adding it. For example, 7 - 5 would become -5 + 7, or 1011 + 0111, with an answer of two in denary, or 0010 in binary.
Hexadecimal refers to a base 16 number system, which is used for representing numbers shorthand. Each digit/letter is has a value of 16 times what it would have one place to the right. It is often favoured over binary because that will have long chains of 0s and 1s, whilst a number's hexadecimal equivalent will be much shorter. The numbers 0-9 are used in hexadecimal for their respective values in binary, but then the letters A-F are used for the numbers 10 to 15 in denary, and '10' is used for 16 in denary. An example of this would be the number 38. If this number is divided by 16 one gets 2 remainder 6, so a 2 is placed in the column with a value of 16x the digit, and a 6 in the column with a value of 1x the digit- so 38 in denary is 26 in hexadecimal. Letters are only generally used for larger numbers - an example being 173. This is (10 x 16) + 13, making the hexadecimal number AD.
Lastly decimals may also be represented using binary, with use of a binary point. Beyond the binary point are values of 2 to negative powers (or 1 over 2 to powers), each being half the value of the one to the left. For example the number 5.25 would be 101.01 as 101 is 5 in binary, and .01 in binary is zero halves + one quarter. Although processing is quick using this system, there is a limited range of fractions available. As such it would be difficult if possible to represent a denary number like 134.62 in binary.
Tuesday, 1 March 2011
Finite State Machines
Finite State Machines refer to mechanise systems which may change between a pre-defined number of 'states', which refer to different situations, the most basic example being 'on' or 'off'. These systems also contain inputs which cause a change between states, as well as possibly outputs. If there are no outputs then the system will be known as a Finite State Automaton and have a 'goal' or 'accept' state. They can be represented as state transition diagrams, as depicted below with arrows as transitions between states due to inputs. In these diagrams there is an initial state denoted with a start arrow, and the accept state will be shown by a double circle.
Those Finite State Machines with outputs do have an initial state, but not an 'accept' state. They are known as Mealy Machines. A state transition diagram for a vending machine, an example of one, is shown below.
Transition tables can also be used for these systems and they differ depending upon whether the FSM has an output. The first table is for the first FSM, whilst the second table is for the second FSM.
Decision tables let one consider the possible combinations and what should happen as a result.
Example: if the week day is odd then output A, if it is even then output B
Y = Yes, N = No
Psuedo code can also used to represent these problems as they would be using similar syntax to inside a computer program, but not in a programming language. For the example shown above the pseudo code would be something like:
If Day = Odd, then Output A
Else Output B
Those Finite State Machines with outputs do have an initial state, but not an 'accept' state. They are known as Mealy Machines. A state transition diagram for a vending machine, an example of one, is shown below.
Transition tables can also be used for these systems and they differ depending upon whether the FSM has an output. The first table is for the first FSM, whilst the second table is for the second FSM.
Input | Current State | Next State |
Nothing | S0 | S0 |
Incorrect Code | S0 | S1 |
Nothing | S1 | S0 |
Correct Code | S0 | S2 |
Nothing | S2 | S0 |
Input | Current State | Output | Next State |
0p | S0 | 0 | S0 |
50p | S0 | 0 | S1 |
50p | S1 | 1 | S2 |
£1 | S0 | 1 | S2 |
0p | S2 | 0 | S1 |
Decision tables let one consider the possible combinations and what should happen as a result.
Example: if the week day is odd then output A, if it is even then output B
Conditions | Specific Data | |
Mon/Wed/Fri/Sun | Y | N |
Tues/Thurs/Sat | N | Y |
Output A | Y | N |
Output B | N | Y |
Y = Yes, N = No
Psuedo code can also used to represent these problems as they would be using similar syntax to inside a computer program, but not in a programming language. For the example shown above the pseudo code would be something like:
If Day = Odd, then Output A
Else Output B
Subscribe to:
Posts (Atom)