코드는 모호하지 않은 디코딩 속성을 충족해야합니다. 정보학 EGE, 과제 A9, 폴리 아 코프 K

  테마: 정보 인코딩 및 해독

  항목 확인 : 인코딩 및 de 능력 정보를 인 코드하다

이론 자료 :

  코딩  - 한 언어에서 다른 언어로 정보를 번역하는 것입니다 (다른 알파벳으로 다른 시스템에서 작성).

인코딩 된 메시지는 다음과 같은 경우 처음부터 고유하게 디코딩 될 수 있습니다.  파노 조건: 코드 워드가없는 다른 코드 워드의 시작입니다.

인코딩 된 메시지는 다음과 같이 고유하게 디코딩 될 수 있습니다 if  역노 조건: 코드 워드가없는 다른 코드 워드의 끝입니다.

Fano 조건은 모호하지 않은 디코딩을 위해 충분하지만 필수 조건은 아닙니다.

작업 예 :

문자 A, B, C, D 및 D로 구성된 시퀀스를 인코딩하기 위해 우리는 통신 채널의 수신 측에 나타나는 바이너리 시퀀스를 고유하게 디코딩 할 수 있도록 고르지 않은 바이너리 코드를 사용하기로 결정했습니다. 사용 된 코드는 A - 1, B - 000, B - 001, D - 011이었습니다. 문자 D에 대한 코드 워드를 지정하십시오.

코드는 모호하지 않은 디코딩 속성을 충족해야합니다.

일반적인 접근 방식 :

Fano 조건 또는 논리적 추론을 사용하여 답을 찾으십시오.

해결책 :

1) 00 - Fano 조건을 ​​위반합니다. 코드 체인은 B = 000 및 B = 001의 시작과 일치합니다. 체인 000000을 모호하지 않게 디코딩하는 것은 불가능합니다 : DDD 또는 BB가 될 수 있으므로 첫 번째 옵션은 맞지 않습니다.

2) 01 - Fano 조건을 ​​위반합니다. 코드 체인은 T = 011의 시작과 일치합니다.  H 모호하지 않게 체인 011을 디코딩하는 것은 불가능합니다 : YES 또는 G 일 수 있으므로 두 번째 옵션도 적합하지 않습니다

3) 11 - Fano 조건을 ​​위반합니다. 코드 체인은 시작 A = 1과 일치합니다. N모호하지 않게 체인 111을 디코딩하는 것은 불가능합니다 : 이것은 YES 또는 AAA 일 수 있습니다. 세 번째 옵션은 적합하지 않습니다.

4) 010 - Fano 상태가 위반되지 않았습니다.

답변 : 4) 010

교육을위한 과제 :

1) 문자 A, B, C, D로만 이루어진 메시지의 통신 ​​채널을 통한 전송의 경우 길이가 고르지 않은 코드, A = 00, B = 11, C = 100을 사용하기로 결정했습니다. 문자 길이가 최소이고 코드화 된 메시지의 일대일 분리가 허용되도록 문자 G를 어떻게 부호화해야합니까?

2) 문자 A, B, C, D로만 구성된 메시지의 통신 ​​채널을 통한 전송의 경우 길이가 고르지 않은 코드, 즉 A = 1, B = 000, C = 001을 사용하기로 결정했습니다. 문자 길이가 최소이고 코드화 된 메시지의 일대일 분리가 허용되도록 문자 G를 어떻게 부호화해야합니까?

3) 문자 A, B, C, D 및 D로 구성된 시퀀스를 인코딩하려면 불균등 한 2 진 코드가 사용되며 결과 바이너리 시퀀스를 고유하게 디코딩 할 수 있습니다. 이 코드는 A - 10, B - 11, B - 000, D - 001, D - 011입니다. 코드 중 하나에 대한 코드 워드의 길이를 단축하여 명확하게 코드를 디코딩 할 수 있습니까? 나머지 문자의 코드는 변경하면 안됩니다. 정답을 선택하십시오.

1) 불가능하다.

2) 문자 B - 1

3) B - 00 문자

4) D - 01 문자

4) 문자 A, B, C, D 및 D로 구성된 특정 시퀀스를 인 코드하기 위해 불균일 한 이진 코드가 사용되어 결과 바이너리 시퀀스를 모호하지 않게 디코딩 할 수 있습니다. 이 코드는 A - 11, B - 10, B - 011, D - 000, D - 001입니다. 코드 중 하나에 대한 코드 워드의 길이를 단축하여 명확하게 코드를 디코딩 할 수 있습니까? 나머지 문자의 코드는 변경하면 안됩니다. 정답을 선택하십시오.

1) 문자 G - 00

2) 불가능하다.

3) B - 01 문자

4) 문자 B - 1

5) 문자 A, B, C, D 및 D로 구성된 시퀀스를 인코딩하려면 불균등 한 바이너리 코드가 사용되며 결과 바이너리 시퀀스를 고유하게 디코딩 할 수 있습니다. 이 코드는 A - 10, B - 001, B - 0001, D - 110, D - 111입니다. 코드 중 하나에 대한 코드 워드의 길이를 단축하여 명확하게 코드를 디코딩 할 수 있습니까? 나머지 문자의 코드는 변경하면 안됩니다. 정답을 선택하십시오.

1) G-11 문자

2) 불가능하다.

3) B - 000 문자

문자 A, B, C, D, D 및 E로 구성된 특정 시퀀스를 인코딩하려면 Fano 조건을 ​​만족하지 않는 고르지 않은 이진 코드를 사용하기로 결정했습니다. 문자 A의 경우 코드 워드 0이 사용되었습니다. 문자 B의 경우, 코드 워드 10. 6 개의 코드 워드 길이의 가능한 한 작은 합계는 얼마입니까?
참고 Fano 조건은 코드 워드가 다른 코드 워드의 시작이 아님을 의미합니다. 이렇게하면 코드화 된 메시지를 모호하지 않게 해독 할 수 있습니다.

데모 옵션 EGE 2017 - 작업 번호 5

해결책 :

코드 워드를 찾으려면이 표를 사용하십시오.

나머지 문자의 코드가 0에서 시작하면 문자 A = 0의 코드가 코드의 시작 부분이되므로이 옵션은 적합하지 않습니다. 코드 B = 10이면 문자 C, D, D, E의 코드는 11에서 시작합니다. 4 개의 다른 코드를 얻으려면 4 자 (1111, 1110, 1101, 1100)로 구성된 코드를 사용해야합니다.

0	1
	1
	1		0
	1	0	1	0

A - 0 (1 문자)
  B - 10 (2 자)
  B - 1100 (4 자)
  G - 1101 (4 문자)
  D - 1110 (4 자)
  E - 1111 (4 문자)

1+2+4+4+4+4 = 19

답변 : 19

데모 옵션 EGE 2016 - 작업 번호 5

통신 채널은 P, O, C, T; 전송을 위해, 모호하지 않은 디코딩을 허용하는 바이너리 코드가 사용된다. 문자 T, O, P의 경우 다음 코드 워드가 사용됩니다. T : 111, O : 0, P : 100.

코드에서 모호하지 않은 디코딩을 허용하는 문자 C에 대해 가장 짧은 코드 단어를 지정하십시오. 그러한 코드가 여러 개인 경우 숫자가 가장 작은 코드를 지정하십시오.

해결책 :

코드 워드를 찾으려면이 스키마를 사용하십시오.

나머지 문자의 코드가 시작되면 0 문자 코드 오.=0   코드의 시작 부분이므로이 옵션은 적합하지 않습니다. 편지의 코드 이후 F=100 및 문자 코드 T =111 그 다음 편지 와  이 번호로 시작하고 끝낼 수 없습니다.

답변 : 101

문자 A, B, C 및 D만으로 구성된 메시지를 인코딩하려면 이진 코드 길이가 고르지 않습니다.

이러한 방식으로 문자 시퀀스 GAVBGV를 인코딩하고 그 결과를 16 진 코드로 작성하면 다음과 같은 결과를 얻습니다.

1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16

해결책 :

GAVBGV = 0110001011011010

0110	0010	1101	1010
6	2	D	A

답변 : 4

흑백 비트 맵 이미지는 왼쪽 위 모퉁이에서 시작하여 오른쪽 아래 모서리에서 끝나는 라인 단위로 인코딩됩니다. 인코딩 할 때 1은 검은 색을 나타내고 0은 흰색을 나타냅니다.

압축을 위해 결과는 8 진법으로 기록되었습니다. 올바른 코드 항목을 선택하십시오.

1) 57414 2) 53414 3) 53412 4) 53012

해결책 :

1	0	1	0	1
1	1	0	0	0
0	1	0	1	0

101	011	100	001	010
5	3	4	1	2

답변 : 3

시끄러운 채널을 통해 번호를 전송할 경우 패리티 검사 코드가 사용됩니다. 각 자릿수는 길이가 4 인 선행 제로로 2 진 표현으로 작성되고 모듈로 2의 요소 합계가 결과 시퀀스에 추가됩니다. 예를 들어, 23을 전달하면 0010100110 시퀀스가 ​​생성됩니다. 01100010100100100110 형식으로 채널을 통해 전송 된 번호를 결정 하시겠습니까?

1) 6543 2) 62926 3) 62612 4) 3456

해결책 :

01100010100100100110

01100	01010	01001	00110
6	5	4	3

답변 : 1

O, L, A, G, K의 문자를 부호화하기 위해서, 각각 0, 1, 2, 3, 4의 2 진 코드가 사용됩니다 (1 비트 표현의 경우에는 1이 중요하지 않습니다). 문자 VOKOLKA의 시퀀스를 인코딩하고 결과를 16 진수 코드로 작성하는 방법은 다음과 같습니다.

1) 4531253 2) 9876 3) E832 4) 238E

해결책 :

오.	L	A	H	~까지
0=00	1=01	2=10	3=11	4=100

COUNT = 1110100000110010

1110	1000	0011	0010
전자	8	3	2

답변 : 3

문자 A, B, C, D로만 이루어진 메시지의 통신 ​​채널을 통한 전송의 경우 길이가 고르지 않은 코드, 즉 A = 00, B = 11, C = 100을 사용하기로 결정했습니다. 문자 길이가 최소이고 코드화 된 메시지의 일대일 분리가 허용되도록 문자 G를 어떻게 부호화해야합니까?

1) 010 2) 0 3) 01 4) 011

해결책 :

A = 00, B = 11, C = 100, D =

답변 : 3

문자 A, B, C, D 및 D로 구성된 시퀀스를 인코딩하기 위해 우리는 통신 채널의 수신 측에 나타나는 바이너리 시퀀스를 고유하게 디코딩 할 수 있도록 고르지 않은 바이너리 코드를 사용하기로 결정했습니다. 문자 A, B, C 및 D의 경우 A - 111, B - 110, C - 101, D - 100과 같은 코드 단어가 사용되었습니다.

문자 D를 인코딩하려면 아래 나열된 코드 단어를 지정하십시오.

코드는 모호하지 않은 디코딩 속성을 충족해야합니다. 둘 이상의 코드 워드를 사용할 수있는 경우 가장 짧은 코드 워드를 지정하십시오.

1) 1 2) 0 3) 01 4) 10

해결책 :

A-111, B-110, B-101, D-100, D-

답변 : 2

통신 채널은 A, B, C, G의 4 문자 만 포함하는 메시지를 전송합니다. A, B, C : A - 10110, B - 11000, C - 00101 문자를 인코딩하는 데 5 비트 코드 워드가 사용됩니다. 다음 속성이 충족되었습니다. 세트의 두 단어가 적어도 세 위치에서 다릅니다. 이 속성은 간섭이있는 경우 메시지를 디코딩 할 때 중요합니다. 다음 중 G 코드에 사용할 수있는 다음 코드 중 4 개의 코드 단어 모두에 대해 지정된 속성을 사용할 수 있습니까?

1) 01110 2) 01011 3) 10001 4) 위의 단어 중 어느 것도 적용되지 않습니다.

해결책 :

1) 01 110 : A - 10 110 - 적어도 세 가지 위치에서 다르지 않음

2) 01011 : A-101 10, B-1 1000, B-0010 1 - 적어도 3 개 위치가 상이 함

답변 : 2

통신 채널을 통한 데이터 전송의 경우, 5 비트 코드가 사용된다. 메시지에는 다음 코드 단어로 인코딩 된 문자 A, B 및 C 만 포함됩니다.

A-10001, B-01101, B-10110.

변속기가 간섭을 일으킬 수 있습니다. 그러나 일부 오류는이를 수정하려고 할 수 있습니다. 이들 3 개의 코드 워드 중 임의의 2 개는 적어도 3 개의 위치에서 서로 상이하다. 따라서 단어 전송시 하나 이상의 위치에서 오류가 발생하면 어떤 문자가 전송되었는지에 대해 합리적인 가정을 할 수 있습니다. 예를 들어, 코드 워드 01111이 수신되면, 문자 B가 전송 된 것으로 간주됩니다 (B에 대한 코드 워드와의 차이점은 다른 코드 워드에 대해서는 더 많은 차이가 있음을 나타냅니다). 수신 된 코드 워드 단어가 두 개 이상의 위치에서 문자 A, B, C의 코드 단어와 다르므로 오류가 발생했다고 간주됩니다 ( 'x'로 표시됨).

메시지 수신 00110 11101 11000 11001.이 메시지 디코드 - 올바른 옵션을 선택하십시오.

1) VBHH 2) ABBVA 3) xxxx 4) VBHA

해결책 :

00110	11101	11000	11001
B = 1,101	B = 0 1101	x	A = 10 001

답변 : 4

문자 A, B, C, D 및 D로 구성된 특정 시퀀스를 인 코드하려면 균일하지 않은 이진 코드가 사용되어 결과 바이너리 시퀀스를 고유하게 디코딩 할 수 있습니다. 다음은 코드입니다. A - 1; B-0100; B - 000; G-011; D - 0101. 코드가 고유하게 디코딩 될 수 있도록 문자 중 하나에 대한 코드 워드의 길이를 단축해야합니다. 나머지 문자의 코드는 변경하면 안됩니다. 다음 중 수행 할 수있는 방법은?

A-1, B-011, B-00, G-010

답변 : 9

통신 채널은 각각 15 개의 문자 A, 10 개의 문자 B, 6 개의 문자 C 및 4 개의 문자 D (메시지에 다른 문자가 없음)를 포함하는 메시지를 전송합니다. 각 문자는 바이너리 시퀀스로 인코딩됩니다. 코드를 선택할 때 두 가지 요구 사항이 고려되었습니다.

a) 코드 워드는 다른 코드 워드의 시작이 아니다. (코드가 모호하지 않은 디코딩을 허용해야한다.)

b) 부호화 된 메시지의 전체 길이는 가능한 한 짧아야한다.

문자 A, B, C 및 D를 인코딩하기 위해 다음 중 어떤 코드를 선택해야합니까?

1) A : 1, B : 01, B : 001, D : 111

2) A : 1, B : 01, C : 10, D : 111

3) A : 00, B : 01, C : 10, D : 11

4) A : 100, B : 101, C : 11, D : 0

해결책 :

코드 워드는 다른 코드 워드의 시작이 아닙니다. A  시작이다. R  1 및 2 버전.

인코딩 된 메시지의 전체 길이는 가능한 짧아야합니다.

3 : A : 00 (15), B : 01 (10), B : 10 (6), D : 11 (4)

2.15+2.10+2.6+2.4 = 70

A : 100 (15), B : 101 (10), B : 11 (6), D : 0 (4)

3.15+3.10+2.6_1.4 = 61

답변 : 3

통신 채널은 균일 한 2 진 코드를 사용하여 4 개의 문자 P, P, C, T 만 포함하는 메시지를 전송합니다. 각 문자는 자체 코드 워드에 해당하며 다음과 같은 속성이 일련의 코드 워드에 대해 충족됩니다. 세트의 두 단어는 적어도 3 순위. 이 속성은 간섭이있는 경우 메시지를 디코딩 할 때 중요합니다. 문자 P에 대한 5 비트 코드는 1에서 시작하여 0에서 끝납니다. 문자 T에 대한 코드 워드를 결정하십시오. 문자 P에 대한 5 비트 코드는 1에서 시작하여 0에서 끝납니다. 문자 P, P, C를 인 코드하려면 5 비트 코드 워드가 사용됩니다 : P : 01111, P : 00001, C : 11000.

해결책 :

C : 1 1000

T : 1,011 0 (T는 1에서 시작하여 0에서 끝납니다)

C와 T : 2 글자가 같으면 다른 3 글자가 달라야 함을 의미합니다.

답변 : 1 0110

컴퓨터 과학의 통합 주 시험, 과제 A9, Polyakov K.

문자 A, B, C, D 및 D로 구성된 특정 시퀀스를 인 코드하려면 균일하지 않은 이진 코드가 사용되어 결과 바이너리 시퀀스를 고유하게 디코딩 할 수 있습니다. 이 코드는 A - 00, B - 010, B - 011, D - 101, D - 111입니다. 코드 중 하나에 대한 코드 워드의 길이를 단축하여 명확하게 코드를 디코딩 할 수 있습니까? 나머지 문자의 코드는 변경하면 안됩니다. 정답을 선택하십시오.

예제들
1. 문자 A, B, C, D 및 D로 구성된 시퀀스를 인코딩하기 위해 우리는 통신 채널의 수신 측에 나타나는 바이너리 시퀀스를 고유하게 디코딩 할 수 있도록 고르지 않은 바이너리 코드를 사용하기로 결정했습니다. 사용 된 코드 :
A-1, B-000, B-001, D-011. 문자 D에 대한 코드 워드를 지정하십시오.이 코드 워드의 길이는 가능한 한 작아야합니다. 코드는 모호하지 않은 디코딩 속성을 충족해야합니다.
1) 00 2) 01 3)11 4) 010
해결책 :
8) 코드의 알려진 부분에 대해 Fano 조건이 충족되었음을 주목하십시오 - 코드 단어는 다른 코드 단어의 시작 부분이 아닙니다
9) D = 00 인 경우 B = 000 및 B = 001의 시작 부분과 일치하므로 000000 문자열을 모호하지 않게 디코딩 할 수 없습니다. DDD 또는 BB 일 수 있습니다. 그래서 첫 번째 옵션은 적합하지 않습니다.
10) D = 01 인 경우, 그러한 코드 체인은 T = 011의 시작과 일치하며, 체인을 모호하지 않게 디코딩하는 것은 불가능합니다. 011 : YES 또는 T 일 수 있습니다. 두 번째 옵션도 적합하지 않습니다.
11) D = 11이면 Fano 조건도 위반됩니다. 코드 워드 A = 1이 문자 D의 코드 시작과 일치하므로 체인을 모호하지 않게 디코딩 할 수 없습니다. 111 : 예 또는 AAA 일 수 있습니다. 세 번째 옵션은 적합하지 않습니다.
12) D = 010, Fano 조건을 ​​위반하지 않습니다.
13) 정답은 4입니다.

2. 문자 A, B, C, D로만 이루어진 메시지의 통신 ​​채널을 통한 전송의 경우 길이가 고르지 않은 코드, 즉 A = 0, B = 10, C = 110을 사용하기로 결정했습니다. 문자 길이가 최소이고 코드화 된 메시지의 일대일 분리가 허용되도록 문자 G를 어떻게 부호화해야합니까?
1) 1 2) 1110 3) 111 4) 11
솔루션 (옵션 1, 선택 방법) :
1) 코드 문자 G의 길이를 늘리는 순서로 모든 옵션을 고려하십시오
2) T = 1로 시작합니다. 메시지 "10"은 GA 또는 B와 같이 두 가지 방식으로 디코딩 될 수 있으므로이 옵션은 적합하지 않습니다.
3) 다음으로 가장 긴 옵션은 T = 11이다. 이 경우 메시지 "110"은 HA 또는 B로 디코딩 될 수 있으므로이 옵션도 적합하지 않습니다
4) 세 번째 옵션 인 G = 111은 모든 문자 조합에서 모호하지 않은 디코딩을 제공하므로 ...
5) ... 정답은 3입니다.

가능한 문제점 :
  반복 할 때 실수를하고 옵션을 볼 수 있습니다.

해결책 (옵션 2, "스마트"방법) :
1) 불균일 코드를 사용하여 기록 된 메시지가 모호하지 않게 복호화되기 위해서는 어떤 코드도 다른 (더 긴) 코드의 시작이 아니어야한다. 이 조건을 Fano 조건이라고합니다.
2) 첫 번째 솔루션에서와 마찬가지로, 우리는 Γ 문자에 대한 가장 짧은 코드로 시작하는 옵션을 고려합니다. 우리의 경우 코드 T = 1은 문자 B와 C의 코드의 시작이므로 Fano 조건이 만족되지 않으면이 코드는 적합하지 않습니다
3) 코드 D = 11은 다른 코드 (문자 B의 코드)의 시작이기도하므로 잘못된 변형입니다
4) 코드의 세 번째 변종 인 G = 111은 이미 알려진 코드의 시작이 아닙니다. 또한 기존 코드 중 어느 것도 코드 111의 시작 부분이 아닙니다. 그래서 fano 조건이 충족된다.
5) 그러므로 정답은 3입니다.

편리한 형식으로 전자 책을 무료로 다운로드하고 읽으십시오.

컴퓨터 과학 시험 A9, Polyakov K. - fileskachat.com을 빠르고 무료로 다운로드하십시오.