Definition - what is combinatorics. Computer science
The amount of information as a measure of reducing the uncertainty of knowledge
Information and knowledge. A person receives information from the surrounding world with the help of the senses, analyzes it and identifies significant patterns with the help of thinking, stores the information received in memory. The process of systematic scientific knowledge of the surrounding world leads to the accumulation of information in the form of knowledge (facts, scientific theories, and so on). Thus, from the point of view of the process of cognition, information can be considered as knowledge.
The process of cognition can be visually depicted as an expanding circle of knowledge (this method was invented by the ancient Greeks). Outside this circle lies the area of ignorance, and the circle is the boundary between knowledge and ignorance. The paradox is that the more knowledge a person has (the wider the circle of knowledge), the more he feels the lack of knowledge (the greater the border of our ignorance, the measure of which in this model is the circumference) - fig. 1.1.
 |
| Rice. 1.1 Knowledge and ignorance |
So, the volume of knowledge of a school graduate is much greater than the volume of knowledge of a first-grader, however, the border of his ignorance is much greater. Indeed, a first-grader knows nothing about the laws of physics and therefore does not realize the insufficiency of his knowledge, while a school graduate in preparation for physics exams may discover that there are physical laws that he does not know or do not understand.
The information that a person receives can be considered a measure of reducing the uncertainty of knowledge. If a certain message leads to a decrease in the uncertainty of our knowledge, then we can say that such a message contains information.
For example, after passing an exam in computer science, you are tormented by uncertainty, you do not know what grade you received. Finally, the examination committee announces the results of the exam, and you receive a message that brings complete certainty, now you know your grade. There is a transition from ignorance to complete knowledge, which means that the message of the examination committee contains information.
Reducing the uncertainty of knowledge. The approach to information as a measure of reducing the uncertainty of knowledge allows you to quantify information, which is extremely important for computer science. Consider the issue of determining the amount of information in more detail on specific examples.
Suppose we have a coin that we throw at flat surface. With equal probability, one of two possible events will occur - the coin will be in one of two positions: heads or tails.
We can say that events are equally probable if, with an increasing number of experiments, the numbers of heads and tails are gradually approaching. For example, if we toss a coin 10 times, then heads can come up 7 times, and tails 3 times, if we toss a coin 100 times, then heads can come up 60 times, and tails can come up 40 times if we toss a coin 1000 times, then "eagle" can fall out 520 times, and "tails" - 480 and so on.
As a result, with a very large series of experiments, the number of heads and tails will almost equal.
There is an uncertainty in our knowledge before the toss (two events are possible), and it is impossible to predict how the coin will fall. After the toss, there is complete certainty, since we see (we receive a visual message) that the coin is in this moment is in a certain position (for example, "eagle"). This message leads to a halving of the uncertainty of our knowledge, since before the throw we had two probable events, and after the throw - only one, that is, two times less (Fig. 1.2).
 |
| Rice. 1.2 Possible and past events |
In the surrounding reality, situations are quite often encountered when a certain number of equally probable events can occur. So, when throwing an equilateral tetrahedral pyramid, there are 4 equally probable events, and when throwing a six-sided dice, there are 6 equally probable events.
The greater the number of possible events, the greater the initial uncertainty and, accordingly, the greater large quantity information will contain a message about the results of the experiment.
Units for measuring the amount of information. For the quantitative expression of any quantity, it is necessary to determine the unit of measurement. So, for measuring length, a meter is chosen as a unit, for measuring mass, a kilogram, and so on. Similarly, to determine the amount of information, you must enter a unit of measure.
Behind unit of information such amount of information is received that contains a message that reduces the uncertainty by half. This unit is called "bit".
If we return to the experiment with tossing a coin, then here the uncertainty is just halved and, therefore, the amount of information received is 1 bit.
The smallest unit for measuring the amount of information is a bit, and the next largest unit is a byte, with
1 byte = 2 3 bits = 8 bits
In computer science, the system of education of multiple units for measuring the amount of information is somewhat different from those accepted in most sciences. Traditional metric units, e.g. International system units of SI, as multipliers of multiple units, the coefficient 10n is used, where n \u003d 3, 6, 9 and so on, which corresponds to the decimal prefixes Kilo (10 3), Mega (10 6), Giga (10 9) and so on.
The computer operates with numbers not in decimal, but in binary, therefore, in multiple units of measuring the amount of information, the coefficient 2 n is used.
So, units of measurement of the amount of information that are multiples of a byte are entered as follows:
1 KB = 2 10 bytes = 1024 bytes;
1 MB = 2 10 KB = 1024 KB;
1 GB = 2 10 MB = 1024 MB.
The number of possible events and the amount of information. There is a formula that relates the number of possible events N and the amount of information I:
| N=2 I | (2.1) |
Using this formula, you can easily determine the number of possible events, if the amount of information is known. For example, if we received 4 bits of information, then the number of possible events was:
On the contrary, to determine the amount of information, if the number of events is known, it is necessary to solve the exponential equation for /. For example, in the game "Tic-Tac-Toe" on the field 8x8 before the first move, there are 64 possible events (64 different options for the location of the "X"), then the equation becomes:
Since 64 \u003d 2 6, we get:
Thus, I = 6 bits, that is, the amount of information received by the second player after the first move of the first player is 6 bits.
Questions for reflection
1. Give examples of reducing the uncertainty of knowledge after receiving information about the event.
2. What is the uncertainty of knowledge in the experience of tossing a coin?
3. How does the amount of information depend on the number of possible events?
Tasks
1.1. How much information will the second player get after the first player's first move in a game of tic-tac-toe on a 4x4 field?
1.2. What was the number of possible events if, after the implementation of one of them, we received an amount of information equal to 3 bits? 7 bits?
Information is information or data that does not contain uncertainty for the addressee. If, nevertheless, the information contains some uncertainty, then it can be perceived only with a certain probability. Therefore, in the presence of uncertainty, the recipient of information somehow seeks to minimize the uncertainty itself. If at the same time the recipient of information manages to eliminate the uncertainty completely, then he owns the information completely. How this can be done in practice is the subject of this chapter.
QUANTITATIVE MEASURE OF UNCERTAINTY
To compare uncertainties, consider the following examples or experiments a, b and g , containing uncertainties H(a), H(b) and H(g), respectively:
1. Determine the next world chess champion (experiment a).
2. Determine the number of the lottery ticket, which will receive the largest winnings in the upcoming lottery draw (experiment b).
3. Determine the next president of the Russian Federation (experiment g).
Obviously, the degree of uncertainty of each experiment differs from the other two, and most likely there are inequalities
H(b) > H(a) > H(g),
where H(a), H(b) and H(g) are quantitative measures of uncertainties (or entropies) of experiments a, b and g, respectively. In a special case, if for some experience d the equality H(d) = 0 takes place, then we say that experience d is reliable, i.e. it does not contain uncertainty. In other words, the uncertainty of experience is nothing more than a lack of information or negative information.
I. Hartley formula. Let a be an arbitrary experiment with k equiprobable outcomes A k
Events A 1 A 2 . . . A k
Probabilities 1/ k 1/ k . . . 1/ k .
For k= 1 H(a) = 0, and as k increases, H(a) also increases, i.e.
where f is some function of k. On the other hand, if b is another experiment independent of a with l equiprobable outcomes B l , then for a complex experiment ab, which consists in the simultaneous execution of experiments a and b, it is natural to assume that the degree of uncertainty of experiment ab is equal to the sum of the uncertainties characterizing experiments a and b, those.
H(ab) = H(a) + H(b).
Thus, as a function f, we can choose a logarithmic function and assume that
H(a) = log 2 k .
This is Hartley's formula and it is a measure of uncertainty about experience a contained in experience a and having two equally likely outcomes (eg "yes" or "no"). In other words, H(a) is the amount of information (a bit is considered as the unit of measurement of the amount of information), with the help of which the uncertainty of experience a turns into reliability.
So, for example, to guess the intended number in the range from 1 to 8, you need a maximum of 3 bits of information, i.e. three questions need to be asked.
II. Shannon formula. Let a be an arbitrary experience with k unequal outcomes A k:
Events A 1 A 2 . . . A k
Probabilities P(A 1) P(A 2) . . . P(A k) .
H(a) = - å P(A i)log 2 P(A i)
There is a measure of the uncertainty of experience a according to Shannon. In particular, when Р(А i) = 1/ k , Hartley's formula follows from Shannon's formula.
3.1.1. Prove that H(ab) = H(a) + H(b).
3.1.2. How many questions you need to ask the students of the academic group to the teacher in order to determine the headman of this group (answers to the teacher's questions can be either "yes" or "no").
3.1.3. Consider the problem 3.1.2. in case of one question.
3.1.4. Let x be an element of the set M of cardinality m. How many
information needed to determine the element x?
3.1.5. Let x 1 and x 2 be two arbitrary elements of the sets M 1 and M 2 of cardinality m 1 and m 2, respectively. How much information is needed to simultaneously determine the elements x 1 and x 2?
3.1.6. Let there be 27 gold coins, of which one is fake (lighter than real ones), and scales with cups. How many weighings must be made to determine the counterfeit coin?
3.1.7. Prove that any experiment a H(a) ³ 0, and H(a) = 0 if and only if one of the probabilities is equal to 1 and the rest are equal to 0.
3.1.8. Prove that H(a) ≤ log 2 k , where k is the number of outcomes of experiment a , and equality is achieved only if the outcomes are equally probable.
3.1.9. What properties does H(a) have if a has two outcomes?
CONDITIONAL UNCERTAINTY.
Amount of information
Let a and b be two arbitrary experiments with k and l outcomes A k , B l respectively. Then if a and b are independent, then
H(ab) = H(a) + H(b) ,
and if a and b are dependent, then
H(ab) = H(a) + H a (b) ,
where H a (b) is the conditional uncertainty of experiment b under the condition that experiment a is performed and is determined by the equality k
H a (b) = å P(A i)H A i (b) .
Here H A i (b) is the conditional uncertainty of experience b under the condition of the outcome A i and is determined by the formula: l
H A i (b) = - å P A i (B j) log 2 P A i (B j) , i = 1 , k .
Obviously, if a and b are independent, then H a (b) = H(b) , and H a (b) ≤ H(b) if a and b are dependent.
There is also the equality
Consider the difference
I (a , b) \u003d H (b) - H a (b) ,
which indicates how much the outcome of experience a reduces the uncertainty of experience b. The number I (a , b) is called the amount of information about experience b contained in experience a.
In particular, for a =b we have I (a , a) = 0, which can be interpreted as the amount of information about experience a contained in itself. If a and b are independent, then
those. generally
I (a, b) ≥ 0,
which can be interpreted something like this: there will be no harm from everything that is taught at the university, and in the worst case, there will simply be no benefit.
I (a , b) = I (b, a) ,
then I (a , b) can also be called mutual information of two experiments a and b
H(ab) = H(a) + H a (b) ,
I (a , b) = H(a) + H(b) - H(ab) ,
therefore kl
I (a , b) = Σ Σ P(A i B j) log 2 P(A i B j) /(P(A i) P(B j)) .
Thus, we have obtained the final formula for the amount of information I (a, b).
3.2.1. Prove that if a and b are arbitrary experiments, then;
A) H(ab) = H(a) + H a (b) ;
b) H(ab) ≤ H(a) + H(b) ;
V) 0 ≤ H a (b) ≤ H(b) ;
G) I (a , b) = I (b, a) ;
e) I (a , b) ≤ H(a) ;
3.2.2. Derive a formula for I (a , b) .
3.2.3. Let experience b consist in extracting one ball from an urn containing m black and n white balls, experience a k - in preliminary extraction from the same urn (without returning back) k balls. What is the uncertainty of the experiment b and the information about the experience contained in the experiments a 6,
3.2.4. Let m parts be withdrawn from batches of n parts manufactured on the conveyor for selective control. Denote by a the percentage of defects in the entire batch, and by b the percentage of defects in the sample. Define I (a , b).
3.2.5. (About the cities of liars and honest people). Let it be known that the inhabitants of some city A always tell the truth, and the inhabitants of a neighboring city B always lie. Observer H knows that he is in one of these two cities, but does not know which one. By questioning the person he meets, he needs to determine in which city he is located, or in which city his interlocutor lives (residents of A can go to B and back), or both. Asking what is smallest number questions to be asked by N (on all questions of N, the counter answers only "yes" or "no").
TRANSFER OF INFORMATION
Let us once again return to the general scheme of information transfer, considering real messages as some experiments with the corresponding tables of probability distribution in them of individual letters or combinations of letters.
In particular, if x and x" are the transmitted and distorted messages, respectively, then we define the amount of information I(x", x) - the output of the channel relative to its input as:
I (x ", x) \u003d H (x) - H x "(x),
where H(x), H(x") are the message entropies x and x" respectively.
Meaning
C = max I(x", x)
is called the channel capacity, i.e. it characterizes the maximum amount of information that can be transmitted through the channel in one clock cycle. In fact, the channel capacity is the upper limit of the rate R of reliable information transfer, and this limit can be approached arbitrarily close.
Theorem 1.(about coding). For any number R less than the bandwidth C of the channel, and any e>0, there is a block transmission method with a rate not less than R and an error probability P(e) not exceeding e.
At the same time, any method of transmitting information at a rate greater than the bandwidth leads to the fact that the error probability will be greater than some fixed value.
Theorem 2.(conversion of the coding theorem). If the value of R exceeds the capacity of the channel C, then there is a constant e 0 (depending on R and C) such that for any method of block transmission of information at a rate not less than R, the inequality
Р(е)³ e 0 .
Denote by I(a i) the amount of information contained in the symbol a i and define it as:
I(a i) = - log 2 P(a i) ,
where P(a i) is the probability of occurrence of the character a i in the message text itself.
If the message text is written in some natural language
(and it can be considered as a natural code that detects and corrects errors), then each letter of this language has its own frequency of occurrence in the text (for example, in Russian, the letters o, e, e are much more common (P o \u003d 0.09, P e,ё = 0.07) than the letters e and f (P e = 0.003, P f = 0.002)) and therefore the uncertainty H L natural language defined as m
H L = - å P(a i) log 2 P(a i) ,
and redundancy ~ L, respectively, as
C L \u003d 1 - H L / log 2 m,
where m is the number of natural language letters.
Obviously, 0 ≤ С L ≤ 1, therefore, with optimal coding, part of the text can be omitted without compromising understanding.
So, for example, С L = 0.5 for the literary in English, and the redundancy of other languages is somewhat less.
Note that the redundancy of the language is not a disadvantage, but rather an advantage, since, for example, if С L = 50%, then this means that half of the distorted text can be used to restore the entire text.
3.3.1. Determine the bandwidth of the DSC.
3.3.2. Find I(x" , x) for DSC.
3.3.3. Determine the redundancy and uncertainty of the Russian language.
3.3.4. Determine the amount of information of the letters of the English language.
3.3.5. Prove Shannon's theorems for block codes.
3.3.6. Restore text:
A) S??zd q?li??m? p?ln???yu od??ri? m??opr??t?i c? steam??? ?o??rb? ? ?a?o?om;
b)?about?ka?ae? ka?av?n???ay.
Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
1. Alphabet of Discrete Devices. End fields. . . . . . . . . . 4
1.1. Simple Galois field GF(P) . . . . . . . . . . . . . . . . . . . . . 4
1.2. Composite Galois field GF(P n) . . . . . . . . . . . . . . . . . . . 6
2. Information encoding. . . . . . . . . . . . . . . . . . . . . . .9
2.1. Basic concepts. Code examples. . . . . . . . . . . . . . . 9
2.2. Line codes. Ways to set them. . . . . . . . . . . . 15
2.3. Linear code properties. Hamming codes. . . . . . . . . . 22
2.4. Cyclic codes. . . . . . . . . . . . . . . . . . . . . . . . 27
2.5. BCH codes correcting two errors. . . . . . . . . . . . .32
2.6. Nonlinear codes. Hadamard codes. . . . . . . . . . . . . . . .36
2.7. Code Power Bounds. . . . . . . . . . . . . . . . . . . . 40
3. Information and uncertainty. . . . . . . . . . . . . . . . . . 44
3.1. A quantitative measure of uncertainty. . . . . . . . . . . .45
3.2. Conditional uncertainty. The amount of information. . . . .47
3.3. Transfer of information. . . . . . . . . . . . . . . . . . . . . .50
Osipyan Valery Osipovich
ELEMENTS OF THE THEORY OF INFORMATION TRANSMISSION
Editor T.V. Shilova
Technical editor I.A. Zinovskaya
Proofreader M.E. Shulepova
LR No. 200378 of 01/22/97
Signed for publication on January 29, 1997.
Format 60´84 1/16. Paper type. No. 3.
Screen printing. Conv. oven l. 2.75.
Uch.-ed. l. 2.7. Circulation 300 copies. Order No.
Kuban State University
Randomness and uncertainty
Combinatorics is a branch of mathematics that studies combinations, permutations, placements, and enumerations of elements of a set.
What is uncertainty?
Uncertainty is the lack or absence of information about something.
Randomness is a category for the connections between such phenomena real world which can be realized under some conditions and not under others. The randomness of an event lies in the fact that the implementation of a particular outcome has a certain degree of uncertainty.
Randomness is manifested in almost all areas of human activity.
An event is a phenomenon that occurs as a result of actions. Events are usually denoted by large with Latin letters: A, B, C, etc.
A random event is an event that may or may not occur.
The sum of events Ai B is the event C, which consists in the appearance of event A or event B or both events at once:
The product of events A and B is an event C, which consists in the joint appearance of events A and B (their combination):
The probability of an event is a measure of the objective possibility of an event occurring.
Event A is said to be independent of event B if the probability of event A does not depend on whether event B occurs or not. Otherwise, event A is said to be dependent on event B.
Incompatible events are those that cannot occur simultaneously: the occurrence of one excludes the occurrence of the other.
Pseudo-random numbers are numbers that are used in programming to mimic random numbers.
A pseudo-random number generator is an algorithm that generates a sequence of numbers whose elements are almost independent of each other and obey a certain distribution.
A pseudo-random sequence generator is an algorithm for constructing a sequence of pseudo-random numbers due to some external source of random values (for example, noise). Knowing i-th number in a sequence, formulas can be used to determine its (r + 1)th element.
Algorithms for generating pseudo-random sequences are periodic.
Examples. 1. Determine the probability of the appearance of a face of a dice with the number 6.
In this case, the number of common outcomes is 6, since the dice has 6 faces. However, there is only one favorable outcome, since the die has only one face with the number 6, therefore
Example 2. Generate a random list of numbers from 1 to N.
1- th way
If the element's position contains "0", you can place the element.
If the position is not "0", then a random number is generated for the element.
2- th way
We assign zero values to the elements of the list.
We place the element in the sequence.
If the position is not "0", then we check all subsequent ones until we find "0".
3- th way
We assign zero values to the elements of the list.
We place the element in the sequence.
If the element position contains "0", you can place the element.
The uncertainty of knowledge about some event is the number of possible outcomes of the event
Let's go back to the coin example. After you tossed the coin and looked at it, you received a visual message that it came up heads, for example. One of two possible events has occurred. The uncertainty of knowledge has halved: there were two options, only one remained. So, having learned the result of tossing a coin, you received 1 bit of information.
The message that one event out of two equally probable has occurred carries one bit of information.
Let some message contain information that one of N equally probable (equally possible) events has occurred. Then the amount of information i contained in this message and the number of events N are related by the formula:
2 i =N.
If N is an integer power of two (2, 4, 8, 16, etc.), then the calculation is easy to do "in the mind." Otherwise, the amount of information becomes a non-integer value, and to solve the problem, you will have to use the table of logarithms or determine the value of the logarithm approximately (nearest integer, greater).
For example, if out of 256 identical, but different-colored balls, one was randomly chosen, then the message that a red ball was chosen carries 8 bits of information (2 8 = 256).
To guess a number (for sure) in the range from 0 to 100, if it is allowed to ask only binary questions (with the answer "yes" or "no"), you need to ask 7 questions, since the amount of information about the hidden number is more than 6 and less than 7 (2 6 2 7)
The amount of information i contained in the message that one of N equiprobable events has occurred is determined from the solution of the exponential equation: 2 i =N
Alphabetical approach to information measurement
The alphabetical approach is based on the fact that any message can be encoded using a finite sequence of symbols of some alphabet.
Alphabet- an ordered set of characters used to encode messages in some language.
The power of the alphabet- the number of characters of the alphabet.
The binary alphabet contains 2 characters, its power is two.
Messages written with ASCII characters use an alphabet of 256 characters. UNICODE messages use an alphabet of 65,536 characters.
To determine the amount of information in a message with an alphabetical approach, you need to sequentially solve the following problems:
Determine the amount of information (i) in one character using the formula 2 i = N, where N is the power of the alphabet
Determine the number of characters in the message (m)
Calculate the amount of information using the formula: I = i * K.
The amount of information in the entire text (I), consisting of K characters, is equal to the product of the information weight of the character by TO:
I = i * TO.
This value is the information volume of the text.
For example, if an ASCII-encoded text message contains 100 characters, then its information volume is 800 bits.
I = 8 * 100 = 800
For a binary message of the same length, the information volume is 100 bits.
It is also necessary to know the units of measurement of information and the relationship between them.
Information units
As already said, basic unit measurement information - bit.
8 bits are 1 byte.
Along with bytes, larger units are used to measure the amount of information:
1 KB (one kilobyte) = 1024 bytes;
1 MB (one megabyte) = 1024 KB;
1 GB (one gigabyte) = 1024 MB.
IN Lately In connection with the increase in the volume of processed information, such derived units as:
1 Terabyte (TB) = 1024 GB,
1 Petabyte (Pb) = 1024 TB.
Ticket number 3
1. Discrete representation of information: binary numbers; binary encoding of text in computer memory. Information volume of the text.
2. Creation and processing of graphic images by means of a graphic editor.
1. Discrete representation of information: binary numbers; binary encoding of text in computer memory. Information volume of the text.
A person perceives information through the senses. At the same time, he seeks to fix it and present it in a form accessible to others. The form of presentation of information may be different. One and the same object, such as a house, can be depicted graphically in the form of a drawing or a drawing can be made in three projections. It can be described in verse or with the help of mathematical formulas.
The form of presentation of information depends on the purpose for which it serves. For example. Writing a solution to a quadratic equation in an algorithmic or programming language is fundamentally different from the form of writing used in algebra lessons.
Consider representations of numbers.
Numbers are written using special sign systems called number systems. All number systems are divided into positional and non-positional.
Notation is the way to write numbers with special characters numbers.
Numbers:
123, 45678, 1010011, CXL
Numbers:
0, 1, 2, … I, V, X, L, …
Alphabet is a set numbers. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Types of number systems:
non-positional- the value of a digit does not depend on its place (positions) in the notation of a number;
positional- depends on location (positions) in number entry.
Non-positional systems
Unary- one digit stands for one (1 day, 1 stone, 1 ram, ...)
Roman:
I- 1 (finger), V- 5 (open palm, 5 fingers), X- 10 (two palms), L –
50, C – 100 (Centum),
D – 500 (Demimille),
M – 1000 (Mille)
Positional system: the value of a digit is determined by its position in the notation of the number.
Decimal system:
originally - counting on the fingers invented in India, borrowed by the Arabs, brought to Europe
Alphabet: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Base(number of digits): 10
ranks
3 7 8 = 3 102 + 7 101 + 8 100
300 70 8
Other positional systems:
binary, octal, hexadecimal (computer science)
duodecimal (1 foot = 12 inches, 1 shilling = 12 pence)
vigesimal (1 franc = 20 sous)
sexagesimal (1 minute = 60 seconds, 1 hour = 60 minutes)
Number systems in computers
In the 17th century, the German scientist Gottfried Leibniz proposed a unique system for representing numbers using only two symbols - 0 and 1. Today, this method is widely used in technology, including computers, and is called discrete.
The computer is capable of storing only discrete information. His memory, no matter how large it may be, consists of individual bits, which means that it is inherently discrete.
Computer language is the language of binary numbers - binary an alphabet that has two signs, 1 and 0. In logic and technology, these signs are associated with the concepts - yes and no, true and false, on and off. This alphabet is also called binary. In accordance with this, the smallest unit of information is also introduced - bit (English bit, from binary - binary and digit - sign). One bit of information is enough to convey the word "yes" or "no", to encode, for example, the state of a light bulb. By the way, on some switches they write "1 - on" and "0 - off". A look at the switch takes off for us uncertainty in his condition. In this case, we get the amount of information equal to one bit.
BIT - the smallest unit of information, corresponding to one digit of the machine binary code.
Binary encoding (binary notation) has a number of advantages over other coding systems:
To implement it, technically uncomplicated elements with two possible states are needed (there is a current - there is no current, magnetized - not magnetized, etc.).
Representation of information by means of only two states is reliable and noise-resistant.
It is possible to use a special logic algebra (Boolean algebra) to perform logical transformations of information.
Binary arithmetic is much simpler than decimal arithmetic. Binary addition and multiplication tables are extremely simple.
Information processing in a computer is based on the exchange of electrical signals between various devices of the machine. The sign of the presence of a signal can be denoted by the number 1, the sign of the absence - by the number 0.
BINARY TEXT CODING
256 different characters are used to represent text in a computer. To encode 1 character, 8 bits are allocated.
Coding- assigning to each character a decimal code from 0 to 255 or the corresponding binary code from 00000000 to 11111111
Assigning a specific code to a symbol is a matter of agreement, which is fixed in the code table.
As international standard code has been adopted ASCII table(American Standard Code for Information Interchange) :
Codes 0 to 32 (first 33 codes) - operation codes (line feed, space entry, i.e. correspond to function keys);
Codes 33 to 127 – international, match characters Latin alphabet, numbers, signs of arithmetic operations, punctuation marks;
Codes 128 to 255 – national, i.e. national alphabet code.
on 1 character assigned 1 byte(8 bits), a total of 2 8 = 256 characters can be encoded
Since 1997, a new international standard has appeared Unicode, which takes one character to encode 2 bytes(16 bits), and 65536 different characters can be encoded (Unicode includes all existing, extinct and artificially created alphabets of the world, many mathematical, musical, chemical and other characters)
There are currently five Cyrillic encodings: KOI-8, CP1251, CP866, ISO, Mac. To convert text documents from one encoding to another, there are programs called Converters.
I = i * K
Ticket number 4
1. Discrete representation of information: encoding a color image in a computer (raster approach). Representation and processing of sound and video images. The concept of multimedia.
2. Working with the file system, with a graphical interface (performing standard operations with files: creating, copying, renaming, deleting). Organization of an individual information space (setting up desktop elements, checking for viruses, using an archiver).
1. Discrete representation of information: encoding a color image in a computer (raster approach). Representation and processing of sound and video images. The concept of multimedia.
Information, including graphics and sound, can be presented in analog or discrete form. Information is stored in a computer in discrete form. Graphic and audio information from analog to discrete form is converted by sampling, i.e. splitting a continuous graphic image and a continuous audio signal into separate elements.
Graphic information encoding
Spatial Discretization- transfer of a graphic image from an analog form to a digital computer format by breaking the image into separate small fragments (dots) where each element is assigned a color code.
Pixel – min area of the image on the screen, given color
Bitmap is formed from separate dots - pixels, each of which can have its own color. Binary image code displayed on the screen is stored in video memory. Raster graphics pattern encoding resembles - a mosaic of squares that have a certain color.
The quality of image encoding depends on:
1) dot size (the smaller its size, the greater the number of dots in the image);
2) the number of colors (the greater the number of possible states of the point, the better the image) Color palette - the set of colors used.
The quality of a bitmap depends on:
1) monitor resolution - the number of dots vertically and horizontally.
2) used color palette (16, 256, 65536 colors)
3) color depth - the number of bits for encoding the color of a point
for storage black and white images used 1 bit
Color images generated according to the binary color code stored in the video memory. Color images have different color depths. The color image on the screen is formed by mixing three basic colors - red, green and blue. Base colors can be given different intensities to achieve a rich palette.
BINARY AUDIO CODING
In analog form, sound is a wave with continuously changing amplitude and frequency. Work with sound files on a computer began in the early 90s. At the heart of sound coding using a PC is the process of converting air vibrations into electric current vibrations and subsequent sampling of an analog electrical signal. Encoding and playback of sound information is carried out using special programs (sound recording editor). The quality of playback of encoded audio depends on - the sampling rate and its resolution (audio encoding depth - number of levels)
Temporal Discretization- a method of converting sound into digital form by breaking the sound wave into separate small time sections where the amplitudes of these sections are quantized (they are assigned a certain value).
This is done using an analog-to-digital converter located on the sound card. Thus, the continuous dependence of the signal amplitude on time is replaced by a discrete sequence of loudness levels. Modern 16-bit sound cards encode 65536 different volume levels or 16-bit sound depth (each sound amplitude value is assigned a 16-bit code)
The quality of audio encoding depends on:
1) sound encoding depth - the number of sound levels
2) sampling rates - the number of signal level changes per unit
time (usually 1 second).
Founder of information theory Claude Shannon defined information, How removed uncertainty. More precisely, obtaining information is a necessary condition for removing uncertainty. Uncertainty arises in a situation of choice. The task that is solved in the course of removing uncertainty is to reduce the number of options considered (diversity reduction), and as a result, the choice of one option corresponding to the situation from among the possible ones. Uncertainty removal provides an opportunity to make informed decisions and act. This is the controlling role of information.
Imagine that you walked into a store and asked to be sold chewing gum. A saleswoman who has, say, 16 brands of chewing gum is in a state of uncertainty. She cannot fulfill your request without more information. If you specified, say, “Orbit”, and out of 16 initial options, the saleswoman now considers only 8, you have reduced her uncertainty by half (looking ahead, let's say that halving the uncertainty corresponds to obtaining 1 bit of information). If you, without further ado, just pointed your finger at the window, - “this one!”, then the uncertainty was completely removed. Again, looking ahead, let's say that with this gesture in this example you told the saleswoman 4 bits of information.
Situation maximum uncertainty suggests that there are several equiprobable alternatives (options), i.e. none of the options is preferred. Moreover, the more equally likely options observed, the greater the uncertainty, the more difficult it is to make an unambiguous choice and the more information required to get it. For N options, this situation is described by the following probability distribution: (1/N , 1/N , ... 1/N ).
The minimum uncertainty is 0, i.e. this situation complete certainty, meaning that the choice is made, and all necessary information received. The probability distribution for a situation of complete certainty looks like this: {1, 0, …0} .
The quantity characterizing the amount of uncertainty in information theory is denoted by the symbol H and has the name entropy, more precisely information entropy.
Entropy (H) – measure of uncertainty expressed in bits. Entropy can also be viewed as a measure of the uniformity of distribution random variable.
Figure 8. shows the behavior of entropy for the case of two alternatives, with a change in the ratio of their probabilities (p , (1-p )).
The entropy reaches its maximum value in this case when both probabilities are equal to each other and equal to ½, the zero entropy value corresponds to the cases (p 0 =0, p 1 =1) and (p 0 =1, p 1 =0).
Amount of information I And entropy H characterize the same situation, but from qualitatively opposite sides. I is the amount of information required to remove the uncertainty H. According to Léon Brillouin information is negative entropy (negentropy).
When the uncertainty is removed completely, the amount of information obtained I equal to the inherent uncertainty H.
With partial removal of uncertainty, the amount of information received and the remaining unresolved uncertainty add up to the initial uncertainty. H t + I t = H.
For this reason, the formulas that will be presented below to calculate the entropy H are also formulas for calculating the amount of information I, i.e. when it comes to complete removal of uncertainty, H they can be replaced by I.
