Catalog of tasks. Transfer of information. Code selection

Version for printing and copying in MS Word

To transmit a message over a communication channel consisting only of the letters A, B, C, D, they decided to use a code of uneven length: A=1, B=01, B=001. How should the letter G be encoded so that the code length is minimal and the encoded message can be unambiguously divided into letters?

Answer:

To transmit a message over a communication channel consisting only of the letters A, B, C, D, they decided to use a code of uneven length: A=0, B=100, C=101. How should the letter G be encoded so that the code length is minimal and the encoded message can be unambiguously divided into letters?

Answer:

To encode a certain sequence consisting of the letters A, B, C, D and D, a non-uniform binary code is used, which makes it possible to unambiguously decode the resulting binary sequence. Here is the code: A-10, B-001, B-0001, G-110, D-111.

Is it possible to shorten the length of the codeword for one of the letters so that the code can still be decoded unambiguously? The codes of the remaining letters should not change. Select correct option answer.

1) this is impossible

2) for the letter B – 000

3) for the letter B – 0

4) for the letter G – 11

Answer:

To encode a certain sequence consisting of the letters A, B, C, D and D, a non-uniform binary code is used, which makes it possible to unambiguously decode the resulting binary sequence. Here is the code: A-011, B-000, B-11, G-001, D-10. Is it possible to shorten the length of the codeword for one of the letters so that the code can still be decoded unambiguously? The codes of the remaining letters should not change. Choose the correct answer.

1) this is impossible

2) for the letter A – 01

3) for the letter B – 00

4) for the letter G – 00

Answer:

To encode a certain sequence consisting of the letters A, B, C, D and D, a non-uniform binary code is used, which makes it possible to unambiguously decode the resulting binary sequence. Here is the code: A – 00, B – 01, C – 100, D – 101, D – 110. Is it possible to shorten the length of the code word for one of the letters so that the code can still be decoded unambiguously? The codes of the remaining letters should not change. Choose the correct answer.

1) for the letter D – 11

2) this is impossible

3) for the letter G – 10

4) for the letter D – 10

Answer:

To encode a certain sequence consisting of the letters A, B, C, D and D, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. For the letters A, B, C and D, the following code words were used: A-111, B-110, B-100, G-101.

Indicate what code word can be used to encode the letter D. The code must satisfy the property of unambiguous decoding. If more than one codeword can be used, enter the shortest one.

Answer:

To encode a certain sequence consisting of the letters A, B, C, D and D, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. For the letters A, B, C and D, the following code words were used: A - 100, B - 101, C - 111, D - 110.

Indicate which code word from those listed below can be used to encode the letter D. The code must satisfy the property of unambiguous decoding. If more than one codeword can be used, enter the shortest one.

Answer:

To encode a certain sequence consisting of the letters A, B, C, D and D, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. For the letters A, B, C and D, the following code words were used: A - 001, B - 010, C - 000, D - 011.

Indicate which code word from those listed below can be used to encode the letter D.

The code must satisfy the property of unambiguous decoding. If more than one codeword can be used, enter the shortest one.

Answer:

To encode a certain sequence consisting of the letters A, B, C, D and D, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. For the letters A, B, C and D, the following code words were used: A - 111, B - 110, C - 101, D - 100.

Indicate which code word from those listed below can be used to encode the letter D. The code must satisfy the property of unambiguous decoding. If more than one code word can be used, enter the shortest one.

Answer:

Messages containing only 4 letters are transmitted over the communication channel: E, H, O, T. To encode the letters E, H, O, 5-bit code words are used: E - 00000, H - 00111, O - 11011.

.

4) none of the above words are suitable

Answer:

Messages containing only 4 letters are transmitted over the communication channel: P, O, P, T. To encode the letters P, O, P, 5-bit code words are used: P - 11111, O - 11000, P - 00100.

This set of codewords has the following property: any two words from the set differ in at least three positions.

This property is important for decrypting messages in the presence of interference. Which of the following codewords can be used for the letter T such that the specified property holds for all four codewords?

4) none of the specified words are suitable

Answer:

Messages containing only 4 letters are transmitted through the communication channel: E, N, O, T.

In any message, the most letters are O, the next most common letter is E, then N. The letter T is less common than any other.

To transmit messages, you need to use a non-uniform binary code that allows unambiguous decoding; messages should be as short as possible. The cryptographer can use one of the codes listed below. Which code should he choose?

1) E−0, N−1, O−00, T−11

2) O−1, N−0, E−01, T−10

3) E−1, N−01, O−001, T−000

4) O−0, N−11, E−101, T−100

Answer:

Messages containing only 4 letters are transmitted through the communication channel: A, I, C, T.

In any message, the most letters are A, the next most common letter is C, then I. The letter T is less common than any other.

To transmit messages, you need to use a non-uniform binary code that allows unambiguous decoding; messages should be as short as possible. The cryptographer can use one of the codes listed below. Which code should he choose?

1) A−0, I−1, S−00, T−11

2) S−1, I−0, A−01, T−10

3) A−1, I−01, S−001, T−000

4) S−0, I−11, A−101, T−100

Answer:

Messages containing only 4 letters are transmitted over the communication channel: I, G, L, A. To encode the letters I, G, L, 6-bit code words are used:

I - 000000, G - 001110, L - 110110.

This set of code words has the following property: any two words from the set differ in at least three positions. This property is important for decrypting messages in the presence of interference. It is necessary to select a code word for the letter A so that the specified property is satisfied for all four code words.

Is it possible to use one of these words: 111110, 111000, 000110?

Answer:

Messages containing only 4 letters are transmitted over the communication channel: P, A, P, K. To encode the letters P, A, P, 6-bit code words are used:

P - 111111, A - 110001, P - 001001.

This set of code words has the following property: any two words from the set differ in at least three positions. This property is important for decrypting messages in the presence of interference. It is necessary to select a code word for the letter K so that the specified property is satisfied for all four code words.

Is it possible to use one of these words: 000001, 111001, 000111?

4) no, none of the above words are suitable

Answer:

Messages containing only 4 letters are transmitted through the communication channel: S, L, O, N; For transmission, a binary code is used that allows unambiguous decoding. For the letters S, O, N, the following code words are used: S: 011, O: 00, N: 11. Specify a code word for the letter L such that the code will allow unambiguous decoding. If there are several such codes, indicate the one with the shorter length.

Answer:

Messages containing only 4 letters are transmitted through the communication channel: A, T, O, M; For transmission, a binary code is used that allows unambiguous decoding. For the letters T, O, M, the following code words are used: T: 100, O: 00, M: 11. Specify a code word for the letter A such that the code will allow unambiguous decoding. If there are several such codes, indicate the one with the shorter length.

Answer:

Messages containing only 4 letters K, O, P, A are transmitted over the communication channel; For transmission, a binary code is used that allows unambiguous decoding. For the letters P, A, K, the following code words are used:

R: 000, A: 10, K: 01.

Specify a code word for the letter O such that the code will allow unambiguous decoding. If there are several such code words, indicate the one with the shorter length.

Answer:

Messages containing only 4 letters P, O, S, T are transmitted through the communication channel; For transmission, a binary code is used that allows unambiguous decoding. For the letters T, O, P, the following code words are used:

T: 111, O: 10, P: 01.

Specify a code word for the letter C such that the code will allow unambiguous decoding. If there are several such code words, indicate the one with the shorter length.

Answer:

To encode a certain sequence consisting of the letters U, CH, E, N, I and K, an uneven binary prefix code is used. Here is the code: U - 000, Ch - 001, E - 010, N - 100, I - 011, K - 11. Is it possible to shorten the length of the code word for one of the letters so that the code still remains a prefix? The codes of the remaining letters should not change.

1) the code word for the letter E can be shortened to 01

2) the code word for the letter K can be reduced to 1

3) the code word for the letter N can be reduced to 10

4) this is impossible

Answer:

To encode a certain sequence consisting of the letters U, CH, E, N, I and K, an uneven binary prefix code is used. Here is the code: U - 000, Ch - 001, E - 010, N - 100, I - 101, K - 11. Is it possible to shorten the length of the code word for one of the letters so that the code still remains a prefix? The codes of the remaining letters should not change.

Choose the correct answer.

Note. A prefix code is a code in which no code word is the beginning of another; Such codes make it possible to unambiguously decode the resulting binary sequence.

1) the code word for the letter E can be shortened to 01

2) the code word for the letter K can be reduced to 1

3) the code word for the letter N can be reduced to 10

4) this is impossible

Answer:

To transmit a message over a communication channel consisting only of characters A, B, C and D, an uneven (in length) code is used: A – 0; B – 100; Q – 101. What code word should be used to encode the symbol G so that its length is minimal, and the code allows for an unambiguous division of the encoded message into symbols?

Answer:

To encode a certain sequence consisting of the letters A, B, C, D, D and E, an uneven binary prefix code is used.

Code words are given for four letters: A - 011, B - 010, C - 001, D - 000. Which code words from the options below are suitable for the letters D and E? If more than one option is suitable, indicate the one for which the sum of the codeword lengths is less.

Note. A prefix code is a code in which no code word is the beginning of another; Such codes make it possible to unambiguously decode the resulting binary sequence.

1) D - 100, E - 110

2) D - 100, E - 11

3) D - 10, E - 11

4) D - 10, E - 1

Answer:

To encode a certain sequence consisting of the letters A, B, C, D, D and E, an uneven binary prefix code is used.

Code words are given for four letters: A - 111, B - 110, C - 101, D - 100. Which code words from the options below are suitable for the letters D and E? If more than one option is suitable, indicate the one in which the sum of the codeword lengths is less.

Note. A prefix code is a code in which no code word is the beginning of another; Such codes make it possible to unambiguously decode the resulting binary sequence.

1) D - 001, E - 011

2) D - 001, E - 01

3) D - 00, E - 01

4) D - 0, E - 01

Answer:

To transmit a message over a communication channel consisting only of characters A, B, C and D, an uneven (in length) code is used: A - 0; B - 10; Q - 110. What code word should be used to encode the symbol G so that its length is minimal, and the code allows for an unambiguous division of the encoded message into symbols?

Answer:

To encode a certain sequence consisting of the letters K, L, M, N, we decided to use a non-uniform binary code that satisfies the Fano condition. For the letter H we used code word 0, for the letter K we used code word 110. What is the shortest possible total length of all four code words?

Note.

Answer:

To encode a certain sequence consisting of the letters K, L, M, N, we decided to use a non-uniform binary code that satisfies the Fano condition. For the letter L we used code word 1, for the letter M we used code word 011. What is the shortest possible total length of all four code words?

Note. The Fano condition means that no codeword is the beginning of another codeword. This makes it possible to unambiguously decrypt encrypted messages.

Answer:

Messages are transmitted through the communication channel, each of which contains 16 letters A, 8 letters B, 4 letters C and 4 letters G (there are no other letters in the messages). Each letter is encoded as a binary sequence. When choosing the code, two requirements were taken into account.

Task No. 5 in the Unified State Exam 2017

(in the Unified State Exam 2014 - task A9,

in the Unified State Exam 2015 - task 1)

Specification of control measuring materials for the 2016 unified state exam in computer science and ICT

Practice

1. Let's look at examples of tasks from Unified State Examinations of the past years

• ​To encode a certain sequence consisting of the letters A, B, C, D and D, a non-uniform binary code is used, which makes it possible to unambiguously decode the resulting binary sequence. Here is the code:

A - 00, B - 01, C - 100, D - 101, D - 110. Is it possible to shorten the length of the code word for one of the letters so that the code can still be decoded unambiguously? The codes of the remaining letters should not change.
Choose the correct answer.
1) for the letter D - 11
2) this is impossible
3) for the letter G - 10
4) for the letter D - 10

When solving this task, you can try to select a chain of letter codes that would be unambiguously decoded or, conversely, would not be unambiguously decoded, and analyze the options. But you can solve this problem faster by using the Fano condition (see in theory). Let's check whether it is possible to reduce the code of the letter G to 10. In this case, the Fano condition is violated, i.e. the code of the letter G will become the beginning of the code of the letter B, unambiguous decoding is impossible. We see the same thing if we reduce the code of the letter D to 10. This option is not suitable either. And if the code of the letter D is reduced to 11, then this code is neither the beginning nor the end of any code. This is the answer.

Answer: 1

• A 5-bit code is used to transmit data over a communication channel. The message contains only the letters A, B and C, which are encoded with the following code words:

A - 11010, B - 00110, C - 10101.
There may be interference during transmission. However, you can try to correct some errors. Any two of these three code words differ from each other in at least three positions. Therefore, if an error occurred in at most one position when transmitting a word, then an educated guess can be made about which letter was transmitted. (They say that “the code corrects one error.”) For example, if the code word 10110 is received, it is considered that the letter B was transmitted. (The difference from the code word for B is only in one position; for other code words there are more differences.)
If the received codeword differs from the codewords for the letters A, B, C in more than one position, then an error is considered to have occurred (it is denoted by 'x').
Received message 00111 11110 11000 10111. Decode this message - select the correct option.
1) BAAV
2) BAAx
3)xxxx
4) xAAx

I will arrange the letter codes in a column under each of the received code words:

	00111	111 10	1100 0	1011 1
A	11010	110 10	1101 0	11010
B	00110	00110	00110	00110
IN	10101	10101	10101	1010 1

I highlighted in red those numbers that differ in the word codes, and for those letters where there is no more than one difference. Thus, the received message can be decoded as BAAW.

Answer: 1

• To encode a certain sequence consisting of the letters A, B, C, D and D, a non-uniform binary code is used, which makes it possible to unambiguously decode the resulting binary sequence. Here is the code:

A - 0; B - 100; B - 1010; G - 111; D - 110. It is required to reduce the length of the code word for one of the letters so that the code can still be decoded unambiguously. The codes of the remaining letters should not change.
Which of the following methods can this be done?
1) for the letter B - 101
2) this is impossible
3) for the letter B - 010
4) for the letter B - 10

This task is practically no different from the first one, try to solve it yourself.

2. Solutions to Unified State Exam assignments on the website are very well explained. K.Polyakova ( )

3. And, in conclusion, I recommend taking the online test for task No. 1 (A1) on the websiteK.Polyakova(select) or on the website ege.yandex.ru (

1. Example assignment

Messages containing only four letters are transmitted over the communication channel,
A, B, C, D. For transmission, a non-uniform binary code is used that satisfies the Fano condition; for the letters A, B, C the following code words are used: A: 0, B: 100, C: 110.

Indicate the shortest code word that can be used for the letter G in such a code. If there are several such codes, indicate the code with the smallest numerical value.

Correct answer : 101

Solution: Since the code A is 0, the code for G cannot begin with 0 (the Fano condition for the letters A and G is violated). Therefore, the code for G must begin with 1. Both words of length 2 that begin with 1 cannot be used: 10 is the beginning of the code for the letter B, and 11 is the beginning of the code for the letter C. Of those starting with 1, words of length 3 to use as the code for Words 101 and 111 are available. In both cases, the Fano condition is satisfied. Of these, word 101 has the smallest code value (see Fig. 1).

Comment. The Fano condition will also be satisfied if any word that begins with 101 or 111 is used as a code for G. The Fano condition will NOT be satisfied if any word that begins with words 100 and 110 - codes for B - is used as a code for G and B. Together with the above, this means that as a code for G, use any word that begins with 101 or 111 and ONLY such a word.

Fig.5-1. All binary words are of length no more than 3; Each tree node corresponds to one such word. The nodes corresponding to the beginnings of code words are marked in red; orange – nodes corresponding to continuations of code words; green - words that can be code words for G if the Fano condition is met.

2. One more task

Messages containing only six letters are transmitted over the communication channel,
A, B, C, D, E, E. For transmission, a non-uniform binary code is used that satisfies the Fano condition; for the letters A, B, C the following code words are used: A: 0, B: 101, C: 110.

What is the smallest possible total length of all codewords?

Note. The Fano condition means that no codeword is the beginning of another codeword. Codes that satisfy the Fano condition allow unambiguous decoding.

Correct answer : 18

Solution: In accordance with the remark after solving problem 5-1, each of the code words for the letters G, D, E is a continuation of one of the words 100 and 111 (the codes for the letter B in the conditions of problems 5-1 and 5-2 are different). Thus, among the words that can be used, there are only two words of length 3 - the words 100 and 111 themselves. But if you use both of these words as code words, say, for the letters G and D, then there will be no code words left for the letter E - any of the words possible for E is a continuation of the words already selected for G and D. Therefore, in the code (say, for the letter G) you can use only one of the three-letter words 100 and 111. For the remaining two letters you will have to use 4-letter words. An example of such a code that satisfies the Fano condition: A: 0, B: 101, C: 110, D: 100, D: 1110, E: 1111. Total length of code words: 1+3+3+3+4+4 = 18 .

3. And one more task

Messages containing only 4 letters S, O, F, T are transmitted over the communication channel using a uniform binary code. To encode the letters S, O, F, 5-bit code words are used: S – 01111, O – 00001, F – 11000.

This set of codewords has the following property:

any two words from the set differ in at least three positions.

This property is important for decrypting messages in the presence of interference.

What code word can be used for the letter T so that the specified property holds for all four code words? In your answer, indicate the largest (in the sense of the denoted binary number) from such code words.

Correct answer : 10110

Solution:

The required number cannot begin with 11. Indeed, it is the only number that differs from the code of the letter F in at least 3 digits. – this is the number 11111. But this number is not suitable, because it differs from the letter C code in only one position. Therefore, the largest of the possible code words (if it starts with 1) must begin with 10. From comparison with the code of the letter C, we find that at least one of the three remaining digits is 0. The largest of such numbers is the number 10110. By checking, we are convinced that that it fits.

More coding tasks at

5. To encode a certain sequence consisting of the letters A, B, C, D, D, E, we decided to use a non-uniform binary code that satisfies the Fano condition.
For the letter A, the code word 0 was used; for the letter B – code word 10. What is the smallest possible sum of the lengths of all six code words?

Note.
The Fano condition means that no codeword is the beginning of another codeword. This makes it possible to unambiguously decrypt encrypted messages.

Answer: 19 ___________________________.

Solution:
1) We encode:
A 0
B 10
B 110
G 1110
D 1111
E 10000
total:19 Answer: 19

1.One more task

To encode a certain sequence consisting of the letters A, B, C, D and D, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. For the letters A, B, C and D, the following code words were used: A–111, B–110, B–100, G–0.

Indicate which of the following code words can be used to encode the letter D. The code must satisfy the property of unambiguous decoding. If more than one codeword can be used, enter the shortest one.

1) 00; 2) 001; 3) 10; 4) 101

Solution. The set of code words for the letters A, B, C, D is prefixed (none of them is the beginning of another). Let's see if among the proposed options there is one, after adding which the code will remain prefixed. However, unlike the task from the demo version, here, by condition, more than one option can lead to the result of a code that allows unambiguous decoding. Therefore, you need to sort through the options from shorter to longer and, if the option does not lead to a prefix code, make sure that this option actually gives a code that does not allow unambiguous decoding.

1) Code for D: 00 – does not allow unambiguous decoding (00 allows two decryptions: GG and D).

2) Code for D: 10 – does not allow unambiguous decoding (100 allows two decryptions: B and DG).

3) Code for D: 001 – does not allow unambiguous decoding (00100 allows two decodings: GGV and DGG).

4) Code for D: 101 – together with codes for A, B, C, D forms a prefix code.

Correct answer: 4

One more Problem 2.

To encode a certain sequence consisting of the letters A, B, C, D and D, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. Code used: A-1, B-000, B-001, G-011. Indicate what code word the letter D should be encoded with. The length of this code word should be the smallest of all possible. The code must satisfy the property of unambiguous decoding.

1) 00 2) 01 3) 11 4) 010

Solution. The set of code words for the letters A, B, C, D is prefixed (none of them is the beginning of another). Let's see if among the proposed options there is one, after adding which the code will remain prefixed.

1) 00 – not suitable (is the beginning of the code word 000 for the letter B);

2) 01 – not suitable (is the beginning of the code word 011 for the letter G);

3) 11 – not suitable (is a continuation (!) of code word 1 for the letter A);

4) 010 – suitable! (is not anyone’s beginning and no one is its beginning).

Answer: 4.

Note 1. The Fano condition is a sufficient condition for a code to be decodable unambiguously, but it is not necessary. That is, a code may allow unambiguous decoding, but not satisfy the Fano condition. The simplest example of such codes is the so-called. postfix codes. These are codes in which no code word is the end of another code word. For these codes, decoding is done in the same way as for prefix codes, but moving from right to left.

Note 2. In the considered problem A, it is enough to find one option that satisfies the requirements of the problem. It is NOT REQUIRED to prove that the other options will not allow the code to be unambiguously decoded. However, in in this case it's easy to do. Namely.