코드가 fano 조건을 충족합니까? 우리는 컴퓨터 과학 통합 국가 시험을 준비하고 있습니다. 파노 상태. Fano 조건의 실제 적용
다른 코드 테이블을 고려해 보겠습니다. A B C D D 000 01 10 011 100 여기서 Fano 조건은 만족되지 않습니다. 왜냐하면 문자 B(01)의 코드는 문자 G(011) 코드의 시작이고 문자 코드는 D(100)는 문자 B(10)의 코드로 시작됩니다. 그러나 "역" Fano 조건이 충족된다는 점을 알 수 있습니다. 즉, 어떤 코드도 다른 코드의 끝이 아닙니다(이러한 코드를 postfix라고 함). 따라서 인코딩된 메시지는 끝에서부터 명확하게 디코딩될 수 있습니다. 예를 들어 체인 011000110110을 생각해 보세요. 마지막 편지이 메시지에는 B(코드 10)만 있을 수 있습니다: B 0110001101 10 끝에서 두 번째 문자는 B(코드 01): B B 01100011 01 10 등입니다: B D G B B 01 100 011 01 10.
슬라이드 26프레젠테이션에서 "정보 인코딩 방법". 프레젠테이션이 포함된 아카이브의 크기는 734KB입니다.코딩 방법
다른 프레젠테이션 요약"이진 코딩" - 숫자. 바이너리 코딩 텍스트 정보. 인코딩 테이블. 텍스트의 정보량. 컴퓨터의 이진 코딩. 텍스트 정보의 코딩. 확장된 코드 테이블. 상징. 고유한 바이너리 코드입니다. 편지 라틴 알파벳. 바이너리 시스템을 사용합니다. 컴퓨터.
"이진 코드로 정보 인코딩" - 정의. 숫자 체계. 바이너리 시스템계산. 코딩. 정보의 인코딩. 코딩 예시를 들어보세요. 십진수 시스템. 숫자의 의미. 숫자의 의미는 위치에 따라 다릅니다. 알파벳. 언어. 로마 인 비 위치 시스템. 바이너리 코딩. 여기서 암호화된 것은 무엇입니까?
"코딩 방법" - 열 번호입니다. 편지 원본 텍스트. 정보의 인코딩. 정보 인코딩 방법. 정보를 디코딩합니다. 전송된 정보. 코드의 세계에서. 자동 코딩. 좌표 방법. 장점과 단점. 다양한 코드. 소년. 무엇을 부를 수 있나요? 공책정보 저장 측면에서. 인코딩된 텍스트. 정보매체. 키워드. 퍼즐을 풀어보세요.
"정보 인코딩 방법" - 컴퓨터 메모리에서 정보는 이진 코드로 표시됩니다. 인코딩 및 디코딩. 정보를 인코딩할 수 있습니다. 정보 인코딩 방법. 간단한 코드 테이블을 만들어 보겠습니다. 암호화된 단어를 찾으려면 첫 음절만 취하세요. 다가오는 스쿠너의 깃발에서 Lom이 읽은 것. 생각해 내다 나만의 방식러시아 알파벳의 문자 코딩. 작업. 암호화된 정보. 루이 점자 발명 특별한 방법정보 제시.
"정보 인코딩 방법" - 컴퓨터의 이진 코딩. 정보의 양. Shapp 광학 전신. 파노 상태. 사용할 코드. 메시지 받음. "예 혹은 아니오". 최초의 전신. 정보 인코딩 방법. 녹음 정보. 왜 바이너리 코딩인가? 신호 플래그. 코딩. 인코딩 및 디코딩. 정보의 인코딩. 인코딩 방법을 선택합니다. 정보 유형. 옵션은 몇 개인가요?
이 수업은 컴퓨터 과학 통합 상태 시험의 과제 5를 해결하는 방법에 대해 다룹니다.
다섯 번째 주제는 과제로 특징지어집니다. 기본 레벨난이도, 실행시간 - 약 2분, 최대점수 - 1
- 코딩- 저장, 전송 및 처리에 편리한 형식으로 정보를 표시하는 것입니다. 정보를 그러한 표현으로 변환하는 규칙을 암호.
- 코딩이 일어난다 제복그리고 고르지 않은:
- 균일한 인코딩을 사용하면 모든 기호는 동일한 길이의 코드에 해당합니다.
- ~에 고르지 못한 코딩 다른 문자길이가 다른 코드에 대응하면 디코딩이 어려워집니다.
예:다음을 사용하여 문자 A, B, C, D를 암호화해 보겠습니다. 바이너리 코딩균일한 코드를 생성하고 가능한 메시지 수를 계산합니다.
그래서 우리는 얻었습니다 유니폼 코드, 왜냐하면 각 코드 단어의 길이는 모든 코드에서 동일합니다. (2).
메시지 인코딩 및 암호 해독
디코딩 (디코딩)- 일련의 코드에서 메시지를 복원하는 것입니다.
디코딩 문제를 해결하려면 Fano 조건을 알아야 합니다.
파노 조건:없음 코드워드다른 코드워드의 시작 부분이어서는 안 됩니다(메시지가 처음부터 명확하게 디코딩되도록 보장).
접두사 코드다른 코드워드의 시작과 일치하는 코드워드가 없는 코드입니다. 이 코드를 사용하는 메시지는 명확하게 디코딩됩니다.
명확한 디코딩이 제공됩니다.
5가지 통합 상태 시험 문제 해결
통합 상태 시험 5.1:문자 O, B, D, P, A를 인코딩하기 위해 우리는 각각 숫자 0, 1, 2, 3, 4의 이진 표현을 사용하기로 결정했습니다(단일 문자의 경우 하나의 중요하지 않은 0을 보존함). 숫자 표현).
이런 식으로 WATERFALL이라는 문자 시퀀스를 인코딩하고 결과를 8진수 코드로 작성합니다.
✍ 해결책:
- 숫자를 이진 코드로 변환하고 문자와 일치시켜 보겠습니다.
결과: 22162
통합 주 시험 결정 이 과제의컴퓨터 과학 분야의 비디오:
또 다른 분석을 생각해 보자 5 통합 상태 시험 과제:
통합 상태 시험 5.2:라틴 알파벳 5자의 경우 해당 이진 코드가 지정됩니다(일부 문자의 경우 2비트, 일부 문자의 경우 3비트). 이 코드는 표에 나와 있습니다.
| ㅏ | 비 | 씨 | 디 | 이자형 |
|---|---|---|---|---|
| 000 | 110 | 01 | 001 | 10 |
이진 문자열 1100000100110으로 인코딩되는 문자 집합은 무엇입니까?
✍ 해결책:
- 먼저 Fano 조건을 확인합니다. 코드워드가 다른 코드워드의 시작이 아니라는 것입니다. 조건은 참입니다.
- 표에 제시된 데이터에 따라 코드를 왼쪽에서 오른쪽으로 나눕니다. 그런 다음 문자로 번역해 보겠습니다.
✎ 1가지 솔루션:
결과: b a c d e.
✎ 두 번째 해결 방법:
110
000 01
001 10
결과: b a c d e.
또한 컴퓨터 과학 분야의 통합 상태 시험 과제에 대한 솔루션에 대한 비디오를 시청할 수 있습니다.
다음 5번째 과제를 풀어보겠습니다.
통합 상태 시험 5.3:
잡음이 많은 채널을 통해 숫자를 전송하려면 패리티 검사 코드가 사용됩니다. 각 숫자는 다음과 같이 기록됩니다. 이진 표현, 길이 4에 선행 0이 추가되고 모듈로 2의 요소 합계가 결과 시퀀스에 추가됩니다(예를 들어 23을 전송하면 시퀀스 0010100110을 얻습니다).
01100010100100100110 형식으로 채널을 통해 전송된 번호를 확인합니다.
✍ 해결책:
- 고려해 봅시다 예문제 설명에서 :
답변: 6 5 4 3
컴퓨터 과학 분야의 통합 상태 시험 과제에 대한 솔루션에 대한 비디오를 시청할 수 있습니다.
통합 상태 시험 5.4:
문자 K, L, M, N으로 구성된 특정 시퀀스를 인코딩하기 위해 그들은 Fano 조건을 충족하는 비균일 이진 코드를 사용하기로 결정했습니다. 문자 H에는 코드워드 0이 사용되었고 문자 K에는 코드워드 10이 사용되었습니다.
4개의 코드워드 모두의 가능한 가장 짧은 총 길이는 얼마입니까?
✍ 해결책:
✎ 1개의 솔루션 옵션논리적 결론을 바탕으로:
- 모든 문자에 대해 가능한 가장 짧은 코드워드를 찾아봅시다.
- 코드워드 01 그리고 00 Fano 조건을 위반하므로 사용할 수 없습니다(0부터 시작하고 0 - 이것 N).
- 두 자리 코드워드부터 시작해 보겠습니다. 편지를 받아보자 엘코드워드 11 . 그러면 Fano 조건을 위반하지 않고 네 번째 문자에 대한 코드 단어를 선택하는 것이 불가능합니다(110 또는 111을 사용하면 11로 시작됩니다).
- 이는 3자리 코드워드를 사용해야 함을 의미합니다. 문자를 인코딩하자 엘그리고 중코드 단어 110 그리고 111 . Fano 조건이 만족됩니다.
✎ 옵션 2:
(N) -> 0 -> 1자 (K) -> 10 -> 2자 (L) -> 110 -> 3자 (M) -> 111 -> 3자 답변: 9
정보학 5 작업 2017 FIPI 옵션 2의 통합 상태 시험(Krylov S.S., Churkina T.E. 편집):
4개의 문자만 포함된 메시지는 통신 채널(A, B, C, D)을 통해 전송됩니다. 전송에는 명확한 디코딩을 허용하는 이진 코드가 사용됩니다. 문자 A, B, C의 경우 A: 101010, B: 011011, C: 01000과 같은 코드 워드가 사용됩니다.
Г, 코드가 명확한 디코딩을 허용합니다. 가장 작은수치.
✍ 해결책:
- 가장 작은 코드는 다음과 같습니다. 0 그리고 1 (한 자리). 그러나 이는 Fano 조건을 만족하지 않습니다( ㅏ하나로 시작합니다 - 101010 , 비처음부터 시작됩니다 - 011011 ).
- 다음으로 가장 작은 코드는 두 글자 단어입니다. 00 . 제시된 코드워드의 접두사가 아니기 때문에 지 = 00.
결과: 00
정보학 5 작업 2017 FIPI 옵션 16의 통합 상태 시험(Krylov S.S., Churkina T.E. 편집):
문자 A, B, C, D 및 D로 구성된 특정 시퀀스를 인코딩하기 위해 우리는 비균일 이진 코드를 사용하기로 결정했습니다. 이를 통해 통신 채널의 수신 측에 나타나는 이진 시퀀스를 명확하게 디코딩할 수 있습니다. 사용된 코드는 A - 01, B - 00, C - 11, D - 100입니다.
문자 D를 인코딩해야 하는 코드 단어를 나타냅니다. 길이이 코드워드는 최소가능한 모든 것. 코드는 속성을 충족해야 합니다. 명확한 디코딩. 해당 코드가 여러 개인 경우 숫자 값이 가장 낮은 코드를 표시하십시오.
✍ 해결책:
결과: 101
수업에 대한 더 자세한 분석은 컴퓨터 과학 2017 통합 상태 시험 비디오에서 볼 수 있습니다.
정보학 5 작업 2017 FIPI 옵션 17(Krylov S.S., Churkina T.E.)의 통합 상태 시험:
문자 A, B, C, D, D 및 E로 구성된 특정 시퀀스를 인코딩하기 위해 우리는 비균일 이진 코드를 사용하기로 결정했습니다. 이를 통해 통신 채널의 수신 측에 나타나는 이진 시퀀스를 명확하게 디코딩할 수 있습니다. . 사용된 코드는 A - 0, B - 111, C - 11001, D - 11000, D - 10입니다.
문자 E를 인코딩해야 하는 코드 단어를 나타냅니다.이 코드워드의 길이는 가능한 한 짧아야 합니다. 코드는 명확한 디코딩 특성을 충족해야 합니다. 해당 코드가 여러 개인 경우 숫자 값이 가장 낮은 코드를 표시하십시오.
✍ 해결책:
1 - 부적합(A를 제외한 모든 문자는 1로 시작) 10 - 부적합(코드 D에 해당) 11 - 부적합(코드 B, C 및 D의 시작) 100 - 부적합(코드 D - 10 -은 101 - 부적합(코드 D - 10 - 이 코드의 시작) 110 - 부적합(코드 B 및 D의 시작) 111 - 부적합(코드 B에 해당) 1000 - 부적합( 코드 D - 10 - 이 코드의 시작) 1001 - 부적합(코드 D - 10 - 이 코드의 시작) 1010 - 부적합(코드 D - 10 - 이 코드의 시작) 1011 - 부적합 (코드 D - 10 - 이 코드의 시작) 1100 - 적합하지 않음(코드 B 및 D의 시작) 1101 - 적합
결과: 1101
더 상세한 솔루션이 작업은 비디오 튜토리얼에 나와 있습니다.
작업 5. 통합 상태 시험 2018 컴퓨터 과학(FIPI)의 데모 버전:
10개의 문자만 포함된 암호화된 메시지는 A, B, E, I, K, L, R, S, T, U 통신 채널을 통해 전송됩니다. 전송에는 고르지 않은 이진 코드가 사용됩니다. 코드어는 9글자에 사용됩니다. 
문자에 대한 가장 짧은 코드 단어를 지정하십시오. 비, 코드는 Fano 조건을 충족합니다.그러한 코드가 여러 개인 경우 다음과 같이 코드를 표시하십시오. 가장 작은수치.
✍ 해결책:
결과: 1100
2018년 통합 상태 시험 데모 버전의 5번째 작업에 대한 자세한 솔루션을 보려면 다음 비디오를 시청하세요.
작업 5_9. 2017년 모델 시험 옵션. 옵션 4(Krylov S.S., Churkina T.E.):
네 글자만 포함된 암호화된 메시지는 통신 채널(A, B, C, D)을 통해 전송됩니다. 전송에는 명확한 디코딩을 허용하는 이진 코드가 사용됩니다. 편지의 경우 ㅏ, 비, 안에사용된 코드 단어:
A: 00011 B: 111 C: 1010
문자에 대한 가장 짧은 코드 단어를 지정하십시오. G, 코드는 명확한 디코딩을 허용합니다.그러한 코드가 여러 개인 경우 다음과 같이 코드를 표시하십시오. 가장 작은수치.
✍ 해결책:
결과: 00
작업 5_10. 2018년 10월 1일의 교육 옵션 3번(FIPI):
문자만 포함된 메시지는 통신 채널을 통해 전송됩니다. A, E, D, K, M, R; 전송에는 Fano 조건을 만족하는 바이너리 코드가 사용된다. 사용되는 것으로 알려짐 다음 코드:
E – 000 D – 10 K – 111
인코딩된 메시지 길이를 최대한 짧게 지정하세요. 데마카르.
답에 숫자(비트 수)를 쓰십시오.
✍ 해결책:
D E D M A K A R 10,000 10,001 01,111 01,110
결과: 20
작업에 대한 솔루션을 참조하세요.
작업 31. 고르지 않은 코드. 파노 조건
5-54 문자 A, B, C, D 및 D로 구성된 특정 시퀀스를 인코딩하기 위해 비균일 이진 코드를 사용하기로 결정했습니다. 이를 통해 수신 측에 나타나는 이진 시퀀스를 명확하게 디코딩할 수 있습니다. 통신 채널. 문자 A, B, C 및 D의 경우 A - 001, B - 010, C - 000, D - 011과 같은 코드 워드가 사용되었습니다.
아래 나열된 코드 단어 중 문자 D를 인코딩하는 데 사용할 수 있는 코드 단어를 나타냅니다.
코드는 명확한 디코딩 특성을 충족해야 합니다. 두 개 이상의 코드워드를 사용할 수 있는 경우 가장 짧은 코드워드를 입력하십시오.
1) 00 2) 01 3) 0000 4) 101
5-85. 문자 U, CH, E, N, I 및 K로 구성된 특정 시퀀스를 인코딩하려면 고르지 않은 이진 접두사 코드가 사용됩니다. 코드는 다음과 같습니다: U – 000, Ch – 001, E – 010, N – 100, I – 011, K – 11. 문자 중 하나에 대한 코드 단어의 길이를 줄여 코드가 여전히 유지되도록 할 수 있습니까? 접두사로 남아 있습니까? 나머지 문자의 코드는 변경되어서는 안됩니다. 선택하다 올바른 옵션답변.
메모. 접두사 코드는 코드 단어가 다른 코드 단어의 시작이 아닌 코드입니다. 이러한 코드를 사용하면 결과 이진 시퀀스를 명확하게 디코딩할 수 있습니다.
1) 문자 E의 코드 워드는 01로 단축될 수 있습니다.
2) 문자 K의 코드워드는 1로 줄어들 수 있습니다.
3) 문자 N의 코드워드는 10으로 줄어들 수 있습니다.
4) 이것은 불가능하다
5-94. 문자 A, B, C, D로 구성된 특정 시퀀스를 인코딩하기 위해 그들은 Fano 조건을 만족하는 비균일 이진 코드를 사용하기로 결정했습니다. 문자 A에는 코드워드 1이 사용되었고, 문자 B에는 코드워드 011이 사용되었습니다. 4개의 코드워드 중 가능한 가장 짧은 총 길이는 얼마입니까?
5-74. 4개의 문자만 포함된 메시지는 E, H, O, T의 통신 채널을 통해 전송됩니다. 모든 메시지에서 가장 많은 문자는 O이고, 다음으로 가장 흔한 문자는 E, N입니다. 문자 T는 다른 문자보다 덜 일반적입니다. . 메시지를 전송하려면 명확한 디코딩을 허용하는 균일하지 않은 이진 코드를 사용해야 합니다. 메시지는 가능한 한 짧아야 합니다. 암호 작성자는 아래 나열된 코드 중 하나를 사용할 수 있습니다. 그는 어떤 코드를 선택해야 할까요?
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 – 10, E – 111, T – 110
5-105. 메시지는 통신 채널을 통해 전송되며 각 메시지에는 A 15자, B 10자, C 6자, G 4자가 포함되어 있습니다(메시지에 다른 문자는 없습니다). 각 문자는 이진 시퀀스로 인코딩됩니다. 코드를 선택할 때 두 가지 요구 사항이 고려되었습니다.
a) 하나의 코드 단어가 다른 코드 단어의 시작이 아닙니다(이는 코드가 명확한 디코딩을 허용하는 데 필요합니다).
b) 인코딩된 메시지의 전체 길이는 가능한 짧아야 합니다.
문자 A, B, C, D를 인코딩하려면 다음 중 어떤 코드를 선택해야 합니까?
1) A:1, B:01, C: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
5-102. 메시지에는 10개의 서로 다른 문자가 있습니다. 전송할 때 고르지 않은 이진 접두사 코드가 사용됩니다. 세 글자의 코드는 11, 100, 101로 알려져 있습니다. 나머지 일곱 글자의 코드는 길이가 같습니다. 10개 코드워드의 최소 총 길이는 얼마입니까?
5-104. 메시지에는 A 50자, B 30자, C 20자, G 5자가 포함되어 있습니다. 전송 시 고르지 않은 이진 접두사 코드가 사용되어 인코딩된 메시지의 최소 길이를 얻을 수 있었습니다. 비트 단위로 어떤가요?
5개의 문자만 포함된 메시지는 A, B, C, D, E의 통신 채널을 통해 전송됩니다. 전송에는 명확한 디코딩을 허용하는 이진 코드가 사용됩니다. 문자 A, B, C의 경우 A – 111, B – 0, C – 100과 같은 코드 워드가 사용됩니다.
코드가 명확한 디코딩을 허용하는 문자 D에 대해 가장 짧은 코드워드를 지정하십시오. 해당 코드가 여러 개인 경우 숫자 값이 가장 낮은 코드를 표시하십시오.
9-1-23. 래스터 256색을 변환한 후 그래픽 파일 16색 형식에서는 크기가 15KB만큼 줄었습니다. 사이즈는 얼마였나요? 소스 파일 KB로?
9-1-25. 래스터 그래픽 파일을 변환한 후 볼륨이 1.5배 감소했습니다. 변환 후 얻은 경우 처음에 팔레트에 몇 개의 색상이 있었습니까? 래스터 이미지 16색 팔레트에서 동일한 해상도를 사용합니까?
13-37. 에 등록할 때 컴퓨터 시스템각 사용자에게는 8자로 구성된 식별자가 발급되며, 첫 번째와 마지막은 18자 중 하나이고 나머지는 숫자입니다(10자 허용). 십진수). 이러한 각 식별자는 컴퓨터 프로그램가능한 최소 및 동일한 정수 바이트 수로 기록됩니다(문자별 인코딩이 사용됩니다. 모든 숫자는 동일하고 가능한 최소 비트 수로 인코딩됩니다. 모든 문자도 동일하고 가능한 최소 비트 수로 인코딩됩니다. 비트). 500개의 비밀번호를 기록하기 위해 이 프로그램에서 할당한 메모리 양을 바이트 단위로 결정합니다.
13-38. 팀 올림피아드에 사용되는 컴퓨터 시스템에 등록할 때 각 학생에게는 고유 식별자– 1부터 1000까지의 정수. 각 식별자를 저장하는 데는 동일하고 가능한 최소 비트 수가 사용됩니다. 팀 ID는 순차적으로 기록되는 학생 ID와 8개의 ID로 구성됩니다. 추가 비트. 시스템은 동일하고 최소 바이트 수를 사용하여 각 명령 ID를 기록합니다. 모든 팀에는 동일한 수의 참가자가 있습니다. 참가하는 20개 팀의 ID를 저장하는 데 180바이트가 걸린다면 각 팀의 구성원은 몇 명입니까?
13-50. 컴퓨터 시스템에 등록할 때 각 사용자에게는 A, B, C, D, E, F, G, H, K, L, M, N. 데이터베이스에서는 각 사용자에 대한 정보를 저장하는 데이터에는 동일하고 가능한 최소 정수 바이트가 할당됩니다. 이 경우 비밀번호의 문자별 인코딩이 사용되며 모든 문자는 동일하고 가능한 최소 비트 수로 인코딩됩니다. 비밀번호 자체 외에도 추가 정보가 각 사용자에 대해 시스템에 저장되며 여기에 정수 바이트가 할당됩니다. 이 번호는 모든 사용자에게 동일합니다. 20명의 사용자에 대한 정보를 저장하려면 300바이트가 필요합니다. 저장에 할당된 바이트 수 추가 정보한 명의 사용자 정도? 답변에는 정수(바이트 수)만 적어 두십시오.
16-165. 의미 산술 표현: 9 22 + 3 66 – 18 이 표기법에는 "2"의 숫자가 몇 개 있습니까?
자연스럽게 질문이 생깁니다. 디코딩이 항상 고유한 비균일 코드가 있습니까? 예, 존재합니다.
로버트 파노다음을 공식화했습니다. 충분조건코드에 명확한 디코딩이 있는지 확인합니다. 어떤 코드워드도 다른 코드워드의 시작이 아닙니다.이 조건이 충족되면 디코딩에 문제가 없습니다.
허락하다 A 1, A 2그리고 A 3- 일부 알파벳 위의 단어는 다음과 같습니다. A 1=2 3, 그건 A 1에서 얻은 A 2간단히 단어만 추가하면 A 3(단어 A 2또는 A 3단일 문자일 수 있음). 단어의 이름을 지정하자 A 2, 이는 단어의 첫 부분입니다. A 1, 접두사단어 A 1. 예를 들어, 단어의 경우 11101101 접두사는 단어가 될 것입니다 1110110 , 111011 , 11101 , 1110 , 111 , 11 , 1 .
그러면 코드에 대한 Fano 조건은 다음과 같이 공식화될 수 있습니다.
어떤 코드워드도 다른 코드워드의 접두어가 아닙니다..
Fano 조건을 만족하는 코드를 호출합니다. 접두사. 따라서 코드 앞에 접두사가 있으면 명확한 디코딩이 가능합니다.
예를 들어, 코드워드로 구성된 코드 {0, 10, 11} 는 접두사이며 다음 코드 시퀀스입니다. 01001101110 유일한 방법으로 코드 단어로 나눌 수 있습니다. 0 10 0 11 0 11 10 .
코드워드로 구성된 코드 {0, 10, 11, 100} , 접두사가 붙지 않으며 명확한 디코딩을 허용하지 않습니다. 실제로 동일한 시퀀스를 코드 단어로 나눌 수 있습니다. 다른 방법들: 0 10 0 11 0 11 10 또는 0 100 11 0 11 10 .
Fano 조건은 코드에 대한 명확한 디코딩을 위한 충분조건일 뿐 필수조건은 아니라는 점에 유의하는 것이 중요합니다.
예를 들어, 단 두 개의 코드워드로 구성된 간단한 코드 {1, 10} 는 분명히 접두사는 아니지만 이 코드로 인코딩하여 얻은 모든 코드 시퀀스를 명확하게 디코딩합니다. 실제로 이러한 순서에서는 두 개의 0이 나란히 나타날 수 없습니다. 그런 다음 각 0을 두 번째 코드 단어의 역 이미지로 앞의 단위로 바꾸고 나머지 모든 것을 첫 번째 단어의 역 이미지로 대체하면 이는 명확한 디코딩이 됩니다.
다른 것들도 있고 그 이하도 있어요 간단한 코드, 동일한 속성을 가지고 있습니다. 예를 들어, 코드 {01,10,011} 또한 접두사가 붙지 않지만 명확한 디코딩이 있습니다(직접 증명해 보세요).
Fano 조건이 만족되지 않으면 코드가 고유하게 디코딩 가능한지 어떻게 확인할 수 있습니까? 다음 방법을 사용할 수 있습니다.
말을 하자 A 2~이다 접두사단어 A 1. 그 다음에 A 1=2 3, 어디 A 3어떤 단어, 단어의 마지막 부분 A 1. 전화하자 3 접미사몇 마디 A 1그리고 A 2, 그 중 하나는 다른 하나의 접두사이고 쌍 자체는 A 1그리고 A 2전화하자 접두사.
주어진 코드에서 코드워드의 모든 접두어 쌍을 고려하고 이들로부터 모든 접미어 세트를 구성해 보겠습니다. 다음으로 우리는 모든 접두사 쌍을 고려합니다. 그 중 하나는 코드 단어이고 다른 하나는 접미사이며, 접미사 세트를 확장하여 접미사를 구성합니다. 새로운 접미사가 더 이상 나타나지 않을 때까지 이 과정을 계속하겠습니다. 코드워드와 일치하는 접미사가 없는 경우에만 코드를 고유하게 디코딩할 수 있습니다.
예를 들어, 코드의 경우 {01,10,011} 많은 접미사가있을 것입니다 {1,0,11} . 여기에 있는 단일 접미사는 코드 단어와 일치하지 않으므로 이 코드는 고유하게 디코딩 가능하다고 주장할 수 있습니다.
작업 1.다음 코드가 고유한 디코딩 속성을 가지고 있는지 확인합니다. a) {110, 11, 100, 00, 10} 비) {100, 001, 101, 1101, 11011} .
접두사가 아닌 코드로 얻은 디코딩 시퀀스는 접두사 코드보다 더 복잡한 분석이 필요합니다. 접두사 코드가끔 불린다 즉각적인(즉시 디코딩 가능) 왜냐하면 코드 시퀀스를 읽을 때 단어의 마지막 기호에 도달하면 코드 단어의 끝이 즉시 인식되기 때문입니다. 이것이 접두사 코드의 장점입니다.
2019 통합 상태 시험의 데모 버전 – 작업 번호 5
문자 A, B, C, D, D, E로 구성된 특정 시퀀스를 인코딩하기 위해 Fano 조건을 만족하는 비균일 이진 코드를 사용하기로 결정했습니다. 문자 A의 경우 코드 워드 0이 사용되었습니다. 문자 B의 경우 – 코드 워드 10. 문자 B, D, D, E의 코드 워드 길이의 가능한 가장 작은 합은 얼마입니까?
메모. Fano 조건은 코드워드가 다른 코드워드의 시작이 아님을 의미합니다. 이를 통해 암호화된 메시지를 명확하게 해독할 수 있습니다.
해결책:
답변:
2018 통합 상태 시험의 데모 버전 – 작업 번호 5
10개의 문자만 포함된 암호화된 메시지는 A, B, E, I, K, L, R, S, T, U 통신 채널을 통해 전송됩니다. 전송에는 고르지 않은 이진 코드가 사용됩니다. 코드어는 9글자에 사용됩니다.
코드가 Fano 조건을 만족하도록 문자 B에 대한 가장 짧은 코드워드를 나타냅니다. 해당 코드가 여러 개인 경우 숫자 값이 가장 낮은 코드를 표시하십시오. 메모. Fano 조건은 코드워드가 다른 코드워드의 시작이 아님을 의미합니다. 이를 통해 암호화된 메시지를 명확하게 해독할 수 있습니다.
해결책:
답: 1100
문자 A, B, C, D, D, E로 구성된 특정 시퀀스를 인코딩하기 위해 Fano 조건을 만족하는 비균일 이진 코드를 사용하기로 결정했습니다. 문자 A의 경우 코드 워드 0이 사용되었습니다. 문자 B – 코드 단어 10의 경우. 6개 코드 단어의 길이를 모두 더한 가장 작은 합은 얼마입니까?
메모. Fano 조건은 코드워드가 다른 코드워드의 시작이 아님을 의미합니다. 이를 통해 암호화된 메시지를 명확하게 해독할 수 있습니다.
2017년 통합 상태 시험의 데모 버전 - 작업 번호 5
해결책:
코드 단어를 찾기 위해 우리는 이 표를 사용할 것입니다.
나머지 문자의 코드가 0으로 시작하는 경우 문자 A=0의 코드가 해당 코드의 시작이 되므로 이 옵션은 적합하지 않습니다. 코드 B = 10이면 문자 B, 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
2016 통합 상태 시험의 데모 버전 – 작업 번호 5
네 글자만 포함된 메시지는 통신 채널(P, O, S, T)을 통해 전송됩니다. 전송에는 명확한 디코딩을 허용하는 이진 코드가 사용됩니다. 문자 T, O, P의 경우 T: 111, O: 0, P: 100과 같은 코드 워드가 사용됩니다.
코드가 명확한 디코딩을 허용하는 문자 C에 대해 가장 짧은 코드 단어를 지정하십시오. 해당 코드가 여러 개인 경우 숫자 값이 가장 낮은 코드를 표시하십시오.
해결책:
코드 단어를 찾기 위해 우리는 이 체계를 사용할 것입니다.
나머지 문자의 코드가 다음으로 시작하는 경우 0 , 문자 코드 에 대한=0 코드의 시작 부분이 되므로 이 옵션은 적합하지 않습니다. 문자코드부터 피=100 및 문자 코드 티 =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 | 디 | ㅏ |
답: 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에 선행 0이 추가된 이진 표현으로 작성되며 해당 요소의 모듈로 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, Z, K를 인코딩하려면 숫자 0, 1, 2, 3, 4의 이진 코드가 각각 사용됩니다(한 자리 표현의 경우 하나의 중요하지 않은 0이 보존됨). 이러한 방식으로 BARRIER 문자 시퀀스를 인코딩하고 결과를 16진수 코드로 작성하면 다음과 같은 결과를 얻게 됩니다.
1) 4531253 2) 9876 3) E832 4) 238E
해결책:
| 에 대한 | 엘 | ㅏ | 지 | 에게 |
| 0=00 | 1=01 | 2=10 | 3=11 | 4=100 |
장벽 = 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, C-101, D-100, D-?
답: 2
4개의 문자만 포함하는 메시지는 통신 채널 A, B, C, D를 통해 전송됩니다. 문자 A, B, C를 인코딩하려면 A - 10110, B - 11000, C - 00101의 5비트 코드 단어가 사용됩니다. 이 코드 세트의 경우 단어는 다음과 같은 속성을 갖습니다. 세트의 두 단어는 적어도 세 위치에서 다릅니다. 이 속성은 간섭이 있을 때 메시지를 해독하는 데 중요합니다. 다음 중 문자 G에 사용할 수 있는 코드 단어 중 지정된 속성이 네 개의 코드 단어 모두에 대해 유지되도록 할 수 있는 코드 단어는 무엇입니까?
1) 01110 2) 01011 3) 10001 4) 위 단어 중 어느 것도 적합하지 않음
해결책:
1) 01 110: A - 10 110 - 최소 3개 위치에서 다르지 않음
2) 01011: A - 101 10, B - 1 1000, C - 0010 1 - 최소 3개 위치에서 다름
답: 2
5비트 코드는 통신 채널을 통해 데이터를 전송하는 데 사용됩니다. 메시지에는 다음 코드 단어로 인코딩된 문자 A, B 및 C만 포함되어 있습니다.
A - 10001, B - 01101, C - 10110.
전송 중에 간섭이 발생할 수 있습니다. 그러나 일부 오류를 수정해 볼 수는 있습니다. 이거 둘 중 아무거나 세 가지 코드단어는 적어도 세 가지 위치에서 서로 다릅니다. 따라서 단어를 전송할 때 최대 한 위치에서 오류가 발생하면 어떤 문자가 전송되었는지에 대해 교육적인 추측을 할 수 있습니다. (“코드는 하나의 오류를 정정한다”고 합니다.) 예를 들어 코드워드 01111이 수신되면 문자 B가 전송된 것으로 간주됩니다. (B에 대한 코드워드와의 차이점은 한 위치에만 있습니다. 다른 코드워드는 더 많은 차이가 있습니다.) 수신된 코드워드와 문자 A, B, C에 대한 코드워드와 두 위치 이상 다를 경우 오류가 발생한 것으로 간주합니다('로 표시함). 엑스').
수신된 메시지는 00110 11101 11000 11001입니다. 이 메시지를 해독하세요. 올바른 옵션을 선택하세요.
1) VBxx 2) VBVA 3) xxxx 4) VBxA
해결책:
| 00110 | 11101 | 11000 | 11001 |
| B=1 0110 | B=0 1101 | 엑스 | A=10,001 |
답: 4
문자 A, B, C, D 및 D로 구성된 특정 시퀀스를 인코딩하려면 균일하지 않은 이진 코드가 사용되므로 결과 이진 시퀀스를 명확하게 디코딩할 수 있습니다. 코드는 다음과 같습니다. A – 1; B – 0100; B – 000; G – 011; D – 0101. 코드를 여전히 명확하게 디코딩할 수 있도록 문자 중 하나에 대한 코드 워드의 길이를 줄여야 합니다. 나머지 문자의 코드는 변경되어서는 안됩니다. 어느 것 위의 방법그것은 할 수 있습니까?
1) 문자 G – 11의 경우 2) 문자 B – 00의 경우 3) 문자 G – 01의 경우 4) 이는 불가능합니다.
해결책:
답: 2
문자 A, B, C, D로 구성된 특정 시퀀스를 인코딩하기 위해 그들은 Fano 조건을 만족하는 비균일 이진 코드를 사용하기로 결정했습니다. 문자 A에는 코드워드 1이 사용되었고, 문자 B에는 코드워드 011이 사용되었습니다. 4개의 코드워드 중 가능한 가장 짧은 총 길이는 얼마입니까?
1) 7 2) 8 3) 9 4) 10
해결책:
A-1, B-011, B-00, G-010
답: 9
메시지는 통신 채널을 통해 전송되며 각 메시지에는 A 15자, B 10자, C 6자, G 4자가 포함되어 있습니다(메시지에 다른 문자는 없습니다). 각 문자는 이진 시퀀스로 인코딩됩니다. 코드를 선택할 때 두 가지 요구 사항이 고려되었습니다.
a) 하나의 코드 단어가 다른 코드 단어의 시작이 아닙니다(이는 코드가 명확한 디코딩을 허용하는 데 필요합니다).
b) 인코딩된 메시지의 전체 길이는 가능한 짧아야 합니다.
문자 A, B, C, D를 인코딩하려면 다음 중 어떤 코드를 선택해야 합니까?
1) A:1, B:01, C: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
해결책:
두 코드 단어 모두 다른 코드 단어의 시작이 아닙니다. ㅏ시작이다 G첫 번째와 두 번째 옵션에서.
인코딩된 메시지의 전체 길이는 가능한 한 짧아야 합니다.
3) A:00(15), B:01(10), C:10(6), D:11(4)
2.15+2.10+2.6+2.4 = 70
4) A:100(15), B:101(10), C:11(6), D:0(4)
3.15+3.10+2.6_1.4 = 61
답: 3
유니폼을 이용한 커뮤니케이션 채널을 통해 바이너리 코드 P, R, S, T 4개의 문자만 포함하는 메시지가 전송됩니다. 각 문자에는 고유한 코드 단어가 있으며 코드 단어 집합의 경우 다음 속성이 충족됩니다. 집합의 두 단어는 최소 세 위치에서 다릅니다. 이 속성은 간섭이 있을 때 메시지를 해독하는 데 중요합니다. 문자 P, P, C를 인코딩하려면 5비트 코드워드가 사용됩니다: P: 01111, P: 00001, C: 11000. 문자 T의 5비트 코드는 1로 시작하고 0으로 끝납니다. 문자 T.
해결책:
에스: 1 1000
전화: 1 011 0 (T는 1로 시작하고 0으로 끝납니다)
S와 T: 2개의 문자가 동일합니다. 이는 나머지 3개의 문자가 달라야 함을 의미합니다.
답변: 1 0110