Introduction to Leaf
Inventor Leaf came up with a device for transmitting numbers. His device transmitted messages in the form of a chain of short and long signals. In his notes, Listik denoted a short signal with the number “0”, and a long one with the number “1”. When transmitting numbers, he used the following code for each digit:
The number 12, consisting of the numbers 1 and 2, Listik wrote down for transmission as follows:
The device transmitted this message in a chain of such signals: three short, one long, two short, one long and one short.
The number 77 according to the Listik system was encoded as follows:
Information encoding
Encoding is the transfer of information into a form convenient for transmission or storage.
For example, texts are encoded using letters and punctuation marks. At the same time, the same record can be encoded in different ways: in Russian, in English, in Chinese ...
Numbers are encoded with digits. The numbers we are used to are called Arabic. Sometimes Roman numerals are used. In this case, the way information is encoded changes. For example, 12 and XII are different ways of writing the same number.
Music can be encoded using special signs - notes. Road signs are coded messages to drivers and pedestrians using pictograms.
Products in the store are marked with a barcode that contains information about the product and its manufacturer.
A barcode is a sequence of black and white stripes that encodes information in a form that is easy to read by technical devices. In addition, a code in the form of a series of numbers can be placed under the barcode.
Information is always stored and transmitted in the form of codes. You can not store just information, without a medium. In the same way, one cannot simply store and transmit information: it always has some form, that is, it is encoded.
Binary coding
Binary coding is the encoding of information using zeros and ones. For computer technology, this way of presenting information turned out to be very convenient.
The fact is that computers are built on elements that can be in two possible states. One such state is denoted by the number 0, the other by the number 1.
An example of a binary device is a conventional electric light bulb. It can be in one of two states: on (state 1) or off (state 0).
It is possible to build an electric memory on light bulbs and store in it, for example, numbers using Leaf's binary code.
Four light bulbs are required to store each decimal digit. This is how you can remember the number 6:
We set the switches to the right position - and went to drink tea! If the electricity is not turned off, the information will be saved.
Light bulbs, of course, are not suitable for the production of computers: they are large, burn out quickly, are expensive (after all, millions of them are needed), and the environment is very hot.
In modern computers, an electronic device - a transistor - is used as a memory element.
The transistor can pass current through itself (state 1) or not (state 0).
There was a time when each transistor was made separately and was significant in size.
Now transistors, like other electronic components, are made in a way similar to photo printing. One microchip the size of a fingernail, several million transistors can be printed.
The code that Leaf encoded messages is actually used to work with numbers in a computer.
With binary coding, you can not look at this table at all, but remember a simple rule for converting a binary code into a decimal digit.
The unit in the code in the first place on the right gives the number
lo 1, on the second - 2, on the third - 4, on the fourth - 8. To get a decimal digit, the numbers are added. For example, the code “0101” is translated into the number 5 (the sum of the numbers 4 and 1).
The same rule can be used for decoding. For example, the number 6 is written as the sum of the numbers 4 and 2, which means that its code will be “0110”.
A tablet with numbers written in the number system used in ancient Babylon. Approximately 1700 BC Deciphered in 1945
Number systems
Leaf Code and Number Encoding
The previous lesson showed how to write numbers using zeros and ones. Leaf encodes every digit number four binary signs.
So, the number 102 is written with the Leaf code using 12 binary characters:
Leaf encodes separately each of the 10 digits and uses 4 binary digits for this. But four binary characters can encode not 10, but 16 values:
It turns out that 6 Leaf codes (which is more than half of 10) are wasted!
Is it possible to code more economically?
It is possible if you encode not numbers(from which the number is collected), and immediately numbers! So, the number 102, with this encoding method, can be written not with twelve, but only with seven binary characters (we save 5 digits):
Such coding will be covered in this tutorial. But let's start in order.
Decimal number system
As you know, numbers are built from digits, and there are only ten digits, here they are:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
How, then, with the help of only ten digits, write down large numbers? We will see this now, but first remember the definition:
The way numbers are written is called number system.
learned word reckoning, consonant with the word "calculation", already means "a way of writing numbers." But it seemed to mathematicians that the phrase notation sounds better. Nothing, we will also master this two-word term! Now let's take a look at that number system to which they are accustomed.
Look at the number 253. In this entry, the first number from the right (it is called low digit) means “three ones”, five means “five tens”, and two ( highest digit) - "two hundred".
It turns out: 253 = 2 100 + 5 10 + 3 1.
We are speaking: "two hundred and fifty three". This means the number that is obtained by addition:
two hundred (2 100 = two hundred),
five tens (5 10 = fifty) and
three units (3 1 = three).
We see that the value of a digit in a number entry depends on positions in which the digit is located. The positions of the numbers are called differently discharges numbers.
The lower digit means units:
The second digit from the right means tens:
The third digit from the right means hundreds:
We see that the contribution of a digit to a number increases from right to left.
Number systems in which the contribution of a digit to a number depends on positions the numbers in the record are called positional number systems.
The number system familiar to us is positional, as we have seen. Note that in basis it is assigned the number 10 - the number of digits used.
The lower digit shows the number of units in the number, the second from the right - the number of tens (1 10). The third - shows hundreds (10 10), the fourth - thousands (10 100) and so on.
We count by units, units are added to tens (ten units are replaced by one tens), tens are added to hundreds (ten tens are replaced by one hundred), and so on.
The number 10 is the basis of the usual number system, so it is called decimal system, or the number system according to foundation 10.
Look again at how the entry 2789 translates into a number.
The number is obtained by adding deposits the numbers included in it:
The contribution of each digit is obtained by multiplying that digit by a multiplier that depends on the position and is associated with the base of the system.
Position multipliers are calculated according to the following rule:
1. The multiplier of the first (right) position is equal to 1 .
2. The multiplier of each next position is obtained by multiplying the base of the system (number 10 ) by the multiplier of the previous position.
The position multipliers will be called position weights, or positional scales.
The number is equal to the sum of deposits. The contribution is equal to the product of the digit and the positional weight. The weight of the first position is 1, the second is 10, the third is 100, and so on. That is, the weight of each position (except the first one) is obtained from the weight of the previous one by multiplying by the base of the system. The weight of the first position is equal to one.
That's how: they multiplied, added and did not suspect! It turns out that we write numbers in positional number system base ten! Why is the base of our system equal to 10? Well, this is understandable: after all, we have 10 fingers, it is convenient to count by bending them in order.
But for a computer, as you already know, the binary system is more familiar, that is positional number system base two.
Binary number system
There are only two digits in the binary number system:
If in the decimal system the position weights are obtained by multiplying by ten, then in the binary system - by multiplying by two:
It turns out: 1011 2 = 1 2 · 4 + 0· 2 · 2 + 1 2 · 1 + 1 1 .
In the binary system, they count as units, units add up to twos (two units are replaced by one two), twos are added to fours (two twos are replaced by one four), and so on.
When you need to clarify in which system a number is written, the base of the system is attributed to it from below:
1011 2 - the number is written in the binary system.
It is not difficult to convert it to the decimal system, you just need to perform multiplication and addition operations:
1011 2 = 1 2 · 4 + 0· 2 · 2 + 1 2 · 1 + 1 1 =
1 8 + 0 4 + 1 2 + 1 1 = 11 10 .
Binary to decimal conversion
In the binary system, the contribution of one in the first place from the right is the number 1, in the second - 2, in the third - 4, in the fourth - 8, and so on. The contributions of the zeros are, of course, equal to zero regardless of their positions.
We get the following rule:
To convert from binary to decimal, you need to write down the weight of its position over each binary digit and add the numbers written over the units.
10111 2 = 16 + 4 + 2 + 1 = 23 10 .
Another example, the number 100110:
100110 2 = 32 + 4 + 2 = 38 10 .
Convert from decimal to binary
To convert from decimal to binary, we will use the previous scheme with position weights:
Let it be necessary to convert the number 26 to the binary system. We select the beginning of the binary number (highest digit) according to the scheme. 32 is a lot, so we start with 16:
Part of the original number, namely 16, is encoded, it remains to encode 26 - 16 = 10. We take 8 (the largest of the possible positional weights):
It remains to encode 10 - 8 = 2. Four is a lot. We write to position 0 and take 2:
We encoded the whole number, so the last digit must be zero:
It turns out: 26 10 \u003d 11010 2.
The decimal-to-binary conversion rule can be formulated as follows.
To better understand this algorithm, work on the test bench. Click the button Reset, dial the number. Then press the button Start: you will see how the Tester performs the algorithm for converting a number to a binary system in steps.
Please note: in the algorithm record, the item that will be executed is highlighted after pressing a button Start. For example, if the item is highlighted “Repeat until the number goes to zero”, then after pressing Start The tester will check the current number for zero and decide whether to continue the repetition.
(Perform the tester on the e-application page.)
Positional systems with other bases
Vasya loves the decimal system, his computer loves binary, and curious mathematicians love different positional number systems, because you can take any number as a base, not just 2 or 10.
Let's take the ternary number system as an example.
Ternary number system
The ternary number system uses, you guessed it, three digits:
In the ternary system, they count as units, units add up to triplets (three units are replaced by one triple), triplets into nines (three triplets are replaced by one nine), and so on.
Interestingly, in 1958, under the leadership of N.P. Brusentsov, the Setun computer was created at Moscow State University, and it worked with numbers not in binary, but in the ternary number system! The first prototype of the "Setun" is shown in the photo:
Convert from ternary to decimal
Let us designate the positional contributions of digits in the ternary number system on the diagram:
To convert to the decimal system, we add the numbers multiplied by their positional weights (positions with zero digits, of course, can be omitted):
10212 3 = 1 81 + 2 9 + 1 3 + 2 1 = 104 10 .
In the binary system, we did without multiplication (it makes no sense to multiply by 1). There is a number 2 in the ternary system, so you have to double the corresponding positional weights.
Decimal to ternary conversion
Let it be necessary to translate the number 196 into the ternary system. We select the beginning of the ternary number according to the scheme. 243 is a lot, so we start with 81 and the number 2 (2 81< 196):
Part of the original number, namely 162 = 2 81, is encoded, it remains to encode 196 - 162 = 34. We take 27 and the number 1 (the number 2 gives 54, which is too much):
It remains to encode 34 - 1 27 = 7. The position with a weight of 9 gives too much, we write 0 into it and take a position with a weight of 3 and the number 2:
It remains to encode 7 - 2 3 = 1. This is just the value of the remaining minor digit:
It turns out: 196 10 \u003d 21021 3.
Positional systems: basic rules
Let us formulate the general rules for constructing numbers in positional number systems.
The number is written in numbers, for example:
To determine the value of a number, you need to multiply the digits by the weights of their positions and add the results.
Positions are numbered from right to left. The weight of the first position is 1.
The weight of each next position is obtained from the weight of the previous one by multiplying by the base of the system.
It turns out that the weight of the second position is always equal to the base of the system.
The base of the system shows the number of digits that is used in this system. So, in a system with a base of 10 - ten digits, in a system with a base of 5 - five digits.
Consider an example. If the entry
means a number in the system with base 5, then it is equal to
3242 5 = 3 125 + 2 25 + 4 5 + 2 1 = 447 10 .
The same notation in base 6 means a number
3242 6 = 3 216 + 2 36 + 4 6 + 2 1 = 746 10 .
Non-positional number systems
Positional number systems did not appear immediately, primitive people denoted the number of some objects by an equal number of others (considered pebbles, sticks, bones).
More convenient counting methods were also used: notches on a stick, dashes on a stone, knots on a rope.
Sometimes modern people also use such a number system, marking, for example, the number of days that have passed by notches.
That's an example non-positional unit number system: used for counting one digit (stone, stick, bone, dash, knot ...), and the contribution of this digit does not depend on its place (position), it is always equal to one unit.
It is clear that using positional number systems is much more convenient.
Actions on numbers
Operations on numbers in the positional system with any base are performed in the same way as in the decimal system: they are based on the addition and multiplication tables of the digits of the corresponding number systems.
It would be strange if in different systems to add, subtract, multiply and divide would have to be different! Indeed, in all number systems, numbers are built in the same way, which means that actions on them must be performed in the same way.
Let's look at a few examples.
Addition
5 + 7 = 12. We write 2 in the least significant digit, and add one to the next digit.
Let's build an octal addition table:
According to the addition table 5 + 7 \u003d 14 8. We write 4 in the least significant digit, and add one to the next digit.
Subtraction
We take 1 in the second digit and subtract 7 from the number 15. Similarly, in the octal system:
We take 1 in the second digit and subtract 7 from the number 15 8 . According to the addition table in line 7, we find the number 15. The number of the corresponding column gives the result of the difference - the number 6.
That's probably convenient for spiders to use
octal number system!
Multiplication
2 7 =14. We write 4, and 1 goes to the “mind” (add to the next category). 4 7 \u003d 28. We write 9 (8 plus 1 from the “mind”) and transfer 2 to the next digit.
Let's build an octal multiplication table:
2 7 = 16 8 . We write 6, and 1 goes to the “mind” (add to the next digit). 4 7= 34 8 . We write 5 (4 plus 1 from the “mind”) and transfer 3 to the next digit.
Division
3 5< 17 < 4·5, поэтому первая цифра результата - 3. Из 17 вычитаем 5·3 = 15. К разности 2 приписываем цифру 5, получается 25. 25 = 5 ·5. Из 25 вычитаем 25=5·5, получается 0 - деление закончено.
In the multiplication table in line 5 we find the appropriate number 17 8 = 5 3:
This means that the first digit of the result is 3. From 17 8 we subtract 17 8 = 5 3. We attribute the last digit 5 to the difference 0. 5 \u003d 5 1. Subtract 5 from 5, it turns out 0 - the division is completed.
Questions
1. Define the term “number system”.
2. Define the term “positional number system”.
3. Explain the principles of constructing numbers in the decimal number system using the example of the number 548.
4. What is called position weight? Tell the algorithm for finding the position weight. What is the weight of the third position from the right in the decimal representation of the number? And in binary? And in ternary?
5. What is meant by a discharge? In what digit is the number 5 in the decimal number 1532?
6. What is called the contribution of a figure? What is the contribution of the number 7 in the number 1745 10 ? What about the contribution of the number 4 in the number 1432 5 ?
7. Define the term “base of the positional number system”. How is the base of the system related to the number of digits in this system? How many digits are in the 5-decimal number system? And in hexadecimal? What about base 25?
8. Where is the lowest digit in the number entry? And the older one?
9. Tell the algorithm for converting a binary number to a decimal number system and perform this algorithm for the number 101101 2.
10. Tell the algorithm for converting a decimal number into a binary number system and perform this algorithm for the number 50 10.
11. How to convert a number from any positional number system to a decimal system? Build an explanation using the example of a system with base 4.
Hometasks
Option 1. Performed without a computer, “on paper”
1. Read tongue twisters, replacing binary numbers with decimal ones:
Ate well done
100001 2 pies with a pie,
Yes, with cottage cheese.
There were 101000 2 mice,
Carried 101000 2 groszy,
And 10 2 mice are worse
They carried 10 2 grosz each.
2. Solve binary-letter puzzles:
3. Perform calculations and write down the answer in decimal notation:
1) 100 2 5 8 =
2) 100 3 + 100 5 =
3) 10 9 10 100 – 10 900 =
4) 33 4 + 44 5 =
5) 15 6 + 51 8 =
4. Translate the given numbers into the indicated number systems:
Option 2: Run on a computer
1. Write an arithmetic expression to solve the following problem and calculate the answer:
Our clever Malvina
Guardians of Pinocchio
And bought for him
What he needs the most:
10 2 covers, 11 2 rulers
And stickers for 111 2 rubles.
On the covers - Barmaley,
The price of each is 101 2 rubles.
On the line that I bought
101010 2 rubles was enough.
How much did the purchases cost?
Thinking for half a minute.
2. Try to use the standard Calculator program to convert numbers from a poem into a familiar decimal notation ( View- Engineering, Bin- binary representation of a number, Dec- decimal representation of a number). Write down algorithms for converting numbers using the Calculator from binary to decimal and vice versa, from decimal to binary.
Option 3. For the curious
1. Prove that the entry 10 in any positional number system means a number equal to the base of this system.
2. Determine the base of the positional number system b for each equality:
1) 10 b = 50 10 ;
2) 11 b = 6 10 ;
3) 100 b = 64 10 ;
4) 101 b = 26 10 ;
5) 50 b = 30 10 ;
6) 99 b = 909 10 ;
7) 21 b = 15 6 ;
8) 10 2 b = 100 b ;
9) 12 2 b = 22 b ;
10) 14 b· b = 104 b .
p ALIGN="JUSTIFY">3. The hexadecimal number system uses 16 digits. The first ten digits coincide with the digits of the decimal system, and the last ones are indicated by the letters of the Latin alphabet:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
Meaning |
|
Let's translate, for example, the number A8 16 into the decimal system:
A8 16 = 10 16 + 8 1 = 168 10 .
In each task, find the value of the number x:
1) 25 16 = x 10 ; 4) 170 10 = x 16 ;
2) AB 16 = x 10 ; 5) 2569 10 = x 16 ;
3) FD 16 = x 10 ; 6) 80 32 = x 16 .
4. Complete the following tasks.
1) Find the weight of the third position in the number entry, if it is known that the weight of the second position is 7. The numbering of positions is from right to left.
2) The number system uses 5 digits. Find the weight of the fourth position from the right in the number entry.
3) The number is written as two units: 11. In what number system is it written if it is 21 in decimal?
4) In a certain number system, the number looks like 100. How many digits does this number system use if the number is 2500 in decimal?
5) Two numbers are written as 100, but in systems with different bases. It is known that the base of the first system is twice the base of the second. Which number is greater and by how much?
6) Find the base of the system if it is known that the number 101 written in this system means the decimal number 37.
7) In what number system do you need to add zero to the right of its record to double a number?
8) Multiplying by 10 in decimal means adding zero to the right of the number. Formulate the rule for multiplying by 10 b in a system with a base b.
5. Formulate an algorithm for converting a number from decimal to ternary number system.
6. Build addition and multiplication tables for the quaternary number system. Using these tables, perform the following actions on numbers in a column (remaining in the quaternary number system):
1. a) 1021 4 + 333 4 ;
b) 3333 4 + 3210 4 ;
2. a) 321 4 - 123 4 ;
b) 1000 4 - 323 4 ;
3. a) 13 4 12 4 ;
b) 302 4 23 4 ;
4. a) 1123 4:13 4 ;
b) 112003 4:101 4 .
7. Build addition and multiplication tables for the binary number system. Using these tables, perform the following actions on numbers in a column (remaining in the binary number system):
1. a) 1001 2 + 1010 2 ;
b) 10111 2 + 1110 2 ;
2. a) 1110 2 - 101 2 ;
b) 10000 2 - 111 2;
3. a) 101 2 11 2 ;
b) 1110 2 101 2 ;
4. a) 1000110 2:101 2 ;
b) 100000100 2:1101 2 .
Workshop
On the pages of the electronic application, work with the performer Encoder.
The exercises contain the following groups of tasks:
to decimal
1. From binary to decimal
2. From ternary to decimal
3. From quinary to decimal
4. Hex to Decimal
From decimal
1. From decimal to binary
2. From decimal to ternary
3. From decimal to quinary
4. From decimal to hexadecimal
Class 1
2. 1101 2 = ? 10
3. 11101 2 = ? 10
Credit class 2
10. 1001 2 = ? 16
Teacher material
Positional number systems
In the positional number system, a number is written as a string of special characters:
a n a n–1 ... a 2 a 1 (1)
Symbols a i called figures. They denote ordinal countable quantities, starting from zero and down to the value one less number. q called basis number systems. That is, if q- base, then the values of the digits lie in the interval (including the boundaries).
The position of the digit in the notation of the number (1) is called it position, or discharge.
Note 1. On these pages, the term “position” is preferred. Firstly, the word “position” is in good agreement with the concept of “positional number system”, and secondly, the term “positional weight” or “position weight” sounds better, clearer and simpler than “digit weight” or “digit weight”. However, the teacher can and should remind students from time to time that "position" and "rank" are equivalent terms.
Note 2. The definition of the positional number system given in the texts for the student is not entirely accurate. The mere dependence of the contribution of a digit on the position is not enough. For example, in the Roman numeral system, the contribution of a digit also depends on the position (the numbers IV and VI are different), but this system is not positional. The exact definition can be considered the entire set of rules for constructing a number, given in this context for the teacher (that is, along with the fact of positional dependence, the definition includes: the finiteness of the set of digits and the rule for finding a number from its record).
Positions are numbered from right to left. The number in the first position is called junior digit of the number, in the last - senior.
Each position has a number associated with it, which we will call its weight ( position weight).
Position weights are determined by the following recursive rule:
1. The weight of the lowest position is 1.
2. The weight of each next position is obtained from the weight of the previous one by multiplying by the base of the system.
Let q- the base of the number system. Then the rule for calculating positional weights w i can be written more concisely as a recursive formula:
1. w 1 = 1.
2. w i = w i-one · q(for all i > 1).
In the positional number system, the notation
a n a n–1 ... a 2 a 1 (1)
means number N, equal to the sum of the products of digits by their positional weights:
N= a n· w n + a n-one · w n–1 + ... + a 2 · w 2 + a one · w 1 . (2)
The product of a digit and its positional weight (i.e. a i· w i) will be called positional contribution of the digit.
Formula (2) is the basis for the rules for transferring numbers from one system to another, proposed in the texts for the student.
In the decimal number system, numbers are written using ten Arabic characters: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
The positional weights of this system are: ..., 1000, 100, 10, 1.
4627 10 = 4 1000 + 6 100 + 2 10 + 7 1.
In the binary number system, numbers are written using two Arabic characters: 0 and 1. The positional weights of this system are: ..., 256, 128, 64, 32, 16, 8, 4, 2, 1.
For example, entry 10101 is “decoded” as follows:
10101 2 = 1 16 + 0 8 + 1 4 + 0 2 + 1 1.
Note that the recursive rule for calculating weights implies that w i = q i–1 and, therefore, the notation (2) is equivalent to the traditional notation in the form of a power polynomial:
N= a n· q n–1 + a n-one · q n–2 + ... + a 2 · q + a 1 . (3)
Let's prove it by induction. base induction at i= 1 is checked directly: w 1 = q 0 = 1.
Induction hypothesis: let the statement be true for some n:
w n = q n–1 .
Let us prove that it will be valid for n + 1.
That is, we prove the validity of the equality:
wn+1 = q n.
Indeed, w n+1 = w n· q(according to the recursive determination of the position weight), and w n = q n–1 by the induction hypothesis. It turns out:
wn+1 = w n· q = q n-one · q = q n.
Let us prove that any number can be represented in the form (1) (Theorem 1) in a unique way (Theorem 2).
Theorem 1 (existence). Any number m can be represented in the form (1) for any q > 1.
Proof. Let's prove it by induction. For m = 0
and m= 1 it is easy to build the desired representation - these are 0 and 1, respectively (for any q> 1). Let's say we managed to represent the number m in the form (1). Let us then find a representation for m+ 1. To do this, it suffices to transform the sum
a n q n–1 + a n-one · q n–2 + ... + a 2 · q + a 1 + 1 to form (1).
If a a 1 < (q–1), then the desired representation is obtained by replacing the digit a 1 on a " 1 = a 1 + 1.
If a a 1 = (q–1), we get the transfer of the unit to the next position:
a n q n F–1+ a n-one · q n–2 + ... + (a 2 + 1) q + 0.
Next, we argue similarly. If a a 2 < (q–1), then the desired representation is obtained by replacing the digit a 2 on a " 2 = a 2 + 1. If a 2 = (q–1), then a We replace 2 with zero and move the unit to the next position.
Or on some i < n we will finish the construction, or we will get the record 1000...0 - one and n zeros on the right. The proof is complete.
Let us prove the lemma before Theorem 2.
Lemma. The contribution of each non-zero digit in record (1) exceeds the sum of the contributions of the digits located to the right of it.
a n a n–1 ... a 2 a 1 . (1)
Proof. Let us prove that for any n > 1:
a n q n–1 > a n-one · q n–2 + ... + a 2 · q+ a 1 .
Numbers a i lie in the interval , so it suffices to prove the inequality for the smallest non-zero digit on the left side and the maximum digits on the right:
q n–1 > ( q-one)· q n–2 + ... + (q-one)· q + (q–1).
On the right side we take out the multiplier ( q-1) outside the bracket:
(q-one)· q n–2 + ... + (q-one)· q + (q–1) =
= (q-one)·( q n–2 + ... + q + 1).
The sum of the geometric progression in the last bracket is calculated using the well-known formula:
(q-one)·( q n–2 + ... + q + 1) =
= (q-one)·( q n–1 –1)/(q–1) = q n–1 – 1.
We get an obvious inequality that proves the lemma:
q n–1 > q n–1 – 1.
Theorem 2 (uniqueness). A number in the form (1) is represented in a unique way.
Proof. It follows from the lemma that numbers that have a different number of digits in their notation (insignificant zeros on the left are not taken into account) cannot be equal: a number with a large number of digits is always greater. Therefore, we only need to prove that if a i not equal b i for all i from 1 to n, then the records
a n a n–1 ... a 2 a 1 (4)
b n b n–1 ... b 2 b 1 (5)
cannot represent the same number.
Let's look at entries (4) and (5) from left to right looking for mismatched digits. Let it be a k and b k let it go a k – b k = d.
On the k-th place in the record revealed a difference in d· q k-one . This difference should be compensated by the contributions of positions to the right. But this is impossible, since by the lemma the sum of the contributions of positions to the right is always less than the contribution of the current position. The theorem has been proven.
Convert to decimal
To convert numbers from a base system q to the decimal system, you can use formula (2) by performing multiplications and additions in it.
N= a n· w n + a n-one · w n–1 + ... + a 2 · w 2 + a one · w 1 (2)
When translating from the binary system, only addition is involved (because you can not multiply by 1). Thus, we obtain the translation rule formulated in the Reading Room:
To convert from binary to decimal, you need to write down the weight of its position over each binary digit and add the numbers written over the units.
So, for example, for the number 10111 we get:
10111 2 = 16 + 4 + 2 + 1 = 23 10
The general rule for transferring from q-ary system to decimal sounds like this:
To transfer from q-ary system into decimal, you need to write down the weight of its position above each digit and find the sum of the products of the digits by their positional weights (that is, find the sum of positional contributions).
So, for example, for the number 10212 3 we get:
We add the numbers multiplied by their positional weights (positions with zero digits, of course, can be omitted):
10212 3 = 1 81 + 2 9 + 1 3 + 2 1 = 104 10 .
Transfer to q-ic
To convert numbers from decimal to base q we will continue to rely on formula (2):
N= a n· w n + a n-one · w n–1 + ... + a 2 · w 2 + a one · w 1 . (2)
Translation algorithm.
I. Repeat until the number goes to zero:
1. Find the first position on the left, the weight of which is not greater than the current number. Write the maximum possible digit into the position, such that its positional contribution (the product of the digit by the weight) does not exceed the current number.
2. Decrease the current number by the contribution of the constructed position.
II. In positions not occupied by the constructed figures, write zeros.
In each position, the maximum possible digit is taken, since, according to the lemma, the contribution of this digit cannot be compensated by the digits located to the right. The algorithm will work due to the proven existence (Theorem 1) and uniqueness (Theorem 2) of the number representation in the form (1).
For a binary system, we obtain a variant of the algorithm given in the material for the student.
To convert to binary, you need to build a template with weights of binary digits:
Number translation is performed according to the following algorithm:
I. Repeat until the number goes to zero:
1. Write 1 to the first position on the left, the weight of which is not greater than the current number.
2. Decrease the current number by the weight of the built unit.
II. In positions not occupied by ones, write zeros.
This method of translation in practice turns out to be much simpler and faster than the traditional algorithm with finding residuals.
When converting from a decimal system to a ternary one, one has to take into account both the positional weights themselves and their doubling. For a quick translation, you can build a table, the lines of which correspond to the positions of the digits, the columns to the digits, and the cells to the contributions of the digit to the number, depending on its position in the number entry:
position 729 |
||
position 243 |
||
position 81 |
||
position 27 |
||
position 9 |
||
position 3 |
||
position 1 |
Let's say the contribution of the number 2 in position 243 is the number 486, and in position 9 is the number 18.
To convert to a ternary system, you need to look through the table row by row in search of the largest number that does not exceed the current value.
For example, let's convert the number 183 to the ternary system. A suitable value is located in the third row and first column:
position 729 |
||
position 243 |
||
position 81 |
||
position 27 |
||
position 9 |
||
position 3 |
||
position 1 |
So the ternary number begins with the number 2:
183 10 = 202?? 3
For the number 21–18 = 3, there is an exact value in the table, the translation is complete:
183 10 = 20210 3 .
For systems with a large base, the corresponding tables will, of course, be more voluminous. As a last example, let's build a table for converting to hexadecimal number system:
Let the number 4255 be converted to hexadecimal. We look in the table (from left to right in rows, starting from the top) for the first number that will not be greater than the original number 4255:
We get the first digit 1 at position 4096:
It remains to encode 4255 - 4096 = 159.
We skip line 256 (the corresponding figure will be 0), and in line 16 we find the appropriate value 144:
We get the numbers in positions 256 and 16:
It remains to encode 159 - 144 = 15. It is clear that this is the value of the lowest digit:
It turns out: 4255 10 \u003d 109F 16.
Actions on numbers
This section is presented in the material for the student schematically, in an introductory manner.
You can devote a separate, large and quite interesting lesson to the topic, but there is already a lot of material - it is difficult to grasp the immensity!
In a simple, introductory version, it is shown that operations on numbers in any number system are performed in exactly the same way as in the decimal system. It would be strange if it were otherwise, because the numbers in all positional systems are built according to the same rules, which means that actions on them should be performed in the same way.
The section is supported by homework assignments of option 3. These exercises can be recommended to inquisitive schoolchildren as individual assignments.
Notation is a way of writing numbers using a given set of special characters (numbers).
Writing a number in some number system is called number code.
A separate position in the image of a number is usually called discharge, and the position number is the digit number. The number of digits in the notation of a number is called the bit depth and coincides with its length.
There are positional and non-positional systems .
In non-positional systems reckoning the weight of the digit does not depend on the position, which she ranks among. So, for example, in the Roman number system in the number XXXII (thirty-two), the weight of the digit X in any position is simply ten.
An example of a non-positional number system is Roman. The numbers used in the Roman system are: I(1), V(5), X(10), L(50), C(100), D(500), M(1000).
The value of a number in the Roman numeral system is defined as the sum or difference of the digits in the number. If the smaller number is to the left of the larger one, then it is subtracted; if it is to the right, it is added.
Example:
CCXXXII=232
IX=9
In positional systems reckoning the weight of each digit changes depending on its position in the sequence of digits representing the number.
Any positional system is characterized by its foundation.
The base of a positional number system is the number of different characters or symbols used to represent digits in a given system.
Any natural number can be taken as a base - two, three, four, sixteen, etc. Therefore, an infinite number of positional systems are possible.
Examples of a positional number system are binary, decimal, octal, hexadecimal, etc.
D decimal number system.
AT this system has 10 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, but information is carried not only by the number, but also by the place on which the number stands (that is, its position). The rightmost digit of the number shows the number of units, the second from the right - the number of tens, the next - the number of hundreds, etc.
Example:
333
10
= 3*100 +
3*10+3*1 = 300 + 30 + 3
Binary number system.
There are only two digits in this system - 0 and 1. The base of the system is the number 2. The rightmost digit of the number shows the number of units, the next digit - the number of twos, the next - the number of fours, etc. The binary number system allows you to encode any natural number - to represent it as a sequence of zeros and ones.
Example:
1011
2
= 1*2^3 +
0*2*2+1*2^1+1*2^0 =1*8 + 1*2+1=11
10
Octal number system.
There are 8 digits in this number system: 0, 1, 2, 3, 4, 5, 6, 7. To convert, for example, the number 611 (octal), you need to replace each digit with its equivalent binary triad (three digits). It is easy to guess that to translate a multi-digit binary number into an octal system, you need to break it into triads from right to left and replace each triad with the corresponding octal digit.
Example:
6118 =011 001 001 2
1 110 011 101 2 = 1435 8 (4 triads)
Hexadecimal number system.
The notation of a number in the octal number system is quite compact, but it is even more compact in the hexadecimal system. As the first 10 of the 16 hexadecimal digits, the usual digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 are taken, but the first letters of the Latin alphabet are used as the remaining 6 digits: A, B, C, D, E, F. The conversion from hexadecimal to binary and vice versa is done in the same way as it is done for the octal system.
Converting integers to other number systems
An integer with base 10 is converted to the base 2 number system by successively dividing the number by base 2 until a remainder is obtained. The resulting remainder from the division and the last quotient are written in the reverse order obtained by division. The generated number will be a number with base N2.
Converting numbers to decimal system is carried out by compiling a power series with the base of the system from which the number is translated. Then the value of the sum is calculated.
a) Translate 10101101 s.s.
101011012 = 1*2^7+ 0*2^6+ 1*2^5+ 0*2^4+ 1*2^3+ 1*2^2+ 0*2^1+ 1*2^0 = 173
b) Translate 7038.
7038 = 7*8^2+ 0*8^1+ 3*8^0= 451
c) Translate B2E16.
B2E16 = 11*16^2+ 2*16^1+ 14*16^0= 2862
Notation is a method of writing a number using a specified set of special characters (numbers).
Notation:
- gives a representation of a set of numbers (integer and/or real);
- gives each number a unique representation (or at least a standard representation);
- displays the algebraic and arithmetic structure of a number.
Writing a number in some number system is called number code.
A single position in the display of a number is called discharge, so the position number is rank number.
The number of digits in a number is called bit depth and matches its length.
Number systems are divided into positional and non-positional. Positional number systems are divided
on the homogeneous and mixed.
octal number system, hexadecimal number system and other number systems.
Translation of number systems. Numbers can be converted from one number system to another.
Correspondence table of numbers in various number systems.
